3 // Copyright (C) 2005, 2006, 2009, 2010 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 <ext/typelist.h>
45 #include <ext/pb_ds/tag_and_trait.hpp>
46 #include <ext/pb_ds/detail/standard_policies.hpp>
47 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
48 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
52 /** @defgroup pbds Policy-Based Data Structures
55 * This is a library of policy-based elementary data structures:
56 * associative containers and priority queues. It is designed for
57 * high-performance, flexibility, semantic safety, and conformance
58 * to the corresponding containers in std (except for some points
59 * where it differs by design).
62 * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
67 #define PB_DS_BASE_C_DEC \
68 detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
70 /// An abstract basic associative container.
71 template<typename Key
,
76 class container_base
: public PB_DS_BASE_C_DEC
79 typedef typename PB_DS_BASE_C_DEC base_type
;
82 typedef Tag container_category
;
83 typedef Allocator allocator_type
;
84 typedef typename
allocator_type::size_type size_type
;
85 typedef typename
allocator_type::difference_type difference_type
;
88 typedef typename
allocator_type::template rebind
<Key
>::other::value_type key_type
;
89 typedef typename
allocator_type::template rebind
<key_type
>::other key_rebind
;
90 typedef typename
key_rebind::reference key_reference
;
91 typedef typename
key_rebind::const_reference const_key_reference
;
92 typedef typename
key_rebind::pointer key_pointer
;
93 typedef typename
key_rebind::const_pointer const_key_pointer
;
96 typedef Mapped mapped_type
;
97 typedef typename
allocator_type::template rebind
<mapped_type
>::other mapped_rebind
;
98 typedef typename
mapped_rebind::reference mapped_reference
;
99 typedef typename
mapped_rebind::const_reference const_mapped_reference
;
100 typedef typename
mapped_rebind::pointer mapped_pointer
;
101 typedef typename
mapped_rebind::const_pointer const_mapped_pointer
;
104 typedef typename
base_type::value_type value_type
;
105 typedef typename
allocator_type::template rebind
<value_type
>::other value_rebind
;
106 typedef typename
value_rebind::reference reference
;
107 typedef typename
value_rebind::const_reference const_reference
;
108 typedef typename
value_rebind::pointer pointer
;
109 typedef typename
value_rebind::const_pointer const_pointer
;
112 typedef typename
base_type::iterator iterator
;
113 typedef typename
base_type::const_iterator const_iterator
;
114 typedef typename
base_type::point_iterator point_iterator
;
115 typedef typename
base_type::const_point_iterator const_point_iterator
;
118 ~container_base() { }
121 #define PB_DS_CLASS_NAME container_base
122 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
123 #undef PB_DS_CLASS_NAME
126 #undef PB_DS_BASE_C_DEC
129 #define PB_DS_BASE_C_DEC \
130 container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
131 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
133 /// An abstract basic hash-based associative container.
134 template<typename Key
,
138 typename Resize_Policy
,
143 class basic_hash_table
: public PB_DS_BASE_C_DEC
146 typedef PB_DS_BASE_C_DEC base_type
;
150 ~basic_hash_table() { }
153 #define PB_DS_CLASS_NAME basic_hash_table
154 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
155 #undef PB_DS_CLASS_NAME
159 operator=(const base_type
&);
162 #undef PB_DS_BASE_C_DEC
165 #define PB_DS_BASE_C_DEC \
166 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
168 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
170 /// A concrete collision-chaining hash-based associative container.
171 template<typename Key
,
173 typename Hash_Fn
= typename
detail::default_hash_fn
<Key
>::type
,
174 typename Eq_Fn
= typename
detail::default_eq_fn
<Key
>::type
,
175 typename Comb_Hash_Fn
= detail::default_comb_hash_fn::type
,
176 typename Resize_Policy
= typename
detail::default_resize_policy
<Comb_Hash_Fn
>::type
,
177 bool Store_Hash
= detail::default_store_hash
,
178 typename Allocator
= std::allocator
<char> >
179 class cc_hash_table
: public PB_DS_BASE_C_DEC
182 typedef PB_DS_BASE_C_DEC base_type
;
185 typedef Hash_Fn hash_fn
;
187 typedef Resize_Policy resize_policy
;
188 typedef Comb_Hash_Fn comb_hash_fn
;
190 // Default constructor.
193 // Constructor taking some policy objects. r_hash_fn will be
194 // copied by the Hash_Fn object of the container object.
195 cc_hash_table(const hash_fn
& h
)
198 // Constructor taking some policy objects. r_hash_fn will be
199 // copied by the hash_fn object of the container object, and
200 // r_eq_fn will be copied by the eq_fn object of the container
202 cc_hash_table(const hash_fn
& h
, const eq_fn
& e
)
203 : base_type(h
, e
) { }
205 // Constructor taking some policy objects. r_hash_fn will be
206 // copied by the hash_fn object of the container object, r_eq_fn
207 // will be copied by the eq_fn object of the container object, and
208 // r_comb_hash_fn will be copied by the comb_hash_fn object of the
210 cc_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_hash_fn
& ch
)
211 : base_type(h
, e
, ch
) { }
213 // Constructor taking some policy objects. r_hash_fn will be
214 // copied by the hash_fn object of the container object, r_eq_fn
215 // will be copied by the eq_fn object of the container object,
216 // r_comb_hash_fn will be copied by the comb_hash_fn object of the
217 // container object, and r_resize_policy will be copied by the
218 // resize_policy object of the container object.
219 cc_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_hash_fn
& ch
,
220 const resize_policy
& rp
)
221 : base_type(h
, e
, ch
, rp
) { }
223 // Constructor taking __iterators to a range of value_types. The
224 // value_types between first_it and last_it will be inserted into
225 // the container object.
226 template<typename It
>
227 cc_hash_table(It first
, It last
)
228 { base_type::copy_from_range(first
, last
); }
230 // Constructor taking __iterators to a range of value_types and
231 // some policy objects. The value_types between first_it and
232 // last_it will be inserted into the container object.
233 template<typename It
>
234 cc_hash_table(It first
, It last
, const hash_fn
& h
)
236 { copy_from_range(first
, last
); }
238 // Constructor taking __iterators to a range of value_types and
239 // some policy objects The value_types between first_it and
240 // last_it will be inserted into the container object. r_hash_fn
241 // will be copied by the hash_fn object of the container object,
242 // and r_eq_fn will be copied by the eq_fn object of the container
244 template<typename It
>
245 cc_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
)
247 { copy_from_range(first
, last
); }
249 // Constructor taking __iterators to a range of value_types and
250 // some policy objects The value_types between first_it and
251 // last_it will be inserted into the container object. r_hash_fn
252 // will be copied by the hash_fn object of the container object,
253 // r_eq_fn will be copied by the eq_fn object of the container
254 // object, and r_comb_hash_fn will be copied by the comb_hash_fn
255 // object of the container object.
256 template<typename It
>
257 cc_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
258 const comb_hash_fn
& ch
)
259 : base_type(h
, e
, ch
)
260 { copy_from_range(first
, last
); }
262 // Constructor taking __iterators to a range of value_types and
263 // some policy objects The value_types between first_it and
264 // last_it will be inserted into the container object. r_hash_fn
265 // will be copied by the hash_fn object of the container object,
266 // r_eq_fn will be copied by the eq_fn object of the container
267 // object, r_comb_hash_fn will be copied by the comb_hash_fn
268 // object of the container object, and r_resize_policy will be
269 // copied by the resize_policy object of the container object.
270 template<typename It
>
271 cc_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
272 const comb_hash_fn
& ch
, const resize_policy
& rp
)
273 : base_type(h
, e
, ch
, rp
)
274 { copy_from_range(first
, last
); }
276 cc_hash_table(const cc_hash_table
& other
)
277 : base_type((const base_type
&)other
)
284 operator=(const cc_hash_table
& other
)
288 cc_hash_table
tmp(other
);
295 swap(cc_hash_table
& other
)
296 { base_type::swap(other
); }
299 #undef PB_DS_BASE_C_DEC
302 #define PB_DS_BASE_C_DEC \
303 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
305 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
307 /// A concrete general-probing hash-based associative container.
308 template<typename Key
,
310 typename Hash_Fn
= typename
detail::default_hash_fn
<Key
>::type
,
311 typename Eq_Fn
= typename
detail::default_eq_fn
<Key
>::type
,
312 typename Comb_Probe_Fn
= detail::default_comb_hash_fn::type
,
313 typename Probe_Fn
= typename
detail::default_probe_fn
<Comb_Probe_Fn
>::type
,
314 typename Resize_Policy
= typename
detail::default_resize_policy
<Comb_Probe_Fn
>::type
,
315 bool Store_Hash
= detail::default_store_hash
,
316 typename Allocator
= std::allocator
<char> >
317 class gp_hash_table
: public PB_DS_BASE_C_DEC
320 typedef PB_DS_BASE_C_DEC base_type
;
323 typedef Hash_Fn hash_fn
;
325 typedef Comb_Probe_Fn comb_probe_fn
;
326 typedef Probe_Fn probe_fn
;
327 typedef Resize_Policy resize_policy
;
329 // Default constructor.
332 // Constructor taking some policy objects. r_hash_fn will be
333 // copied by the hash_fn object of the container object.
334 gp_hash_table(const hash_fn
& h
)
337 // Constructor taking some policy objects. r_hash_fn will be
338 // copied by the hash_fn object of the container object, and
339 // r_eq_fn will be copied by the eq_fn object of the container
341 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
)
342 : base_type(h
, e
) { }
344 // Constructor taking some policy objects. r_hash_fn will be
345 // copied by the hash_fn object of the container object, r_eq_fn
346 // will be copied by the eq_fn object of the container object, and
347 // r_comb_probe_fn will be copied by the comb_probe_fn object of
348 // the container object.
349 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_probe_fn
& cp
)
350 : base_type(h
, e
, cp
) { }
352 // Constructor taking some policy objects. r_hash_fn will be
353 // copied by the hash_fn object of the container object, r_eq_fn
354 // will be copied by the eq_fn object of the container object,
355 // r_comb_probe_fn will be copied by the comb_probe_fn object of
356 // the container object, and r_probe_fn will be copied by the
357 // probe_fn object of the container object.
358 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_probe_fn
& cp
,
360 : base_type(h
, e
, cp
, p
) { }
362 // Constructor taking some policy objects. r_hash_fn will be
363 // copied by the hash_fn object of the container object, r_eq_fn
364 // will be copied by the eq_fn object of the container object,
365 // r_comb_probe_fn will be copied by the comb_probe_fn object of
366 // the container object, r_probe_fn will be copied by the probe_fn
367 // object of the container object, and r_resize_policy will be
368 // copied by the Resize_Policy object of the container object.
369 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_probe_fn
& cp
,
370 const probe_fn
& p
, const resize_policy
& rp
)
371 : base_type(h
, e
, cp
, p
, rp
) { }
373 // Constructor taking __iterators to a range of value_types. The
374 // value_types between first_it and last_it will be inserted into
375 // the container object.
376 template<typename It
>
377 gp_hash_table(It first
, It last
)
378 { base_type::copy_from_range(first
, last
); }
380 // Constructor taking __iterators to a range of value_types and
381 // some policy objects. The value_types between first_it and
382 // last_it will be inserted into the container object. r_hash_fn
383 // will be copied by the hash_fn object of the container object.
384 template<typename It
>
385 gp_hash_table(It first
, It last
, const hash_fn
& h
)
387 { base_type::copy_from_range(first
, last
); }
389 // Constructor taking __iterators to a range of value_types and
390 // some policy objects. The value_types between first_it and
391 // last_it will be inserted into the container object. r_hash_fn
392 // will be copied by the hash_fn object of the container object,
393 // and r_eq_fn will be copied by the eq_fn object of the container
395 template<typename It
>
396 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
)
398 { base_type::copy_from_range(first
, last
); }
400 // Constructor taking __iterators to a range of value_types and
401 // some policy objects. The value_types between first_it and
402 // last_it will be inserted into the container object. r_hash_fn
403 // will be copied by the hash_fn object of the container object,
404 // r_eq_fn will be copied by the eq_fn object of the container
405 // object, and r_comb_probe_fn will be copied by the comb_probe_fn
406 // object of the container object.
407 template<typename It
>
408 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
409 const comb_probe_fn
& cp
)
410 : base_type(h
, e
, cp
)
411 { base_type::copy_from_range(first
, last
); }
413 // Constructor taking __iterators to a range of value_types and
414 // some policy objects. The value_types between first_it and
415 // last_it will be inserted into the container object. r_hash_fn
416 // will be copied by the hash_fn object of the container object,
417 // r_eq_fn will be copied by the eq_fn object of the container
418 // object, r_comb_probe_fn will be copied by the comb_probe_fn
419 // object of the container object, and r_probe_fn will be copied
420 // by the probe_fn object of the container object.
421 template<typename It
>
422 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
423 const comb_probe_fn
& cp
, const probe_fn
& p
)
424 : base_type(h
, e
, cp
, p
)
425 { base_type::copy_from_range(first
, last
); }
427 // Constructor taking __iterators to a range of value_types and
428 // some policy objects. The value_types between first_it and
429 // last_it will be inserted into the container object. r_hash_fn
430 // will be copied by the hash_fn object of the container object,
431 // r_eq_fn will be copied by the eq_fn object of the container
432 // object, r_comb_probe_fn will be copied by the comb_probe_fn
433 // object of the container object, r_probe_fn will be copied by
434 // the probe_fn object of the container object, and
435 // r_resize_policy will be copied by the resize_policy object of
436 // the container object.
437 template<typename It
>
438 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
439 const comb_probe_fn
& cp
, const probe_fn
& p
,
440 const resize_policy
& rp
)
441 : base_type(h
, e
, cp
, p
, rp
)
442 { base_type::copy_from_range(first
, last
); }
444 gp_hash_table(const gp_hash_table
& other
)
445 : base_type((const base_type
&)other
)
452 operator=(const gp_hash_table
& other
)
456 gp_hash_table
tmp(other
);
463 swap(gp_hash_table
& other
)
464 { base_type::swap(other
); }
467 #undef PB_DS_BASE_C_DEC
470 #define PB_DS_BASE_C_DEC \
471 container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
473 /// An abstract basic tree-like (tree, trie) associative container.
474 template<typename Key
, typename Mapped
, typename Tag
,
475 typename Node_Update
, typename Policy_Tl
, typename Allocator
>
476 class basic_tree
: public PB_DS_BASE_C_DEC
479 typedef PB_DS_BASE_C_DEC base_type
;
482 typedef Node_Update node_update
;
488 #define PB_DS_CLASS_NAME basic_tree
489 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
490 #undef PB_DS_CLASS_NAME
493 #undef PB_DS_BASE_C_DEC
496 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
497 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
499 #define PB_DS_BASE_C_DEC \
500 basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
501 typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
503 /// A concrete basic tree-based associative container.
504 template<typename Key
, typename Mapped
, typename Cmp_Fn
= std::less
<Key
>,
505 typename Tag
= rb_tree_tag
,
506 template<typename Const_Node_Iterator
, typename Node_Iterator
, typename Cmp_Fn_
, typename Allocator_
>
507 class Node_Update
= __gnu_pbds::null_tree_node_update
,
508 typename Allocator
= std::allocator
<char> >
509 class tree
: public PB_DS_BASE_C_DEC
512 typedef PB_DS_BASE_C_DEC base_type
;
515 // Comparison functor type.
516 typedef Cmp_Fn cmp_fn
;
520 // Constructor taking some policy objects. r_cmp_fn will be copied
521 // by the Cmp_Fn object of the container object.
522 tree(const cmp_fn
& c
)
525 // Constructor taking __iterators to a range of value_types. The
526 // value_types between first_it and last_it will be inserted into
527 // the container object.
528 template<typename It
>
529 tree(It first
, It last
)
530 { base_type::copy_from_range(first
, last
); }
532 // Constructor taking __iterators to a range of value_types and
533 // some policy objects The value_types between first_it and
534 // last_it will be inserted into the container object. r_cmp_fn
535 // will be copied by the cmp_fn object of the container object.
536 template<typename It
>
537 tree(It first
, It last
, const cmp_fn
& c
)
539 { base_type::copy_from_range(first
, last
); }
541 tree(const tree
& other
)
542 : base_type((const base_type
&)other
) { }
548 operator=(const tree
& other
)
560 { base_type::swap(other
); }
563 #undef PB_DS_BASE_C_DEC
564 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
567 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
568 detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
570 #define PB_DS_BASE_C_DEC \
571 basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
572 typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
574 /// A concrete basic trie-based associative container.
575 template<typename Key
,
577 typename E_Access_Traits
= typename
detail::default_trie_e_access_traits
<Key
>::type
,
578 typename Tag
= pat_trie_tag
,
579 template<typename Const_Node_Iterator
,
580 typename Node_Iterator
,
581 typename E_Access_Traits_
,
583 class Node_Update
= null_trie_node_update
,
584 typename Allocator
= std::allocator
<char> >
585 class trie
: public PB_DS_BASE_C_DEC
588 typedef PB_DS_BASE_C_DEC base_type
;
591 // Element access traits type.
592 typedef E_Access_Traits e_access_traits
;
596 // Constructor taking some policy objects. r_e_access_traits will
597 // be copied by the E_Access_Traits object of the container
599 trie(const e_access_traits
& t
)
602 // Constructor taking __iterators to a range of value_types. The
603 // value_types between first_it and last_it will be inserted into
604 // the container object.
605 template<typename It
>
606 trie(It first
, It last
)
607 { base_type::copy_from_range(first
, last
); }
609 // Constructor taking __iterators to a range of value_types and
610 // some policy objects. The value_types between first_it and
611 // last_it will be inserted into the container object.
612 template<typename It
>
613 trie(It first
, It last
, const e_access_traits
& t
)
615 { base_type::copy_from_range(first
, last
); }
617 trie(const trie
& other
)
618 : base_type((const base_type
&)other
) { }
624 operator=(const trie
& other
)
636 { base_type::swap(other
); }
639 #undef PB_DS_BASE_C_DEC
640 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
643 #define PB_DS_BASE_C_DEC \
644 container_base<Key, Mapped, list_update_tag, \
645 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
647 /// A list-update based associative container.
648 template<typename Key
,
650 class Eq_Fn
= typename
detail::default_eq_fn
<Key
>::type
,
651 class Update_Policy
= detail::default_update_policy::type
,
652 class Allocator
= std::allocator
<char> >
653 class list_update
: public PB_DS_BASE_C_DEC
656 typedef PB_DS_BASE_C_DEC base_type
;
660 typedef Update_Policy update_policy
;
661 typedef Allocator allocator
;
665 // Constructor taking __iterators to a range of value_types. The
666 // value_types between first_it and last_it will be inserted into
667 // the container object.
668 template<typename It
>
669 list_update(It first
, It last
)
670 { base_type::copy_from_range(first
, last
); }
672 list_update(const list_update
& other
)
673 : base_type((const base_type
&)other
) { }
679 operator=(const list_update
& other
)
683 list_update
tmp(other
);
690 swap(list_update
& other
)
691 { base_type::swap(other
); }
694 #undef PB_DS_BASE_C_DEC
697 } // namespace __gnu_pbds