Re: [boost] Hash tables and singly linked lists

From: John E. Potter (jpotter_at_[hidden])
Date: 2001-01-13 06:00:49

On Thu, 11 Jan 2001, Matthew Austern wrote:

> There's another defensible option, though.  Internally we
> still have something like insert-after semantics, but
> externally it looks like ordinary insert-before.  The way
> this works is that, internally, an slist iterator that 
> refers to an element will point to the *previous* list node.
> You'll be changing iterator dereference from something like
> *(p->val) to something like *(p->next->val).
> 
> The advantage of this is obvious: users get reasonable
> insertion performance, without having to switch from 
> insert() to insert_after().  One disadvantage is equally
> obvious: iterator dereference becomes slower.  (Two pointer
> dereferences instead of one.)
> 
> 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.

John