std::ranges:: lexicographical_compare

From cppreference.com

Defined in header `<algorithm>`
Call signature
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)	(since 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)	(since C++20)

Checks if the first range [ first1 , last1 ) is lexicographically less than the second range [ first2 , last2 ) .

1) Elements are compared using the given binary comparison function comp .

2) Same as (1) , but uses r as the source range, as if using ranges:: begin ( r ) as first and ranges:: end ( r ) as last .

Lexicographical comparison is an operation with the following properties:

Two ranges are compared element by element.
The first mismatching element defines which range is lexicographically less or greater than the other.
If one range is a prefix of another, the shorter range is lexicographically less than the other.
If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal .
An empty range is lexicographically less than any non-empty range.
Two empty ranges are lexicographically equal .

The function-like entities described on this page are algorithm function objects (informally known as niebloids ), that is:

Explicit template argument lists cannot be specified when calling any of them.
None of them are visible to argument-dependent lookup .
When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

Parameters

first1, last1	-	the first range of elements to examine
r1	-	the first range of elements to examine
first2, last2	-	the second range of elements to examine
r2	-	the second range of elements to examine
comp	-	comparison function to apply to the projected elements
proj1	-	projection to apply to the first range of elements
proj2	-	projection to apply to the second range of elements

Return value

true if the first range is lexicographically less than the second.

Complexity

At most $2\cdotmin(N1, N2)$ applications of the comparison and corresponding projections, where N1 = ranges:: distance ( first1, last1 ) and N2 = ranges:: distance ( first2, last2 ) .

Possible implementation

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;

Example

Run this code

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

Possible output:

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

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

ranges::equal (C++20)	determines if two sets of elements are the same (algorithm function object)
lexicographical_compare	returns true if one range is lexicographically less than another (function template)