Namensräume
Varianten
Aktionen

std::upper_bound

Von cppreference.com
< cpp‎ | algorithm
 
C++
 
Algorithmenbibliothek
Beschränkte Algorithmen und Algorithmen für Bereiche (C++20)
Beschränkte Algorithmen, z.B. ranges::copy, ranges::sort, ...
Ausführungsrichtlinien (C++17)
Nicht-modifizierende Sequenzoperationen
Stapeloperationen
(C++17)
Suchoperationen
(C++11)                (C++11)(C++11)

Modifizierende Sequenzoperationen
Kopieroperationen
(C++11)
(C++11)
(C++11)
Tauschoperationen
Transformationsoperationen
Generierungsoperationen
Entfernungsoperationen
Ordnungsändernde Operationen
(bis C++17)(C++11)
(C++20)(C++20)
Stichprobenoperationen
(C++17)

Sortier- und verwandte Operationen
Partitionierungsoperationen
Sortieroperationen
Binäre Suchoperationen
(auf partitionierten Bereichen)
upper_bound
Mengenoperationen (auf sortierten Bereichen)
Zusammenführungsoperationen (auf sortierten Bereichen)
Heapoperationen
Minimum/Maximum-Operationen
(C++11)
(C++17)
Lexikographische Vergleichsoperationen
(C++20)
Permutationsoperationen
C-Bibliothek
Numerische Operationen
Operationen auf uninitialisiertem Speicher
 
Definiert in Header <algorithm>
(1)
template< class ForwardIt, class T >

ForwardIt upper_bound( ForwardIt first, ForwardIt last,

                       const T& value );
 (constexpr seit C++20)
(bis C++26)
template< class ForwardIt, class T = typename std::iterator_traits

                                         <ForwardIt>::value_type >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last,

                                 const T& value );
 (seit C++26)
(2)
template< class ForwardIt, class T, class Compare >

ForwardIt upper_bound( ForwardIt first, ForwardIt last,

                       const T& value, Compare comp );
 (constexpr seit C++20)
(bis C++26)
template< class ForwardIt, class T = typename std::iterator_traits

                                         <ForwardIt>::value_type,
          class Compare >
constexpr ForwardIt upper_bound( ForwardIt first, ForwardIt last,

                                 const T& value, Compare comp );
 (seit C++26)

Sucht das erste Element im partitionierten Bereich [first, last), das nach value geordnet ist.

1) Die Ordnung wird durch operator< bestimmt.

Gibt den ersten Iterator iter im Bereich [first, last) zurück, für den bool(value < *iter) true ist, oder last, falls kein solcher iter existiert.

Wenn die Elemente elem im Bereich [first, last) nicht bezüglich des Ausdrucks bool(value < elem) partitioniert sind, ist das Verhalten undefiniert.

 (bis C++20)

Entspricht std::upper_bound(first, last, value, std::less{}).

 (seit C++20)
2) Die Ordnung wird durch comp bestimmt.
Gibt den ersten Iterator iter im Bereich [first, last) zurück, für den bool(comp(value, *iter)) true ist, oder last, falls kein solcher iter existiert.
Wenn die Elemente elem im Bereich [first, last) nicht bezüglich des Ausdrucks bool(comp(value, elem)) partitioniert sind, ist das Verhalten undefiniert.

Inhalt

[edit] Parameter

first, last - das Iterator-Paar, das den partitionierten Bereich der zu untersuchenden Elemente definiert
value - Wert, mit dem die Elemente verglichen werden sollen
comp - Binäres Prädikat, das **wahr** zurückgibt, wenn das erste Argument vor dem zweiten geordnet ist.

Die Signatur der Prädikatfunktion sollte äquivalent zur folgenden sein:

 bool pred(const Type1 &a, const Type2 &b);

Obwohl die Signatur nicht zwingend const & haben muss, darf die Funktion die ihr übergebenen Objekte nicht modifizieren und muss alle Werte vom Typ (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt, ebenso wenig wie Type1, es sei denn, für Type1 ist eine Verschiebung gleichbedeutend mit einer Kopie(seit C++11)).
Der Typ Type1 muss so beschaffen sein, dass ein Objekt vom Typ T implizit in Type1 konvertiert werden kann. Der Typ Type2 muss so beschaffen sein, dass ein Objekt vom Typ ForwardIt dereferenziert und dann implizit in Type2 konvertiert werden kann. ​

Typanforderungen
-
ForwardIt muss die Anforderungen von LegacyForwardIterator erfüllen.
-
Compare muss die Anforderungen an ein Binäres Prädikat erfüllen. Es muss nicht Compare erfüllen.

[edit] Rückgabewert

Iterator auf das erste Element des Bereichs [first, last), das nach value geordnet ist, oder last, falls kein solches Element gefunden wird.

[edit] Komplexität

Gegeben sei N als std::distance(first, last).

1) Höchstens log2(N)+O(1) Vergleiche mit value unter Verwendung von operator<
2) Höchstens log2(N)+O(1) Anwendungen des Vergleichers comp.

