iterator_range::size() is not SFINAE-friendly

[Jonathan Wakely <jwakely.boost@…>]

iterator_range<I>::size() is always defined, but fails a static assertion if I is not a random access iterator. This means it's not possible to use SFINAE To detect whether r.size() is valid.

By moving the size() member to a new base type like the one below (and updating iterator_range to use this->m_Begin and this->m_End everywhere) the function will only be present when it can actually be used:

        template<class IteratorT, class CategoryT
                 = typename std::iterator_traits<IteratorT>::iterator_category>
        class iterator_range_base
        {
        protected:
            template< class Iterator >
            iterator_range_base( Iterator Begin, Iterator End ) :
                m_Begin(Begin), m_End(End)
            {}

            // begin and end iterators
            IteratorT m_Begin;
            IteratorT m_End;
        };

        template<class IteratorT>
        class iterator_range_base<IteratorT, std::random_access_iterator_tag>
        {
        protected:
            template< class Iterator >
            iterator_range_base( Iterator Begin, Iterator End ) :
                m_Begin(Begin), m_End(End)
            {}

            typedef BOOST_DEDUCED_TYPENAME
                iterator_difference<IteratorT>::type difference_type;

            // begin and end iterators
            IteratorT m_Begin;
            IteratorT m_End;

        public:
            difference_type
            size() const { return m_End - m_Begin; }
        };

Also, the comment at the top of iterator_range_core.hpp says:

Defines the \c iterator_class and related functions.

which should presumably say "iterator_range class" not "iterator_class"

[Nathan Ridge]

Replying to Jonathan Wakely <jwakely.boost@…>:

iterator_range<I>::size() is always defined, but fails a static assertion if I is not a random access iterator. This means it's not possible to use SFINAE To detect whether r.size() is valid.

What is a use case for using SFINAE to detect whether r.size() is valid? (I'm not questioning that there is one, I'm just curious.)

[Jonathan Wakely <jwakely.boost@…>]

I have a zip function to iterate over a variable number of ranges:

for (auto& e : zip(container, array, other_ranges, ...))
  /* ... */;

In order to ensure iteration stops at the end of the shortest range I need to know the length of each range. I used to assume each range had a r.size() member, but that broke for iterator_range with non-random access iterators, so now I use std::distance(std::begin(r), std::end(r)), which is O(n). I would prefer to use r.size() if it's usable, but I can't use SFINAE to tell if size() is usable, because iterator_range<I>::size() is always defined, but not always usable.

I could define a traits class to detect if the range is iterator_range and only use size() if it doesn't contain RA iterators, but I'd prefer to avoid that and just use SFINAE.

[Nathan Ridge]

Replying to Jonathan Wakely <jwakely.boost@…>:

I have a zip function to iterate over a variable number of ranges:

for (auto& e : zip(container, array, other_ranges, ...))
  /* ... */;

In order to ensure iteration stops at the end of the shortest range I need to know the length of each range. I used to assume each range had a r.size() member, but that broke for iterator_range with non-random access iterators, so now I use std::distance(std::begin(r), std::end(r)), which is O(n). I would prefer to use r.size() if it's usable, but I can't use SFINAE to tell if size() is usable, because iterator_range<I>::size() is always defined, but not always usable.

I could define a traits class to detect if the range is iterator_range and only use size() if it doesn't contain RA iterators, but I'd prefer to avoid that and just use SFINAE.

Why not write zip() in such a way that it stops looping when the iterator of any one of the ranges reaches end()?

[jwakely.boost@…]

I use boost::zip_iteratorso to construct an end iterator that is reachable from {r1.begin(), r2.begin(), ...} it needs to be {r1.begin()+N, r2.begin()+N, ...} (where N is the size of the smallest range) not {r1.end(), r2.end(), ...} because operator== for zip_iterator is only true if all members of the tuple are equal.

​https://gitorious.org/redistd/redistd/blobs/master/include/redi/zip.h Since I switched from using the size() member it needs fixing to avoid calling both std::distance() and std::advance(), but the point of this ticket is that I'd prefer to use size() when possible

[Nathan Ridge]

Replying to jwakely.boost@…:

I use boost::zip_iteratorso to construct an end iterator that is reachable from {r1.begin(), r2.begin(), ...} it needs to be {r1.begin()+N, r2.begin()+N, ...} (where N is the size of the smallest range) not {r1.end(), r2.end(), ...} because operator== for zip_iterator is only true if all members of the tuple are equal.

​https://gitorious.org/redistd/redistd/blobs/master/include/redi/zip.h Since I switched from using the size() member it needs fixing to avoid calling both std::distance() and std::advance(), but the point of this ticket is that I'd prefer to use size() when possible

