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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: joaquin_at_[hidden]
Date: 2010-03-18 03:35:45

Howard Hinnant escribió:
> 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.
>   

I'm not getting this. N2023 (allegedly) *proves* that singly linked 
unordered containers
*can't* implement iterator erase(iterator) with O(1) complexity. So 
N2023 can be
right or wrong (if there's some flaw in the proof), but if a committee 
member votes for NAD
I think it's only fair to demand some evidence from him as to why N2023 
is wrong. Do
you agree so far with me?

Now, it's not that whatever technique they reportedly have applied is a 
trivial one,
since at least three industry-level implementations of unordered 
containers have the
problem predicted by N2023. Or, maybe that member is using *doubly 
linked* unordered
containers: In that case N2023 does not apply and iterator 
erase(iterator) can indeed
be implemented in O(1), but then if 579 is as a consequence closed as 
NAD this is
tantamount to stating that singly linked hash tables are not valid 
implementations of
C++ unordered containers.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo