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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk