std::lexicographical_compare_three_way() 算法

自 C++20 起

// (1)
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));

// (2)
template< class InputIt1, class InputIt2 >
constexpr auto lexicographical_compare_three_way( InputIt1 first1, InputIt1 last1,
                                                  InputIt2 first2, InputIt2 last2 );

使用三路比较按字典顺序比较两个范围 [first1; last1) 和 [first2; last2)，并生成最强适用比较类别类型的结果。

• (1) 根据 comp 返回两个范围中第一个非等效对元素的顺序（如果存在），否则（如果一个范围根据 comp 等效于另一个范围的前缀），返回两个范围长度之间的顺序。

• (2) 等效于

  return std::lexicographical_compare_three_way(first1, last1, first2, last2, std::compare_three_way());

参数

first1 last1	第一个要比较的元素范围。
first2 last2	第二个要比较的元素范围。
comp	一个函数对象类型。如果其返回类型不是三种比较类别类型（std::strong_ordering、std::weak_ordering 或 std::partial_ordering）之一，则程序格式错误 。

类型要求

InputIt1 InputIt2

LegacyInputIterator

返回值

上述指定的比较类别类型的值。

复杂度

最多 N 次 comp 应用，其中 N 是两个范围中较小者的长度。

异常

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

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

可能的实现

lexicographical_compare_three_way(1)

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

示例

Main.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);
    }
}

输出

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