[Bug libstdc++/41975] [C++0x] [DR579] unordered_set::erase performs worse when nearly empty

[fdumont at gcc dot gnu.org]

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

--- Comment #33 from François Dumont <fdumont at gcc dot gnu.org> 2011-11-23 20:30:25 UTC ---
Author: fdumont
Date: Wed Nov 23 20:30:18 2011
New Revision: 181677

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=181677
Log:
2011-11-23  François Dumont <fdumont@gcc.gnu.org>

    PR libstdc++/41975
    * include/bits/hashtable.h (_Hashtable<>): Major data model
    modification to limit performance impact of empty buckets in
    erase(iterator) implementation.
    * include/bits/hashtable_policy.h (_Hashtable_iterator,
    _Hashtable_const_iterator): Remove not used anymore.
    * include/bits/hashtable_policy.h (_Prime_rehash_policy): Remove
    _M_grow_factor, just use natural evolution of prime numbers. Add
    _M_prev_size to know when the number of buckets can be reduced.
    * include/bits/unordered_set.h (__unordered_set<>,
    __unordered_multiset<>), unordered_map.h (__unordered_map<>,
    __unordered_multimap<>): Change default value of cache hash code
    template parameter, false for integral types with noexcept hash
    functor, true otherwise.
    * include/debug/unordered_map, unordered_set: Adapt transformation
    from iterator/const_iterator to respectively
    local_iterator/const_local_iterator.
    * testsuite/performance/23_containers/copy_construct/unordered_set.cc:
    New.
    * testsuite/23_containers/unordered_set/instantiation_neg.cc: New.
    * testsuite/23_containers/unordered_set/hash_policy/rehash.cc: New.
    * testsuite/23_containers/unordered_multiset/cons/copy.cc: New.
    * testsuite/23_containers/unordered_multiset/erase/1.cc,
    24061-multiset.cc: Add checks on the number of bucket elements.
    * testsuite/23_containers/unordered_multiset/insert/multiset_range.cc,
    multiset_single.cc, multiset_single_move.cc: Likewise.


Added:
    trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/cons/copy.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_set/hash_policy/rehash.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_set/instantiation_neg.cc
   
trunk/libstdc++-v3/testsuite/performance/23_containers/copy_construct/unordered_set.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/bits/hashtable.h
    trunk/libstdc++-v3/include/bits/hashtable_policy.h
    trunk/libstdc++-v3/include/bits/unordered_map.h
    trunk/libstdc++-v3/include/bits/unordered_set.h
    trunk/libstdc++-v3/include/debug/unordered_map
    trunk/libstdc++-v3/include/debug/unordered_set
    trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/24061-multiset.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_range.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single.cc
   
trunk/libstdc++-v3/testsuite/23_containers/unordered_multiset/insert/multiset_single_move.cc