id,summary,reporter,owner,description,type,status,milestone,component,version,severity,resolution,keywords,cc
4264,boost multi_index hashed_unique erase takes linear time,anonymous,Joaquín M López Muñoz,"Hi,

We are using a multi_index with several hashed_unique indices. We make the number of bucket pretty large to avoid hash key clashes.

When we do an erase, the time it takes is linear to the number of buckets. What happens is that erase returns an iterator to the next item, which means that it has to search linearly through all the buckets until it find a bucket with an item in it. In our tests it takes several milliseconds for this to happen (we have 1000000 buckets). As the number of items in the multi_index decreases, the performance gets worse because it has to do a linear search further to find a non-empty bucket.

When the item from the first non-empty bucket is deleted, it also takes longer because the hashed index keeps a variable to know what the first non empty bucket is. when the first non-empty bucket becomes empty, it has to do another linear search to find the next non-empty bucket.

I would suggest to have erase return void, and not to keep track of the first non-empty bucket, so that erase will take the expected constant time. Iterating is expected to take linear time so if that is slow it is expected, but erase should be constant time.",Bugs,closed,,multi_index,Boost 1.41.0,Problem,fixed,,