Boost logo

Boost :

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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at