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. 
Which I think brings us back to the original issue - do we want a
find_size() operation to eliminate this cast? It is generally useful (I see
a lot of distance() followed by cast calls).

Sean

On Sun, Sep 14, 2014 at 3:09 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 was referring to a function with the signature:
> template <typename I> // I models Iterator
> auto size(I f, I l) -> iterator_size_t
>
> Yes, it has that signature also. It also allows type type of the sentinel
> to differ. When used in that form, it requires that the iterator and
> sentinel together satisfy the SizedIteratorRange concept -- which basically
> means they can be subtracted to find the distance in O(1). In addition to
> random access iterators, counted iterators model that concept, even when
> they're not random access. If you try to pass a pair that don't satisfy
> SizedIteratorRange, the call will fail to compile. That is how it differs
> from distance.
>
> I spent quite a bit of time thinking about the std::list problem. In
> addition to the binary SizedIteratorRange concept, there is the unary
> SizedIterable concept. This concept requires size(rng) as a valid
> expression, and it requires that it's return type is integral.
>
> A global size function is defined such that size(rng) returns rng.size()
> if that's well-formed. (size(rng) will also try to dispatch to size(begin(rng),
> end(rng)), which works if begin and end model SizedIteratorRange as
> described above.)
>
> In recognition of the fact that some Iterables might have size members
> that aren't O(1), (e.g. C++98 std::list) the SizedIterable concept also
> checks a trait, is_sized_iterable. That gives a way for a user to
> override the default and opt-out of modeling the concept.
>
> Note that since SizedIterable is defined in terms of size and not the
> other way around, size(rng) might compile for a type that doesn't model
> SizedIterable. It might be possible to add a static_assert in the body of
> size to catch this case, but that seems like nannying to me. std::begin
> doesn't do anything clever like that, and that's probably fine.
>
> I think this gives some useful defaults for a useful function, and a way
> to control how range types model the concept. Feedback welcome.
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/ericniebler/range-v3/pull/47/files#r17522993>.
>