std::ranges...cal_compare(3)

🎀 std::ranges::lexicographical_compare 🎀

okay bestie, welcome to the C++ Standard Libary manual page for std::ranges::lexicographical_compare (and yes, the page says “Libary” — not me, I’m just the messenger 💀). This one is all about comparing two ranges in dictionary-ish order, and it’s honestly kind of iconic once you get the vibe. 🦋

---

🌸 NAME 🌸

std::ranges::lexicographical_compare — std::ranges::lexicographical_compare (yes, the page literally repeats it like that, no cap 💅).

---

📜 Synopsis 📜

Defined in header <algorithm>

Call signature:

template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,
          class Proj1 = std::identity, class Proj2 =
std::identity,
          std::indirect_strict_weak_order<
              std::projected<I1, Proj1>,
(1) (since C++20)
              std::projected<I2, Proj2>> Comp = ranges::less >
constexpr bool
    lexicographical_compare( I1 first1, S1 last1, I2 first2, S2
last2,

                             Comp comp = {}, Proj1 proj1 = {},
Proj2 proj2 = {} );
template< ranges::input_range R1, ranges::input_range R2,

          class Proj1 = std::identity, class Proj2 =
std::identity,
          class std::indirect_strict_weak_order<
              std::projected<ranges::iterator_t<R1>, Proj1>,
(2) (since C++20)
              std::projected<ranges::iterator_t<R2>, Proj2>> Comp
= ranges::less >
constexpr bool
    lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},

                             Proj1 proj1 = {}, Proj2 proj2 = {} );

So what does it actually do? It checks if the first range [first1, last1) is lexicographically less than the second range [first2, last2). ✨

1. Elements are compared using the given binary comparison function comp.
2. Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

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.

The function-like entities described on this page are niebloids, that is:

• Explicit template argument lists cannot be specified when calling any of them.
• None of them are visible to argument-dependent lookup.
• When any of them are found by normal unqualified lookup as the name to the left of the function-call operator, argument-dependent lookup is inhibited.

In practice, they may be implemented as function objects, or with special compiler extensions. 🧚

---

🫶 Parameters 🫶

• first1, last1 — the first range of elements to examine
• r1 — the first range of elements to examine
• first2, last2 — the second range of elements to examine
• r2 — the second range of elements to examine
• comp — comparison function to apply to the projected elements
• proj1 — projection to apply to the first range of elements
• proj2 — projection to apply to the second range of elements

---

✅ Return value ✅

true if the first range is lexicographically less than the second.

---

⚡ Complexity ⚡

At most 2·min(N1, N2) applications of the comparison and corresponding projections, where N1 = ranges::distance(first1, last1) and N2 = ranges::distance(first2, last2).

---

🛠️ Possible implementation 🛠️

struct lexicographical_compare_fn {
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<I1, Proj1>,
                 std::projected<I2, Proj2>> Comp = ranges::less>
    constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
                              Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
        {
            if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
                return true;

            if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1)))
                return false;
        }
        return (first1 == last1) && (first2 != last2);
    }

    template<ranges::input_range R1, ranges::input_range R2,
             class Proj1 = std::identity, class Proj2 = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R1>, Proj1>,
                 std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less>
    constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {},
                              Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::ref(comp), std::ref(proj1), std::ref(proj2));
    } };

inline constexpr lexicographical_compare_fn lexicographical_compare;

---

🌈 Example 🌈

// Run this code

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

int main()
{
    std::vector<char> v1 {'a', 'b', 'c', 'd'};
    std::vector<char> v2 {'a', 'b', 'c', 'd'};

    namespace ranges = std::ranges;
    auto os = std::ostream_iterator<char>(std::cout, " ");

    std::mt19937 g {std::random_device {}()};
    while (not ranges::lexicographical_compare(v1, v2))
    {
        ranges::copy(v1, os);
        std::cout << ">= ";
        ranges::copy(v2, os);
        std::cout << '\n';

        ranges::shuffle(v1, g);
        ranges::shuffle(v2, g);
    }

    ranges::copy(v1, os);
    std::cout << "<  ";
    ranges::copy(v2, os);
    std::cout << '\n';
}

---

🍓 Possible output 🍓

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

---

👀 See also 👀

• ranges::equal — determines if two sets of elements are the same (C++20) (niebloid)
• lexicographical_compare — returns true if one range is lexicographically less than another (function template)

---

Source/version/date: http://cppreference.com · 2024.06.10 · std::ranges...cal_compare(3) — and that’s the whole page, bestie. go flex that range comparison knowledge 💖✨