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