Re: [boost] Hash tables and singly linked lists

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?

                        --Matt