std::ranges::lexicographical_compare

Definiert in Header `<algorithm>`
Aufruf-Signatur
template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, class Proj1 = std::identity, class Proj2 = std::identity, std::indirect_strict_weak_order< std::projected<I1, Proj1>, std::projected<I2, Proj2>> Comp = ranges::less > constexpr bool lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(1)	(seit C++20)
template< ranges::input_range R1, ranges::input_range R2, class Proj1 = std::identity, class Proj2 = std::identity, std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less > constexpr bool lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );	(2)	(seit C++20)

Prüft, ob der erste Bereich [first1, last1) lexikographisch kleiner ist als der zweite Bereich [first2, last2).

1) Elemente werden mit der gegebenen binären Vergleichsfunktion comp verglichen.

2) Dasselbe wie (1), aber verwendet r als Quellbereich, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würden.

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.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als niebloids bekannt), d.h.

Können explizite Template-Argumentlisten bei keinem von ihnen angegeben werden.
Keiner von ihnen ist für Argument-abhängige Suche sichtbar.
Wenn einer von ihnen durch normale unqualifizierte Suche als Name links vom Funktionsaufrufoperator gefunden wird, wird die Argument-abhängige Suche unterdrückt.

[bearbeiten] Parameter

first1, last1	-	das Iterator-Sentinel-Paar, das den ersten Bereich der zu untersuchenden Elemente definiert
r1	-	der erste Bereich der zu untersuchenden Elemente
first2, last2	-	das Iterator-Sentinel-Paar, das den zweiten Bereich der zu untersuchenden Elemente definiert
r2	-	der zweite Bereich der zu untersuchenden Elemente
comp	-	Vergleichsfunktion, die auf die projizierten Elemente angewendet wird
proj1	-	Projektion, die auf den ersten Bereich der Elemente angewendet wird
proj2	-	Projektion, die auf den zweiten Bereich der Elemente angewendet wird

[bearbeiten] Rückgabewert

true, wenn der erste Bereich lexikographisch kleiner ist als der zweite.

[bearbeiten] Komplexität

Maximal $2\cdotmin(N1, N2)$ Anwendungen des Vergleichs und der entsprechenden Projektionen, wobei N1 = ranges::distance(first1, last1) und N2 = ranges::distance(first2, last2).

[bearbeiten] Mögliche Implementierung

struct lexicographical_compare_fn
{
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<I1, Proj1>,
                 std::projected<I2, Proj2>> Comp = ranges::less>
    constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                              Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
                return true;
 
            if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1)))
                return false;
        }
        return (first1 == last1) && (first2 != last2);
    }
 
    template<ranges::input_range R1, ranges::input_range R2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R1>, Proj1>,
                 std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less>
    constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::ref(comp), std::ref(proj1), std::ref(proj2));
    }
};
 
inline constexpr lexicographical_compare_fn lexicographical_compare;

[bearbeiten] Beispiel

Führen Sie diesen Code aus

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
 
int main()
{
    std::vector<char> v1 {'a', 'b', 'c', 'd'};
    std::vector<char> v2 {'a', 'b', 'c', 'd'};
 
    namespace ranges = std::ranges;
    auto os = std::ostream_iterator<char>(std::cout, " ");
 
    std::mt19937 g {std::random_device {}()};
    while (not ranges::lexicographical_compare(v1, v2))
    {
        ranges::copy(v1, os);
        std::cout << ">= ";
        ranges::copy(v2, os);
        std::cout << '\n';
 
        ranges::shuffle(v1, g);
        ranges::shuffle(v2, g);
    }
 
    ranges::copy(v1, os);
    std::cout << "<  ";
    ranges::copy(v2, os);
    std::cout << '\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

[bearbeiten] Siehe auch

ranges::equal (C++20)	Bestimmt, ob zwei Elementmengen gleich sind (Algorithmus-Funktionsobjekt)[edit]
lexicographical_compare	gibt true zurück, wenn ein Bereich lexikographisch kleiner als ein anderer ist (Funktionsvorlage) [editieren]

Compiler-Unterstützung
Freestanding und gehostet
Sprache
Standardbibliothek
Header der Standardbibliothek
Benannte Anforderungen
Feature-Test-Makros (C++20)
Bibliothek für Sprachunterstützung
Konzepte-Bibliothek (C++20)
Diagnostik-Bibliothek
Speicherverwaltungsbibliothek
Metaprogrammierungsbibliothek (C++11)
Allgemeine Dienstprogramme-Bibliothek
Container-Bibliothek
Iterator-Bibliothek
Ranges-Bibliothek (C++20)
Algorithmen-Bibliothek
Bibliothek für Zeichenketten
Textverarbeitungsbibliothek
Numerik-Bibliothek
Datums- und Zeitbibliothek
Ein-/Ausgabe-Bibliothek
Dateisystembibliothek (C++17)
Unterstützung für nebenläufige Programmierung (C++11)
Ausführungssteuerungsbibliothek (C++26)
Technische Spezifikationen
Symbolverzeichnis
Externe Bibliotheken

cppreference.com

Namensräume

Varianten

Ansichten

Aktionen