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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: Beman Dawes (bdawes_at_[hidden])
Date: 2009-11-23 20:53:20

On Mon, Nov 23, 2009 at 6:40 PM, Thorsten Ottosen <
thorsten.ottosen_at_[hidden]> wrote:

 ...

> Our very own Joaquín anticipated this problem very early:
>
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf
>
> "In pathological cases, h(n) can be as bad as ½ n(n + 1): this happens when
> the elements
> are erased in reverse order as they are arranged in the hash table."
>
> It would be interesting to know
>
> 1) how intrusive containers avoid this, and
>
> 2) also if this is a real problem in real code.
>
> At any rate, Joaquin shows that the *lower bound* complexity of erase is
> actually lg n, and not O(1).
>
> Does anyone know how the WG21 LWG responded to his paper?
>
> The Portland wiki says:

N2023 erase(iterator) for unordered containers should not return an iterator

6 votes NO, 4 votes to ask for better justification, no votes in favor of
either proposed alternative. The consensus opinion was that since the
iterator could serve as its own proxy, there appears to be no need for the
change. In general, "converts to" is undesirable because it interferes with
template matching.

I'm guessing from the small number of votes that it was handled by a
subgroup. It isn't clear they fully understood the problem, although it is
often the case that wiki notes do not fully capture the discussion.

Like you, I'm wondering how intrusive containers avoid the problem. Also,
what do other implementations do, and how do they perform?

--Beman