Iterators Must Go

dsimcha dsimcha at yahoo.com
Sat May 9 21:49:08 PDT 2009


== Quote from Rainer Deyke (rainerd at eldwood.com)'s article
> dsimcha wrote:
> > == Quote from Rainer Deyke (rainerd at eldwood.com)'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)
>   list.erase(r)
> '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()
> Or:
>   list.eraseFrontOf(find(list, e))
> Or:
>   list.eraseOne(find(list, e))
> Or:
>   list.findAndErase(e)
> Or:
>   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
> 'PairOfRanges'.
> >> 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?

You do make some good points here, but as counter points:  Your examples rely on
the fact that there are two iterators, a begin iterator and an end iterator.  In
C++, this means that testing for the end of a range/iterator/whatever must be
reduced to some kind of comparison, thus exposing an implementation detail in the
design.  Thinking about some of the ranges I've written, I cannot picture how I
would reduce testing for empty to a comparison operation without resorting to some
pretty significant kludges.



More information about the Digitalmars-d mailing list