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