9

在 C++/STL 中，排序仅通过使用小于运算符来完成。虽然我不知道排序算法是如何实际实现的，但我假设其他操作是隐式创建的：

a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)

与使用三值 * 比较函数（例如 Java）相比，这对性能有好处吗？或者为什么做出这个设计决定？

我的假设是任何三值比较函数仍然必须自己实现这些比较，从而获得相同的性能。

**通过三值比较函数，我的意思是一个比较函数，它返回 -1、0 和 1 表示小于、等于和高于*

更新： C++20 中 似乎有一个宇宙飞船<=>操作符，所以显然委员会认为只使用operator<.

4

3 回答 3

11

在某种意义上，其他两个是隐含的，但更准确的说法是比较排序实际上不需要三值比较器，并且 C++ 的排序以不使用三值比较器的方式实现，以最小化比较器所需的行为。

std::sort 定义和专门使用这样的东西是错误的：

template <typename T, typename Cmp>
int get_tri_value(const T &a, const T &b, Cmp lessthan) {
    if (lessthan(a,b)) return -1;
    if (lessthan(b,a)) return 1;
    return 0;
}

...因为在调用lessthan. 如果您的算法对返回 1 和返回 0 之间的差异没有任何用处，那么您就浪费了比较。

C++ 指的是“严格的弱排序”。If<是严格的弱排序，并且!(a < b) && !(b < a)，它不一定遵循a == b。它们只是在排序中“在同一个地方”，并且!(a < b) && !(b < a)是等价关系。因此，sort订单等价类对象所需的比较器不提供总订单。

它唯一的区别是你在什么时候说什么!(a < b)。对于严格的总顺序，您会推断b <= a，阅读“小于或等于”。对于严格的弱顺序，您不能定义b <= a为意味着b < a || b == a并使其为真。C++ 对此很迂腐，因为它允许运算符重载，所以它几乎必须如此，因为重载运算符的人需要行话来告诉用户他们的代码他们在运算符之间的关系方面可以期待什么。Java确实谈到了比较器和hashCode与equals一致，这就是你所需要的。C++ 必须处理 <、>、==、<=、>=、赋值的后置条件等等。

C++ 在 API 中对此采用了相当纯的数学方法，因此所有内容都根据单个二进制关系定义。Java 在某些方面更友好，并且更喜欢三路比较，其中基本单元的定义（比较）有点复杂，但由此得出的逻辑更简单。这也意味着排序算法每次比较都会获得更多信息，这有时很有用。例如，请参阅“荷兰国旗”快速排序优化，当数据中有很多“在同一个地方”重复时，这是一个好处。

在这种情况下，三值比较器是速度增益。set但是 C++ 对 sort 和andmap等使用了一致的比较器定义lower_bound，这几乎没有从三值比较器中受益（可能保存一个比较，也可能没有）。我猜他们为了特定或有限的潜在效率收益而决定不使他们漂亮的通用界面复杂化。

于 2010-03-05T12:20:32.640 回答
1

我在 C++ 中的猜测只是为了减少代码重复：一旦在类/类型上定义了比较操作，您不仅可以通过简单地编写 a < b 来比较这些对象，还可以获得对集合进行排序的能力这样的物体。

至于排序，我们只需要小于运算符，为什么要引入额外的东西呢？:)

于 2010-03-05T09:39:39.780 回答
0

如果您指的是 std::sort()，则它仅使用 less() 运算符，因为它不需要保留等效元素的相对顺序，因此它只需要 less() 运算符和隐式的更大() 运算符。

虽然 std::stable_sort 会保留它，但速度较慢。它需要 less() 运算符和双向迭代器来交换 equal() 运算符来构造“三值”比较函数

于 2010-03-05T11:05:38.037 回答