如果要求比较器是严格的总排序，而不仅仅是严格的弱排序，C标准算法会更快吗？

Question

许多C标准算法，如std::排序（），假设比较器comp是一个严格的弱排序，并且不能假设comp具有任何其他（不错的）属性。但是很多时候comp确实有更多的属性，而不仅仅是一个严格的弱排序。特别是，很多时候comp是一个严格的总顺序（所以特别是，对于所有a和b：comp（a， b），comp（b， a）或a=b总是正确的。例如，通常的运算符

通过仅假设comp是严格的弱排序，C标准库是否限制自己使用非最优算法？换言之，如果C标准算法假设比较器是严格的总排序而不是严格的弱排序，那么某些标准算法会比当前实现的算法更快吗？

更新：更确切地说，“严格的总排序”意味着什么，让我们假设STL假设＜code＞comp＜/code＞（对＜code＞T＜/code＞类型的对象进行操作）具有＜code＞运算符的所有良好的序理论性质

更一般地说，如果STL对comp做出了“更好”的假设（即假设comp不仅仅是严格的弱排序），那么任何STL算法都可以更快吗？




Answer 1

例如，通常的运算符

所以你只是在谈论状态的相似性，而不是真正的相等性(不管在一种具有可变状态的语言中是什么)。

通过限制自己只假设comp是一个严格的弱排序，C标准库限制了自己吗

不，前提是错误的。容器和算法库（生成排序序列的算法、在排序范围上操作的算法以及有序关联容器）并没有以任何方式限制其自身：它明确表示，可以根据比较Comp来定义等价关系，据我所知，该等价关系未命名（让我们称之为Sim）：

Sim (x，y)

所以你有你的严格命令，只需将Sim称为“相等”并重载运算符==以定义为Sim。

所以唯一的问题是使用二进制比较函数的愚蠢，这意味着对f.ex进行多次扫描。字符串来确定相等性，并且无法访问三元比较（如 strcmp）。如果您可以直接访问 Sim，在平等的情况下，您仍然会称 Comp 而不是 Sim，或者称 Comp 然后调用另一个 Comp。

只有当你先验地怀疑“相等”是最可能的结果时，你才会使用Sim，然后使用Comp。这是荒谬的。

三种方法比较序列更好。走三条路。