Re: [boost] [range] [general] making member functionsSFINAE-friendly

Subject: Re: [boost] [range] [general] making member functionsSFINAE-friendly
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2013-02-18 19:49:53

On Mon, Feb 18, 2013 at 4:06 PM, Robert Ramey <ramey_at_[hidden]> wrote:

> Dave Abrahams wrote:
> > on Mon Feb 18 2013, Jonathan Wakely <jwakely.boost-AT-kayari.org>

> wrote:
>
[...]

> >> Given that I'm already requiring the type can be used with
> >> std::begin() and std::end(), i.e. is range-like, I'm happy to not
> >> support types that have a non-range-like size().  If your type quacks
> >> like a duck but swims like a fish it doesn't meet my requirements for
> >> a duck.
> >
> > This sounds like the language commonly used in the Python community
> > about (their version of) concepts.
> > <
> http://grokbase.com/t/python/python-list/02c225syvb/source-code-size-metric-python-and-modern-c#20021207htb5htssa6yj355yhcjbz4wm7y
> >
> >
> > There's no "range-like."  There's a family of Range concepts:
> >
> http://www.boost.org/doc/libs/1_53_0/libs/range/doc/html/range/concepts.html
> > http://www.boost.org/community/generic_programming.html#concept
> >
> > Maybe I'm off base here, but reading the above makes it hard for me to
> > hear the rest of what you wrote.
>
> FWIW - we had a thread a couple of months ago regarding Boost Range
> concepts, how they were defined and how they were implemented and
> what they should mean for users of Boost Range.  I was dissatisfied with
> all three of these aspects of Boost Range but couldn't convince anyone
> else of my point of view.
>

Which three aspects are you referring to?

> Looking that the documentation/synopsis of iterator_range<T> I see a few
> things
> of interest:
>
> a) Documentation says that it fullfills the ForwardIteratorRange concept -
> OK
>

You mean the Forward Range concept. And there is a caveat that a subset of
the interface is still available for Single Pass Iterators as well.

> b) But then it includes the size() function - so doesn't that mean that it
> full fills
> the concept for RandomAccessRange concept?  very confusing.
>

2 things:
- Forward Iterator Range + size() does not give you a Random Access Range;
you need a lot more; see [1].
- size() is listed under "for Random Access Range only". Maybe there should
be an additional note that an iterator_range of a Random Access Iterator is
a Random Access Range, but other than that, I'm not sure what's confusing,
and I suspect it isn't the aforementioned that you're finding confusing.

c) shouldn't there be:
>
> template<ForwardIteratorRange>
> class forward_iterator_range {
>     ...
> };
>
> ...
>
> template<RandomIteratorRange>
> class random_access_iterator_range : public {
>     size_type size() const;
> };
>
> Boost Range concept doesn't specify size() for a ForwardIteratorRange.  But
> I think this is another mistake since size() could be implemented (in a
> different way)
> for iterators fullfilling this concept.
>

In a different O(n) way, sure, but the standard has made a conscious
decision to keep any size functions O(1). If you want a potentially O(n)
"size", just do distance.

You can augment your classification of ranges to include
RangesWithConstantTimeSize, which would include all Random Access Ranges as
well as some non-Random Access Ranges. But there is no such
precisely-defined, widely agreed-upon concept and corresponding interface
(AFAIK).

Wouldn't restructuring interator_range along the lines of the above resolve
> all the confusion here?
>

As pointed out before, that requires you to dig out the traversal category
of your iterator in order to choose the right iterator_range variant.
Eventually we'd just end up with a trait that wraps a given iterator with
the iterator_range variant with the strongest traversal category, which
usage-wise isn't really much different from the present situation.

- Jeff

[1]
http://www.boost.org/libs/range/doc/html/range/concepts/random_access_range.html