]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
aa118a03 | 3 | // Copyright (C) 2005-2014 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 | ||
8fc81078 | 44 | #include <bits/c++config.h> |
d7f245b1 | 45 | #include <ext/typelist.h> |
4569a895 AT |
46 | #include <ext/pb_ds/tag_and_trait.hpp> |
47 | #include <ext/pb_ds/detail/standard_policies.hpp> | |
48 | #include <ext/pb_ds/detail/container_base_dispatch.hpp> | |
a345e45d | 49 | #include <ext/pb_ds/detail/branch_policy/traits.hpp> |
4569a895 | 50 | |
5e11f978 | 51 | namespace __gnu_pbds |
4569a895 | 52 | { |
a345e45d | 53 | /** |
30a96b3b BK |
54 | * @defgroup containers-pbds Containers |
55 | * @ingroup pbds | |
0eb95b0d BK |
56 | * @{ |
57 | */ | |
4569a895 | 58 | |
30a96b3b | 59 | /** |
d8dd52a9 | 60 | * @defgroup hash-based Hash-Based |
30a96b3b BK |
61 | * @ingroup containers-pbds |
62 | * @{ | |
63 | */ | |
a345e45d BK |
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 | |
4569a895 | 69 | |
30a96b3b BK |
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 | */ | |
4569a895 AT |
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, | |
a345e45d BK |
102 | typename Policy_Tl, |
103 | typename _Alloc> | |
104 | class basic_hash_table : public PB_DS_HASH_BASE | |
4569a895 AT |
105 | { |
106 | private: | |
a345e45d | 107 | typedef typename PB_DS_HASH_BASE base_type; |
4569a895 AT |
108 | |
109 | public: | |
110 | virtual | |
111 | ~basic_hash_table() { } | |
112 | ||
113 | protected: | |
30a96b3b BK |
114 | basic_hash_table() { } |
115 | ||
116 | basic_hash_table(const basic_hash_table& other) | |
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 | { } | |
4569a895 AT |
157 | |
158 | private: | |
a345e45d | 159 | basic_hash_table& |
4569a895 AT |
160 | operator=(const base_type&); |
161 | }; | |
162 | ||
a345e45d | 163 | #undef PB_DS_HASH_BASE |
4569a895 AT |
164 | |
165 | ||
a345e45d | 166 | #define PB_DS_CC_HASH_BASE \ |
4569a895 | 167 | basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ |
d7f245b1 | 168 | cc_hash_tag, \ |
a345e45d | 169 | typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc> |
4569a895 | 170 | |
30a96b3b BK |
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 | */ | |
4569a895 AT |
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, | |
a345e45d BK |
203 | typename _Alloc = std::allocator<char> > |
204 | class cc_hash_table : public PB_DS_CC_HASH_BASE | |
4569a895 AT |
205 | { |
206 | private: | |
a345e45d | 207 | typedef PB_DS_CC_HASH_BASE base_type; |
4569a895 AT |
208 | |
209 | public: | |
a345e45d BK |
210 | typedef cc_hash_tag container_category; |
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; | |
4569a895 | 215 | |
30a96b3b | 216 | /// Default constructor. |
4569a895 AT |
217 | cc_hash_table() { } |
218 | ||
30a96b3b BK |
219 | /// Constructor taking some policy objects. r_hash_fn will be |
220 | /// copied by the Hash_Fn object of the container object. | |
a345e45d | 221 | cc_hash_table(const hash_fn& h) |
3441f106 | 222 | : base_type(h) { } |
4569a895 | 223 | |
30a96b3b BK |
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. | |
4569a895 | 228 | cc_hash_table(const hash_fn& h, const eq_fn& e) |
3441f106 | 229 | : base_type(h, e) { } |
4569a895 | 230 | |
30a96b3b BK |
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. | |
4569a895 | 236 | cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch) |
3441f106 | 237 | : base_type(h, e, ch) { } |
4569a895 | 238 | |
30a96b3b BK |
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. | |
a345e45d BK |
245 | cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch, |
246 | const resize_policy& rp) | |
3441f106 | 247 | : base_type(h, e, ch, rp) { } |
4569a895 | 248 | |
30a96b3b BK |
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. | |
4569a895 AT |
252 | template<typename It> |
253 | cc_hash_table(It first, It last) | |
254 | { base_type::copy_from_range(first, last); } | |
255 | ||
30a96b3b BK |
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. | |
4569a895 AT |
259 | template<typename It> |
260 | cc_hash_table(It first, It last, const hash_fn& h) | |
3441f106 | 261 | : base_type(h) |
94df301f | 262 | { this->copy_from_range(first, last); } |
4569a895 | 263 | |
30a96b3b BK |
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. | |
4569a895 AT |
270 | template<typename It> |
271 | cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) | |
3441f106 | 272 | : base_type(h, e) |
94df301f | 273 | { this->copy_from_range(first, last); } |
4569a895 | 274 | |
30a96b3b BK |
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. | |
4569a895 AT |
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) | |
3441f106 | 285 | : base_type(h, e, ch) |
94df301f | 286 | { this->copy_from_range(first, last); } |
4569a895 | 287 | |
30a96b3b BK |
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. | |
4569a895 | 296 | template<typename It> |
a345e45d | 297 | cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, |
4569a895 | 298 | const comb_hash_fn& ch, const resize_policy& rp) |
3441f106 | 299 | : base_type(h, e, ch, rp) |
94df301f | 300 | { this->copy_from_range(first, last); } |
4569a895 AT |
301 | |
302 | cc_hash_table(const cc_hash_table& other) | |
3441f106 | 303 | : base_type((const base_type&)other) |
4569a895 AT |
304 | { } |
305 | ||
306 | virtual | |
307 | ~cc_hash_table() { } | |
308 | ||
a345e45d | 309 | cc_hash_table& |
4569a895 AT |
310 | operator=(const cc_hash_table& other) |
311 | { | |
3441f106 | 312 | if (this != &other) |
4569a895 AT |
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 | ||
a345e45d | 325 | #undef PB_DS_CC_HASH_BASE |
4569a895 AT |
326 | |
327 | ||
a345e45d | 328 | #define PB_DS_GP_HASH_BASE \ |
4569a895 | 329 | basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \ |
d7f245b1 | 330 | gp_hash_tag, \ |
a345e45d | 331 | typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc> |
4569a895 | 332 | |
30a96b3b BK |
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 | */ | |
4569a895 AT |
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, | |
a345e45d BK |
367 | typename _Alloc = std::allocator<char> > |
368 | class gp_hash_table : public PB_DS_GP_HASH_BASE | |
4569a895 AT |
369 | { |
370 | private: | |
a345e45d | 371 | typedef PB_DS_GP_HASH_BASE base_type; |
4569a895 AT |
372 | |
373 | public: | |
a345e45d BK |
374 | typedef gp_hash_tag container_category; |
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; | |
4569a895 | 380 | |
30a96b3b | 381 | /// Default constructor. |
4569a895 AT |
382 | gp_hash_table() { } |
383 | ||
30a96b3b BK |
384 | /// Constructor taking some policy objects. r_hash_fn will be |
385 | /// copied by the hash_fn object of the container object. | |
4569a895 | 386 | gp_hash_table(const hash_fn& h) |
3441f106 | 387 | : base_type(h) { } |
4569a895 | 388 | |
30a96b3b BK |
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. | |
4569a895 | 393 | gp_hash_table(const hash_fn& h, const eq_fn& e) |
3441f106 | 394 | : base_type(h, e) { } |
4569a895 | 395 | |
30a96b3b BK |
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. | |
4569a895 | 401 | gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp) |
3441f106 | 402 | : base_type(h, e, cp) { } |
4569a895 | 403 | |
30a96b3b BK |
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. | |
a345e45d | 410 | gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, |
4569a895 | 411 | const probe_fn& p) |
3441f106 | 412 | : base_type(h, e, cp, p) { } |
4569a895 | 413 | |
30a96b3b BK |
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. | |
a345e45d | 422 | gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp, |
4569a895 | 423 | const probe_fn& p, const resize_policy& rp) |
3441f106 | 424 | : base_type(h, e, cp, p, rp) { } |
4569a895 | 425 | |
30a96b3b BK |
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. | |
4569a895 AT |
429 | template<typename It> |
430 | gp_hash_table(It first, It last) | |
431 | { base_type::copy_from_range(first, last); } | |
432 | ||
30a96b3b BK |
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. | |
4569a895 AT |
437 | template<typename It> |
438 | gp_hash_table(It first, It last, const hash_fn& h) | |
3441f106 | 439 | : base_type(h) |
4569a895 AT |
440 | { base_type::copy_from_range(first, last); } |
441 | ||
30a96b3b BK |
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. | |
4569a895 AT |
448 | template<typename It> |
449 | gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e) | |
3441f106 | 450 | : base_type(h, e) |
4569a895 AT |
451 | { base_type::copy_from_range(first, last); } |
452 | ||
30a96b3b BK |
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. | |
4569a895 | 460 | template<typename It> |
a345e45d | 461 | gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, |
4569a895 | 462 | const comb_probe_fn& cp) |
3441f106 | 463 | : base_type(h, e, cp) |
4569a895 AT |
464 | { base_type::copy_from_range(first, last); } |
465 | ||
30a96b3b BK |
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. | |
4569a895 | 474 | template<typename It> |
a345e45d | 475 | gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e, |
4569a895 | 476 | const comb_probe_fn& cp, const probe_fn& p) |
3441f106 | 477 | : base_type(h, e, cp, p) |
4569a895 AT |
478 | { base_type::copy_from_range(first, last); } |
479 | ||
30a96b3b BK |
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. | |
4569a895 | 490 | template<typename It> |
a345e45d BK |
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, | |
4569a895 | 493 | const resize_policy& rp) |
3441f106 | 494 | : base_type(h, e, cp, p, rp) |
4569a895 AT |
495 | { base_type::copy_from_range(first, last); } |
496 | ||
497 | gp_hash_table(const gp_hash_table& other) | |
3441f106 | 498 | : base_type((const base_type&)other) |
4569a895 AT |
499 | { } |
500 | ||
501 | virtual | |
502 | ~gp_hash_table() { } | |
503 | ||
a345e45d | 504 | gp_hash_table& |
4569a895 AT |
505 | operator=(const gp_hash_table& other) |
506 | { | |
3441f106 | 507 | if (this != &other) |
4569a895 AT |
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 | }; | |
30a96b3b | 519 | //@} hash-based |
a345e45d | 520 | #undef PB_DS_GP_HASH_BASE |
4569a895 | 521 | |
30a96b3b BK |
522 | |
523 | /** | |
d8dd52a9 | 524 | * @defgroup branch-based Branch-Based |
30a96b3b BK |
525 | * @ingroup containers-pbds |
526 | * @{ | |
527 | */ | |
a345e45d BK |
528 | #define PB_DS_BRANCH_BASE \ |
529 | detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type | |
4569a895 | 530 | |
30a96b3b BK |
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 | */ | |
a345e45d BK |
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 | |
4569a895 AT |
556 | { |
557 | private: | |
a345e45d | 558 | typedef typename PB_DS_BRANCH_BASE base_type; |
4569a895 AT |
559 | |
560 | public: | |
a345e45d | 561 | typedef Node_Update node_update; |
4569a895 AT |
562 | |
563 | virtual | |
a345e45d | 564 | ~basic_branch() { } |
4569a895 AT |
565 | |
566 | protected: | |
30a96b3b BK |
567 | basic_branch() { } |
568 | ||
569 | basic_branch(const basic_branch& other) | |
570 | : base_type((const base_type&)other) { } | |
4569a895 | 571 | |
30a96b3b BK |
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 | }; | |
a345e45d | 599 | #undef PB_DS_BRANCH_BASE |
4569a895 AT |
600 | |
601 | ||
a345e45d BK |
602 | #define PB_DS_TREE_NODE_AND_IT_TRAITS \ |
603 | detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc> | |
4569a895 | 604 | |
a345e45d BK |
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> | |
4569a895 | 610 | |
30a96b3b BK |
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. | |
d8dd52a9 | 620 | * @tparam Node_Update Updates tree internal-nodes, |
30a96b3b BK |
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 | */ | |
4569a895 AT |
629 | template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>, |
630 | typename Tag = rb_tree_tag, | |
a345e45d BK |
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 | |
4569a895 AT |
636 | { |
637 | private: | |
a345e45d | 638 | typedef PB_DS_TREE_BASE base_type; |
4569a895 AT |
639 | |
640 | public: | |
30a96b3b | 641 | /// Comparison functor type. |
a345e45d | 642 | typedef Cmp_Fn cmp_fn; |
4569a895 AT |
643 | |
644 | tree() { } | |
645 | ||
30a96b3b BK |
646 | /// Constructor taking some policy objects. r_cmp_fn will be |
647 | /// copied by the Cmp_Fn object of the container object. | |
4569a895 | 648 | tree(const cmp_fn& c) |
3441f106 | 649 | : base_type(c) { } |
4569a895 | 650 | |
30a96b3b BK |
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. | |
4569a895 AT |
654 | template<typename It> |
655 | tree(It first, It last) | |
656 | { base_type::copy_from_range(first, last); } | |
657 | ||
30a96b3b BK |
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. | |
4569a895 AT |
662 | template<typename It> |
663 | tree(It first, It last, const cmp_fn& c) | |
30a96b3b | 664 | : base_type(c) |
4569a895 AT |
665 | { base_type::copy_from_range(first, last); } |
666 | ||
667 | tree(const tree& other) | |
3441f106 | 668 | : base_type((const base_type&)other) { } |
4569a895 AT |
669 | |
670 | virtual | |
671 | ~tree() { } | |
672 | ||
a345e45d | 673 | tree& |
4569a895 AT |
674 | operator=(const tree& other) |
675 | { | |
3441f106 | 676 | if (this != &other) |
4569a895 AT |
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 | ||
a345e45d BK |
689 | #undef PB_DS_TREE_BASE |
690 | #undef PB_DS_TREE_NODE_AND_IT_TRAITS | |
4569a895 AT |
691 | |
692 | ||
a345e45d BK |
693 | #define PB_DS_TRIE_NODE_AND_IT_TRAITS \ |
694 | detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc> | |
4569a895 | 695 | |
a345e45d BK |
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> | |
4569a895 | 701 | |
30a96b3b BK |
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. | |
d8dd52a9 | 711 | * @tparam Node_Update Updates trie internal-nodes, |
30a96b3b BK |
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 | */ | |
4569a895 AT |
720 | template<typename Key, |
721 | typename Mapped, | |
a345e45d BK |
722 | typename _ATraits = \ |
723 | typename detail::default_trie_access_traits<Key>::type, | |
4569a895 | 724 | typename Tag = pat_trie_tag, |
a345e45d BK |
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 | |
4569a895 AT |
732 | { |
733 | private: | |
a345e45d | 734 | typedef PB_DS_TRIE_BASE base_type; |
4569a895 AT |
735 | |
736 | public: | |
30a96b3b | 737 | /// Element access traits type. |
a345e45d | 738 | typedef _ATraits access_traits; |
4569a895 AT |
739 | |
740 | trie() { } | |
741 | ||
30a96b3b BK |
742 | /// Constructor taking some policy objects. r_access_traits will |
743 | /// be copied by the _ATraits object of the container object. | |
a345e45d | 744 | trie(const access_traits& t) |
3441f106 | 745 | : base_type(t) { } |
4569a895 | 746 | |
30a96b3b BK |
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. | |
4569a895 AT |
750 | template<typename It> |
751 | trie(It first, It last) | |
752 | { base_type::copy_from_range(first, last); } | |
753 | ||
30a96b3b BK |
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. | |
4569a895 | 757 | template<typename It> |
a345e45d | 758 | trie(It first, It last, const access_traits& t) |
3441f106 | 759 | : base_type(t) |
4569a895 AT |
760 | { base_type::copy_from_range(first, last); } |
761 | ||
762 | trie(const trie& other) | |
3441f106 | 763 | : base_type((const base_type&)other) { } |
4569a895 AT |
764 | |
765 | virtual | |
766 | ~trie() { } | |
767 | ||
a345e45d | 768 | trie& |
4569a895 AT |
769 | operator=(const trie& other) |
770 | { | |
3441f106 | 771 | if (this != &other) |
4569a895 AT |
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 | }; | |
30a96b3b | 783 | //@} branch-based |
a345e45d BK |
784 | #undef PB_DS_TRIE_BASE |
785 | #undef PB_DS_TRIE_NODE_AND_IT_TRAITS | |
4569a895 AT |
786 | |
787 | ||
30a96b3b | 788 | /** |
d8dd52a9 | 789 | * @defgroup list-based List-Based |
30a96b3b BK |
790 | * @ingroup containers-pbds |
791 | * @{ | |
792 | */ | |
a345e45d BK |
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 | |
4569a895 | 796 | |
30a96b3b BK |
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 | */ | |
4569a895 AT |
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, | |
a345e45d BK |
814 | class _Alloc = std::allocator<char> > |
815 | class list_update : public PB_DS_LU_BASE | |
4569a895 AT |
816 | { |
817 | private: | |
a345e45d | 818 | typedef typename PB_DS_LU_BASE base_type; |
4569a895 AT |
819 | |
820 | public: | |
a345e45d BK |
821 | typedef list_update_tag container_category; |
822 | typedef Eq_Fn eq_fn; | |
823 | typedef Update_Policy update_policy; | |
4569a895 AT |
824 | |
825 | list_update() { } | |
826 | ||
30a96b3b BK |
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. | |
4569a895 AT |
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) | |
3441f106 | 835 | : base_type((const base_type&)other) { } |
4569a895 AT |
836 | |
837 | virtual | |
838 | ~list_update() { } | |
839 | ||
a345e45d | 840 | list_update& |
4569a895 AT |
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 | }; | |
30a96b3b | 855 | //@} list-based |
a345e45d | 856 | #undef PB_DS_LU_BASE |
4569a895 | 857 | |
30a96b3b | 858 | // @} group containers-pbds |
5e11f978 | 859 | } // namespace __gnu_pbds |
4569a895 | 860 | |
a345e45d | 861 | #endif |