41 #ifndef PB_DS_ASSOC_CNTNR_HPP
42 #define PB_DS_ASSOC_CNTNR_HPP
48 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
52 #define PB_DS_BASE_C_DEC \
53 detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
56 template<
typename Key,
61 class container_base :
public PB_DS_BASE_C_DEC
64 typedef typename PB_DS_BASE_C_DEC base_type;
67 typedef Tag container_category;
68 typedef Allocator allocator_type;
69 typedef typename allocator_type::size_type size_type;
70 typedef typename allocator_type::difference_type difference_type;
73 typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
74 typedef typename allocator_type::template rebind<key_type>::other key_rebind;
75 typedef typename key_rebind::reference key_reference;
76 typedef typename key_rebind::const_reference const_key_reference;
77 typedef typename key_rebind::pointer key_pointer;
78 typedef typename key_rebind::const_pointer const_key_pointer;
81 typedef Mapped mapped_type;
82 typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
83 typedef typename mapped_rebind::reference mapped_reference;
84 typedef typename mapped_rebind::const_reference const_mapped_reference;
85 typedef typename mapped_rebind::pointer mapped_pointer;
86 typedef typename mapped_rebind::const_pointer const_mapped_pointer;
89 typedef typename base_type::value_type value_type;
90 typedef typename allocator_type::template rebind<value_type>::other value_rebind;
91 typedef typename value_rebind::reference reference;
92 typedef typename value_rebind::const_reference const_reference;
93 typedef typename value_rebind::pointer pointer;
94 typedef typename value_rebind::const_pointer const_pointer;
97 typedef typename base_type::iterator iterator;
98 typedef typename base_type::const_iterator const_iterator;
99 typedef typename base_type::point_iterator point_iterator;
100 typedef typename base_type::const_point_iterator const_point_iterator;
103 ~container_base() { }
106 #define PB_DS_CLASS_NAME container_base
108 #undef PB_DS_CLASS_NAME
111 #undef PB_DS_BASE_C_DEC
114 #define PB_DS_BASE_C_DEC \
115 container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
116 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
119 template<
typename Key,
123 typename Resize_Policy,
128 class basic_hash_table :
public PB_DS_BASE_C_DEC
131 typedef PB_DS_BASE_C_DEC base_type;
135 ~basic_hash_table() { }
138 #define PB_DS_CLASS_NAME basic_hash_table
140 #undef PB_DS_CLASS_NAME
144 operator=(
const base_type&);
147 #undef PB_DS_BASE_C_DEC
150 #define PB_DS_BASE_C_DEC \
151 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
153 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
156 template<
typename Key,
158 typename Hash_Fn =
typename detail::default_hash_fn<Key>::type,
160 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
161 typename Resize_Policy =
typename detail::default_resize_policy<Comb_Hash_Fn>::type,
162 bool Store_Hash = detail::default_store_hash,
164 class cc_hash_table :
public PB_DS_BASE_C_DEC
167 typedef PB_DS_BASE_C_DEC base_type;
170 typedef Hash_Fn hash_fn;
172 typedef Resize_Policy resize_policy;
173 typedef Comb_Hash_Fn comb_hash_fn;
180 cc_hash_table(
const hash_fn& h)
187 cc_hash_table(
const hash_fn& h,
const eq_fn& e)
188 : base_type(h, e) { }
195 cc_hash_table(
const hash_fn& h,
const eq_fn& e,
const comb_hash_fn& ch)
196 : base_type(h, e, ch) { }
204 cc_hash_table(
const hash_fn& h,
const eq_fn& e,
const comb_hash_fn& ch,
205 const resize_policy& rp)
206 : base_type(h, e, ch, rp) { }
211 template<
typename It>
212 cc_hash_table(It first, It last)
213 { base_type::copy_from_range(first, last); }
218 template<
typename It>
219 cc_hash_table(It first, It last,
const hash_fn& h)
221 { copy_from_range(first, last); }
229 template<
typename It>
230 cc_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e)
232 { copy_from_range(first, last); }
241 template<
typename It>
242 cc_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e,
243 const comb_hash_fn& ch)
244 : base_type(h, e, ch)
245 { copy_from_range(first, last); }
255 template<
typename It>
256 cc_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e,
257 const comb_hash_fn& ch,
const resize_policy& rp)
258 : base_type(h, e, ch, rp)
259 { copy_from_range(first, last); }
261 cc_hash_table(
const cc_hash_table& other)
262 : base_type((
const base_type&)other)
269 operator=(
const cc_hash_table& other)
273 cc_hash_table tmp(other);
280 swap(cc_hash_table& other)
281 { base_type::swap(other); }
284 #undef PB_DS_BASE_C_DEC
287 #define PB_DS_BASE_C_DEC \
288 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
290 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
293 template<
typename Key,
295 typename Hash_Fn =
typename detail::default_hash_fn<Key>::type,
297 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
298 typename Probe_Fn =
typename detail::default_probe_fn<Comb_Probe_Fn>::type,
299 typename Resize_Policy =
typename detail::default_resize_policy<Comb_Probe_Fn>::type,
300 bool Store_Hash = detail::default_store_hash,
302 class gp_hash_table :
public PB_DS_BASE_C_DEC
305 typedef PB_DS_BASE_C_DEC base_type;
308 typedef Hash_Fn hash_fn;
310 typedef Comb_Probe_Fn comb_probe_fn;
311 typedef Probe_Fn probe_fn;
312 typedef Resize_Policy resize_policy;
319 gp_hash_table(
const hash_fn& h)
326 gp_hash_table(
const hash_fn& h,
const eq_fn& e)
327 : base_type(h, e) { }
334 gp_hash_table(
const hash_fn& h,
const eq_fn& e,
const comb_probe_fn& cp)
335 : base_type(h, e, cp) { }
343 gp_hash_table(
const hash_fn& h,
const eq_fn& e,
const comb_probe_fn& cp,
345 : base_type(h, e, cp, p) { }
354 gp_hash_table(
const hash_fn& h,
const eq_fn& e,
const comb_probe_fn& cp,
355 const probe_fn& p,
const resize_policy& rp)
356 : base_type(h, e, cp, p, rp) { }
361 template<
typename It>
362 gp_hash_table(It first, It last)
363 { base_type::copy_from_range(first, last); }
369 template<
typename It>
370 gp_hash_table(It first, It last,
const hash_fn& h)
372 { base_type::copy_from_range(first, last); }
380 template<
typename It>
381 gp_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e)
383 { base_type::copy_from_range(first, last); }
392 template<
typename It>
393 gp_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e,
394 const comb_probe_fn& cp)
395 : base_type(h, e, cp)
396 { base_type::copy_from_range(first, last); }
406 template<
typename It>
407 gp_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e,
408 const comb_probe_fn& cp,
const probe_fn& p)
409 : base_type(h, e, cp, p)
410 { base_type::copy_from_range(first, last); }
422 template<
typename It>
423 gp_hash_table(It first, It last,
const hash_fn& h,
const eq_fn& e,
424 const comb_probe_fn& cp,
const probe_fn& p,
425 const resize_policy& rp)
426 : base_type(h, e, cp, p, rp)
427 { base_type::copy_from_range(first, last); }
429 gp_hash_table(
const gp_hash_table& other)
430 : base_type((
const base_type&)other)
437 operator=(
const gp_hash_table& other)
441 gp_hash_table tmp(other);
448 swap(gp_hash_table& other)
449 { base_type::swap(other); }
452 #undef PB_DS_BASE_C_DEC
455 #define PB_DS_BASE_C_DEC \
456 container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
459 template<
typename Key,
typename Mapped,
typename Tag,
460 typename Node_Update,
typename Policy_Tl,
typename Allocator>
461 class basic_tree :
public PB_DS_BASE_C_DEC
464 typedef PB_DS_BASE_C_DEC base_type;
467 typedef Node_Update node_update;
473 #define PB_DS_CLASS_NAME basic_tree
475 #undef PB_DS_CLASS_NAME
478 #undef PB_DS_BASE_C_DEC
481 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
482 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
484 #define PB_DS_BASE_C_DEC \
485 basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
486 typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
489 template<
typename Key,
typename Mapped,
typename Cmp_Fn = std::less<Key>,
490 typename Tag = rb_tree_tag,
491 template<
typename Const_Node_Iterator,
typename Node_Iterator,
typename Cmp_Fn_,
typename Allocator_>
492 class Node_Update = __gnu_pbds::null_tree_node_update,
494 class tree :
public PB_DS_BASE_C_DEC
497 typedef PB_DS_BASE_C_DEC base_type;
501 typedef Cmp_Fn cmp_fn;
507 tree(
const cmp_fn& c)
513 template<
typename It>
514 tree(It first, It last)
515 { base_type::copy_from_range(first, last); }
521 template<
typename It>
522 tree(It first, It last,
const cmp_fn& c)
524 { base_type::copy_from_range(first, last); }
526 tree(
const tree& other)
527 : base_type((
const base_type&)other) { }
533 operator=(
const tree& other)
545 { base_type::swap(other); }
548 #undef PB_DS_BASE_C_DEC
549 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
552 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
553 detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
555 #define PB_DS_BASE_C_DEC \
556 basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
557 typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
560 template<
typename Key,
562 typename E_Access_Traits =
typename detail::default_trie_e_access_traits<Key>::type,
564 template<
typename Const_Node_Iterator,
565 typename Node_Iterator,
566 typename E_Access_Traits_,
568 class Node_Update = null_trie_node_update,
570 class trie :
public PB_DS_BASE_C_DEC
573 typedef PB_DS_BASE_C_DEC base_type;
577 typedef E_Access_Traits e_access_traits;
584 trie(
const e_access_traits& t)
590 template<
typename It>
591 trie(It first, It last)
592 { base_type::copy_from_range(first, last); }
597 template<
typename It>
598 trie(It first, It last,
const e_access_traits& t)
600 { base_type::copy_from_range(first, last); }
602 trie(
const trie& other)
603 : base_type((
const base_type&)other) { }
609 operator=(
const trie& other)
621 { base_type::swap(other); }
624 #undef PB_DS_BASE_C_DEC
625 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
628 #define PB_DS_BASE_C_DEC \
629 container_base<Key, Mapped, list_update_tag, \
630 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
633 template<
typename Key,
636 class Update_Policy = detail::default_update_policy::type,
638 class list_update :
public PB_DS_BASE_C_DEC
641 typedef PB_DS_BASE_C_DEC base_type;
645 typedef Update_Policy update_policy;
646 typedef Allocator allocator;
653 template<
typename It>
654 list_update(It first, It last)
655 { base_type::copy_from_range(first, last); }
657 list_update(
const list_update& other)
658 : base_type((
const base_type&)other) { }
664 operator=(
const list_update& other)
668 list_update tmp(other);
675 swap(list_update& other)
676 { base_type::swap(other); }
679 #undef PB_DS_BASE_C_DEC
The "standard" allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manu...
One of the comparison functors.
GNU extensions for policy-based data structures for public use.