RE: [boost] Hash tables and singly linked lists

From: Gary Powell (Gary.Powell_at_[hidden])
Date: 2001-01-12 11:49:43

>xor double'ly linked list?

>> an
> iterator for such a list will need to keep track of pointers to three 
> different nodes, not just to one node.  
<<

A forward iterator only needs 2 pointers, and a reverse iterator, again 2. A
bidirectional iterator would need 3.  It kind of messes up the STL interface
to provide all three. (at least as I understand it.)

begin<forward_iterator>() 
begin<bidirectional_iterator>() ?

vs the more normal begin().

I'd be willing to code one up if people would like to see a demonstration of
it.

I used it on a project (written in C) that had 100K nodes and needed to be
able to be sorted. So I used a bidirectional iterator, but it was a space
for the whole list problem, at the time I wrote it, the execution cost for
traversal wasn't a limiting factor in the algorithms we were using.

Also because it was written in C, I used a inherit from the node technique
to contain the list, eliminating the pointer to the data as well.  BTW there
have been proposals for a set of containers which use this technique, and
articles in C++ Report (long may it rest in peace). I can look those up if
anyone is interested as well. I believe the author was trying to sell his
containers but the idea could be borrowed.

Yes I understand about the addressing vs integer issues.

  -gary-

gary.powell_at_[hidden]