libstdc++
gp_ht_map_.hpp
Go to the documentation of this file.
1 // -*- C++ -*-
2 
3 // Copyright (C) 2005-2020 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 rebind_traits<_Alloc, Key>::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 rebind_traits<_Alloc, entry> entry_traits;
173  typedef typename entry_traits::allocator_type entry_allocator;
174  typedef typename entry_traits::pointer entry_pointer;
175  typedef typename entry_traits::const_pointer const_entry_pointer;
176  typedef typename entry_traits::reference entry_reference;
177  typedef typename entry_traits::const_reference const_entry_reference;
178  typedef typename entry_traits::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  _GLIBCXX_NODISCARD 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
std::true_type
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
Definition: type_traits:75
std::false_type
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Definition: type_traits:78
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition: valarray:1234
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition: valarray:1214
__gnu_pbds
GNU extensions for policy-based data structures for public use.
Definition: assoc_container.hpp:52
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:213
__gnu_pbds::detail::stored_data
Primary template for representation of stored data. Two types of data can be stored: value and hash.
Definition: types_traits.hpp:97
__gnu_pbds::detail::types_traits
Traits for abstract types.
Definition: types_traits.hpp:156
__gnu_pbds::detail::gp_ht_map::get_hash_fn
const Hash_Fn & get_hash_fn() const
Return current const hash_fn.
__gnu_pbds::detail::gp_ht_map::empty
bool empty() const
True if size() == 0.
__gnu_pbds::detail::gp_ht_map::get_resize_policy
Resize_Policy & get_resize_policy()
Return current resize_policy.
__gnu_pbds::detail::gp_ht_map::get_comb_probe_fn
const Comb_Probe_Fn & get_comb_probe_fn() const
Return current const comb_probe_fn.
__gnu_pbds::detail::gp_ht_map::get_eq_fn
Eq_Fn & get_eq_fn()
Return current eq_fn.
__gnu_pbds::detail::gp_ht_map::get_hash_fn
Hash_Fn & get_hash_fn()
Return current hash_fn.
__gnu_pbds::detail::gp_ht_map::get_resize_policy
const Resize_Policy & get_resize_policy() const
Return current const resize_policy.
__gnu_pbds::detail::gp_ht_map::get_probe_fn
Probe_Fn & get_probe_fn()
Return current probe_fn.
__gnu_pbds::detail::gp_ht_map::get_comb_probe_fn
Comb_Probe_Fn & get_comb_probe_fn()
Return current comb_probe_fn.
__gnu_pbds::detail::gp_ht_map::get_probe_fn
const Probe_Fn & get_probe_fn() const
Return current const probe_fn.
__gnu_pbds::detail::gp_ht_map::get_eq_fn
const Eq_Fn & get_eq_fn() const
Return current const eq_fn.