三元比较运算符是否总是高效的？

Question

在他的“宇宙飞船”运算符提案中（第2.2.2节，第12页底部），Herb Sutter说：

基于 <=> 和其返回类型：这种模型具有重大优势，与之前对C++和其他语言的建议相比，一些独特之处：

[...]

(6)效率，包括最终实现零开销抽象比较：绝大多数比较总是单通道的。唯一的例外是，在支持部分排序和相等性的类型情况下生成 <= 和 >=。对于<，单通道是实现零开销原则的关键，以避免重复相等比较，例如用于struct Outer { Employeee; /*more members*/ };的struct Employee { string name; /*more members*/ }——今天的比较违反了零开销抽象，因为Outer上的operator <执行冗余的相等比较, 它执行if (e != that.e) return e < that.e;，这会两次遍历e.name的相等前缀（如果名称相同，则其他Employee成员的相等前缀也会被遍历两次），这通常无法优化。正如Kamiński所指出的那样，零开销抽象是C++的支柱，并且首次实现其比较是基于<=>的设计的显着优势。

但是他随后举了这个例子（第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。

这里有什么我没有注意到的地方吗？

- Cris Luengo

---

我同意你的观点。在这种情况下，两个项目之间可能存在无关性，因此需要进行详尽搜索，使用太空船运算符实现可以提供更高的可维护性，但可能会牺牲一定的运行时体验。 - Richard Hodges

优化方面怎么样？如果您执行a<=>b > 0，进入小于和等于分支有什么用呢？ - Robert Andrzejuk

只有编译器能够证明is_the_same_person_as和is_transitive_child_of都是无副作用的，并且if语句条件中最多只有一个条件会同时为真，才可能发生这种情况。换句话说，这种可能性非常小。 - TLW

Answer 1

定义operator>(a,b)为a<=>b > 0，会带来一些性能开销。然而，具体的开销大小是相对的。在比较运算的成本与程序其他部分的成本相比微不足道的情况下，通过实现一个运算符而不是五个来减少代码重复可能是可以接受的折衷方案。

然而，这个提案并没有建议删除其他比较运算符以支持 <=>，如果你想重载其他比较运算符，你可以自由地这样做： 做到通用： 不要限制本质属性，不要武断地限制完整的使用集合，避免特殊情况和部分功能。例如，本文支持所有七个比较运算符和操作，包括通过 <=> 添加三路比较。它还支持所有五个主要的比较类别，包括偏序。

- Sergey Kalinichenko

---

当然，您仍然可以手动重载运算符，但是Herb的评论“最终实现了零开销比较抽象”似乎并不总是正确的。 - Cris Luengo

Herb在这种情况下使用零开销抽象的意思是，假设有一个只包含operator <和operator ==（例如来自库的）的类型，如果该库提供了operator <=>，那么用户无法手动编写比编译器更好的<=实现。如果使用了这个新语言特性（在像词典顺序这样的高效三路比较的情况下），用户将来不会遇到任何开销。虽然上面的问题不成立，但由于如果不使用它就不需要支付费用，所以这很好。 - Araeos

@Araeos - “如果你不使用它，你就不需要为它付费”这种说法是不正确的，例如，如果你正在使用的库函数决定使用operator<= /等来实现<=>。 - TLW

Answer 2

对于“large”的某些定义。由于在部分排序中，a == b当且仅当a <= b和b <= a，因此会产生开销。复杂度将与拓扑排序相同，为O(V+E)。当然，现代C++的方法是编写安全、清晰和易读的代码，然后再进行优化。您可以选择先实现飞船操作符，然后在确定性能瓶颈后再进行特殊化。

- user9163035

---

我同意你关于先编写清晰代码，再进行优化的评论。那总是一个很好的建议！ - Cris Luengo

Answer 3

一般来说，当你处理的类型一次比较要么只是微不足道地更昂贵，要么与不同的比较相同的成本时，重载<=>是有意义的。

对于字符串而言，<=>似乎比直接使用==测试更昂贵，因为您必须减去每对两个字符。但是，由于您已经必须将每对字符加载到内存中，因此在此基础上添加一个减法是微不足道的开销。实际上，有时编译器将两个数字进行相等性比较实现为减法并针对零进行测试。即使对于不执行该操作的编译器，减法和针对零进行比较也可能没有明显的效率差异。

因此，对于基本类型，您可以更或多或少地正常运行。

当您处理像树排序这样的东西时，您确实需要事先知道您关心哪个操作。如果您只要求==，那么您真的不想搜索其余部分的树以了解它们是否不同。

但就个人而言……我从不使用比较运算符来实现类似树排序的东西。为什么？因为我认为这样的比较应该是逻辑上快速的操作。而树搜索是非常缓慢的操作，您真的不想在意外情况下或除了绝对必要的时候进行操作。

看看这种情况。在家谱中说某个人“小于”另一个人到底意味着什么？这意味着其中一个是另一个的孩子。直接用is_transitive_child_of提出这个问题，在代码中更可读，不是吗？

你的比较逻辑越复杂，你所做的事情就越不可能是真正的“比较”。这里可能有一些文本描述，可以称之为“比较”操作，这样会更易读。

当然，这样的类可以有一个函数，返回表示两个对象之间关系的partial_order。但我不会称该函数为operator<=>。

但无论如何，<=>是否是比较的零开销抽象？不是；您可以构造案例，其中计算排序的成本显着高于检测您请求的特定关系的成本。但就我个人而言，如果是这种情况，您很可能根本不应该通过运算符进行此类类型的比较。

- Nicol Bolas