Namespaces
Variants

std::ranges:: upper_bound

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Constrained algorithms
All names in this menu belong to namespace std::ranges
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations (on sorted ranges)
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutation operations
Fold operations
Operations on uninitialized storage
Return types
(Anmerkung: Der bereitgestellte HTML-Code enthält keinen übersetzbaren Text, da alle Tags leer sind oder nur Klassenattribute enthalten, die nicht übersetzt werden sollen.)
Definiert im Header <algorithm>
Aufrufsignatur
(1)
template < std:: forward_iterator I, std:: sentinel_for < I > S,

class T, class Proj = std:: identity ,
std:: indirect_strict_weak_order
< const T * , std :: projected < I, Proj >> Comp = ranges:: less >
constexpr I upper_bound ( I first, S last, const T & value,

Comp comp = { } , Proj proj = { } ) ;
(seit C++20)
(bis C++26)
template < std:: forward_iterator I, std:: sentinel_for < I > S,

class Proj = std:: identity ,
class T = std :: projected_value_t < I, Proj > ,
std:: indirect_strict_weak_order
< const T * , std :: projected < I, Proj >> Comp = ranges:: less >
constexpr I upper_bound ( I first, S last, const T & value,

Comp comp = { } , Proj proj = { } ) ;
(seit C++26)
(2)
template < ranges:: forward_range R,

class T, class Proj = std:: identity ,
std:: indirect_strict_weak_order
< const T * , std :: projected < ranges:: iterator_t < R > ,
Proj >> Comp = ranges:: less >
constexpr ranges:: borrowed_iterator_t < R >

upper_bound ( R && r, const T & value, Comp comp = { } , Proj proj = { } ) ;
(seit C++20)
(bis C++26)
template < ranges:: forward_range R,

class Proj = std:: identity ,
class T = std :: projected_value_t < ranges:: iterator_t < R > , Proj > ,
std:: indirect_strict_weak_order
< const T * , std :: projected < ranges:: iterator_t < R > ,
Proj >> Comp = ranges:: less >
constexpr ranges:: borrowed_iterator_t < R >

upper_bound ( R && r, const T & value, Comp comp = { } , Proj proj = { } ) ;
(seit C++26)
1) Gibt einen Iterator zurück, der auf das erste Element im Bereich [ first , last ) zeigt, das größer als value ist, oder last falls kein solches Element gefunden wird. Der Bereich [ first , last ) muss bezüglich des Ausdrucks oder ! comp ( value, element ) partitioniert sein, d.h. alle Elemente, für die der Ausdruck true ist, müssen allen Elementen vorausgehen, für die der Ausdruck false ist. Ein vollständig sortierter Bereich erfüllt dieses Kriterium.
2) Gleich wie (1) , verwendet jedoch r als Quellbereich, als würde ranges:: begin ( r ) als first und ranges:: end ( r ) als last verwendet werden.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithm Function Objects (informell bekannt als Niebloids ), das heißt:

Inhaltsverzeichnis

Parameter

first, last - das Iterator-Sentinel-Paar, das den teilweise geordneten Bereich der zu untersuchenden Elemente definiert
r - der teilweise geordnete Bereich, der untersucht werden soll
value - Wert, mit dem die Elemente verglichen werden
pred - Prädikat, das auf die projizierten Elemente angewendet wird
proj - Projektion, die auf die Elemente angewendet wird

Rückgabewert

Iterator, der auf das erste Element zeigt, das größer als value ist, oder last , falls kein solches Element gefunden wird.

Komplexität

Die Anzahl der Vergleiche und Anwendungen der Projektion ist logarithmisch im Abstand zwischen first und last (höchstens log 2 (last - first) + O(1) Vergleiche und Anwendungen der Projektion). Für einen Iterator, der nicht random_access_iterator modelliert, ist die Anzahl der Iterator-Inkremente jedoch linear.

Mögliche Implementierung 

struct upper_bound_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<I, Proj>> Comp = ranges::less>
    constexpr I operator()(I first, S last, const T& value,
                           Comp comp = {}, Proj proj = {}) const
    {
        I it;
        std::iter_difference_t<I> count, step;
        count = ranges::distance(first, last);
        while (count > 0)
        {
            it = first; 
            step = count / 2;
            ranges::advance(it, step, last);
            if (!comp(value, std::invoke(proj, *it)))
            {
                first = ++it;
                count -= step + 1;
            }
            else
                count = step;
        }
        return first;
    }
    template<ranges::forward_range R, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<ranges::iterator_t<R>,
                                           Proj>> Comp = ranges::less>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value,
                       std::ref(comp), std::ref(proj));
    }
};
inline constexpr upper_bound_fn upper_bound;

Hinweise

Feature-Test Makro Wert Std Funktion
__cpp_lib_algorithm_default_value_type 202403 (C++26) Listeninitialisierung für Algorithmen ( 1,2 )

Beispiel

Diesen Code ausführen 
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <iterator>
#include <vector>
int main()
{
    namespace ranges = std::ranges;
    std::vector<int> data{1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6};
    {
        auto lower = ranges::lower_bound(data.begin(), data.end(), 4);
        auto upper = ranges::upper_bound(data.begin(), data.end(), 4);
        ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
    {
        auto lower = ranges::lower_bound(data, 3);
        auto upper = ranges::upper_bound(data, 3);
        ranges::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 0}, {2, 2}, {2, 1}, {3, 0}, {3, 1}};
    auto cmpz = [](CD x, CD y) { return x.real() < y.real(); };
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = ranges::upper_bound(nums, {2, 0}, cmpz);
    #else
        auto it = ranges::upper_bound(nums, CD{2, 0}, cmpz);
    #endif
    assert((*it == CD{3, 0}));
}

Ausgabe: 

4 4 4 
3 3 3 3

Siehe auch

(C++20)
gibt den Bereich der Elemente zurück, die einem bestimmten Schlüssel entsprechen
(Algorithmus-Funktionsobjekt)
(C++20)
gibt einen Iterator zum ersten Element zurück, das nicht kleiner als der gegebene Wert ist
(Algorithmus-Funktionsobjekt)
(C++20)
unterteilt einen Elementbereich in zwei Gruppen
(Algorithmus-Funktionsobjekt)
gibt einen Iterator zum ersten Element zurück, das größer als ein bestimmter Wert ist
(Funktions-Template)