libstdc++
assoc_container.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005, 2006, 2009, 2010 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>
49 #include <ext/pb_ds/detail/basic_tree_policy/traits.hpp>
50 
51 namespace __gnu_pbds
52 {
53  /** @defgroup pbds Policy-Based Data Structures
54  * @ingroup extensions
55  *
56  * This is a library of policy-based elementary data structures:
57  * associative containers and priority queues. It is designed for
58  * high-performance, flexibility, semantic safety, and conformance
59  * to the corresponding containers in std (except for some points
60  * where it differs by design).
61  *
62  * For details, see:
63  * http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
64  *
65  * @{
66  */
67 
68 #define PB_DS_BASE_C_DEC \
69  detail::container_base_dispatch<Key, Mapped, Tag, Policy_Tl, Allocator>::type
70 
71  /// An abstract basic associative container.
72  template<typename Key,
73  typename Mapped,
74  typename Tag,
75  typename Policy_Tl,
76  typename Allocator>
77  class container_base : public PB_DS_BASE_C_DEC
78  {
79  private:
80  typedef typename PB_DS_BASE_C_DEC base_type;
81 
82  public:
83  typedef Tag container_category;
84  typedef Allocator allocator_type;
85  typedef typename allocator_type::size_type size_type;
86  typedef typename allocator_type::difference_type difference_type;
87 
88  // key_type
89  typedef typename allocator_type::template rebind<Key>::other::value_type key_type;
90  typedef typename allocator_type::template rebind<key_type>::other key_rebind;
91  typedef typename key_rebind::reference key_reference;
92  typedef typename key_rebind::const_reference const_key_reference;
93  typedef typename key_rebind::pointer key_pointer;
94  typedef typename key_rebind::const_pointer const_key_pointer;
95 
96  // mapped_type
97  typedef Mapped mapped_type;
98  typedef typename allocator_type::template rebind<mapped_type>::other mapped_rebind;
99  typedef typename mapped_rebind::reference mapped_reference;
100  typedef typename mapped_rebind::const_reference const_mapped_reference;
101  typedef typename mapped_rebind::pointer mapped_pointer;
102  typedef typename mapped_rebind::const_pointer const_mapped_pointer;
103 
104  // value_type
105  typedef typename base_type::value_type value_type;
106  typedef typename allocator_type::template rebind<value_type>::other value_rebind;
107  typedef typename value_rebind::reference reference;
108  typedef typename value_rebind::const_reference const_reference;
109  typedef typename value_rebind::pointer pointer;
110  typedef typename value_rebind::const_pointer const_pointer;
111 
112  // iterators
113  typedef typename base_type::iterator iterator;
114  typedef typename base_type::const_iterator const_iterator;
115  typedef typename base_type::point_iterator point_iterator;
116  typedef typename base_type::const_point_iterator const_point_iterator;
117 
118  virtual
119  ~container_base() { }
120 
121  protected:
122 #define PB_DS_CLASS_NAME container_base
124 #undef PB_DS_CLASS_NAME
125  };
126 
127 #undef PB_DS_BASE_C_DEC
128 
129 
130 #define PB_DS_BASE_C_DEC \
131  container_base<Key, Mapped, Tag, typename __gnu_cxx::typelist::append< \
132  typename __gnu_cxx::typelist::create4<Hash_Fn, Eq_Fn, Resize_Policy, detail::integral_constant<int, Store_Hash> >::type, Policy_TL>::type, Allocator>
133 
134  /// An abstract basic hash-based associative container.
135  template<typename Key,
136  typename Mapped,
137  typename Hash_Fn,
138  typename Eq_Fn,
139  typename Resize_Policy,
140  bool Store_Hash,
141  typename Tag,
142  typename Policy_TL,
143  typename Allocator>
144  class basic_hash_table : public PB_DS_BASE_C_DEC
145  {
146  private:
147  typedef PB_DS_BASE_C_DEC base_type;
148 
149  public:
150  virtual
151  ~basic_hash_table() { }
152 
153  protected:
154 #define PB_DS_CLASS_NAME basic_hash_table
156 #undef PB_DS_CLASS_NAME
157 
158  private:
160  operator=(const base_type&);
161  };
162 
163 #undef PB_DS_BASE_C_DEC
164 
165 
166 #define PB_DS_BASE_C_DEC \
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, Allocator>
170 
171  /// A concrete collision-chaining hash-based associative container.
172  template<typename Key,
173  typename Mapped,
174  typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
175  typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
176  typename Comb_Hash_Fn = detail::default_comb_hash_fn::type,
177  typename Resize_Policy = typename detail::default_resize_policy<Comb_Hash_Fn>::type,
178  bool Store_Hash = detail::default_store_hash,
179  typename Allocator = std::allocator<char> >
180  class cc_hash_table : public PB_DS_BASE_C_DEC
181  {
182  private:
183  typedef PB_DS_BASE_C_DEC base_type;
184 
185  public:
186  typedef Hash_Fn hash_fn;
187  typedef Eq_Fn eq_fn;
188  typedef Resize_Policy resize_policy;
189  typedef Comb_Hash_Fn comb_hash_fn;
190 
191  // Default constructor.
192  cc_hash_table() { }
193 
194  // Constructor taking some policy objects. r_hash_fn will be
195  // copied by the Hash_Fn object of the container object.
196  cc_hash_table(const hash_fn& h)
197  : base_type(h) { }
198 
199  // Constructor taking some policy objects. r_hash_fn will be
200  // copied by the hash_fn object of the container object, and
201  // r_eq_fn will be copied by the eq_fn object of the container
202  // object.
203  cc_hash_table(const hash_fn& h, const eq_fn& e)
204  : base_type(h, e) { }
205 
206  // Constructor taking some policy objects. r_hash_fn will be
207  // copied by the hash_fn object of the container object, r_eq_fn
208  // will be copied by the eq_fn object of the container object, and
209  // r_comb_hash_fn will be copied by the comb_hash_fn object of the
210  // container object.
211  cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch)
212  : base_type(h, e, ch) { }
213 
214  // Constructor taking some policy objects. r_hash_fn will be
215  // copied by the hash_fn object of the container object, r_eq_fn
216  // will be copied by the eq_fn object of the container object,
217  // r_comb_hash_fn will be copied by the comb_hash_fn object of the
218  // container object, and r_resize_policy will be copied by the
219  // resize_policy object of the container object.
220  cc_hash_table(const hash_fn& h, const eq_fn& e, const comb_hash_fn& ch,
221  const resize_policy& rp)
222  : base_type(h, e, ch, rp) { }
223 
224  // Constructor taking __iterators to a range of value_types. The
225  // value_types between first_it and last_it will be inserted into
226  // the container object.
227  template<typename It>
228  cc_hash_table(It first, It last)
229  { base_type::copy_from_range(first, last); }
230 
231  // Constructor taking __iterators to a range of value_types and
232  // some policy objects. The value_types between first_it and
233  // last_it will be inserted into the container object.
234  template<typename It>
235  cc_hash_table(It first, It last, const hash_fn& h)
236  : base_type(h)
237  { copy_from_range(first, last); }
238 
239  // Constructor taking __iterators to a range of value_types and
240  // some policy objects The value_types between first_it and
241  // last_it will be inserted into the container object. r_hash_fn
242  // will be copied by the hash_fn object of the container object,
243  // and r_eq_fn will be copied by the eq_fn object of the container
244  // object.
245  template<typename It>
246  cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
247  : base_type(h, e)
248  { copy_from_range(first, last); }
249 
250  // Constructor taking __iterators to a range of value_types and
251  // some policy objects The value_types between first_it and
252  // last_it will be inserted into the container object. r_hash_fn
253  // will be copied by the hash_fn object of the container object,
254  // r_eq_fn will be copied by the eq_fn object of the container
255  // object, and r_comb_hash_fn will be copied by the comb_hash_fn
256  // object of the container object.
257  template<typename It>
258  cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
259  const comb_hash_fn& ch)
260  : base_type(h, e, ch)
261  { copy_from_range(first, last); }
262 
263  // Constructor taking __iterators to a range of value_types and
264  // some policy objects The value_types between first_it and
265  // last_it will be inserted into the container object. r_hash_fn
266  // will be copied by the hash_fn object of the container object,
267  // r_eq_fn will be copied by the eq_fn object of the container
268  // object, r_comb_hash_fn will be copied by the comb_hash_fn
269  // object of the container object, and r_resize_policy will be
270  // copied by the resize_policy object of the container object.
271  template<typename It>
272  cc_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
273  const comb_hash_fn& ch, const resize_policy& rp)
274  : base_type(h, e, ch, rp)
275  { copy_from_range(first, last); }
276 
277  cc_hash_table(const cc_hash_table& other)
278  : base_type((const base_type&)other)
279  { }
280 
281  virtual
282  ~cc_hash_table() { }
283 
284  cc_hash_table&
285  operator=(const cc_hash_table& other)
286  {
287  if (this != &other)
288  {
289  cc_hash_table tmp(other);
290  swap(tmp);
291  }
292  return *this;
293  }
294 
295  void
296  swap(cc_hash_table& other)
297  { base_type::swap(other); }
298  };
299 
300 #undef PB_DS_BASE_C_DEC
301 
302 
303 #define PB_DS_BASE_C_DEC \
304  basic_hash_table<Key, Mapped, Hash_Fn, Eq_Fn, Resize_Policy, Store_Hash, \
305  gp_hash_tag, \
306  typename __gnu_cxx::typelist::create2<Comb_Probe_Fn, Probe_Fn>::type, Allocator>
307 
308  /// A concrete general-probing hash-based associative container.
309  template<typename Key,
310  typename Mapped,
311  typename Hash_Fn = typename detail::default_hash_fn<Key>::type,
312  typename Eq_Fn = typename detail::default_eq_fn<Key>::type,
313  typename Comb_Probe_Fn = detail::default_comb_hash_fn::type,
314  typename Probe_Fn = typename detail::default_probe_fn<Comb_Probe_Fn>::type,
315  typename Resize_Policy = typename detail::default_resize_policy<Comb_Probe_Fn>::type,
316  bool Store_Hash = detail::default_store_hash,
317  typename Allocator = std::allocator<char> >
318  class gp_hash_table : public PB_DS_BASE_C_DEC
319  {
320  private:
321  typedef PB_DS_BASE_C_DEC base_type;
322 
323  public:
324  typedef Hash_Fn hash_fn;
325  typedef Eq_Fn eq_fn;
326  typedef Comb_Probe_Fn comb_probe_fn;
327  typedef Probe_Fn probe_fn;
328  typedef Resize_Policy resize_policy;
329 
330  // Default constructor.
331  gp_hash_table() { }
332 
333  // Constructor taking some policy objects. r_hash_fn will be
334  // copied by the hash_fn object of the container object.
335  gp_hash_table(const hash_fn& h)
336  : base_type(h) { }
337 
338  // Constructor taking some policy objects. r_hash_fn will be
339  // copied by the hash_fn object of the container object, and
340  // r_eq_fn will be copied by the eq_fn object of the container
341  // object.
342  gp_hash_table(const hash_fn& h, const eq_fn& e)
343  : base_type(h, e) { }
344 
345  // Constructor taking some policy objects. r_hash_fn will be
346  // copied by the hash_fn object of the container object, r_eq_fn
347  // will be copied by the eq_fn object of the container object, and
348  // r_comb_probe_fn will be copied by the comb_probe_fn object of
349  // the container object.
350  gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp)
351  : base_type(h, e, cp) { }
352 
353  // Constructor taking some policy objects. r_hash_fn will be
354  // copied by the hash_fn object of the container object, r_eq_fn
355  // will be copied by the eq_fn object of the container object,
356  // r_comb_probe_fn will be copied by the comb_probe_fn object of
357  // the container object, and r_probe_fn will be copied by the
358  // probe_fn object of the container object.
359  gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
360  const probe_fn& p)
361  : base_type(h, e, cp, p) { }
362 
363  // Constructor taking some policy objects. r_hash_fn will be
364  // copied by the hash_fn object of the container object, r_eq_fn
365  // will be copied by the eq_fn object of the container object,
366  // r_comb_probe_fn will be copied by the comb_probe_fn object of
367  // the container object, r_probe_fn will be copied by the probe_fn
368  // object of the container object, and r_resize_policy will be
369  // copied by the Resize_Policy object of the container object.
370  gp_hash_table(const hash_fn& h, const eq_fn& e, const comb_probe_fn& cp,
371  const probe_fn& p, const resize_policy& rp)
372  : base_type(h, e, cp, p, rp) { }
373 
374  // Constructor taking __iterators to a range of value_types. The
375  // value_types between first_it and last_it will be inserted into
376  // the container object.
377  template<typename It>
378  gp_hash_table(It first, It last)
379  { base_type::copy_from_range(first, last); }
380 
381  // Constructor taking __iterators to a range of value_types and
382  // some policy objects. The value_types between first_it and
383  // last_it will be inserted into the container object. r_hash_fn
384  // will be copied by the hash_fn object of the container object.
385  template<typename It>
386  gp_hash_table(It first, It last, const hash_fn& h)
387  : base_type(h)
388  { base_type::copy_from_range(first, last); }
389 
390  // Constructor taking __iterators to a range of value_types and
391  // some policy objects. The value_types between first_it and
392  // last_it will be inserted into the container object. r_hash_fn
393  // will be copied by the hash_fn object of the container object,
394  // and r_eq_fn will be copied by the eq_fn object of the container
395  // object.
396  template<typename It>
397  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e)
398  : base_type(h, e)
399  { base_type::copy_from_range(first, last); }
400 
401  // Constructor taking __iterators to a range of value_types and
402  // some policy objects. The value_types between first_it and
403  // last_it will be inserted into the container object. r_hash_fn
404  // will be copied by the hash_fn object of the container object,
405  // r_eq_fn will be copied by the eq_fn object of the container
406  // object, and r_comb_probe_fn will be copied by the comb_probe_fn
407  // object of the container object.
408  template<typename It>
409  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
410  const comb_probe_fn& cp)
411  : base_type(h, e, cp)
412  { base_type::copy_from_range(first, last); }
413 
414  // Constructor taking __iterators to a range of value_types and
415  // some policy objects. The value_types between first_it and
416  // last_it will be inserted into the container object. r_hash_fn
417  // will be copied by the hash_fn object of the container object,
418  // r_eq_fn will be copied by the eq_fn object of the container
419  // object, r_comb_probe_fn will be copied by the comb_probe_fn
420  // object of the container object, and r_probe_fn will be copied
421  // by the probe_fn object of the container object.
422  template<typename It>
423  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
424  const comb_probe_fn& cp, const probe_fn& p)
425  : base_type(h, e, cp, p)
426  { base_type::copy_from_range(first, last); }
427 
428  // Constructor taking __iterators to a range of value_types and
429  // some policy objects. The value_types between first_it and
430  // last_it will be inserted into the container object. r_hash_fn
431  // will be copied by the hash_fn object of the container object,
432  // r_eq_fn will be copied by the eq_fn object of the container
433  // object, r_comb_probe_fn will be copied by the comb_probe_fn
434  // object of the container object, r_probe_fn will be copied by
435  // the probe_fn object of the container object, and
436  // r_resize_policy will be copied by the resize_policy object of
437  // the container object.
438  template<typename It>
439  gp_hash_table(It first, It last, const hash_fn& h, const eq_fn& e,
440  const comb_probe_fn& cp, const probe_fn& p,
441  const resize_policy& rp)
442  : base_type(h, e, cp, p, rp)
443  { base_type::copy_from_range(first, last); }
444 
445  gp_hash_table(const gp_hash_table& other)
446  : base_type((const base_type&)other)
447  { }
448 
449  virtual
450  ~gp_hash_table() { }
451 
452  gp_hash_table&
453  operator=(const gp_hash_table& other)
454  {
455  if (this != &other)
456  {
457  gp_hash_table tmp(other);
458  swap(tmp);
459  }
460  return *this;
461  }
462 
463  void
464  swap(gp_hash_table& other)
465  { base_type::swap(other); }
466  };
467 
468 #undef PB_DS_BASE_C_DEC
469 
470 
471 #define PB_DS_BASE_C_DEC \
472  container_base<Key, Mapped, Tag, Policy_Tl, Allocator>
473 
474  /// An abstract basic tree-like (tree, trie) associative container.
475  template<typename Key, typename Mapped, typename Tag,
476  typename Node_Update, typename Policy_Tl, typename Allocator>
477  class basic_tree : public PB_DS_BASE_C_DEC
478  {
479  private:
480  typedef PB_DS_BASE_C_DEC base_type;
481 
482  public:
483  typedef Node_Update node_update;
484 
485  virtual
486  ~basic_tree() { }
487 
488  protected:
489 #define PB_DS_CLASS_NAME basic_tree
491 #undef PB_DS_CLASS_NAME
492  };
493 
494 #undef PB_DS_BASE_C_DEC
495 
496 
497 #define PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC \
498  detail::tree_traits<Key, Mapped,Cmp_Fn,Node_Update,Tag, Allocator>
499 
500 #define PB_DS_BASE_C_DEC \
501  basic_tree<Key,Mapped,Tag,typename PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC::node_update, \
502  typename __gnu_cxx::typelist::create2<Cmp_Fn, PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC >::type, Allocator>
503 
504  /// A concrete basic tree-based associative container.
505  template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
506  typename Tag = rb_tree_tag,
507  template<typename Const_Node_Iterator, typename Node_Iterator, typename Cmp_Fn_, typename Allocator_>
508  class Node_Update = __gnu_pbds::null_tree_node_update,
509  typename Allocator = std::allocator<char> >
510  class tree : public PB_DS_BASE_C_DEC
511  {
512  private:
513  typedef PB_DS_BASE_C_DEC base_type;
514 
515  public:
516  // Comparison functor type.
517  typedef Cmp_Fn cmp_fn;
518 
519  tree() { }
520 
521  // Constructor taking some policy objects. r_cmp_fn will be copied
522  // by the Cmp_Fn object of the container object.
523  tree(const cmp_fn& c)
524  : base_type(c) { }
525 
526  // Constructor taking __iterators to a range of value_types. The
527  // value_types between first_it and last_it will be inserted into
528  // the container object.
529  template<typename It>
530  tree(It first, It last)
531  { base_type::copy_from_range(first, last); }
532 
533  // Constructor taking __iterators to a range of value_types and
534  // some policy objects The value_types between first_it and
535  // last_it will be inserted into the container object. r_cmp_fn
536  // will be copied by the cmp_fn object of the container object.
537  template<typename It>
538  tree(It first, It last, const cmp_fn& c)
539  : base_type(c)
540  { base_type::copy_from_range(first, last); }
541 
542  tree(const tree& other)
543  : base_type((const base_type&)other) { }
544 
545  virtual
546  ~tree() { }
547 
548  tree&
549  operator=(const tree& other)
550  {
551  if (this != &other)
552  {
553  tree tmp(other);
554  swap(tmp);
555  }
556  return *this;
557  }
558 
559  void
560  swap(tree& other)
561  { base_type::swap(other); }
562  };
563 
564 #undef PB_DS_BASE_C_DEC
565 #undef PB_DS_TREE_NODE_AND_IT_TRAITS_C_DEC
566 
567 
568 #define PB_DS_TRIE_NODE_AND_ITS_TRAITS \
569  detail::trie_traits<Key,Mapped,E_Access_Traits,Node_Update,Tag,Allocator>
570 
571 #define PB_DS_BASE_C_DEC \
572  basic_tree<Key,Mapped,Tag, typename PB_DS_TRIE_NODE_AND_ITS_TRAITS::node_update, \
573  typename __gnu_cxx::typelist::create2<E_Access_Traits, PB_DS_TRIE_NODE_AND_ITS_TRAITS >::type, Allocator>
574 
575  /// A concrete basic trie-based associative container.
576  template<typename Key,
577  typename Mapped,
578  typename E_Access_Traits = typename detail::default_trie_e_access_traits<Key>::type,
579  typename Tag = pat_trie_tag,
580  template<typename Const_Node_Iterator,
581  typename Node_Iterator,
582  typename E_Access_Traits_,
583  typename Allocator_>
584  class Node_Update = null_trie_node_update,
585  typename Allocator = std::allocator<char> >
586  class trie : public PB_DS_BASE_C_DEC
587  {
588  private:
589  typedef PB_DS_BASE_C_DEC base_type;
590 
591  public:
592  // Element access traits type.
593  typedef E_Access_Traits e_access_traits;
594 
595  trie() { }
596 
597  // Constructor taking some policy objects. r_e_access_traits will
598  // be copied by the E_Access_Traits object of the container
599  // object.
600  trie(const e_access_traits& t)
601  : base_type(t) { }
602 
603  // Constructor taking __iterators to a range of value_types. The
604  // value_types between first_it and last_it will be inserted into
605  // the container object.
606  template<typename It>
607  trie(It first, It last)
608  { base_type::copy_from_range(first, last); }
609 
610  // Constructor taking __iterators to a range of value_types and
611  // some policy objects. The value_types between first_it and
612  // last_it will be inserted into the container object.
613  template<typename It>
614  trie(It first, It last, const e_access_traits& t)
615  : base_type(t)
616  { base_type::copy_from_range(first, last); }
617 
618  trie(const trie& other)
619  : base_type((const base_type&)other) { }
620 
621  virtual
622  ~trie() { }
623 
624  trie&
625  operator=(const trie& other)
626  {
627  if (this != &other)
628  {
629  trie tmp(other);
630  swap(tmp);
631  }
632  return *this;
633  }
634 
635  void
636  swap(trie& other)
637  { base_type::swap(other); }
638  };
639 
640 #undef PB_DS_BASE_C_DEC
641 #undef PB_DS_TRIE_NODE_AND_ITS_TRAITS
642 
643 
644 #define PB_DS_BASE_C_DEC \
645  container_base<Key, Mapped, list_update_tag, \
646  typename __gnu_cxx::typelist::create2<Eq_Fn, Update_Policy>::type, Allocator>
647 
648  /// A list-update based associative container.
649  template<typename Key,
650  typename Mapped,
651  class Eq_Fn = typename detail::default_eq_fn<Key>::type,
652  class Update_Policy = detail::default_update_policy::type,
653  class Allocator = std::allocator<char> >
654  class list_update : public PB_DS_BASE_C_DEC
655  {
656  private:
657  typedef PB_DS_BASE_C_DEC base_type;
658 
659  public:
660  typedef Eq_Fn eq_fn;
661  typedef Update_Policy update_policy;
662  typedef Allocator allocator;
663 
664  list_update() { }
665 
666  // Constructor taking __iterators to a range of value_types. The
667  // value_types between first_it and last_it will be inserted into
668  // the container object.
669  template<typename It>
670  list_update(It first, It last)
671  { base_type::copy_from_range(first, last); }
672 
673  list_update(const list_update& other)
674  : base_type((const base_type&)other) { }
675 
676  virtual
677  ~list_update() { }
678 
679  list_update&
680  operator=(const list_update& other)
681  {
682  if (this !=& other)
683  {
684  list_update tmp(other);
685  swap(tmp);
686  }
687  return *this;
688  }
689 
690  void
691  swap(list_update& other)
692  { base_type::swap(other); }
693  };
694 
695 #undef PB_DS_BASE_C_DEC
696 
697  // @} group pbds
698 } // namespace __gnu_pbds
699 
700 #endif
A concrete basic trie-based associative container.
A concrete collision-chaining hash-based associative container.
An abstract basic tree-like (tree, trie) associative container.
An abstract basic hash-based associative container.
One of the comparison functors.
Definition: stl_function.h:205
An abstract basic associative container.
A list-update based associative container.
A concrete basic tree-based associative container.
A concrete general-probing hash-based associative container.
The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...
Definition: allocator.h:66