libstdc++
cc_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 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
58namespace __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
__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_comb_hash_fn
Comb_Hash_Fn & get_comb_hash_fn()
Return current comb_hash_fn.
__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_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.
__gnu_pbds::detail::cc_ht_map::get_eq_fn
Eq_Fn & get_eq_fn()
Return current eq_fn.
__gnu_pbds::detail::cc_ht_map::empty
bool empty() const
True if size() == 0.
__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_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.