std::ranges::lexicographical_compare() 算法

自 C++20 起

简化

// (1)
constexpr bool
    lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2,
                             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
constexpr bool lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {} );

参数类型是泛型的，并具有以下约束

• I1, I2 - std::input_iterator

• S1, S2 - std::sentinel_for<I1>, std::sentinel_for<I2>

• R1, R2 - std::ranges::input_range

• Comp:

  • (1) - std::indirect_strict_weak_order<std::projected<I1, Proj1>, std::projected<I2, Proj2>>
  • (2) - std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>

• Proj1, Proj2 - (无)

Proj1, Proj2 和 Pred 模板参数的默认类型如下：对于所有重载，均为 std::identity，ranges::less。

此外，每个重载都有以下约束

• (1) - std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
• (2) - std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>

详细

// (1)
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
    lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2,
                             Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );

// (2)
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 lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},
                                        Proj1 proj1 = {}, Proj2 proj2 = {} );

检查第一个范围 [first1; last1) 是否按字典顺序小于第二个范围 [first2; last2)。

• (1) 使用给定的二元比较函数 comp 比较元素。

• (2) 与 (1) 相同，但使用 r 作为源范围，如同使用 ranges::begin(r) 作为 first 且 ranges::end(r) 作为 last。

字典序比较是一种具有以下属性的操作

• 两个范围逐元素进行比较。
• 第一个不匹配的元素决定哪个范围在字典序上小于或大于另一个。
• 如果一个范围是另一个范围的前缀，则较短的范围在字典序上小于另一个。
• 如果两个范围具有等价元素且长度相同，则这些范围在字典序上相等。
• 空范围在字典序上小于任何非空范围。
• 两个空范围在字典序上相等。

本页描述的函数类实体是niebloids。

参数

first1 last1	要比较的第一个元素范围。
r1	要比较的第一个元素范围。
first2 last2	要比较的第二个元素范围。
r2	要比较的第一个元素范围。
comp	应用于投影元素的比较函数。
proj1	应用于第一个范围元素的投影。
proj2	应用于第一个范围元素的投影。

返回值

如果第一个范围在字典序上小于第二个，则为 true。

复杂度

给定 N1 为 ranges::distance(first1, last1)，N2 为 ranges::distance(first2, last2)。

最多 2 * min(N1, N2) 次比较和相应的投影应用

异常

(无)

可能的实现

ranges::lexicographical_compare

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;

示例

Main.cpp

#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';
}

输出

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