2008-06-04 Benjamin Kosnik <bkoz@redhat.com>

	* include/ext/pb_ds/assoc_container.hpp: Change allocator typedef
	to allocator_type, as per existing conventions.	
	* include/ext/pb_ds/detail/binomial_heap_base_/
	binomial_heap_base_.hpp: Same.
	* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
	* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp: Same.
	* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
	* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Same.
	* include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp: Same.
	* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Same.
	* include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	left_child_next_sibling_heap_.hpp: Same.
	* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Same.
	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
	* include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
	* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/
	rc_binomial_heap_.hpp: Same.
	* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Same.
	* include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
	* include/ext/pb_ds/list_update_policy.hpp: Same.
	* include/ext/pb_ds/exception.hpp: Same.
	* include/ext/pb_ds/tree_policy.hpp: Same.
	* include/ext/pb_ds/trie_policy.hpp: Same.
	* include/ext/pb_ds/priority_queue.hpp: Same.
	* testsuite/util/regression/trait/assoc/trait.hpp: Same.
	* testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
	* testsuite/util/regression/rand/priority_queue/detail/
	defs_fn_imps.hpp: Same.
	* testsuite/util/regression/rand/priority_queue/detail/
	operator_fn_imps.hpp: Same.
	* testsuite/util/regression/rand/priority_queue/
	container_rand_regression_test.hpp: Same.
	* testsuite/util/regression/rand/assoc/detail/defs_fn_imps.hpp: Same.
	* testsuite/util/regression/rand/assoc/detail/
	operator_fn_imps.hpp: Same.
	* testsuite/util/regression/rand/assoc/
	container_rand_regression_test.hpp: Same.
	* testsuite/util/native_type/assoc/native_multimap.hpp: Same.
	* testsuite/util/native_type/assoc/native_hash_multimap.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	tree_supports_order_statistics.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	trie_supports_prefix_search.hpp: Same.
	* testsuite/util/common_type/assoc/detail/
	trie_supports_order_statistics.hpp: Same.



git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@136359 138bc75d-0d04-0410-961f-82ee72b054a4

37 files changed, 111 insertions, 73 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 1132ddd49da..d06e303f343 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,54 @@
+2008-06-04  Benjamin Kosnik  <bkoz@redhat.com>
+
+	* include/ext/pb_ds/assoc_container.hpp: Change allocator typedef
+	to allocator_type, as per existing conventions.	
+	* include/ext/pb_ds/detail/binomial_heap_base_/
+	binomial_heap_base_.hpp: Same.
+	* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Same.
+	* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Same.
+	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp: Same.
+	* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Same.
+	* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Same.
+	* include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp: Same.
+	* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Same.
+	* include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp: Same.
+	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+	left_child_next_sibling_heap_.hpp: Same.
+	* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Same.
+	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Same.
+	* include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp: Same.
+	* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Same.
+	* include/ext/pb_ds/detail/rc_binomial_heap_/
+	rc_binomial_heap_.hpp: Same.
+	* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Same.
+	* include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp: Same.
+	* include/ext/pb_ds/list_update_policy.hpp: Same.
+	* include/ext/pb_ds/exception.hpp: Same.
+	* include/ext/pb_ds/tree_policy.hpp: Same.
+	* include/ext/pb_ds/trie_policy.hpp: Same.
+	* include/ext/pb_ds/priority_queue.hpp: Same.
+	* testsuite/util/regression/trait/assoc/trait.hpp: Same.
+	* testsuite/util/regression/trait/assoc/type_trait.hpp: Same.
+	* testsuite/util/regression/rand/priority_queue/detail/
+	defs_fn_imps.hpp: Same.
+	* testsuite/util/regression/rand/priority_queue/detail/
+	operator_fn_imps.hpp: Same.
+	* testsuite/util/regression/rand/priority_queue/
+	container_rand_regression_test.hpp: Same.
+	* testsuite/util/regression/rand/assoc/detail/defs_fn_imps.hpp: Same.
+	* testsuite/util/regression/rand/assoc/detail/
+	operator_fn_imps.hpp: Same.
+	* testsuite/util/regression/rand/assoc/
+	container_rand_regression_test.hpp: Same.
+	* testsuite/util/native_type/assoc/native_multimap.hpp: Same.
+	* testsuite/util/native_type/assoc/native_hash_multimap.hpp: Same.
+	* testsuite/util/common_type/assoc/detail/
+	tree_supports_order_statistics.hpp: Same.
+	* testsuite/util/common_type/assoc/detail/
+	trie_supports_prefix_search.hpp: Same.
+	* testsuite/util/common_type/assoc/detail/
+	trie_supports_order_statistics.hpp: Same.
+	
 2008-06-02  Sandra Loosemore  <sandra@codesourcery.com>
 	    Daniel Jacobowitz  <dan@codesourcery.com>
 
