Почему Boost.Range is_sorted не требует повторных итераторов?

Для алгоритмов С++ 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)

post: любые копии предыдущего значения r больше не требуются либо быть разыменованным, либо находиться в домене ==.

Примечание: это не предназначено для "доказательства одним примером", но кажется, что любой алгоритм, основанный на сравнении (например, adjacent_find), обязательно потребует итераторов вперед, чтобы иметь возможность для сравнения между двумя итераторами.

Вопрос: почему версия Boost.Range is_sorted не требует более сильной концепции ForwardRange (и ForwardIterator для ее низкоуровневых подпрограмм), которая требуется std::is_sorted? Это ошибка в Boost.Range?

Ответы

Ответ 1

Похоже, что версии итератора в boost.algorithm правильно требуют ForwardIterators. И верьте или нет, существуют также версии на основе диапазона в boost.algorithm. Дублирование кода в лучшем виде. Документация отстает от источника в соответствии с Ticket # 9367, Изменения набора # 86741 исправляет остальную часть документации, заявляя, что для всех вариантов алгоритмов проверки сортировки требуется ForwardIterators.

Я предпочел бы реализацию в <boost/algorithm/cxx11/is_sorted.hpp> по сравнению с версиями <boost/range/algorithm_ext/is_sorted.hpp>, которые с 2010 года кажутся гниющими.

РЕДАКТИРОВАТЬ: Похоже, что для реализаций Boost.Range требовалось ForwardIterator, но это зафиксировало их в 2010 году?!?.