c++ - binary_search、find_if 和 <functional>

Question

std::find_if 在其重载函数之一中采用谓词。绑定(bind)器使得为用户定义的类型编写 EqualityComparators 并将它们用于动态比较或静态比较成为可能。

相比之下，标准库的二进制搜索函数采用比较器和 const T& 来比较应该用于比较的值。这对我来说感觉不一致，并且可能效率更低，因为每次都必须使用两个参数调用比较器，而不是将常量参数绑定(bind)到它。虽然有可能以使用 std::bind 的方式实现 std::binary_search，但这需要所有比较器都继承自 std::binary_function。我见过的大多数代码都不会这样做。

当将比较器与以 const T& 为值的算法一起使用时，让比较器从 std::binary_function 继承而不是让我使用 Binder ？是否有理由不在这些函数中提供谓词重载？

Answer 1

std::binary_search 的单参数谓词版本无法在 O(log n) 时间内完成。

想一想“猜猜我想到的字母”这个老游戏。你可以问:“是 A 吗？” “是 B 吗？”.. 依此类推，直到找到字母。这是一个线性或 O(n) 算法。但更聪明的做法是问“它在 M 之前吗？” “是在G之前吗？” “是在我之前吗？”依此类推，直到找到有问题的字母。这是一个对数或 O(log n) 算法。

这就是std::binary_search确实如此，要做到这一点需要能够区分三个条件:

• 候选C是搜索的项目X
• 候选C大于X
• 候选C小于X

单参数谓词 P(x) 仅表示“x 具有属性 P”或“x 不具有属性 P”。您无法从此 bool 函数获得三个结果。

比较器(比如 <)让您通过计算 C < X 和 X < C 得到三个结果。然后您有三种可能性:

• !(C < X) && !(X < C) C等于X
• C < X && !(X < C) C小于X
• !(C < X) && X < C C大于X

请注意，X 和 C 都绑定(bind)到 < 的两个参数在不同的时间，这就是为什么你不能只将 X 绑定(bind)到 < 的一个参数并使用它。

编辑:感谢 jpalecek 提醒我 binary_search 使用 <，而不是 <=。 编辑编辑:感谢 Rob Kennedy 的澄清。