Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Thorsten Ottosen (nesotto_at_[hidden])
Date: 2010-03-18 08:17:06
> 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.
He uses doubly linked lists.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk