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 允许您进行这种琐碎的检查，否则您将总是被迫进行这种检查。在 "you don't pay for what you don't use" 的意义上，这对我来说很有意义。

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

std::lower_bound 中没有小案例？

No trivial case in std::lower_bound?

c++

algorithm

std

time-complexity

lower-bound