c++ - 为什么 std::binary_search 使用 ForwardIterator 而不是 RandomIterator？

Question

我很惊讶它如何在使用不支持 auto middle = first + (last - first)/2; 的 ForwardIterator 时计算 middle。

Answer 1

当然，即使它不是随机迭代器，您也可以计算元素的数量。

如果是随机迭代器，只需要last - first就可以在常数时间内得到，如果不是，至少可以first一个一个地推进，直到last，并以线性复杂度获取计数。

应该实现的是根据iterator标签进行调度，下面是std::advance的实现图示例，展示了如何根据iterator的类型进行调度:

template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n,
input_iterator_tag)
{
    while (n--) ++i;
}
template <class ForwardIterator, class Distance>
inline void __advance(ForwardIterator& i, Distance n,
forward_iterator_tag)
{
    advance(i, n, input_iterator_tag());
}
template <class BidiectionalIterator, class Distance>
inline void __advance(BidiectionalIterator& i, Distance n,
bidirectional_iterator_tag)
{
    if (n >= 0)
        while (n--) ++i;
    else
        while (n++) --i;
}
template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n,
random_access_iterator_tag)
{
    i += n;
}
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}