为什么std :: binary_search返回bool？

Question

根据草案N4431,std::binary_search算法库中的函数返回a bool,[binary.search]:

  template<class ForwardIterator, class T>
  bool binary_search(ForwardIterator first, ForwardIterator last,
                     const T& value);

  template<class ForwardIterator, class T, class Compare>
  bool binary_search(ForwardIterator first, ForwardIterator last,
                     const T& value, Compare comp);

要求:元素e的[first,last)相对于该表达式被划分e < value和!(value < e)或comp(e, value)和!comp(value, e).此外,所有元素e的[first,last),e < value暗示!(value < e)或comp(e, value) implies !comp(value, e).

返回:true如果满足相应条件i的范围内存在迭代器[first,last): !(*i < value) && !(value < *i)或comp(*i, value) == false && comp(value, *i) == false.

复杂性:最多log ₂(last-first)+ O(1)比较.

有谁知道为什么会这样？

大多数其他泛型算法要么将迭代器返回到元素,要么迭代器等效于表示元素序列末尾的迭代器(即,在序列中考虑的最后一个元素之后),这就是我所拥有的预期.

Answer 1

这个功能的名称在1994年版的STL中isMember.我认为您同意具有该名称的函数应该返回bool

http://www.stepanovpapers.com/Stepanov-The_Standard_Template_Library-1994.pdf

Answer 2

它在 C++ 中被分成多个不同的函数，至于推理，几乎不可能说出为什么有人会以这种或那种方式做某事。binary_search会告诉你这样的元素是否存在。如果您需要知道它们的位置，请使用lower_boundand upper_boundwhich 将分别给出开始/结束迭代器。它还可以equal_range同时提供开始和结束。

由于其他人似乎认为它的创建方式是显而易见的，所以我将论证我的观点，如果您不是亚历山大·斯捷潘诺夫或与他共事的人，为什么很难/不可能回答。

遗憾的是SGI STL FAQbinary_search根本没有提及。list<>::size它解释了线性时间或pop返回的推理void。他们似乎没有认为binary_search足够特别来记录它。

我们来看看@user2899162提到的可能的性能提升：

binary_search 您可以在这里找到 SGI STL 算法的原始实现。看看它，我们几乎可以将其简化（我们都知道标准库中的内部名称有多糟糕）：

template <class ForwardIter, class V>
bool binary_search(ForwardIter first, ForwardIter last, const V& value) {
    ForwardIter it = lower_bound(first, last, value);
    return it != last && !(value < *it);
}

正如您所看到的，它是根据 实现的lower_bound并获得了相同的性能。如果他们真的希望它能够利用可能的性能改进，他们就不会以较慢的方式实现它，所以这似乎不是他们这样做的原因。

现在让我们看看它只是一个便利函数

它只是一个方便的函数似乎更有可能，但是浏览 STL，您会发现许多其他算法也可以实现这一点。看看上面的实现，您会发现它只比 a 多了一点点，std::find(begin, end, value) != end;但我们必须一直编写它，并且没有返回 a 的便利函数bool。为什么是在这里而不是所有其他算法呢？这并不是很明显，也不能简单地解释。

总之，我发现它远非显而易见，并且真的不知道我是否可以自信而诚实地回答它。