11

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?

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
  • Indeed this seems suspicious. – Matthieu M. Feb 26 '14 at 10:32
  • @MatthieuM. I wonder though if one could make it work for input iterators by caching the last value that has been read? – TemplateRex Feb 26 '14 at 11:17
  • 1
    It would then impose a requirement on said value: it would have to be copyable. – Matthieu M. Feb 26 '14 at 13:14
  • Hmmm doesn't a SinglePassRange correspond to a SinglePassIterator rather than an InputIterator? See http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/new-iter-concepts.html#single-pass-iterators-lib-single-pass-iterators – dyp Feb 26 '14 at 15:05
  • @dyp [Earlier in that document](http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/new-iter-concepts.html#design), 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. – TemplateRex Feb 26 '14 at 15:26

1 Answers1

2

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

Casey
  • 41,449
  • 7
  • 95
  • 125