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

从某种意义上说,另外两个是隐含的,但更准确的说法是,比较排序实际上并不存在 一个三值比较器和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 . 他们只是“在同一个地方”,而且 sort 订单 等价类

唯一不同的是你什么时候说什么 !(a < b) b <= a ,改为“小于或等于”。对于严格的弱序,你不能定义 b<=A. 意思 b < a || b == a

C++在API中采用了相当纯的数学方法,所以所有的事物都是以单一的二元关系定义的。Java在某些方面更友好,并且更喜欢三方比较,其中基本单元(比较)的定义稍微复杂一点,但是从中引出的逻辑更简单。这也意味着排序算法在每次比较中获得更多的信息,这有时是有用的。例如,请参阅“荷兰国旗”快速排序优化,当数据中存在大量“在同一位置”重复项时,这是一个好处。

set map , lower_bound 以此类推,三值比较器几乎没有什么好处(也许可以保存一个比较,也许不能)。我猜他们决定不为了获得特定或有限的潜在效率收益而使他们友好的、通用的接口复杂化。

我在C++中的猜测是为了减少代码复制:一旦定义了类/类型上的比较OP,就可以通过简单地编写一个LT来比较这些对象。b、 同时也获得了对这类对象进行排序的能力。

至于排序,我们只需要少于运算符,为什么要引入额外的东西?:)