std::ranges::lexicographical_compare

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 = {} );

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 = {} );

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

Ein lexikografischer Vergleich ist eine Operation mit den folgenden Eigenschaften:

• Zwei Bereiche werden elementweise verglichen.
• Das erste nicht übereinstimmende Element bestimmt, welcher Bereich lexikografisch kleiner oder größer als der andere ist.
• Wenn ein Bereich ein Präfix eines anderen ist, ist der kürzere Bereich lexikografisch kleiner als der andere.
• Wenn zwei Bereiche äquivalente Elemente haben und gleich lang sind, sind die Bereiche lexikografisch gleich.
• Ein leerer Bereich ist lexikografisch kleiner als jeder nicht leere Bereich.
• Zwei leere Bereiche sind lexikografisch gleich.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:

• Es können keine expliziten Vorlagenargumentlisten angegeben werden, wenn eine von ihnen aufgerufen wird.
• Keine von ihnen ist für argumentabhängige Namenssuche sichtbar.
• Wenn eine von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird die argumentabhängige Namenssuche unterbunden.

Parameter

Rückgabewert

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

Komplexität

Höchstens 2·min(N1, N2) Anwendungen des Vergleichs und entsprechender Projektionen, wobei N1 = ranges:: distance ( first1, last1 ) und N2 = ranges:: distance ( first2, last2 ) .

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;

Beispiel

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

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

Siehe auch