3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
33 // Permission to use, copy, modify, sell, and distribute this software
34 // is hereby granted without fee, provided that the above copyright
35 // notice appears in all copies, and that both that copyright notice
36 // and this permission notice appear in supporting documentation. None
37 // of the above authors, nor IBM Haifa Research Laboratories, make any
38 // representation about the suitability of this software for any
39 // purpose. It is provided "as is" without express or implied
43 * @file assoc_container.hpp
44 * Contains associative containers.
47 #ifndef PB_DS_ASSOC_CNTNR_HPP
48 #define PB_DS_ASSOC_CNTNR_HPP
50 #include <ext/typelist.h>
51 #include <ext/pb_ds/tag_and_trait.hpp>
52 #include <ext/pb_ds/detail/standard_policies.hpp>
53 #include <ext/pb_ds/detail/container_base_dispatch.hpp>
54 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
58 #define PB_DS_BASE_C_DEC \
59 detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
61 // An abstract basic associative container.
62 template<typename Key
,
67 class container_base
: public PB_DS_BASE_C_DEC
70 typedef typename PB_DS_BASE_C_DEC base_type
;
73 typedef Tag container_category
;
74 typedef Allocator allocator_type
;
75 typedef typename
allocator_type::size_type size_type
;
76 typedef typename
allocator_type::difference_type difference_type
;
79 typedef typename
allocator_type::template rebind
<Key
>::other::value_type key_type
;
80 typedef typename
allocator_type::template rebind
<key_type
>::other key_rebind
;
81 typedef typename
key_rebind::reference key_reference
;
82 typedef typename
key_rebind::const_reference const_key_reference
;
83 typedef typename
key_rebind::pointer key_pointer
;
84 typedef typename
key_rebind::const_pointer const_key_pointer
;
87 typedef Mapped mapped_type
;
88 typedef typename
allocator_type::template rebind
<mapped_type
>::other mapped_rebind
;
89 typedef typename
mapped_rebind::reference mapped_reference
;
90 typedef typename
mapped_rebind::const_reference const_mapped_reference
;
91 typedef typename
mapped_rebind::pointer mapped_pointer
;
92 typedef typename
mapped_rebind::const_pointer const_mapped_pointer
;
95 typedef typename
base_type::value_type value_type
;
96 typedef typename
allocator_type::template rebind
<value_type
>::other value_rebind
;
97 typedef typename
value_rebind::reference reference
;
98 typedef typename
value_rebind::const_reference const_reference
;
99 typedef typename
value_rebind::pointer pointer
;
100 typedef typename
value_rebind::const_pointer const_pointer
;
103 typedef typename
base_type::iterator iterator
;
104 typedef typename
base_type::const_iterator const_iterator
;
105 typedef typename
base_type::point_iterator point_iterator
;
106 typedef typename
base_type::const_point_iterator const_point_iterator
;
109 ~container_base() { }
112 #define PB_DS_CLASS_NAME container_base
113 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
114 #undef PB_DS_CLASS_NAME
117 #undef PB_DS_BASE_C_DEC
120 #define PB_DS_BASE_C_DEC \
121 container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
122 typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
124 // An abstract basic hash-based associative container.
125 template<typename Key
,
129 typename Resize_Policy
,
134 class basic_hash_table
: public PB_DS_BASE_C_DEC
137 typedef PB_DS_BASE_C_DEC base_type
;
141 ~basic_hash_table() { }
144 #define PB_DS_CLASS_NAME basic_hash_table
145 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
146 #undef PB_DS_CLASS_NAME
150 operator=(const base_type
&);
153 #undef PB_DS_BASE_C_DEC
156 #define PB_DS_BASE_C_DEC \
157 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
159 typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, Allocator>
161 // A concrete collision-chaining hash-based associative container.
162 template<typename Key
,
164 typename Hash_Fn
= typename
detail::default_hash_fn
<Key
>::type
,
165 typename Eq_Fn
= typename
detail::default_eq_fn
<Key
>::type
,
166 typename Comb_Hash_Fn
= detail::default_comb_hash_fn::type
,
167 typename Resize_Policy
= typename
detail::default_resize_policy
<Comb_Hash_Fn
>::type
,
168 bool Store_Hash
= detail::default_store_hash
,
169 typename Allocator
= std::allocator
<char> >
170 class cc_hash_table
: public PB_DS_BASE_C_DEC
173 typedef PB_DS_BASE_C_DEC base_type
;
176 typedef Hash_Fn hash_fn
;
178 typedef Resize_Policy resize_policy
;
179 typedef Comb_Hash_Fn comb_hash_fn
;
181 // Default constructor.
184 // Constructor taking some policy objects. r_hash_fn will be
185 // copied by the Hash_Fn object of the container object.
186 cc_hash_table(const hash_fn
& h
)
189 // Constructor taking some policy objects. r_hash_fn will be
190 // copied by the hash_fn object of the container object, and
191 // r_eq_fn will be copied by the eq_fn object of the container
193 cc_hash_table(const hash_fn
& h
, const eq_fn
& e
)
194 : base_type(h
, e
) { }
196 // Constructor taking some policy objects. r_hash_fn will be
197 // copied by the hash_fn object of the container object, r_eq_fn
198 // will be copied by the eq_fn object of the container object, and
199 // r_comb_hash_fn will be copied by the comb_hash_fn object of the
201 cc_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_hash_fn
& ch
)
202 : base_type(h
, e
, ch
) { }
204 // Constructor taking some policy objects. r_hash_fn will be
205 // copied by the hash_fn object of the container object, r_eq_fn
206 // will be copied by the eq_fn object of the container object,
207 // r_comb_hash_fn will be copied by the comb_hash_fn object of the
208 // container object, and r_resize_policy will be copied by the
209 // resize_policy object of the container object.
210 cc_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_hash_fn
& ch
,
211 const resize_policy
& rp
)
212 : base_type(h
, e
, ch
, rp
) { }
214 // Constructor taking __iterators to a range of value_types. The
215 // value_types between first_it and last_it will be inserted into
216 // the container object.
217 template<typename It
>
218 cc_hash_table(It first
, It last
)
219 { base_type::copy_from_range(first
, last
); }
221 // Constructor taking __iterators to a range of value_types and
222 // some policy objects. The value_types between first_it and
223 // last_it will be inserted into the container object.
224 template<typename It
>
225 cc_hash_table(It first
, It last
, const hash_fn
& h
)
227 { copy_from_range(first
, last
); }
229 // Constructor taking __iterators to a range of value_types and
230 // some policy objects The value_types between first_it and
231 // last_it will be inserted into the container object. r_hash_fn
232 // will be copied by the hash_fn object of the container object,
233 // and r_eq_fn will be copied by the eq_fn object of the container
235 template<typename It
>
236 cc_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
)
238 { copy_from_range(first
, last
); }
240 // Constructor taking __iterators to a range of value_types and
241 // some policy objects The value_types between first_it and
242 // last_it will be inserted into the container object. r_hash_fn
243 // will be copied by the hash_fn object of the container object,
244 // r_eq_fn will be copied by the eq_fn object of the container
245 // object, and r_comb_hash_fn will be copied by the comb_hash_fn
246 // object of the container object.
247 template<typename It
>
248 cc_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
249 const comb_hash_fn
& ch
)
250 : base_type(h
, e
, ch
)
251 { copy_from_range(first
, last
); }
253 // Constructor taking __iterators to a range of value_types and
254 // some policy objects The value_types between first_it and
255 // last_it will be inserted into the container object. r_hash_fn
256 // will be copied by the hash_fn object of the container object,
257 // r_eq_fn will be copied by the eq_fn object of the container
258 // object, r_comb_hash_fn will be copied by the comb_hash_fn
259 // object of the container object, and r_resize_policy will be
260 // copied by the resize_policy object of the container object.
261 template<typename It
>
262 cc_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
263 const comb_hash_fn
& ch
, const resize_policy
& rp
)
264 : base_type(h
, e
, ch
, rp
)
265 { copy_from_range(first
, last
); }
267 cc_hash_table(const cc_hash_table
& other
)
268 : base_type((const base_type
&)other
)
275 operator=(const cc_hash_table
& other
)
279 cc_hash_table
tmp(other
);
286 swap(cc_hash_table
& other
)
287 { base_type::swap(other
); }
290 #undef PB_DS_BASE_C_DEC
293 #define PB_DS_BASE_C_DEC \
294 basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
296 typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
298 // A concrete general-probing hash-based associative container.
299 template<typename Key
,
301 typename Hash_Fn
= typename
detail::default_hash_fn
<Key
>::type
,
302 typename Eq_Fn
= typename
detail::default_eq_fn
<Key
>::type
,
303 typename Comb_Probe_Fn
= detail::default_comb_hash_fn::type
,
304 typename Probe_Fn
= typename
detail::default_probe_fn
<Comb_Probe_Fn
>::type
,
305 typename Resize_Policy
= typename
detail::default_resize_policy
<Comb_Probe_Fn
>::type
,
306 bool Store_Hash
= detail::default_store_hash
,
307 typename Allocator
= std::allocator
<char> >
308 class gp_hash_table
: public PB_DS_BASE_C_DEC
311 typedef PB_DS_BASE_C_DEC base_type
;
314 typedef Hash_Fn hash_fn
;
316 typedef Comb_Probe_Fn comb_probe_fn
;
317 typedef Probe_Fn probe_fn
;
318 typedef Resize_Policy resize_policy
;
320 // Default constructor.
323 // Constructor taking some policy objects. r_hash_fn will be
324 // copied by the hash_fn object of the container object.
325 gp_hash_table(const hash_fn
& h
)
328 // Constructor taking some policy objects. r_hash_fn will be
329 // copied by the hash_fn object of the container object, and
330 // r_eq_fn will be copied by the eq_fn object of the container
332 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
)
333 : base_type(h
, e
) { }
335 // Constructor taking some policy objects. r_hash_fn will be
336 // copied by the hash_fn object of the container object, r_eq_fn
337 // will be copied by the eq_fn object of the container object, and
338 // r_comb_probe_fn will be copied by the comb_probe_fn object of
339 // the container object.
340 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_probe_fn
& cp
)
341 : base_type(h
, e
, cp
) { }
343 // Constructor taking some policy objects. r_hash_fn will be
344 // copied by the hash_fn object of the container object, r_eq_fn
345 // will be copied by the eq_fn object of the container object,
346 // r_comb_probe_fn will be copied by the comb_probe_fn object of
347 // the container object, and r_probe_fn will be copied by the
348 // probe_fn object of the container object.
349 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_probe_fn
& cp
,
351 : base_type(h
, e
, cp
, p
) { }
353 // Constructor taking some policy objects. r_hash_fn will be
354 // copied by the hash_fn object of the container object, r_eq_fn
355 // will be copied by the eq_fn object of the container object,
356 // r_comb_probe_fn will be copied by the comb_probe_fn object of
357 // the container object, r_probe_fn will be copied by the probe_fn
358 // object of the container object, and r_resize_policy will be
359 // copied by the Resize_Policy object of the container object.
360 gp_hash_table(const hash_fn
& h
, const eq_fn
& e
, const comb_probe_fn
& cp
,
361 const probe_fn
& p
, const resize_policy
& rp
)
362 : base_type(h
, e
, cp
, p
, rp
) { }
364 // Constructor taking __iterators to a range of value_types. The
365 // value_types between first_it and last_it will be inserted into
366 // the container object.
367 template<typename It
>
368 gp_hash_table(It first
, It last
)
369 { base_type::copy_from_range(first
, last
); }
371 // Constructor taking __iterators to a range of value_types and
372 // some policy objects. The value_types between first_it and
373 // last_it will be inserted into the container object. r_hash_fn
374 // will be copied by the hash_fn object of the container object.
375 template<typename It
>
376 gp_hash_table(It first
, It last
, const hash_fn
& h
)
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 // and r_eq_fn will be copied by the eq_fn object of the container
386 template<typename It
>
387 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
)
389 { base_type::copy_from_range(first
, last
); }
391 // Constructor taking __iterators to a range of value_types and
392 // some policy objects. The value_types between first_it and
393 // last_it will be inserted into the container object. r_hash_fn
394 // will be copied by the hash_fn object of the container object,
395 // r_eq_fn will be copied by the eq_fn object of the container
396 // object, and r_comb_probe_fn will be copied by the comb_probe_fn
397 // object of the container object.
398 template<typename It
>
399 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
400 const comb_probe_fn
& cp
)
401 : base_type(h
, e
, cp
)
402 { base_type::copy_from_range(first
, last
); }
404 // Constructor taking __iterators to a range of value_types and
405 // some policy objects. The value_types between first_it and
406 // last_it will be inserted into the container object. r_hash_fn
407 // will be copied by the hash_fn object of the container object,
408 // r_eq_fn will be copied by the eq_fn object of the container
409 // object, r_comb_probe_fn will be copied by the comb_probe_fn
410 // object of the container object, and r_probe_fn will be copied
411 // by the probe_fn object of the container object.
412 template<typename It
>
413 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
414 const comb_probe_fn
& cp
, const probe_fn
& p
)
415 : base_type(h
, e
, cp
, p
)
416 { base_type::copy_from_range(first
, last
); }
418 // Constructor taking __iterators to a range of value_types and
419 // some policy objects. The value_types between first_it and
420 // last_it will be inserted into the container object. r_hash_fn
421 // will be copied by the hash_fn object of the container object,
422 // r_eq_fn will be copied by the eq_fn object of the container
423 // object, r_comb_probe_fn will be copied by the comb_probe_fn
424 // object of the container object, r_probe_fn will be copied by
425 // the probe_fn object of the container object, and
426 // r_resize_policy will be copied by the resize_policy object of
427 // the container object.
428 template<typename It
>
429 gp_hash_table(It first
, It last
, const hash_fn
& h
, const eq_fn
& e
,
430 const comb_probe_fn
& cp
, const probe_fn
& p
,
431 const resize_policy
& rp
)
432 : base_type(h
, e
, cp
, p
, rp
)
433 { base_type::copy_from_range(first
, last
); }
435 gp_hash_table(const gp_hash_table
& other
)
436 : base_type((const base_type
&)other
)
443 operator=(const gp_hash_table
& other
)
447 gp_hash_table
tmp(other
);
454 swap(gp_hash_table
& other
)
455 { base_type::swap(other
); }
458 #undef PB_DS_BASE_C_DEC
461 #define PB_DS_BASE_C_DEC \
462 container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
464 // An abstract basic tree-like (tree, trie) associative container.
465 template<typename Key
, typename Mapped
, typename Tag
,
466 typename Node_Update
, typename Policy_Tl
, typename Allocator
>
467 class basic_tree
: public PB_DS_BASE_C_DEC
470 typedef PB_DS_BASE_C_DEC base_type
;
473 typedef Node_Update node_update
;
479 #define PB_DS_CLASS_NAME basic_tree
480 #include <ext/pb_ds/detail/constructors_destructor_fn_imps.hpp>
481 #undef PB_DS_CLASS_NAME
484 #undef PB_DS_BASE_C_DEC
487 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
488 detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
490 #define PB_DS_BASE_C_DEC \
491 basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
492 typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
494 // A concrete basic tree-based associative container.
495 template<typename Key
, typename Mapped
, typename Cmp_Fn
= std::less
<Key
>,
496 typename Tag
= rb_tree_tag
,
497 template<typename Const_Node_Iterator
, typename Node_Iterator
, typename Cmp_Fn_
, typename Allocator_
>
498 class Node_Update
= __gnu_pbds::null_tree_node_update
,
499 typename Allocator
= std::allocator
<char> >
500 class tree
: public PB_DS_BASE_C_DEC
503 typedef PB_DS_BASE_C_DEC base_type
;
506 // Comparison functor type.
507 typedef Cmp_Fn cmp_fn
;
511 // Constructor taking some policy objects. r_cmp_fn will be copied
512 // by the Cmp_Fn object of the container object.
513 tree(const cmp_fn
& c
)
516 // Constructor taking __iterators to a range of value_types. The
517 // value_types between first_it and last_it will be inserted into
518 // the container object.
519 template<typename It
>
520 tree(It first
, It last
)
521 { base_type::copy_from_range(first
, last
); }
523 // Constructor taking __iterators to a range of value_types and
524 // some policy objects The value_types between first_it and
525 // last_it will be inserted into the container object. r_cmp_fn
526 // will be copied by the cmp_fn object of the container object.
527 template<typename It
>
528 tree(It first
, It last
, const cmp_fn
& c
)
530 { base_type::copy_from_range(first
, last
); }
532 tree(const tree
& other
)
533 : base_type((const base_type
&)other
) { }
539 operator=(const tree
& other
)
551 { base_type::swap(other
); }
554 #undef PB_DS_BASE_C_DEC
555 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
558 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
559 detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
561 #define PB_DS_BASE_C_DEC \
562 basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
563 typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
565 // A concrete basic trie-based associative container.
566 template<typename Key
,
568 typename E_Access_Traits
= typename
detail::default_trie_e_access_traits
<Key
>::type
,
569 typename Tag
= pat_trie_tag
,
570 template<typename Const_Node_Iterator
,
571 typename Node_Iterator
,
572 typename E_Access_Traits_
,
574 class Node_Update
= null_trie_node_update
,
575 typename Allocator
= std::allocator
<char> >
576 class trie
: public PB_DS_BASE_C_DEC
579 typedef PB_DS_BASE_C_DEC base_type
;
582 // Element access traits type.
583 typedef E_Access_Traits e_access_traits
;
587 // Constructor taking some policy objects. r_e_access_traits will
588 // be copied by the E_Access_Traits object of the container
590 trie(const e_access_traits
& t
)
593 // Constructor taking __iterators to a range of value_types. The
594 // value_types between first_it and last_it will be inserted into
595 // the container object.
596 template<typename It
>
597 trie(It first
, It last
)
598 { base_type::copy_from_range(first
, last
); }
600 // Constructor taking __iterators to a range of value_types and
601 // some policy objects. The value_types between first_it and
602 // last_it will be inserted into the container object.
603 template<typename It
>
604 trie(It first
, It last
, const e_access_traits
& t
)
606 { base_type::copy_from_range(first
, last
); }
608 trie(const trie
& other
)
609 : base_type((const base_type
&)other
) { }
615 operator=(const trie
& other
)
627 { base_type::swap(other
); }
630 #undef PB_DS_BASE_C_DEC
631 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
634 #define PB_DS_BASE_C_DEC \
635 container_base<Key, Mapped, list_update_tag, \
636 typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
638 // A list-update based associative container.
639 template<typename Key
,
641 class Eq_Fn
= typename
detail::default_eq_fn
<Key
>::type
,
642 class Update_Policy
= detail::default_update_policy::type
,
643 class Allocator
= std::allocator
<char> >
644 class list_update
: public PB_DS_BASE_C_DEC
647 typedef PB_DS_BASE_C_DEC base_type
;
651 typedef Update_Policy update_policy
;
652 typedef Allocator allocator
;
656 // Constructor taking __iterators to a range of value_types. The
657 // value_types between first_it and last_it will be inserted into
658 // the container object.
659 template<typename It
>
660 list_update(It first
, It last
)
661 { base_type::copy_from_range(first
, last
); }
663 list_update(const list_update
& other
)
664 : base_type((const base_type
&)other
) { }
670 operator=(const list_update
& other
)
674 list_update
tmp(other
);
681 swap(list_update
& other
)
682 { base_type::swap(other
); }
685 #undef PB_DS_BASE_C_DEC
687 } // namespace __gnu_pbds