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-18 10:25:46

On Mar 18, 2010, at 10:21 AM, joaquin_at_[hidden] wrote:

> Howard Hinnant escribió:
>> On Mar 18, 2010, at 3:35 AM, joaquin_at_[hidden] wrote:
>> 
>>  
>>> 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.
>>>    
>> 
>> This is a good summary of the situation with the following added information: [...]
> 
> I sincerely hope that 579 is then reopened so that singly linked implementations of
> unordered associative containers are accepted back into the standard.

Issue 579 is still open:

http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579

How it will be closed is very much in debate.

> I participate
> in the Spanish C++ committee and will route my opinion through our representative
> in JTC1/SC22/WG21.

Thank you, please do.  Your participation through your national body representative is very important!

-Howard