与三值比较函数相比,仅使用小于运算符进行排序

Question

在C++/STL中,仅使用less-than运算符进行排序.尽管我不知道排序算法是如何实际实现的,但我认为其他操作是隐含的:

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

与使用trivalue*compare函数(例如Java)相比,这对性能有好处,或者为什么要做出这样的设计决策呢？

我的假设是,任何trivalue compareto函数仍然必须实现这些比较,从而产生相同的性能.

**通过trivalue比较函数,我的意思是比较函数,它返回-1,0和1小于,等于和大于*

更新: 似乎太空船<=>运营商正在使用C++ 20,所以显然委员会认为只有使用的缺点operator<.

Answer 1

从某种意义上说,另外两个是隐含的,但更准确的是说,一个比较排序实际上并不需要三值比较,和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++指的是"严格的弱排序".如果<是严格的弱排序,并且!(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在某些方面更友好,并且更喜欢三向比较,其中基本单元的定义(比较)稍微复杂一些,但是由它引出的逻辑更简单.这也意味着排序算法在每次比较时获得更多信息,这有时是有用的.例如,请参阅"荷兰旗"快速排序优化,这在数据中存在大量"在同一位置"重复时是一个好处.

在这种情况下,三值比较器是速度增益.但是,C++使用的排序,也为比较一致的定义set和map,lower_bound等等,这几乎从三值比较受益(可能救人一个比较,也许不是).我猜他们决定不为了特定或有限的潜在效率增益而使他们漂亮的通用界面复杂化.