diff --git a/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
index e2ac37c11cc..8dbb43a9030 100644
--- a/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/assoc_container.hpp
@@ -71,13 +71,13 @@ namespace __gnu_pbds
 
   public:
     typedef Tag 					container_category;
-    typedef Allocator 					allocator;
-    typedef typename allocator::size_type 		size_type;
-    typedef typename allocator::difference_type 	difference_type;
+    typedef Allocator 					allocator_type;
+    typedef typename allocator_type::size_type 		size_type;
+    typedef typename allocator_type::difference_type 	difference_type;
 
     // key_type
-    typedef typename allocator::template rebind<Key>::other::value_type key_type;
-    typedef typename allocator::template rebind<key_type>::other key_rebind;
+    typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
+    typedef typename allocator_type::template rebind<key_type>::other key_rebind;
     typedef typename key_rebind::reference 		key_reference;
     typedef typename key_rebind::const_reference 	const_key_reference;
     typedef typename key_rebind::pointer 		key_pointer;
@@ -85,7 +85,7 @@ namespace __gnu_pbds
 
     // mapped_type
     typedef Mapped 					mapped_type;
-    typedef typename allocator::template rebind<mapped_type>::other mapped_rebind;
+    typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
     typedef typename mapped_rebind::reference 		mapped_reference;
     typedef typename mapped_rebind::const_reference	const_mapped_reference;
     typedef typename mapped_rebind::pointer 		mapped_pointer;
@@ -93,7 +93,7 @@ namespace __gnu_pbds
 
     // value_type
     typedef typename base_type::value_type 		value_type;
-    typedef typename allocator::template rebind<value_type>::other value_rebind;
+    typedef typename allocator_type::template rebind<value_type>::other value_rebind;
     typedef typename value_rebind::reference		reference;
     typedef typename value_rebind::const_reference 	const_reference;
     typedef typename value_rebind::pointer 		pointer;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
index 6e46cedbbe9..587cfe06dcb 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
@@ -241,7 +241,7 @@ namespace __gnu_pbds
 
       typedef Cmp_Fn cmp_fn;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
       typedef typename Node_And_It_Traits::node_update node_update;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
index cf10195d28c..310ddadf28b 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
@@ -178,7 +178,7 @@ namespace __gnu_pbds
 
       typedef Cmp_Fn cmp_fn;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
     public:
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp
index 8f1826ef164..3641faad2a9 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_/binomial_heap_.hpp
@@ -93,7 +93,7 @@ namespace __gnu_pbds
       typedef typename base_type::const_iterator const_iterator;
       typedef typename base_type::iterator iterator;
       typedef typename base_type::cmp_fn cmp_fn;
-      typedef typename base_type::allocator allocator;
+      typedef typename base_type::allocator_type allocator_type;
 
       binomial_heap_();
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp
index acd1c3cf4dc..c77063618e5 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp
@@ -138,7 +138,7 @@ namespace __gnu_pbds
 
       typedef Cmp_Fn cmp_fn;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
     public:
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp
index 3a772fa1df8..71c7327120e 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp
@@ -167,7 +167,7 @@ namespace __gnu_pbds
 #undef PB_DS_GEN_POS
 
     public:
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
       typedef Hash_Fn hash_fn;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp
index 8da31e70e8a..2fcb25c8310 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp
@@ -168,7 +168,7 @@ namespace __gnu_pbds
 #undef PB_DS_GEN_POS
 
     public:
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
       typedef Hash_Fn hash_fn;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp
index 196ae3010ca..a200b7e3672 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp
@@ -194,7 +194,7 @@ namespace __gnu_pbds
 
       typedef Cmp_Fn cmp_fn;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
     public:
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp
index 267beccceaf..8b8b1cffe90 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp
@@ -154,7 +154,7 @@ namespace __gnu_pbds
       typedef cond_dealtor<entry, Allocator> cond_dealtor_t;
 
     public:
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
       typedef Eq_Fn eq_fn;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
