如果比较函数在C++标准算法中需要是严格的全序关系而不仅仅是严格的弱序关系，那么这些算法会更快吗？

Question

如果比较函数在C++标准算法中需要是严格的全序关系而不仅仅是严格的弱序关系，那么这些算法会更快吗？

7

许多C++标准算法，如std::sort()，假定比较器comp是一个严格弱序，不能假定comp有任何其他（好的）属性。但很多时候，comp确实具有更多的属性，不仅仅是一个严格弱序。特别地，很多时候comp是一个严格全序（因此特别地，对于所有a和b，以下情况中恰好有一个始终为真：comp(a, b)，comp(b, a)或a = b）。例如，通常在浮点数、整数和std::string上的operator<()都是严格全序。

通过仅假设comp是严格弱序，C++标准库是否限制了自己使用不太优化的算法？换句话说，如果C++标准算法假定比较器是严格的全序关系而不仅仅是严格的弱序关系，那么一些标准算法是否会比当前实现的更快？

更新：为了更准确地说明“严格的全序关系”的含义，让我们假设STL假定comp（操作类型为T的对象）具有所有漂亮的序理论属性，就像int上的operator<()一样。（因此，如果您愿意，我们还可以假设在类型为T的对象上定义了operator==()，它的工作方式与您期望的相同；这个假设是可选的，如果您愿意，您可以做出不同的假设。）是否有任何STL算法可以更快地运行？

更一般地说，如果STL对comp进行了“更好的”假设（即假设不仅仅是comp是一个简单的严格弱序关系），那么是否有任何STL算法可以更快地运行？

- Matthew K.

1

@curiousguy cc Matt，在C++20之前，你必须自己创建。在C++20中，您可以检查返回类型是否为std::strong_ordering，这是严格总序比较的新返回类型。请参见https://en.cppreference.com/w/cpp/language/default_comparisons。 - NathanOliver

8

请注意，由于NaN，浮点数上的 operator< 不是严格的排序。 - n314159

1

@n314159 不过你不必使用这些非值。 - curiousguy

2

我不知道这是否有帮助，因为我不太理解它，但是Java要求Comparator具有完全排序，如果您没有这样做，排序方法可能会抛出异常。这意味着浮点类型的排序方法对NaN进行特殊处理，将其与正常比较运算符进行不同的比较。我不确定为什么Java需要完全排序。 - Boann

2

@JaMiT，我开发了一个算法，如果比较器是全序的话，可以更高效地实现。所以我想知道STL算法中是否有类似的情况。 - Matthew K.

显示剩余16条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- curiousguy · Accepted Answer

例如，浮点数、整数和std::strings上的通常operator<()都是严格的全序关系。

因此，你只谈论状态的相似性，而不是真正的相等（在具有可变状态的语言中是什么）。

通过限制自己仅假定comp为严格弱排序，C++标准库是否限制了自己？

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

Sim(x,y) <=> !Comp(x,y) && !Comp(y,x)

因此，你有你的严格顺序，只需将Sim称为“相等”，并重载operator==来定义为Sim。

所以唯一的问题在于使用二进制比较函数的愚蠢，这意味着需要多次扫描字符串来确定相等性，而且没有三进制比较（例如像 strcmp）的访问权限。如果你直接访问 Sim，则在相等情况下仍需调用 Comp，或者先调用 Comp 再调用另一个 Comp。

只有在您事先怀疑“相等”是最可能的结果时，才会使用 Sim 然后再使用 Comp。这是荒谬的。

三路比较更适合比较序列。选择三路比较。