Wenn jedoch ForwardIt kein LegacyRandomAccessIterator ist, ist die Anzahl der Iterator-Inkremente linear in N. Insbesondere sind Iteratoren von std::map, std::multimap, std::set und std::multiset keine Zufallszugriffsiteratoren, daher sollten deren Member-Funktionen upper_bound bevorzugt werden.

[edit] Mögliche Implementierung

Siehe auch die Implementierungen in libstdc++ und libc++.

upper_bound (1) 
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value)
{
    return std::upper_bound(first, last, value, std::less{});
}
upper_bound (2) 
template<class ForwardIt, class T = typename std::iterator_traits<ForwardIt>::value_type,
         class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0)
    {
        it = first; 
        step = count / 2;
        std::advance(it, step);
 
        if (!comp(value, *it))
        {
            first = ++it;
            count -= step + 1;
        } 
        else
            count = step;
    }
 
    return first;
}

[edit] Hinweise

Obwohl std::upper_bound nur eine Partitionierung des Bereichs [first, last) erfordert, wird dieser Algorithmus normalerweise in Fällen verwendet, in denen der Bereich [first, last) sortiert ist, so dass die binäre Suche für jedes value gültig ist.

Für jeden Iterator iter im Bereich [first, last) erfordert std::upper_bound, dass value < *iter und comp(value, *iter) wohlgeformt sind, während std::lower_bound stattdessen erfordert, dass *iter < value und comp(*iter, value) wohlgeformt sind.

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

[edit] Beispiel

Führen Sie diesen Code aus
#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <vector>
 
struct PriceInfo { double price; };
 
int main()
{
    const std::vector<int> data{1, 2, 4, 5, 5, 6};
 
    for (int i = 0; i < 7; ++i)
    {
        // Search first element that is greater than i
        auto upper = std::upper_bound(data.begin(), data.end(), i);
 
        std::cout << i << " < ";
        upper != data.end()
            ? std::cout << *upper << " at index " << std::distance(data.begin(), upper)
            : std::cout << "not found";
        std::cout << '\n';
    }
 
    std::vector<PriceInfo> prices{{100.0}, {101.5}, {102.5}, {102.5}, {107.3}};
 
    for (double to_find : {102.5, 110.2})
    {
        auto prc_info = std::upper_bound(prices.begin(), prices.end(), to_find,
            [](double value, const PriceInfo& info)
            {
                return value < info.price;
            });
 
        prc_info != prices.end()
            ? std::cout << prc_info->price << " at index " << prc_info - prices.begin()
            : std::cout << to_find << " not found";
        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 = std::upper_bound(nums.cbegin(), nums.cend(), {2, 0}, cmpz);
    #else
        auto it = std::upper_bound(nums.cbegin(), nums.cend(), CD{2, 0}, cmpz);
    #endif
    assert((*it == CD{3, 0}));
}

Ausgabe

0 < 1 at index 0
1 < 2 at index 1
2 < 4 at index 2
3 < 4 at index 2
4 < 5 at index 3
5 < 6 at index 5
6 < not found 
107.3 at index 4
110.2 not found

[edit] Fehlerberichte

Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR angewendet auf Verhalten wie veröffentlicht Korrigiertes Verhalten
LWG 270 C++98 Compare musste Compare erfüllen und T musste
LessThanComparable sein (starke schwache Ordnung erforderlich)		 nur eine Partitionierung ist erforderlich;
heterogene Vergleiche zulässig
LWG 384 C++98 es waren höchstens log2(N)+1 Vergleiche erlaubt korrigiert zu log2(N)+O(1)
LWG 577 C++98 last konnte nicht zurückgegeben werden erlaubt
LWG 2150 C++98 wenn irgendein Iterator iter im Bereich [first, last) existiert, so dass
bool(comp(value, *iter)) true ist, konnte std::upper_bound
jeden Iterator im Bereich [iter, last) zurückgeben		 kein Iterator nach
iter kann zurückgegeben werden

[edit] Siehe auch

 gibt den Bereich von Elementen zurück, die einem bestimmten Schlüssel entsprechen
(Funktionstemplate) [edit]
 Gibt einen Iterator zum ersten Element zurück, das nicht kleiner als der gegebene Wert ist
(Funktionstemplate) [edit]
 Teilt einen Bereich von Elementen in zwei Gruppen auf
(Funktionstemplate) [edit]
(C++11)
 Findet den Partitionierungspunkt eines partitionierten Bereichs
(Funktionstemplate) [edit]
(C++20)
 Gibt einen Iterator zum ersten Element zurück, das *größer* als ein bestimmter Wert ist
(Algorithmus-Funktionsobjekt)[edit]
 gibt einen Iterator zum ersten Element zurück, das *größer* als der gegebene Schlüssel ist
(public member function of std::set<Key,Compare,Allocator>) [edit]
 gibt einen Iterator zum ersten Element zurück, das *größer* als der gegebene Schlüssel ist
(public member function of std::multiset<Key,Compare,Allocator>) [edit]
Abgerufen von "https://cppreference.de/mwiki/index.php?title=cpp/algorithm/upper_bound&oldid=180595"