Нет стандартного случая в std :: lower_bound?
Почему нет тривиального сравнения в качестве первого шага в 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 (последний — первый)), но в таком случае это может быть O (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));
}
Другие решения