From: Matt Austern (austern_at_[hidden])
Date: 2001-01-13 13:32:48
"John E. Potter" wrote:
> > There's a less obvious disadvantage of having iterators that
> > point to the previous node: dealing with L.end() becomes
> > harder. The problem is that end() must find a pointer to
> > the last node in the list. (As opposed to just wrapping a
> > null pointer.) Clearly you don't want and O(N) end() that
> > steps through the list, so you're left with just one option:
> > having the list maintain a pointer to the first node, and also
> > a pointer to the last node. That's what I meant by a tradeoff
> > between features and space: in exchange for insert-after
> > semantics, you're paying one word of overhead.
> Another alternative. Since the iterator contains a prior pointer,
> iterators may be invalidated in ways other than erase of the
> current node. That makes containers of iterators unlikely and the
> total number of iterators likely becomes small. The space can be
> shifted to the iterator with a prior and current pointer. The
> list contains a single pointer. Insert, erase, begin, end are O(1).
> Dereference is one step. Increment is two updates, but one is
> local to the iterator. The increased size of the iterator may
> make everything slower or may not be measurable.
I don't see how that lets you get away without having an end
pointer in the list itself. If an iterator has a prior pointer,
then doesn't the end iterator still have to have a pointer to
the last list node?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk