unordered_set::erase performs worse when nearly empty

[Ian Lance Taylor]

Shaun Jackman <sjackman@bcgsc.ca> writes:

> unordered_set::erase returns an iterator to the next element in the hash
> table. When the hash table is empty, this means checking every single
> bucket. For a hash table that used to have a lot of elements (say one
> million) which were all removed and now has only a few elements (say
> two), erasing an element is very slow. I'm not using the iterator
> returned by erase. Is there a way to avoid this situation? I'm not very
> keen on checking the load_factor and resizing the number buckets.

I think you have described the situation accurately.  It would be easy
for libstdc++ to expose a variant of erase which does not return an
iterator (it's already there, but it's a private method), but that
would be a non-standard extension to the standardized class.  I
recommend that you file an enhancement request at
http://gcc.gnu.org/bugzilla/ to see what the libstdc++ maintainers
think.  Or you could try asking on the libstdc++@gcc.gnu.org mailing
list.

Ian