Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Algorithms

The std::lexicographical_compare algorithm

Reference for C++ std::lexicographical_compare and lexicographical_compare_three_way: dictionary order of ranges, prefixes, comparators and strings.

std::lexicographical_compare returns true if the first range comes before the second in dictionary order: it compares the two ranges element by element, and the first position where they differ decides. If one range is a prefix of the other, the shorter one is less. This is the ordering behind operator< for std::string, std::vector, std::pair and std::tuple.

You rarely need to call it directly for whole containers, because a < b already does it. It is useful for sub-ranges, for ranges of different container types, and for custom element comparisons such as case-insensitive text.

C++
bool before = std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());

Try it

C++ Dictionary order of ranges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Case-insensitive ordering and sorting with it

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template<class InIt1, class InIt2>
bool lexicographical_compare(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);

template<class InIt1, class InIt2, class Compare>
bool lexicographical_compare(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, Compare comp);

// C++20
template<class InIt1, class InIt2>
auto lexicographical_compare_three_way(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);
Name Description
first1, last1 The first range.
first2, last2 The second range.
comp Strict weak ordering applied to elements (default <).

Returns: true if the first range is lexicographically less than the second, otherwise false. The three-way version returns a comparison category value (for example std::strong_ordering) that you compare with 0.

Errors / undefined behavior: none for valid ranges.

Usage notes

  • How the decision is made: the first pair with comp(a, b) or comp(b, a) true decides. If one range ends first, it is smaller; if both end together, they are equal and the result is false.
  • Strict: equal ranges are not "less" than each other. That is exactly what std::sort expects from a comparator.
  • Complexity: at most 2 * min(N1, N2) comparisons.
  • Strings: std::string comparison uses the character values, not the language's alphabet, so "Z" < "a" in ASCII. For human-facing sorting use a collation-aware comparator.
  • Prefer operators for whole containers: a < b on vectors, arrays, pairs and tuples calls this algorithm, or <=> since C++20.
  • Three-way: lexicographical_compare_three_way (C++20) needs only one pass to tell less, equal or greater; it works well with types that define operator<=>.
  • Ranges: std::ranges::lexicographical_compare (C++20) takes ranges and projections.