Re: [boost] Hash tables and singly linked lists

From: Matthew Austern (austern_at_[hidden])
Date: 2001-01-16 13:43:45

"John E. Potter" wrote:
> 
> Circular list with no dummy node.  Tail points to last node.  For
> an empty list end == begin == (0, 0).  For a non empty list, end
> == (tail, tail->next) and begin == (0, tail->next).  Iterators
> naturally increment to end.  There are only n values for current,
> but there are n + 1 values for pred.  Iterator== is on pred only.

A good point.  That sounds like a useful data structure; it has
all of the advantages of an slist with a pointer to the last element,
and fewer of the disadvantages.  (It still has the disadvantage of
increased iterator fragility.)

Performance characteristics will be very different from those of the
slist<> that I currently have.  It may be useful to provide both 
data structures.  At the least, I should do some real measurements.

                        --Matt