Re: [boost] [unordered] Buffered functions?

Subject: Re: [boost] [unordered] Buffered functions?
From: Daniel James (daniel_james_at_[hidden])
Date: 2008-11-27 16:10:59

2008/11/27 David Abrahams <dave_at_[hidden]>:
>
> Yes, I figured it was something like that.  It still doesn't make sense
> to me.  If the number of repeated values in a bucket is small, it won't
> hurt to traverse all of them.  If it is really large enough that
> traversing all equal values to get to the next value is expensive, it
> will destroy O(1) lookup in any buckets with collisions.

That's always an issue with hash tables. But you can improve matters
by using a better hash function or lowering the maximum load factor.
But if your container is slowing down because you have elements with
equal keys there's nothing you can do. Maybe you could use
unordered_map<key, vector<value> >?

>  Did anyone
> profile this in a real application and find it to be a win?

No, and nobody has found it to be a loss either. It isn't about
optimization, it's about meeting the complexity requirements.

> Stable order when inserting is nice, but ought to be achievable without
> the overhead of an extra pointer per node.

Stable order is not just nice, it's a requirement. But it was never
the main purpose of this design, I implemented it before the standard
changed, but it is a nice side product.

Daniel