问题标签 [strict-weak-ordering]

来自http://stdcxx.apache.org/doc/stdlibref/less-equal.html

--

您可以将 less_equal 对象传递给任何需要二进制函数的算法。例如，sort() 算法可以接受二进制函数作为替代比较对象来对序列进行排序。less_equal 将在该算法中以下列方式使用：

--

现在我很困惑，上面的文档是否正确？

【SGI官方文档】

由于非自反性和传递性，operator< 总是满足偏序的定义。严格弱序的定义更加严格，全序的定义更加严格。

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

前三个公理，非自反性、反对称性和传递性，是偏序的定义；等价的传递性是严格弱排序的定义所要求的。全序是满足更严格条件的排序：等价必须与等价相同。

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

1.偏序是否隐含地定义了等价？

2.严格弱排序和全排序呢？

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

我知道要使用std::sort()，比较函数必须是严格的弱序，否则会因为访问地址越界而崩溃。（https://gcc.gnu.org/ml/gcc-bugs/2013-12/msg00333.html）

但是，当比较函数不是严格的弱顺序时，为什么 std::sort() 会访问越界地址？它试图比较什么？

另外我想知道 STL 中是否还有其他我应该注意的陷阱。

我有以下问题：考虑这个（简化的）结构：

现在我想要一组所有的任务并用它做一些工作。因此我有一个相等运算符，它检查每个元素是否相等。

为此，我使用了 std::unordered_set，效果很好。

但是现在我希望这些任务按它们在集合中的优先级（以获得最高优先级的任务）进行排序。显然，这对于 std::unordered_set 是不可能的，所以我尝试了一个带有以下 less 运算符的 std::set：

但这意味着通过严格的弱排序，当优先级相等时，两个任务是相等的，这是我不想要的（我想维护我的 isEqual 方法进行相等性检查）。

完成一组任务的最佳方法是什么，我可以非常快速地插入元素并且没有重复条目（由我的 isEqual 函数定义），但能够非常快速地检索具有最高优先级的任务？
我没有绑定到任何特定的 STL 容器，但不想使用任何第三方库（甚至没有提升）。

Field2 在我的数据中并不总是可用，所以有时我使用通配符值 0，它可以匹配 field1 匹配的任何值。如果我从不插入具有通配符值的元素并且只在集合中查找它们，这在 C++ 中是否有效？我可以接受 find 函数在这种情况下返回任何值，这在我的代码中很少发生，但希望在重复调用时它会是相同的值。

根据规范，binary_search 似乎不需要严格的弱排序，这应该是执行查找时在数据结构上使用的唯一算法，对吧？还是我应该担心一些未定义的行为？

25.4 排序及相关操作

...为了使 25.4.3 中描述的算法以外的算法正常工作，comp 必须对值进行严格的弱排序...

25.4.3 二分查找

我一直在玩 STL 容器和它们支持的比较函数/函子，但是我发现 priority_queue 不遵循通常的严格弱排序，我试图了解可能是什么原因但无法弄清楚，任何指针会有所帮助。

在这篇博客中还提到，priority_queue 不遵循严格的弱排序。在此处输入链接描述

是否有任何现有的 Python2 实现，其中排序是可传递的？也就是说，如果不创建用户定义的类型就不可能看到这种行为：

由于这个反例，CPython 不具有传递性

但是，CPython 中的这种排序仅记录为实现细节。

我最近一直在阅读内存重新排序。我的问题是关于多线程场景。考虑下面的例子：

我一直在 X86-64 Windows 平台上编码，从未考虑过可以重新排序 A 和 B 的存储（在编译器级别或硬件级别），我可能最终在线程 2 中得到 B = 0 并发现 A 仍然存在0. 并且从来没有遇到过这样的代码的任何问题或讨厌的错误。是不是因为 x86-x64 是强排序的，windows C 编译器也是如此。

对于要在具有弱排序内存的任何其他平台上执行这样的代码，我是否需要确保在锁内更​​新和访问 A 和 B（假设底层锁实现使用内存屏障并确保仅在所有先前的加载和存储在所有处理器内核上都是可见的）。

谢谢

我知道我应该对 c++ 比较器遵循严格的弱排序。主要原因是!(a > b) && !(b > a)应该充当等价运算符。

但问题只是在不需要等价运算符的地方进行排序，而不是 like std::set。

例如，有集合的向量，如果集合 A 是 B 的真子集，那么经过排序后，集合 A 的索引应该小于集合 B 的索引。

所以假设你这样写比较器

那么std::sort这个比较器是否总是像拓扑排序一样工作？

加）

感谢 Oliver Charlesworth 缺少信息。

我真的很想知道这样的比较器可以使用快速排序或插入排序（一些著名的基于比较的排序算法）作为拓扑排序。

我在 std::sort 的比较函数中遇到严格的弱排序问题。我不明白为什么这会失败。

我有一些嵌套结构：

std::vector<Trade>在我的代码中，在某些时候我有一个我想要排序的填充。

我的排序功能：

我的比较功能：

在运行该函数并进行调试时，我的第一个项目compareDateAndTime()在其中一个语句（月）上返​​回 true 后传递给传递。下一项在小时比较时返回 true，但随后我得到“调试断言失败！” 使用“表达式：无效的运算符<”。

做一些谷歌搜索，这与严格的弱排序有关。但是为什么在比较 int 变量时会失败呢？