Re: [boost] Hash tables and singly linked lists

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2001-01-11 16:21:29

Matthew Austern wrote on 1/11/2001 3:40 PM
<snip terrific post>

Thanks for the great outline of slist design options.

I am tending towards agreeing with you on slist.  The whole point of this 
thing is to save space; otherwise you would use list.  So I favor the 1 
word overhead design.  Unfortunately for me, this is not what I currently 
have coded in the Metrowerks lib (3 words overhead, O(1) size).  And I 
would like to just toss the O(N) insert/erase stuff too.

I looked at the "iterators point to previous nodes" design a couple years 
ago.  One thing that worried me was invalidating an outstanding iterator 
by erasing the element before it.  So I don't suggest that route either.

>For example, I'm using a vector<slist> for my hashtables.

I got scared off of this by the possibility that client code might 
instantiate a non-zero-sized allocator (which then adds a multiple of 
bucket_size overhead).

-Howard