Re: [boost] [unordered] Buffered functions?

Subject: Re: [boost] [unordered] Buffered functions?
From: Daniel James (daniel_james_at_[hidden])
Date: 2008-11-26 14:48:29

2008/11/26 David Abrahams <dave_at_[hidden]>:
>
> 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