1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2020 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the terms
7 // of the GNU General Public License as published by the Free Software
8 // Foundation; either version 3, or (at your option) any later
9 // version.
10 
11 // This library is distributed in the hope that it will be useful, but
12 // WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 // General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26 
27 // Permission to use, copy, modify, sell, and distribute this software
28 // is hereby granted without fee, provided that the above copyright
29 // notice appears in all copies, and that both that copyright notice
30 // and this permission notice appear in supporting documentation. None
31 // of the above authors, nor IBM Haifa Research Laboratories, make any
32 // representation about the suitability of this software for any
33 // purpose. It is provided "as is" without express or implied
34 // warranty.
35 
36 /**
37  * @file assoc_container.hpp
38  * Contains associative containers.
39  */
40 
41 #ifndef PB_DS_ASSOC_CNTNR_HPP
42 #define PB_DS_ASSOC_CNTNR_HPP
43 
44 #include <bits/c++config.h>
45 #include <ext/typelist.h>
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>
49 #include <ext/pb_ds/detail/branch_policy/traits.hpp>
50 
51 namespace __gnu_pbds
52 {
53   /**
54    *  @defgroup containers-pbds Containers
55    *  @ingroup pbds
56    *  @{
57    */
58 
59   /**
60    *  @defgroup hash-based Hash-Based
61    *  @ingroup containers-pbds
62    *  @{
63    */
64 #define PB_DS_HASH_BASE \
65   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, \
66     typename __gnu_cxx::typelist::append< \
67     typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, \
68     detail::integral_constant<int, Store_Hash> >::type, Policy_Tl>::type>::type
69 
70   /**
71    *  @defgroup hash-detail Base and Policy Classes
72    *  @ingroup hash-based
73    */
74 
75   /**
76    *  A hashed container abstraction.
77    *
78    *  @tparam Key 	    	Key type.
79    *  @tparam Mapped 	    	Map type.
80    *  @tparam Hash_Fn	    	Hashing functor.
81    *  @tparam Eq_Fn	    	Equal functor.
82    *  @tparam Resize_Policy 	Resizes hash.
83    *  @tparam Store_Hash    	Indicates whether the hash value
84    *                            will be stored along with each key.
85    *  @tparam Tag 	    	Instantiating data structure type,
86    *			    	see container_tag.
87    *  @tparam Policy_TL	    	Policy typelist.
88    *  @tparam _Alloc 	    	Allocator type.
89    *
90    *  Base is dispatched at compile time via Tag, from the following
91    *  choices: cc_hash_tag, gp_hash_tag, and descendants of basic_hash_tag.
92    *
93    *  Base choices are: detail::cc_ht_map, detail::gp_ht_map
94    */
95   template<typename Key,
96 	   typename Mapped,
97 	   typename Hash_Fn,
98 	   typename Eq_Fn,
99 	   typename Resize_Policy,
100 	   bool Store_Hash,
101 	   typename Tag,
102 	   typename Policy_Tl,
103 	   typename _Alloc>
104   class basic_hash_table : public PB_DS_HASH_BASE
105   {
106   private:
107     typedef typename PB_DS_HASH_BASE 		base_type;
108 
109   public:
110     virtual
~basic_hash_table()111     ~basic_hash_table() { }
112 
113   protected:
basic_hash_table()114     basic_hash_table() { }
115 
basic_hash_table(const basic_hash_table & other)116     basic_hash_table(const basic_hash_table& other)
117     : base_type((const base_type&)other) { }
118 
119     template<typename T0>
basic_hash_table(T0 t0)120       basic_hash_table(T0 t0) : base_type(t0) { }
121 
122     template<typename T0, typename T1>
basic_hash_table(T0 t0,T1 t1)123       basic_hash_table(T0 t0, T1 t1) : base_type(t0, t1) { }
124 
125     template<typename T0, typename T1, typename T2>
basic_hash_table(T0 t0,T1 t1,T2 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>
basic_hash_table(T0 t0,T1 t1,T2 t2,T3 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>
basic_hash_table(T0 t0,T1 t1,T2 t2,T3 t3,T4 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>
basic_hash_table(T0 t0,T1 t1,T2 t2,T3 t3,T4 t4,T5 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>
basic_hash_table(T0 t0,T1 t1,T2 t2,T3 t3,T4 t4,T5 t5,T6 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>
basic_hash_table(T0 t0,T1 t1,T2 t2,T3 t3,T4 t4,T5 t5,T6 t6,T7 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>
basic_hash_table(T0 t0,T1 t1,T2 t2,T3 t3,T4 t4,T5 t5,T6 t6,T7 t7,T8 t8)153       basic_hash_table(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6,
154 		       T7 t7, T8 t8)
155       : base_type(t0, t1, t2, t3, t4, t5, t6, t7, t8)
156       { }
157 
158   private:
159     basic_hash_table&
160     operator=(const base_type&);
161   };
162 
163 #undef PB_DS_HASH_BASE
164 
165 
166 #define PB_DS_CC_HASH_BASE \
167   basic_hash_table<Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
168 		   cc_hash_tag,	\
169 	  typename __gnu_cxx::typelist::create1<Comb_Hash_Fn>::type, _Alloc>
170 
171 
172   /**
173    *  A collision-chaining hash-based associative container.
174    *
175    *  @tparam Key 	    	Key type.
176    *  @tparam Mapped 	    	Map type.
177    *  @tparam Hash_Fn	    	Hashing functor.
178    *  @tparam Eq_Fn	    	Equal functor.
179    *  @tparam Comb_Hash_Fn	Combining hash functor.
180    *                            If Hash_Fn is not null_type, then this
181    *                            is the ranged-hash functor; otherwise,
182    *                            this is the range-hashing functor.
183    *                    XXX(See Design::Hash-Based Containers::Hash Policies.)
184    *  @tparam Resize_Policy 	Resizes hash.
185    *  @tparam Store_Hash    	Indicates whether the hash value
186    *                            will be stored along with each key.
187    *                            If Hash_Fn is null_type, then the
188    *                            container will not compile if this
189    *                            value is true
190    *  @tparam _Alloc 	    	Allocator type.
191    *
192    *  Base tag choices are: 	cc_hash_tag.
193    *
194    *  Base is basic_hash_table.
195    */
196   template<typename Key,
197 	   typename Mapped,
198 	   typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
199 	   typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
200 	   typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
201 	   typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
202 	   bool Store_Hash = detail::default_store_hash,
203 	   typename _Alloc = std::allocator<char> >
204   class cc_hash_table :  public PB_DS_CC_HASH_BASE
205   {
206   private:
207     typedef PB_DS_CC_HASH_BASE 			base_type;
208 
209   public:
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;
215 
216     /// Default constructor.
cc_hash_table()217     cc_hash_table() { }
218 
219     /// Constructor taking some policy objects. r_hash_fn will be
220     /// copied by the Hash_Fn object of the container object.
cc_hash_table(const hash_fn & h)221     cc_hash_table(const hash_fn& h)
222     : base_type(h) { }
223 
224     /// Constructor taking some policy objects. r_hash_fn will be
225     /// copied by the hash_fn object of the container object, and
226     /// r_eq_fn will be copied by the eq_fn object of the container
227     /// object.
cc_hash_table(const hash_fn & h,const eq_fn & e)228     cc_hash_table(const hash_fn& h, const eq_fn& e)
229     : base_type(h, e) { }
230 
231     /// Constructor taking some policy objects. r_hash_fn will be
232     /// copied by the hash_fn object of the container object, r_eq_fn
233     /// will be copied by the eq_fn object of the container object,
234     /// and r_comb_hash_fn will be copied by the comb_hash_fn object
235     /// of the container object.
cc_hash_table(const hash_fn & h,const eq_fn & e,const comb_hash_fn & ch)236     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
237     : base_type(h, e, ch) { }
238 
239     /// Constructor taking some policy objects. r_hash_fn will be
240     /// copied by the hash_fn object of the container object, r_eq_fn
241     /// will be copied by the eq_fn object of the container object,
242     /// r_comb_hash_fn will be copied by the comb_hash_fn object of
243     /// the container object, and r_resize_policy will be copied by
244     /// the resize_policy object of the container object.
cc_hash_table(const hash_fn & h,const eq_fn & e,const comb_hash_fn & ch,const resize_policy & rp)245     cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
246 		  const resize_policy& rp)
247     : base_type(h, e, ch, rp) { }
248 
249     /// Constructor taking __iterators to a range of value_types. The
250     /// value_types between first_it and last_it will be inserted into
251     /// the container object.
252     template<typename It>
cc_hash_table(It first,It last)253     cc_hash_table(It first, It last)
254     { base_type::copy_from_range(first, last); }
255 
256     /// Constructor taking __iterators to a range of value_types and
257     /// some policy objects. The value_types between first_it and
258     /// last_it will be inserted into the container object.
259     template<typename It>
cc_hash_table(It first,It last,const hash_fn & h)260     cc_hash_table(It first, It last, const hash_fn& h)
261     : base_type(h)
262     { this->copy_from_range(first, last); }
263 
264     /// Constructor taking __iterators to a range of value_types and
265     /// some policy objects The value_types between first_it and
266     /// last_it will be inserted into the container object. r_hash_fn
267     /// will be copied by the hash_fn object of the container object,
268     /// and r_eq_fn will be copied by the eq_fn object of the
269     /// container object.
270     template<typename It>
cc_hash_table(It first,It last,const hash_fn & h,const eq_fn & e)271     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
272     : base_type(h, e)
273     { this->copy_from_range(first, last); }
274 
275     /// Constructor taking __iterators to a range of value_types and
276     /// some policy objects The value_types between first_it and
277     /// last_it will be inserted into the container object. r_hash_fn
278     /// will be copied by the hash_fn object of the container object,
279     /// r_eq_fn will be copied by the eq_fn object of the container
280     /// object, and r_comb_hash_fn will be copied by the comb_hash_fn
281     /// object of the container object.
282     template<typename It>
cc_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_hash_fn & ch)283     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
284 		  const comb_hash_fn& ch)
285     : base_type(h, e, ch)
286     { this->copy_from_range(first, last); }
287 
288     /// Constructor taking __iterators to a range of value_types and
289     /// some policy objects The value_types between first_it and
290     /// last_it will be inserted into the container object. r_hash_fn
291     /// will be copied by the hash_fn object of the container object,
292     /// r_eq_fn will be copied by the eq_fn object of the container
293     /// object, r_comb_hash_fn will be copied by the comb_hash_fn
294     /// object of the container object, and r_resize_policy will be
295     /// copied by the resize_policy object of the container object.
296     template<typename It>
cc_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_hash_fn & ch,const resize_policy & rp)297     cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
298 		  const comb_hash_fn& ch, const resize_policy& rp)
299     : base_type(h, e, ch, rp)
300     { this->copy_from_range(first, last); }
301 
cc_hash_table(const cc_hash_table & other)302     cc_hash_table(const cc_hash_table& other)
303     : base_type((const base_type&)other)
304     { }
305 
306     virtual
~cc_hash_table()307     ~cc_hash_table() { }
308 
309     cc_hash_table&
operator =(const cc_hash_table & other)310     operator=(const cc_hash_table& other)
311     {
312       if (this != &other)
313 	{
314 	  cc_hash_table tmp(other);
315 	  swap(tmp);
316 	}
317       return *this;
318     }
319 
320     void
swap(cc_hash_table & other)321     swap(cc_hash_table& other)
322     { base_type::swap(other); }
323   };
324 
325 #undef PB_DS_CC_HASH_BASE
326 
327 
328 #define PB_DS_GP_HASH_BASE \
329   basic_hash_table<Key, Mapped,	Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
330 		   gp_hash_tag, \
331   typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, _Alloc>
332 
333 
334   /**
335    *  A general-probing hash-based associative container.
336    *
337    *  @tparam Key 	    	Key type.
338    *  @tparam Mapped 	    	Map type.
339    *  @tparam Hash_Fn	    	Hashing functor.
340    *  @tparam Eq_Fn	    	Equal functor.
341    *  @tparam Comb_Probe_Fn	Combining probe functor.
342    *                            If Hash_Fn is not null_type, then this
343    *                            is the ranged-probe functor; otherwise,
344    *                            this is the range-hashing functor.
345    *                    XXX See Design::Hash-Based Containers::Hash Policies.
346    *  @tparam Probe_Fn		Probe functor.
347    *  @tparam Resize_Policy 	Resizes hash.
348    *  @tparam Store_Hash    	Indicates whether the hash value
349    *                            will be stored along with each key.
350    *                            If Hash_Fn is null_type, then the
351    *                            container will not compile if this
352    *                            value is true
353    *  @tparam _Alloc 	    	Allocator type.
354    *
355    *  Base tag choices are: 	gp_hash_tag.
356    *
357    *  Base is basic_hash_table.
358    */
359   template<typename Key,
360 	   typename Mapped,
361 	   typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
362 	   typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
363 	   typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
364 	   typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
365 	   typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
366 	   bool Store_Hash = detail::default_store_hash,
367 	   typename _Alloc = std::allocator<char> >
368   class gp_hash_table : public PB_DS_GP_HASH_BASE
369   {
370   private:
371     typedef PB_DS_GP_HASH_BASE 			base_type;
372 
373   public:
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;
380 
381     /// Default constructor.
gp_hash_table()382     gp_hash_table() { }
383 
384     /// Constructor taking some policy objects. r_hash_fn will be
385     /// copied by the hash_fn object of the container object.
gp_hash_table(const hash_fn & h)386     gp_hash_table(const hash_fn& h)
387     : base_type(h) { }
388 
389     /// Constructor taking some policy objects. r_hash_fn will be
390     /// copied by the hash_fn object of the container object, and
391     /// r_eq_fn will be copied by the eq_fn object of the container
392     /// object.
gp_hash_table(const hash_fn & h,const eq_fn & e)393     gp_hash_table(const hash_fn& h, const eq_fn& e)
394     : base_type(h, e) { }
395 
396     /// Constructor taking some policy objects. r_hash_fn will be
397     /// copied by the hash_fn object of the container object, r_eq_fn
398     /// will be copied by the eq_fn object of the container object,
399     /// and r_comb_probe_fn will be copied by the comb_probe_fn object
400     /// of the container object.
gp_hash_table(const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp)401     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
402     : base_type(h, e, cp) { }
403 
404     /// Constructor taking some policy objects. r_hash_fn will be
405     /// copied by the hash_fn object of the container object, r_eq_fn
406     /// will be copied by the eq_fn object of the container object,
407     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
408     /// the container object, and r_probe_fn will be copied by the
409     /// probe_fn object of the container object.
gp_hash_table(const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp,const probe_fn & p)410     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
411 		  const probe_fn& p)
412     : base_type(h, e, cp, p) { }
413 
414     /// Constructor taking some policy objects. r_hash_fn will be
415     /// copied by the hash_fn object of the container object, r_eq_fn
416     /// will be copied by the eq_fn object of the container object,
417     /// r_comb_probe_fn will be copied by the comb_probe_fn object of
418     /// the container object, r_probe_fn will be copied by the
419     /// probe_fn object of the container object, and r_resize_policy
420     /// will be copied by the Resize_Policy object of the container
421     /// object.
gp_hash_table(const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp,const probe_fn & p,const resize_policy & rp)422     gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
423 		  const probe_fn& p, const resize_policy& rp)
424     : base_type(h, e, cp, p, rp) { }
425 
426     /// Constructor taking __iterators to a range of value_types. The
427     /// value_types between first_it and last_it will be inserted into
428     /// the container object.
429     template<typename It>
gp_hash_table(It first,It last)430     gp_hash_table(It first, It last)
431     { base_type::copy_from_range(first, last); }
432 
433     /// Constructor taking __iterators to a range of value_types and
434     /// some policy objects. The value_types between first_it and
435     /// last_it will be inserted into the container object. r_hash_fn
436     /// will be copied by the hash_fn object of the container object.
437     template<typename It>
gp_hash_table(It first,It last,const hash_fn & h)438     gp_hash_table(It first, It last, const hash_fn& h)
439     : base_type(h)
440     { base_type::copy_from_range(first, last); }
441 
442     /// Constructor taking __iterators to a range of value_types and
443     /// some policy objects. The value_types between first_it and
444     /// last_it will be inserted into the container object. r_hash_fn
445     /// will be copied by the hash_fn object of the container object,
446     /// and r_eq_fn will be copied by the eq_fn object of the
447     /// container object.
448     template<typename It>
gp_hash_table(It first,It last,const hash_fn & h,const eq_fn & e)449     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
450     : base_type(h, e)
451     { base_type::copy_from_range(first, last); }
452 
453     /// Constructor taking __iterators to a range of value_types and
454     /// some policy objects. The value_types between first_it and
455     /// last_it will be inserted into the container object. r_hash_fn
456     /// will be copied by the hash_fn object of the container object,
457     /// r_eq_fn will be copied by the eq_fn object of the container
458     /// object, and r_comb_probe_fn will be copied by the
459     /// comb_probe_fn object of the container object.
460     template<typename It>
gp_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp)461     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
462 		  const comb_probe_fn& cp)
463     : base_type(h, e, cp)
464     { base_type::copy_from_range(first, last); }
465 
466     /// Constructor taking __iterators to a range of value_types and
467     /// some policy objects. The value_types between first_it and
468     /// last_it will be inserted into the container object. r_hash_fn
469     /// will be copied by the hash_fn object of the container object,
470     /// r_eq_fn will be copied by the eq_fn object of the container
471     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
472     /// object of the container object, and r_probe_fn will be copied
473     /// by the probe_fn object of the container object.
474     template<typename It>
gp_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp,const probe_fn & p)475     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
476 		  const comb_probe_fn& cp, const probe_fn& p)
477     : base_type(h, e, cp, p)
478     { base_type::copy_from_range(first, last); }
479 
480     /// Constructor taking __iterators to a range of value_types and
481     /// some policy objects. The value_types between first_it and
482     /// last_it will be inserted into the container object. r_hash_fn
483     /// will be copied by the hash_fn object of the container object,
484     /// r_eq_fn will be copied by the eq_fn object of the container
485     /// object, r_comb_probe_fn will be copied by the comb_probe_fn
486     /// object of the container object, r_probe_fn will be copied by
487     /// the probe_fn object of the container object, and
488     /// r_resize_policy will be copied by the resize_policy object of
489     /// the container object.
490     template<typename It>
gp_hash_table(It first,It last,const hash_fn & h,const eq_fn & e,const comb_probe_fn & cp,const probe_fn & p,const resize_policy & rp)491     gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
492 		  const comb_probe_fn& cp, const probe_fn& p,
493 		  const resize_policy& rp)
494     : base_type(h, e, cp, p, rp)
495     { base_type::copy_from_range(first, last); }
496 
gp_hash_table(const gp_hash_table & other)497     gp_hash_table(const gp_hash_table& other)
498     : base_type((const base_type&)other)
499     { }
500 
501     virtual
~gp_hash_table()502     ~gp_hash_table() { }
503 
504     gp_hash_table&
operator =(const gp_hash_table & other)505     operator=(const gp_hash_table& other)
506     {
507       if (this != &other)
508 	{
509 	  gp_hash_table tmp(other);
510 	  swap(tmp);
511 	}
512       return *this;
513     }
514 
515     void
swap(gp_hash_table & other)516     swap(gp_hash_table& other)
517     { base_type::swap(other); }
518   };
519   ///@} hash-based
520 #undef PB_DS_GP_HASH_BASE
521 
522 
523   /**
524    *  @defgroup branch-based Branch-Based
525    *  @ingroup containers-pbds
526    *  @{
527    */
528 #define PB_DS_BRANCH_BASE \
529   detail::container_base_dispatch<Key, Mapped, _Alloc, Tag, Policy_Tl>::type
530 
531   /**
532    *  @defgroup branch-detail Base and Policy Classes
533    *  @ingroup branch-based
534    */
535 
536   /**
537    *  A branched, tree-like (tree, trie) container abstraction.
538    *
539    *  @tparam Key 	  	Key type.
540    *  @tparam Mapped 	  	Map type.
541    *  @tparam Tag 	  	Instantiating data structure type,
542    *                            see container_tag.
543    *  @tparam Node_Update 	Updates nodes, restores invariants.
544    *  @tparam Policy_TL         Policy typelist.
545    *  @tparam _Alloc 	  	Allocator type.
546    *
547    *  Base is dispatched at compile time via Tag, from the following
548    *  choices: tree_tag, trie_tag, and their descendants.
549    *
550    *  Base choices are: detail::ov_tree_map, detail::rb_tree_map,
551    *		       	detail::splay_tree_map, and detail::pat_trie_map.
552    */
553   template<typename Key, typename Mapped, typename Tag,
554 	   typename Node_Update, typename Policy_Tl, typename _Alloc>
555   class basic_branch : public PB_DS_BRANCH_BASE
556   {
557   private:
558     typedef typename PB_DS_BRANCH_BASE 	       	base_type;
559 
560   public:
561     typedef Node_Update 			node_update;
562 
563     virtual
~basic_branch()564     ~basic_branch() { }
565 
566   protected:
basic_branch()567     basic_branch() { }
568 
basic_branch(const basic_branch & other)569     basic_branch(const basic_branch& other)
570     : base_type((const base_type&)other) { }
571 
572     template<typename T0>
basic_branch(T0 t0)573       basic_branch(T0 t0) : base_type(t0) { }
574 
575     template<typename T0, typename T1>
basic_branch(T0 t0,T1 t1)576       basic_branch(T0 t0, T1 t1) : base_type(t0, t1) { }
577 
578     template<typename T0, typename T1, typename T2>
basic_branch(T0 t0,T1 t1,T2 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>
basic_branch(T0 t0,T1 t1,T2 t2,T3 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>
basic_branch(T0 t0,T1 t1,T2 t2,T3 t3,T4 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>
basic_branch(T0 t0,T1 t1,T2 t2,T3 t3,T4 t4,T5 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>
basic_branch(T0 t0,T1 t1,T2 t2,T3 t3,T4 t4,T5 t5,T6 t6)596       basic_branch(T0 t0, T1 t1, T2 t2, T3 t3, T4 t4, T5 t5, T6 t6)
597       : base_type(t0, t1, t2, t3, t4, t5, t6) { }
598   };
599 #undef PB_DS_BRANCH_BASE
600 
601 
602 #define PB_DS_TREE_NODE_AND_IT_TRAITS \
603   detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag,_Alloc>
604 
605 #define PB_DS_TREE_BASE \
606   basic_branch<Key,Mapped, Tag, \
607 	       typename PB_DS_TREE_NODE_AND_IT_TRAITS::node_update, \
608 	       typename __gnu_cxx::typelist::create2<Cmp_Fn, \
609 	       PB_DS_TREE_NODE_AND_IT_TRAITS>::type, _Alloc>
610 
611 
612   /**
613    *  A tree-based container.
614    *
615    *  @tparam Key 	 	Key type.
616    *  @tparam Mapped 	 	Map type.
617    *  @tparam Cmp_Fn	 	Comparison functor.
618    *  @tparam Tag 	 	Instantiating data structure type,
619    *                            see container_tag.
620    *  @tparam Node_Update 	Updates tree internal-nodes,
621    *                            restores invariants when invalidated.
622    *                     XXX See design::tree-based-containers::node invariants.
623    *  @tparam _Alloc 	 	Allocator type.
624    *
625    *  Base tag choices are: ov_tree_tag, rb_tree_tag, splay_tree_tag.
626    *
627    *  Base is basic_branch.
628    */
629   template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
630 	   typename Tag = rb_tree_tag,
631 	   template<typename Node_CItr, typename Node_Itr,
632 		    typename Cmp_Fn_, typename _Alloc_>
633 	   class Node_Update = null_node_update,
634 	   typename _Alloc = std::allocator<char> >
635   class tree : public PB_DS_TREE_BASE
636   {
637   private:
638     typedef PB_DS_TREE_BASE 			base_type;
639 
640   public:
641     /// Comparison functor type.
642     typedef Cmp_Fn 				cmp_fn;
643 
tree()644     tree() { }
645 
646     /// Constructor taking some policy objects. r_cmp_fn will be
647     /// copied by the Cmp_Fn object of the container object.
tree(const cmp_fn & c)648     tree(const cmp_fn& c)
649     : base_type(c) { }
650 
651     /// Constructor taking __iterators to a range of value_types. The
652     /// value_types between first_it and last_it will be inserted into
653     /// the container object.
654     template<typename It>
tree(It first,It last)655     tree(It first, It last)
656     { base_type::copy_from_range(first, last); }
657 
658     /// Constructor taking __iterators to a range of value_types and
659     /// some policy objects The value_types between first_it and
660     /// last_it will be inserted into the container object. r_cmp_fn
661     /// will be copied by the cmp_fn object of the container object.
662     template<typename It>
tree(It first,It last,const cmp_fn & c)663     tree(It first, It last, const cmp_fn& c)
664     : base_type(c)
665     { base_type::copy_from_range(first, last); }
666 
tree(const tree & other)667     tree(const tree& other)
668     : base_type((const base_type&)other) { }
669 
670     virtual
~tree()671     ~tree() { }
672 
673     tree&
operator =(const tree & other)674     operator=(const tree& other)
675     {
676       if (this != &other)
677 	{
678 	  tree tmp(other);
679 	  swap(tmp);
680 	}
681       return *this;
682     }
683 
684     void
swap(tree & other)685     swap(tree& other)
686     { base_type::swap(other); }
687   };
688 
689 #undef PB_DS_TREE_BASE
690 #undef PB_DS_TREE_NODE_AND_IT_TRAITS
691 
692 
693 #define PB_DS_TRIE_NODE_AND_IT_TRAITS \
694   detail::trie_traits<Key,Mapped,_ATraits,Node_Update,Tag,_Alloc>
695 
696 #define PB_DS_TRIE_BASE \
697   basic_branch<Key,Mapped,Tag, \
698 	       typename PB_DS_TRIE_NODE_AND_IT_TRAITS::node_update, \
699 	       typename __gnu_cxx::typelist::create2<_ATraits, \
700 	       PB_DS_TRIE_NODE_AND_IT_TRAITS >::type, _Alloc>
701 
702 
703   /**
704    *  A trie-based container.
705    *
706    *  @tparam Key 	  	Key type.
707    *  @tparam Mapped 	  	Map type.
708    *  @tparam _ATraits	  	Element access traits.
709    *  @tparam Tag 	  	Instantiating data structure type,
710    *                            see container_tag.
711    *  @tparam Node_Update 	Updates trie internal-nodes,
712    *                            restores invariants when invalidated.
713    *                     XXX See design::tree-based-containers::node invariants.
714    *  @tparam _Alloc 	  	Allocator type.
715    *
716    *  Base tag choice is pat_trie_tag.
717    *
718    *  Base is basic_branch.
719    */
720   template<typename Key,
721 	   typename Mapped,
722 	   typename _ATraits = \
723 		    typename detail::default_trie_access_traits<Key>::type,
724 	   typename Tag = pat_trie_tag,
725 	   template<typename Node_CItr,
726 		    typename Node_Itr,
727 		    typename _ATraits_,
728 		    typename _Alloc_>
729 	   class Node_Update = null_node_update,
730 	   typename _Alloc = std::allocator<char> >
731   class trie : public PB_DS_TRIE_BASE
732   {
733   private:
734     typedef PB_DS_TRIE_BASE			base_type;
735 
736   public:
737     /// Element access traits type.
738     typedef _ATraits 				access_traits;
739 
trie()740     trie() { }
741 
742     /// Constructor taking some policy objects. r_access_traits will
743     /// be copied by the _ATraits object of the container object.
trie(const access_traits & t)744     trie(const access_traits& t)
745     : base_type(t) { }
746 
747     /// Constructor taking __iterators to a range of value_types. The
748     /// value_types between first_it and last_it will be inserted into
749     /// the container object.
750     template<typename It>
trie(It first,It last)751     trie(It first, It last)
752     { base_type::copy_from_range(first, last); }
753 
754     /// Constructor taking __iterators to a range of value_types and
755     /// some policy objects. The value_types between first_it and
756     /// last_it will be inserted into the container object.
757     template<typename It>
trie(It first,It last,const access_traits & t)758     trie(It first, It last, const access_traits& t)
759     : base_type(t)
760     { base_type::copy_from_range(first, last); }
761 
trie(const trie & other)762     trie(const trie& other)
763     : base_type((const base_type&)other) { }
764 
765     virtual
~trie()766     ~trie() { }
767 
768     trie&
operator =(const trie & other)769     operator=(const trie& other)
770     {
771       if (this != &other)
772 	{
773 	  trie tmp(other);
774 	  swap(tmp);
775 	}
776       return *this;
777     }
778 
779     void
swap(trie & other)780     swap(trie& other)
781     { base_type::swap(other); }
782   };
783   ///@} branch-based
784 #undef PB_DS_TRIE_BASE
785 #undef PB_DS_TRIE_NODE_AND_IT_TRAITS
786 
787 
788   /**
789    *  @defgroup list-based List-Based
790    *  @ingroup containers-pbds
791    *  @{
792    */
793 #define PB_DS_LU_BASE \
794   detail::container_base_dispatch<Key, Mapped, _Alloc, list_update_tag,	\
795     typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type>::type
796 
797 
798   /**
799    *  A list-update based associative container.
800    *
801    *  @tparam Key 	    	Key type.
802    *  @tparam Mapped 	    	Map type.
803    *  @tparam Eq_Fn	    	Equal functor.
804    *  @tparam Update_Policy	Update policy, determines when an element
805    *                            will be moved to the front of the list.
806    *  @tparam _Alloc 	    	Allocator type.
807    *
808    *  Base is detail::lu_map.
809    */
810   template<typename Key,
811 	   typename Mapped,
812 	   class Eq_Fn = typename detail::default_eq_fn<Key>::type,
813 	   class Update_Policy = detail::default_update_policy::type,
814 	   class _Alloc = std::allocator<char> >
815   class list_update : public PB_DS_LU_BASE
816   {
817   private:
818     typedef typename PB_DS_LU_BASE 		base_type;
819 
820   public:
821     typedef list_update_tag	       		container_category;
822     typedef Eq_Fn 				eq_fn;
823     typedef Update_Policy 			update_policy;
824 
list_update()825     list_update() { }
826 
827     /// Constructor taking __iterators to a range of value_types. The
828     /// value_types between first_it and last_it will be inserted into
829     /// the container object.
830     template<typename It>
list_update(It first,It last)831     list_update(It first, It last)
832     { base_type::copy_from_range(first, last); }
833 
list_update(const list_update & other)834     list_update(const list_update& other)
835     : base_type((const base_type&)other) { }
836 
837     virtual
~list_update()838     ~list_update() { }
839 
840     list_update&
operator =(const list_update & other)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
swap(list_update & other)852     swap(list_update& other)
853     { base_type::swap(other); }
854   };
855   ///@} list-based
856 #undef PB_DS_LU_BASE
857 
858   /// @} group containers-pbds
859 } // namespace __gnu_pbds
860 
861 #endif
862