gründe für std :: lower_bound und std :: upper_bound?

std::lower_bound

Gibt einen Iterator zurück, der auf das erste Element im Bereich [first, last) zeigt, der nicht kleiner als (d. H. Größer oder gleich) ist.

std::upper_bound

Gibt einen Iterator zurück, der auf das erste Element im Bereich [first, last) zeigt, das größer als Wert ist.

Indem Sie die untere und obere Grenze mischen, können Sie also genau beschreiben, wo Ihr Bereich beginnt und wo er endet.

Ist das sinnvoll?

Ja.

Beispiel:

stellen sie sich vektor vor

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };

auto lower = std::lower_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                  // ^ lower

auto upper = std::upper_bound(data.begin(), data.end(), 4);

1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
                           // ^ upper

std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

drucke: 4 4 4

http://en.cppreference.com/w/cpp/algorithm/lower_bound

http://en.cppreference.com/w/cpp/algorithm/upper_bound

In diesem Fall denke ich, ein Bild sagt mehr als tausend Worte. Angenommen, wir verwenden sie, um in den folgenden Sammlungen nach 2 zu suchen. Die Pfeile zeigen, welche Iteratoren die beiden zurückgeben würden:

Wenn Sie also mehr als ein Objekt mit diesem Wert bereits in der Auflistung haben, gibt Ihnen lower_bound einen Iterator, der sich auf das erste Objekt bezieht, und upper_bound gibt einen Iterator an, der sich unmittelbar auf das Objekt von direkt bezieht Sie.

Dadurch werden (unter anderem) die zurückgegebenen Iteratoren als hint-Parameter für insert verwendet.

Wenn Sie diese als Hinweis verwenden, wird das Element, das Sie einfügen, das neue erste Element mit diesem Wert (wenn Sie lower_bound verwendet haben) oder das letzte Element mit diesem Wert (wenn Sie upper_bound verwendet haben). Wenn die Auflistung zuvor kein Element mit diesem Wert enthielt, wird immer noch ein Iterator angezeigt, der als hint verwendet werden kann, um ihn an der richtigen Stelle in der Auflistung einzufügen.

Natürlich können Sie auch ohne Hinweis einfügen. Mit einem Hinweis erhalten Sie jedoch die Garantie, dass das Einfügen mit konstanter Komplexität abgeschlossen wird, vorausgesetzt, dass das neue Element, das eingefügt werden soll, unmittelbar vor dem Element eingefügt werden kann, auf das der Iterator zeigt (wie es der Fall ist) diese beiden Fälle).

Betrachten Sie die Reihenfolge

1 2 3 4 5 6 6 6 7 8 9

untergrenze für 6 ist die Position der ersten 6.

obergrenze für 6 ist die Position der 7.

diese Positionen dienen als gemeinsames Paar (Anfang, Ende), das den Lauf von 6 Werten angibt.

Beispiel:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

auto main()
    -> int
{
    vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
    auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
    auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
    for( auto it = pos1; it != pos2; ++it )
    {
        cout << *it;
    }
    cout << endl;
}

Ich akzeptierte Brians Antwort, aber ich habe gerade eine andere hilfreiche Denkweise erkannt, die mir Klarheit verleiht. Ich füge dies als Referenz hinzu.

Stellen Sie sich den zurückgegebenen Iterator als zeigend vor, nicht auf das Element * iter, sondern nur vor diesem Element, d. H. Zwischen diesem Element und dem vorhergehenden Element in der Liste (falls vorhanden). Wenn man das so betrachtet, werden die Kontrakte der beiden Funktionen symmetrisch: lower_bound ermittelt die Position des Übergangs von <val nach> = val und upper_bound ermittelt die Position des Übergangs von <= val nach> val. Oder anders ausgedrückt: lower_bound ist der Anfang des Bereichs von Elementen, die mit val verglichen werden (d. H. Der Bereich, den std :: equal_range zurückgibt), und upper_bound ist das Ende von ihnen.

Ich wünschte, sie würden so darüber (oder eine der anderen guten Antworten) in den Dokumenten sprechen. das würde es viel weniger rätselhaft machen!

der Quellcode hat tatsächlich eine zweite Erklärung, die ich sehr hilfreich fand, um die Bedeutung der Funktion zu verstehen:

lower_bound: Findet die Position first , an der [val] eingefügt werden konnte , ohne die Reihenfolge zu ändern.

upper_bound: Findet die letzte Position, an der [ val] eingefügt werden konnte, ohne die Reihenfolge zu ändern.

dies bildet einen Bereich, in den der Wert eingefügt werden kann, wobei jedoch die ursprüngliche Reihenfolge des Containers beibehalten wird

lower_bound return "first", d. h. finde die "untere Grenze des Bereichs"

upper_bound return "last" d. h. finde die "obere Grenze des Bereichs"

