1

std::find_if在它的一个重载函数中接受一个谓词。Binder 可以为用户定义的类型编写 EqualityComparators 并将它们用于动态比较或静态比较。

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

在将比较器与以 a作为值而不是让我使用活页夹的std::binary_function算法一起使用时，让比较器继承自它是否有可能的好处？const T&是否有理由不在这些函数中提供谓词重载？

4

3 回答 3

8

单参数谓词版本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”。您无法从此布尔函数获得三个结果。

比较器（比如<）让您通过计算 C < X 和 X < C 来获得三个结果。然后您有三种可能性：

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

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

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

于 2010-03-03T14:12:06.210 回答
1

它们是完全不同的算法：线性find_if查找谓词为真的第一项，如果给定值在其中，则利用对范围进行排序以对数时间进行测试。binary_search

谓词 forbinary_search指定对范围进行排序所依据的函数（您很可能希望使用用于对其进行排序的相同谓词）。

您不能利用排序来搜索满足某些完全不相关的谓词的值（find_if无论如何您都必须使用）。但是请注意，使用排序范围，您可以做的不仅仅是使用lower_bound,upper_bound和测试是否存在equal_range。

这个问题，目的是什么std::binary_function是一个有趣的问题。

它所做的只是为 和 提供result_type类型first_argument_type定义second_argument_type。这些将允许用户在给定函子作为模板参数的情况下找出并使用这些类型，例如

template <class T, class BinaryFunction>
void foo(const T& a, const T& b, BinaryFunction f)
{
     //declare a variable to store the result of the function call
     typename BinaryFunction::result_type result = f(a, b);
     //...
 }

但是，我认为在标准库中使用它们的唯一地方是创建其他仿函数包装器，例如bind1st, bind2nd, not1, not2。（如果它们被用于其他目的，只要你将函数用作函子，人们就会对你大喊大叫，因为这将是一件不可移植的事情。）

例如，binary_negate可以实现为 (GCC)：

template<typename _Predicate>
class binary_negate
: public binary_function<typename _Predicate::first_argument_type,
             typename _Predicate::second_argument_type, bool>
{
protected:
  _Predicate _M_pred;

public:
  explicit
  binary_negate(const _Predicate& __x) : _M_pred(__x) { }

  bool
  operator()(const typename _Predicate::first_argument_type& __x,
     const typename _Predicate::second_argument_type& __y) const
  { return !_M_pred(__x, __y); }
};

当然，operator()可能只是一个模板，在这种情况下，那些 typedef 是不必要的（有什么缺点吗？）。可能还有元编程技术可以找出参数类型是什么，而无需用户显式地对它们进行类型定义。我想它会在某种程度上妨碍 C++0x 提供的功能 - 例如，当我想使用可变参数模板为任何数量的函数实现否定器时......

（与 和 相比，IMO 的 C++98 仿函数有点过于不灵活和原始std::tr1::bind，std::tr1::mem_fn但可能当时编译器对实现这些工作所需的元编程技术的支持并不那么好，也许这些技术仍在被发现。 )

于 2010-03-03T16:11:26.420 回答
0

这是对 C++ 中 Functor 概念的误解。

它与继承无关。使对象成为仿函数（有资格传递给任何算法）的属性分别是表达式object(x)或的有效性object(x, y)，无论它是函数指针还是具有重载函数调用运算符的对象。绝对不是从任何东西继承。这同样适用于std::bind。

使用二元仿函数作为比较器的原因在于比较器（例如std::less）是二元仿函数，能够直接使用它们是件好事。

恕我直言，提供或使用您建议的谓词版本没有任何好处（毕竟，它只需要传递一个引用）。使用 binders 不会有（性能）增益，因为它与算法做同样的事情（bind 会传递额外的参数来代替算法）。

于 2010-03-03T14:31:07.347 回答