index 421a6bea617..3abb259a789 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
@@ -158,7 +158,7 @@ namespace __gnu_pbds
 
     public:
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp
index 6d3790653a4..4ad1e4115d2 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp
@@ -137,7 +137,7 @@ namespace __gnu_pbds
 
       typedef Cmp_Fn cmp_fn;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
 
       pairing_heap_();
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp
index 00a00d34bce..eb55ea52e01 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp
@@ -164,7 +164,7 @@ namespace __gnu_pbds
 
     public:
       typedef pat_trie_tag container_category;
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp
index b5d50a92ae8..6d638395bac 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp
@@ -124,7 +124,7 @@ namespace __gnu_pbds
 
     public:
       typedef Cmp_Fn cmp_fn;
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
       typedef typename base_type::key_type key_type;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp
index fc90ea7dea2..a0832bf97b6 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp
@@ -62,24 +62,24 @@ namespace __gnu_pbds
     class rc
     {
     private:
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
-      typedef typename allocator::size_type size_type;
+      typedef typename allocator_type::size_type size_type;
 
       typedef Node node;
 
       typedef
-      typename allocator::template rebind<
+      typename allocator_type::template rebind<
 	node>::other::pointer
       node_pointer;
 
       typedef
-      typename allocator::template rebind<
+      typename allocator_type::template rebind<
 	node_pointer>::other::pointer
       entry_pointer;
 
       typedef
-      typename allocator::template rebind<
+      typename allocator_type::template rebind<
 	node_pointer>::other::const_pointer
       const_entry_pointer;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp
index 5b4a3b4122f..729dccf3c77 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/rc_binomial_heap_/rc_binomial_heap_.hpp
@@ -112,7 +112,7 @@ namespace __gnu_pbds
 
       typedef typename base_type::cmp_fn cmp_fn;
 
-      typedef typename base_type::allocator allocator;
+      typedef typename base_type::allocator_type allocator_type;
 
     public:
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp
index 1642abb068f..10be0c2a4cf 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/splay_tree_.hpp
@@ -145,7 +145,7 @@ namespace __gnu_pbds
       typedef typename base_type::node_pointer node_pointer;
 
     public:
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
       typedef typename Allocator::size_type size_type;
       typedef typename Allocator::difference_type difference_type;
       typedef Cmp_Fn cmp_fn;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp
index ee874e823be..9eb617dcf09 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp
@@ -137,7 +137,7 @@ namespace __gnu_pbds
 
       typedef Cmp_Fn cmp_fn;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
     public:
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp
index 2a1319a4629..c1146303616 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp
@@ -85,9 +85,9 @@ namespace __gnu_pbds
 
       typedef E_Access_Traits e_access_traits;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
-      typedef typename allocator::size_type size_type;
+      typedef typename allocator_type::size_type size_type;
 
       typedef null_node_metadata metadata_type;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/exception.hpp b/libstdc++-v3/include/ext/pb_ds/exception.hpp
index 77d3f2d6927..4a35931b3c5 100644
--- a/libstdc++-v3/include/ext/pb_ds/exception.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/exception.hpp
@@ -61,7 +61,7 @@ namespace __gnu_pbds
 
   // An entry cannot be inserted into a container object for logical
   // reasons (not, e.g., if memory is unabvailable, in which case
-  // the allocator's exception will be thrown).
+  // the allocator_type's exception will be thrown).
   struct insert_error : public container_error { };
 
   // A join cannot be performed logical reasons (i.e., the ranges of
diff --git a/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp b/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp
index 5a63a3e16dc..67a4e883fa7 100644
--- a/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp
@@ -66,13 +66,13 @@ namespace __gnu_pbds
   class move_to_front_lu_policy
   {
   public:
-    typedef Allocator allocator;
+    typedef Allocator allocator_type;
       
     // Metadata on which this functor operates.
     typedef null_lu_metadata metadata_type;
       
     // Reference to metadata on which this functor operates.
-    typedef typename allocator::template rebind<metadata_type>::other metadata_rebind;
+    typedef typename allocator_type::template rebind<metadata_type>::other metadata_rebind;
     typedef typename metadata_rebind::reference metadata_reference;
       
     // Creates a metadata object.
@@ -103,14 +103,14 @@ namespace __gnu_pbds
   : private detail::counter_lu_policy_base<typename Allocator::size_type>
   {
   public:
-    typedef Allocator allocator;
+    typedef Allocator allocator_type;
 
     enum
       {
 	max_count = Max_Count
       };
 
-    typedef typename allocator::size_type size_type;
+    typedef typename allocator_type::size_type size_type;
 
     // Metadata on which this functor operates.
     typedef detail::counter_lu_metadata<size_type> metadata_type;
diff --git a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
index 90ffafffefa..3433f5116fe 100644
--- a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
@@ -68,11 +68,11 @@ namespace __gnu_pbds
     typedef Value_Type 					value_type;
     typedef Cmp_Fn 					cmp_fn;
     typedef Tag 					container_category;
-    typedef Allocator 					allocator;
-    typedef typename allocator::size_type 		size_type;
-    typedef typename allocator::difference_type 	difference_type;
+    typedef Allocator 					allocator_type;
+    typedef typename allocator_type::size_type 		size_type;
+    typedef typename allocator_type::difference_type 	difference_type;
 
-    typedef typename allocator::template rebind<value_type>::other value_rebind;
+    typedef typename allocator_type::template rebind<value_type>::other value_rebind;
     typedef typename value_rebind::reference 		reference;
     typedef typename value_rebind::const_reference 	const_reference;
     typedef typename value_rebind::pointer 	   	pointer;
diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
index dedabec5c48..1f3da0ee481 100644
--- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
@@ -80,8 +80,8 @@ namespace __gnu_pbds
 
   public:
     typedef Cmp_Fn cmp_fn;
-    typedef Allocator allocator;
-    typedef typename allocator::size_type size_type;
+    typedef Allocator allocator_type;
+    typedef typename allocator_type::size_type size_type;
     typedef typename base_type::key_type key_type;
     typedef typename base_type::const_key_reference const_key_reference;
 
@@ -120,7 +120,7 @@ namespace __gnu_pbds
     // Const pointer to the container's value-type.
     typedef typename base_type::const_pointer const_pointer;
 
-    typedef typename allocator::template rebind<metadata_type>::other metadata_rebind;
+    typedef typename allocator_type::template rebind<metadata_type>::other metadata_rebind;
     // Const metadata reference.
     typedef typename metadata_rebind::const_reference const_metadata_reference;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
index b18de195ed8..642c5300a66 100644
--- a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
@@ -167,10 +167,10 @@ namespace __gnu_pbds
     typedef typename e_access_traits::const_iterator const_e_iterator;
 
     // Allocator type.
-    typedef Allocator allocator;
+    typedef Allocator allocator_type;
 
     // Size type.
-    typedef typename allocator::size_type size_type;
+    typedef typename allocator_type::size_type size_type;
     typedef detail::null_node_metadata metadata_type;
     typedef Const_Node_Iterator const_node_iterator;
     typedef Node_Iterator node_iterator;
@@ -256,8 +256,8 @@ namespace __gnu_pbds
   public:
     typedef E_Access_Traits e_access_traits;
     typedef typename e_access_traits::const_iterator const_e_iterator;
-    typedef Allocator allocator;
-    typedef typename allocator::size_type size_type;
+    typedef Allocator allocator_type;
+    typedef typename allocator_type::size_type size_type;
     typedef typename base_type::key_type key_type;
     typedef typename base_type::const_key_reference const_key_reference;
 
diff --git a/libstdc++-v3/testsuite/util/common_type/assoc/detail/tree_supports_order_statistics.hpp b/libstdc++-v3/testsuite/util/common_type/assoc/detail/tree_supports_order_statistics.hpp
index f4b23110491..c219271a8c4 100644
--- a/libstdc++-v3/testsuite/util/common_type/assoc/detail/tree_supports_order_statistics.hpp
+++ b/libstdc++-v3/testsuite/util/common_type/assoc/detail/tree_supports_order_statistics.hpp
@@ -69,7 +69,7 @@ namespace __gnu_pbds
             typename Tree_Cntnr::const_node_iterator,
             typename Tree_Cntnr::node_iterator,
             typename Tree_Cntnr::cmp_fn,
-            typename Tree_Cntnr::allocator> >::value
+            typename Tree_Cntnr::allocator_type> >::value
 	  };
       };
 
diff --git a/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_order_statistics.hpp b/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_order_statistics.hpp
index c23708f23cc..82d47804286 100644
--- a/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_order_statistics.hpp
+++ b/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_order_statistics.hpp
@@ -69,7 +69,7 @@ namespace __gnu_pbds
             typename Tree_Cntnr::const_node_iterator,
             typename Tree_Cntnr::node_iterator,
             typename Tree_Cntnr::e_access_traits,
-            typename Tree_Cntnr::allocator> >::value
+            typename Tree_Cntnr::allocator_type> >::value
 	  };
       };
 
