2008/11/26 David Abrahams <dave@boostpro.com>:
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.
That's what it avoids. Because equal values are grouped together, you only need to examine a single key for all the equal values. Here's a quick diagram of a bucket in an unordered_multiset (assuming that the hash function is terrible and 5,3 and 2 all end up in the same bucket): http://www.calamity.org.uk/x/bucket.png The black links represent the normal single linked list. The red links are a circular list running backwards through equal values. This results in a red link from the first node in a group of equals values to the last node - this lets you quickly skip over equal values. This structure is easy to maintain and has some nice results, such as a stable order when inserting. The only tricky part was erasing by iterator. Daniel