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