Subject: Re: [boost] [unordered] Buffered functions?
From: Ion GaztaÃ±aga (igaztanaga_at_[hidden])
Date: 2008-11-26 15:15:28
David Abrahams wrote:
> on Wed Nov 26 2008, Ion GaztaÃ±aga <igaztanaga-AT-gmail.com> wrote:
>> For example, unordered_multisets have an additional pointer to group
>> equal values in a singly linked list so that bucket traversing is
>> linear to the number of different values instead of the number of
>> values in the bucket. It's a nice feature and useful in several
>> scenarios (I even added that option to Intrusive unordered
>> containers), but you have to pay for it ;-)
> Hmm, that doesn't make a lot of sense to me. Lots of equal values in a
> hash table can quickly destroy its O(1) lookup characteristics.
Ok, but unordered_multimap is supposed to deal with equal values just
like multimap, so I think you have use cases where you might introduce
many "equal" values (for example a lot of requests/packets... from the
same client, user, or whatever). If you chain groups together you might
save a lot of comparisons. In case you introduce a lot of values with
the same key you penalize all the keys that share the same bucket.
Again, this depends on the application, but having multiple equal keys
seems ok to me, and the container will surely not rehash if a lot of
equals keys are introduced and other buckets are empty (load would be
Not to mention that with these group pointers equal_range is O(1).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk