53 #ifdef PB_DS_HT_MAP_TRACE_
62 #ifdef PB_DS_DATA_TRUE_INDICATOR
63 #define PB_DS_CC_HASH_NAME cc_ht_map
66 #ifdef PB_DS_DATA_FALSE_INDICATOR
67 #define PB_DS_CC_HASH_NAME cc_ht_set
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>
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>
79 #define PB_DS_HASH_EQ_FN_C_DEC \
80 hash_eq_fn<Key, Eq_Fn, _Alloc, Store_Hash>
82 #define PB_DS_RANGED_HASH_FN_C_DEC \
83 ranged_hash_fn<Key, Hash_Fn, _Alloc, Comb_Hash_Fn, Store_Hash>
85 #define PB_DS_CC_HASH_TRAITS_BASE \
86 types_traits<Key, Mapped, _Alloc, Store_Hash>
89 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
90 debug_map_base<Key, Eq_Fn, \
91 typename rebind_traits<_Alloc, Key>::const_reference>
132 template<
typename Key,
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,
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
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_;
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;
173 typedef typename entry_pointer_traits::allocator_type entry_pointer_allocator;
174 typedef typename entry_pointer_traits::pointer entry_pointer_array;
178 typedef Resize_Policy resize_base;
180 #ifdef _GLIBCXX_DEBUG
181 typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
184 #define PB_DS_GEN_POS std::pair<entry_pointer, typename _Alloc::size_type>
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;
199 typedef Comb_Hash_Fn comb_hash_fn;
200 typedef Resize_Policy resize_policy;
205 store_hash = Store_Hash
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;
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;
224 #ifdef PB_DS_DATA_TRUE_INDICATOR
225 typedef point_iterator_ point_iterator;
228 #ifdef PB_DS_DATA_FALSE_INDICATOR
229 typedef point_const_iterator_ point_iterator;
232 typedef point_const_iterator_ point_const_iterator;
234 #ifdef PB_DS_DATA_TRUE_INDICATOR
235 typedef iterator_ iterator;
238 #ifdef PB_DS_DATA_FALSE_INDICATOR
239 typedef const_iterator_ iterator;
242 typedef const_iterator_ const_iterator;
244 PB_DS_CC_HASH_NAME();
246 PB_DS_CC_HASH_NAME(
const Hash_Fn&);
248 PB_DS_CC_HASH_NAME(
const Hash_Fn&,
const Eq_Fn&);
250 PB_DS_CC_HASH_NAME(
const Hash_Fn&,
const Eq_Fn&,
const Comb_Hash_Fn&);
252 PB_DS_CC_HASH_NAME(
const Hash_Fn&,
const Eq_Fn&,
const Comb_Hash_Fn&,
253 const Resize_Policy&);
255 PB_DS_CC_HASH_NAME(
const PB_DS_CLASS_C_DEC&);
258 ~PB_DS_CC_HASH_NAME();
261 swap(PB_DS_CLASS_C_DEC&);
263 template<
typename It>
265 copy_from_range(It, It);
277 _GLIBCXX_NODISCARD
inline bool
313 insert(const_reference r_val)
314 {
return insert_imp(r_val, traits_base::m_store_extra_indicator); }
316 inline mapped_reference
317 operator[](key_const_reference r_key)
319 #ifdef PB_DS_DATA_TRUE_INDICATOR
320 return (subscript_imp(r_key, traits_base::m_store_extra_indicator));
323 return traits_base::s_null_type;
327 inline point_iterator
328 find(key_const_reference);
330 inline point_const_iterator
331 find(key_const_reference)
const;
333 inline point_iterator
336 inline point_const_iterator
340 erase(key_const_reference);
342 template<
typename Pred>
352 inline const_iterator
358 inline const_iterator
361 #ifdef _GLIBCXX_DEBUG
363 assert_valid(
const char*,
int)
const;
366 #ifdef PB_DS_HT_MAP_TRACE_
376 do_resize_if_needed();
379 do_resize_if_needed_no_throw();
382 resize_imp(size_type);
385 do_resize(size_type);
388 resize_imp_no_exceptions(size_type, entry_pointer_array, size_type);
391 resize_imp_no_exceptions_reassign_pointer(entry_pointer,
396 resize_imp_no_exceptions_reassign_pointer(entry_pointer,
401 deallocate_links_in_list(entry_pointer);
410 rels_entry(entry_pointer);
412 #ifdef PB_DS_DATA_TRUE_INDICATOR
413 inline mapped_reference
414 subscript_imp(key_const_reference r_key,
false_type)
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();
422 && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key))
424 resize_base::notify_insert_search_collision();
428 resize_base::notify_insert_search_end();
431 PB_DS_CHECK_KEY_EXISTS(r_key)
432 return (p_e->m_value.second);
435 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
436 return insert_new_imp(value_type(r_key, mapped_type()), pos)->second;
439 inline mapped_reference
440 subscript_imp(key_const_reference r_key,
true_type)
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();
447 !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash,
448 r_key, pos_hash_pair.second))
450 resize_base::notify_insert_search_collision();
454 resize_base::notify_insert_search_end();
457 PB_DS_CHECK_KEY_EXISTS(r_key)
458 return p_e->m_value.second;
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;
474 insert_new_imp(const_reference r_val, size_type pos)
476 if (do_resize_if_needed())
477 pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
480 entry_pointer p_e = get_entry(r_val,
481 traits_base::m_no_throw_copies_indicator);
484 p_e->m_p_next = m_entries[pos];
485 m_entries[pos] = p_e;
486 resize_base::notify_inserted(++m_num_used_e);
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;
494 insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair)
497 if (do_resize_if_needed())
498 r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val));
500 entry_pointer p_e = get_entry(r_val,
501 traits_base::m_no_throw_copies_indicator);
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;
514 find_key_pointer(key_const_reference r_key,
false_type)
516 entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)];
517 resize_base::notify_find_search_start();
519 !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key))
521 resize_base::notify_find_search_collision();
525 resize_base::notify_find_search_end();
527 #ifdef _GLIBCXX_DEBUG
529 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
531 PB_DS_CHECK_KEY_EXISTS(r_key)
533 return &p_e->m_value;
537 find_key_pointer(key_const_reference r_key,
true_type)
539 comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key);
540 entry_pointer p_e = m_entries[pos_hash_pair.first];
541 resize_base::notify_find_search_start();
543 !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value),
545 r_key, pos_hash_pair.second))
547 resize_base::notify_find_search_collision();
551 resize_base::notify_find_search_end();
553 #ifdef _GLIBCXX_DEBUG
555 PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key)
557 PB_DS_CHECK_KEY_EXISTS(r_key)
559 return &p_e->m_value;
563 erase_in_pos_imp(key_const_reference, size_type);
566 erase_in_pos_imp(key_const_reference,
const comp_hash&);
569 erase_entry_pointer(entry_pointer&);
571 #ifdef PB_DS_DATA_TRUE_INDICATOR
573 inc_it_state(pointer& r_p_value,
576 inc_it_state((mapped_const_pointer& )r_p_value, r_pos);
581 inc_it_state(const_pointer& r_p_value,
584 _GLIBCXX_DEBUG_ASSERT(r_p_value != 0);
586 if (r_pos.
first != 0)
588 r_p_value = &r_pos.
first->m_value;
593 if (m_entries[r_pos.
second] != 0)
596 r_p_value = &r_pos.
first->m_value;
603 get_start_it_state(pointer& r_p_value,
607 if (m_entries[r_pos.
second] != 0)
610 r_p_value = &r_pos.
first->m_value;
616 #ifdef _GLIBCXX_DEBUG
618 assert_entry_pointer_array_valid(
const entry_pointer_array,
619 const char*,
int)
const;
622 assert_entry_pointer_valid(
const entry_pointer,
true_type,
623 const char*,
int)
const;
626 assert_entry_pointer_valid(
const entry_pointer,
false_type,
627 const char*,
int)
const;
630 #ifdef PB_DS_HT_MAP_TRACE_
632 trace_list(const_entry_pointer)
const;
636 #ifdef PB_DS_DATA_TRUE_INDICATOR
637 friend class iterator_;
640 friend class const_iterator_;
642 static entry_allocator s_entry_allocator;
643 static entry_pointer_allocator s_entry_pointer_allocator;
644 static iterator s_end_it;
645 static const_iterator s_const_end_it;
646 static point_iterator s_find_end_it;
647 static point_const_iterator s_const_find_end_it;
650 size_type m_num_used_e;
651 entry_pointer_array m_entries;
655 store_hash_ok = !Store_Hash
656 || !is_same<Hash_Fn, __gnu_pbds::null_type>::value
659 PB_DS_STATIC_ASSERT(sth, store_hash_ok);
674 #undef PB_DS_CLASS_T_DEC
675 #undef PB_DS_CLASS_C_DEC
676 #undef PB_DS_HASH_EQ_FN_C_DEC
677 #undef PB_DS_RANGED_HASH_FN_C_DEC
678 #undef PB_DS_CC_HASH_TRAITS_BASE
679 #undef PB_DS_DEBUG_MAP_BASE_C_DEC
680 #undef PB_DS_CC_HASH_NAME
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
_T1 first
The first member.
_T2 second
The second member.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
GNU extensions for policy-based data structures for public use.
Struct holding two objects of arbitrary type.
Conditional deallocate constructor argument.
Primary template for representation of stored data. Two types of data can be stored: value and hash.
Consistent API for accessing allocator-related types.
Traits for abstract types.
Eq_Fn & get_eq_fn()
Return current eq_fn.
Comb_Hash_Fn & get_comb_hash_fn()
Return current comb_hash_fn.
bool empty() const
True if size() == 0.
const Eq_Fn & get_eq_fn() const
Return current const eq_fn.
const Comb_Hash_Fn & get_comb_hash_fn() const
Return current const comb_hash_fn.
const Resize_Policy & get_resize_policy() const
Return current const resize_policy.
const Hash_Fn & get_hash_fn() const
Return current const hash_fn.
Hash_Fn & get_hash_fn()
Return current hash_fn.
Resize_Policy & get_resize_policy()
Return current resize_policy.