# std::lexicographical_compare_three_way

> C++ Atlas: `cppatlas.com/w/cpp/algorithm/lexicographical_compare_three_way` | Source: https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare_three_way | Domain: Algorithms | Standards: C++20

Lexicographically compares two ranges [first1, last1) and [first2, last2) using three-way comparison and produces a result of the strongest applicable comparison category type.

## Official Specification Summary (cppreference)

```cpp
// Defined in header <algorithm>

template< class InputIt1, class InputIt2, class Cmp >
constexpr auto lexicographical_compare_three_way
    ( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
      Cmp comp ) -> decltype(comp(*first1, *first2)); // (1) (since C++20)

template< class InputIt1, class InputIt2 >
constexpr auto lexicographical_compare_three_way
    ( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 ); // (2) (since C++20)
```

Lexicographically compares two ranges `[first1,` `last1)` and `[first2,` `last2)` using three-way comparison and produces a result of the strongest applicable comparison category type.

1) Returns the order between the first non-equivalent pair of elements according to `comp` in both ranges if any, otherwise (if one ranges is equivalent to the prefix of another according to `comp`), returns the order between the length of both ranges.

2) Equivalent to `return std::lexicographical_compare_three_way(first1, last1, first2, last2, std::compare_three_way());`

If the return type is not one of the three comparison category types, the program is ill-formed:

- `std::strong_ordering`
- `std::weak_ordering`
- `std::partial_ordering`

### Parameters

- `first1, last1` - the first range of elements to examine
- `first2, last2` - the second range of elements to examine
- `comp` - a function object

**Type requirements**

- `InputIt1, InputIt2` must meet the requirements of *LegacyInputIterator*.

### Return value

The value of a comparison category type specified above.

### Complexity

Given N¹ as `std::distance(first1, last1)` and N² as `std::distance(first2, last2)`:

1) At most min(¹,N²) applications of `comp`.

2) At most min(N¹,N²) applications of `std::compare_three_way()`.

### Possible implementation

```cpp
template<class I1, class I2, class Cmp>
constexpr auto lexicographical_compare_three_way(I1 f1, I1 l1, I2 f2, I2 l2, Cmp comp)
    -> decltype(comp(*f1, *f2))
{
    using ret_t = decltype(comp(*f1, *f2));
    static_assert(std::disjunction_v<
                      std::is_same<ret_t, std::strong_ordering>,
                      std::is_same<ret_t, std::weak_ordering>,
                      std::is_same<ret_t, std::partial_ordering>>,
                  "The return type must be a comparison category type.");

    bool exhaust1 = (f1 == l1);
    bool exhaust2 = (f2 == l2);
    for (; !exhaust1 && !exhaust2; exhaust1 = (++f1 == l1), exhaust2 = (++f2 == l2))
        if (auto c = comp(*f1, *f2); c != 0)
            return c;

    return !exhaust1 ? std::strong_ordering::greater:
           !exhaust2 ? std::strong_ordering::less:
                       std::strong_ordering::equal;
}
```

### Example

```cpp
#include <algorithm>
#include <cctype>
#include <compare>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <utility>

using namespace std::literals;

void show_result(std::string_view s1, std::string_view s2, std::strong_ordering o)
{
    std::cout << std::quoted(s1) << " is ";
    std::is_lt(o) ? std::cout << "less than ":
    std::is_gt(o) ? std::cout << "greater than ":
                    std::cout << "equal to ";
    std::cout << std::quoted(s2) << '\n';
}

std::strong_ordering cmp_icase(unsigned char x, unsigned char y)
{
    return std::toupper(x) <=> std::toupper(y);
};

int main()
{
    for (const auto& [s1, s2] :
    {
        std::pair{"one"sv, "ONE"sv}, {"two"sv, "four"sv}, {"three"sv, "two"sv}
    })
    {
        const auto res = std::lexicographical_compare_three_way(
            s1.cbegin(), s1.cend(), s2.cbegin(), s2.cend(), cmp_icase);
        show_result(s1, s2, res);
    }
}
```

Output:

```text
"one" is equal to "ONE"
"two" is greater than "four"
"three" is less than "two"
```

### Defect reports

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

| DR | Applied to | Behavior as published | Correct behavior |
| --- | --- | --- | --- |
| LWG 3410 | C++20 | extraneous comparisons between iterators were required | such requirement removed |

### See also

- [`lexicographical_compare`](https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare): returns `true` if one range is lexicographically less than another (function template)
- [`compare_three_way`](https://en.cppreference.com/w/cpp/utility/compare/compare_three_way) (C++20): constrained function object implementing `x <=> y` (class)
- [`ranges::lexicographical_compare`](https://en.cppreference.com/w/cpp/algorithm/ranges/lexicographical_compare) (C++20): returns `true` if one range is lexicographically less than another (algorithm function object)

---
Attribution: content from https://en.cppreference.com/w/cpp/algorithm/lexicographical_compare_three_way (cppreference.com), licensed under CC-BY-SA 3.0 and GFDL. Modified: converted to markdown, study notes added. Offline snapshot of 9 February 2025.