Die Standard-C++ -Programmiersprache-Bibliothek bietet viele nützliche Funktionen für die Arbeit mit Containern. Eine solche Funktion ist lower_bound. Mit dieser Funktion können Sie das erste Element in einem sortierten Container suchen, der mindestens einen angegebenen Wert hat.
Funktion lower_bound ist ein wichtiges Werkzeug bei der Arbeit mit geordneten Datenfolgen wie Vektoren oder Listen. Es ermöglicht Ihnen, Elemente effizient in sortierten Containern zu finden, ohne dass Sie alle Elemente auf der Suche nach dem gewünschten durchlaufen müssen.
Um die Funktion zu verwenden lower_bound Sie müssen den Anfang und das Ende des Containers angeben und den zu suchenden Wert angeben. Die Funktion gibt einen Iterator zurück, der auf das erste Element zeigt, das nicht kleiner als der angegebene Wert ist. Wenn alle Elemente des Containers kleiner als der angegebene Wert sind, gibt die Funktion einen Iterator zurück, der auf das Ende des Containers zeigt.
Die Syntax der Funktion lower_bound in C++
Die Funktion lower_bound in der Programmiersprache C++ wird verwendet, um die Position eines Elements in einem sortierten Bereich zu finden. Die Syntax dieser Funktion ist ziemlich einfach und hat die folgende Form:
iterator lower_bound (Iterator first, Iterator last, const T& val);Hier enthalten die Parameter der lower_bound-Funktion:
- first - Ein Iterator, der auf den Anfang des Bereichs zeigt
- last - Ein Iterator, der auf das Ende des Bereichs zeigt
- val - der Wert des Elements, dessen Position gefunden werden soll
Die lower_bound-Funktion gibt einen Iterator für das erste Element in einem Bereich zurück, der nicht kleiner als der angegebene val-Wert ist. Wenn alle Elemente des Bereichs kleiner als der angegebene Wert sind, gibt die Funktion den Iterator am Ende des Bereichs zurück (Iterator last ).
Parameter der lower_bound-Funktion in C++
Die lower_bound-Funktion in C++ akzeptiert zwei Parameter:
- Erster Parameter - ein Iterator, der auf den Anfang eines Bereichs von Elementen verweist, unter denen Sie die Position zum Einfügen eines neuen Elements finden oder das erste Element finden müssen, das nicht kleiner als der angegebene Wert ist. Ein Iterator kann ein Zeiger oder ein Iteratorobjekt sein, z. B. ein Iterator eines std::vector- oder std::list-Containers.
- Zweiter Parameter - der Wert, für den die Position im Bereich ermittelt werden soll. Der Wert kann ein beliebiger Datentyp sein, der mit Containerelementen vergleichbar ist. Dies kann ein einfacher Typ, eine Struktur oder ein benutzerdefiniertes Objekt sein.
Die lower_bound-Funktion gibt einen Iterator zurück, der auf das erste Element in einem Bereich zeigt, der nicht kleiner als der angegebene Wert ist. Wenn kein solches Element vorhanden ist, wird ein Iterator zurückgegeben, der auf das Ende des Bereichs zeigt.
Der Rückgabewert der Funktion lower_bound in C++
Die Funktion lower_bound() gibt einen Iterator für das erste Element in einem Bereich zurück, der nicht kleiner (oder gleich ist, wenn die Vergleichsoperation fair ist) als der angegebene Wert ist.
- Wenn ein Wert gefunden wird, gibt die Funktion einen Iterator für diesen Wert zurück.
- Wenn kein Wert gefunden wird, aber kleiner als alle Elemente im Bereich ist, gibt die Funktion einen Iterator für das erste Element im Bereich zurück.
- Wenn kein Wert gefunden wird, aber größer als alle Elemente im Bereich ist, gibt die Funktion den Iterator an die Position hinter dem letzten Element zurück.
Die Verwendung der Funktion lower_bound() ist nützlich, wenn Sie eine Position finden oder einen Wert in einen geordneten Container einfügen möchten.
Verwenden Sie die Funktion lower_bound in C ++, um nach einem Element zu suchen
Der Vorteil der Verwendung der Funktion lower_bound besteht darin, dass sie für die Zeit O(logN) funktioniert, wobei N die Anzahl der Elemente im Container ist. Dies macht es zu einem sehr effektiven Werkzeug, um Elemente in großen Containern zu finden.
Um die Funktion lower_bound zu verwenden, muss der Container aufsteigend sortiert werden. Wenn der Container nicht sortierte Daten enthält, muss er vor dem Aufruf der lower_bound-Funktion beispielsweise mit der sort-Funktion sortiert werden.
Lower_bound nimmt zwei Argumente an: Iteratoren am Anfang und Ende des Containers sowie den Wert, für den wir nach der Position suchen. Die Funktion gibt einen Iterator für das erste Element zurück, mit dem ein Bereich beginnt, der nicht kleiner als der angegebene Wert ist.
Sie können die Funktion lower_bound verwenden, um nach einem bestimmten Element zu suchen oder nach der Position zu suchen, an der ein Segment beginnt, das alle Elemente enthält, die nicht kleiner als der angegebene Wert sind.
Beispiel für die Verwendung der lower_bound-Funktion :
#include #include #include int main() vec = ;int target = 6;// Ищем позицию первого элемента, не меньшего 6auto it = std::lower_bound(vec.begin(), vec.end(), target);if (it != vec.end() && *it == target) else return 0;>In diesem Beispiel gibt die Funktion lower_bound einen Iterator für ein Element mit dem Wert 6 zurück, da dieses Element das erste Element im Container ist, das nicht kleiner als 6 ist.
Die Verwendung der lower_bound-Funktion ist eine Möglichkeit, Elemente in einem sortierten Container effizient zu finden, was sie zu einer sehr nützlichen und beliebten Funktion in der C++ - Programmierung macht.
Verwenden Sie die Funktion lower_bound in C ++, um die Einfügeposition eines Elements zu bestimmen
Die Funktion lower_bound in der Programmiersprache C++ ermöglicht es Ihnen, die Einfügeposition eines Elements in einen sortierten Container zu bestimmen. Es führt eine binäre Suche durch und gibt einen Iterator zurück, der auf das erste Element zeigt, das nicht kleiner als der angegebene Wert ist.
Diese Funktion ist nützlich, wenn Sie bestimmen müssen, wo ein neues Element in einem sortierten Array oder Vektor eingefügt werden soll. Es ermöglicht Ihnen, die Einfügeposition effizient zu finden, anstatt aufeinanderfolgend durch alle Elemente des Containers zu gehen.
Die Verwendung der lower_bound-Funktion wird auf die folgenden Schritte reduziert:
- Sortieren Sie den Container, wenn er noch nicht sortiert ist.
- Rufen Sie die Funktion lower_bound auf und übergeben Sie den Anfang und das Ende des Containers sowie den Wert, den Sie einfügen möchten.
- Die Funktion gibt einen Iterator zurück, der auf das erste Element zeigt, das nicht kleiner als der angegebene Wert ist.
Daher befindet sich die Einfügeposition des Elements zwischen dem Element, auf das der zurückgegebene Iterator zeigt, und dem vorherigen Element.
Die Verwendung der lower_bound-Funktion hilft, die Effizienz des Programms bei der Arbeit mit Listen, Arrays oder Vektoren zu erhöhen, insbesondere bei großen Datenmengen. Dadurch können Sie schnell eine Position zum Einfügen neuer Elemente finden, die zur Aufrechterhaltung der Ordnung des Containers erforderlich sind.
Wie funktioniert die Funktion lower_bound in C++ für sortierte Container
Die Funktion lower_bound in C++ wird verwendet, um einen Iterator für ein Element zu suchen, das einen Wert hat, der nicht kleiner ist als der angegebene Wert. Es ist besonders nützlich für die Arbeit mit sortierten Containern wie std::vector oder std::set .
Der Funktionsablauf umfasst die Anwendung eines binären Suchalgorithmus, der das gesuchte Element effektiv in einem sortierten Container findet. Der Algorithmus wählt die Mitte des Containers aus und vergleicht den Wert des Elements mit dem gewünschten Element. Wenn der Wert des Elements kleiner ist als der gesuchte Wert, wird die Suche in der zweiten Hälfte des Containers fortgesetzt, andernfalls wird die Suche in der ersten Hälfte fortgesetzt. Dieser Vorgang wird wiederholt, bis das gesuchte Element gefunden wird oder die Größe des Containers auf Null reduziert wird.
Das Ergebnis der Funktion lower_bound ist ein Iterator für das erste Element, das größer oder gleich dem gewünschten Wert ist. Wenn kein Element gefunden wird, wird ein Iterator für das letzte Element des Containers zurückgegeben.
Die Funktion lower_bound hat eine Zeitkomplexität von O(log n), wobei n die Größe des Containers ist. Dies macht es zu einem effektiven Werkzeug für den Umgang mit großen sortierten Behältern.
Merkmale der Verwendung von lower_bound mit benutzerdefinierten Datentypen
Mit der Funktion lower_bound in C++ können Sie einen bestimmten Wert oder einen Bereich von Werten in einem sortierten Bereich suchen. Die Verwendung dieser Funktion mit benutzerdefinierten Datentypen erfordert jedoch einige Besonderheiten.
Der erste Schritt besteht darin, ein Vergleichskriterium für einen benutzerdefinierten Datentyp zu definieren. Dazu müssen Sie den Vergleichsoperator "kleiner" (<) überladen, der die Beziehung zwischen den Elementen bestimmt.
Wenn Sie die lower_bound-Funktion aufrufen, müssen Sie die Iteratoren an den Anfang und das Ende des sortierten Bereichs sowie den zu suchenden Wert oder Wertebereich übergeben. In diesem Fall verwendet die Funktion einen überladenen Vergleichsoperator, um die Position des gewünschten Werts zu bestimmen.
Bei der Verwendung eines benutzerdefinierten Datentyps muss jedoch berücksichtigt werden, dass lower_bound einen Iterator auf das erste Element zurückgibt, das nicht kleiner als der angegebene Wert ist. Dies kann bedeuten, dass das gesuchte Element möglicherweise nicht im Bereich vorhanden ist, und lower_bound gibt einen Iterator für das nächste Element zurück.
Ein Beispiel:
struct CustomType ;bool operator<(const CustomType& a, const CustomType& b)int main() data = , , , , , , >;// Используем lower_bound для поиска значения 5auto it = std::lower_bound(data.begin(), data.end(), CustomType, [](const CustomType& a, const CustomType& b) < return a.value < b.value; >);std::cout value
In diesem Beispiel sucht lower_bound mit einem überladenen Vergleichsoperator nach dem Wert 5 im data-Vektor. Am Ende gibt die Funktion einen Iterator für das erste Element zurück, nicht kleiner als 5, dh für das Element mit dem Wert 5.
Die Verwendung von lower_bound mit benutzerdefinierten Datentypen erfordert die Definition eines Vergleichsoperators und die Berücksichtigung der Eigenschaften des zurückgegebenen Iterators. Auf diese Weise können Sie Daten basierend auf benutzerdefinierten Typen suchen und bearbeiten.
Beispiele für die Verwendung der Funktion lower_bound in C++
Die Funktion lower_bound in C ++ wird verwendet, um die Position des ersten Elements in einem geordneten Bereich zu finden, der nicht kleiner als der angegebene Wert ist.
Im Folgenden finden Sie einige Beispiele für die Verwendung der lower_bound-Funktion:
- Beispiel 1: Nehmen wir an, wir haben einen sortierten Vektor von Zahlen: . Wir wollen die Position des ersten Elements finden, das mindestens 4 ist. Mit der Funktion lower_bound können wir Position 3 erhalten, da das Element mit dem Index 3 (Wert 7) nicht kleiner als 4 ist.
- Beispiel 2: Angenommen, wir haben einen sortierten Zeilenvektor: . Wir wollen die Position der ersten Zeile finden, die nicht kleiner als "cat" ist. Mit der Funktion lower_bound können wir Position 2 erhalten, da die Zeile mit dem Index 2 ("cherry") nicht kleiner als "cat" ist.
- Beispiel 3: Lassen Sie uns ein sortiertes Array von ganzen Zahlen haben: . Wir wollen die Position der ersten Zahl finden, die nicht kleiner als 5 ist. Mit der Funktion lower_bound können wir Position 2 erhalten, da die Zahl mit dem Index 2 (Wert 6) nicht kleiner als 5 ist.
Die lower_bound-Funktion ist nützlich, wenn Sie das erste Vorkommen eines Elements finden möchten, das mindestens einen bestimmten Wert in einem geordneten Bereich hat. Es funktioniert für verschiedene Datentypen, einschließlich Vektoren, Arrays und Container, die den Vergleichsoperator unterstützen "
Vor- und Nachteile der Verwendung der Funktion lower_bound in C++
- Vorteile:
- Mit der lower_bound-Funktion können Sie mithilfe der binären Suche effizient nach einem Wert in einem sortierten Bereich eines Containers suchen.
- Gibt einen Iterator für das erste Element zurück, das größer oder gleich dem gewünschten Wert ist.
- Garantiert eine logarithmische Suchkomplexität, die besonders für große Datenmengen nützlich ist.
- Anwendbar auf viele Container, einschließlich Vektor, Liste und sogar assoziative Container.
- Erfordert das Vorsortieren der Containerdaten, was zeit- und speicherintensiv sein kann.
- Kann ein fehlerhaftes Ergebnis zurückgeben, wenn der Container nicht sortiert ist, was zu unvorhersehbaren Konsequenzen führen kann.
- Wenn kein Wert gefunden wird, gibt die Funktion nach dem letzten einen Iterator zum nächsten Element zurück.
- Kann nicht für unsortierte Container oder für die Suche nach Elementen außerhalb des Containerbereichs verwendet werden.
Insgesamt ist die Funktion lower_bound ein leistungsfähiges Werkzeug, um Elemente in sortierten Containern in C++ effizient zu finden, erfordert jedoch eine sorgfältige Verwendung und Bereitstellung der richtigen Daten.
