std::ranges::lexicographical_compare

定义于头文件 `<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>, 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 = {} );	(1)	(C++20 起)
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 = {} );	(2)	(C++20 起)

检查第一个范围 [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。

[编辑] 复杂度

最多应用比较和相应投影 $2\cdotmin(N1, N2)$ 次，其中 N1 = ranges::distance(first1, last1) 且 N2 = ranges::distance(first2, last2)。

[编辑] 可能的实现

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;

[编辑] 示例

运行此代码

#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

[编辑] 参阅

ranges::equal (C++20)	判断两组元素是否相同 (算法函数对象)[编辑]
lexicographical_compare	如果一个范围在字典上小于另一个范围，则返回 true (函数模板) [编辑]

编译器支持
自由（freestanding）与宿主（hosted）
语言
标准库
标准库头文件
具名要求
特性测试宏 (C++20)
语言支持库
概念库 (C++20)
诊断库
内存管理库
元编程库 (C++11)
通用工具库
容器库
迭代器库
范围库 (C++20)
算法库
字符串库
文本处理库
数值库
日期和时间库
输入/输出库
文件系统库 (C++17)
并发支持库 (C++11)
执行控制库 (C++26)
技术规范
符号索引
外部库

cppreference.cn

命名空间

变体

视图

操作