Why doesn't Boost.Range is_sorted require forward iterators?

Question

The C++11 algorithms std::is_sorted and std::is_sorted_until both require ForwardIterators. However, the Boost.Range version boost::is_sorted only requires SinglePassRanges which corresponds to InputIterators. 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?

Bluh

Indeed this seems suspicious. – Rabid

@MatthieuM. I wonder though if one could make it work for input iterators by caching the last value that has been read? – Bluh

It would then impose a requirement on said value: it would have to be copyable. – Rabid

Hmmm doesn't a SinglePassRange correspond to a SinglePassIterator rather than an InputIterator? See boost.org/doc/libs/1_55_0/libs/iterator/doc/… – Daffi

@Daffi Earlier in that document, InputIterator is said to be a readable SinglePassIterator. And just below your quoted passage, there is the table for ForwardIterator which has "r == s and r is dereferenceable implies ++r == ++s." Without this, the previous value is no longer dereferenceable or comparable if copies of the iterator are incremented. – Bluh

Answer 1

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?!?.

Custos

+1 and accepted. thanks for digging up all that dirt on Boost. It's a mess to say it nicely. – Bluh