Are iterators and ranges going to co-exist?

[Andrei Alexandrescu]

On 07/20/2010 03:01 AM, Peter Alexander wrote:
> Some more arguments for iterators/cursors:
>
> 1. How would you implement Floyd's cycle finding algorithm using ranges?
> (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
> It uses two iterators over the same range. You would have to wastefully
> use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the 
SList definition in std.algorithm. A SList range is exactly one pointer 
thick. With singly-linked lists it's the iterator approach that is 
wasteful because it canonically transports a null pointer as end().

> 2. I often store C++ iterators in container elements so that I can
> quickly remove them when I want to. How can I do this with ranges? I
> have to waste an extra word?

Yes. What was the largest container of 
iterators-in-another-container-that-I-want-to-remove-later?

> 3. To traverse a sequence in random order, I usually do something like
> this:
>
> // C is any container
> C c = ...;
>
> // Create an array of iterators
> vector<C::iterator> order;
> for (C::iterator i = c.begin(); i != c.end(); ++i)
> order.push_back(c);
>
> std::random_shuffle(order.begin(), order.end());
>
> for (vector<C::iterator>::iterator i = order.begin();
> i != order.end(); ++i)
> {
> C::iterator it = *i;
> // do stuff with *it
> }
>
> How can I do this with only ranges? Am I again going to have to double
> my memory usage?

This is a rehash of the indexing argument. If interested in saving 
memory, you may want to use pointers, which, agreed, can only point to 
one element so they aren't as powerful as iterators. (But then you'd 
seldom want to modify an iterator in such a structure.) I don't think 
such scenarios are compelling enough to warrant introducing iterators 
alongside ranges.

> 4. As an extension to the above, how would you implement rearrangement
> algorithms with ranges? For example, below is the cycle_to permutation
> algorithm from Stepanov's "Elements of Programming":
>
> template <typename I, typename F>
> void cycle_to(I i, F f)
> {
> I k = f(i);
> while (k != i)
> {
> exchange_values(i, k);
> k = f(k);
> }
> }
>
> f is a function that maps iterators to iterators (read: not ranges to
> ranges). Again, we see that using ranges here does nothing but increase
> our memory requirements, and unnecessarily complicates the code.

I've always thought that that chapter is rather weak. When did you use 
cycle_to last time?

> The recurring theme here is that there are algorithms and practices that
> call for iterators, and while you could use a range ignoring everything
> but the front or back to do the same job, it is simply an awkward way of
> sidestepping the real issue.

I agree (with qualifications) with the truthiness of the statement, but 
not with the alleged dimension of the problem. Also, like many one-sided 
arguments, this one presents introducing iterators as an all-win deal 
and neglects the associated costs.


Andrei