diff --git a/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_prefix_search.hpp b/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_prefix_search.hpp
index 0adf029507e..5b8c4f3759d 100644
--- a/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_prefix_search.hpp
+++ b/libstdc++-v3/testsuite/util/common_type/assoc/detail/trie_supports_prefix_search.hpp
@@ -69,7 +69,7 @@ namespace __gnu_pbds
             typename Tree_Cntnr::const_node_iterator,
             typename Tree_Cntnr::node_iterator,
             typename Tree_Cntnr::e_access_traits,
-            typename Tree_Cntnr::allocator> >::value
+            typename Tree_Cntnr::allocator_type> >::value
 	  };
       };
 
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp
index a3f82ba8a75..f644ae2de1a 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_hash_multimap.hpp
@@ -76,12 +76,12 @@ namespace __gnu_pbds
 
     public:
       typedef native_hash_tag 			container_category;
-      typedef Allocator 			allocator;
+      typedef Allocator 			allocator_type;
       typedef typename base_type::iterator 	iterator;
       typedef typename base_type::const_iterator const_iterator;
 
       typedef
-      typename allocator::template rebind<pair_type>::other::const_reference
+      typename allocator_type::template rebind<pair_type>::other::const_reference
       const_reference;
 
       native_hash_multimap() : base_type(Init_Size)
