re PR libstdc++/41975 ([C++0x] [DR579] unordered_set::erase performs worse when nearly empty)

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.

From-SVN: r181677

1 files changed, 24 insertions, 0 deletions

diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc
index 327dc4bd0b2..e48e31149e3 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/erase/1.cc
@@ -23,6 +23,18 @@
 #include <string>
 #include <testsuite_hooks.h>
 
+namespace
+{
+  std::size_t
+  get_nb_bucket_elems(const std::unordered_multiset<std::string>& us)
+  {
+    std::size_t nb = 0;
+    for (std::size_t b = 0; b != us.bucket_count(); ++b)
+      nb += us.bucket_size(b);
+    return nb;
+  }
+}
+
 void test01()
 {
   bool test __attribute__((unused)) = true;
@@ -45,14 +57,17 @@ void test01()
   ms1.insert("one line behind");
   ms1.insert("because to why");
   VERIFY( ms1.size() == 11 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
 
   VERIFY( ms1.erase("eeilo") == 1 );
   VERIFY( ms1.size() == 10 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   iterator it1 = ms1.find("eeilo");
   VERIFY( it1 == ms1.end() );
 
   VERIFY( ms1.erase("tillsammans") == 1 );
   VERIFY( ms1.size() == 9 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   iterator it2 = ms1.find("tillsammans");
   VERIFY( it2 == ms1.end() );
 
@@ -61,17 +76,20 @@ void test01()
   VERIFY( it3 != ms1.end() );
   VERIFY( ms1.erase(*it3) == 1 );
   VERIFY( ms1.size() == 8 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   it3 = ms1.find("belonging (no longer mix)");
   VERIFY( it3 == ms1.end() );
 
   VERIFY( !ms1.erase("abra") );
   VERIFY( ms1.size() == 8 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
 
   VERIFY( !ms1.erase("eeilo") );
   VERIFY( ms1.size() == 8 );
 
   VERIFY( ms1.erase("because to why") == 2 );
   VERIFY( ms1.size() == 6 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   iterator it4 = ms1.find("because to why");
   VERIFY( it4 == ms1.end() );
 
@@ -87,11 +105,13 @@ void test01()
 
   VERIFY( ms1.erase(*it5) == 1 );
   VERIFY( ms1.size() == 5 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   it5 = ms1.find("umbra/penumbra");
   VERIFY( it5 == ms1.end() );
 
   VERIFY( ms1.erase(*it6) == 1 );
   VERIFY( ms1.size() == 4 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   it6 = ms1.find("one line behind");
   VERIFY( it6 == ms1.end() );
 
@@ -103,6 +123,7 @@ void test01()
 
   VERIFY( ms1.erase(*it8) == 1 );
   VERIFY( ms1.size() == 3 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   VERIFY( ++it7 == it9 );
 
   iterator it10 = it9;
@@ -110,15 +131,18 @@ void test01()
   iterator it11 = it10;
 
   VERIFY( ms1.erase(*it9) == 1 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   VERIFY( ms1.size() == 2 );
   VERIFY( ++it10 == ms1.end() );
 
   VERIFY( ms1.erase(ms1.begin()) != ms1.end() );  
   VERIFY( ms1.size() == 1 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   VERIFY( ms1.begin() == it11 );
 
   VERIFY( ms1.erase(*ms1.begin()) == 1 );  
   VERIFY( ms1.size() == 0 );
+  VERIFY( get_nb_bucket_elems(ms1) == ms1.size() );
   VERIFY( ms1.begin() == ms1.end() );
 }