c++ - PartialOrdering、StrictWeakOrdering、TotalOrdering,在应用上的主要区别是什么

标签 c++ sorting stl partial-ordering strict-weak-ordering

[SGI official document]

Because of irreflexivity and transitivity, operator< always satisfies the definition of a partial ordering. The definition of a strict weak ordering is stricter, and the definition of a total ordering is stricter still.

而且我还阅读了文档中严格弱排序的定义:StrictWeakOrdering

The first three axioms, irreflexivity, antisymmetry, and transitivity, are the definition of a partial ordering; transitivity of equivalence is required by the definition of a strict weak ordering. A total ordering is one that satisfies an even stronger condition: equivalence must be the same as equality.

我不太确定这些定义。一些主要问题:

1.部分排序是否隐式定义了等价?

2.严格弱序全序呢?

3.STL在排序算法中要求严格的弱排序,为什么不是偏序或全序? 对于这个问题,我读过一些教科书,通过证明规则满足三个公理来证明一个有效的比较规则:非自反性、反对称性、传递性,这是偏序的定义,文档提到 operator< 总是满足这个定义,所以为什么我们不能只使用部分排序或等效地使用运算符来比较对象

最佳答案

部分排序本质上是 <= .如果两个a <= bb <= a那么你可能会说 a相当于b .但也有可能 a <= b也不b <= a ——这两个要素是不可比的。因此,您不能对具有偏序关系的集合强加全序(如 std::sort 需要)——您最多可以进行拓扑排序。您也无法推导出等价关系 - 同样,可能存在无法比较的元素。

严格的弱排序就像 < .它不允许同时拥有 a < bb < a , 如果两者都不是 a < b也不b < a , 你可以只读ab等价。

全序只是严格的弱序,其中两个元素当且仅当它们相等时才等价(只有在小于谓词之外还有相等比较谓词并且没有 C++ 标准库算法时才有意义同时使用两者,因此在这种情况下这个问题在很大程度上没有实际意义。

关于c++ - PartialOrdering、StrictWeakOrdering、TotalOrdering,在应用上的主要区别是什么,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18781405/

相关文章:

c++ - 在 C++ 中存储 XML 树的最有效数据结构

python - 为什么 Python 的 sorted() 方法不会反转字典中具有相同值的键的顺序?

c++ - C++ STL 中 SORT 的自定义比较函数?

c++ - 下限 == 上限

c++ - C++中的Pangram函数

c++ 编译问题——可以使用 cl.exe 正常编译,但无法从 Visual Studio 2015 编译

c++ - Qt:QGraphicsLineItem在QGraphicsScene中的位置

java - 同时排序两个数组

list - 如何从两个已经排序的列表中创建一个排序列表

c++ - 优先队列不排序