Why doesn't Boost.Range is_sorted require forward iterators?
algorithm, boost-range, c++, c++11, iterator
Solution
It looks like the iterator versions in boost.algorithm correctly require `ForwardIterators`. And believe it or not, there are also range-based versions in boost.algorithm. Code duplication at its best. The documentation is lagging behind the source according to Ticket #9367, Changeset #86741 corrects the rest of the documentation to state that all flavors of the sort-checking algorithms require `ForwardIterators`.
I would prefer the implementations in `<boost/algorithm/cxx11/is_sorted.hpp>` over those in `<boost/range/algorithm_ext/is_sorted.hpp>` which seem to be bit-rotting since 2010.
EDIT: Digging around, it appears that the Boost.Range implementations did require `ForwardIterator`, but this commit broke them in 2010?!?.
Problem
The C++11 algorithms `std::is_sorted` and `std::is_sorted_until` both require `ForwardIterator`s. However, the Boost.Range version `boost::is_sorted` only requires `SinglePassRange`s which corresponds to `InputIterator`s. In particular, it delegates to an an iterator-based implementation like this: ``` 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; } ``` Here we see a `*first` iterator dereference that happens after the `++it` iterator increment. This means that `Iterator` should have `ForwardIterator` as its required category. Why? Because the Standard says so in 24.2.3 Input iterators [input.iterators]/p2 (see table 107 with the line about `++r`) post: any copies of the previous value of `r` are no longer required either to be dereferenceable or to be in the domain of `==`. Note: this is not intended to be "a proof by single example", but it seems that any comparison based algorithm (e.g. `adjacent_find`) would necessarily require forward iterators in order to be able to make a comparison between two iterators. Question: why doesn't the Boost.Range version of `is_sorted` require the stronger concept of `ForwardRange` (and `ForwardIterator` for its low-level routines) that is required by `std::is_sorted`? Is it a bug in Boost.Range?