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));
}