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.
bool before = std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
Try 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.
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
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)orcomp(b, a)true decides. If one range ends first, it is smaller; if both end together, they are equal and the result isfalse. - Strict: equal ranges are not "less" than each other. That is exactly what
std::sortexpects from a comparator. - Complexity: at most 2 * min(N1, N2) comparisons.
- Strings:
std::stringcomparison 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 < bon 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 defineoperator<=>. - Ranges:
std::ranges::lexicographical_compare(C++20) takes ranges and projections.