libstdc++
gp_ht_map_.hpp
Go to the documentation of this file.
1// -*- C++ -*-
2
3// Copyright (C) 2005-2021 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
55namespace __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
__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::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::gp_ht_map::empty
bool empty() const
True if size() == 0.
__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_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_hash_fn
const Hash_Fn & get_hash_fn() const
Return current const hash_fn.
__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_eq_fn
Eq_Fn & get_eq_fn()
Return current eq_fn.
__gnu_pbds::detail::gp_ht_map::get_eq_fn
const Eq_Fn & get_eq_fn() const
Return current const eq_fn.
__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_resize_policy
const Resize_Policy & get_resize_policy() const
Return current const resize_policy.
__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_probe_fn
const Probe_Fn & get_probe_fn() const
Return current const probe_fn.