[Bug libstdc++/58153] unordered_multimap::erase(iterator) is not constant-time when many entries have the same key

["redi at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153

--- Comment #1 from Jonathan Wakely <redi at gcc dot gnu.org> ---
(In reply to Kenton Varda from comment #0)
> I do not know exactly what the standard requires here, but all of the
> references I can find claim that erase(iter) should be average-time O(1),
> and none of them suggest that having a large number of entries with the same
> key should cause trouble.

The standard says average case O(1), worst case O(a.size()), so if every
element in the container has the same key then it's O(n).

> FWIW, it looks like libc++ has the same behavior.  Maybe my expectations
> were wrong, and unordered_multimap was never meant to contain more than a
> couple entries per key?

It supports any number of entries with the same key, you just can't expect O(1)
erase operations in that case.  If you have very many collisions maybe your
choice of key or your choice of container isn't ideal.