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