Let me suggest an alternative way of implementing such a zipped range:

• Use a custom iterator class rather than boost::zip_iterator
  • Use a special marker value to represent 'end'
  • In the begin iterator, store the end of each component range as well as the current position in each
• When incrementing the begin iterator, increment each component iterator. When any one of them compare equal to the corresponding end iterator, set the iterator's value to the special marker value that represents 'end'

This way:

• You don't do an extra traversal of forward and bidirectional component ranges to figure out their size
• You range is usable with single-pass component ranges

The only disadvantage I can see is the extra memory to store the component end iterators in the zipped range's iterator.

[Nathan Ridge]

Regarding the original request for making iterator_range::size() SFINAE-friendly: I am a little hesitant about it because of the effect on the code's readability. I am curious:

• Do you recommend this as a general technique to apply to member functions of templates where the member function only makes sense for a subset of the template parameters? If not, what makes iterator_range::size() special?
• Do you see this technique used commonly elsewhere (for example, libstdc++)?

(where by "this technique" I mean "factoring out the member function into a base class that's specialized for the relevant subset of template parameters").

[jwakely.boost@…]

Thank you for actually addressing the subject, feel free to write your own custom iterator that way if you want to! :-)

I see my request as analogous to the standard's requirement that a function shall not participate in overload resolution if it doesn't meet the required concepts. The size() member isn't a function template so can't use disable_if directly, hence my suggestion to move it to a base class that can be partially specialized, but I don't care how it's done, I just think it should be done.

[jwakely.boost@…]

Another analogy would be std::forward_list, it has no size() member. It doesn't have a size member that fails a static assertion.

[Nathan Ridge]

Replying to jwakely.boost@…:

I see my request as analogous to the standard's requirement that a function shall not participate in overload resolution if it doesn't meet the required concepts. The size() member isn't a function template so can't use disable_if directly, hence my suggestion to move it to a base class that can be partially specialized, but I don't care how it's done, I just think it should be done.

I started a thread on the boost mailing list about this topic: ​http://thread.gmane.org/gmane.comp.lib.boost.devel/238845

Feel free to weigh in. I will implement the workaround if it has concensus.

[Nathan Ridge]

Replying to Jonathan Wakely <jwakely.boost@…>:

I used to assume each range had a r.size() member, but that broke for iterator_range with non-random access iterators, so now I use std::distance(std::begin(r), std::end(r)), which is O(n). I would prefer to use r.size() if it's usable

Actually, according to section 24.4.4/4 [iterator.operations] of the standard, std::distance is O(1) for random-access iterators. So you can just always use std::distance.

In light of this, do you still think there is a use case for what you are requesting?

[jwakely.boost@…]

Feel free to weigh in.

I'd rather not, the boost lists are an enormous time sink. The only reply is typical: offering advice without bothering to read the ticket you linked to, which provides the use case. The reason iterator_range::size() doesn't use std::distance() is to guarantee it's O(1). The same reason std::forward_list doesn't provide size() (but it *doesn't provide* it, rather than providing it and failing a static assertion.)

So you can just always use std::distance.

Solving the problem for RA iterators was never the issue, obviously std::distance works for them, but that's sub-optimal for non-RA iterators. If a container such as std::map, which has bidirectional iterators, provides an O(1) size() member then I want to use it. But I can't tell whether a range provides size() or not, because iterator_range provides it but it isn't usable.

I'm currently tempted just to say my type doesn't support boost::iterator_range and be done with it.

[Nathan Ridge]

Replying to jwakely.boost@…:

So you can just always use std::distance.

Solving the problem for RA iterators was never the issue, obviously std::distance works for them, but that's sub-optimal for non-RA iterators. If a container such as std::map, which has bidirectional iterators, provides an O(1) size() member then I want to use it. But I can't tell whether a range provides size() or not, because iterator_range provides it but it isn't usable.

Ah, I see now. Thanks for clarifying!

Feel free to weigh in.

I'd rather not, the boost lists are an enormous time sink. The only reply is typical: offering advice without bothering to read the ticket you linked to, which provides the use case.

I'm sorry to hear you have such a poor opinion of the boost lists. I am happy to make your case for you, now that I understand it.

[Jonathan Wakely <jwakely.boost@…>]

I decided to bite the bullet and resubscribe to the list, although your summary of the issue is perfect so I hope I won't have much to add.

[Neil Groves]

I strongly agree with Jonathan Wakely on this matter. It is something I have wanted to improve for quite some time.

I want to go slightly further since there are other member functions that make sense for bidirectional traversal and then some more for random_access traversal. I'll clean this all up in one iteration.