带有三路比较谓词的STL函数

Question

有没有类似于 std::sort()、std::binary_search()、std::lower_bound() 和std::upper_bound() 这样接受三向比较谓词（如果小于则返回-1，相等则返回0，大于则返回1）而不是 less 谓词（如果小于则返回 true，等于或大于则返回 false）的 STL 函数库？

当然，less 谓词可以很容易地从现有的三向谓词中构造出来（例如像 [](A a, B b) { return compare3(a,b)<0; }），但这会导致对谓词进行额外的调用。

- user222202

---

重点是什么？无论如何你都必须测试两次返回值。这些谓词不应该太复杂，它们应该是简单的和内联的，以便重复调用不会受到惩罚。 - littleadv

重点是：检查谓词的结果是int，这是一种廉价的测试方式（甚至更多，检查int是否小于0、等于0和大于0可以被编译器优化为一次检查）。 比较对象可以是任意重的（字符串、复杂对象）。 - user222202

@user222202 - 哪种算法会利用这种三重检查？ - littleadv

@user222202：*_bound不能这样做，因为如果这样做会返回错误的结果。关于binary_search，请参阅 Knuth 的《计算机程序设计艺术》以获取有关为什么这种“优化”具有可疑价值的详细分析。 - Yakov Galka

@user222202 - 你知道STL是一个通用库，具有任何人都可以使用并期望合理（预定义）性能的通用算法吗？你总是可以实现针对你要求进行优化的算法，并使它们表现更好，但你不能从通用库中期望这样做，因为对于你而言的优化可能会破坏其他人的结果，而你不会关心。通用库无法做到这一点。 - littleadv

Answer 1

如果你看上面算法的实现，你会发现lower/upper_bound根本不进行三路分支，binary_search只在最后一次迭代中进行三路分支以检查相等性，至于sort()，我不知道但我几乎可以肯定它也不进行三路分支。所以你的“优化”不会给你任何提升。相反，你的比较将会更慢。

- Yakov Galka

---

这就是为什么我正在寻找适用于三元谓词的实现（特别是经过优化的）。 - user222202

@user222202，换句话说，大多数基于比较的算法在超过90％的比较中只需要等于==或小于<。这是算法的属性，而不是实现的属性。 - Yakov Galka

实际上，对于某些算法（如lower_bound），C++标准仅要求定义(*iter < value)，而(value < *iter)则不是必需的。 - Yakov Galka

@ybungalobill，无论是二分搜索还是二叉树搜索（用于map和set），每当比较返回false时（通常占50%的情况），都必须使用交换后的参数进行第二次调用。这是因为应该插入或删除的元素必须被识别。另一方面，对于sort()来说，我认为这并不重要，因为你所需要做的就是纠正a[i]<a[j]但i>j的位置。 - Jo So

@JoSo：这完全不正确。标准还要求最多进行 log2(N) + O(1) 次比较。请参见此处的参考实现。我还记得 Knuth 在《计算机程序设计艺术》第三卷中对此有很好的描述。 - Yakov Galka