c++ - std::lower_bound 中没有简单的情况？

Question

为什么 std::lower_bound( ) 中的第一步没有简单的比较?

作为初始步骤 std::lower_bound更改迭代器 it来自 first在列表的中心位置:

step = std::distance(first,last) / 2;
it = std::advance(first, step);

之后算法开始比较那个中心- it给定 value :

if (*it < value) { ... } else { ... }

但最简单的情况是在重新定位之前进行一次比较作为初始步骤 it :

if (value < *first) return last;
// else start original algorithm ...

假设有一个很长的列表，您仍然需要等到 std::lower_bound。在目前的形式中，value < *first是真的。当然它是 O( log_2( last - first ) )，但在这种情况下它可能是 O(1) 只有一个额外的行。

Answer 1

这种实现 lower_bound 的方式允许您进行这种琐碎的检查，否则您将总是被迫进行这种检查。从“你不用为你不用的东西付费”的意义上来说，这对我来说很有意义。

因为 lower_bound 仅适用于排序结构，如果您认为值得，您可以随时与第一个元素进行比较。

尽管如此，实际的实现看起来还是有所不同，因此一些 STL 实现可能实际上会执行此检查。

来自 SGI 的实现例如看起来像这样(检查未完成!):

template <class _ForwardIter, class _Tp, class _Distance>
_ForwardIter __lower_bound(_ForwardIter __first, _ForwardIter __last,
                           const _Tp& __val, _Distance*) 
{
  _Distance __len = 0;
  distance(__first, __last, __len);
  _Distance __half;
  _ForwardIter __middle;

  while (__len > 0) {
    __half = __len >> 1;
    __middle = __first;
    advance(__middle, __half);
    if (*__middle < __val) {
      __first = __middle;
      ++__first;
      __len = __len - __half - 1;
    }
    else
      __len = __half;
  }
  return __first;
}

template <class _ForwardIter, class _Tp>
inline _ForwardIter lower_bound(_ForwardIter __first, _ForwardIter __last,
                const _Tp& __val) {
  __STL_REQUIRES(_ForwardIter, _ForwardIterator);
  __STL_REQUIRES_SAME_TYPE(_Tp,
      typename iterator_traits<_ForwardIter>::value_type);
  __STL_REQUIRES(_Tp, _LessThanComparable);
  return __lower_bound(__first, __last, __val,
                       __DISTANCE_TYPE(__first));
}