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 10:21:02

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. I 
participate
in the Spanish C++ committee and will route my opinion through our 
representative
in JTC1/SC22/WG21.

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