2

std::lower_bound( )の最初のステップとして簡単な比較がないのはなぜですか?

最初のステップでstd::lower_boundイテレータがリスト内から中央の位置に変更itさfirstれると、次のようになります。

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

その後、アルゴリズムはその center-itと givenの比較を開始しvalueます。

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

しかし、些細なケースは、再配置する前の最初のステップとして 1 つの比較を行うことitです。

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

std::lower_bound非常に長いリストがあり、現在の形で が実現するまで待つ必要があると想像してください。これvalue < *firstは本当です。確かにO( log_2( last - first ) )ですが、そのような場合はO(1)に 1 行だけ追加される可能性があります。

4

1 に答える 1

2

この実装方法により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));
}
于 2015-04-02T16:14:49.007 に答える