Re: [Boost-users] Query regarding insert function in boost::unordered_set

From: Daniel James (daniel_james_at_[hidden])
Date: 2008-08-22 14:05:01

On 22/08/2008, Carvalho, Malcolm <Malcolm.Carvalho_at_[hidden]> wrote:
>
> Is there any way to  make this insertion time constant irrespective of the number of elements already  present in the set?

Insertion time is amortized constant - which means that the average
speed is constant. Occasionally a rehash occurs which make an
individual insertion much slower. The third block of insertions
probably doesn't contain a rehash, which is why it's faster. While the
fourth does, and because the number of elements is now quite large,
it's a larget hit.

You can avoid this by rehashing in advance, so if you first call
'set.rehash(100001)', you should get roughly constant speed (as long
as you don't have to many collisions). For a brief guide to an
appropriate value for rehash see http://preview.tinyurl.com/5zbfef.

Hope that helps,

Daniel