Iterators Must Go

Rainer Deyke rainerd at
Sat May 9 19:10:22 PDT 2009

dsimcha wrote:
> == Quote from Rainer Deyke (rainerd at's article
>> Although I like ranges, it looks to me like there are a couple of
>> operations that would difficult to implement without iterators or some
>> other way to specify a specific position in a range.
>> Finding and erasing an element:
>>   list.erase(find(list.begin(), list.end(), e));
> What's wrong with this?  Since list owns its range representation, it can know the
> implementation details.  For a linked list, this will probably be just a pair of
> pointers under the hood anyhow.  In other words, it's internally still an
> iterator, just prettier looking.

The following is semantically incorrect:
  r = find(list, e)

'find' advances only the front of the range to the found element.
Therefore 'r' is the range of all elements starting with the found
element, but also including all elements after that.

I would expect 'list.erase(range)' to erase all elements in the range.
However, in this case I only want to erase a single element.  This could
still be expressed with ranges, but it would require a different
function.  For example:
  find(list, e).eraseFront()
  list.eraseFrontOf(find(list, e))
  list.eraseOne(find(list, e))
  list.erase(take(1, find(list, e)))

>> Splitting a container on a position:
>>   iter = find(list.begin(), list.end(), e);
>>   do_something_with(list.begin(), iter);
>>   do_something_else_with(iter, list.end());
> This one is legit, as far as I can tell.  On the other hand, although it's
> awkward, you could do something like:
> Range myRange1;
> auto myRange2 = find(myRange1, e);
> struct PairOfRanges {
>     Range myRange1, myRange2;
>     auto front() {
>         return myRange1.front;
>     }
>     bool empty() {
>         return myRange1 == myRange2;
>     }
>     void popFront() {
>         myRange1.popFront;
>     }
> }

Unfortunately this falls apart if my 'do_something_with' in the above
example is 'list.erase', unless 'list.erase' can look inside a

>> Inserting into a container at a position:
>>   iter = find(list.begin(), list.end(), e);
>>   list.insert(iter, array.begin(), array.end());
> Same as erasing.
>> Constructing a range from two independent position:
>>   iter1 = find(list.begin(), list.end(), e1);
>>   iter2 = rfind(list.begin(), list.end(), e2);
>>   do_something_with(iter1, iter2);
> Assuming find() works by popping elements off the front of the range until it
> finds what it's looking for, and then returning that, and rfind() does the same
> thing but from the back, just do something like:
> Range myRange = find(list, e1);
> myRange = rfind(myRange, e2);
> do_something_with(myRange);

That works in this case, but what if the iterators (sorry, ranges) come
from different sources?

Rainer Deyke - rainerd at

More information about the Digitalmars-d mailing list