主页 / coding / 问题 / 79185202
Accepted
PiotrNycz
Asked: 2024-11-13 21:50:04 +0800 CST

std::ranges::sort 不能与非默认运算符 <=> 一起使用？

  • 772

我有一个案例，当结构类型需要非默认时operator<=>- 在定义对象顺序时并非所有字段都很重要。

struct A
{
    int a;
    int b; // not important when ordering
    int c;

    constexpr std::strong_ordering operator<=>(const A& rhs) const
    {
        if (const auto res = a<=>rhs.a; res != 0) return res;
        return c<=>rhs.c;
    }
};

令我惊讶的是，我不能使用这种类型的容器作为参数std::ranges::sort：

std::array<A, 100> aa{};
std::ranges::sort(aa);

我在最新的 gcc (14) 和 clang (19) 上检查了它，它基本上声称范围不可排序，因为std::invocable_v<std::ranges::less&, A&, A&>事实并非如此。请参阅godbold 链接

更多观察：

  1. 它与 std::sort( std::sort(aa.begin(), aa.end());)一起使用
  2. 添加非默认时有效operator==
  3. 并且它与默认值 ( =default)一起使用operator<=>

这是编译器错误、C++ 标准错误还是某些奇怪的 C++ 规则在这里起作用，并且应该是这样的？如果最后一个选项是正确的 - 您能为这种行为提供理由吗？

更新：

从评论来看，似乎std::ranges::less{}(A{}, A{})不仅需要operator<（派生自operator<=>），而且operator==不能从非默认派生而来，operator<=>因此出现错误。

但仍然存在一个问题——为什么std::ranges::less需要operator==？

评论中的更好的例子：链接

c++

2 个回答

  1. 总体而言，std::ranges算法比算法受到更多限制std::。目标不是提供算法所需的绝对最小操作集，而是提供具有凝聚力的操作模型。

    在这种情况下，所有基于排序的算法都需要排序和相等性。在其他几种语言中，如果不提供相等性，您甚至无法选择排序。这是较弱的功能，因此同时提供两者是有意义的。

    因此std::ranges::sort(aa)失败，因为虽然A提供了排序（<=>），但它不提供相等性（==）。所以你的选择是：

    • 要么提供相应的==运算符（同样不考虑b），要么
    • 提供自定义排序sort（不会查看b）。

    请注意，范围算法确实支持投影，因此后者可能看起来像：

    std::ranges::sort(aa, std::ranges::less(), [](A const& a){ return std::tie(a.a, a.c); });

    您可以将其包装在像这样的可爱的适配器中：

    std::ranges::sort(aa, std::ranges::less(), by(&A::a, &A::c));
    • 4
  2. Best Answer

    排序算法依赖于被排序项是完全有序的（在数学意义上）。这意味着存在一个自反、传递、反对称的顺序，并且为了成为全序，必须强连通，这意味着对于任何a和b，

    a <= b || b <= a

    或者：

    if (a != b) then a <= b or b <= a

    并且由于反对称性要求，它要么a <= b要么b <= a。这又意味着对于任何集合，a, b, c, ...都存在一个排列，x, y, z, ...使得x <= y <= z <= ...，或者换句话说：该集合可以排序。

    因此，其操作数必须完全有序的约束ranges::less不仅是为了要求某些运算符可用，也是为了表明这些运算符必须具有某些语义。然后可以在可用运算符具有这些语义的假设下编写算法。

    这就是为什么 C++20 中的概念除了类型要求外，通常还有语义要求。编译器不会强制执行语义要求，但开发人员在定义建模概念的类型时应该遵守这些要求，因此，当类型建模概念时，开发人员可以假设该类型也满足概念的所有语义要求。

    如果类型是全序的，则所有比较运算符都已明确定义，并且可以（在数学上）仅从<运算符推断出来。因此，该totally_ordered概念要求所有运算符都可用，只是因为它对于全序类型有意义，并且因为使用该运算符定义所有运算符很容易<=>。

    ==但是，出于性能原因，当类型具有自定义运算符时，编译器不会自动生成运算符<=>，因为<=>可能无法像 那样高效地实现==，并且不能保证隐式提供的==运算符具有与根据（自定义）运算<=>符实现的相同的语义。例如，在比较字符串时，==对于具有不同长度的字符串，时间复杂度可以达到 O(1)，而<=>不能。

    因此，如果<=>不是默认值，则必须明确定义==以便定义所有比较运算符，这对于建模概念是必需的totally_ordered，这是所需的ranges_less，这是使用的ranges::sort，因为排序算法需要完全排序才能按设计工作。

    另请参阅对另一个问题的回答。

    • 1

相关问题