三路比较运算符总是有效的吗？

Question

Herb Sutter 在他的 proposal for the "spaceship" operator（第 2.2.2 节，第 12 页底部）中说：

Basing everything on <=> and its return type: This model has major advantages, some unique to this proposal compared to previous proposals for C++ and the capabilities of other languages:

[...]

(6) Efficiency, including finally achieving zero-overhead abstraction for comparisons: The vast majority of comparisons are always single-pass. The only exception is generated <= and >= in the case of types that support both partial ordering and equality. For <, single-pass is essential to achieve the zero-overhead principle to avoid repeating equality comparisons, such as for struct Employee { string name; /*more members*/ }; used in struct Outer { Employeee; /*more members*/ }; – today’s comparisons violates zero-overhead abstraction because operator< on Outer performs redundant equality comparisons, because it performs if (e != that.e) return e < that.e; which traverses the equal prefix of e.name twice (and if the name is equal, traverses the equal prefixes of other members of Employee twice as well), and this cannot be optimized away in general. As Kamiński notes, zero-overhead abstraction is a pillar of C++, and achieving it for comparisons for the first time is a significant advantage of this design based on <=>.

但随后他给出了这个例子（第 1.4.5 节，第 6 页）：

class PersonInFamilyTree { // ...
public:
  std::partial_ordering operator<=>(const PersonInFamilyTree& that) const {
    if (this->is_the_same_person_as ( that)) return partial_ordering::equivalent;
    if (this->is_transitive_child_of( that)) return partial_ordering::less;
    if (that. is_transitive_child_of(*this)) return partial_ordering::greater;
    return partial_ordering::unordered;
  }
  // ... other functions, but no other comparisons ...
};

将 operator>(a,b) 定义为 a<=>b > 0 不会导致大量开销吗？（尽管形式与他讨论的不同）。该代码将首先测试相等性，然后测试 less，最后测试 greater，而不是仅直接测试 greater.

我是不是漏掉了什么？

Answer 1

Would define operator>(a,b) as a<=>b > 0 not lead to large overhead?

它会导致一些开销。但是，开销的大小是相对的 - 在运行比较的成本相对于程序的其余部分可以忽略不计的情况下，通过实施一个运算符而不是五个运算符来减少代码重复可能是一个可以接受的权衡。

但是，该提案不建议删除其他比较运算符以支持<=>：如果你想重载其他比较运算符，你可以随意：

Be general: Don’t restrict what is inherent. Don’t arbitrarily restrict a complete set of uses. Avoid special cases and partial features. – For example, this paper supports all seven comparison operators and operations, including adding three-way comparison via <=>. It also supports all five major comparison categories, including partial orders.

Answer 2

对于一些大的定义。存在开销，因为在部分排序中，a == b iff a <= b 和 b <= a。复杂度与拓扑排序相同，O(V+E)。当然，现代 C++ 方法是编写安全、干净和可读的代码，然后然后优化。您可以选择先实现飞船操作符，然后在确定性能瓶颈后进行专门化。

Answer 3

一般来说，当您处理一种类型时，重载 <=> 是有意义的，在这种类型中，一次进行所有比较要么只是稍微贵一点，要么与以不同方式进行比较的成本相同。

对于字符串，<=> 似乎比直接 == 测试更昂贵，因为您必须减去每对两个字符。然而，由于您已经必须将每对字符加载到内存中，因此在其之上添加一个减法是微不足道的开销。事实上，比较两个数字是否相等有时由编译器作为减法和针对零的测试来实现。即使对于不这样做的编译器，减去零并与零进行比较的效率也可能不会显着降低。

所以对于像这样的基本类型，你或多或少没问题。

当您处理诸如树排序之类的事情时，您确实需要知道 up-front 您关心的是哪个操作。如果您只要求==，您真的不想为了知道它们不相等而必须搜索树的其余部分。

但就我个人而言...我绝不会一开始就使用比较运算符来实现树排序之类的东西。为什么？因为我认为这样的比较在逻辑上应该是快速的操作。鉴于树搜索是如此缓慢的操作，您真的不想偶然或在绝对必要之外的任何时候这样做。

看看这个案例。说家谱中的一个人是 "less than" 另一个人到底是什么意思？这意味着一个是另一个的child。直接用 is_transitive_child_of?

问这个问题在代码中不是更具可读性吗？

您的比较逻辑越复杂，您所做的真正是 "comparison" 的可能性就越小。可能有一些文本描述可以调用此 "comparison" 操作，这将更具可读性。

哦，当然，这样的class可以有一个函数，returns一个partial_order表示两者之间的关系objects。但我不会调用该函数 operator<=>.

但无论如何，<=>是比较的zero-overhead抽象吗？不;您可以构建这样的案例，其中计算排序的成本远高于检测您要求的特定关系的成本。但就个人而言，如果是这种情况，您很有可能根本不应该通过运算符 .

来比较此类类型

三路比较运算符总是有效的吗？

Is the three-way comparison operator always efficient?

c++

operators

spaceship-operator

c++20