Re: [boost] [unordered] unordered_set::erase() complexity bug?

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