Adjust pb_ds extensions to use allocator_traits

These changes are largely useless, because most of them are simply
allowing 'reference' and 'const_reference' types to be obtained from an
allocator, and since C++11 allocators don't define reference types (they
just use plain lvalue references. Pretending to support C++98 allocators
with user-defined reference types is a waste of time (especially as
several of the pb_ds types appear to use a static allocator object which
means stateful allocators are not supported).

	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp:
	Use detail::rebind_traits.
	* include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp:
	Likewise.
	* include/ext/pb_ds/detail/bin_search_tree_/traits.hpp: Likewise.
	* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Likewise.
	* include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp: Likewise.
	* include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp: Likewise.
	* include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp:
	Likewise.
	* include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp:
	Likewise.
	* include/ext/pb_ds/detail/branch_policy/branch_policy.hpp: Likewise.
	* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Likewise.
	* include/ext/pb_ds/detail/cond_dealtor.hpp: Likewise.
	* include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp (has_eq_fn): Likewise.
	* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Likewise.
	* include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp: Likewise.
	* include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Likewise.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	left_child_next_sibling_heap_.hpp: Likewise.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp:
	Likewise.
	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
	point_const_iterator.hpp: Likewise.
	* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/
	constructors_destructor_fn_imps.hpp: Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Likewise.
	* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Likewise.
	* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Likewise.
	* include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp: Likewise.
	* include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Likewise.
	* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Likewise.
	* include/ext/pb_ds/detail/splay_tree_/node.hpp: Likewise.
	* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Likewise.
	* include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp:
	Likewise.
	* include/ext/pb_ds/detail/type_utils.hpp: Fix typo in comment.
	* include/ext/pb_ds/detail/types_traits.hpp (stored_value): Add
	bool parameter to control whether the hash value is stored.
	(select_base_type): New class template and partial specialization.
	(maybe_null_type): Likewise.
	(rebind_traits): New class template.
	(type_base): Remove four nearly identical specializations.
	(type_dispatch): Remove.
	(type_traits): Use select_base_type and maybe_null_type instead of
	type_base to control differences between specializations.
	* include/ext/pb_ds/list_update_policy.hpp: Use detail::rebind_traits.
	* include/ext/pb_ds/priority_queue.hpp: Likewise.
	* include/ext/pb_ds/tree_policy.hpp: Likewise.
	* include/ext/pb_ds/trie_policy.hpp: Likewise.

From-SVN: r277336

37 files changed, 382 insertions, 469 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 9f19e4f..bf0af28 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,5 +1,59 @@
 2019-10-23  Jonathan Wakely  <jwakely@redhat.com>
 
+	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp:
+	Use detail::rebind_traits.
+	* include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp:
+	Likewise.
+	* include/ext/pb_ds/detail/bin_search_tree_/traits.hpp: Likewise.
+	* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Likewise.
+	* include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp: Likewise.
+	* include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp: Likewise.
+	* include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp:
+	Likewise.
+	* include/ext/pb_ds/detail/binomial_heap_base_/binomial_heap_base_.hpp:
+	Likewise.
+	* include/ext/pb_ds/detail/branch_policy/branch_policy.hpp: Likewise.
+	* include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Likewise.
+	* include/ext/pb_ds/detail/cond_dealtor.hpp: Likewise.
+	* include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp (has_eq_fn): Likewise.
+	* include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Likewise.
+	* include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp: Likewise.
+	* include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp: Likewise.
+	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+	left_child_next_sibling_heap_.hpp: Likewise.
+	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp:
+	Likewise.
+	* include/ext/pb_ds/detail/left_child_next_sibling_heap_/
+	point_const_iterator.hpp: Likewise.
+	* include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Likewise.
+	* include/ext/pb_ds/detail/ov_tree_map_/
+	constructors_destructor_fn_imps.hpp: Likewise.
+	* include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp: Likewise.
+	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp: Likewise.
+	* include/ext/pb_ds/detail/pairing_heap_/pairing_heap_.hpp: Likewise.
+	* include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Likewise.
+	* include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp: Likewise.
+	* include/ext/pb_ds/detail/rb_tree_map_/node.hpp: Likewise.
+	* include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Likewise.
+	* include/ext/pb_ds/detail/splay_tree_/node.hpp: Likewise.
+	* include/ext/pb_ds/detail/thin_heap_/thin_heap_.hpp: Likewise.
+	* include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp:
+	Likewise.
+	* include/ext/pb_ds/detail/type_utils.hpp: Fix typo in comment.
+	* include/ext/pb_ds/detail/types_traits.hpp (stored_value): Add
+	bool parameter to control whether the hash value is stored.
+	(select_base_type): New class template and partial specialization.
+	(maybe_null_type): Likewise.
+	(rebind_traits): New class template.
+	(type_base): Remove four nearly identical specializations.
+	(type_dispatch): Remove.
+	(type_traits): Use select_base_type and maybe_null_type instead of
+	type_base to control differences between specializations.
+	* include/ext/pb_ds/list_update_policy.hpp: Use detail::rebind_traits.
+	* include/ext/pb_ds/priority_queue.hpp: Likewise.
+	* include/ext/pb_ds/tree_policy.hpp: Likewise.
+	* include/ext/pb_ds/trie_policy.hpp: Likewise.
+
 	* include/backward/hash_set (hash_set): Use __alloc_traits.
 	* include/backward/hashtable.h (_Hashtable): Likewise.
 	* include/ext/alloc_traits.h (__alloc_traits::allocate): Add overload
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 b64cc38..89ccf9e 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
@@ -77,7 +77,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC  \
     debug_map_base<Key,	eq_by_less<Key, Cmp_Fn>, \
-	      typename _Alloc::template rebind<Key>::other::const_reference>
+	      typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
 #ifdef PB_DS_TREE_TRACE
