Begründung für std :: lower_bound und std :: upper_bound?

Wenn Sie mehrere Elemente im Bereich [ first , last), dessen Wert gleich dem Wert val Sie auf der Suche sind, dann wird der Bereich [ l , u), wo

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

ist genau die Anzahl der Elemente, die gleich val im Bereich [firstlast). So l und u sind die "Untergrenze" und "Obergrenze" für die gleichen Bereich. Es macht Sinn, wenn Sie daran gewöhnt sind zu denken in der halb-offenen Intervalle.

(Beachten Sie, dass std::equal_range zurück sowohl die unteren und oberen Grenze in einem paar, in einem einzigen Aufruf.)

InformationsquelleAutor der Antwort Brian

Halte die Reihenfolge

1 2 3 4 5 6 6 6 7 8 9

untere Schranke für die 6 ist die position des ersten 6.

Obere Grenze für die 6 ist die position des 7.

diese Positionen dienen als Allgemeine (begin, end) paar Benennung der Lauf der 6-Werte.

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;
}

InformationsquelleAutor der Antwort Cheers and hth. - Alf

Nahm ich Brians Antwort, aber ich habe gerade realisiert, eine andere hilfreiche Art des Denkens über ist es, das schafft mehr Klarheit für mich, so dass ich bin das hinzufügen dieses für Referenz.

Denke, dass der zurückgegebene iterator als Hinweis, nicht auf das element *iter, aber nur vor , element, d.h. zwischendass element und dem vorherigen element in der Liste, wenn es einen gibt. Denken Sie, dass die Art und Weise, die Verträge der beiden Funktionen symmetrisch werden: lower_bound findet die position des übergangs von <val >=val und upper_bound findet die position des übergangs von <=val >val. Oder um es anders auszudrücken, lower_bound ist der Beginn der Reihe von Elementen, vergleichen, gleich val (d.h. der Bereich, std::equal_range gibt) und upper_bound ist das Ende von Ihnen.

Ich wünschte, Sie würden darüber sprechen, wie diese (oder jede andere gute Antworten gegeben) - in den docs; das würde es viel weniger verwirrend!

InformationsquelleAutor der Antwort Don Hatch

Gibt es bereits gute Antworten darauf, was std::lower_bound und std::upper_boundist.

Ich würde gerne Ihre Frage beantworten ', wie um Sie zu erinnern'?

Seine leicht zu verstehen/merken, wenn wir ziehen eine Analogie mit STL begin() und end() Methoden eines Containers. begin() gibt den Start-iterator für den container, während end() gibt der iterator die nur außerhalb des Behälters, und wir alle wissen, wie hilfreich Sie sind während der Iteration.

Nun, auf einen sortierten container und gegebenen Wert lower_boundund upper_bound zurück Reihe von Iteratoren für diesen Wert einfach zu iterieren (wie begin und end)

Praktische Verwendung::

Neben der oben genannten Verwendung auf sortierte Liste, um die Auswahl für einen gegebenen Wert eines der besseren Anwendungen von upper_bound ist, um auf Daten zuzugreifen, die viele-zu-eins-Beziehung in einer Karte.

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

Den oben genannten 10-mappings eingespart werden können, wie folgt zugeordnet:

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

Die Werte zugegriffen werden kann durch den Ausdruck (--map.upper_bound(val))->second.

Für Werte von T, angefangen von der niedrigsten bis 0, den Ausdruck zurück UND.
Für Werte von T im Bereich von 1 zu 3, wird es wieder 'ein' und so weiter..

Nun, sich vorstellen, wir haben 100te von Daten die Zuordnung zu einem Wert und 100te von solchen Zuordnungen.
Dieser Ansatz reduziert die Größe der Karte und damit effizient.

InformationsquelleAutor der Antwort shainu vy

Ja. Die Frage absolut hat einen Punkt. Wenn jemand hat diese Funktionen Ihre Namen waren Sie denken nur von sortierten arrays mit sich wiederholenden Elementen. Wenn Sie ein array mit eindeutigen Elementen, "std::lower_bound()" wirkt eher wie eine Suche nach einer "oberen Grenze", es sei denn, es findet das eigentliche element.

Also das ist, was ich erinnere mich, über diese Funktionen:

• Wenn du eine binäre Suche, erwägen Sie die Verwendung von std::lower_bound(), und Lesen Sie das Handbuch. std::binary_search() basiert auf es auch.
• Wenn Sie auf der Suche nach dem "Ort" des einen Wert in einem sortierten array mit eindeutigen Werten, betrachten std::lower_bound() und Lesen Sie die Bedienungsanleitung.
• Wenn Sie eine beliebige Aufgabe Suche in einem sortierten array ist, Lesen Sie die Anleitung für beide std::lower_bound() und std::upper_bound().

Andernfalls Lesen Sie das Handbuch nach einem oder zwei Monaten seit der letzten Verwendung dieser Funktionen fast sicher, führt zu einem Fehler.

InformationsquelleAutor der Antwort Angel Sinigersky