Re: [boost] portable hash_map

From: Beman Dawes (bdawes_at_[hidden])
Date: 2001-03-05 15:04:00

At 11:27 AM 3/5/2001 -0800, Matt Austern wrote:

 > - I might have an new idea that will permit fast iteration
 >   without giving up any of the other desirable properties:
 >   have a single slist for all the elements, and then have
 >   a separate vector of slist iterator pairs for the buckets.
 >   My new insight is that elements in that single slist do
 >   not have to appear in bucket order.  I don't know why that
 >   didn't occur to me before today.

Please remember that hash lists used for speed efficiency (at low loading 
factors), space efficiency (at high loading factors), and speed-space 
efficiency blends (at moderate loading factors).

So doing something that adds even one additional pointer per bucket (to 
speed iteration) impacts some uses.

Have you considered a hash_map_generator<> instead?  That way you could 
offer no-list, single-list, and double-list (like Bill Plauger's) 
forms.  Lots of work, but also gives users lot's of choices.

I guess if I had to pick one, the single list form would be it, but the 
others offer interesting trades offs.  PJP's double-list implementation is 
a closer replacement for std::map for example.

Cheers,

--Beman