std::lexicographical_compare() 算法

自 C++20 起

// (1)
template< class InputIt1, class InputIt2 >
constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );

// (2)
template< class InputIt1, class InputIt2, class Compare >
constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2 );

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2,
                              Compare comp );

自 C++17 起

// (1)
template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );

// (2)
template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );

// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2 );

// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
                              ForwardIt1 first1, ForwardIt1 last1,
                              ForwardIt2 first2, ForwardIt2 last2,
                              Compare comp );

C++17 之前

// (1)
template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );

// (2)
template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );

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

• (1) 元素使用 operator< 进行比较。

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

• (2 - 4) 同 (1)，但根据 policy 执行。

  重载决议

  仅当 std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>  (C++20 前) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>  (C++20 起) 为 true 时，这些重载才参与重载决议。

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

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

参数

first1 last1	第一个要比较的元素范围。
r1	第一个要比较的元素范围。
first2 last2	第二个要比较的元素范围。
r2	第二个要比较的元素范围。
proj1	应用于第一个范围元素的投影。
proj2	应用于第二个范围元素的投影。
comp	比较函数对象（即满足Compare要求的对象），如果第一个参数小于第二个，则返回true。 比较函数的签名应等效于以下内容 bool cmp(const Type1 &a, const Type2 &b); 签名不需要有 `const&`，但不得修改参数。 必须接受类型（可能是 const）Type和Type2的所有值，无论值类别如何（因此不允许Type1&，也不允许Type1，除非对于Type1移动等同于复制 (C++11 起)） 类型 Type1 和 Type2 必须是这样的：类型为 InputIt1 和 InputIt2 的对象可以被解引用然后隐式转换为它们。

类型要求

InputIt1 InputIt2	LegacyInputIterator
ForwardIt1 ForwardIt2	LegacyForwardIterator
Compare	Compare

返回值

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

复杂度

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

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

异常

带有模板参数 ExecutionPolicy 的重载报告错误如下

• 如果作为算法一部分调用的函数执行抛出异常并且 ExecutionPolicy 是标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为是实现定义的.
• 如果算法未能分配内存，则抛出 std::bad_alloc。

可能的实现

lexicographical_compare(1) 和 lexicographical_compare(2)

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