Re: [boost] [unordered] Buffered functions?

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 
still low).

Not to mention that with these group pointers equal_range is O(1).

Regards,

Ion