On Mon, Feb 18, 2013 at 4:06 PM, Robert Ramey <ramey@rrsd.com> 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-...
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....