Beide Funktionen sind insofern sehr ähnlich, als sie in einer sortierten Reihenfolge einen Einfügepunkt finden, der die Sortierung beibehält. Wenn in der Sequenz keine Elemente vorhanden sind, die dem Suchbegriff entsprechen, wird derselbe Iterator zurückgegeben.

Wenn Sie versuchen, etwas in der Sequenz zu finden, verwenden Sie lower_bound - wenn es gefunden wird, zeigt es direkt auf das Element.

Wenn Sie in die Sequenz einfügen, verwenden Sie upper_bound - die ursprüngliche Reihenfolge der Duplikate bleibt erhalten.

Für ein Array oder einen Vektor:

std :: lower_bound: Gibt einen Iterator zurück, der auf das erste Element in dem Bereich zeigt, das ist 

• kleiner oder gleich dem Wert (für Array oder Vektor in absteigender Reihenfolge)
• größer oder gleich wert (für Array oder Vektor in aufsteigender Reihenfolge)

std :: upper_bound: Gibt einen Iterator zurück, der auf das erste Element in dem Bereich zeigt, das ist

• kleiner als Wert (für Array oder Vektor in absteigender Reihenfolge)

• größer als Wert (für Array oder Vektor in aufsteigender Reihenfolge)

Ja. Die Frage hat absolut einen Punkt. Wenn jemand diesen Funktionen ihre Namen gab, dachte er nur an sortierte Arrays mit sich wiederholenden Elementen. Wenn Sie ein Array mit eindeutigen Elementen haben, verhält sich "std :: lower_bound ()" eher wie eine Suche nach einer "oberen Grenze", es sei denn, es findet das eigentliche Element.

Ich erinnere mich also an diese Funktionen:

• Wenn Sie eine binäre Suche durchführen, sollten Sie std :: lower_bound () verwenden und das Handbuch lesen. Auch std :: binary_search () basiert darauf.
• Wenn Sie den "Ort" eines Werts in einem sortierten Array eindeutiger Werte ermitteln möchten, ziehen Sie std :: lower_bound () in Betracht und lesen Sie das Handbuch.
• Wenn Sie eine beliebige Aufgabe haben, in einem sortierten Array zu suchen, lesen Sie das Handbuch für std :: lower_bound () und std :: upper_bound ().

Wenn Sie das Handbuch nach ein oder zwei Monaten nicht gelesen haben, seit Sie diese Funktionen zum letzten Mal verwendet haben, führt dies höchstwahrscheinlich zu einem Fehler.

Es gibt bereits gute Antworten, was std::lower_bound und std::upper_boundis ist.

Ich würde gerne Ihre Frage beantworten 'Wie erinnere ich mich an sie'?

Es ist leicht zu verstehen/sich zu erinnern, wenn wir eine Analogie mit den STL begin()- und end()-Methoden eines Containers zeichnen. begin() gibt den Start-Iterator an den Container zurück, während end() den Iterator außerhalb des Containers zurückgibt, und wir alle wissen, wie nützlich sie während der Iteration sind.

Für einen sortierten Container und einen bestimmten Wert gibt lower_boundund upper_bound einen Bereich von Iteratoren für diesen Wert zurück, der leicht durchlaufen werden kann (wie Anfang und Ende).

Praktischer Gebrauch ::

Abgesehen von der oben genannten Verwendung einer sortierten Liste, um auf den Bereich für einen gegebenen Wert zuzugreifen, besteht eine der besseren Anwendungen von upper_bound darin, auf Daten zuzugreifen, die eine Viele-zu-Eins-Beziehung in einer Karte haben.

Betrachten Sie zum Beispiel die folgende Beziehung: 1 -> a, 2 -> a, 3 -> a, 4 -> b, 5 -> c, 6 -> c, 7 -> c, 8 -> c , 9 -> c, 10 -> c

Die obigen 10 Zuordnungen können wie folgt in der Karte gespeichert werden:

numeric_limits<T>::lowest() : UND
1 : a
4 : b
5 : c
11 : UND

Auf die Werte kann mit dem Ausdruck (--map.upper_bound(val))->second zugegriffen werden.

Für Werte von T im Bereich von niedrigsten bis 0 gibt der Ausdruck UND..__ zurück. Für Werte von T im Bereich von 1 bis 3 gibt es 'a' usw. zurück.

Stellen Sie sich nun vor, wir haben Hunderte von Daten, die einem Wert zugeordnet werden können, und Hunderten solcher Zuordnungen. Dieser Ansatz reduziert die Größe der Karte und macht sie dadurch effizient.

Stellen Sie sich vor, was Sie tun würden, wenn Sie das erste Element gleich val in [first, last) finden möchten. Sie schließen zuerst die ersten Elemente aus, die strikt kleiner als val sind, und dann rückwärts vom letzten - 1 diejenigen, die strikt größer als val sind. Der verbleibende Bereich ist dann [lower_bound, upper_bound]