Алгоритмы C ++ 11 std::is_sorted
а также std::is_sorted_until
оба требуют ForwardIterator
s. Тем не менее, версия Boost.Range boost::is_sorted
требуется только SinglePassRange
с, что соответствует InputIterator
s. В частности, он делегирует реализацию на основе итератора, например:
template<class Iterator, class Comp>
inline Iterator is_sorted_until (Iterator first, Iterator last, Comp c) {
if (first == last)
return last;
Iterator it = first; ++it;
for (; it != last; first = it, ++it)
if (c(*it, *first))
return it;
return it;
}
Здесь мы видим *first
разыменование итератора, которое происходит после ++it
приращение итератора. Это означает, что Iterator
должен иметь ForwardIterator
как его обязательная категория. Зачем? Потому что стандарт так говорит в
24.2.3. Итераторы ввода [input.iterators] / p2 (см. таблицу 107 со строкой о ++r
)
сообщение: любые копии предыдущего значения
r
больше не требуются
или быть разыменованным или находиться в области==
,
Заметкаэто не является «доказательством на одном примере», но кажется, что любой алгоритм основан на сравнении (например, adjacent_find
) обязательно потребуются прямые итераторы, чтобы можно было сравнить два итератора.
Вопрос: почему не версия Boost.Range is_sorted
требуют более сильной концепции ForwardRange
(а также ForwardIterator
для его низкоуровневых процедур), что требуется std::is_sorted
? Это ошибка в Boost.Range?
Похоже, что версии итератора в boost.algorithm правильно требуют ForwardIterators
, И верить этому или нет, В boost.algorithm есть также версии на основе диапазона. Дублирование кода в лучшем виде. Документация отстает от источника в соответствии с Билет № 9367, Набор изменений # 86741 исправляет оставшуюся часть документации, утверждая, что все разновидности алгоритмов проверки сортировки требуют ForwardIterators
,
Я бы предпочел реализации в <boost/algorithm/cxx11/is_sorted.hpp>
над теми, кто в <boost/range/algorithm_ext/is_sorted.hpp>
которые кажутся немного гниющими с 2010 года.
РЕДАКТИРОВАТЬ: копаться, кажется, что реализации Boost.Range сделал требовать ForwardIterator
, но этот коммит сломал их в 2010 году?!?.
Других решений пока нет …