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