libstdc++
assoc_container.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 Free Software Foundation, Inc.
4//
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
9// version.
10
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.
15
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.
19
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/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
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
34// warranty.
35
36/**
37 * @file assoc_container.hpp
38 * Contains associative containers.
39 */
40
41#ifndef PB_DS_ASSOC_CNTNR_HPP
42#define PB_DS_ASSOC_CNTNR_HPP
43
44#include <bits/c++config.h>
45#include <ext/typelist.h>
50
51namespace __gnu_pbds
52{
53 /**
54 * @defgroup containers-pbds Containers
55 * @ingroup pbds
56 * @{
57 */
58
59 /**
60 * @defgroup hash-based Hash-Based
61 * @ingroup containers-pbds
62 * @{
63 */
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
69
70 /**
71 * @defgroup hash-detail Base and Policy Classes
72 * @ingroup hash-based
73 */
74
75 /**
76 * A hashed container abstraction.
77 *
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,
86 * see container_tag.
87 * @tparam Policy_TL Policy typelist.
88 * @tparam _Alloc Allocator type.
89 *
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.
92 *
93 * Base choices are: detail::cc_ht_map, detail::gp_ht_map
94 */
95 template<typename Key,
96 typename Mapped,
97 typename Hash_Fn,
98 typename Eq_Fn,
99 typename Resize_Policy,
100 bool Store_Hash,
101 typename Tag,
102 typename Policy_Tl,
103 typename _Alloc>
104 class basic_hash_table : public PB_DS_HASH_BASE
105 {
106 private:
107 typedef typename PB_DS_HASH_BASE base_type;
108
109 public:
110 virtual
112
113 protected:
114 basic_hash_table() { }
115
117 : base_type((const base_type&)other) { }
118
119 template<typename T0>
120 basic_hash_table(T0 t0) : base_type(t0) { }
121
122 template<typename T0, typename T1>
123 basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
124
125 template<typename T0, typename T1, typename T2>
126 basic_hash_table(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
127
128 template<typename T0, typename T1, typename T2, typename T3>
129 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3)
130 : base_type(t0, t1, t2, t3) { }
131
132 template<typename T0, typename T1, typename T2, typename T3, typename T4>
133 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
134 : base_type(t0, t1, t2, t3, t4) { }
135
136 template<typename T0, typename T1, typename T2, typename T3, typename T4,
137 typename T5>
138 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
139 : base_type(t0, t1, t2, t3, t4, t5) { }
140
141 template<typename T0, typename T1, typename T2, typename T3, typename T4,
142 typename T5, typename T6>
143 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
144 : base_type(t0, t1, t2, t3, t4, t5, t6) { }
145
146 template<typename T0, typename T1, typename T2, typename T3, typename T4,
147 typename T5, typename T6, typename T7>
148 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6, T7 t7)
149 : base_type(t0, t1, t2, t3, t4, t5, t6, t7) { }
150
151 template<typename T0, typename T1, typename T2, typename T3, typename T4,
152 typename T5, typename T6, typename T7, typename T8>
153 basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
154 T7 t7, T8 t8)
155 : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
156 { }
157
158 private:
160 operator=(const base_type&);
161 };
162
163#undef PB_DS_HASH_BASE
164
165
166#define PB_DS_CC_HASH_BASE \
167 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
168 cc_hash_tag, \
169 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
170
171
172 /**
173 * A collision-chaining hash-based associative container.
174 *
175 * @tparam Key Key type.
176 * @tparam Mapped Map type.
177 * @tparam Hash_Fn Hashing functor.
178 * @tparam Eq_Fn Equal functor.
179 * @tparam Comb_Hash_Fn Combining hash functor.
180 * If Hash_Fn is not null_type, then this
181 * is the ranged-hash functor; otherwise,
182 * this is the range-hashing functor.
183 * XXX(See Design::Hash-Based Containers::Hash Policies.)
184 * @tparam Resize_Policy Resizes hash.
185 * @tparam Store_Hash Indicates whether the hash value
186 * will be stored along with each key.
187 * If Hash_Fn is null_type, then the
188 * container will not compile if this
189 * value is true
190 * @tparam _Alloc Allocator type.
191 *
192 * Base tag choices are: cc_hash_tag.
193 *
194 * Base is basic_hash_table.
195 */
196 template<typename Key,
197 typename Mapped,
198 typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
199 typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
200 typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
201 typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
202 bool Store_Hash = detail::default_store_hash,
203 typename _Alloc = std::allocator<char> >
204 class cc_hash_table : public PB_DS_CC_HASH_BASE
205 {
206 private:
207 typedef PB_DS_CC_HASH_BASE base_type;
208
209 public:
211 typedef Hash_Fn hash_fn;
212 typedef Eq_Fn eq_fn;
213 typedef Resize_Policy resize_policy;
214 typedef Comb_Hash_Fn comb_hash_fn;
215
216 /// Default constructor.
218
219 /// Constructor taking some policy objects. r_hash_fn will be
220 /// copied by the Hash_Fn object of the container object.
221 cc_hash_table(const hash_fn& h)
222 : base_type(h) { }
223
224 /// Constructor taking some policy objects. r_hash_fn will be
225 /// copied by the hash_fn object of the container object, and
226 /// r_eq_fn will be copied by the eq_fn object of the container
227 /// object.
228 cc_hash_table(const hash_fn& h, const eq_fn& e)
229 : base_type(h, e) { }
230
231 /// Constructor taking some policy objects. r_hash_fn will be
232 /// copied by the hash_fn object of the container object, r_eq_fn
233 /// will be copied by the eq_fn object of the container object,
234 /// and r_comb_hash_fn will be copied by the comb_hash_fn object
235 /// of the container object.
236 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
237 : base_type(h, e, ch) { }
238
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 /// r_comb_hash_fn will be copied by the comb_hash_fn object of
243 /// the container object, and r_resize_policy will be copied by
244 /// the resize_policy object of the container object.
245 cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
246 const resize_policy& rp)
247 : base_type(h, e, ch, rp) { }
248
249 /// Constructor taking __iterators to a range of value_types. The
250 /// value_types between first_it and last_it will be inserted into
251 /// the container object.
252 template<typename It>
253 cc_hash_table(It first, It last)
254 { base_type::copy_from_range(first, last); }
255
256 /// Constructor taking __iterators to a range of value_types and
257 /// some policy objects. The value_types between first_it and
258 /// last_it will be inserted into the container object.
259 template<typename It>
260 cc_hash_table(It first, It last, const hash_fn& h)
261 : base_type(h)
262 { this->copy_from_range(first, last); }
263
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. r_hash_fn
267 /// will be copied by the hash_fn object of the container object,
268 /// and r_eq_fn will be copied by the eq_fn object of the
269 /// container object.
270 template<typename It>
271 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
272 : base_type(h, e)
273 { this->copy_from_range(first, last); }
274
275 /// Constructor taking __iterators to a range of value_types and
276 /// some policy objects The value_types between first_it and
277 /// last_it will be inserted into the container object. r_hash_fn
278 /// will be copied by the hash_fn object of the container object,
279 /// r_eq_fn will be copied by the eq_fn object of the container
280 /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
281 /// object of the container object.
282 template<typename It>
283 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
284 const comb_hash_fn& ch)
285 : base_type(h, e, ch)
286 { this->copy_from_range(first, last); }
287
288 /// Constructor taking __iterators to a range of value_types and
289 /// some policy objects The value_types between first_it and
290 /// last_it will be inserted into the container object. r_hash_fn
291 /// will be copied by the hash_fn object of the container object,
292 /// r_eq_fn will be copied by the eq_fn object of the container
293 /// object, r_comb_hash_fn will be copied by the comb_hash_fn
294 /// object of the container object, and r_resize_policy will be
295 /// copied by the resize_policy object of the container object.
296 template<typename It>
297 cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
298 const comb_hash_fn& ch, const resize_policy& rp)
299 : base_type(h, e, ch, rp)
300 { this->copy_from_range(first, last); }
301
302 cc_hash_table(const cc_hash_table& other)
303 : base_type((const base_type&)other)
304 { }
305
306 virtual
307 ~cc_hash_table() { }
308
310 operator=(const cc_hash_table& other)
311 {
312 if (this != &other)
313 {
314 cc_hash_table tmp(other);
315 swap(tmp);
316 }
317 return *this;
318 }
319
320 void
321 swap(cc_hash_table& other)
322 { base_type::swap(other); }
323 };
324
325#undef PB_DS_CC_HASH_BASE
326
327
328#define PB_DS_GP_HASH_BASE \
329 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
330 gp_hash_tag, \
331 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
332
333
334 /**
335 * A general-probing hash-based associative container.
336 *
337 * @tparam Key Key type.
338 * @tparam Mapped Map type.
339 * @tparam Hash_Fn Hashing functor.
340 * @tparam Eq_Fn Equal functor.
341 * @tparam Comb_Probe_Fn Combining probe functor.
342 * If Hash_Fn is not null_type, then this
343 * is the ranged-probe functor; otherwise,
344 * this is the range-hashing functor.
345 * XXX See Design::Hash-Based Containers::Hash Policies.
346 * @tparam Probe_Fn Probe functor.
347 * @tparam Resize_Policy Resizes hash.
348 * @tparam Store_Hash Indicates whether the hash value
349 * will be stored along with each key.
350 * If Hash_Fn is null_type, then the
351 * container will not compile if this
352 * value is true
353 * @tparam _Alloc Allocator type.
354 *
355 * Base tag choices are: gp_hash_tag.
356 *
357 * Base is basic_hash_table.
358 */
359 template<typename Key,
360 typename Mapped,
361 typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
362 typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
363 typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
364 typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
365 typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
366 bool Store_Hash = detail::default_store_hash,
367 typename _Alloc = std::allocator<char> >
368 class gp_hash_table : public PB_DS_GP_HASH_BASE
369 {
370 private:
371 typedef PB_DS_GP_HASH_BASE base_type;
372
373 public:
375 typedef Hash_Fn hash_fn;
376 typedef Eq_Fn eq_fn;
377 typedef Comb_Probe_Fn comb_probe_fn;
378 typedef Probe_Fn probe_fn;
379 typedef Resize_Policy resize_policy;
380
381 /// Default constructor.
383
384 /// Constructor taking some policy objects. r_hash_fn will be
385 /// copied by the hash_fn object of the container object.
386 gp_hash_table(const hash_fn& h)
387 : base_type(h) { }
388
389 /// Constructor taking some policy objects. r_hash_fn will be
390 /// copied by the hash_fn object of the container object, and
391 /// r_eq_fn will be copied by the eq_fn object of the container
392 /// object.
393 gp_hash_table(const hash_fn& h, const eq_fn& e)
394 : base_type(h, e) { }
395
396 /// Constructor taking some policy objects. r_hash_fn will be
397 /// copied by the hash_fn object of the container object, r_eq_fn
398 /// will be copied by the eq_fn object of the container object,
399 /// and r_comb_probe_fn will be copied by the comb_probe_fn object
400 /// of the container object.
401 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
402 : base_type(h, e, cp) { }
403
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 /// r_comb_probe_fn will be copied by the comb_probe_fn object of
408 /// the container object, and r_probe_fn will be copied by the
409 /// probe_fn object of the container object.
410 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
411 const probe_fn& p)
412 : base_type(h, e, cp, p) { }
413
414 /// Constructor taking some policy objects. r_hash_fn will be
415 /// copied by the hash_fn object of the container object, r_eq_fn
416 /// will be copied by the eq_fn object of the container object,
417 /// r_comb_probe_fn will be copied by the comb_probe_fn object of
418 /// the container object, r_probe_fn will be copied by the
419 /// probe_fn object of the container object, and r_resize_policy
420 /// will be copied by the Resize_Policy object of the container
421 /// object.
422 gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
423 const probe_fn& p, const resize_policy& rp)
424 : base_type(h, e, cp, p, rp) { }
425
426 /// Constructor taking __iterators to a range of value_types. The
427 /// value_types between first_it and last_it will be inserted into
428 /// the container object.
429 template<typename It>
430 gp_hash_table(It first, It last)
431 { base_type::copy_from_range(first, last); }
432
433 /// Constructor taking __iterators to a range of value_types and
434 /// some policy objects. The value_types between first_it and
435 /// last_it will be inserted into the container object. r_hash_fn
436 /// will be copied by the hash_fn object of the container object.
437 template<typename It>
438 gp_hash_table(It first, It last, const hash_fn& h)
439 : base_type(h)
440 { base_type::copy_from_range(first, last); }
441
442 /// Constructor taking __iterators to a range of value_types and
443 /// some policy objects. The value_types between first_it and
444 /// last_it will be inserted into the container object. r_hash_fn
445 /// will be copied by the hash_fn object of the container object,
446 /// and r_eq_fn will be copied by the eq_fn object of the
447 /// container object.
448 template<typename It>
449 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
450 : base_type(h, e)
451 { base_type::copy_from_range(first, last); }
452
453 /// Constructor taking __iterators to a range of value_types and
454 /// some policy objects. The value_types between first_it and
455 /// last_it will be inserted into the container object. r_hash_fn
456 /// will be copied by the hash_fn object of the container object,
457 /// r_eq_fn will be copied by the eq_fn object of the container
458 /// object, and r_comb_probe_fn will be copied by the
459 /// comb_probe_fn object of the container object.
460 template<typename It>
461 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
462 const comb_probe_fn& cp)
463 : base_type(h, e, cp)
464 { base_type::copy_from_range(first, last); }
465
466 /// Constructor taking __iterators to a range of value_types and
467 /// some policy objects. The value_types between first_it and
468 /// last_it will be inserted into the container object. r_hash_fn
469 /// will be copied by the hash_fn object of the container object,
470 /// r_eq_fn will be copied by the eq_fn object of the container
471 /// object, r_comb_probe_fn will be copied by the comb_probe_fn
472 /// object of the container object, and r_probe_fn will be copied
473 /// by the probe_fn object of the container object.
474 template<typename It>
475 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
476 const comb_probe_fn& cp, const probe_fn& p)
477 : base_type(h, e, cp, p)
478 { base_type::copy_from_range(first, last); }
479
480 /// Constructor taking __iterators to a range of value_types and
481 /// some policy objects. The value_types between first_it and
482 /// last_it will be inserted into the container object. r_hash_fn
483 /// will be copied by the hash_fn object of the container object,
484 /// r_eq_fn will be copied by the eq_fn object of the container
485 /// object, r_comb_probe_fn will be copied by the comb_probe_fn
486 /// object of the container object, r_probe_fn will be copied by
487 /// the probe_fn object of the container object, and
488 /// r_resize_policy will be copied by the resize_policy object of
489 /// the container object.
490 template<typename It>
491 gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
492 const comb_probe_fn& cp, const probe_fn& p,
493 const resize_policy& rp)
494 : base_type(h, e, cp, p, rp)
495 { base_type::copy_from_range(first, last); }
496
497 gp_hash_table(const gp_hash_table& other)
498 : base_type((const base_type&)other)
499 { }
500
501 virtual
502 ~gp_hash_table() { }
503
505 operator=(const gp_hash_table& other)
506 {
507 if (this != &other)
508 {
509 gp_hash_table tmp(other);
510 swap(tmp);
511 }
512 return *this;
513 }
514
515 void
516 swap(gp_hash_table& other)
517 { base_type::swap(other); }
518 };
519 ///@} hash-based
520#undef PB_DS_GP_HASH_BASE
521
522
523 /**
524 * @defgroup branch-based Branch-Based
525 * @ingroup containers-pbds
526 * @{
527 */
528#define PB_DS_BRANCH_BASE \
529 detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
530
531 /**
532 * @defgroup branch-detail Base and Policy Classes
533 * @ingroup branch-based
534 */
535
536 /**
537 * A branched, tree-like (tree, trie) container abstraction.
538 *
539 * @tparam Key Key type.
540 * @tparam Mapped Map type.
541 * @tparam Tag Instantiating data structure type,
542 * see container_tag.
543 * @tparam Node_Update Updates nodes, restores invariants.
544 * @tparam Policy_TL Policy typelist.
545 * @tparam _Alloc Allocator type.
546 *
547 * Base is dispatched at compile time via Tag, from the following
548 * choices: tree_tag, trie_tag, and their descendants.
549 *
550 * Base choices are: detail::ov_tree_map, detail::rb_tree_map,
551 * detail::splay_tree_map, and detail::pat_trie_map.
552 */
553 template<typename Key, typename Mapped, typename Tag,
554 typename Node_Update, typename Policy_Tl, typename _Alloc>
555 class basic_branch : public PB_DS_BRANCH_BASE
556 {
557 private:
558 typedef typename PB_DS_BRANCH_BASE base_type;
559
560 public:
561 typedef Node_Update node_update;
562
563 virtual
564 ~basic_branch() { }
565
566 protected:
567 basic_branch() { }
568
569 basic_branch(const basic_branch& other)
570 : base_type((const base_type&)other) { }
571
572 template<typename T0>
573 basic_branch(T0 t0) : base_type(t0) { }
574
575 template<typename T0, typename T1>
576 basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
577
578 template<typename T0, typename T1, typename T2>
579 basic_branch(T0 t0, T1 t1, T2 t2) : base_type(t0, t1, t2) { }
580
581 template<typename T0, typename T1, typename T2, typename T3>
582 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3)
583 : base_type(t0, t1, t2, t3) { }
584
585 template<typename T0, typename T1, typename T2, typename T3, typename T4>
586 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4)
587 : base_type(t0, t1, t2, t3, t4) { }
588
589 template<typename T0, typename T1, typename T2, typename T3, typename T4,
590 typename T5>
591 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5)
592 : base_type(t0, t1, t2, t3, t4, t5) { }
593
594 template<typename T0, typename T1, typename T2, typename T3, typename T4,
595 typename T5, typename T6>
596 basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
597 : base_type(t0, t1, t2, t3, t4, t5, t6) { }
598 };
599#undef PB_DS_BRANCH_BASE
600
601
602#define PB_DS_TREE_NODE_AND_IT_TRAITS \
603 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
604
605#define PB_DS_TREE_BASE \
606 basic_branch<Key,Mapped, Tag, \
607 typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
608 typename __gnu_cxx::typelist::create2<Cmp_Fn, \
609 PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
610
611
612 /**
613 * A tree-based container.
614 *
615 * @tparam Key Key type.
616 * @tparam Mapped Map type.
617 * @tparam Cmp_Fn Comparison functor.
618 * @tparam Tag Instantiating data structure type,
619 * see container_tag.
620 * @tparam Node_Update Updates tree internal-nodes,
621 * restores invariants when invalidated.
622 * XXX See design::tree-based-containers::node invariants.
623 * @tparam _Alloc Allocator type.
624 *
625 * Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
626 *
627 * Base is basic_branch.
628 */
629 template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
630 typename Tag = rb_tree_tag,
631 template<typename Node_CItr, typename Node_Itr,
632 typename Cmp_Fn_, typename _Alloc_>
633 class Node_Update = null_node_update,
634 typename _Alloc = std::allocator<char> >
635 class tree : public PB_DS_TREE_BASE
636 {
637 private:
638 typedef PB_DS_TREE_BASE base_type;
639
640 public:
641 /// Comparison functor type.
642 typedef Cmp_Fn cmp_fn;
643
644 tree() { }
645
646 /// Constructor taking some policy objects. r_cmp_fn will be
647 /// copied by the Cmp_Fn object of the container object.
648 tree(const cmp_fn& c)
649 : base_type(c) { }
650
651 /// Constructor taking __iterators to a range of value_types. The
652 /// value_types between first_it and last_it will be inserted into
653 /// the container object.
654 template<typename It>
655 tree(It first, It last)
656 { base_type::copy_from_range(first, last); }
657
658 /// Constructor taking __iterators to a range of value_types and
659 /// some policy objects The value_types between first_it and
660 /// last_it will be inserted into the container object. r_cmp_fn
661 /// will be copied by the cmp_fn object of the container object.
662 template<typename It>
663 tree(It first, It last, const cmp_fn& c)
664 : base_type(c)
665 { base_type::copy_from_range(first, last); }
666
667 tree(const tree& other)
668 : base_type((const base_type&)other) { }
669
670 virtual
671 ~tree() { }
672
673 tree&
674 operator=(const tree& other)
675 {
676 if (this != &other)
677 {
678 tree tmp(other);
679 swap(tmp);
680 }
681 return *this;
682 }
683
684 void
685 swap(tree& other)
686 { base_type::swap(other); }
687 };
688
689#undef PB_DS_TREE_BASE
690#undef PB_DS_TREE_NODE_AND_IT_TRAITS
691
692
693#define PB_DS_TRIE_NODE_AND_IT_TRAITS \
694 detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
695
696#define PB_DS_TRIE_BASE \
697 basic_branch<Key,Mapped,Tag, \
698 typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
699 typename __gnu_cxx::typelist::create2<_ATraits, \
700 PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
701
702
703 /**
704 * A trie-based container.
705 *
706 * @tparam Key Key type.
707 * @tparam Mapped Map type.
708 * @tparam _ATraits Element access traits.
709 * @tparam Tag Instantiating data structure type,
710 * see container_tag.
711 * @tparam Node_Update Updates trie internal-nodes,
712 * restores invariants when invalidated.
713 * XXX See design::tree-based-containers::node invariants.
714 * @tparam _Alloc Allocator type.
715 *
716 * Base tag choice is pat_trie_tag.
717 *
718 * Base is basic_branch.
719 */
720 template<typename Key,
721 typename Mapped,
722 typename _ATraits = \
723 typename detail::default_trie_access_traits<Key>::type,
724 typename Tag = pat_trie_tag,
725 template<typename Node_CItr,
726 typename Node_Itr,
727 typename _ATraits_,
728 typename _Alloc_>
729 class Node_Update = null_node_update,
730 typename _Alloc = std::allocator<char> >
731 class trie : public PB_DS_TRIE_BASE
732 {
733 private:
734 typedef PB_DS_TRIE_BASE base_type;
735
736 public:
737 /// Element access traits type.
738 typedef _ATraits access_traits;
739
740 trie() { }
741
742 /// Constructor taking some policy objects. r_access_traits will
743 /// be copied by the _ATraits object of the container object.
745 : base_type(t) { }
746
747 /// Constructor taking __iterators to a range of value_types. The
748 /// value_types between first_it and last_it will be inserted into
749 /// the container object.
750 template<typename It>
751 trie(It first, It last)
752 { base_type::copy_from_range(first, last); }
753
754 /// Constructor taking __iterators to a range of value_types and
755 /// some policy objects. The value_types between first_it and
756 /// last_it will be inserted into the container object.
757 template<typename It>
758 trie(It first, It last, const access_traits& t)
759 : base_type(t)
760 { base_type::copy_from_range(first, last); }
761
762 trie(const trie& other)
763 : base_type((const base_type&)other) { }
764
765 virtual
766 ~trie() { }
767
768 trie&
769 operator=(const trie& other)
770 {
771 if (this != &other)
772 {
773 trie tmp(other);
774 swap(tmp);
775 }
776 return *this;
777 }
778
779 void
780 swap(trie& other)
781 { base_type::swap(other); }
782 };
783 ///@} branch-based
784#undef PB_DS_TRIE_BASE
785#undef PB_DS_TRIE_NODE_AND_IT_TRAITS
786
787
788 /**
789 * @defgroup list-based List-Based
790 * @ingroup containers-pbds
791 * @{
792 */
793#define PB_DS_LU_BASE \
794 detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag, \
795 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
796
797
798 /**
799 * A list-update based associative container.
800 *
801 * @tparam Key Key type.
802 * @tparam Mapped Map type.
803 * @tparam Eq_Fn Equal functor.
804 * @tparam Update_Policy Update policy, determines when an element
805 * will be moved to the front of the list.
806 * @tparam _Alloc Allocator type.
807 *
808 * Base is detail::lu_map.
809 */
810 template<typename Key,
811 typename Mapped,
812 class Eq_Fn = typename detail::default_eq_fn<Key>::type,
813 class Update_Policy = detail::default_update_policy::type,
814 class _Alloc = std::allocator<char> >
815 class list_update : public PB_DS_LU_BASE
816 {
817 private:
818 typedef typename PB_DS_LU_BASE base_type;
819
820 public:
822 typedef Eq_Fn eq_fn;
823 typedef Update_Policy update_policy;
824
825 list_update() { }
826
827 /// Constructor taking __iterators to a range of value_types. The
828 /// value_types between first_it and last_it will be inserted into
829 /// the container object.
830 template<typename It>
831 list_update(It first, It last)
832 { base_type::copy_from_range(first, last); }
833
834 list_update(const list_update& other)
835 : base_type((const base_type&)other) { }
836
837 virtual
838 ~list_update() { }
839
840 list_update&
841 operator=(const list_update& other)
842 {
843 if (this !=& other)
844 {
845 list_update tmp(other);
846 swap(tmp);
847 }
848 return *this;
849 }
850
851 void
852 swap(list_update& other)
853 { base_type::swap(other); }
854 };
855 ///@} list-based
856#undef PB_DS_LU_BASE
857
858 /// @} group containers-pbds
859} // namespace __gnu_pbds
860
861#endif
GNU extensions for policy-based data structures for public use.
The standard allocator, as per C++03 [20.4.1].
Definition: allocator.h:125
One of the comparison functors.
Definition: stl_function.h:366
cc_hash_table(It first, It last, const hash_fn &h, const eq_fn &e, const comb_hash_fn &ch)
Constructor taking __iterators to a range of value_types and some policy objects The value_types betw...
cc_hash_table(const hash_fn &h, const eq_fn &e)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
cc_hash_table(const hash_fn &h, const eq_fn &e, const comb_hash_fn &ch)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
cc_hash_table(It first, It last, const hash_fn &h, const eq_fn &e, const comb_hash_fn &ch, const resize_policy &rp)
Constructor taking __iterators to a range of value_types and some policy objects The value_types betw...
cc_hash_table(It first, It last, const hash_fn &h)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
cc_hash_table()
Default constructor.
cc_hash_table(It first, It last)
Constructor taking __iterators to a range of value_types. The value_types between first_it and last_i...
cc_hash_table(It first, It last, const hash_fn &h, const eq_fn &e)
Constructor taking __iterators to a range of value_types and some policy objects The value_types betw...
cc_hash_table(const hash_fn &h)
Constructor taking some policy objects. r_hash_fn will be copied by the Hash_Fn object of the contain...
cc_hash_table(const hash_fn &h, const eq_fn &e, const comb_hash_fn &ch, const resize_policy &rp)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
gp_hash_table(const hash_fn &h, const eq_fn &e, const comb_probe_fn &cp, const probe_fn &p)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
gp_hash_table(It first, It last, const hash_fn &h, const eq_fn &e, const comb_probe_fn &cp, const probe_fn &p, const resize_policy &rp)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
gp_hash_table()
Default constructor.
gp_hash_table(It first, It last, const hash_fn &h, const eq_fn &e, const comb_probe_fn &cp, const probe_fn &p)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
gp_hash_table(It first, It last, const hash_fn &h, const eq_fn &e, const comb_probe_fn &cp)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
gp_hash_table(It first, It last)
Constructor taking __iterators to a range of value_types. The value_types between first_it and last_i...
gp_hash_table(const hash_fn &h, const eq_fn &e)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
gp_hash_table(const hash_fn &h, const eq_fn &e, const comb_probe_fn &cp, const probe_fn &p, const resize_policy &rp)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
gp_hash_table(It first, It last, const hash_fn &h)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
gp_hash_table(const hash_fn &h)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
gp_hash_table(It first, It last, const hash_fn &h, const eq_fn &e)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
gp_hash_table(const hash_fn &h, const eq_fn &e, const comb_probe_fn &cp)
Constructor taking some policy objects. r_hash_fn will be copied by the hash_fn object of the contain...
tree(const cmp_fn &c)
Constructor taking some policy objects. r_cmp_fn will be copied by the Cmp_Fn object of the container...
tree(It first, It last, const cmp_fn &c)
Constructor taking __iterators to a range of value_types and some policy objects The value_types betw...
tree(It first, It last)
Constructor taking __iterators to a range of value_types. The value_types between first_it and last_i...
Cmp_Fn cmp_fn
Comparison functor type.
trie(It first, It last)
Constructor taking __iterators to a range of value_types. The value_types between first_it and last_i...
trie(It first, It last, const access_traits &t)
Constructor taking __iterators to a range of value_types and some policy objects. The value_types bet...
trie(const access_traits &t)
Constructor taking some policy objects. r_access_traits will be copied by the _ATraits object of the ...
_ATraits access_traits
Element access traits type.
list_update(It first, It last)
Constructor taking __iterators to a range of value_types. The value_types between first_it and last_i...
A resize policy which delegates operations to size and trigger policies.
Collision-chaining hash.
General-probing hash.
A null node updator, indicating that no node updates are required.
std::tr1::hash< Key > type
Dispatched type.
std::equal_to< Key > type
Dispatched type.
direct_mask_range_hashing type
Dispatched type.
hash_standard_resize_policy< size_policy_type, trigger, false, size_type > type
Dispatched type.
lu_move_to_front_policy type
Dispatched type.
cond_type::__type type
Dispatched type.