* [PATCH] Adjust pb_ds extensions to use allocator_traits
@ 2019-10-23 16:18 Jonathan Wakely
0 siblings, 0 replies; only message in thread
From: Jonathan Wakely @ 2019-10-23 16:18 UTC (permalink / raw)
To: libstdc++, gcc-patches; +Cc: Tadeus Prastowo, Alexander Kulkov
[-- Attachment #1: Type: text/plain, Size: 3747 bytes --]
This fixes the PDBS containers to support C++11-style allocators. I
consider the hours spent doing this completely wasted, but it was
necessary to keep the testsuite clean. I still want this code to go
away.
Tested powerpc64le-linux, committed to trunk.
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.
[-- Attachment #2: patch.txt --]
[-- Type: text/plain, Size: 78279 bytes --]
commit 238cc9d024d2c1392ca9d695bb6e5eb9dab521fe
Author: Jonathan Wakely <jwakely@redhat.com>
Date: Wed Oct 23 11:52:17 2019 +0100
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.
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 b64cc38aa61..89ccf9e30ab 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 bcde6a0413b..b44e3b00611 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 b42c03524a4..7a601bdb697 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 dbfd612917e..58cb69e2d8d 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 38381adef65..1efcdc38171 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 1ad0d79810c..3f15875453e 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 15c89a604a0..bb39b9b0281 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 306950d37dc..d8c2d35141e 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 04cfb337ef3..38f60c2d057 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 1a6affc70b2..93006fbaa8d 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 b92aa2668ca..89766e394cd 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 85d4a8a9796..240493c05f3 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 90dfd50ef8e..c1cb552f9cc 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 7d0185eea66..4724f7d1e89 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 6a8eb59683c..33904110fb4 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 32d67eb3d3a..5e80258ef68 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;
+ left_child_next_sibling_heap_node_<Value_Type, Node_Metadata, _Alloc>
+ node;
- typedef typename node_allocator::value_type node;
- typedef typename node_allocator::pointer node_pointer;
- typedef typename node_allocator::const_pointer node_const_pointer;
+ 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 4a7746c227b..9dd36a30ea7 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 4ec381ddfa3..bb6d3dc8cad 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 a3c0fb49c9a..9f561762c69 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 e081392a8cd..57a284a39a6 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 2427cbc8d66..e45d3a74e7c 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 0859da17d7a..b601031f727 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 ccf453881d2..e9fb0b38fb0 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 3f7e054e249..2da385813a4 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 cf610cb6e35..b9d71c76746 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 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 _Alloc::template rebind<Inode> __rebind_in;
- typedef typename __rebind_in::other::pointer inode_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 7271e18d3f2..b2330fa1c43 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 rebind_traits<_Alloc, rb_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;
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 5c996d11e28..0cf81a73a51 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 fb875493cac..b647d3f8b68 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 e8a2aabd7e4..f440fa3b7e7 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 2bb113a79d7..6377d4fa432 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 143600796b7..265b1cfcfe0 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 908d61d1ed3..86a00244845 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,189 +91,99 @@ 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.
+ /// Choose value_type to be a key/value pair or just a key.
+ template<typename Key, typename Mapped>
+ struct select_value_type
+ {
+ typedef std::pair<const Key, Mapped> type;
+ };
+
+ /// Specialization for sets where the key is the value_type.
+ template<typename Key>
+ struct select_value_type<Key, null_type>
+ {
+ typedef Key type;
+ };
+
+ /// Base class for conditionally defining a static data member.
template<typename Key, typename Mapped, typename _Alloc, bool Store_Hash>
- struct type_base;
+ 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 Mapped, typename _Alloc>
- struct type_base<Key, Mapped, _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;
-
- 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;
+ static null_type s_null_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>
- {
- 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;
- };
-
-
- /**
- * 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>
- {
- 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;
- };
-
- 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;
-
- /**
- * 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>
+ /// 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>
{
- 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, size_type> stored_data_type;
-
- static null_type s_null_type;
+ using reference = T&;
+ using const_reference = const T&;
};
-
- 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
+#else
+ : _Alloc::template rebind<T>::other
{
- typedef type_base<Key, Mapped, _Alloc, Store_Hash> type;
+ typedef typename _Alloc::template rebind<T>::other allocator_type;
};
+#endif
+
/// 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
+ : public maybe_null_type<Key, Mapped, _Alloc, Store_Hash>
{
+ public:
+ 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 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;
- 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_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, size_type, Store_Hash> stored_data_type;
+
+ 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 165d297f094..c1ba92ebaeb 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 c779e8c1b83..ea16bf66b87 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 431bb023549..bf831b80f93 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 9c750aa56b3..f74234ea104 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
{
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2019-10-23 16:18 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-10-23 16:18 [PATCH] Adjust pb_ds extensions to use allocator_traits Jonathan Wakely
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).