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

Subject: Re: [boost] [unordered] unordered_set::erase() complexity bug?
From: JOAQUIN M. LOPEZ MUÑOZ (joaquin_at_[hidden])
Date: 2009-11-25 12:32:46

Beman Dawes <bdawes <at> acm.org> writes:
> 
> On Mon, Nov 23, 2009 at 6:40 PM, Thorsten Ottosen <
> thorsten.ottosen <at> dezide.com> wrote:
> >
> > 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."
> > [...]
> > 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?

Boost.MultiIndex's hashed indices suffer from the same problem
(it's in this context that I noticed the issue leading to the
aforementioned paper). I don't really see a way out (the paper
purportedly *proves* there's no way out) save for the proposed
workarounds. As you say at another post, it'd be nice is the thing
is reconsidered by the LWG.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo