http://gcc.gnu.org/bugzilla/show_bug.cgi?id=58153
Bug ID: 58153
Summary: unordered_multimap::erase(iterator) is not
constant-time when many entries have the same key
Product: gcc
Version: 4.8.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: temporal at gmail dot com
It appears that if an unordered_multimap has k entries with the same key, then
erase(iter) for any of those entries is O(k) rather than constant-time. The
problem is that _Hashtable::erase() searches through all nodes in the bucket
looking for the one previous to the one being removed. This is reasonable for
unordered_map, where buckets are expected to have no more than a couple
entries. But it is surprising for unordered_multimap, whose whole purpose is
to support multiple entries with the same key (and therefore the same bucket).
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.
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?
