Boost logo

Boost :

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2010-03-17 18:06:36


On Mar 17, 2010, at 5:29 PM, Joaquin M Lopez Munoz wrote:

> Howard Hinnant <howard.hinnant <at> gmail.com> writes:
>
>>
>> On Mar 16, 2010, at 2:27 PM, Brad Higgins wrote:
>>
>>>
>>> On Mar 15, 2010, at 4:11 PM, Howard Hinnant wrote:
>>>> I'm reviving an old thread with new information:
>>>>
>>>> The LWG looked at this issue last week:
>>>>
>>>> http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579
>> [...]
>> Thanks for sharing your real-world experience Brad. I've passed
>> your note on to the C++ committee. To answer your question, one
>> vendor has already shipped these containers and with a design that
>> reportedly does not suffer from this quadratic behavior, and is
>> very reluctant to have this signature change.
>
> Howard, I'm intrigued by the "reportedly" bit in the
> sentence above. Has any member of the committee had access
> to that code and assessed whether the quadratic behavior
> is *effectively* avoided?

I do not have access to the code. I have no reason to doubt the report. I have not seen actual timings from tests run.

Just a few minutes ago I changed my implementation of unordered_map to use a "lazy increment" for the iterator and ran it against Brad's test:

$ time a.out
Add 500000 elements...done!

remove the elements...done!

real 0m0.153s
user 0m0.127s
sys 0m0.020s

This time is about the same as I got using an erase() that did not increment the iterator. The "lazy increment" allows the iterator to walk off of the end of bucket, and does not try to find the next bucket until dereference, another increment, or comparison. I do not claim this is "the solution" it is one of several I'm exploring. I mention it here in case others want to try it and report their experience.

-Howard


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk