Query regarding insert function in boost::unordered_set
Hi,
I need to use boost::unordered_set for inserting about 100000 elements
with a constant time efficiency for the insert function.
I checked the time taken for inserting 25,000 elements each time, and
found that it is as follows:
Time for inserting 1-25000 elements: 250
Time for inserting 25001-50000 elements: 250
Time for inserting 50001-75000 elements: 171
Time for inserting 75001-100000 elements: 297
I am using the std::pair
On 22/08/2008, Carvalho, Malcolm
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
participants (2)
-
Carvalho, Malcolm -
Daniel James