std::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.

[edit] Parameters

[edit] Return value

true if the first range is lexicographically less than the second, otherwise false.

[edit] Complexity

Given \(\scriptsize N_1\)N1 as std::distance (first1, last1) and \(\scriptsize N_2\)N2 as std::distance (first2, last2):

[edit] Exceptions

The overloads with a template parameter named ExecutionPolicy report errors as follows:

• If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

[edit] Possible implementation

template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
 InputIt2 first2, InputIt2 last2)
{
 for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
 {
 if (*first1 < *first2)
 return true;
 if (*first2 < *first1)
 return false;
 }
 
 return (first1 == last1) && (first2 != last2);
}

template<class InputIt1, class InputIt2, class Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
 InputIt2 first2, InputIt2 last2, Compare comp)
{
 for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
 {
 if (comp(*first1, *first2))
 return true;
 if (comp(*first2, *first1))
 return false;
 }
 
 return (first1 == last1) && (first2 != last2);
}

[edit] Example

#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
 
void print(const std::vector <char>& v, auto suffix)
{
 for (char c : v)
 std::cout << c << ' ';
 std::cout << suffix;
}
 
int main()
{
 std::vector <char> v1{'a', 'b', 'c', 'd'};
 std::vector <char> v2{'a', 'b', 'c', 'd'};
 
 for (std::mt19937 g{std::random_device {}()};
 !std::lexicographical_compare(v1.begin(), v1.end(),
 v2.begin(), v2.end());)
 {
 print(v1, ">= ");
 print(v2, '\n');
 
 std::shuffle (v1.begin(), v1.end(), g);
 std::shuffle (v2.begin(), v2.end(), g);
 }
 
 print(v1, "< ");
 print(v2, '\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] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

[edit] See also