std::lexicographical_compare
| Definiert in Header <algorithm> |
||
template< class InputIt1, class InputIt2 > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(1) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > |
(2) | (seit C++17) |
template< class InputIt1, class InputIt2, class Compare > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, |
(3) | (constexpr seit C++20) |
| template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > |
(4) | (seit C++17) |
Prüft, ob der erste Bereich [first1, last1) lexikographisch kleiner ist als der zweite Bereich [first2, last2).
|
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> ist true. |
(bis C++20) |
|
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> ist true. |
(seit C++20) |
Lexikographischer Vergleich ist eine Operation mit den folgenden Eigenschaften:
- Zwei Bereiche werden elementweise verglichen.
- Das erste Element, das abweicht, bestimmt, welcher Bereich lexikographisch kleiner oder größer ist als der andere.
- Wenn ein Bereich ein Präfix eines anderen ist, ist der kürzere Bereich lexikographisch kleiner als der andere.
- Wenn zwei Bereiche äquivalente Elemente haben und die gleiche Länge haben, sind die Bereiche lexikographisch gleich.
- Ein leerer Bereich ist lexikographisch kleiner als jeder nicht-leere Bereich.
- Zwei leere Bereiche sind lexikographisch gleich.
Inhalt |
[edit] Parameter
| first1, last1 | - | Das Iteratorenpaar, das den ersten Bereich der zu untersuchenden Elemente definiert. |
| first2, last2 | - | Das Iteratorenpaar, das den zweiten Bereich der zu untersuchenden Elemente definiert. |
| policy | - | die Ausführungsrichtlinie, die verwendet werden soll |
| comp | - | Ein Vergleichsfunktions-Objekt (d.h. ein Objekt, das die Anforderungen an Compare erfüllt), das true zurückgibt, wenn das erste Argument *weniger* als das zweite ist. Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein bool cmp(const Type1& a, const Type2& b); Obwohl die Signatur nicht const& haben muss, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte vom Typ (möglicherweise const) |
| Typanforderungen | ||
-InputIt1, InputIt2 müssen die Anforderungen an LegacyInputIterator erfüllen. | ||
-ForwardIt1, ForwardIt2 müssen die Anforderungen an LegacyForwardIterator erfüllen. | ||
-Compare muss die Anforderungen an Compare erfüllen. | ||
[edit] Rückgabewert
true, wenn der erste Bereich lexikographisch kleiner ist als der zweite, andernfalls false.
[edit] Komplexität
Gegeben N1 als std::distance(first1, last1) und N2 als std::distance(first2, last2)
[edit] Ausnahmen
Die Überladungen mit einem Template-Parameter namens ExecutionPolicy berichten Fehler wie folgt
- Wenn die Ausführung einer Funktion, die als Teil des Algorithmus aufgerufen wird, eine Ausnahme auslöst und
ExecutionPolicyeine der Standardrichtlinien ist, wird std::terminate aufgerufen. Für jede andereExecutionPolicyist das Verhalten implementierungsabhängig. - Wenn dem Algorithmus der Speicher zur Neuzuweisung fehlt, wird std::bad_alloc ausgelöst.
[edit] Mögliche Implementierung
| lexicographical_compare (1) |
|---|
template<class InputIt1, class InputIt2> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) { for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2) { if (*first1 < *first2) return true; if (*first2 < *first1) return false; } return (first1 == last1) && (first2 != last2); } |
| lexicographical_compare (3) |
template<class InputIt1, class InputIt2, class Compare> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp) { for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2) { if (comp(*first1, *first2)) return true; if (comp(*first2, *first1)) return false; } return (first1 == last1) && (first2 != last2); } |
[edit] Beispiel
#include <algorithm> #include <iostream> #include <random> #include <vector> void print(const std::vector<char>& v, auto suffix) { for (char c : v) std::cout << c << ' '; std::cout << suffix; } int main() { std::vector<char> v1{'a', 'b', 'c', 'd'}; std::vector<char> v2{'a', 'b', 'c', 'd'}; for (std::mt19937 g{std::random_device{}()}; !std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());) { print(v1, ">= "); print(v2, '\n'); std::shuffle(v1.begin(), v1.end(), g); std::shuffle(v2.begin(), v2.end(), g); } print(v1, "< "); print(v2, '\n'); }
Mögliche Ausgabe
a b c d >= a b c d d a b c >= c b d a b d a c >= a d c b a c d b < c d a b
[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 142 | C++98 | Es waren höchstens min(N1,N2) Vergleiche erlaubt, aber das ist nicht möglich (Äquivalenz wird durch 2 Vergleiche bestimmt) |
verdoppelte das Limit |
| LWG 1205 | C++98 | die Ergebnisse von lexikographischen Vergleichen mit leeren Bereichen waren unklar | wurde klargestellt |
[edit] Siehe auch
| Bestimmt, ob zwei Elementmengen gleich sind (Funktionstempelat) | |
| vergleicht zwei Bereiche mittels Drei-Wege-Vergleich (Funktionsvorlage) | |
| gibt true zurück, wenn ein Bereich lexikographisch kleiner als ein anderer ist (Algorithmus-Funktionsobjekt) |
