2

为什么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)，只有一行。

4

1 回答 1

2

This way of implementing lower_bound allows you to do this trivial check, whereas otherwise you would always be forced to do this check. In the sense of "you don't pay for what you don't use" this makes sense to me.

Because lower_bound works on sorted structures only, you can always compare with the first element if you deem it worth it.

Still, the actual implementation looks different, so some STL-implementations may actually do this check.

The implementation from SGI e.g. looks like this (check not done!):

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));
}
于 2015-04-02T16:14:49.007 回答