std::ranges::lexicographical_compare - cppreference.com (original) (raw)

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.

Contents

• 1 Parameters
• 2 Return value
• 3 Complexity
• 4 Possible implementation
• 5 Example
• 6 See also

[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 S1, std::input_iterator I2, std::sentinel_for 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, Proj1>, std::projected<ranges::iterator_t, 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 #include #include #include #include   int main() { std::vector v1 {'a', 'b', 'c', 'd'}; std::vector v2 {'a', 'b', 'c', 'd'};   namespace ranges = std::ranges; auto os = std::ostream_iterator(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

[edit] See also