diff --git a/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp b/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp
index 906fca3244e..c9e12114296 100644
--- a/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp
+++ b/libstdc++-v3/testsuite/util/native_type/assoc/native_multimap.hpp
@@ -70,7 +70,7 @@ namespace __gnu_pbds
     public:
       typedef native_tree_tag container_category;
 
-      typedef Allocator allocator;
+      typedef Allocator allocator_type;
 
       typedef
       typename Allocator::template rebind<
diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.hpp
index 7eaa3968f9a..af0a8e17b7e 100644
--- a/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.hpp
+++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/container_rand_regression_test.hpp
@@ -129,7 +129,7 @@ namespace detail
 
   private:
     typedef Cntnr 					cntnr;
-    typedef typename cntnr::allocator 			allocator;
+    typedef typename cntnr::allocator_type 			allocator_type;
     typedef typename cntnr::size_type 			size_type;
     typedef regression_test_traits<Cntnr> 		test_traits;
     typedef typename test_traits::key_type 		key_type;
diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/defs_fn_imps.hpp b/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/defs_fn_imps.hpp
index 0acb20cd62e..f3e01d97fac 100644
--- a/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/defs_fn_imps.hpp
+++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/defs_fn_imps.hpp
@@ -180,7 +180,7 @@ void
 PB_DS_CLASS_C_DEC::
 policy_defs()
 {
-  typedef typename Cntnr::allocator test_allocator;
+  typedef typename Cntnr::allocator_type test_allocator;
 
   policy_defs(typename Cntnr::container_category());
 }
diff --git a/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/operator_fn_imps.hpp b/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/operator_fn_imps.hpp
index 323376480d3..8c11f765766 100644
--- a/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/operator_fn_imps.hpp
+++ b/libstdc++-v3/testsuite/util/regression/rand/assoc/detail/operator_fn_imps.hpp
@@ -71,7 +71,7 @@ operator()()
       for (m_i = 0; m_i < m_n; ++m_i)
         {
 	  PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i));
