Boost C++ Libraries: Ticket #8011: iterator_range::size() is not SFINAE-friendly

Nathan Ridge — Mon, 11 Feb 2013 23:48:46 GMT

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.)

Tue, 12 Feb 2013 15:36:14 GMT

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 — Tue, 12 Feb 2013 18:32:45 GMT

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@… — Wed, 13 Feb 2013 00:19:53 GMT

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 — Wed, 13 Feb 2013 01:06:03 GMT

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 — Wed, 13 Feb 2013 01:09:04 GMT

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@… — Wed, 13 Feb 2013 08:26:09 GMT

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@… — Wed, 13 Feb 2013 10:01:12 GMT

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 — Mon, 18 Feb 2013 05:34:43 GMT

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 — Mon, 18 Feb 2013 06:47:37 GMT

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@… — Mon, 18 Feb 2013 09:32:19 GMT

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 — Mon, 18 Feb 2013 10:15:03 GMT

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.

Mon, 18 Feb 2013 11:11:31 GMT

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.

status changed; resolution set

Neil Groves — Mon, 24 Feb 2014 18:32:47 GMT

status new → closed
resolution → fixed

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.