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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2010-03-18 08:17:06

joaquin_at_[hidden] skrev:
> Howard Hinnant escribió:

>> 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.

FYI,

He uses doubly linked lists.

-Thorsten