-	  allocator::set_label(m_i);
+	  allocator_type::set_label(m_i);
 	  switch (m_i)
             {
             case 0:
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.hpp b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.hpp
index eeedc27bdca..dadf8b4d7b5 100644
--- a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.hpp
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/container_rand_regression_test.hpp
@@ -141,7 +141,7 @@ namespace __gnu_pbds
       private:
 	typedef Cntnr cntnr;
 
-	typedef typename cntnr::allocator allocator;
+	typedef typename cntnr::allocator_type allocator_type;
 
 	typedef typename cntnr::size_type size_type;
 
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/defs_fn_imps.hpp b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/defs_fn_imps.hpp
index 85bc6b0a14e..ae406937337 100644
--- a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/defs_fn_imps.hpp
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/defs_fn_imps.hpp
@@ -50,15 +50,10 @@ PB_DS_CLASS_C_DEC::
 defs()
 {
   // General container types.
-
   typedef typename Cntnr::size_type test_size_type;
-
   typedef typename Cntnr::difference_type difference_type;
-
   value_defs();
-
   iterator_defs();
-
   policy_defs();
 }
 
@@ -68,13 +63,9 @@ PB_DS_CLASS_C_DEC::
 value_defs()
 {
   typedef typename Cntnr::value_type test_value_type;
-
   typedef typename Cntnr::reference test_reference;
-
   typedef typename Cntnr::const_reference test_const_reference;
-
   typedef typename Cntnr::pointer test_pointer;
-
   typedef typename Cntnr::const_pointer test_const_pointer;
 }
 
@@ -92,11 +83,8 @@ PB_DS_CLASS_C_DEC::
 iterator_defs()
 {
   typedef typename Cntnr::point_iterator test_point_iterator;
-
   typedef typename Cntnr::const_point_iterator const_test_point_iterator;
-
   typedef typename Cntnr::iterator test_iterator;
-
   typedef typename Cntnr::const_iterator const_test_iterator;
 }
 
@@ -105,7 +93,6 @@ void
 PB_DS_CLASS_C_DEC::
 policy_defs()
 {
-  typedef typename Cntnr::allocator test_allocator;
-
+  typedef typename Cntnr::allocator_type test_allocator;
   typedef typename Cntnr::cmp_fn test_cmp_fn;
 }
diff --git a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/operator_fn_imps.hpp b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/operator_fn_imps.hpp
index 7a34b812167..61869919843 100644
--- a/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/operator_fn_imps.hpp
+++ b/libstdc++-v3/testsuite/util/regression/rand/priority_queue/detail/operator_fn_imps.hpp
@@ -71,7 +71,7 @@ operator()()
       for (m_i = 0; m_i < m_n; ++m_i)
         {
 	  PB_DS_TRACE("Op #" << static_cast<unsigned long>(m_i));
-	  allocator::set_label(m_i);
+	  allocator_type::set_label(m_i);
 	  switch(m_i)
             {
             case 0:
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp
index e8791a4472a..5e97aea41e5 100644
--- a/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/trait.hpp
@@ -76,7 +76,7 @@ namespace detail
 #define PB_DS_NATIVE_TYPE_TRAITS_C_DEC \
   native_type_traits<typename PB_DS_TYPE_TRAITS_C_DEC::key_type, \
 		     typename PB_DS_TYPE_TRAITS_C_DEC::mapped_type, \
-		     typename Cntnr::allocator>
+		     typename Cntnr::allocator_type>
 
 #define PB_DS_RESIZE_TRAITS_C_DEC \
   regression_test_resize_traits<Cntnr, typename Cntnr::container_category>
diff --git a/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp b/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp
index 5c0682de38f..b9db4a71b3d 100644
--- a/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp
+++ b/libstdc++-v3/testsuite/util/regression/trait/assoc/type_trait.hpp
@@ -82,12 +82,12 @@ namespace __gnu_pbds
 	{ return extract_key_imp(r_val); }
 
       private:
-	typedef typename cntnr::allocator::template rebind<basic_type>::other
+	typedef typename cntnr::allocator_type::template rebind<basic_type>::other
 	basic_type_rebind;
 	
 	typedef typename basic_type_rebind::const_reference basic_type_const_reference;
 
-	typedef typename cntnr::allocator::template rebind<std::pair<basic_type, basic_type> >::other pair_type_rebind;
+	typedef typename cntnr::allocator_type::template rebind<std::pair<basic_type, basic_type> >::other pair_type_rebind;
 	typedef typename pair_type_rebind::const_reference pair_type_const_reference;
 
 	template<typename Gen>