libstdc++
cc_ht_map_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2013 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 cc_hash_table_map_/cc_ht_map_.hpp
38  * Contains an implementation class for cc_ht_map_.
39  */
40 
41 #include <utility>
42 #include <iterator>
43 #include <ext/pb_ds/detail/cond_dealtor.hpp>
44 #include <ext/pb_ds/tag_and_trait.hpp>
45 #include <ext/pb_ds/detail/hash_fn/ranged_hash_fn.hpp>
46 #include <ext/pb_ds/detail/types_traits.hpp>
47 #include <ext/pb_ds/exception.hpp>
48 #include <ext/pb_ds/detail/eq_fn/hash_eq_fn.hpp>
49 #ifdef _GLIBCXX_DEBUG
50 #include <ext/pb_ds/detail/debug_map_base.hpp>
51 #endif
52 #ifdef PB_DS_HT_MAP_TRACE_
53 #include <iostream>
54 #endif
55 #include <debug/debug.h>
56 
57 namespace __gnu_pbds
58 {
59  namespace detail
60  {
61 #ifdef PB_DS_DATA_TRUE_INDICATOR
62 #define PB_DS_CC_HASH_NAME cc_ht_map
63 #endif
64 
65 #ifdef PB_DS_DATA_FALSE_INDICATOR
66 #define PB_DS_CC_HASH_NAME cc_ht_set
67 #endif
68 
69 #define PB_DS_CLASS_T_DEC \
70  template<typename Key, typename Mapped, typename Hash_Fn, \
71  typename Eq_Fn, typename _Alloc, bool Store_Hash, \
72  typename Comb_Hash_Fn, typename Resize_Policy>
73 
74 #define PB_DS_CLASS_C_DEC \
75  PB_DS_CC_HASH_NAME<Key, Mapped, Hash_Fn, Eq_Fn, _Alloc, \
76  Store_Hash, Comb_Hash_Fn, Resize_Policy>
77 
78 #define PB_DS_HASH_EQ_FN_C_DEC \
79  hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash>
80 
81 #define PB_DS_RANGED_HASH_FN_C_DEC \
82  ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, Store_Hash>
83 
84 #define PB_DS_CC_HASH_TRAITS_BASE \
85  types_traits<Key, Mapped, _Alloc, Store_Hash>
86 
87 #ifdef _GLIBCXX_DEBUG
88 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
89  debug_map_base<Key, Eq_Fn, \
90  typename _Alloc::template rebind<Key>::other::const_reference>
91 #endif
92 
93 
94  /**
95  * A collision-chaining hash-based container.
96  *
97  *
98  * @ingroup hash-detail
99  *
100  * @tparam Key Key type.
101  *
102  * @tparam Mapped Map type.
103  *
104  * @tparam Hash_Fn Hashing functor.
105  * Default is __gnu_cxx::hash.
106  *
107  * @tparam Eq_Fn Equal functor.
108  * Default std::equal_to<Key>
109  *
110  * @tparam _Alloc Allocator type.
111  *
112  * @tparam Store_Hash If key type stores extra metadata.
113  * Defaults to false.
114  *
115  * @tparam Comb_Hash_Fn Combining hash functor.
116  * If Hash_Fn is not null_type, then this
117  * is the ranged-hash functor; otherwise,
118  * this is the range-hashing functor.
119  * XXX(See Design::Hash-Based Containers::Hash Policies.)
120  * Default direct_mask_range_hashing.
121  *
122  * @tparam Resize_Policy Resizes hash.
123  * Defaults to hash_standard_resize_policy,
124  * using hash_exponential_size_policy and
125  * hash_load_check_resize_trigger.
126  *
127  *
128  * Bases are: detail::hash_eq_fn, Resize_Policy, detail::ranged_hash_fn,
129  * detail::types_traits. (Optional: detail::debug_map_base.)
130  */
131  template<typename Key,
132  typename Mapped,
133  typename Hash_Fn,
134  typename Eq_Fn,
135  typename _Alloc,
136  bool Store_Hash,
137  typename Comb_Hash_Fn,
138  typename Resize_Policy >
139  class PB_DS_CC_HASH_NAME:
140 #ifdef _GLIBCXX_DEBUG
141  protected PB_DS_DEBUG_MAP_BASE_C_DEC,
142 #endif
143  public PB_DS_HASH_EQ_FN_C_DEC,
144  public Resize_Policy,
145  public PB_DS_RANGED_HASH_FN_C_DEC,
146  public PB_DS_CC_HASH_TRAITS_BASE
147  {
148  private:
149  typedef PB_DS_CC_HASH_TRAITS_BASE traits_base;
150  typedef typename traits_base::comp_hash comp_hash;
151  typedef typename traits_base::value_type value_type_;
152  typedef typename traits_base::pointer pointer_;
153  typedef typename traits_base::const_pointer const_pointer_;
154  typedef typename traits_base::reference reference_;
155  typedef typename traits_base::const_reference const_reference_;
156 
157  struct entry : public traits_base::stored_data_type
158  {
159  typename _Alloc::template rebind<entry>::other::pointer m_p_next;
160  };
161 
162  typedef cond_dealtor<entry, _Alloc> cond_dealtor_t;
163 
164  typedef typename _Alloc::template rebind<entry>::other entry_allocator;
165  typedef typename entry_allocator::pointer entry_pointer;
166  typedef typename entry_allocator::const_pointer const_entry_pointer;
167  typedef typename entry_allocator::reference entry_reference;
168  typedef typename entry_allocator::const_reference const_entry_reference;
169 
170  typedef typename _Alloc::template rebind<entry_pointer>::other entry_pointer_allocator;
171  typedef typename entry_pointer_allocator::pointer entry_pointer_array;
172 
173  typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base;
174  typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base;
175  typedef Resize_Policy resize_base;
176 
177 #ifdef _GLIBCXX_DEBUG
178  typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
179 #endif
180 
181 #define PB_DS_GEN_POS std::pair<entry_pointer, typename _Alloc::size_type>
182 
183 #include <ext/pb_ds/detail/unordered_iterator/point_const_iterator.hpp>
184 #include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
185 #include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
186 #include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>
187 
188 #undef PB_DS_GEN_POS
189 
190  public:
191  typedef _Alloc allocator_type;
192  typedef typename _Alloc::size_type size_type;
193  typedef typename _Alloc::difference_type difference_type;
194  typedef Hash_Fn hash_fn;
195  typedef Eq_Fn eq_fn;
196  typedef Comb_Hash_Fn comb_hash_fn;
197  typedef Resize_Policy resize_policy;
198 
199  /// Value stores hash, true or false.
200  enum
201  {
202  store_hash = Store_Hash
203  };
204 
205  typedef typename traits_base::key_type key_type;
206  typedef typename traits_base::key_pointer key_pointer;
207  typedef typename traits_base::key_const_pointer key_const_pointer;
208  typedef typename traits_base::key_reference key_reference;
209  typedef typename traits_base::key_const_reference key_const_reference;
210  typedef typename traits_base::mapped_type mapped_type;
211  typedef typename traits_base::mapped_pointer mapped_pointer;
212  typedef typename traits_base::mapped_const_pointer mapped_const_pointer;
213  typedef typename traits_base::mapped_reference mapped_reference;
214  typedef typename traits_base::mapped_const_reference mapped_const_reference;
215  typedef typename traits_base::value_type value_type;
216  typedef typename traits_base::pointer pointer;
217  typedef typename traits_base::const_pointer const_pointer;
218  typedef typename traits_base::reference reference;
219  typedef typename traits_base::const_reference const_reference;
220 
221 #ifdef PB_DS_DATA_TRUE_INDICATOR
222  typedef point_iterator_ point_iterator;
223 #endif
224 
225 #ifdef PB_DS_DATA_FALSE_INDICATOR
226  typedef point_const_iterator_ point_iterator;
227 #endif
228 
229  typedef point_const_iterator_ point_const_iterator;
230 
231 #ifdef PB_DS_DATA_TRUE_INDICATOR
232  typedef iterator_ iterator;
233 #endif
234 
235 #ifdef PB_DS_DATA_FALSE_INDICATOR
236  typedef const_iterator_ iterator;
237 #endif
238 
239  typedef const_iterator_ const_iterator;
240 
241  PB_DS_CC_HASH_NAME();
242 
243  PB_DS_CC_HASH_NAME(const Hash_Fn&);
244 
245  PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&);
246 
247  PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&);
248 
249  PB_DS_CC_HASH_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&,
250  const Resize_Policy&);
251 
252  PB_DS_CC_HASH_NAME(const PB_DS_CLASS_C_DEC&);
253 
254  virtual
255  ~PB_DS_CC_HASH_NAME();
256 
257  void
258  swap(PB_DS_CLASS_C_DEC&);
259 
260  template<typename It>
261  void
262  copy_from_range(It, It);
263 
264  void
265  initialize();
266 
267  inline size_type
268  size() const;
269 
270  inline size_type
271  max_size() const;
272 
273  /// True if size() == 0.
274  inline bool
275  empty() const;
276 
277  /// Return current hash_fn.
278  Hash_Fn&
279  get_hash_fn();
280 
281  /// Return current const hash_fn.
282  const Hash_Fn&
283  get_hash_fn() const;
284 
285  /// Return current eq_fn.
286  Eq_Fn&
287  get_eq_fn();
288 
289  /// Return current const eq_fn.
290  const Eq_Fn&
291  get_eq_fn() const;
292 
293  /// Return current comb_hash_fn.
294  Comb_Hash_Fn&
295  get_comb_hash_fn();
296 
297  /// Return current const comb_hash_fn.
298  const Comb_Hash_Fn&
299  get_comb_hash_fn() const;
300 
301  /// Return current resize_policy.
302  Resize_Policy&
303  get_resize_policy();
304 
305  /// Return current const resize_policy.
306  const Resize_Policy&
307  get_resize_policy() const;
308 
309  inline std::pair<point_iterator, bool>
310  insert(const_reference r_val)
311  { return insert_imp(r_val, traits_base::m_store_extra_indicator); }
312 
313  inline mapped_reference
314  operator[](key_const_reference r_key)
315  {
316 #ifdef PB_DS_DATA_TRUE_INDICATOR
317  return (subscript_imp(r_key, traits_base::m_store_extra_indicator));
318 #else
319  insert(r_key);
320  return traits_base::s_null_type;
321 #endif
322  }
323 
324  inline point_iterator
325  find(key_const_reference);
326 
327  inline point_const_iterator
328  find(key_const_reference) const;
329 
330  inline point_iterator
331  find_end();
332 
333  inline point_const_iterator
334  find_end() const;
335 
336  inline bool
337  erase(key_const_reference);
338 
339  template<typename Pred>
340  inline size_type
341  erase_if(Pred);
342 
343  void
344  clear();
345 
346  inline iterator
347  begin();
348 
349  inline const_iterator
350  begin() const;
351 
352  inline iterator
353  end();
354 
355  inline const_iterator
356  end() const;
357 
358 #ifdef _GLIBCXX_DEBUG
359  void
360  assert_valid(const char*, int) const;
361 #endif
362 
363 #ifdef PB_DS_HT_MAP_TRACE_
364  void
365  trace() const;
366 #endif
367 
368  private:
369  void
370  deallocate_all();
371 
372  inline bool
373  do_resize_if_needed();
374 
375  inline void
376  do_resize_if_needed_no_throw();
377 
378  void
379  resize_imp(size_type);
380 
381  void
382  do_resize(size_type);
383 
384  void
385  resize_imp_no_exceptions(size_type, entry_pointer_array, size_type);
386 
387  inline entry_pointer
388  resize_imp_no_exceptions_reassign_pointer(entry_pointer,
389  entry_pointer_array,
390  false_type);
391 
392  inline entry_pointer
393  resize_imp_no_exceptions_reassign_pointer(entry_pointer,
394  entry_pointer_array,
395  true_type);
396 
397  void
398  deallocate_links_in_list(entry_pointer);
399 
400  inline entry_pointer
401  get_entry(const_reference, false_type);
402 
403  inline entry_pointer
404  get_entry(const_reference, true_type);
405 
406  inline void
407  rels_entry(entry_pointer);
408 
409 #ifdef PB_DS_DATA_TRUE_INDICATOR
410  inline mapped_reference
411  subscript_imp(key_const_reference r_key, false_type)
412  {
413  _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
414  const size_type pos = ranged_hash_fn_base::operator()(r_key);
415  entry_pointer p_e = m_entries[pos];
416  resize_base::notify_insert_search_start();
417 
418  while (p_e != 0
419  && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key))
420  {
421  resize_base::notify_insert_search_collision();
422  p_e = p_e->m_p_next;
423  }
424 
425  resize_base::notify_insert_search_end();
426  if (p_e != 0)
427  {
428  PB_DS_CHECK_KEY_EXISTS(r_key)
429  return (p_e->m_value.second);
430  }
431 
432  PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
433  return insert_new_imp(value_type(r_key, mapped_type()), pos)->second;
434  }
435 
436  inline mapped_reference
437  subscript_imp(key_const_reference r_key, true_type)
438  {
439  _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
440  comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
441  entry_pointer p_e = m_entries[pos_hash_pair.first];
442  resize_base::notify_insert_search_start();
443  while (p_e != 0 &&
444  !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash,
445  r_key, pos_hash_pair.second))
446  {
447  resize_base::notify_insert_search_collision();
448  p_e = p_e->m_p_next;
449  }
450 
451  resize_base::notify_insert_search_end();
452  if (p_e != 0)
453  {
454  PB_DS_CHECK_KEY_EXISTS(r_key)
455  return p_e->m_value.second;
456  }
457 
458  PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
459  return insert_new_imp(value_type(r_key, mapped_type()),
460  pos_hash_pair)->second;
461  }
462 #endif
463 
464  inline std::pair<point_iterator, bool>
465  insert_imp(const_reference, false_type);
466 
467  inline std::pair<point_iterator, bool>
468  insert_imp(const_reference, true_type);
469 
470  inline pointer
471  insert_new_imp(const_reference r_val, size_type pos)
472  {
473  if (do_resize_if_needed())
474  pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
475 
476  // Following lines might throw an exception.
477  entry_pointer p_e = get_entry(r_val,
478  traits_base::m_no_throw_copies_indicator);
479 
480  // At this point no exceptions can be thrown.
481  p_e->m_p_next = m_entries[pos];
482  m_entries[pos] = p_e;
483  resize_base::notify_inserted(++m_num_used_e);
484 
485  _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
486  _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
487  return &p_e->m_value;
488  }
489 
490  inline pointer
491  insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair)
492  {
493  // Following lines might throw an exception.
494  if (do_resize_if_needed())
495  r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
496 
497  entry_pointer p_e = get_entry(r_val,
498  traits_base::m_no_throw_copies_indicator);
499 
500  // At this point no exceptions can be thrown.
501  p_e->m_hash = r_pos_hash_pair.second;
502  p_e->m_p_next = m_entries[r_pos_hash_pair.first];
503  m_entries[r_pos_hash_pair.first] = p_e;
504  resize_base::notify_inserted(++m_num_used_e);
505  _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
506  _GLIBCXX_DEBUG_ONLY(assert_valid(__FILE__, __LINE__);)
507  return &p_e->m_value;
508  }
509 
510  inline pointer
511  find_key_pointer(key_const_reference r_key, false_type)
512  {
513  entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)];
514  resize_base::notify_find_search_start();
515  while (p_e != 0 &&
516  !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key))
517  {
518  resize_base::notify_find_search_collision();
519  p_e = p_e->m_p_next;
520  }
521 
522  resize_base::notify_find_search_end();
523 
524 #ifdef _GLIBCXX_DEBUG
525  if (p_e == 0)
526  PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
527  else
528  PB_DS_CHECK_KEY_EXISTS(r_key)
529 #endif
530  return &p_e->m_value;
531  }
532 
533  inline pointer
534  find_key_pointer(key_const_reference r_key, true_type)
535  {
536  comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
537  entry_pointer p_e = m_entries[pos_hash_pair.first];
538  resize_base::notify_find_search_start();
539  while (p_e != 0 &&
540  !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value),
541  p_e->m_hash,
542  r_key, pos_hash_pair.second))
543  {
544  resize_base::notify_find_search_collision();
545  p_e = p_e->m_p_next;
546  }
547 
548  resize_base::notify_find_search_end();
549 
550 #ifdef _GLIBCXX_DEBUG
551  if (p_e == 0)
552  PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
553  else
554  PB_DS_CHECK_KEY_EXISTS(r_key)
555 #endif
556  return &p_e->m_value;
557  }
558 
559  inline bool
560  erase_in_pos_imp(key_const_reference, size_type);
561 
562  inline bool
563  erase_in_pos_imp(key_const_reference, const comp_hash&);
564 
565  inline void
566  erase_entry_pointer(entry_pointer&);
567 
568 #ifdef PB_DS_DATA_TRUE_INDICATOR
569  void
570  inc_it_state(pointer& r_p_value,
571  std::pair<entry_pointer, size_type>& r_pos) const
572  {
573  inc_it_state((mapped_const_pointer& )r_p_value, r_pos);
574  }
575 #endif
576 
577  void
578  inc_it_state(const_pointer& r_p_value,
579  std::pair<entry_pointer, size_type>& r_pos) const
580  {
581  _GLIBCXX_DEBUG_ASSERT(r_p_value != 0);
582  r_pos.first = r_pos.first->m_p_next;
583  if (r_pos.first != 0)
584  {
585  r_p_value = &r_pos.first->m_value;
586  return;
587  }
588 
589  for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second)
590  if (m_entries[r_pos.second] != 0)
591  {
592  r_pos.first = m_entries[r_pos.second];
593  r_p_value = &r_pos.first->m_value;
594  return;
595  }
596  r_p_value = 0;
597  }
598 
599  void
600  get_start_it_state(pointer& r_p_value,
601  std::pair<entry_pointer, size_type>& r_pos) const
602  {
603  for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second)
604  if (m_entries[r_pos.second] != 0)
605  {
606  r_pos.first = m_entries[r_pos.second];
607  r_p_value = &r_pos.first->m_value;
608  return;
609  }
610  r_p_value = 0;
611  }
612 
613 #ifdef _GLIBCXX_DEBUG
614  void
615  assert_entry_pointer_array_valid(const entry_pointer_array,
616  const char*, int) const;
617 
618  void
619  assert_entry_pointer_valid(const entry_pointer, true_type,
620  const char*, int) const;
621 
622  void
623  assert_entry_pointer_valid(const entry_pointer, false_type,
624  const char*, int) const;
625 #endif
626 
627 #ifdef PB_DS_HT_MAP_TRACE_
628  void
629  trace_list(const_entry_pointer) const;
630 #endif
631 
632  private:
633 #ifdef PB_DS_DATA_TRUE_INDICATOR
634  friend class iterator_;
635 #endif
636 
637  friend class const_iterator_;
638 
639  static entry_allocator s_entry_allocator;
640  static entry_pointer_allocator s_entry_pointer_allocator;
641  static iterator s_end_it;
642  static const_iterator s_const_end_it;
643  static point_iterator s_find_end_it;
644  static point_const_iterator s_const_find_end_it;
645 
646  size_type m_num_e;
647  size_type m_num_used_e;
648  entry_pointer_array m_entries;
649 
650  enum
651  {
652  store_hash_ok = !Store_Hash
653  || !is_same<Hash_Fn, __gnu_pbds::null_type>::value
654  };
655 
656  PB_DS_STATIC_ASSERT(sth, store_hash_ok);
657  };
658 
659 #include <ext/pb_ds/detail/cc_hash_table_map_/constructor_destructor_fn_imps.hpp>
660 #include <ext/pb_ds/detail/cc_hash_table_map_/entry_list_fn_imps.hpp>
661 #include <ext/pb_ds/detail/cc_hash_table_map_/find_fn_imps.hpp>
662 #include <ext/pb_ds/detail/cc_hash_table_map_/resize_fn_imps.hpp>
663 #include <ext/pb_ds/detail/cc_hash_table_map_/debug_fn_imps.hpp>
664 #include <ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp>
665 #include <ext/pb_ds/detail/cc_hash_table_map_/policy_access_fn_imps.hpp>
666 #include <ext/pb_ds/detail/cc_hash_table_map_/erase_fn_imps.hpp>
667 #include <ext/pb_ds/detail/cc_hash_table_map_/iterators_fn_imps.hpp>
668 #include <ext/pb_ds/detail/cc_hash_table_map_/insert_fn_imps.hpp>
669 #include <ext/pb_ds/detail/cc_hash_table_map_/trace_fn_imps.hpp>
670 
671 #undef PB_DS_CLASS_T_DEC
672 #undef PB_DS_CLASS_C_DEC
673 #undef PB_DS_HASH_EQ_FN_C_DEC
674 #undef PB_DS_RANGED_HASH_FN_C_DEC
675 #undef PB_DS_CC_HASH_TRAITS_BASE
676 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
677 #undef PB_DS_CC_HASH_NAME
678  } // namespace detail
679 } // namespace __gnu_pbds
std::end
auto end(_Container &__cont) -> decltype(__cont.end())
Return an iterator pointing to one past the last element of the container.
Definition: range_access.h:68
iterator_::iterator_
iterator_()
Default constructor.
Definition: iterator.hpp:70
std::pair::first
_T1 first
second_type is the second bound type
Definition: stl_pair.h:101
__gnu_pbds::detail::types_traits
Traits for abstract types.
Definition: types_traits.hpp:263
std::begin
auto begin(_Container &__cont) -> decltype(__cont.begin())
Return an iterator pointing to the first element of the container.
Definition: range_access.h:48
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:51
std::swap
void swap(_Tp &, _Tp &) noexcept(__and_< is_nothrow_move_constructible< _Tp >, is_nothrow_move_assignable< _Tp >>::value)
Swaps two values.
Definition: move.h:166
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:96
const_iterator_::const_iterator_
const_iterator_()
Default constructor.
Definition: unordered_iterator/const_iterator.hpp:69
std::pair::second
_T2 second
first is a copy of the first object
Definition: stl_pair.h:102
__gnu_pbds::detail::cond_dealtor
Conditional deallocate constructor argument.
Definition: cond_dealtor.hpp:50