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