[Bug libstdc++/41975] New: unordered_set::erase performs worse when nearly empty

[sjackman at gmail dot com]

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.

Thanks,
Shaun


-- 
           Summary: unordered_set::erase performs worse when nearly empty
           Product: gcc
           Version: 4.4.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: sjackman at gmail dot com
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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