Re: [boost] Hash tables and singly linked lists

From: Matthew Austern (austern_at_[hidden])
Date: 2001-01-11 16:52:14

Gary Powell wrote:
> 
> Have you considered the old xor double'ly linked list? Has the single
> address space of a slist and the bi-directional capability of a list? The
> iterators are invalidated easier because if the node before or after changes
> the addressing won't work.

It's a cute trick, yes.  One problem with it, of course, is that 
it isn't portable.  You can't xor pointers, only integers, and
the C++ standard does not guarantee that there is any integer type
large enough to store a pointer.  (This may be a purely theoretical
issue, since I don't know of any common architecture that lacks such
a type.) 

As you say, there are a number of operations that will require patching
up links.  And another issue is that, unless I'm missing something, an
iterator for such a list will need to keep track of pointers to three 
different nodes, not just to one node.  Still, it might be worth seeing
how far this idea can be pushed.  It's not a substitute for singly
linked lists, but it may be a  good choice if you care about space, and 
you need traversal in both directions, and you don't mind slow iteration.

                                --Matt