3 // Copyright (C) 2005-2016 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 // General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
37 * @file assoc_container.hpp
38 * Contains associative containers.
41 #ifndef PB_DS_ASSOC_CNTNR_HPP
42 #define PB_DS_ASSOC_CNTNR_HPP
44 #include <bits/c++config.h>
45 #include <ext/typelist.h>
46 #include <ext/pb_ds/tag_and_trait.hpp>
47 #include <ext/pb_ds/detail/standard_policies.hpp>
48 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
49 #include <ext/pb_ds/detail/branch_policy/traits.hpp>
54 * @defgroup containers-pbds Containers
60 * @defgroup hash-based Hash-Based
61 * @ingroup containers-pbds
64 #define PB_DS_HASH_BASE \
65 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
66 typename __gnu_cxx::typelist::append< \
67 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
68 detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
71 * @defgroup hash-detail Base and Policy Classes
76 * A hashed container abstraction.
78 * @tparam Key Key type.
79 * @tparam Mapped Map type.
80 * @tparam Hash_Fn Hashing functor.
81 * @tparam Eq_Fn Equal functor.
82 * @tparam Resize_Policy Resizes hash.
83 * @tparam Store_Hash Indicates whether the hash value
84 * will be stored along with each key.
85 * @tparam Tag Instantiating data structure type,
87 * @tparam Policy_TL Policy typelist.
88 * @tparam _Alloc Allocator type.
90 * Base is dispatched at compile time via Tag, from the following
91 * choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
93 * Base choices are: detail::cc_ht_map, detail::gp_ht_map
95 template<typename Key,
99 typename Resize_Policy,
104 class basic_hash_table : public PB_DS_HASH_BASE
107 typedef typename PB_DS_HASH_BASE base_type;
111 ~basic_hash_table() { }
114 basic_hash_table() { }
116 basic_hash_table(const basic_hash_table& other)
117 : base_type((const base_type&)other) { }
119 template<typename T0>
120 basic_hash_table(T0 t0) : base_type(t0) { }
122 template<typename T0, typename T1>
123 _GLIBCXX_ABI_TAG_EMPTY
124 basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
126 template<typename T0, typename T1, typename T2>
127 _GLIBCXX_ABI_TAG_EMPTY
128 basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
130 template<typename T0, typename T1, typename T2, typename T3>
131 _GLIBCXX_ABI_TAG_EMPTY
132 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
133 : base_type(t0, t1, t2, t3) { }
135 template<typename T0, typename T1, typename T2, typename T3, typename T4>
136 _GLIBCXX_ABI_TAG_EMPTY
137 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
138 : base_type(t0, t1, t2, t3, t4) { }
140 template<typename T0, typename T1, typename T2, typename T3, typename T4,
142 _GLIBCXX_ABI_TAG_EMPTY
143 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
144 : base_type(t0, t1, t2, t3, t4, t5) { }
146 template<typename T0, typename T1, typename T2, typename T3, typename T4,
147 typename T5, typename T6>
148 _GLIBCXX_ABI_TAG_EMPTY
149 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
150 : base_type(t0, t1, t2, t3, t4, t5, t6) { }
152 template<typename T0, typename T1, typename T2, typename T3, typename T4,
153 typename T5, typename T6, typename T7>
154 _GLIBCXX_ABI_TAG_EMPTY
155 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
156 : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }
158 template<typename T0, typename T1, typename T2, typename T3, typename T4,
159 typename T5, typename T6, typename T7, typename T8>
160 _GLIBCXX_ABI_TAG_EMPTY
161 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
163 : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
168 operator=(const base_type&);
171 #undef PB_DS_HASH_BASE
174 #define PB_DS_CC_HASH_BASE \
175 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
177 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
181 * A collision-chaining hash-based associative container.
183 * @tparam Key Key type.
184 * @tparam Mapped Map type.
185 * @tparam Hash_Fn Hashing functor.
186 * @tparam Eq_Fn Equal functor.
187 * @tparam Comb_Hash_Fn Combining hash functor.
188 * If Hash_Fn is not null_type, then this
189 * is the ranged-hash functor; otherwise,
190 * this is the range-hashing functor.
191 * XXX(See Design::Hash-Based Containers::Hash Policies.)
192 * @tparam Resize_Policy Resizes hash.
193 * @tparam Store_Hash Indicates whether the hash value
194 * will be stored along with each key.
195 * If Hash_Fn is null_type, then the
196 * container will not compile if this
198 * @tparam _Alloc Allocator type.
200 * Base tag choices are: cc_hash_tag.
202 * Base is basic_hash_table.
204 template<typename Key,
206 typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
207 typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
208 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
209 typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
210 bool Store_Hash = detail::default_store_hash,
211 typename _Alloc = std::allocator<char> >
212 class cc_hash_table : public PB_DS_CC_HASH_BASE
215 typedef PB_DS_CC_HASH_BASE base_type;
218 typedef cc_hash_tag container_category;
219 typedef Hash_Fn hash_fn;
221 typedef Resize_Policy resize_policy;
222 typedef Comb_Hash_Fn comb_hash_fn;
224 /// Default constructor.
227 /// Constructor taking some policy objects. r_hash_fn will be
228 /// copied by the Hash_Fn object of the container object.
229 cc_hash_table(const hash_fn& h)
232 /// Constructor taking some policy objects. r_hash_fn will be
233 /// copied by the hash_fn object of the container object, and
234 /// r_eq_fn will be copied by the eq_fn object of the container
236 cc_hash_table(const hash_fn& h, const eq_fn& e)
237 : base_type(h, e) { }
239 /// Constructor taking some policy objects. r_hash_fn will be
240 /// copied by the hash_fn object of the container object, r_eq_fn
241 /// will be copied by the eq_fn object of the container object,
242 /// and r_comb_hash_fn will be copied by the comb_hash_fn object
243 /// of the container object.
244 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
245 : base_type(h, e, ch) { }
247 /// Constructor taking some policy objects. r_hash_fn will be
248 /// copied by the hash_fn object of the container object, r_eq_fn
249 /// will be copied by the eq_fn object of the container object,
250 /// r_comb_hash_fn will be copied by the comb_hash_fn object of
251 /// the container object, and r_resize_policy will be copied by
252 /// the resize_policy object of the container object.
253 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
254 const resize_policy& rp)
255 : base_type(h, e, ch, rp) { }
257 /// Constructor taking __iterators to a range of value_types. The
258 /// value_types between first_it and last_it will be inserted into
259 /// the container object.
260 template<typename It>
261 cc_hash_table(It first, It last)
262 { base_type::copy_from_range(first, last); }
264 /// Constructor taking __iterators to a range of value_types and
265 /// some policy objects. The value_types between first_it and
266 /// last_it will be inserted into the container object.
267 template<typename It>
268 cc_hash_table(It first, It last, const hash_fn& h)
270 { this->copy_from_range(first, last); }
272 /// Constructor taking __iterators to a range of value_types and
273 /// some policy objects The value_types between first_it and
274 /// last_it will be inserted into the container object. r_hash_fn
275 /// will be copied by the hash_fn object of the container object,
276 /// and r_eq_fn will be copied by the eq_fn object of the
277 /// container object.
278 template<typename It>
279 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
281 { this->copy_from_range(first, last); }
283 /// Constructor taking __iterators to a range of value_types and
284 /// some policy objects The value_types between first_it and
285 /// last_it will be inserted into the container object. r_hash_fn
286 /// will be copied by the hash_fn object of the container object,
287 /// r_eq_fn will be copied by the eq_fn object of the container
288 /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
289 /// object of the container object.
290 template<typename It>
291 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
292 const comb_hash_fn& ch)
293 : base_type(h, e, ch)
294 { this->copy_from_range(first, last); }
296 /// Constructor taking __iterators to a range of value_types and
297 /// some policy objects The value_types between first_it and
298 /// last_it will be inserted into the container object. r_hash_fn
299 /// will be copied by the hash_fn object of the container object,
300 /// r_eq_fn will be copied by the eq_fn object of the container
301 /// object, r_comb_hash_fn will be copied by the comb_hash_fn
302 /// object of the container object, and r_resize_policy will be
303 /// copied by the resize_policy object of the container object.
304 template<typename It>
305 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
306 const comb_hash_fn& ch, const resize_policy& rp)
307 : base_type(h, e, ch, rp)
308 { this->copy_from_range(first, last); }
310 cc_hash_table(const cc_hash_table& other)
311 : base_type((const base_type&)other)
318 operator=(const cc_hash_table& other)
322 cc_hash_table tmp(other);
329 swap(cc_hash_table& other)
330 { base_type::swap(other); }
333 #undef PB_DS_CC_HASH_BASE
336 #define PB_DS_GP_HASH_BASE \
337 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
339 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
343 * A general-probing hash-based associative container.
345 * @tparam Key Key type.
346 * @tparam Mapped Map type.
347 * @tparam Hash_Fn Hashing functor.
348 * @tparam Eq_Fn Equal functor.
349 * @tparam Comb_Probe_Fn Combining probe functor.
350 * If Hash_Fn is not null_type, then this
351 * is the ranged-probe functor; otherwise,
352 * this is the range-hashing functor.
353 * XXX See Design::Hash-Based Containers::Hash Policies.
354 * @tparam Probe_Fn Probe functor.
355 * @tparam Resize_Policy Resizes hash.
356 * @tparam Store_Hash Indicates whether the hash value
357 * will be stored along with each key.
358 * If Hash_Fn is null_type, then the
359 * container will not compile if this
361 * @tparam _Alloc Allocator type.
363 * Base tag choices are: gp_hash_tag.
365 * Base is basic_hash_table.
367 template<typename Key,
369 typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
370 typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
371 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
372 typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
373 typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
374 bool Store_Hash = detail::default_store_hash,
375 typename _Alloc = std::allocator<char> >
376 class gp_hash_table : public PB_DS_GP_HASH_BASE
379 typedef PB_DS_GP_HASH_BASE base_type;
382 typedef gp_hash_tag container_category;
383 typedef Hash_Fn hash_fn;
385 typedef Comb_Probe_Fn comb_probe_fn;
386 typedef Probe_Fn probe_fn;
387 typedef Resize_Policy resize_policy;
389 /// Default constructor.
392 /// Constructor taking some policy objects. r_hash_fn will be
393 /// copied by the hash_fn object of the container object.
394 gp_hash_table(const hash_fn& h)
397 /// Constructor taking some policy objects. r_hash_fn will be
398 /// copied by the hash_fn object of the container object, and
399 /// r_eq_fn will be copied by the eq_fn object of the container
401 gp_hash_table(const hash_fn& h, const eq_fn& e)
402 : base_type(h, e) { }
404 /// Constructor taking some policy objects. r_hash_fn will be
405 /// copied by the hash_fn object of the container object, r_eq_fn
406 /// will be copied by the eq_fn object of the container object,
407 /// and r_comb_probe_fn will be copied by the comb_probe_fn object
408 /// of the container object.
409 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
410 : base_type(h, e, cp) { }
412 /// Constructor taking some policy objects. r_hash_fn will be
413 /// copied by the hash_fn object of the container object, r_eq_fn
414 /// will be copied by the eq_fn object of the container object,
415 /// r_comb_probe_fn will be copied by the comb_probe_fn object of
416 /// the container object, and r_probe_fn will be copied by the
417 /// probe_fn object of the container object.
418 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
420 : base_type(h, e, cp, p) { }
422 /// Constructor taking some policy objects. r_hash_fn will be
423 /// copied by the hash_fn object of the container object, r_eq_fn
424 /// will be copied by the eq_fn object of the container object,
425 /// r_comb_probe_fn will be copied by the comb_probe_fn object of
426 /// the container object, r_probe_fn will be copied by the
427 /// probe_fn object of the container object, and r_resize_policy
428 /// will be copied by the Resize_Policy object of the container
430 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
431 const probe_fn& p, const resize_policy& rp)
432 : base_type(h, e, cp, p, rp) { }
434 /// Constructor taking __iterators to a range of value_types. The
435 /// value_types between first_it and last_it will be inserted into
436 /// the container object.
437 template<typename It>
438 gp_hash_table(It first, It last)
439 { base_type::copy_from_range(first, last); }
441 /// Constructor taking __iterators to a range of value_types and
442 /// some policy objects. The value_types between first_it and
443 /// last_it will be inserted into the container object. r_hash_fn
444 /// will be copied by the hash_fn object of the container object.
445 template<typename It>
446 gp_hash_table(It first, It last, const hash_fn& h)
448 { base_type::copy_from_range(first, last); }
450 /// Constructor taking __iterators to a range of value_types and
451 /// some policy objects. The value_types between first_it and
452 /// last_it will be inserted into the container object. r_hash_fn
453 /// will be copied by the hash_fn object of the container object,
454 /// and r_eq_fn will be copied by the eq_fn object of the
455 /// container object.
456 template<typename It>
457 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
459 { base_type::copy_from_range(first, last); }
461 /// Constructor taking __iterators to a range of value_types and
462 /// some policy objects. The value_types between first_it and
463 /// last_it will be inserted into the container object. r_hash_fn
464 /// will be copied by the hash_fn object of the container object,
465 /// r_eq_fn will be copied by the eq_fn object of the container
466 /// object, and r_comb_probe_fn will be copied by the
467 /// comb_probe_fn object of the container object.
468 template<typename It>
469 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
470 const comb_probe_fn& cp)
471 : base_type(h, e, cp)
472 { base_type::copy_from_range(first, last); }
474 /// Constructor taking __iterators to a range of value_types and
475 /// some policy objects. The value_types between first_it and
476 /// last_it will be inserted into the container object. r_hash_fn
477 /// will be copied by the hash_fn object of the container object,
478 /// r_eq_fn will be copied by the eq_fn object of the container
479 /// object, r_comb_probe_fn will be copied by the comb_probe_fn
480 /// object of the container object, and r_probe_fn will be copied
481 /// by the probe_fn object of the container object.
482 template<typename It>
483 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
484 const comb_probe_fn& cp, const probe_fn& p)
485 : base_type(h, e, cp, p)
486 { base_type::copy_from_range(first, last); }
488 /// Constructor taking __iterators to a range of value_types and
489 /// some policy objects. The value_types between first_it and
490 /// last_it will be inserted into the container object. r_hash_fn
491 /// will be copied by the hash_fn object of the container object,
492 /// r_eq_fn will be copied by the eq_fn object of the container
493 /// object, r_comb_probe_fn will be copied by the comb_probe_fn
494 /// object of the container object, r_probe_fn will be copied by
495 /// the probe_fn object of the container object, and
496 /// r_resize_policy will be copied by the resize_policy object of
497 /// the container object.
498 template<typename It>
499 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
500 const comb_probe_fn& cp, const probe_fn& p,
501 const resize_policy& rp)
502 : base_type(h, e, cp, p, rp)
503 { base_type::copy_from_range(first, last); }
505 gp_hash_table(const gp_hash_table& other)
506 : base_type((const base_type&)other)
513 operator=(const gp_hash_table& other)
517 gp_hash_table tmp(other);
524 swap(gp_hash_table& other)
525 { base_type::swap(other); }
528 #undef PB_DS_GP_HASH_BASE
532 * @defgroup branch-based Branch-Based
533 * @ingroup containers-pbds
536 #define PB_DS_BRANCH_BASE \
537 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
540 * @defgroup branch-detail Base and Policy Classes
541 * @ingroup branch-based
545 * A branched, tree-like (tree, trie) container abstraction.
547 * @tparam Key Key type.
548 * @tparam Mapped Map type.
549 * @tparam Tag Instantiating data structure type,
551 * @tparam Node_Update Updates nodes, restores invariants.
552 * @tparam Policy_TL Policy typelist.
553 * @tparam _Alloc Allocator type.
555 * Base is dispatched at compile time via Tag, from the following
556 * choices: tree_tag, trie_tag, and their descendants.
558 * Base choices are: detail::ov_tree_map, detail::rb_tree_map,
559 * detail::splay_tree_map, and detail::pat_trie_map.
561 template<typename Key, typename Mapped, typename Tag,
562 typename Node_Update, typename Policy_Tl, typename _Alloc>
563 class basic_branch : public PB_DS_BRANCH_BASE
566 typedef typename PB_DS_BRANCH_BASE base_type;
569 typedef Node_Update node_update;
577 basic_branch(const basic_branch& other)
578 : base_type((const base_type&)other) { }
580 template<typename T0>
581 basic_branch(T0 t0) : base_type(t0) { }
583 template<typename T0, typename T1>
584 basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
586 template<typename T0, typename T1, typename T2>
587 basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
589 template<typename T0, typename T1, typename T2, typename T3>
590 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
591 : base_type(t0, t1, t2, t3) { }
593 template<typename T0, typename T1, typename T2, typename T3, typename T4>
594 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
595 : base_type(t0, t1, t2, t3, t4) { }
597 template<typename T0, typename T1, typename T2, typename T3, typename T4,
599 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
600 : base_type(t0, t1, t2, t3, t4, t5) { }
602 template<typename T0, typename T1, typename T2, typename T3, typename T4,
603 typename T5, typename T6>
604 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
605 : base_type(t0, t1, t2, t3, t4, t5, t6) { }
607 #undef PB_DS_BRANCH_BASE
610 #define PB_DS_TREE_NODE_AND_IT_TRAITS \
611 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
613 #define PB_DS_TREE_BASE \
614 basic_branch<Key,Mapped, Tag, \
615 typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
616 typename __gnu_cxx::typelist::create2<Cmp_Fn, \
617 PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
621 * A tree-based container.
623 * @tparam Key Key type.
624 * @tparam Mapped Map type.
625 * @tparam Cmp_Fn Comparison functor.
626 * @tparam Tag Instantiating data structure type,
628 * @tparam Node_Update Updates tree internal-nodes,
629 * restores invariants when invalidated.
630 * XXX See design::tree-based-containers::node invariants.
631 * @tparam _Alloc Allocator type.
633 * Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
635 * Base is basic_branch.
637 template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
638 typename Tag = rb_tree_tag,
639 template<typename Node_CItr, typename Node_Itr,
640 typename Cmp_Fn_, typename _Alloc_>
641 class Node_Update = null_node_update,
642 typename _Alloc = std::allocator<char> >
643 class tree : public PB_DS_TREE_BASE
646 typedef PB_DS_TREE_BASE base_type;
649 /// Comparison functor type.
650 typedef Cmp_Fn cmp_fn;
654 /// Constructor taking some policy objects. r_cmp_fn will be
655 /// copied by the Cmp_Fn object of the container object.
656 tree(const cmp_fn& c)
659 /// Constructor taking __iterators to a range of value_types. The
660 /// value_types between first_it and last_it will be inserted into
661 /// the container object.
662 template<typename It>
663 tree(It first, It last)
664 { base_type::copy_from_range(first, last); }
666 /// Constructor taking __iterators to a range of value_types and
667 /// some policy objects The value_types between first_it and
668 /// last_it will be inserted into the container object. r_cmp_fn
669 /// will be copied by the cmp_fn object of the container object.
670 template<typename It>
671 tree(It first, It last, const cmp_fn& c)
673 { base_type::copy_from_range(first, last); }
675 tree(const tree& other)
676 : base_type((const base_type&)other) { }
682 operator=(const tree& other)
694 { base_type::swap(other); }
697 #undef PB_DS_TREE_BASE
698 #undef PB_DS_TREE_NODE_AND_IT_TRAITS
701 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \
702 detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
704 #define PB_DS_TRIE_BASE \
705 basic_branch<Key,Mapped,Tag, \
706 typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
707 typename __gnu_cxx::typelist::create2<_ATraits, \
708 PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
712 * A trie-based container.
714 * @tparam Key Key type.
715 * @tparam Mapped Map type.
716 * @tparam _ATraits Element access traits.
717 * @tparam Tag Instantiating data structure type,
719 * @tparam Node_Update Updates trie internal-nodes,
720 * restores invariants when invalidated.
721 * XXX See design::tree-based-containers::node invariants.
722 * @tparam _Alloc Allocator type.
724 * Base tag choice is pat_trie_tag.
726 * Base is basic_branch.
728 template<typename Key,
730 typename _ATraits = \
731 typename detail::default_trie_access_traits<Key>::type,
732 typename Tag = pat_trie_tag,
733 template<typename Node_CItr,
737 class Node_Update = null_node_update,
738 typename _Alloc = std::allocator<char> >
739 class trie : public PB_DS_TRIE_BASE
742 typedef PB_DS_TRIE_BASE base_type;
745 /// Element access traits type.
746 typedef _ATraits access_traits;
750 /// Constructor taking some policy objects. r_access_traits will
751 /// be copied by the _ATraits object of the container object.
752 trie(const access_traits& t)
755 /// Constructor taking __iterators to a range of value_types. The
756 /// value_types between first_it and last_it will be inserted into
757 /// the container object.
758 template<typename It>
759 trie(It first, It last)
760 { base_type::copy_from_range(first, last); }
762 /// Constructor taking __iterators to a range of value_types and
763 /// some policy objects. The value_types between first_it and
764 /// last_it will be inserted into the container object.
765 template<typename It>
766 trie(It first, It last, const access_traits& t)
768 { base_type::copy_from_range(first, last); }
770 trie(const trie& other)
771 : base_type((const base_type&)other) { }
777 operator=(const trie& other)
789 { base_type::swap(other); }
792 #undef PB_DS_TRIE_BASE
793 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS
797 * @defgroup list-based List-Based
798 * @ingroup containers-pbds
801 #define PB_DS_LU_BASE \
802 detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
803 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
807 * A list-update based associative container.
809 * @tparam Key Key type.
810 * @tparam Mapped Map type.
811 * @tparam Eq_Fn Equal functor.
812 * @tparam Update_Policy Update policy, determines when an element
813 * will be moved to the front of the list.
814 * @tparam _Alloc Allocator type.
816 * Base is detail::lu_map.
818 template<typename Key,
820 class Eq_Fn = typename detail::default_eq_fn<Key>::type,
821 class Update_Policy = detail::default_update_policy::type,
822 class _Alloc = std::allocator<char> >
823 class list_update : public PB_DS_LU_BASE
826 typedef typename PB_DS_LU_BASE base_type;
829 typedef list_update_tag container_category;
831 typedef Update_Policy update_policy;
835 /// Constructor taking __iterators to a range of value_types. The
836 /// value_types between first_it and last_it will be inserted into
837 /// the container object.
838 template<typename It>
839 list_update(It first, It last)
840 { base_type::copy_from_range(first, last); }
842 list_update(const list_update& other)
843 : base_type((const base_type&)other) { }
849 operator=(const list_update& other)
853 list_update tmp(other);
860 swap(list_update& other)
861 { base_type::swap(other); }
866 // @} group containers-pbds
867 } // namespace __gnu_pbds