仅使用小于运算符与三值比较函数相比进行排序 [英] Sorting only using the less-than operator compared to a trivalue compare function
问题描述
在C ++ / STL排序中，只使用less-than运算符。 Altough我不知道如何实际实现排序算法，我假设其他操作是创建implicite：
In C++/STL sorting is done by using only the less-than operator. Altough I have no idea how the sorting algorithms are actually implemented, I assume that the other operations are created implicite:
a > b *equals* b < a == true
a == b *equals* !(a < b) && !(b < a)
与使用trivalue *比较函数
Compared to using a trivalue* compare function, like for example Java, is this good for performance, or why was this design decision made?
我的假设是，任何trivalue compareto函数仍然必须实现这些比较本身，导致相同的性能。
My assumption is that any trivalue compareto function still has to implement these comparissons in itself, resulting in the same performance.
* 通过三值比较函数，我的意思是一个比较函数，返回-1,0和1小于，等于和高于
推荐答案
在某种意义上，其他两个是隐含的，但更准确的是说比较排序需要三值比较器，并且C ++的排序以不使用一个的方式实现，以便最小化比较器所需的行为。
In a sense the other two are implicit, but more accurate would be to say that a comparison sort doesn't actually need a tri-valued comparator, and C++'s sorts are implemented in a way which doesn't use one in order to minimise the behaviour required of the comparator.
std :: sort定义并使用这样的东西是错误的：
It would be wrong for std::sort to define and exclusively use something like this:
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返回之间的差异做任何有用的事情，那么你浪费了一个比较。
... because you'd end up with an inefficient algorithm in terms of number of calls to lessthan. If your algorithm doesn't do anything useful with the difference between a 1 return and a 0 return, then you've wasted a comparison.
C ++是指订单。如果< 是严格的弱排序，！（a a == b 。他们只是在排序中的在同一个地方，！（a< b）&& ！（b 排序排序对象的等价类所需的比较器不提供总订单。
C++ refers to "strict weak orderings". If < is a strict weak ordering, and !(a < b) && !(b < a), it doesn't necessarily follow that a == b. They're just "in the same place" in the ordering, and !(a < b) && !(b < a) is an equivalence relation. So the comparator required by sort orders equivalence classes of objects, it doesn't provide a total order.
它的唯一区别是你在！（a< b）时说的。对于严格的总订单，您可以推导出 b <= a ，读为小于或等于。对于严格的弱顺序，您不能定义 b <= a 表示 b < a || b == a 并且这是真的。 C ++对这个很有意思，因为它允许操作符重载，因为人们重载操作符需要使用术语，以告诉用户他们的代码他们可以期望如何操作符的关联。 Java确实讨论了比较器和hashCode与equals一致，这是你需要的。 C ++必须处理<>，==，< =，> =，赋值的后置条件，等等。
The only difference it makes is what you say when !(a < b). For a strict total order, you would deduce b <= a, read "less than or equal to". For a strict weak order, you can't define b <= a to mean b < a || b == a and have this be true. C++ is pedantic about this, and since it allows operator overloading it pretty much has to be, since people overloading operators need the jargon in order to tell users of their code what they can expect in terms of how the operators relate. Java does talk about the comparator and the hashCode being consistent with equals, which is all you need. C++ has to deal with <, >, ==, <=, >=, the post-condition of assignment, and so on.
纯数学方法在API中，所以一切都是根据单个二元关系定义的。 Java在某些方面更加友好，并且更喜欢三向比较，其中基本单元（比较）的定义有点复杂，但是从中导出的逻辑更简单。它也意味着排序算法每次比较获得更多的信息，偶尔是有用的。有关示例，请参阅荷兰标志快速排序优化，当数据中有很多在同一地点重复时，这是一个优点。
C++ takes quite a pure mathematical approach to this in the API, so everything is defined in terms of the single binary relation. Java is friendlier in some respects, and prefers three-way comparisons where the definition of the fundamental unit (the comparison) is a bit more complex, but the logic leading from it is simpler. It also means the sort algorithm gets more information per comparison, which occasionally is useful. For an example, see the "Dutch flag" quicksort optimisation, which is a benefit when there are a lot of "in the same place" duplicates in the data.
这种情况下，三值比较器是速度增益。但是C ++使用一个比较器的一致的定义排序，并且 set 和 map ， lower_bound 等，这几乎不能从三值比较器中获益（也许保存一个比较，也许不是）。我猜想他们决定不复杂他们漂亮的，通用的界面，为了特定或有限的潜在效率增益的利益。
In that case, a three-values comparator is a speed gain. But C++ uses a consistent definition of a comparator for sort and also for set and map, lower_bound and so on, which barely benefit from a three-value comparator (maybe save one comparison, maybe not). I'd guess they decided not to complicate their nice, general interface in the interests of specific or limited potential efficiency gains.
这篇关于仅使用小于运算符与三值比较函数相比进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
