Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk