Return SizedIteratorRanges from ranges::range for RandomAccessIteratorRanges and SizedIterables

The interface of `ranges::range` consists of:

- `ranges::range(Iterator, Sentinel, Size) -> sized_iterator_range`
- `ranges::range(Iterator, Sentinel) -> iterator_range`

However, when calling `ranges::range(Iterator, Sentinel)` with `RandomAccessIterator`s, we can 
compute the range size in `O(1)` and return a `sized_iterator_range`.

Furthermore, some containers like `std::list` provide only `BidirectionalIterator`s, but they have
an `O(1)` `size()` member function.

This patch changes `ranges::range` interface to: 

- `ranges::range(Iterator, Sentinel, Size) -> sized_iterator_range`
- `ranges::range(Iterator, Sentinel) -> sized_iterator_range` (if possible) / `iterator_range`
- `ranges::range(Iterable&) -> sized_iterator_range` (if possible) / `iterator_range`

The `ranges::range(Iterable&)` dispatches to a `sized_iterator_range` if the `Iterable` has `RandomAccessIterator`s or `ranges::size(Iterable&)` can compute its size (which is `O(1)`). Otherwise it returns an `iterator_range`.

Note:  the `algorithm/equal.cpp` test used to perform one comparison in the modified `CHECK` clause when comparing two `RandomAccessRange`s even tho they had different sizes. Now it doesn't need to perform any comparison at all. 
On Sat, Sep 13, 2014 at 7:02 PM, Eric Niebler <notifications@github.com>
wrote:

> In include/range/v3/iterator_range.hpp:
>
> >                  return {std::move(begin), std::move(end)};
> >              }
> >
> > -            template<typename I, typename S, typename Size>
> > +            template<typename I, typename S,
> > +                     CONCEPT_REQUIRES_(IteratorRange<I, S>{} && RandomAccessIterator<I>{})>
> > +            static sized_iterator_range<I, S> invoke(range_fn, I begin, S end)
> > +            {
> > +                const auto s = static_cast<iterator_size_t<I>>(distance(begin, end));
>
> I know you feel that std:: pair of iterators should model Range, but I'm
> undecided about that. If we make pair model Range, size will just work
> for it.
>

I was referring to a function with the signature:

template <typename I> // I models Iterator
auto size(I f, I l) -> iterator_size_t<I>


> What is the list:: size issue you refer to?
>
Many people just assumed that list::size() would execute in constant time.
So implementors started implementing it so it would (in the SGI STL it was
linear). This caused a huge number of issues for people porting code from
an implementation with constant time size() to one with linear time -
suddenly some algorithms would go quadratic.

The constant time size() conflicted with the guarantee on one form of
splice() and so in C++11 the requirements were changed that list::size()
must be constant time and, the requirements on splice were weakened to
allow linear time. [I actually thought the correct answer was that size()
should be constant time - unless it was proceeded by splice, then it could
be linear [basically a splice can trigger a re-calc on size]. That way, you
can perform multiple splice operations without incurring a large penalty.

If we have a size() operation on ranges, people will assume it is constant
time. This will be reinforced by the fact that is usually will be a
constant time operation. It is just a bad name. A property that requires an
O(N) calculation should have a name that implies that (i.e. find_size() ) -
using a verb in the name is a good way to imply that work is being done.

The reason distance() was used instead of subtraction is because people
would assume that subtraction was constant time - but distance() was not a
great choice either.

Sean



> —
> Reply to this email directly or view it on GitHub
> <https://github.com/ericniebler/range-v3/pull/47/files#r17516073>.
>