std::ranges::lexicographical_compare

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

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.

[edit] Parameters

[edit] Return value

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

[edit] Complexity

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

[edit] 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;

[edit] Example

#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

[edit] See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文