@@ -108,16 +108,17 @@ namespace __gnu_pbds
       public Node_And_It_Traits::node_update
     {
       typedef Node_And_It_Traits 			traits_type;
+      typedef rebind_traits<_Alloc, typename traits_type::node>
+	node_alloc_traits;
 
     protected:
       typedef PB_DS_BIN_TREE_TRAITS_BASE 	       	traits_base;
 
       typedef
-      typename _Alloc::template rebind<typename traits_type::node>::other
-      node_allocator;
+      typename node_alloc_traits::allocator_type	node_allocator;
 
-      typedef typename node_allocator::value_type 	node;
-      typedef typename node_allocator::pointer 		node_pointer;
+      typedef typename node_alloc_traits::value_type 	node;
+      typedef typename node_alloc_traits::pointer 	node_pointer;
 
       typedef typename traits_type::null_node_update_pointer
       null_node_update_pointer;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp
index bcde6a0..b44e3b0 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp
@@ -58,10 +58,7 @@ namespace __gnu_pbds
     class bin_search_tree_const_node_it_
     {
     private:
-      typedef
-      typename _Alloc::template rebind<
-      Node>::other::pointer
-      node_pointer;
+      typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer;
 
     public:
       /// Category.
@@ -83,9 +80,8 @@ namespace __gnu_pbds
       typedef typename Node::metadata_type metadata_type;
 
       /// Const metadata reference type.
-      typedef
-      typename _Alloc::template rebind<metadata_type>::other::const_reference
-      metadata_const_reference;
+      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference
+	metadata_const_reference;
 
 
       bin_search_tree_const_node_it_(const node_pointer p_nd = 0)
@@ -137,10 +133,7 @@ namespace __gnu_pbds
     : public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
     {
     private:
-      typedef
-      typename _Alloc::template rebind<
-      Node>::other::pointer
-      node_pointer;
+      typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer;
 
     public:
       /// Iterator's value type.
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp
index b42c035..7a601bd 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp
@@ -64,14 +64,14 @@ namespace __gnu_pbds
     {
     private:
       typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
+      typedef rebind_traits<_Alloc, Node> node_alloc_traits;
 
     public:
       typedef Node node;
 
       typedef
       bin_search_tree_const_it_<
-	typename _Alloc::template rebind<
-	node>::other::pointer,
+	typename node_alloc_traits::pointer,
 	typename type_traits::value_type,
 	typename type_traits::pointer,
 	typename type_traits::const_pointer,
@@ -83,8 +83,7 @@ namespace __gnu_pbds
 
       typedef
       bin_search_tree_it_<
-	typename _Alloc::template rebind<
-	node>::other::pointer,
+	typename node_alloc_traits::pointer,
 	typename type_traits::value_type,
 	typename type_traits::pointer,
 	typename type_traits::const_pointer,
@@ -96,8 +95,7 @@ namespace __gnu_pbds
 
       typedef
       bin_search_tree_const_it_<
-	typename _Alloc::template rebind<
-	node>::other::pointer,
+	typename node_alloc_traits::pointer,
 	typename type_traits::value_type,
 	typename type_traits::pointer,
 	typename type_traits::const_pointer,
@@ -109,8 +107,7 @@ namespace __gnu_pbds
 
       typedef
       bin_search_tree_it_<
-	typename _Alloc::template rebind<
-	node>::other::pointer,
+	typename node_alloc_traits::pointer,
 	typename type_traits::value_type,
 	typename type_traits::pointer,
 	typename type_traits::const_pointer,
@@ -171,14 +168,14 @@ namespace __gnu_pbds
     {
     private:
       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
+      typedef rebind_traits<_Alloc, Node> node_alloc_traits;
 
     public:
       typedef Node node;
 
       typedef
       bin_search_tree_const_it_<
-	typename _Alloc::template rebind<
-	node>::other::pointer,
+	typename node_alloc_traits::pointer,
 	typename type_traits::value_type,
 	typename type_traits::pointer,
 	typename type_traits::const_pointer,
@@ -192,8 +189,7 @@ namespace __gnu_pbds
 
       typedef
       bin_search_tree_const_it_<
-	typename _Alloc::template rebind<
-	node>::other::pointer,
+	typename node_alloc_traits::pointer,
 	typename type_traits::value_type,
 	typename type_traits::pointer,
 	typename type_traits::const_pointer,
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 dbfd612..58cb69e 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
@@ -102,23 +102,23 @@ namespace __gnu_pbds
 
       typedef integral_constant<int, simple_value> 	no_throw_copies_t;
 
-      typedef typename _Alloc::template rebind<value_type>	__rebind_v;
-      typedef typename __rebind_v::other 		value_allocator;
+      typedef rebind_traits<_Alloc, value_type>		__rebind_v;
+      typedef typename __rebind_v::allocator_type 	value_allocator;
 
     public:
-      typedef typename value_allocator::pointer		pointer;
-      typedef typename value_allocator::const_pointer	const_pointer;
-      typedef typename value_allocator::reference	reference;
-      typedef typename value_allocator::const_reference	const_reference;
+      typedef typename __rebind_v::pointer		pointer;
+      typedef typename __rebind_v::const_pointer	const_pointer;
+      typedef typename __rebind_v::reference	reference;
+      typedef typename __rebind_v::const_reference	const_reference;
 
       typedef typename __conditional_type<simple_value,
 					  value_type, pointer>::__type
       							entry;
 
-      typedef typename _Alloc::template rebind<entry>::other
+      typedef typename rebind_traits<_Alloc, entry>::allocator_type
       							entry_allocator;
 
-      typedef typename entry_allocator::pointer 	entry_pointer;
+      typedef typename rebind_traits<_Alloc, entry>::pointer 	entry_pointer;
 
       typedef binary_heap_point_const_iterator_<value_type, entry,
 						simple_value, _Alloc>
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp
index 38381ad..1efcdc3 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_cmp.hpp
@@ -62,10 +62,10 @@ namespace __gnu_pbds
       struct entry_cmp<_VTp, Cmp_Fn, _Alloc, false>
       {
       private:
-	typedef typename _Alloc::template rebind<_VTp>		__rebind_v;
+	typedef rebind_traits<_Alloc, _VTp>		__rebind_v;
 
       public:
-	typedef typename __rebind_v::other::const_pointer	entry;
+	typedef typename __rebind_v::const_pointer	entry;
 
 	/// Compare plus entry.
 	struct type : public Cmp_Fn
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp
index 1ad0d79..3f15875 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/entry_pred.hpp
@@ -61,10 +61,10 @@ namespace __gnu_pbds
       struct entry_pred<_VTp, Pred, _Alloc, false>
       {
       private:
-	typedef typename _Alloc::template rebind<_VTp>		__rebind_v;
+	typedef rebind_traits<_Alloc, _VTp>		__rebind_v;
 
       public:
-	typedef typename __rebind_v::other::const_pointer	entry;
+	typedef typename __rebind_v::const_pointer	entry;
 
 	struct type : public Pred
 	{
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp
index 15c89a6..bb39b9b0 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/point_const_iterator.hpp
@@ -55,7 +55,7 @@ namespace __gnu_pbds
     class binary_heap_point_const_iterator_
     {
     protected:
-      typedef typename _Alloc::template rebind<Entry>::other::pointer entry_pointer;
+      typedef typename rebind_traits<_Alloc, Entry>::pointer entry_pointer;
 
     public:
       /// Category.
@@ -68,23 +68,19 @@ namespace __gnu_pbds
       typedef Value_Type value_type;
 
       /// Iterator's pointer type.
-      typedef typename _Alloc::template rebind<value_type>::other::pointer
-      pointer;
+      typedef typename rebind_traits<_Alloc, value_type>::pointer pointer;
 
       /// Iterator's const pointer type.
-      typedef
-      typename _Alloc::template rebind<value_type>::other::const_pointer
-      const_pointer;
+      typedef typename rebind_traits<_Alloc, value_type>::const_pointer
+	const_pointer;
 
       /// Iterator's reference type.
-      typedef
-      typename _Alloc::template rebind<value_type>::other::reference
-      reference;
+      typedef typename rebind_traits<_Alloc, value_type>::reference
+	reference;
 
       /// Iterator's const reference type.
-      typedef
-      typename _Alloc::template rebind<value_type>::other::const_reference
-      const_reference;
+      typedef typename rebind_traits<_Alloc, value_type>::const_reference
+	const_reference;
 
       inline
       binary_heap_point_const_iterator_(entry_pointer p_e) : m_p_e(p_e)
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 306950d..d8c2d35 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
@@ -78,7 +78,7 @@ namespace __gnu_pbds
     : public PB_DS_B_HEAP_BASE
     {
     private:
-      typedef typename _Alloc::template rebind<Value_Type>::other __rebind_v;
+      typedef rebind_traits<_Alloc, Value_Type>		__rebind_v;
       typedef PB_DS_B_HEAP_BASE	  			base_type;
 
     protected:
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp b/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp
index 04cfb33..38f60c2 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/branch_policy/branch_policy.hpp
@@ -42,6 +42,7 @@
 #define PB_DS_BRANCH_POLICY_BASE_HPP
 
 #include <ext/pb_ds/tag_and_trait.hpp>
+#include <ext/pb_ds/detail/types_traits.hpp>
 
 namespace __gnu_pbds
 {
@@ -59,8 +60,8 @@ namespace __gnu_pbds
 	typedef typename remove_const<value_type>::type	rcvalue_type;
 	typedef typename remove_const<key_type>::type	rckey_type;
 
-	typedef typename _Alloc::template rebind<rcvalue_type>::other rebind_v;
-	typedef typename _Alloc::template rebind<rckey_type>::other   rebind_k;
+	typedef rebind_traits<_Alloc, rcvalue_type>	rebind_v;
+	typedef rebind_traits<_Alloc, rckey_type>	rebind_k;
 
 	typedef	typename rebind_v::reference 		reference;
 	typedef	typename rebind_v::const_reference 	const_reference;
@@ -91,7 +92,7 @@ namespace __gnu_pbds
 	typedef typename Node_CItr::value_type 		   it_type;
        	typedef typename std::iterator_traits<it_type>::value_type value_type;
 	typedef typename remove_const<value_type>::type		   rcvalue_type;
-	typedef typename _Alloc::template rebind<rcvalue_type>::other rebind_v;
+	typedef rebind_traits<_Alloc, rcvalue_type>	rebind_v;
 	typedef	typename rebind_v::reference 		reference;
 	typedef	typename rebind_v::const_reference 	const_reference;
 	typedef	typename rebind_v::const_pointer	const_pointer;
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 1a6affc..93006fb 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
@@ -40,6 +40,7 @@
 
 #include <utility>
 #include <iterator>
+#include <memory>
 #include <ext/pb_ds/detail/cond_dealtor.hpp>
 #include <ext/pb_ds/tag_and_trait.hpp>
 #include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp>
@@ -73,7 +74,7 @@ namespace __gnu_pbds
 
 #define PB_DS_CLASS_C_DEC \
     PB_DS_CC_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc,	\
-		     Store_Hash, Comb_Hash_Fn, Resize_Policy>
+		       Store_Hash, Comb_Hash_Fn, Resize_Policy>
 
 #define PB_DS_HASH_EQ_FN_C_DEC \
     hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash>
@@ -87,7 +88,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
     debug_map_base<Key,	Eq_Fn, \
-		  typename _Alloc::template rebind<Key>::other::const_reference>
+		   typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
 
@@ -135,7 +136,7 @@ namespace __gnu_pbds
 	     typename _Alloc,
 	     bool Store_Hash,
 	     typename Comb_Hash_Fn,
-	     typename Resize_Policy >
+	     typename Resize_Policy>
     class PB_DS_CC_HASH_NAME:
 #ifdef _GLIBCXX_DEBUG
       protected PB_DS_DEBUG_MAP_BASE_C_DEC,
@@ -156,19 +157,21 @@ namespace __gnu_pbds
 
       struct entry : public traits_base::stored_data_type
       {
-	typename _Alloc::template rebind<entry>::other::pointer m_p_next;
+	typename rebind_traits<_Alloc, entry>::pointer m_p_next;
       };
 
       typedef cond_dealtor<entry, _Alloc> 	cond_dealtor_t;
 
-      typedef typename _Alloc::template rebind<entry>::other entry_allocator;
-      typedef typename entry_allocator::pointer entry_pointer;
-      typedef typename entry_allocator::const_pointer const_entry_pointer;
-      typedef typename entry_allocator::reference entry_reference;
-      typedef typename entry_allocator::const_reference const_entry_reference;
+      typedef rebind_traits<_Alloc, entry> entry_traits;
+      typedef typename entry_traits::allocator_type entry_allocator;
+      typedef typename entry_traits::pointer entry_pointer;
+      typedef typename entry_traits::const_pointer const_entry_pointer;
+      typedef typename entry_traits::reference entry_reference;
+      typedef typename entry_traits::const_reference const_entry_reference;
 
-      typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
-      typedef typename entry_pointer_allocator::pointer entry_pointer_array;
+      typedef rebind_traits<_Alloc, entry_pointer> entry_pointer_traits;
+      typedef typename entry_pointer_traits::allocator_type entry_pointer_allocator;
+      typedef typename entry_pointer_traits::pointer entry_pointer_array;
 
       typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base;
       typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/cond_dealtor.hpp b/libstdc++-v3/include/ext/pb_ds/detail/cond_dealtor.hpp
index b92aa26..89766e3 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/cond_dealtor.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/cond_dealtor.hpp
@@ -41,6 +41,8 @@
 #ifndef PB_DS_COND_DEALTOR_HPP
 #define PB_DS_COND_DEALTOR_HPP
 
+#include <ext/pb_ds/detail/types_traits.hpp>
+
 namespace __gnu_pbds
 {
   namespace detail
@@ -49,11 +51,11 @@ namespace __gnu_pbds
     template<typename Entry, typename _Alloc>
       class cond_dealtor
       {
-	typedef typename _Alloc::template rebind<Entry>	__rebind_e;
+	typedef rebind_traits<_Alloc, Entry>	alloc_traits;
 
       public:
-	typedef typename __rebind_e::other 		entry_allocator;
-	typedef typename entry_allocator::pointer 	entry_pointer;
+	typedef typename alloc_traits::allocator_type entry_allocator;
+	typedef typename alloc_traits::pointer	      entry_pointer;
 
 	cond_dealtor(entry_pointer p_e)
 	: m_p_e(p_e), m_no_action_destructor(false) { }
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp
index 85d4a8a..240493c 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp
@@ -35,7 +35,7 @@
 
 /**
  * @file hash_eq_fn.hpp
- * Contains 2 eqivalence functions, one employing a hash value,
+ * Contains 2 equivalence functions, one employing a hash value,
  * and one ignoring it.
  */
 
@@ -43,6 +43,7 @@
 #define PB_DS_HASH_EQ_FN_HPP
 
 #include <utility>
+#include <ext/pb_ds/detail/types_traits.hpp>
 #include <debug/debug.h>
 
 namespace __gnu_pbds
@@ -58,8 +59,8 @@ namespace __gnu_pbds
     struct hash_eq_fn<Key, Eq_Fn, _Alloc, false> : public Eq_Fn
     {
       typedef Eq_Fn 					   eq_fn_base;
-      typedef typename _Alloc::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference 	   key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       hash_eq_fn() { }
 
@@ -82,8 +83,8 @@ namespace __gnu_pbds
     {
       typedef typename _Alloc::size_type 		   size_type;
       typedef Eq_Fn 					   eq_fn_base;
-      typedef typename _Alloc::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference 	   key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       hash_eq_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 90dfd50..c1cb552 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
@@ -85,7 +85,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
    debug_map_base<Key, Eq_Fn, \
-		  typename _Alloc::template rebind<Key>::other::const_reference>
+		  typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
 
@@ -169,12 +169,13 @@ namespace __gnu_pbds
 	entry_status m_stat;
       };
 
-      typedef typename _Alloc::template rebind<entry>::other entry_allocator;
-      typedef typename entry_allocator::pointer entry_pointer;
-      typedef typename entry_allocator::const_pointer const_entry_pointer;
-      typedef typename entry_allocator::reference entry_reference;
-      typedef typename entry_allocator::const_reference const_entry_reference;
-      typedef typename entry_allocator::pointer entry_array;
+      typedef rebind_traits<_Alloc, entry> entry_traits;
+      typedef typename entry_traits::allocator_type entry_allocator;
+      typedef typename entry_traits::pointer entry_pointer;
+      typedef typename entry_traits::const_pointer const_entry_pointer;
+      typedef typename entry_traits::reference entry_reference;
+      typedef typename entry_traits::const_reference const_entry_reference;
+      typedef typename entry_traits::pointer entry_array;
 
       typedef PB_DS_RANGED_PROBE_FN_C_DEC 	ranged_probe_fn_base;
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
index 7d0185ee..4724f7d 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp
@@ -43,6 +43,7 @@
 #define PB_DS_RANGED_HASH_FN_HPP
 
 #include <utility>
+#include <ext/pb_ds/detail/types_traits.hpp>
 #include <debug/debug.h>
 
 namespace __gnu_pbds
@@ -75,8 +76,8 @@ namespace __gnu_pbds
       typedef typename _Alloc::size_type size_type;
       typedef Hash_Fn hash_fn_base;
       typedef Comb_Hash_Fn comb_hash_fn_base;
-      typedef typename _Alloc::template rebind< Key>::other key_allocator;
-      typedef typename key_allocator::const_reference key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       ranged_hash_fn(size_type);
 
@@ -158,8 +159,8 @@ namespace __gnu_pbds
       typedef std::pair<size_type, size_type> comp_hash;
       typedef Hash_Fn hash_fn_base;
       typedef Comb_Hash_Fn comb_hash_fn_base;
-      typedef typename _Alloc::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       ranged_hash_fn(size_type);
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
index 6a8eb59..3390411 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/hash_fn/ranged_probe_fn.hpp
@@ -77,8 +77,8 @@ namespace __gnu_pbds
       typedef Comb_Probe_Fn comb_probe_fn_base;
       typedef Hash_Fn hash_fn_base;
       typedef Probe_Fn probe_fn_base;
-      typedef typename _Alloc::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       ranged_probe_fn(size_type);
 
@@ -183,8 +183,8 @@ namespace __gnu_pbds
       typedef Comb_Probe_Fn comb_probe_fn_base;
       typedef Hash_Fn hash_fn_base;
       typedef Probe_Fn probe_fn_base;
-      typedef typename _Alloc::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       ranged_probe_fn(size_type);
 
@@ -300,8 +300,8 @@ namespace __gnu_pbds
     protected:
       typedef typename _Alloc::size_type size_type;
       typedef Comb_Probe_Fn comb_probe_fn_base;
-      typedef typename _Alloc::template rebind<Key>::other key_allocator;
-      typedef typename key_allocator::const_reference key_const_reference;
+      typedef typename rebind_traits<_Alloc, Key>::const_reference
+	key_const_reference;
 
       ranged_probe_fn(size_type size)
       { Comb_Probe_Fn::notify_resized(size); }
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 32d67eb..5e80258 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
@@ -89,18 +89,21 @@ namespace __gnu_pbds
 #endif
     class left_child_next_sibling_heap : public Cmp_Fn
     {
-    protected:
+    public:
       typedef
-      typename _Alloc::template rebind<
-      left_child_next_sibling_heap_node_<Value_Type, Node_Metadata,
-					 _Alloc> >::other
-      node_allocator;
-
-      typedef typename node_allocator::value_type     	node;
-      typedef typename node_allocator::pointer 		node_pointer;
-      typedef typename node_allocator::const_pointer	node_const_pointer;
+	left_child_next_sibling_heap_node_<Value_Type, Node_Metadata, _Alloc>
+	node;
+
+    private:
+      typedef typename detail::rebind_traits<_Alloc, node> alloc_traits;
+
+    protected:
+      typedef typename alloc_traits::allocator_type node_allocator;
+
+      typedef typename alloc_traits::pointer 		node_pointer;
+      typedef typename alloc_traits::const_pointer	node_const_pointer;
       typedef Node_Metadata node_metadata;
-      typedef std::pair< node_pointer, node_pointer> 	node_pointer_pair;
+      typedef std::pair<node_pointer, node_pointer> 	node_pointer_pair;
 
     private:
       typedef cond_dealtor< node, _Alloc> 		cond_dealtor_t;
@@ -111,17 +114,17 @@ namespace __gnu_pbds
 	};
 
       typedef integral_constant<int, simple_value> 	no_throw_copies_t;
-      typedef typename _Alloc::template rebind<Value_Type>	__rebind_v;
+      typedef rebind_traits<_Alloc, Value_Type>	__rebind_v;
 
     public:
       typedef typename _Alloc::size_type 		size_type;
       typedef typename _Alloc::difference_type 	difference_type;
       typedef Value_Type 				value_type;
 
-      typedef typename __rebind_v::other::pointer 	pointer;
-      typedef typename __rebind_v::other::const_pointer const_pointer;
-      typedef typename __rebind_v::other::reference	reference;
-      typedef typename __rebind_v::other::const_reference const_reference;
+      typedef typename __rebind_v::pointer 	pointer;
+      typedef typename __rebind_v::const_pointer const_pointer;
+      typedef typename __rebind_v::reference	reference;
+      typedef typename __rebind_v::const_reference const_reference;
 
       typedef left_child_next_sibling_heap_node_point_const_iterator_<node, _Alloc>
       point_const_iterator;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp
index 4a7746c..9dd36a3 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp
@@ -41,6 +41,8 @@
 #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_HPP
 #define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_HPP
 
+#include <ext/pb_ds/detail/types_traits.hpp>
+
 namespace __gnu_pbds
 {
   namespace detail
@@ -57,7 +59,7 @@ namespace __gnu_pbds
       typedef typename _Alloc::size_type 	size_type;
       typedef _Metadata 			metadata_type;
 
-      typedef typename _Alloc::template rebind<this_type>::other::pointer node_pointer;
+      typedef typename rebind_traits<_Alloc, this_type>::pointer node_pointer;
 
       value_type 	m_value;
       metadata_type 	m_metadata;
@@ -76,7 +78,7 @@ namespace __gnu_pbds
       typedef _Value 				value_type;
       typedef typename _Alloc::size_type 	size_type;
 
-      typedef typename _Alloc::template rebind<this_type>::other::pointer node_pointer;
+      typedef typename rebind_traits<_Alloc, this_type>::pointer node_pointer;
 
       value_type 	m_value;
       node_pointer 	m_p_l_child;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp
index 4ec381d..bb6d3dc 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/left_child_next_sibling_heap_/point_const_iterator.hpp
@@ -61,7 +61,7 @@ namespace __gnu_pbds
     class left_child_next_sibling_heap_node_point_const_iterator_
     {
     protected:
-      typedef typename _Alloc::template rebind<Node>::other::pointer node_pointer;
+      typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer;
 
     public:
       /// Category.
@@ -74,28 +74,18 @@ namespace __gnu_pbds
       typedef typename Node::value_type value_type;
 
       /// Iterator's pointer type.
-      typedef
-      typename _Alloc::template rebind<
-	value_type>::other::pointer
-      pointer;
+      typedef typename rebind_traits<_Alloc, value_type>::pointer pointer;
 
       /// Iterator's const pointer type.
-      typedef
-      typename _Alloc::template rebind<
-	value_type>::other::const_pointer
-      const_pointer;
+      typedef typename rebind_traits<_Alloc, value_type>::const_pointer
+	const_pointer;
 
       /// Iterator's reference type.
-      typedef
-      typename _Alloc::template rebind<
-	value_type>::other::reference
-      reference;
+      typedef typename rebind_traits<_Alloc, value_type>::reference reference;
 
       /// Iterator's const reference type.
-      typedef
-      typename _Alloc::template rebind<
-	value_type>::other::const_reference
-      const_reference;
+      typedef typename rebind_traits<_Alloc, value_type>::const_reference
+	const_reference;
 
       inline
       left_child_next_sibling_heap_node_point_const_iterator_(node_pointer p_nd) : m_p_nd(p_nd)
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 a3c0fb4..9f56176 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
@@ -78,7 +78,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
     debug_map_base<Key, Eq_Fn, \
-	      typename _Alloc::template rebind<Key>::other::const_reference>
+		   typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
     /// list-based (with updates) associative container.
@@ -101,17 +101,19 @@ namespace __gnu_pbds
      : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
       {
 	typename traits_base::value_type m_value;
-	typename _Alloc::template rebind<entry>::other::pointer m_p_next;
+	typename rebind_traits<_Alloc, entry>::pointer m_p_next;
       };
 
-      typedef typename _Alloc::template rebind<entry>::other entry_allocator;
-      typedef typename entry_allocator::pointer entry_pointer;
-      typedef typename entry_allocator::const_pointer const_entry_pointer;
-      typedef typename entry_allocator::reference entry_reference;
-      typedef typename entry_allocator::const_reference const_entry_reference;
+      typedef rebind_traits<_Alloc, entry>		  entry_alloc_traits;
+      typedef typename entry_alloc_traits::allocator_type entry_allocator;
+      typedef typename entry_alloc_traits::pointer	  entry_pointer;
+      typedef typename entry_alloc_traits::const_pointer  const_entry_pointer;
+      typedef typename entry_alloc_traits::reference	  entry_reference;
+      typedef typename entry_alloc_traits::const_reference const_entry_reference;
 
-      typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
-      typedef typename entry_pointer_allocator::pointer entry_pointer_array;
+      typedef rebind_traits<_Alloc, entry_pointer>	entry_pointer_alloc_traits;
+      typedef typename entry_pointer_alloc_traits::allocator_type entry_pointer_allocator;
+      typedef typename entry_pointer_alloc_traits::pointer entry_pointer_array;
 
       typedef typename traits_base::value_type value_type_;
       typedef typename traits_base::pointer pointer_;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
index e081392..57a284a 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp
@@ -103,11 +103,11 @@ copy_from_range(It first_it, It last_it)
 {
 #ifdef PB_DS_DATA_TRUE_INDICATOR
   typedef std::map<key_type, mapped_type, Cmp_Fn,
-		   typename _Alloc::template rebind<value_type>::other>
+		   typename rebind_traits<_Alloc, value_type>::allocator_type>
     map_type;
 #else
   typedef std::set<key_type, Cmp_Fn,
-		   typename _Alloc::template rebind<Key>::other>
+		   typename rebind_traits<_Alloc, Key>::allocator_type>
     map_type;
 #endif
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp
index 2427cbc..e45d3a7 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp
@@ -58,20 +58,14 @@ namespace __gnu_pbds
     {
 
     protected:
-      typedef
-      typename _Alloc::template rebind<
-      Value_Type>::other::pointer
-      pointer;
+      typedef typename rebind_traits<_Alloc, Value_Type>::pointer
+	pointer;
 
-      typedef
-      typename _Alloc::template rebind<
-	Value_Type>::other::const_pointer
-      const_pointer;
+      typedef typename rebind_traits<_Alloc, Value_Type>::const_pointer
+	const_pointer;
 
-      typedef
-      typename _Alloc::template rebind<
-	Metadata_Type>::other::const_pointer
-      const_metadata_pointer;
+      typedef typename rebind_traits<_Alloc, Metadata_Type>::const_pointer
+	const_metadata_pointer;
 
       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type;
 
@@ -91,33 +85,32 @@ namespace __gnu_pbds
 
       typedef trivial_iterator_difference_type difference_type;
 
-      typedef
-      typename _Alloc::template rebind<
-	Value_Type>::other::const_pointer
-      value_type;
+      typedef typename rebind_traits<_Alloc, Value_Type>::const_pointer
+	value_type;
 
-      typedef
-      typename _Alloc::template rebind<
-	typename remove_const<
-	Value_Type>::type>::other::const_pointer
-      reference;
+      typedef typename rebind_traits<_Alloc,
+	      typename remove_const<Value_Type>::type>::const_pointer
+	reference;
 
-      typedef
-      typename _Alloc::template rebind<
-	typename remove_const<
-	Value_Type>::type>::other::const_pointer
-      const_reference;
+      typedef typename rebind_traits<_Alloc, 
+	      typename remove_const<Value_Type>::type>::const_pointer
+	const_reference;
 
       typedef Metadata_Type metadata_type;
 
-      typedef
-      typename _Alloc::template rebind<
-	metadata_type>::other::const_reference
-      metadata_const_reference;
+      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference
+	metadata_const_reference;
 
     public:
       inline
-      ov_tree_node_const_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata)
+      ov_tree_node_const_it_(const_pointer p_nd = 0,
+			     const_pointer p_begin_nd = 0,
+			     const_pointer p_end_nd = 0,
+			     const_metadata_pointer p_metadata = 0)
+      : m_p_value(const_cast<pointer>(p_nd)),
+	m_p_begin_value(const_cast<pointer>(p_begin_nd)),
+	m_p_end_value(const_cast<pointer>(p_end_nd)),
+	m_p_metadata(p_metadata)
       { }
 
       inline const_reference
@@ -221,22 +214,16 @@ namespace __gnu_pbds
 
       typedef trivial_iterator_difference_type difference_type;
 
-      typedef
-      typename _Alloc::template rebind<
-	Value_Type>::other::pointer
-      value_type;
+      typedef typename rebind_traits<_Alloc, Value_Type>::pointer
+	value_type;
 
-      typedef
-      typename _Alloc::template rebind<
-	typename remove_const<
-	Value_Type>::type>::other::pointer
-      reference;
+      typedef typename rebind_traits<_Alloc,
+	      typename remove_const<Value_Type>::type>::pointer
+	reference;
 
-      typedef
-      typename _Alloc::template rebind<
-	typename remove_const<
-	Value_Type>::type>::other::pointer
-      const_reference;
+      typedef typename rebind_traits<_Alloc, 
+	      typename remove_const<Value_Type>::type>::pointer
+	const_reference;
 
       inline
       ov_tree_node_it_(const_pointer p_nd = 0,  const_pointer p_begin_nd = 0,  const_pointer p_end_nd = 0,  const_metadata_pointer p_metadata = 0) : base_type(p_nd,  p_begin_nd,  p_end_nd,  p_metadata)
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 0859da1..b601031 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
@@ -83,7 +83,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
     debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
-       	typename _Alloc::template rebind<Key>::other::const_reference>
+		   typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
 #ifdef PB_DS_TREE_TRACE
@@ -120,8 +120,9 @@ namespace __gnu_pbds
 
       typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
 
-      typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator;
-      typedef typename value_allocator::pointer 	value_vector;
+      typedef rebind_traits<_Alloc, non_const_value_type> value_alloc_traits;
+      typedef typename value_alloc_traits::allocator_type value_allocator;
+      typedef typename value_alloc_traits::pointer	  value_vector;
 
 #ifdef _GLIBCXX_DEBUG
       typedef PB_DS_DEBUG_MAP_BASE_C_DEC 		debug_base;
@@ -136,16 +137,17 @@ namespace __gnu_pbds
 
       typedef typename traits_type::metadata_type 	metadata_type;
 
-      typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator;
-      typedef typename metadata_allocator::pointer 	metadata_pointer;
-      typedef typename metadata_allocator::const_reference metadata_const_reference;
-      typedef typename metadata_allocator::reference 	metadata_reference;
+      typedef rebind_traits<_Alloc, metadata_type>	metadata_alloc_traits;
+      typedef typename metadata_alloc_traits::allocator_type metadata_allocator;
+      typedef typename metadata_alloc_traits::pointer	metadata_pointer;
+      typedef typename metadata_alloc_traits::const_reference metadata_const_reference;
+      typedef typename metadata_alloc_traits::reference	metadata_reference;
 
       typedef typename traits_type::null_node_update_pointer
       null_node_update_pointer;
 
     public:
-      typedef ov_tree_tag 				 container_category;
+      typedef ov_tree_tag 				container_category;
       typedef _Alloc 					allocator_type;
       typedef typename _Alloc::size_type 		size_type;
       typedef typename _Alloc::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 ccf45388..e9fb0b3 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
@@ -80,7 +80,7 @@ namespace __gnu_pbds
       typedef PB_DS_P_HEAP_BASE				base_type;
       typedef typename base_type::node_pointer 		node_pointer;
 
-      typedef typename _Alloc::template rebind<Value_Type>::other __rebind_a;
+      typedef rebind_traits<_Alloc, Value_Type>		__rebind_a;
 
     public:
       typedef Value_Type 				value_type;
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 3f7e054..2da3858 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
@@ -83,7 +83,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
     debug_map_base<Key,	eq_by_less<Key, std::less<Key> >, \
-		 typename _Alloc::template rebind<Key>::other::const_reference>
+		 typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
 
@@ -109,35 +109,34 @@ namespace __gnu_pbds
     {
     private:
       typedef pat_trie_base				base_type;
-      typedef PB_DS_PAT_TRIE_TRAITS_BASE 	       	traits_base;
+      typedef PB_DS_PAT_TRIE_TRAITS_BASE 		traits_base;
       typedef Node_And_It_Traits			traits_type;
 
       typedef typename traits_type::synth_access_traits synth_access_traits;
       typedef typename synth_access_traits::const_iterator a_const_iterator;
 
-      typedef typename traits_type::node 		node;
-      typedef typename _Alloc::template rebind<node>	__rebind_n;
-      typedef typename __rebind_n::other::const_pointer node_const_pointer;
-      typedef typename __rebind_n::other::pointer 	node_pointer;
+      typedef typename traits_type::node		node;
+      typedef rebind_traits<_Alloc, node>		__rebind_n;
+      typedef typename __rebind_n::const_pointer	node_const_pointer;
+      typedef typename __rebind_n::pointer		node_pointer;
 
-      typedef typename traits_type::head 		head;
-      typedef typename _Alloc::template rebind<head>	__rebind_h;
-      typedef typename __rebind_h::other 		head_allocator;
-      typedef typename head_allocator::pointer 		head_pointer;
+      typedef typename traits_type::head		head;
+      typedef rebind_traits<_Alloc, head>		__rebind_h;
+      typedef typename __rebind_h::allocator_type 	head_allocator;
+      typedef typename __rebind_h::pointer 		head_pointer;
 
-      typedef typename traits_type::leaf 		leaf;
-      typedef typename _Alloc::template rebind<leaf>	__rebind_l;
-      typedef typename __rebind_l::other 		leaf_allocator;
-      typedef typename leaf_allocator::pointer 		leaf_pointer;
-      typedef typename leaf_allocator::const_pointer 	leaf_const_pointer;
+      typedef typename traits_type::leaf		leaf;
+      typedef rebind_traits<_Alloc, leaf>		__rebind_l;
+      typedef typename __rebind_l::allocator_type	leaf_allocator;
+      typedef typename __rebind_l::pointer 		leaf_pointer;
+      typedef typename __rebind_l::const_pointer	leaf_const_pointer;
 
-      typedef typename traits_type::inode 		inode;
+      typedef typename traits_type::inode		inode;
       typedef typename inode::iterator 			inode_iterator;
-      typedef typename _Alloc::template rebind<inode> 	__rebind_in;
-      typedef typename __rebind_in::other 		__rebind_ina;
-      typedef typename __rebind_in::other      	       	inode_allocator;
-      typedef typename __rebind_ina::pointer 		inode_pointer;
-      typedef typename __rebind_ina::const_pointer 	inode_const_pointer;
+      typedef rebind_traits<_Alloc, inode>		__rebind_in;
+      typedef typename __rebind_in::allocator_type	inode_allocator;
+      typedef typename __rebind_in::pointer 		inode_pointer;
+      typedef typename __rebind_in::const_pointer	inode_const_pointer;
 
 
       /// Conditional deallocator.
@@ -179,7 +178,8 @@ namespace __gnu_pbds
       {
       private:
 	typedef inode_pointer 			       	__inp;
-	typedef typename _Alloc::template rebind<__inp>::other 	__rebind_inp;
+	typedef typename rebind_traits<_Alloc, __inp>::allocator_type
+	  __rebind_inp;
 
 #ifdef _GLIBCXX_DEBUG
 	typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> 	bag_type;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
index cf610cb..b9d71c7 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp
@@ -68,8 +68,8 @@ namespace __gnu_pbds
 	{
 	  typedef Metadata     					metadata_type;
 	  typedef _Alloc     					allocator_type;
-	  typedef typename _Alloc::template rebind<Metadata>	__rebind_m;
-	  typedef typename __rebind_m::other::const_reference  const_reference;
+	  typedef typename detail::rebind_traits<_Alloc, Metadata>::const_reference
+	    const_reference;
 
 	  const_reference
 	  get_metadata() const
@@ -99,8 +99,8 @@ namespace __gnu_pbds
 	typedef _Alloc						allocator_type;
 	typedef _ATraits					access_traits;
 	typedef typename _ATraits::type_traits			type_traits;
-	typedef typename _Alloc::template rebind<_Node_base>	__rebind_n;
-	typedef typename __rebind_n::other::pointer 		node_pointer;
+	typedef typename detail::rebind_traits<_Alloc, _Node_base>::pointer
+	  node_pointer;
 
 	node_pointer 						m_p_parent;
 	const node_type 	       				m_type;
@@ -108,8 +108,8 @@ namespace __gnu_pbds
 	_Node_base(node_type type) : m_type(type)
 	{ }
 
-	typedef typename _Alloc::template rebind<_ATraits>    __rebind_at;
-	typedef typename __rebind_at::other::const_pointer    a_const_pointer;
+	typedef typename detail::rebind_traits<_Alloc, _ATraits>::const_pointer
+	  a_const_pointer;
 	typedef typename _ATraits::const_iterator	      a_const_iterator;
 
 #ifdef _GLIBCXX_DEBUG
@@ -211,36 +211,36 @@ namespace __gnu_pbds
     struct _Inode
     : public _Node_base<_ATraits, Metadata>
     {
-      typedef _Node_base<_ATraits, Metadata> 			base_type;
-      typedef typename base_type::type_traits			type_traits;
-      typedef typename base_type::access_traits	       		access_traits;
-      typedef typename type_traits::value_type 			value_type;
-      typedef typename base_type::allocator_type		_Alloc;
-      typedef _Alloc						allocator_type;
-      typedef typename _Alloc::size_type 			size_type;
+      typedef _Node_base<_ATraits, Metadata>		base_type;
+      typedef typename base_type::type_traits		type_traits;
+      typedef typename base_type::access_traits		access_traits;
+      typedef typename type_traits::value_type		value_type;
+      typedef typename base_type::allocator_type	_Alloc;
+      typedef _Alloc					allocator_type;
+      typedef typename _Alloc::size_type		size_type;
 
     private:
-      typedef typename base_type::a_const_pointer      	       a_const_pointer;
-      typedef typename base_type::a_const_iterator     	      a_const_iterator;
+      typedef typename base_type::a_const_pointer	a_const_pointer;
+      typedef typename base_type::a_const_iterator	a_const_iterator;
 
-      typedef typename base_type::node_pointer			node_pointer;
-      typedef typename _Alloc::template rebind<base_type>	__rebind_n;
-      typedef typename __rebind_n::other::const_pointer      node_const_pointer;
+      typedef typename base_type::node_pointer		node_pointer;
+      typedef typename detail::rebind_traits<_Alloc, base_type>::const_pointer
+	node_const_pointer;
 
-      typedef _Leaf<_ATraits, Metadata>	 			leaf;
-      typedef typename _Alloc::template rebind<leaf>::other 	__rebind_l;
-      typedef typename __rebind_l::pointer 			leaf_pointer;
-      typedef typename __rebind_l::const_pointer 	    leaf_const_pointer;
+      typedef _Leaf<_ATraits, Metadata>	 		leaf;
+      typedef typename detail::rebind_traits<_Alloc, leaf>	__rebind_l;
+      typedef typename __rebind_l::pointer 		leaf_pointer;
+      typedef typename __rebind_l::const_pointer 	leaf_const_pointer;
 
-      typedef typename _Alloc::template rebind<_Inode>::other 	__rebind_in;
-      typedef typename __rebind_in::pointer 			inode_pointer;
-      typedef typename __rebind_in::const_pointer 	    inode_const_pointer;
+      typedef detail::rebind_traits<_Alloc, _Inode>	__rebind_in;
+      typedef typename __rebind_in::pointer		inode_pointer;
+      typedef typename __rebind_in::const_pointer 	inode_const_pointer;
 
       inline size_type
       get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer) const;
 
     public:
-      typedef typename _Alloc::template rebind<node_pointer>::other __rebind_np;
+      typedef detail::rebind_traits<_Alloc, node_pointer>	__rebind_np;
       typedef typename __rebind_np::pointer 		node_pointer_pointer;
       typedef typename __rebind_np::reference 		node_pointer_reference;
 
@@ -500,16 +500,12 @@ namespace __gnu_pbds
       typedef typename type_traits::const_reference 	const_reference;
 
       typedef allocator_type				_Alloc;
-      typedef typename _Alloc::template rebind<Node>	__rebind_n;
-      typedef typename __rebind_n::other::pointer	node_pointer;
-      typedef typename _Alloc::template rebind<Leaf>	__rebind_l;
-      typedef typename __rebind_l::other::pointer	leaf_pointer;
-      typedef typename __rebind_l::other::const_pointer	leaf_const_pointer;
-      typedef typename _Alloc::template rebind<Head>	__rebind_h;
-      typedef typename __rebind_h::other::pointer	head_pointer;
-
-      typedef typename _Alloc::template rebind<Inode> __rebind_in;
-      typedef typename __rebind_in::other::pointer 	inode_pointer;
+      typedef typename rebind_traits<_Alloc, Node>::pointer	node_pointer;
+      typedef typename rebind_traits<_Alloc, Leaf>::pointer	leaf_pointer;
+      typedef typename rebind_traits<_Alloc, Leaf>::const_pointer	leaf_const_pointer;
+      typedef typename rebind_traits<_Alloc, Head>::pointer	head_pointer;
+
+      typedef typename rebind_traits<_Alloc, Inode>::pointer 	inode_pointer;
       typedef typename Inode::iterator			inode_iterator;
 
       node_pointer 					m_p_nd;
@@ -814,16 +810,13 @@ namespace __gnu_pbds
     class _Node_citer
     {
     protected:
-      typedef typename _Alloc::template rebind<Node>	__rebind_n;
-      typedef typename __rebind_n::other::pointer	node_pointer;
+      typedef typename rebind_traits<_Alloc, Node>::pointer	node_pointer;
 
-      typedef typename _Alloc::template rebind<Leaf>	__rebind_l;
-      typedef typename __rebind_l::other::pointer	leaf_pointer;
-      typedef typename __rebind_l::other::const_pointer	leaf_const_pointer;
+      typedef typename rebind_traits<_Alloc, Leaf>::pointer	leaf_pointer;
+      typedef typename rebind_traits<_Alloc, Leaf>::const_pointer	leaf_const_pointer;
 
-      typedef typename _Alloc::template rebind<Inode> 	__rebind_in;
-      typedef typename __rebind_in::other::pointer 	inode_pointer;
-      typedef typename __rebind_in::other::const_pointer inode_const_pointer;
+      typedef typename rebind_traits<_Alloc, Inode>::pointer 	inode_pointer;
+      typedef typename rebind_traits<_Alloc, Inode>::const_pointer inode_const_pointer;
 
       typedef typename Node::a_const_pointer		a_const_pointer;
       typedef typename Node::a_const_iterator		a_const_iterator;
@@ -866,9 +859,7 @@ namespace __gnu_pbds
       typedef typename Node::metadata_type 		metadata_type;
 
       /// Const metadata reference type.
-      typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
-      typedef typename __rebind_m::other 		__rebind_ma;
-      typedef typename __rebind_ma::const_reference    metadata_const_reference;
+      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference    metadata_const_reference;
 
       inline
       _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0)
@@ -946,8 +937,7 @@ namespace __gnu_pbds
     private:
       typedef _Node_citer<Node, Leaf, Head, Inode,
 			  _CIterator, Iterator, _Alloc>	base_type;
-      typedef typename _Alloc::template rebind<Node>	__rebind_n;
-      typedef typename __rebind_n::other::pointer	node_pointer;
+      typedef typename rebind_traits<_Alloc, Node>::pointer	node_pointer;
       typedef typename base_type::inode_pointer 	inode_pointer;
       typedef typename base_type::a_const_pointer 	a_const_pointer;
       typedef Iterator 					iterator;
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
index 7271e18..b2330fa 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
@@ -55,23 +55,14 @@ namespace __gnu_pbds
       typedef Value_Type 		value_type;
       typedef Metadata 			metadata_type;
 
-      typedef
-      typename _Alloc::template rebind<
-      rb_tree_node_<
-      Value_Type,
-      Metadata,
-      _Alloc> >::other::pointer
-      node_pointer;
-
-      typedef
-      typename _Alloc::template rebind<
-	metadata_type>::other::reference
-      metadata_reference;
-
-      typedef
-      typename _Alloc::template rebind<
-	metadata_type>::other::const_reference
-      metadata_const_reference;
+      typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer
+	node_pointer;
+
+      typedef typename rebind_traits<_Alloc, metadata_type>::reference
+	metadata_reference;
+
+      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference
+	metadata_const_reference;
 
       bool
       special() const
@@ -109,13 +100,8 @@ namespace __gnu_pbds
       typedef Value_Type 		value_type;
       typedef null_type 	metadata_type;
 
-      typedef
-      typename _Alloc::template rebind<
-      rb_tree_node_<
-      Value_Type,
-      null_type,
-      _Alloc> >::other::pointer
-      node_pointer;
+      typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer
+	node_pointer;
 
       bool
       special() const
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 5c996d1..0cf81a7 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
@@ -54,13 +54,13 @@ namespace __gnu_pbds
       typedef typename allocator_type::size_type 	 size_type;
       typedef _Node 					 node;
 
-      typedef typename _Alloc::template rebind<node>	 __rebind_n;
-      typedef typename __rebind_n::other::pointer      	 node_pointer;
+      typedef typename rebind_traits<_Alloc, node>::pointer node_pointer;
 
-      typedef typename _Alloc::template rebind<node_pointer>  __rebind_np;
 
-      typedef typename __rebind_np::other::pointer 	 entry_pointer;
-      typedef typename __rebind_np::other::const_pointer entry_const_pointer;
+      typedef typename rebind_traits<_Alloc, node_pointer>::pointer
+	entry_pointer;
+      typedef typename rebind_traits<_Alloc, node_pointer>::const_pointer
+	entry_const_pointer;
 
       enum
 	{
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
index fb87549..b647d3f 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
@@ -53,18 +53,14 @@ namespace __gnu_pbds
       typedef Value_Type value_type;
       typedef Metadata metadata_type;
 
-      typedef
-      typename _Alloc::template rebind<
-      splay_tree_node_<Value_Type, Metadata, _Alloc> >::other::pointer
-      node_pointer;
+      typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer
+	node_pointer;
 
-      typedef
-      typename _Alloc::template rebind<metadata_type>::other::reference
-      metadata_reference;
+      typedef typename rebind_traits<_Alloc, metadata_type>::reference
+	metadata_reference;
 
-      typedef
-      typename _Alloc::template rebind<metadata_type>::other::const_reference
-      metadata_const_reference;
+      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference
+	metadata_const_reference;
 
 #ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
       void
@@ -99,10 +95,8 @@ namespace __gnu_pbds
       typedef Value_Type value_type;
       typedef null_type metadata_type;
 
-      typedef
-      typename _Alloc::template rebind<
-      splay_tree_node_<Value_Type, null_type, _Alloc> >::other::pointer
-      node_pointer;
+      typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer
+	node_pointer;
 
       inline bool
       special() const
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 e8a2aab..f440fa3 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
@@ -78,7 +78,7 @@ namespace __gnu_pbds
     : public left_child_next_sibling_heap PB_DS_BASE_T_P
     {
     private:
-      typedef typename _Alloc::template rebind<Value_Type>::other __rebind_a;
+      typedef rebind_traits<_Alloc, Value_Type>		  __rebind_a;
       typedef left_child_next_sibling_heap PB_DS_BASE_T_P base_type;
 
     protected:
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp
index 2bb113a..6377d4f 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp
@@ -49,8 +49,8 @@ namespace __gnu_pbds
     typedef std::size_t 		       		size_type;
     typedef std::string 			       	key_type;
 
-    typedef typename _Alloc::template rebind<key_type>	__rebind_k;
-    typedef typename __rebind_k::other::const_reference	key_const_reference;
+    typedef typename rebind_traits<_Alloc, key_type>::const_reference
+      key_const_reference;
     typedef std::string::const_iterator 		const_iterator;
 
     /// Element type.
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/type_utils.hpp b/libstdc++-v3/include/ext/pb_ds/detail/type_utils.hpp
index 1436007..265b1cf 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/type_utils.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/type_utils.hpp
@@ -35,7 +35,7 @@
 
 /**
  * @file detail/type_utils.hpp
- * Contains utilities for handnling types. All of these classes are based on
+ * Contains utilities for handling types. All of these classes are based on
  * Modern C++ by Andrei Alxandrescu.
  */
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp b/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp
index 908d61d..86a0024 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/types_traits.hpp
@@ -45,7 +45,7 @@
 #include <utility>
 #include <ext/pb_ds/tag_and_trait.hpp>
 #include <ext/pb_ds/detail/type_utils.hpp>
-#include <utility>
+#include <memory>
 
 namespace __gnu_pbds
 {
@@ -91,146 +91,83 @@ namespace __gnu_pbds
 
     /// Primary template for representation of stored data.
     /// Two types of data can be stored: value and hash.
-    template<typename _Tv, typename _Th>
+    template<typename _Tv, typename _Th, bool Store_Hash>
       struct stored_data
       : public stored_value<_Tv>, public stored_hash<_Th>
       { };
 
     /// Specialization for representation of stored data of just value type.
-    template<typename _Tv>
-      struct stored_data<_Tv, null_type>
+    template<typename _Tv, typename _Th>
+      struct stored_data<_Tv, _Th, false>
       : public stored_value<_Tv>
       { };
 
-    /// Primary template.
-    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
-      struct type_base;
-
-    /**
-     * Specialization of type_base for the case where the hash value
-     * is not stored alongside each value.
-     */
-    template<typename Key, typename Mapped, typename _Alloc>
-      struct type_base<Key, Mapped, _Alloc, false>
+    /// Choose value_type to be a key/value pair or just a key.
+    template<typename Key, typename Mapped>
+      struct select_value_type
       {
-      public:
-	typedef typename _Alloc::size_type 		size_type;
-
-      private:
-	typedef typename _Alloc::template rebind<Mapped>	__rebind_m;
-	typedef typename __rebind_m::other			__rebind_ma;
-	typedef std::pair<const Key, Mapped>			__value_type;
-	typedef typename _Alloc::template rebind<__value_type>	__rebind_v;
-       	typedef typename __rebind_v::other			__rebind_va;
-
-      public:
-	typedef typename __rebind_ma::value_type       	mapped_type;
-	typedef typename __rebind_ma::pointer 		mapped_pointer;
-	typedef typename __rebind_ma::const_pointer 	mapped_const_pointer;
-	typedef typename __rebind_ma::reference	       	mapped_reference;
-	typedef typename __rebind_ma::const_reference 	mapped_const_reference;
-
-	typedef typename __rebind_va::value_type 	value_type;
-	typedef typename __rebind_va::pointer 		pointer;
-	typedef typename __rebind_va::const_pointer 	const_pointer;
-	typedef typename __rebind_va::reference 	reference;
-	typedef typename __rebind_va::const_reference 	const_reference;
-
-	typedef stored_data<value_type, null_type>	stored_data_type;
+	typedef std::pair<const Key, Mapped> type;
       };
 
-    /**
-     * Specialization of type_base for the case where the hash value
-     * is stored alongside each value.
-     */
-    template<typename Key, typename Mapped, typename _Alloc>
-      struct type_base<Key, Mapped, _Alloc, true>
+    /// Specialization for sets where the key is the value_type.
+    template<typename Key>
+      struct select_value_type<Key, null_type>
       {
-      public:
-	typedef typename _Alloc::size_type 		size_type;
-
-      private:
-	typedef typename _Alloc::template rebind<Mapped>	__rebind_m;
-	typedef typename __rebind_m::other			__rebind_ma;
-	typedef std::pair<const Key, Mapped>			__value_type;
-	typedef typename _Alloc::template rebind<__value_type>	__rebind_v;
-       	typedef typename __rebind_v::other			__rebind_va;
-
-      public:
-	typedef typename __rebind_ma::value_type       	mapped_type;
-	typedef typename __rebind_ma::pointer 		mapped_pointer;
-	typedef typename __rebind_ma::const_pointer 	mapped_const_pointer;
-	typedef typename __rebind_ma::reference	       	mapped_reference;
-	typedef typename __rebind_ma::const_reference 	mapped_const_reference;
-
-	typedef typename __rebind_va::value_type 	value_type;
-	typedef typename __rebind_va::pointer 		pointer;
-	typedef typename __rebind_va::const_pointer 	const_pointer;
-	typedef typename __rebind_va::reference 	reference;
-	typedef typename __rebind_va::const_reference 	const_reference;
-
-	typedef stored_data<value_type, size_type>	stored_data_type;
+	typedef Key type;
       };
 
+    /// Base class for conditionally defining a static data member.
+    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
+      struct maybe_null_type
+      { };
 
-    /**
-     * Specialization of type_base for the case where the hash value
-     * is not stored alongside each value.
-     */
-    template<typename Key, typename _Alloc>
-      struct type_base<Key, null_type, _Alloc, false>
+    /// Specialization that defines a static data member of type null_type.
+    template<typename Key,typename _Alloc, bool Store_Hash>
+      struct maybe_null_type<Key, null_type, _Alloc, Store_Hash>
       {
-      public:
-	typedef typename _Alloc::size_type 		size_type;
-	typedef Key 					value_type;
-
-      private:
-	typedef typename _Alloc::template rebind<null_type>  	__rebind_m;
-	typedef typename __rebind_m::other			__rebind_ma;
-	typedef typename _Alloc::template rebind<value_type>	__rebind_v;
-       	typedef typename __rebind_v::other			__rebind_va;
-
-      public:
-	typedef typename __rebind_ma::value_type       	mapped_type;
-	typedef typename __rebind_ma::pointer 		mapped_pointer;
-	typedef typename __rebind_ma::const_pointer 	mapped_const_pointer;
-	typedef typename __rebind_ma::reference	       	mapped_reference;
-	typedef typename __rebind_ma::const_reference 	mapped_const_reference;
-
-	typedef typename __rebind_va::pointer 		pointer;
-	typedef typename __rebind_va::const_pointer 	const_pointer;
-	typedef typename __rebind_va::reference 	reference;
-	typedef typename __rebind_va::const_reference 	const_reference;
-
-	typedef stored_data<value_type, null_type>	stored_data_type;
-
-	static null_type 			s_null_type;
+	static null_type s_null_type;
       };
 
-    template<typename Key, typename _Alloc>
+    template<typename Key,typename _Alloc, bool Store_Hash>
       null_type
-      type_base<Key, null_type, _Alloc, false>::s_null_type;
+      maybe_null_type<Key, null_type, _Alloc, Store_Hash>::s_null_type;
 
+    /// Consistent API for accessing allocator-related types.
+    template<typename _Alloc, typename T>
+      struct rebind_traits
+#if __cplusplus >= 201103L
+      : std::allocator_traits<_Alloc>::template rebind_traits<T>
+      {
+	using reference = T&;
+	using const_reference = const T&;
+      };
+#else
+      : _Alloc::template rebind<T>::other
+      {
+	typedef typename _Alloc::template rebind<T>::other allocator_type;
+      };
+#endif
 
-    /**
-     * Specialization of type_base for the case where the hash value
-     * is stored alongside each value.
-     */
-    template<typename Key, typename _Alloc>
-      struct type_base<Key, null_type, _Alloc, true>
+
+    /// Traits for abstract types.
+    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
+      struct types_traits
+      : public maybe_null_type<Key, Mapped, _Alloc, Store_Hash>
       {
       public:
-	typedef typename _Alloc::size_type 		size_type;
-	typedef Key 					value_type;
+	typedef typename _Alloc::size_type			size_type;
+	typedef typename select_value_type<Key, Mapped>::type	value_type;
+	typedef Key						key_type;
+	typedef Mapped						mapped_type;
 
       private:
-	typedef typename _Alloc::template rebind<null_type>  	__rebind_m;
-	typedef typename __rebind_m::other			__rebind_ma;
-	typedef typename _Alloc::template rebind<value_type>	__rebind_v;
-       	typedef typename __rebind_v::other			__rebind_va;
+	typedef rebind_traits<_Alloc, value_type>	__rebind_va;
+	typedef rebind_traits<_Alloc, key_type>		__rebind_ka;
+	typedef rebind_traits<_Alloc, mapped_type>	__rebind_ma;
+
+	typedef no_throw_copies<Key, Mapped>		__nothrowcopy;
 
       public:
-	typedef typename __rebind_ma::value_type       	mapped_type;
 	typedef typename __rebind_ma::pointer 		mapped_pointer;
 	typedef typename __rebind_ma::const_pointer 	mapped_const_pointer;
 	typedef typename __rebind_ma::reference	       	mapped_reference;
@@ -241,39 +178,12 @@ namespace __gnu_pbds
 	typedef typename __rebind_va::reference 	reference;
 	typedef typename __rebind_va::const_reference 	const_reference;
 
-	typedef stored_data<value_type, size_type>	stored_data_type;
+	typedef stored_data<value_type, size_type, Store_Hash> stored_data_type;
 
-	static null_type 		      	s_null_type;
-      };
-
-    template<typename Key, typename _Alloc>
-      null_type
-      type_base<Key, null_type, _Alloc, true>::s_null_type;
-
-
-    /// Type base dispatch.
-    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
-      struct type_dispatch
-      {
-	typedef type_base<Key, Mapped, _Alloc, Store_Hash> type;
-      };
-
-    /// Traits for abstract types.
-    template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
-      struct types_traits
-      : public type_dispatch<Key, Mapped, _Alloc, Store_Hash>::type
-      {
-      private:
-	typedef no_throw_copies<Key, Mapped>		__nothrowcopy;
-	typedef typename _Alloc::template rebind<Key>::other __rebind_a;
-
-      public:
-	typedef typename _Alloc::size_type 		size_type;
-	typedef typename __rebind_a::value_type 	key_type;
-	typedef typename __rebind_a::pointer 		key_pointer;
-	typedef typename __rebind_a::const_pointer 	key_const_pointer;
-	typedef typename __rebind_a::reference 		key_reference;
-	typedef typename __rebind_a::const_reference 	key_const_reference;
+	typedef typename __rebind_ka::pointer 		key_pointer;
+	typedef typename __rebind_ka::const_pointer 	key_const_pointer;
+	typedef typename __rebind_ka::reference 	key_reference;
+	typedef typename __rebind_ka::const_reference 	key_const_reference;
 	typedef std::pair<size_type, size_type> 	comp_hash;
 	typedef integral_constant<int, Store_Hash> 	store_extra;
 	typedef typename __nothrowcopy::indicator 	no_throw_indicator;
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 165d297..c1ba92e 100644
--- a/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp
@@ -43,6 +43,7 @@
 
 #include <bits/c++config.h>
 #include <cstdlib>
+#include <ext/pb_ds/detail/types_traits.hpp>
 #include <ext/pb_ds/detail/list_update_policy/lu_counter_metadata.hpp>
 #include <ext/pb_ds/tag_and_trait.hpp>
 
@@ -62,12 +63,10 @@ namespace __gnu_pbds
      /// Metadata on which this functor operates.
      typedef null_type 					metadata_type;
 
-   private:
-     typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
-
    public:
      /// Reference to metadata on which this functor operates.
-     typedef typename __rebind_m::other::reference 	metadata_reference;
+     typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
+       metadata_reference;
 
      /// Creates a metadata object.
      metadata_type
@@ -108,11 +107,11 @@ namespace __gnu_pbds
 
     private:
       typedef detail::lu_counter_policy_base<size_type> 	base_type;
-      typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
 
     public:
       /// Reference to metadata on which this functor operates.
-      typedef typename __rebind_m::other::reference 	metadata_reference;
+     typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
+       metadata_reference;
 
       /// Creates a metadata object.
       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 c779e8c..ea16bf6 100644
--- a/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/priority_queue.hpp
@@ -95,8 +95,7 @@ namespace __gnu_pbds
     typedef typename detail::container_base_dispatch<_Tv, Cmp_Fn, _Alloc,
 						     Tag>::type
  							base_type;
-    typedef typename _Alloc::template rebind<_Tv>   	__rebind_v;
-    typedef typename __rebind_v::other			__rebind_va;
+    typedef detail::rebind_traits<_Alloc, _Tv>		__rebind_va;
 
  public:
     typedef typename __rebind_va::reference 		reference;
diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
index 431bb02..bf831b8 100644
--- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
@@ -108,13 +108,13 @@ namespace __gnu_pbds
     /// Const pointer to the container's value-type.
     typedef typename base_type::const_pointer 		const_pointer;
 
-    typedef typename _Alloc::template rebind<metadata_type>::other __rebind_m;
-
     /// Const metadata reference.
-    typedef typename __rebind_m::const_reference       metadata_const_reference;
+    typedef typename detail::rebind_traits<_Alloc, metadata_type>::const_reference
+      metadata_const_reference;
 
     /// Metadata reference.
-    typedef typename __rebind_m::reference 		metadata_reference;
+    typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
+      metadata_reference;
 
     /// Returns the node_const_iterator associated with the tree's root node.
     virtual node_const_iterator
diff --git a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
index 9c750aa..f74234e 100644
--- a/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp
@@ -76,8 +76,8 @@ namespace __gnu_pbds
   public:
     typedef typename _Alloc::size_type			  size_type;
     typedef String 					  key_type;
-    typedef typename _Alloc::template rebind<key_type>	  __rebind_k;
-    typedef typename __rebind_k::other::const_reference   key_const_reference;
+    typedef typename detail::rebind_traits<_Alloc, key_type>::const_reference
+      key_const_reference;
 
     enum
       {