Lexicographical Compare

Overview

std::lexicographical_compare (header <algorithm>) compares two ranges element by element, the way a dictionary orders words. It walks both ranges in lockstep and stops at the first position where the elements are not equivalent.

1. If a[i] < b[i] at that position, the result is true.
2. If b[i] < a[i], the result is false.
3. If one range runs out first, the shorter range is less. An empty range is therefore less than any non-empty range.
4. If both run out together, the ranges are equivalent and the result is false.

The algorithm is a strict less-than. It does not require sorted input, and it never looks at more than min(N1, N2) element pairs. It performs at most 2·min(N1, N2) comparisons, because each step may test both directions.

This is the algorithm behind operator< for std::vector, std::array, std::deque, std::list, std::pair and std::tuple. Before C++20 the relational operators on standard containers were defined in terms of it. Since C++20, containers provide operator<=>, which is defined through lexicographical_compare_three_way.

Syntax

#include <algorithm>

// C++98
template<class It1, class It2>
bool lexicographical_compare(It1 first1, It1 last1, It2 first2, It2 last2);

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

// C++17: ExecutionPolicy overloads of both forms above
template<class ExecutionPolicy, class It1, class It2>
bool lexicographical_compare(ExecutionPolicy&& policy,
                             It1 first1, It1 last1, It2 first2, It2 last2);

// C++20: ranges version (std::ranges namespace, projections supported)
// std::ranges::lexicographical_compare(r1, r2, comp = {}, proj1 = {}, proj2 = {});

// C++20: three-way version, returns std::strong_ordering / weak_ordering / partial_ordering
// std::lexicographical_compare_three_way(f1, l1, f2, l2, comp = std::compare_three_way{});

The two ranges may have different iterator and element types, provided comp(*it1, *it2) and comp(*it2, *it1) are both valid. comp must induce a strict weak ordering.

Examples

Basic comparison

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a{1, 2, 3};
    std::vector<int> b{1, 2, 4};
    std::vector<int> c{1, 2};

    auto lt = [](const auto& x, const auto& y) {
        return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
    };

    std::cout << lt(a, b) << '\n';  // 1: 3 < 4 at index 2
    std::cout << lt(c, a) << '\n';  // 1: c is a proper prefix of a
    std::cout << lt(a, a) << '\n';  // 0: equivalent, strict ordering
}

Case-insensitive ordering

When using <cctype> functions, convert through unsigned char first. Passing a negative char to std::tolower is undefined behaviour.

#include <algorithm>
#include <cctype>
#include <set>
#include <string>

struct CaseInsensitiveLess {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](unsigned char x, unsigned char y) {
                return std::tolower(x) < std::tolower(y);
            });
    }
};

std::set<std::string, CaseInsensitiveLess> names;  // "Alice" and "alice" are the same key

Multi-field keys with std::tie

For structured data you usually do not need the algorithm directly. std::tie builds a tuple of references, and tuple comparison is lexicographic.

#include <string>
#include <tuple>

struct Person {
    bool vip;
    std::string last, first;

    friend bool operator<(const Person& l, const Person& r) {
        return std::tie(l.vip, l.last, l.first) < std::tie(r.vip, r.last, r.first);
    }
};
// C++20: prefer `auto operator<=>(const Person&) const = default;`

Ranges version with projections (C++20)

#include <algorithm>
#include <string>
#include <vector>

struct Version { std::vector<int> parts; std::string tag; };

bool older(const Version& a, const Version& b) {          // C++20
    return std::ranges::lexicographical_compare(a.parts, b.parts);
}

bool older_by_tag(const std::vector<Version>& x, const std::vector<Version>& y) {  // C++20
    return std::ranges::lexicographical_compare(
        x, y, std::less{}, &Version::tag, &Version::tag);   // projections on both ranges
}

Three-way result (C++20)

When you need less, equal, and greater in a single pass, lexicographical_compare_three_way avoids calling the algorithm twice.

#include <algorithm>
#include <compare>
#include <vector>

std::vector<double> u{1.0, 2.0}, v{1.0, 2.5};

auto r = std::lexicographical_compare_three_way(      // C++20
    u.begin(), u.end(), v.begin(), v.end());
// r is std::partial_ordering here, because double compares partially
if (r < 0) { /* u before v */ }

The result type is deduced from the comparator. With the default std::compare_three_way it is the common comparison category of the element types, so int gives strong_ordering and double gives partial_ordering.

Parallel overload (C++17)

#include <algorithm>
#include <execution>
#include <vector>

bool before(const std::vector<std::uint8_t>& a, const std::vector<std::uint8_t>& b) {
    return std::lexicographical_compare(std::execution::par_unseq,   // C++17
                                        a.begin(), a.end(), b.begin(), b.end());
}

Parallel execution only pays off for very large ranges with cheap comparison. Short-circuiting is harder to exploit in parallel, so profile before adopting it. Some implementations also need an extra library, such as TBB for libstdc++.

Best Practices

• Prefer container operators for container comparison. a < b on two vectors of the same type is clearer and does the same work.
• Use the algorithm when types differ. Examples are comparing a std::list<int> with a std::vector<int>, or a subrange with a whole container.
• Use std::string_view for text (C++17) and compare with compare() or <. They use char_traits, which for char compares as unsigned char.
• Prefer std::ranges:: in C++20 code. Projections remove most hand-written comparator lambdas, and constraints give better diagnostics.
• Use the three-way form when you need both < and == results. One pass replaces lexicographical_compare called twice, or a call combined with std::equal.
• Keep comparators stateless and pure. They are called in both argument orders, so they must be consistent.

Common Pitfalls

• Result is bool, not an ordering. false means "not less", which could be equal or greater. Do not use it as an equality test; use std::equal (C++98, with a four-iterator overload since C++14) or std::ranges::equal (C++20).
• Non-strict comparators. Passing <= or std::less_equal violates the strict weak ordering requirement. Equal ranges then return true, and the behaviour is undefined.
• Floating-point NaN. With NaN present, < is not a strict weak ordering. Results are unspecified in meaning, and comparison may not be transitive.
• Locale-unaware or signed-char comparison. Hand-written char comparators with std::tolower need the unsigned char cast. This ordering is also not a linguistic collation. For user-visible sorting, use std::collate or ICU.
• Raw C strings. std::lexicographical_compare(s1, s1 + n1, s2, s2 + n2) works, but you must supply the lengths. Passing s1, s1 + strlen(s1) repeatedly is quadratic in loops.
• Mixing signed and unsigned element types. Comparing int and unsigned ranges applies the usual arithmetic conversions, so -1 compares greater than 1u. Use std::cmp_less (C++20) in a custom comparator.
• Lexicographic is not numeric. "10" < "9" is true as strings. For numbers, version strings, and natural ordering, parse first.
• Overload ambiguity with policies. If the first argument is an execution policy, the parallel overload requires forward iterators. Input iterators fail to compile.

See Also

• min-max: std::min/std::max use the same strict < convention.
• merge: merging relies on a consistent strict weak ordering.
• binary-search: sorted-range queries with the same comparator requirements.