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