Namespaces
Variants
Views
Actions

std::ranges::lexicographical_compare

From cppreference.com
< cpp‎ | algorithm‎ | ranges
 
 
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms: std::ranges::copy, std::ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
(C++11)(C++11)(C++11)
(C++17)
Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
(C++11)
Binary search operations
Set operations (on sorted ranges)
Heap operations
(C++11)
Minimum/maximum operations
(C++11)
(C++17)

Permutations
Numeric operations
C library
 
Constrained algorithms
Non-modifying sequence operations
ranges::lexicographical_compare

Modifying sequence operations
Operations on uninitialized storage
Partitioning operations
Sorting operations
Binary search operations
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutations
 
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 a 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 niebloids, that is:

In practice, they may be implemented as function objects, or with special compiler extensions.

Contents

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

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

determines if two sets of elements are the same
(niebloid) [edit]
returns true if one range is lexicographically less than another
(function template) [edit]