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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2010-03-18 10:06:54

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:  It is not sufficient to just have the nodes connected by a doubly linked list.  This alone introduces linear behavior (in terms of adjacent empty buckets) in insert and erase.  The data structure also has two pointers per bucket to mark the beginning and end of each bucket.

-Howard