3 // Copyright (C) 2005 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
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
32 // Permission to use, copy, modify, sell, and distribute this software
33 // is hereby granted without fee, provided that the above copyright
34 // notice appears in all copies, and that both that copyright notice and
35 // this permission notice appear in supporting documentation. None of
36 // the above authors, nor IBM Haifa Research Laboratories, make any
37 // representation about the suitability of this software for any
38 // purpose. It is provided "as is" without express or implied warranty.
41 * @file assoc_cntnr.hpp
42 * Contains associative containers.
45 #ifndef ASSOC_CNTNR_HPP
46 #define ASSOC_CNTNR_HPP
48 #include <ext/pb_assoc/ms_trait.hpp>
49 #include <ext/pb_assoc/ds_trait.hpp>
50 #include <ext/pb_assoc/detail/type_utils.hpp>
51 #include <ext/pb_assoc/detail/typelist.hpp>
52 #include <ext/pb_assoc/detail/standard_policies.hpp>
53 #include <ext/pb_assoc/detail/mapping_level_imp.hpp>
54 #include <ext/pb_assoc/detail/assoc_cntnr_base.hpp>
55 #include <ext/pb_assoc/detail/value_type_adapter/value_type_adapter.hpp>
60 #define PB_ASSOC_CLASS_T_DEC \
68 #define PB_ASSOC_CLASS_C_DEC \
76 #define PB_ASSOC_BASE_C_DEC \
77 detail::assoc_cntnr_base< \
84 #define PB_ASSOC_DIRECT_BASE_C_DEC \
85 detail::assoc_cntnr_base< \
92 template<typename Key,
97 class basic_assoc_cntnr
98 : public detail::assoc_cntnr_base<Key, Data, DS_Tag, Policy_Tl, Allocator>::type
101 typedef typename Allocator::size_type size_type;
102 typedef typename Allocator::difference_type difference_type;
103 typedef DS_Tag ds_category;
104 typedef data_enabled_ms_tag ms_category;
105 typedef Allocator allocator;
108 typename allocator::template rebind<
109 Key>::other::value_type
113 typename allocator::template rebind<
114 Key>::other::reference
118 typename allocator::template rebind<
119 Key>::other::const_reference
123 typename allocator::template rebind<
128 typename allocator::template rebind<
129 Key>::other::const_pointer
133 typename allocator::template rebind<
134 Data>::other::value_type
138 typename allocator::template rebind<
139 Data>::other::reference
143 typename allocator::template rebind<
144 Data>::other::const_reference
145 const_data_reference;
148 typename allocator::template rebind<
149 Data>::other::pointer
153 typename allocator::template rebind<
154 Data>::other::const_pointer
158 typename allocator::template rebind<
159 std::pair<const key_type, data_type> >::other::value_type
163 typename allocator::template rebind<
164 std::pair<const key_type, data_type> >::other::reference
168 typename allocator::template rebind<
169 std::pair<const key_type, data_type> >::other::const_reference
173 typename allocator::template rebind<
174 std::pair<const key_type, data_type> >::other::pointer
178 typename allocator::template rebind<
179 std::pair<const key_type, data_type> >::other::const_pointer
183 typename PB_ASSOC_BASE_C_DEC::const_find_iterator
186 typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
188 typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
190 typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
195 ~basic_assoc_cntnr();
206 inline static const_key_reference
207 extract_key(const_reference r_val);
209 inline std::pair<find_iterator, bool>
210 insert(const_reference r_val);
212 inline data_reference
213 operator[](const_key_reference r_key);
216 find(const_key_reference r_key)
218 return (my_base::find(r_key));
221 inline const_find_iterator
222 find(const_key_reference r_key) const
224 return (my_base::find(r_key));
227 inline const_data_reference
228 operator[](const_key_reference r_key) const;
231 erase(const_key_reference r_key);
243 inline const_iterator
249 inline const_iterator
254 #define PB_ASSOC_CLASS_NAME basic_assoc_cntnr
256 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
257 typename PB_ASSOC_DIRECT_BASE_C_DEC
259 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
261 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
263 #undef PB_ASSOC_CLASS_NAME
266 typedef typename PB_ASSOC_BASE_C_DEC my_base;
270 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
273 #include <ext/pb_assoc/detail/basic_assoc_cntnr/constructors_destructor_fn_imps.hpp>
274 #include <ext/pb_assoc/detail/basic_assoc_cntnr/iterators_fn_imps.hpp>
275 #include <ext/pb_assoc/detail/basic_assoc_cntnr/info_fn_imps.hpp>
276 #include <ext/pb_assoc/detail/basic_assoc_cntnr/erase_fn_imps.hpp>
277 #include <ext/pb_assoc/detail/basic_assoc_cntnr/insert_fn_imps.hpp>
278 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_insert_fn_imps.hpp>
279 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_find_fn_imps.hpp>
280 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_extract_key.hpp>
282 #undef PB_ASSOC_CLASS_T_DEC
284 #undef PB_ASSOC_CLASS_C_DEC
286 #undef PB_ASSOC_BASE_C_DEC
288 #undef PB_ASSOC_DIRECT_BASE_C_DEC
290 #define PB_ASSOC_CLASS_T_DEC \
298 #define PB_ASSOC_CLASS_C_DEC \
301 compound_data_type< \
307 #define PB_ASSOC_DIRECT_BASE_C_DEC \
308 detail::value_type_adapter< \
310 compound_data_type< \
315 detail::mapping_level_imp< \
316 compound_data_type< \
319 #define PB_ASSOC_BASE_C_DEC \
320 detail::assoc_cntnr_base< \
322 compound_data_type< \
328 template<typename Key,
333 class basic_assoc_cntnr<Key, compound_data_type< Cntnr>, DS_Tag, Policy_Tl, Allocator> : public PB_ASSOC_DIRECT_BASE_C_DEC
336 typedef typename Allocator::size_type size_type;
337 typedef typename Allocator::difference_type difference_type;
338 typedef DS_Tag ds_category;
339 typedef compound_data_enabled_ms_tag ms_category;
340 typedef Allocator allocator;
343 typename allocator::template rebind<
344 Key>::other::value_type
348 typename allocator::template rebind<
349 Key>::other::reference
353 typename allocator::template rebind<
354 Key>::other::const_reference
358 typename allocator::template rebind<
363 typename allocator::template rebind<
364 Key>::other::const_pointer
368 typename allocator::template rebind<
369 Cntnr>::other::value_type
373 typename allocator::template rebind<
374 Cntnr>::other::reference
378 typename allocator::template rebind<
379 Cntnr>::other::const_reference
380 const_data_reference;
383 typename allocator::template rebind<
384 Cntnr>::other::pointer
388 typename allocator::template rebind<
389 Cntnr>::other::const_pointer
393 typename allocator::template rebind<
394 std::pair<const key_type, Cntnr> >::other::value_type
398 typename allocator::template rebind<
399 std::pair<const key_type, Cntnr> >::other::reference
403 typename allocator::template rebind<
404 std::pair<const key_type, Cntnr> >::other::const_reference
408 typename allocator::template rebind<
409 std::pair<const key_type, Cntnr> >::other::pointer
413 typename allocator::template rebind<
414 std::pair<const key_type, Cntnr> >::other::const_pointer
418 typename PB_ASSOC_BASE_C_DEC::const_find_iterator
421 typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
423 typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
425 typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
427 template<int Mapping_Level>
434 detail::mapping_level_imp<compound_data_type<Cntnr> >::value
439 detail::value_type_adapter<
446 mapping_level - Mapping_Level>
453 ~basic_assoc_cntnr();
464 inline static const_key_reference
465 extract_key(const_reference r_val);
467 inline std::pair<find_iterator, bool>
468 insert(const_reference r_val);
470 inline data_reference
471 operator[](const_key_reference r_key);
474 find(const_key_reference r_key)
476 return (my_base::find(r_key));
479 inline const_find_iterator
480 find(const_key_reference r_key) const
482 return (my_base::find(r_key));
485 inline const_data_reference
486 operator[](const_key_reference r_key) const;
489 erase(const_key_reference r_key);
501 inline const_iterator
507 inline const_iterator
512 #define PB_ASSOC_CLASS_NAME basic_assoc_cntnr
514 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
515 typename PB_ASSOC_DIRECT_BASE_C_DEC
517 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
519 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
521 #undef PB_ASSOC_CLASS_NAME
524 typedef typename PB_ASSOC_BASE_C_DEC my_base;
528 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
531 #include <ext/pb_assoc/detail/basic_assoc_cntnr/constructors_destructor_fn_imps.hpp>
532 #include <ext/pb_assoc/detail/basic_assoc_cntnr/iterators_fn_imps.hpp>
533 #include <ext/pb_assoc/detail/basic_assoc_cntnr/info_fn_imps.hpp>
534 #include <ext/pb_assoc/detail/basic_assoc_cntnr/erase_fn_imps.hpp>
535 #include <ext/pb_assoc/detail/basic_assoc_cntnr/insert_fn_imps.hpp>
536 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_insert_fn_imps.hpp>
537 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_find_fn_imps.hpp>
538 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_extract_key.hpp>
540 #undef PB_ASSOC_CLASS_T_DEC
542 #undef PB_ASSOC_CLASS_C_DEC
544 #undef PB_ASSOC_BASE_C_DEC
546 #undef PB_ASSOC_DIRECT_BASE_C_DEC
548 #define PB_ASSOC_CLASS_T_DEC \
549 template<typename Key, class DS_Tag, class Policy_Tl, class Allocator>
551 #define PB_ASSOC_CLASS_C_DEC \
559 #define PB_ASSOC_BASE_C_DEC \
560 detail::assoc_cntnr_base< \
567 template<typename Key, class DS_Tag, class Policy_Tl, class Allocator>
568 class basic_assoc_cntnr<Key, null_data_type, DS_Tag, Policy_Tl, Allocator> : public PB_ASSOC_BASE_C_DEC
571 typedef typename Allocator::size_type size_type;
572 typedef typename Allocator::difference_type difference_type;
573 typedef DS_Tag ds_category;
574 typedef basic_ms_tag ms_category;
575 typedef Allocator allocator;
578 typename allocator::template rebind<
579 Key>::other::value_type
583 typename allocator::template rebind<
584 Key>::other::reference
588 typename allocator::template rebind<
589 Key>::other::const_reference
593 typename allocator::template rebind<
598 typename allocator::template rebind<
599 Key>::other::const_pointer
603 typename allocator::template rebind<
604 key_type>::other::value_type
608 typename allocator::template rebind<
609 key_type>::other::const_reference
613 typename allocator::template rebind<
614 key_type>::other::const_reference
618 typename allocator::template rebind<
619 key_type>::other::const_pointer
623 typename allocator::template rebind<key_type>::other::const_pointer
627 typename PB_ASSOC_BASE_C_DEC::const_find_iterator
630 typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
632 typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
634 typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
639 ~basic_assoc_cntnr();
650 inline static const_key_reference
651 extract_key(const_reference r_val);
653 inline std::pair<find_iterator, bool>
654 insert(const_reference r_val);
657 find(const_key_reference r_key)
658 { return (my_base::find(r_key)); }
660 inline const_find_iterator
661 find(const_key_reference r_key) const
662 { return (my_base::find(r_key)); }
665 erase(const_key_reference r_key);
677 inline const_iterator
683 inline const_iterator
688 #define PB_ASSOC_CLASS_NAME basic_assoc_cntnr
690 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
692 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
693 typename PB_ASSOC_DIRECT_BASE_C_DEC
695 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
697 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
699 #undef PB_ASSOC_DIRECT_BASE_C_DEC
701 #undef PB_ASSOC_CLASS_NAME
704 typedef typename PB_ASSOC_BASE_C_DEC my_base;
708 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
711 #include <ext/pb_assoc/detail/basic_assoc_cntnr/constructors_destructor_fn_imps.hpp>
712 #include <ext/pb_assoc/detail/basic_assoc_cntnr/iterators_fn_imps.hpp>
713 #include <ext/pb_assoc/detail/basic_assoc_cntnr/info_fn_imps.hpp>
714 #include <ext/pb_assoc/detail/basic_assoc_cntnr/erase_fn_imps.hpp>
715 #include <ext/pb_assoc/detail/basic_assoc_cntnr/insert_fn_imps.hpp>
716 #include <ext/pb_assoc/detail/basic_assoc_cntnr/extract_key.hpp>
718 #undef PB_ASSOC_CLASS_T_DEC
720 #undef PB_ASSOC_CLASS_C_DEC
722 #undef PB_ASSOC_BASE_C_DEC
724 #define PB_ASSOC_TYPELIST_CHAIN1(X0) pb_assoc::detail::typelist_chain<X0, pb_assoc::detail::null_type>
725 #define PB_ASSOC_TYPELIST_CHAIN2(X0, X1) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN1(X1) >
726 #define PB_ASSOC_TYPELIST_CHAIN3(X0, X1, X2) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN2(X1, X2) >
727 #define PB_ASSOC_TYPELIST_CHAIN4(X0, X1, X2, X3) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN3(X1, X2, X3) >
728 #define PB_ASSOC_TYPELIST_CHAIN5(X0, X1, X2, X3, X4) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN4(X1, X2, X3, X4) >
729 #define PB_ASSOC_TYPELIST_CHAIN6(X0, X1, X2, X3, X4, X5) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN5(X1, X2, X3, X4, X5) >
730 #define PB_ASSOC_TYPELIST_CHAIN7(X0, X1, X2, X3, X4, X5, X6) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN6(X1, X2, X3, X4, X5, X6) >
731 #define PB_ASSOC_TYPELIST_CHAIN8(X0, X1, X2, X3, X4, X5, X6, X7) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN7(X1, X2, X3, X4, X5, X6, X7) >
732 #define PB_ASSOC_TYPELIST_CHAIN9(X0, X1, X2, X3, X4, X5, X6, X7, X8) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN8(X1, X2, X3, X4, X5, X6, X7, X8) >
733 #define PB_ASSOC_TYPELIST_CHAIN10(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN9(X1, X2, X3, X4, X5, X6, X7, X8, X9) >
734 #define PB_ASSOC_TYPELIST_CHAIN11(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN10(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10) >
735 #define PB_ASSOC_TYPELIST_CHAIN12(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN11(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11) >
736 #define PB_ASSOC_TYPELIST_CHAIN13(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN12(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12) >
737 #define PB_ASSOC_TYPELIST_CHAIN14(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN13(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13) >
738 #define PB_ASSOC_TYPELIST_CHAIN15(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN14(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14) >
740 #define PB_ASSOC_CLASS_T_DEC \
746 class Resize_Policy, \
752 #define PB_ASSOC_CLASS_C_DEC \
753 basic_hash_assoc_cntnr< \
764 #define PB_ASSOC_BASE_C_DEC \
769 typename pb_assoc::detail::typelist_append< \
770 pb_assoc::detail::typelist< \
771 PB_ASSOC_TYPELIST_CHAIN4( Hash_Fn, Eq_Fn, Resize_Policy, pb_assoc::detail::int_to_type<Store_Hash>) >, \
775 template<typename Key,
784 class basic_hash_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
787 typedef Hash_Fn hash_fn;
791 typedef Resize_Policy resize_policy;
795 store_hash = Store_Hash
799 ~basic_hash_assoc_cntnr();
817 get_resize_policy() const;
821 typedef typename Allocator::size_type size_type;
824 do_resize(size_type new_size);
826 #define PB_ASSOC_CLASS_NAME basic_hash_assoc_cntnr
828 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
830 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
831 PB_ASSOC_DIRECT_BASE_C_DEC
833 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
835 #undef PB_ASSOC_DIRECT_BASE_C_DEC
837 #undef PB_ASSOC_CLASS_NAME
839 #undef PB_ASSOC_DIRECT_BASE_C_DEC
842 typedef PB_ASSOC_BASE_C_DEC my_base;
844 basic_hash_assoc_cntnr&
845 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
848 #include <ext/pb_assoc/detail/basic_hash_assoc_cntnr/constructors_destructor_fn_imps.hpp>
849 #include <ext/pb_assoc/detail/basic_hash_assoc_cntnr/resize_fn_imps.hpp>
851 #undef PB_ASSOC_CLASS_T_DEC
853 #undef PB_ASSOC_CLASS_C_DEC
855 #undef PB_ASSOC_BASE_C_DEC
857 #define PB_ASSOC_CLASS_T_DEC \
863 class Comb_Hash_Fn, \
864 class Resize_Policy, \
868 #define PB_ASSOC_CLASS_C_DEC \
869 cc_hash_assoc_cntnr< \
879 #define PB_ASSOC_BASE_C_DEC \
880 basic_hash_assoc_cntnr< \
888 pb_assoc::detail::typelist< \
889 PB_ASSOC_TYPELIST_CHAIN1( \
893 template<typename Key,
895 class Hash_Fn = typename pb_assoc::detail::def_hash_fn<Key>::type,
896 class Eq_Fn = typename pb_assoc::detail::def_eq_fn<Key>::type,
897 class Comb_Hash_Fn = pb_assoc::detail::def_comb_hash_fn::type,
898 class Resize_Policy =
899 typename pb_assoc::detail::def_resize_policy<Comb_Hash_Fn>::type,
900 bool Store_Hash = pb_assoc::detail::def_store_hash,
901 class Allocator = std::allocator<char> >
902 class cc_hash_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
905 typedef Comb_Hash_Fn comb_hash_fn;
907 cc_hash_assoc_cntnr();
909 cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn);
911 cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
913 cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
914 const Comb_Hash_Fn& r_comb_hash_fn);
916 cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
917 const Comb_Hash_Fn& r_comb_hash_fn,
918 const Resize_Policy& r_resize_policy);
921 cc_hash_assoc_cntnr(It first_it, It last_it);
924 cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn);
927 cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn,
928 const Eq_Fn& r_eq_fn);
931 cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn);
934 cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy);
936 cc_hash_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
939 ~cc_hash_assoc_cntnr();
941 PB_ASSOC_CLASS_C_DEC&
942 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
945 swap(PB_ASSOC_CLASS_C_DEC& r_other);
951 get_comb_hash_fn() const;
954 typedef PB_ASSOC_BASE_C_DEC my_base;
957 #include <ext/pb_assoc/detail/cc_hash_assoc_cntnr/constructor_destructor_fn_imps.hpp>
959 #undef PB_ASSOC_CLASS_T_DEC
961 #undef PB_ASSOC_CLASS_C_DEC
963 #undef PB_ASSOC_BASE_C_DEC
965 #define PB_ASSOC_CLASS_T_DEC \
971 class Comb_Probe_Fn, \
973 class Resize_Policy, \
977 #define PB_ASSOC_CLASS_C_DEC \
978 gp_hash_assoc_cntnr< \
989 #define PB_ASSOC_BASE_C_DEC \
990 basic_hash_assoc_cntnr< \
998 pb_assoc::detail::typelist< \
999 PB_ASSOC_TYPELIST_CHAIN2( Comb_Probe_Fn, Probe_Fn) >, \
1002 template<typename Key,
1004 class Hash_Fn = typename pb_assoc::detail::def_hash_fn<Key>::type,
1005 class Eq_Fn = typename pb_assoc::detail::def_eq_fn<Key>::type,
1006 class Comb_Probe_Fn = pb_assoc::detail::def_comb_hash_fn::type,
1007 class Probe_Fn = typename detail::def_probe_fn<Comb_Probe_Fn>::type,
1008 class Resize_Policy =
1009 typename pb_assoc::detail::def_resize_policy<Comb_Probe_Fn>::type,
1011 bool Store_Hash = pb_assoc::detail::def_store_hash,
1012 class Allocator = std::allocator<char> >
1013 class gp_hash_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1016 typedef Comb_Probe_Fn comb_probe_fn;
1017 typedef Probe_Fn probe_fn;
1019 gp_hash_assoc_cntnr();
1021 gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn);
1023 gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
1025 gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
1026 const Comb_Probe_Fn& r_comb_probe_fn);
1028 gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
1029 const Comb_Probe_Fn& r_comb_probe_fn,
1030 const Probe_Fn& r_probe_fn);
1032 gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
1033 const Comb_Probe_Fn& r_comb_probe_fn,
1034 const Probe_Fn& r_probe_fn,
1035 const Resize_Policy& r_resize_policy);
1038 gp_hash_assoc_cntnr(It first_it, It last_it);
1041 gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn);
1044 gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
1047 gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn);
1050 gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
1053 gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn, const Resize_Policy& r_resize_policy);
1055 gp_hash_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
1058 ~gp_hash_assoc_cntnr();
1060 PB_ASSOC_CLASS_C_DEC&
1061 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
1064 swap(PB_ASSOC_CLASS_C_DEC& r_other);
1067 get_comb_probe_fn();
1069 const comb_probe_fn&
1070 get_comb_probe_fn() const;
1076 get_probe_fn() const;
1079 typedef PB_ASSOC_BASE_C_DEC my_base;
1082 #include <ext/pb_assoc/detail/gp_hash_assoc_cntnr/constructor_destructor_fn_imps.hpp>
1084 #undef PB_ASSOC_CLASS_T_DEC
1086 #undef PB_ASSOC_CLASS_C_DEC
1088 #undef PB_ASSOC_BASE_C_DEC
1090 #define PB_ASSOC_CLASS_T_DEC \
1096 class Node_Updator, \
1099 #define PB_ASSOC_CLASS_C_DEC \
1100 basic_tree_assoc_cntnr< \
1108 #define PB_ASSOC_BASE_C_DEC \
1109 basic_assoc_cntnr< \
1113 pb_assoc::detail::typelist< \
1114 PB_ASSOC_TYPELIST_CHAIN2( Cmp_Fn, Node_Updator) >, \
1117 template<typename Key,
1123 class basic_tree_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1126 typedef typename Allocator::size_type size_type;
1129 typename Allocator::template rebind<
1130 Key>::other::const_reference
1131 const_key_reference;
1133 typedef Cmp_Fn cmp_fn;
1135 typedef Node_Updator node_updator;
1137 typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
1139 typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
1142 typename PB_ASSOC_BASE_C_DEC::const_reverse_iterator
1143 const_reverse_iterator;
1146 typename PB_ASSOC_BASE_C_DEC::reverse_iterator
1150 typename PB_ASSOC_BASE_C_DEC::const_node_iterator
1151 const_node_iterator;
1153 typedef typename PB_ASSOC_BASE_C_DEC::node_iterator node_iterator;
1156 ~basic_tree_assoc_cntnr();
1168 get_node_updator() const;
1171 erase(const_key_reference r_key);
1176 inline reverse_iterator
1177 erase(reverse_iterator it)
1179 return (my_base::erase(it));
1182 inline reverse_iterator
1185 return (my_base::rbegin());
1188 inline const_reverse_iterator
1191 return (my_base::rbegin());
1194 inline reverse_iterator
1197 return (my_base::rend());
1200 inline const_reverse_iterator
1203 return (my_base::rend());
1206 inline node_iterator
1209 return (my_base::node_begin());
1212 inline const_node_iterator
1215 return (my_base::node_begin());
1218 inline node_iterator
1221 return (my_base::node_end());
1224 inline const_node_iterator
1227 return (my_base::node_end());
1231 join(PB_ASSOC_CLASS_C_DEC& r_other);
1234 split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
1238 #define PB_ASSOC_CLASS_NAME basic_tree_assoc_cntnr
1240 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
1242 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
1243 PB_ASSOC_DIRECT_BASE_C_DEC
1245 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
1247 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
1249 #undef PB_ASSOC_CLASS_NAME
1251 #undef PB_ASSOC_DIRECT_BASE_C_DEC
1254 typedef PB_ASSOC_BASE_C_DEC my_base;
1257 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/constructors_destructor_fn_imps.hpp>
1258 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/policy_access_fn_imps.hpp>
1259 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/range_iteration_fn_imps.hpp>
1260 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/r_range_iteration_fn_imps.hpp>
1261 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/node_iteration_fn_imps.hpp>
1262 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/split_join_fn_imps.hpp>
1263 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/erase_fn_imps.hpp>
1264 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/r_erase_fn_imps.hpp>
1266 #undef PB_ASSOC_CLASS_T_DEC
1268 #undef PB_ASSOC_CLASS_C_DEC
1270 #undef PB_ASSOC_BASE_C_DEC
1272 #define PB_ASSOC_CLASS_T_DEC \
1277 class Node_Updator, \
1280 #define PB_ASSOC_CLASS_C_DEC \
1281 basic_tree_assoc_cntnr< \
1289 #define PB_ASSOC_BASE_C_DEC \
1290 basic_assoc_cntnr< \
1294 pb_assoc::detail::typelist< \
1295 PB_ASSOC_TYPELIST_CHAIN2( Cmp_Fn, Node_Updator) >, \
1298 template<typename Key,
1301 typename Node_Updator,
1303 class basic_tree_assoc_cntnr<Key, Data, Cmp_Fn, ov_tree_ds_tag, Node_Updator, Allocator>
1304 : public PB_ASSOC_BASE_C_DEC
1307 typedef typename Allocator::size_type size_type;
1310 typename Allocator::template rebind<
1311 Key>::other::const_reference
1312 const_key_reference;
1314 typedef Cmp_Fn cmp_fn;
1316 typedef Node_Updator node_updator;
1318 typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
1320 typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
1323 typename PB_ASSOC_BASE_C_DEC::const_node_iterator
1324 const_node_iterator;
1326 typedef typename PB_ASSOC_BASE_C_DEC::node_iterator node_iterator;
1329 ~basic_tree_assoc_cntnr();
1341 get_node_updator() const;
1344 erase(const_key_reference r_key);
1349 inline node_iterator
1352 return (my_base::node_begin());
1355 inline const_node_iterator
1358 return (my_base::node_begin());
1361 inline node_iterator
1364 return (my_base::node_end());
1367 inline const_node_iterator
1370 return (my_base::node_end());
1374 join(PB_ASSOC_CLASS_C_DEC& r_other);
1377 split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
1381 #define PB_ASSOC_CLASS_NAME basic_tree_assoc_cntnr
1383 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
1385 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
1386 PB_ASSOC_DIRECT_BASE_C_DEC
1388 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
1390 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
1392 #undef PB_ASSOC_CLASS_NAME
1394 #undef PB_ASSOC_DIRECT_BASE_C_DEC
1397 typedef PB_ASSOC_BASE_C_DEC my_base;
1400 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/constructors_destructor_fn_imps.hpp>
1401 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/policy_access_fn_imps.hpp>
1402 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/range_iteration_fn_imps.hpp>
1403 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/node_iteration_fn_imps.hpp>
1404 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/split_join_fn_imps.hpp>
1405 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/erase_fn_imps.hpp>
1407 #undef PB_ASSOC_CLASS_T_DEC
1409 #undef PB_ASSOC_CLASS_C_DEC
1411 #undef PB_ASSOC_BASE_C_DEC
1413 #define PB_ASSOC_CLASS_T_DEC \
1419 class Node_Updator, \
1422 #define PB_ASSOC_CLASS_C_DEC \
1431 #define PB_ASSOC_BASE_C_DEC \
1432 basic_tree_assoc_cntnr< \
1440 template<typename Key, typename Data, class Cmp_Fn = std::less<Key>,
1441 typename DS_Tag = rb_tree_ds_tag,
1442 typename Node_Updator = pb_assoc::detail::def_node_updator,
1443 typename Allocator = std::allocator<char> >
1444 class tree_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1446 typedef Cmp_Fn cmp_fn;
1447 typedef Node_Updator node_updator;
1451 tree_assoc_cntnr(const cmp_fn& r_cmp_fn);
1452 tree_assoc_cntnr(const cmp_fn& r_cmp_fn, const Node_Updator&r);
1454 template<typename It>
1455 tree_assoc_cntnr(It first_it, It last_it);
1457 template<typename It>
1458 tree_assoc_cntnr(It first_it, It last_it, const cmp_fn& r_cmp_fn);
1460 template<typename It>
1461 tree_assoc_cntnr(It, It, const cmp_fn&, const Node_Updator&);
1463 tree_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
1466 ~tree_assoc_cntnr();
1468 PB_ASSOC_CLASS_C_DEC&
1469 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
1472 swap(PB_ASSOC_CLASS_C_DEC& r_other);
1475 typedef PB_ASSOC_BASE_C_DEC my_base;
1478 #include <ext/pb_assoc/detail/tree_assoc_cntnr/constructor_destructor_fn_imps.hpp>
1480 #undef PB_ASSOC_CLASS_T_DEC
1482 #undef PB_ASSOC_CLASS_C_DEC
1484 #undef PB_ASSOC_BASE_C_DEC
1486 #define PB_ASSOC_CLASS_T_DEC \
1491 class Update_Policy, \
1494 #define PB_ASSOC_CLASS_C_DEC \
1502 #define PB_ASSOC_BASE_C_DEC \
1503 basic_assoc_cntnr< \
1507 pb_assoc::detail::typelist< \
1508 PB_ASSOC_TYPELIST_CHAIN2( Eq_Fn, Update_Policy) >, \
1511 template<typename Key,
1513 typename Eq_Fn = typename pb_assoc::detail::def_eq_fn<Key>::type,
1514 typename Update_Policy = pb_assoc::detail::def_update_policy::type,
1515 typename Allocator = std::allocator<char> >
1516 class lu_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1519 typedef Eq_Fn eq_fn;
1520 typedef Allocator allocator;
1521 typedef Update_Policy update_policy;
1524 lu_assoc_cntnr(const Eq_Fn& r_eq_fn);
1525 lu_assoc_cntnr(const Eq_Fn& r_eq_fn, const Update_Policy& r_update_policy);
1527 template<typename It>
1528 lu_assoc_cntnr(It first_it, It last_it);
1530 template<typename It>
1531 lu_assoc_cntnr(It first_it, It last_it, const Eq_Fn& r_eq_fn);
1533 template<typename It>
1534 lu_assoc_cntnr(It, It, const Eq_Fn&, const Update_Policy&);
1536 lu_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
1541 PB_ASSOC_CLASS_C_DEC&
1542 operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
1545 swap(PB_ASSOC_CLASS_C_DEC& r_other);
1554 get_update_policy();
1556 const update_policy&
1557 get_update_policy() const;
1560 typedef PB_ASSOC_BASE_C_DEC my_base;
1563 #include <ext/pb_assoc/detail/lu_assoc_cntnr/constructor_destructor_fn_imps.hpp>
1564 #include <ext/pb_assoc/detail/lu_assoc_cntnr/policy_access_fn_imps.hpp>
1566 #undef PB_ASSOC_CLASS_T_DEC
1568 #undef PB_ASSOC_CLASS_C_DEC
1570 #undef PB_ASSOC_BASE_C_DEC
1572 #undef PB_ASSOC_TYPELIST_CHAIN1
1573 #undef PB_ASSOC_TYPELIST_CHAIN2
1574 #undef PB_ASSOC_TYPELIST_CHAIN3
1575 #undef PB_ASSOC_TYPELIST_CHAIN4
1576 #undef PB_ASSOC_TYPELIST_CHAIN5
1577 #undef PB_ASSOC_TYPELIST_CHAIN6
1578 #undef PB_ASSOC_TYPELIST_CHAIN7
1579 #undef PB_ASSOC_TYPELIST_CHAIN8
1580 #undef PB_ASSOC_TYPELIST_CHAIN9
1581 #undef PB_ASSOC_TYPELIST_CHAIN10
1582 #undef PB_ASSOC_TYPELIST_CHAIN11
1583 #undef PB_ASSOC_TYPELIST_CHAIN12
1584 #undef PB_ASSOC_TYPELIST_CHAIN13
1585 #undef PB_ASSOC_TYPELIST_CHAIN14
1586 #undef PB_ASSOC_TYPELIST_CHAIN15
1588 } // namespace pb_assoc
1590 #endif // #ifndef ASSOC_CNTNR_HPP