31 #define _HASHTABLE_H 1 33 #pragma GCC system_header 36 #if __cplusplus > 201402L 40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 template<
typename _Tp,
typename _Hash>
47 __is_fast_hash<_Hash>,
49 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
164 template<
typename _Key,
typename _Value,
typename _Alloc,
165 typename _ExtractKey,
typename _Equal,
166 typename _Hash,
typename _RangeHash,
typename _Unused,
167 typename _RehashPolicy,
typename _Traits>
170 _Hash, _RangeHash, _Unused, _Traits>,
172 _Hash, _RangeHash, _Unused,
173 _RehashPolicy, _Traits>,
175 _Hash, _RangeHash, _Unused,
176 _RehashPolicy, _Traits>,
178 _Hash, _RangeHash, _Unused,
179 _RehashPolicy, _Traits>,
181 _Hash, _RangeHash, _Unused,
182 _RehashPolicy, _Traits>,
184 __alloc_rebind<_Alloc,
185 __detail::_Hash_node<_Value,
186 _Traits::__hash_cached::value>>>
188 static_assert(
is_same<
typename remove_cv<_Value>::type, _Value>::value,
189 "unordered container must have a non-const, non-volatile value_type");
190 #if __cplusplus > 201703L || defined __STRICT_ANSI__ 192 "unordered container must have the same value_type as its allocator");
195 using __traits_type = _Traits;
196 using __hash_cached =
typename __traits_type::__hash_cached;
197 using __constant_iterators =
typename __traits_type::__constant_iterators;
199 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
203 using __node_value_type =
204 __detail::_Hash_node_value<_Value, __hash_cached::value>;
205 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
206 using __value_alloc_traits =
207 typename __hashtable_alloc::__value_alloc_traits;
208 using __node_alloc_traits =
217 _RehashPolicy, _Traits>;
220 typedef _Key key_type;
221 typedef _Value value_type;
222 typedef _Alloc allocator_type;
223 typedef _Equal key_equal;
227 typedef typename __value_alloc_traits::pointer pointer;
228 typedef typename __value_alloc_traits::const_pointer const_pointer;
229 typedef value_type& reference;
230 typedef const value_type& const_reference;
232 using iterator =
typename __insert_base::iterator;
234 using const_iterator =
typename __insert_base::const_iterator;
237 _ExtractKey, _Hash, _RangeHash, _Unused,
238 __constant_iterators::value,
239 __hash_cached::value>;
243 _ExtractKey, _Hash, _RangeHash, _Unused,
244 __constant_iterators::value, __hash_cached::value>;
247 using __rehash_type = _RehashPolicy;
248 using __rehash_state =
typename __rehash_type::_State;
250 using __unique_keys =
typename __traits_type::__unique_keys;
253 _Hashtable_base<_Key, _Value, _ExtractKey,
254 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
257 using __hash_code =
typename __hashtable_base::__hash_code;
258 using __ireturn_type =
typename __insert_base::__ireturn_type;
261 _Equal, _Hash, _RangeHash, _Unused,
262 _RehashPolicy, _Traits>;
266 _Hash, _RangeHash, _Unused,
267 _RehashPolicy, _Traits>;
270 _Equal, _Hash, _RangeHash, _Unused,
271 _RehashPolicy, _Traits>;
273 using __reuse_or_alloc_node_gen_t =
274 __detail::_ReuseOrAllocNode<__node_alloc_type>;
275 using __alloc_node_gen_t =
276 __detail::_AllocNode<__node_alloc_type>;
283 : _M_h(__h), _M_node(__n) { }
286 template<
typename... _Args>
289 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
293 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
295 _Scoped_node(
const _Scoped_node&) =
delete;
296 _Scoped_node&
operator=(
const _Scoped_node&) =
delete;
302 template<
typename _Ht>
305 const value_type&, value_type&&>::type
306 __fwd_value_for(value_type& __val) noexcept
313 struct __hash_code_base_access : __hash_code_base
314 {
using __hash_code_base::_M_bucket_index; };
318 static_assert(noexcept(declval<const __hash_code_base_access&>()
319 ._M_bucket_index(declval<const __node_value_type&>(),
321 "Cache the hash code or qualify your functors involved" 322 " in hash code and bucket index computation with noexcept");
326 "Functor used to map hash code to bucket index" 327 " must be nothrow default constructible");
328 static_assert(noexcept(
329 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
330 "Functor used to map hash code to bucket index must be" 335 "_ExtractKey must be nothrow default constructible");
336 static_assert(noexcept(
337 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
338 "_ExtractKey functor must be noexcept invocable");
340 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
341 typename _ExtractKeya,
typename _Equala,
342 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
343 typename _RehashPolicya,
typename _Traitsa,
347 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
348 typename _ExtractKeya,
typename _Equala,
349 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
350 typename _RehashPolicya,
typename _Traitsa>
353 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
354 typename _ExtractKeya,
typename _Equala,
355 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
356 typename _RehashPolicya,
typename _Traitsa,
357 bool _Constant_iteratorsa>
360 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
361 typename _ExtractKeya,
typename _Equala,
362 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
363 typename _RehashPolicya,
typename _Traitsa,
368 using size_type =
typename __hashtable_base::size_type;
369 using difference_type =
typename __hashtable_base::difference_type;
371 #if __cplusplus > 201402L 377 __buckets_ptr _M_buckets = &_M_single_bucket;
378 size_type _M_bucket_count = 1;
379 __node_base _M_before_begin;
380 size_type _M_element_count = 0;
381 _RehashPolicy _M_rehash_policy;
389 __node_base_ptr _M_single_bucket =
nullptr;
395 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
399 _M_update_bbegin(__node_ptr __n)
401 _M_before_begin._M_nxt = __n;
406 _M_uses_single_bucket(__buckets_ptr __bkts)
const 407 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
410 _M_uses_single_bucket()
const 411 {
return _M_uses_single_bucket(_M_buckets); }
414 _M_base_alloc() {
return *
this; }
417 _M_allocate_buckets(size_type __bkt_count)
419 if (__builtin_expect(__bkt_count == 1,
false))
421 _M_single_bucket =
nullptr;
422 return &_M_single_bucket;
425 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
429 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
431 if (_M_uses_single_bucket(__bkts))
434 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
438 _M_deallocate_buckets()
439 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
444 _M_bucket_begin(size_type __bkt)
const;
448 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
452 template<
typename _Ht>
454 _M_assign_elements(_Ht&&);
456 template<
typename _Ht,
typename _NodeGenerator>
458 _M_assign(_Ht&&,
const _NodeGenerator&);
469 _Hashtable(
const _Hash& __h,
const _Equal& __eq,
470 const allocator_type& __a)
475 template<
bool _No_realloc = true>
476 static constexpr
bool 479 #if __cplusplus <= 201402L 480 return __and_<__bool_constant<_No_realloc>,
484 if constexpr (_No_realloc)
493 noexcept(_S_nothrow_move());
498 template<
typename _InputIterator>
499 _Hashtable(_InputIterator __first, _InputIterator __last,
500 size_type __bkt_count_hint,
501 const _Hash&,
const _Equal&,
const allocator_type&,
504 template<
typename _InputIterator>
505 _Hashtable(_InputIterator __first, _InputIterator __last,
506 size_type __bkt_count_hint,
507 const _Hash&,
const _Equal&,
const allocator_type&,
520 const _Hash& __hf = _Hash(),
521 const key_equal& __eql = key_equal(),
522 const allocator_type& __a = allocator_type());
526 noexcept(_S_nothrow_move())
532 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
534 typename __node_alloc_traits::is_always_equal{})
542 template<
typename _InputIterator>
543 _Hashtable(_InputIterator __f, _InputIterator __l,
544 size_type __bkt_count_hint = 0,
545 const _Hash& __hf = _Hash(),
546 const key_equal& __eql = key_equal(),
547 const allocator_type& __a = allocator_type())
548 :
_Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
553 size_type __bkt_count_hint = 0,
554 const _Hash& __hf = _Hash(),
555 const key_equal& __eql = key_equal(),
556 const allocator_type& __a = allocator_type())
557 :
_Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
558 __hf, __eql, __a, __unique_keys{})
566 noexcept(__node_alloc_traits::_S_nothrow_move()
570 constexpr
bool __move_storage =
571 __node_alloc_traits::_S_propagate_on_move_assign()
572 || __node_alloc_traits::_S_always_equal();
580 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
581 _M_before_begin._M_nxt =
nullptr;
585 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
588 if (_M_bucket_count < __l_bkt_count)
589 rehash(__l_bkt_count);
591 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
599 noexcept(__and_<__is_nothrow_swappable<_Hash>,
600 __is_nothrow_swappable<_Equal>>::value);
605 {
return iterator(_M_begin()); }
608 begin()
const noexcept
609 {
return const_iterator(_M_begin()); }
613 {
return iterator(
nullptr); }
617 {
return const_iterator(
nullptr); }
621 {
return const_iterator(_M_begin()); }
624 cend()
const noexcept
625 {
return const_iterator(
nullptr); }
628 size()
const noexcept
629 {
return _M_element_count; }
631 _GLIBCXX_NODISCARD
bool 632 empty()
const noexcept
633 {
return size() == 0; }
636 get_allocator()
const noexcept
637 {
return allocator_type(this->_M_node_allocator()); }
640 max_size()
const noexcept
641 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
646 {
return this->_M_eq(); }
652 bucket_count()
const noexcept
653 {
return _M_bucket_count; }
656 max_bucket_count()
const noexcept
657 {
return max_size(); }
660 bucket_size(size_type __bkt)
const 664 bucket(
const key_type& __k)
const 665 {
return _M_bucket_index(this->_M_hash_code(__k)); }
668 begin(size_type __bkt)
671 __bkt, _M_bucket_count);
676 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
679 begin(size_type __bkt)
const 682 __bkt, _M_bucket_count);
686 end(size_type __bkt)
const 691 cbegin(size_type __bkt)
const 694 __bkt, _M_bucket_count);
698 cend(size_type __bkt)
const 702 load_factor()
const noexcept
704 return static_cast<float>(
size()) / static_cast<float>(bucket_count());
713 __rehash_policy()
const 714 {
return _M_rehash_policy; }
717 __rehash_policy(
const _RehashPolicy& __pol)
718 { _M_rehash_policy = __pol; }
722 find(
const key_type& __k);
725 find(
const key_type& __k)
const;
728 count(
const key_type& __k)
const;
731 equal_range(
const key_type& __k);
734 equal_range(
const key_type& __k)
const;
736 #if __cplusplus >= 202002L 737 #define __cpp_lib_generic_unordered_lookup 201811L 739 template<
typename _Kt,
740 typename = __has_is_transparent_t<_Hash, _Kt>,
741 typename = __has_is_transparent_t<_Equal, _Kt>>
743 _M_find_tr(
const _Kt& __k);
745 template<
typename _Kt,
746 typename = __has_is_transparent_t<_Hash, _Kt>,
747 typename = __has_is_transparent_t<_Equal, _Kt>>
749 _M_find_tr(
const _Kt& __k)
const;
751 template<
typename _Kt,
752 typename = __has_is_transparent_t<_Hash, _Kt>,
753 typename = __has_is_transparent_t<_Equal, _Kt>>
755 _M_count_tr(
const _Kt& __k)
const;
757 template<
typename _Kt,
758 typename = __has_is_transparent_t<_Hash, _Kt>,
759 typename = __has_is_transparent_t<_Equal, _Kt>>
761 _M_equal_range_tr(
const _Kt& __k);
763 template<
typename _Kt,
764 typename = __has_is_transparent_t<_Hash, _Kt>,
765 typename = __has_is_transparent_t<_Equal, _Kt>>
767 _M_equal_range_tr(
const _Kt& __k)
const;
773 _M_bucket_index(
const __node_value_type& __n)
const noexcept
774 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
777 _M_bucket_index(__hash_code __c)
const 778 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
783 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
785 template<
typename _Kt>
787 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
790 _M_find_node(size_type __bkt,
const key_type& __key,
791 __hash_code __c)
const 793 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
795 return static_cast<__node_ptr
>(__before_n->_M_nxt);
799 template<
typename _Kt>
801 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
802 __hash_code __c)
const 804 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
806 return static_cast<__node_ptr
>(__before_n->_M_nxt);
812 _M_insert_bucket_begin(size_type, __node_ptr);
816 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
817 size_type __next_bkt);
821 _M_get_previous_node(size_type __bkt, __node_ptr __n);
827 _M_insert_unique_node(size_type __bkt, __hash_code,
828 __node_ptr __n, size_type __n_elt = 1);
833 _M_insert_multi_node(__node_ptr __hint,
834 __hash_code __code, __node_ptr __n);
836 template<
typename... _Args>
838 _M_emplace(
true_type __uks, _Args&&... __args);
840 template<
typename... _Args>
842 _M_emplace(
false_type __uks, _Args&&... __args)
843 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
846 template<
typename... _Args>
848 _M_emplace(const_iterator,
true_type __uks, _Args&&... __args)
849 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
851 template<
typename... _Args>
853 _M_emplace(const_iterator,
false_type __uks, _Args&&... __args);
855 template<
typename _Arg,
typename _NodeGenerator>
857 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type __uks);
859 template<
typename _Arg,
typename _NodeGenerator>
861 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
864 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
869 template<
typename _Arg,
typename _NodeGenerator>
871 _M_insert(const_iterator, _Arg&& __arg,
872 const _NodeGenerator& __node_gen,
true_type __uks)
875 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).
first;
879 template<
typename _Arg,
typename _NodeGenerator>
881 _M_insert(const_iterator, _Arg&&,
885 _M_erase(
true_type __uks,
const key_type&);
891 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
895 template<
typename... _Args>
897 emplace(_Args&&... __args)
898 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
900 template<
typename... _Args>
902 emplace_hint(const_iterator __hint, _Args&&... __args)
904 return _M_emplace(__hint, __unique_keys{},
905 std::forward<_Args>(__args)...);
912 erase(const_iterator);
917 {
return erase(const_iterator(__it)); }
920 erase(
const key_type& __k)
921 {
return _M_erase(__unique_keys{}, __k); }
924 erase(const_iterator, const_iterator);
931 void rehash(size_type __bkt_count);
936 #if __cplusplus > 201402L 943 __ret.position =
end();
946 __glibcxx_assert(get_allocator() == __nh.get_allocator());
948 const key_type& __k = __nh._M_key();
949 __hash_code __code = this->_M_hash_code(__k);
950 size_type __bkt = _M_bucket_index(__code);
951 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
954 __ret.position = iterator(__n);
955 __ret.inserted =
false;
960 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
961 __nh._M_ptr =
nullptr;
962 __ret.inserted =
true;
975 __glibcxx_assert(get_allocator() == __nh.get_allocator());
977 const key_type& __k = __nh._M_key();
978 auto __code = this->_M_hash_code(__k);
980 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
981 __nh._M_ptr =
nullptr;
987 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
989 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
990 if (__prev_n == _M_buckets[__bkt])
991 _M_remove_bucket_begin(__bkt, __n->_M_next(),
992 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
993 else if (__n->_M_nxt)
995 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
996 if (__next_bkt != __bkt)
997 _M_buckets[__next_bkt] = __prev_n;
1000 __prev_n->_M_nxt = __n->_M_nxt;
1001 __n->_M_nxt =
nullptr;
1003 return { __n, this->_M_node_allocator() };
1009 extract(const_iterator __pos)
1011 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1012 return _M_extract_node(__bkt,
1013 _M_get_previous_node(__bkt, __pos._M_cur));
1021 __hash_code __code = this->_M_hash_code(__k);
1022 std::size_t __bkt = _M_bucket_index(__code);
1023 if (
__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1024 __nh = _M_extract_node(__bkt, __prev_node);
1029 template<
typename _Compatible_Hashtable>
1033 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1034 node_type>,
"Node types are compatible");
1035 __glibcxx_assert(get_allocator() == __src.get_allocator());
1037 auto __n_elt = __src.size();
1038 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1041 const key_type& __k = _ExtractKey{}(*__pos);
1042 __hash_code __code = this->_M_hash_code(__k);
1043 size_type __bkt = _M_bucket_index(__code);
1044 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1046 auto __nh = __src.extract(__pos);
1047 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1048 __nh._M_ptr =
nullptr;
1051 else if (__n_elt != 1)
1057 template<
typename _Compatible_Hashtable>
1061 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1062 node_type>,
"Node types are compatible");
1063 __glibcxx_assert(get_allocator() == __src.get_allocator());
1065 this->reserve(
size() + __src.size());
1066 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1073 void _M_rehash_aux(size_type __bkt_count,
true_type __uks);
1076 void _M_rehash_aux(size_type __bkt_count,
false_type __uks);
1080 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1085 template<
typename _Key,
typename _Value,
typename _Alloc,
1086 typename _ExtractKey,
typename _Equal,
1087 typename _Hash,
typename _RangeHash,
typename _Unused,
1088 typename _RehashPolicy,
typename _Traits>
1090 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1091 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1092 _M_bucket_begin(size_type __bkt)
const 1095 __node_base_ptr __n = _M_buckets[__bkt];
1096 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
1099 template<
typename _Key,
typename _Value,
typename _Alloc,
1100 typename _ExtractKey,
typename _Equal,
1101 typename _Hash,
typename _RangeHash,
typename _Unused,
1102 typename _RehashPolicy,
typename _Traits>
1103 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1104 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1105 _Hashtable(size_type __bkt_count_hint,
1106 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1107 : _Hashtable(__h, __eq, __a)
1109 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1110 if (__bkt_count > _M_bucket_count)
1112 _M_buckets = _M_allocate_buckets(__bkt_count);
1113 _M_bucket_count = __bkt_count;
1117 template<
typename _Key,
typename _Value,
typename _Alloc,
1118 typename _ExtractKey,
typename _Equal,
1119 typename _Hash,
typename _RangeHash,
typename _Unused,
1120 typename _RehashPolicy,
typename _Traits>
1121 template<
typename _InputIterator>
1122 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1123 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1124 _Hashtable(_InputIterator __f, _InputIterator __l,
1125 size_type __bkt_count_hint,
1126 const _Hash& __h,
const _Equal& __eq,
1128 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1130 for (; __f != __l; ++__f)
1134 template<
typename _Key,
typename _Value,
typename _Alloc,
1135 typename _ExtractKey,
typename _Equal,
1136 typename _Hash,
typename _RangeHash,
typename _Unused,
1137 typename _RehashPolicy,
typename _Traits>
1138 template<
typename _InputIterator>
1139 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1140 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1141 _Hashtable(_InputIterator __f, _InputIterator __l,
1142 size_type __bkt_count_hint,
1143 const _Hash& __h,
const _Equal& __eq,
1145 : _Hashtable(__h, __eq, __a)
1147 auto __nb_elems = __detail::__distance_fw(__f, __l);
1149 _M_rehash_policy._M_next_bkt(
1150 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1153 if (__bkt_count > _M_bucket_count)
1155 _M_buckets = _M_allocate_buckets(__bkt_count);
1156 _M_bucket_count = __bkt_count;
1159 for (; __f != __l; ++__f)
1163 template<
typename _Key,
typename _Value,
typename _Alloc,
1164 typename _ExtractKey,
typename _Equal,
1165 typename _Hash,
typename _RangeHash,
typename _Unused,
1166 typename _RehashPolicy,
typename _Traits>
1168 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1169 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1170 operator=(
const _Hashtable& __ht)
1176 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1178 auto& __this_alloc = this->_M_node_allocator();
1179 auto& __that_alloc = __ht._M_node_allocator();
1180 if (!__node_alloc_traits::_S_always_equal()
1181 && __this_alloc != __that_alloc)
1184 this->_M_deallocate_nodes(_M_begin());
1185 _M_before_begin._M_nxt =
nullptr;
1186 _M_deallocate_buckets();
1187 _M_buckets =
nullptr;
1188 std::__alloc_on_copy(__this_alloc, __that_alloc);
1190 _M_bucket_count = __ht._M_bucket_count;
1191 _M_element_count = __ht._M_element_count;
1192 _M_rehash_policy = __ht._M_rehash_policy;
1193 __alloc_node_gen_t __alloc_node_gen(*
this);
1196 _M_assign(__ht, __alloc_node_gen);
1203 __throw_exception_again;
1207 std::__alloc_on_copy(__this_alloc, __that_alloc);
1211 _M_assign_elements(__ht);
1215 template<
typename _Key,
typename _Value,
typename _Alloc,
1216 typename _ExtractKey,
typename _Equal,
1217 typename _Hash,
typename _RangeHash,
typename _Unused,
1218 typename _RehashPolicy,
typename _Traits>
1219 template<
typename _Ht>
1221 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1222 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1223 _M_assign_elements(_Ht&& __ht)
1225 __buckets_ptr __former_buckets =
nullptr;
1226 std::size_t __former_bucket_count = _M_bucket_count;
1227 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1229 if (_M_bucket_count != __ht._M_bucket_count)
1231 __former_buckets = _M_buckets;
1232 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1233 _M_bucket_count = __ht._M_bucket_count;
1236 __builtin_memset(_M_buckets, 0,
1237 _M_bucket_count *
sizeof(__node_base_ptr));
1242 _M_element_count = __ht._M_element_count;
1243 _M_rehash_policy = __ht._M_rehash_policy;
1244 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1245 _M_before_begin._M_nxt =
nullptr;
1246 _M_assign(std::forward<_Ht>(__ht), __roan);
1247 if (__former_buckets)
1248 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1252 if (__former_buckets)
1255 _M_deallocate_buckets();
1256 _M_rehash_policy._M_reset(__former_state);
1257 _M_buckets = __former_buckets;
1258 _M_bucket_count = __former_bucket_count;
1260 __builtin_memset(_M_buckets, 0,
1261 _M_bucket_count *
sizeof(__node_base_ptr));
1262 __throw_exception_again;
1266 template<
typename _Key,
typename _Value,
typename _Alloc,
1267 typename _ExtractKey,
typename _Equal,
1268 typename _Hash,
typename _RangeHash,
typename _Unused,
1269 typename _RehashPolicy,
typename _Traits>
1270 template<
typename _Ht,
typename _NodeGenerator>
1272 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1273 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1274 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1276 __buckets_ptr __buckets =
nullptr;
1278 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1282 if (!__ht._M_before_begin._M_nxt)
1287 __node_ptr __ht_n = __ht._M_begin();
1289 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1290 this->_M_copy_code(*__this_n, *__ht_n);
1291 _M_update_bbegin(__this_n);
1294 __node_ptr __prev_n = __this_n;
1295 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1297 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1298 __prev_n->_M_nxt = __this_n;
1299 this->_M_copy_code(*__this_n, *__ht_n);
1300 size_type __bkt = _M_bucket_index(*__this_n);
1301 if (!_M_buckets[__bkt])
1302 _M_buckets[__bkt] = __prev_n;
1303 __prev_n = __this_n;
1310 _M_deallocate_buckets();
1311 __throw_exception_again;
1315 template<
typename _Key,
typename _Value,
typename _Alloc,
1316 typename _ExtractKey,
typename _Equal,
1317 typename _Hash,
typename _RangeHash,
typename _Unused,
1318 typename _RehashPolicy,
typename _Traits>
1320 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1321 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1324 _M_rehash_policy._M_reset();
1325 _M_bucket_count = 1;
1326 _M_single_bucket =
nullptr;
1327 _M_buckets = &_M_single_bucket;
1328 _M_before_begin._M_nxt =
nullptr;
1329 _M_element_count = 0;
1332 template<
typename _Key,
typename _Value,
typename _Alloc,
1333 typename _ExtractKey,
typename _Equal,
1334 typename _Hash,
typename _RangeHash,
typename _Unused,
1335 typename _RehashPolicy,
typename _Traits>
1337 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1338 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1339 _M_move_assign(_Hashtable&& __ht,
true_type)
1344 this->_M_deallocate_nodes(_M_begin());
1345 _M_deallocate_buckets();
1347 _M_rehash_policy = __ht._M_rehash_policy;
1348 if (!__ht._M_uses_single_bucket())
1349 _M_buckets = __ht._M_buckets;
1352 _M_buckets = &_M_single_bucket;
1353 _M_single_bucket = __ht._M_single_bucket;
1356 _M_bucket_count = __ht._M_bucket_count;
1357 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1358 _M_element_count = __ht._M_element_count;
1359 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1366 template<
typename _Key,
typename _Value,
typename _Alloc,
1367 typename _ExtractKey,
typename _Equal,
1368 typename _Hash,
typename _RangeHash,
typename _Unused,
1369 typename _RehashPolicy,
typename _Traits>
1371 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1372 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1373 _M_move_assign(_Hashtable&& __ht,
false_type)
1375 if (__ht._M_node_allocator() == this->_M_node_allocator())
1385 template<
typename _Key,
typename _Value,
typename _Alloc,
1386 typename _ExtractKey,
typename _Equal,
1387 typename _Hash,
typename _RangeHash,
typename _Unused,
1388 typename _RehashPolicy,
typename _Traits>
1389 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1390 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1391 _Hashtable(
const _Hashtable& __ht)
1392 : __hashtable_base(__ht),
1394 __rehash_base(__ht),
1396 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1397 _M_buckets(nullptr),
1398 _M_bucket_count(__ht._M_bucket_count),
1399 _M_element_count(__ht._M_element_count),
1400 _M_rehash_policy(__ht._M_rehash_policy)
1402 __alloc_node_gen_t __alloc_node_gen(*
this);
1403 _M_assign(__ht, __alloc_node_gen);
1406 template<
typename _Key,
typename _Value,
typename _Alloc,
1407 typename _ExtractKey,
typename _Equal,
1408 typename _Hash,
typename _RangeHash,
typename _Unused,
1409 typename _RehashPolicy,
typename _Traits>
1410 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1411 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1412 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1414 noexcept(_S_nothrow_move())
1415 : __hashtable_base(__ht),
1417 __rehash_base(__ht),
1418 __hashtable_alloc(
std::
move(__a)),
1419 _M_buckets(__ht._M_buckets),
1420 _M_bucket_count(__ht._M_bucket_count),
1421 _M_before_begin(__ht._M_before_begin._M_nxt),
1422 _M_element_count(__ht._M_element_count),
1423 _M_rehash_policy(__ht._M_rehash_policy)
1426 if (__ht._M_uses_single_bucket())
1428 _M_buckets = &_M_single_bucket;
1429 _M_single_bucket = __ht._M_single_bucket;
1438 template<
typename _Key,
typename _Value,
typename _Alloc,
1439 typename _ExtractKey,
typename _Equal,
1440 typename _Hash,
typename _RangeHash,
typename _Unused,
1441 typename _RehashPolicy,
typename _Traits>
1442 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1443 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1444 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1445 : __hashtable_base(__ht),
1447 __rehash_base(__ht),
1448 __hashtable_alloc(__node_alloc_type(__a)),
1450 _M_bucket_count(__ht._M_bucket_count),
1451 _M_element_count(__ht._M_element_count),
1452 _M_rehash_policy(__ht._M_rehash_policy)
1454 __alloc_node_gen_t __alloc_node_gen(*
this);
1455 _M_assign(__ht, __alloc_node_gen);
1458 template<
typename _Key,
typename _Value,
typename _Alloc,
1459 typename _ExtractKey,
typename _Equal,
1460 typename _Hash,
typename _RangeHash,
typename _Unused,
1461 typename _RehashPolicy,
typename _Traits>
1462 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1463 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1464 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1466 : __hashtable_base(__ht),
1468 __rehash_base(__ht),
1469 __hashtable_alloc(
std::
move(__a)),
1470 _M_buckets(nullptr),
1471 _M_bucket_count(__ht._M_bucket_count),
1472 _M_element_count(__ht._M_element_count),
1473 _M_rehash_policy(__ht._M_rehash_policy)
1475 if (__ht._M_node_allocator() == this->_M_node_allocator())
1477 if (__ht._M_uses_single_bucket())
1479 _M_buckets = &_M_single_bucket;
1480 _M_single_bucket = __ht._M_single_bucket;
1483 _M_buckets = __ht._M_buckets;
1487 _M_update_bbegin(__ht._M_begin());
1493 __alloc_node_gen_t __alloc_gen(*
this);
1495 using _Fwd_Ht =
typename 1496 conditional<__move_if_noexcept_cond<value_type>::value,
1497 const _Hashtable&, _Hashtable&&>::type;
1498 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1503 template<
typename _Key,
typename _Value,
typename _Alloc,
1504 typename _ExtractKey,
typename _Equal,
1505 typename _Hash,
typename _RangeHash,
typename _Unused,
1506 typename _RehashPolicy,
typename _Traits>
1507 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1508 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1509 ~_Hashtable() noexcept
1512 _M_deallocate_buckets();
1515 template<
typename _Key,
typename _Value,
typename _Alloc,
1516 typename _ExtractKey,
typename _Equal,
1517 typename _Hash,
typename _RangeHash,
typename _Unused,
1518 typename _RehashPolicy,
typename _Traits>
1520 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1521 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
:: 1522 swap(_Hashtable& __x)
1523 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1524 __is_nothrow_swappable<_Equal>>::value)
1531 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1532 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1535 if (this->_M_uses_single_bucket())
1537 if (!__x._M_uses_single_bucket())
1539 _M_buckets = __x._M_buckets;
1540 __x._M_buckets = &__x._M_single_bucket;
1543 else if (__x._M_uses_single_bucket())
1545 __x._M_buckets = _M_buckets;
1546 _M_buckets = &_M_single_bucket;
1549 std::swap(_M_buckets, __x._M_buckets);
1551 std::swap(_M_bucket_count, __x._M_bucket_count);
1552 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1553 std::swap(_M_element_count, __x._M_element_count);
1554 std::swap(_M_single_bucket, __x._M_single_bucket);
1559 __x._M_update_bbegin();
1562 template<
typename _Key,
typename _Value,
typename _Alloc,
1563 typename _ExtractKey,
typename _Equal,
1564 typename _Hash,
typename _RangeHash,
typename _Unused,
1565 typename _RehashPolicy,
typename _Traits>
1567 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1568 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1569 find(
const key_type& __k)
1572 __hash_code __code = this->_M_hash_code(__k);
1573 std::size_t __bkt = _M_bucket_index(__code);
1574 return iterator(_M_find_node(__bkt, __k, __code));
1577 template<
typename _Key,
typename _Value,
typename _Alloc,
1578 typename _ExtractKey,
typename _Equal,
1579 typename _Hash,
typename _RangeHash,
typename _Unused,
1580 typename _RehashPolicy,
typename _Traits>
1582 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1583 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1584 find(
const key_type& __k)
const 1587 __hash_code __code = this->_M_hash_code(__k);
1588 std::size_t __bkt = _M_bucket_index(__code);
1589 return const_iterator(_M_find_node(__bkt, __k, __code));
1592 #if __cplusplus > 201703L 1593 template<
typename _Key,
typename _Value,
typename _Alloc,
1594 typename _ExtractKey,
typename _Equal,
1595 typename _Hash,
typename _RangeHash,
typename _Unused,
1596 typename _RehashPolicy,
typename _Traits>
1597 template<
typename _Kt,
typename,
typename>
1599 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1600 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1601 _M_find_tr(
const _Kt& __k)
1604 __hash_code __code = this->_M_hash_code_tr(__k);
1605 std::size_t __bkt = _M_bucket_index(__code);
1606 return iterator(_M_find_node_tr(__bkt, __k, __code));
1609 template<
typename _Key,
typename _Value,
typename _Alloc,
1610 typename _ExtractKey,
typename _Equal,
1611 typename _Hash,
typename _RangeHash,
typename _Unused,
1612 typename _RehashPolicy,
typename _Traits>
1613 template<
typename _Kt,
typename,
typename>
1615 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1616 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1617 _M_find_tr(
const _Kt& __k)
const 1620 __hash_code __code = this->_M_hash_code_tr(__k);
1621 std::size_t __bkt = _M_bucket_index(__code);
1622 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1626 template<
typename _Key,
typename _Value,
typename _Alloc,
1627 typename _ExtractKey,
typename _Equal,
1628 typename _Hash,
typename _RangeHash,
typename _Unused,
1629 typename _RehashPolicy,
typename _Traits>
1631 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1632 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1633 count(
const key_type& __k)
const 1636 auto __it = find(__k);
1640 if (__unique_keys::value)
1646 size_type __result = 1;
1647 for (
auto __ref = __it++;
1648 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1655 #if __cplusplus > 201703L 1656 template<
typename _Key,
typename _Value,
typename _Alloc,
1657 typename _ExtractKey,
typename _Equal,
1658 typename _Hash,
typename _RangeHash,
typename _Unused,
1659 typename _RehashPolicy,
typename _Traits>
1660 template<
typename _Kt,
typename,
typename>
1662 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1663 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1664 _M_count_tr(
const _Kt& __k)
const 1667 __hash_code __code = this->_M_hash_code_tr(__k);
1668 std::size_t __bkt = _M_bucket_index(__code);
1669 auto __n = _M_find_node_tr(__bkt, __k, __code);
1677 size_type __result = 1;
1679 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1687 template<
typename _Key,
typename _Value,
typename _Alloc,
1688 typename _ExtractKey,
typename _Equal,
1689 typename _Hash,
typename _RangeHash,
typename _Unused,
1690 typename _RehashPolicy,
typename _Traits>
1692 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1693 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1694 equal_range(
const key_type& __k)
1695 -> pair<iterator, iterator>
1697 auto __ite = find(__k);
1699 return { __ite, __ite };
1701 auto __beg = __ite++;
1702 if (__unique_keys::value)
1703 return { __beg, __ite };
1708 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1711 return { __beg, __ite };
1714 template<
typename _Key,
typename _Value,
typename _Alloc,
1715 typename _ExtractKey,
typename _Equal,
1716 typename _Hash,
typename _RangeHash,
typename _Unused,
1717 typename _RehashPolicy,
typename _Traits>
1719 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1720 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1721 equal_range(
const key_type& __k)
const 1722 -> pair<const_iterator, const_iterator>
1724 auto __ite = find(__k);
1726 return { __ite, __ite };
1728 auto __beg = __ite++;
1729 if (__unique_keys::value)
1730 return { __beg, __ite };
1735 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1738 return { __beg, __ite };
1741 #if __cplusplus > 201703L 1742 template<
typename _Key,
typename _Value,
typename _Alloc,
1743 typename _ExtractKey,
typename _Equal,
1744 typename _Hash,
typename _RangeHash,
typename _Unused,
1745 typename _RehashPolicy,
typename _Traits>
1746 template<
typename _Kt,
typename,
typename>
1748 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1749 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1750 _M_equal_range_tr(
const _Kt& __k)
1751 -> pair<iterator, iterator>
1753 __hash_code __code = this->_M_hash_code_tr(__k);
1754 std::size_t __bkt = _M_bucket_index(__code);
1755 auto __n = _M_find_node_tr(__bkt, __k, __code);
1756 iterator __ite(__n);
1758 return { __ite, __ite };
1763 auto __beg = __ite++;
1764 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1767 return { __beg, __ite };
1770 template<
typename _Key,
typename _Value,
typename _Alloc,
1771 typename _ExtractKey,
typename _Equal,
1772 typename _Hash,
typename _RangeHash,
typename _Unused,
1773 typename _RehashPolicy,
typename _Traits>
1774 template<
typename _Kt,
typename,
typename>
1776 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1777 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1778 _M_equal_range_tr(
const _Kt& __k)
const 1779 -> pair<const_iterator, const_iterator>
1781 __hash_code __code = this->_M_hash_code_tr(__k);
1782 std::size_t __bkt = _M_bucket_index(__code);
1783 auto __n = _M_find_node_tr(__bkt, __k, __code);
1784 const_iterator __ite(__n);
1786 return { __ite, __ite };
1791 auto __beg = __ite++;
1792 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1795 return { __beg, __ite };
1801 template<
typename _Key,
typename _Value,
typename _Alloc,
1802 typename _ExtractKey,
typename _Equal,
1803 typename _Hash,
typename _RangeHash,
typename _Unused,
1804 typename _RehashPolicy,
typename _Traits>
1806 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1807 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1808 _M_find_before_node(size_type __bkt,
const key_type& __k,
1809 __hash_code __code)
const 1812 __node_base_ptr __prev_p = _M_buckets[__bkt];
1816 for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
1817 __p = __p->_M_next())
1819 if (this->_M_equals(__k, __code, *__p))
1822 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1830 template<
typename _Key,
typename _Value,
typename _Alloc,
1831 typename _ExtractKey,
typename _Equal,
1832 typename _Hash,
typename _RangeHash,
typename _Unused,
1833 typename _RehashPolicy,
typename _Traits>
1834 template<
typename _Kt>
1836 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1837 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1838 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1839 __hash_code __code)
const 1842 __node_base_ptr __prev_p = _M_buckets[__bkt];
1846 for (__node_ptr __p = static_cast<__node_ptr>(__prev_p->_M_nxt);;
1847 __p = __p->_M_next())
1849 if (this->_M_equals_tr(__k, __code, *__p))
1852 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1860 template<
typename _Key,
typename _Value,
typename _Alloc,
1861 typename _ExtractKey,
typename _Equal,
1862 typename _Hash,
typename _RangeHash,
typename _Unused,
1863 typename _RehashPolicy,
typename _Traits>
1865 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1866 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1867 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1869 if (_M_buckets[__bkt])
1873 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1874 _M_buckets[__bkt]->_M_nxt = __node;
1881 __node->_M_nxt = _M_before_begin._M_nxt;
1882 _M_before_begin._M_nxt = __node;
1887 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
1889 _M_buckets[__bkt] = &_M_before_begin;
1893 template<
typename _Key,
typename _Value,
typename _Alloc,
1894 typename _ExtractKey,
typename _Equal,
1895 typename _Hash,
typename _RangeHash,
typename _Unused,
1896 typename _RehashPolicy,
typename _Traits>
1898 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1899 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1900 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
1901 size_type __next_bkt)
1903 if (!__next || __next_bkt != __bkt)
1908 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1911 if (&_M_before_begin == _M_buckets[__bkt])
1912 _M_before_begin._M_nxt = __next;
1913 _M_buckets[__bkt] =
nullptr;
1917 template<
typename _Key,
typename _Value,
typename _Alloc,
1918 typename _ExtractKey,
typename _Equal,
1919 typename _Hash,
typename _RangeHash,
typename _Unused,
1920 typename _RehashPolicy,
typename _Traits>
1922 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1923 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1924 _M_get_previous_node(size_type __bkt, __node_ptr __n)
1927 __node_base_ptr __prev_n = _M_buckets[__bkt];
1928 while (__prev_n->_M_nxt != __n)
1929 __prev_n = __prev_n->_M_nxt;
1933 template<
typename _Key,
typename _Value,
typename _Alloc,
1934 typename _ExtractKey,
typename _Equal,
1935 typename _Hash,
typename _RangeHash,
typename _Unused,
1936 typename _RehashPolicy,
typename _Traits>
1937 template<
typename... _Args>
1939 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1940 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1941 _M_emplace(
true_type , _Args&&... __args)
1942 -> pair<iterator, bool>
1945 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1946 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1947 __hash_code __code = this->_M_hash_code(__k);
1948 size_type __bkt = _M_bucket_index(__code);
1949 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
1951 return std::make_pair(iterator(__p),
false);
1954 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
1955 __node._M_node =
nullptr;
1956 return { __pos,
true };
1959 template<
typename _Key,
typename _Value,
typename _Alloc,
1960 typename _ExtractKey,
typename _Equal,
1961 typename _Hash,
typename _RangeHash,
typename _Unused,
1962 typename _RehashPolicy,
typename _Traits>
1963 template<
typename... _Args>
1965 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1966 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1967 _M_emplace(const_iterator __hint,
false_type ,
1972 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1973 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1975 __hash_code __code = this->_M_hash_code(__k);
1977 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
1978 __node._M_node =
nullptr;
1982 template<
typename _Key,
typename _Value,
typename _Alloc,
1983 typename _ExtractKey,
typename _Equal,
1984 typename _Hash,
typename _RangeHash,
typename _Unused,
1985 typename _RehashPolicy,
typename _Traits>
1987 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1988 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1989 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1990 __node_ptr __node, size_type __n_elt)
1993 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1995 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1998 if (__do_rehash.
first)
2000 _M_rehash(__do_rehash.
second, __saved_state);
2001 __bkt = _M_bucket_index(__code);
2004 this->_M_store_code(*__node, __code);
2007 _M_insert_bucket_begin(__bkt, __node);
2009 return iterator(__node);
2012 template<
typename _Key,
typename _Value,
typename _Alloc,
2013 typename _ExtractKey,
typename _Equal,
2014 typename _Hash,
typename _RangeHash,
typename _Unused,
2015 typename _RehashPolicy,
typename _Traits>
2017 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2018 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2019 _M_insert_multi_node(__node_ptr __hint,
2020 __hash_code __code, __node_ptr __node)
2023 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2025 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2027 if (__do_rehash.
first)
2028 _M_rehash(__do_rehash.
second, __saved_state);
2030 this->_M_store_code(*__node, __code);
2031 const key_type& __k = _ExtractKey{}(__node->_M_v());
2032 size_type __bkt = _M_bucket_index(__code);
2036 __node_base_ptr __prev
2037 = __builtin_expect(__hint !=
nullptr,
false)
2038 && this->_M_equals(__k, __code, *__hint)
2040 : _M_find_before_node(__bkt, __k, __code);
2045 __node->_M_nxt = __prev->_M_nxt;
2046 __prev->_M_nxt = __node;
2047 if (__builtin_expect(__prev == __hint,
false))
2051 && !this->_M_equals(__k, __code, *__node->_M_next()))
2053 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2054 if (__next_bkt != __bkt)
2055 _M_buckets[__next_bkt] = __node;
2062 _M_insert_bucket_begin(__bkt, __node);
2064 return iterator(__node);
2068 template<
typename _Key,
typename _Value,
typename _Alloc,
2069 typename _ExtractKey,
typename _Equal,
2070 typename _Hash,
typename _RangeHash,
typename _Unused,
2071 typename _RehashPolicy,
typename _Traits>
2072 template<
typename _Arg,
typename _NodeGenerator>
2074 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2075 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2076 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
2078 -> pair<iterator, bool>
2080 const key_type& __k = _ExtractKey{}(__v);
2081 __hash_code __code = this->_M_hash_code(__k);
2082 size_type __bkt = _M_bucket_index(__code);
2084 if (__node_ptr __node = _M_find_node(__bkt, __k, __code))
2085 return { iterator(__node),
false };
2087 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2089 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2090 __node._M_node =
nullptr;
2091 return { __pos,
true };
2095 template<
typename _Key,
typename _Value,
typename _Alloc,
2096 typename _ExtractKey,
typename _Equal,
2097 typename _Hash,
typename _RangeHash,
typename _Unused,
2098 typename _RehashPolicy,
typename _Traits>
2099 template<
typename _Arg,
typename _NodeGenerator>
2101 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2102 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2103 _M_insert(const_iterator __hint, _Arg&& __v,
2104 const _NodeGenerator& __node_gen,
2110 __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
2113 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2115 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
2116 __node._M_node =
nullptr;
2120 template<
typename _Key,
typename _Value,
typename _Alloc,
2121 typename _ExtractKey,
typename _Equal,
2122 typename _Hash,
typename _RangeHash,
typename _Unused,
2123 typename _RehashPolicy,
typename _Traits>
2125 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2126 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2127 erase(const_iterator __it)
2130 __node_ptr __n = __it._M_cur;
2131 std::size_t __bkt = _M_bucket_index(*__n);
2136 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2137 return _M_erase(__bkt, __prev_n, __n);
2140 template<
typename _Key,
typename _Value,
typename _Alloc,
2141 typename _ExtractKey,
typename _Equal,
2142 typename _Hash,
typename _RangeHash,
typename _Unused,
2143 typename _RehashPolicy,
typename _Traits>
2145 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2146 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2147 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2150 if (__prev_n == _M_buckets[__bkt])
2151 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2152 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2153 else if (__n->_M_nxt)
2155 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2156 if (__next_bkt != __bkt)
2157 _M_buckets[__next_bkt] = __prev_n;
2160 __prev_n->_M_nxt = __n->_M_nxt;
2161 iterator __result(__n->_M_next());
2162 this->_M_deallocate_node(__n);
2168 template<
typename _Key,
typename _Value,
typename _Alloc,
2169 typename _ExtractKey,
typename _Equal,
2170 typename _Hash,
typename _RangeHash,
typename _Unused,
2171 typename _RehashPolicy,
typename _Traits>
2173 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2174 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2175 _M_erase(
true_type ,
const key_type& __k)
2178 __hash_code __code = this->_M_hash_code(__k);
2179 std::size_t __bkt = _M_bucket_index(__code);
2182 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2187 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2188 _M_erase(__bkt, __prev_n, __n);
2192 template<
typename _Key,
typename _Value,
typename _Alloc,
2193 typename _ExtractKey,
typename _Equal,
2194 typename _Hash,
typename _RangeHash,
typename _Unused,
2195 typename _RehashPolicy,
typename _Traits>
2197 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2198 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2202 __hash_code __code = this->_M_hash_code(__k);
2203 std::size_t __bkt = _M_bucket_index(__code);
2206 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2216 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2217 __node_ptr __n_last = __n->_M_next();
2218 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2219 __n_last = __n_last->_M_next();
2221 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2224 size_type __result = 0;
2227 __node_ptr __p = __n->_M_next();
2228 this->_M_deallocate_node(__n);
2232 while (__n != __n_last);
2234 _M_element_count -= __result;
2235 if (__prev_n == _M_buckets[__bkt])
2236 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2237 else if (__n_last_bkt != __bkt)
2238 _M_buckets[__n_last_bkt] = __prev_n;
2239 __prev_n->_M_nxt = __n_last;
2243 template<
typename _Key,
typename _Value,
typename _Alloc,
2244 typename _ExtractKey,
typename _Equal,
2245 typename _Hash,
typename _RangeHash,
typename _Unused,
2246 typename _RehashPolicy,
typename _Traits>
2248 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2249 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2250 erase(const_iterator __first, const_iterator __last)
2253 __node_ptr __n = __first._M_cur;
2254 __node_ptr __last_n = __last._M_cur;
2255 if (__n == __last_n)
2256 return iterator(__n);
2258 std::size_t __bkt = _M_bucket_index(*__n);
2260 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2261 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2262 std::size_t __n_bkt = __bkt;
2267 __node_ptr __tmp = __n;
2268 __n = __n->_M_next();
2269 this->_M_deallocate_node(__tmp);
2273 __n_bkt = _M_bucket_index(*__n);
2275 while (__n != __last_n && __n_bkt == __bkt);
2276 if (__is_bucket_begin)
2277 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2278 if (__n == __last_n)
2280 __is_bucket_begin =
true;
2284 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2285 _M_buckets[__n_bkt] = __prev_n;
2286 __prev_n->_M_nxt = __n;
2287 return iterator(__n);
2290 template<
typename _Key,
typename _Value,
typename _Alloc,
2291 typename _ExtractKey,
typename _Equal,
2292 typename _Hash,
typename _RangeHash,
typename _Unused,
2293 typename _RehashPolicy,
typename _Traits>
2295 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2296 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2299 this->_M_deallocate_nodes(_M_begin());
2300 __builtin_memset(_M_buckets, 0,
2301 _M_bucket_count *
sizeof(__node_base_ptr));
2302 _M_element_count = 0;
2303 _M_before_begin._M_nxt =
nullptr;
2306 template<
typename _Key,
typename _Value,
typename _Alloc,
2307 typename _ExtractKey,
typename _Equal,
2308 typename _Hash,
typename _RangeHash,
typename _Unused,
2309 typename _RehashPolicy,
typename _Traits>
2311 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2312 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2313 rehash(size_type __bkt_count)
2315 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2317 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2319 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2321 if (__bkt_count != _M_bucket_count)
2322 _M_rehash(__bkt_count, __saved_state);
2326 _M_rehash_policy._M_reset(__saved_state);
2329 template<
typename _Key,
typename _Value,
typename _Alloc,
2330 typename _ExtractKey,
typename _Equal,
2331 typename _Hash,
typename _RangeHash,
typename _Unused,
2332 typename _RehashPolicy,
typename _Traits>
2334 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2335 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2336 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2340 _M_rehash_aux(__bkt_count, __unique_keys{});
2346 _M_rehash_policy._M_reset(__state);
2347 __throw_exception_again;
2352 template<
typename _Key,
typename _Value,
typename _Alloc,
2353 typename _ExtractKey,
typename _Equal,
2354 typename _Hash,
typename _RangeHash,
typename _Unused,
2355 typename _RehashPolicy,
typename _Traits>
2357 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2358 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2359 _M_rehash_aux(size_type __bkt_count,
true_type )
2361 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2362 __node_ptr __p = _M_begin();
2363 _M_before_begin._M_nxt =
nullptr;
2364 std::size_t __bbegin_bkt = 0;
2367 __node_ptr __next = __p->_M_next();
2369 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2370 if (!__new_buckets[__bkt])
2372 __p->_M_nxt = _M_before_begin._M_nxt;
2373 _M_before_begin._M_nxt = __p;
2374 __new_buckets[__bkt] = &_M_before_begin;
2376 __new_buckets[__bbegin_bkt] = __p;
2377 __bbegin_bkt = __bkt;
2381 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2382 __new_buckets[__bkt]->_M_nxt = __p;
2388 _M_deallocate_buckets();
2389 _M_bucket_count = __bkt_count;
2390 _M_buckets = __new_buckets;
2395 template<
typename _Key,
typename _Value,
typename _Alloc,
2396 typename _ExtractKey,
typename _Equal,
2397 typename _Hash,
typename _RangeHash,
typename _Unused,
2398 typename _RehashPolicy,
typename _Traits>
2400 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2401 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2402 _M_rehash_aux(size_type __bkt_count,
false_type )
2404 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2405 __node_ptr __p = _M_begin();
2406 _M_before_begin._M_nxt =
nullptr;
2407 std::size_t __bbegin_bkt = 0;
2408 std::size_t __prev_bkt = 0;
2409 __node_ptr __prev_p =
nullptr;
2410 bool __check_bucket =
false;
2414 __node_ptr __next = __p->_M_next();
2416 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2418 if (__prev_p && __prev_bkt == __bkt)
2423 __p->_M_nxt = __prev_p->_M_nxt;
2424 __prev_p->_M_nxt = __p;
2431 __check_bucket =
true;
2439 if (__prev_p->_M_nxt)
2441 std::size_t __next_bkt
2442 = __hash_code_base::_M_bucket_index(
2443 *__prev_p->_M_next(), __bkt_count);
2444 if (__next_bkt != __prev_bkt)
2445 __new_buckets[__next_bkt] = __prev_p;
2447 __check_bucket =
false;
2450 if (!__new_buckets[__bkt])
2452 __p->_M_nxt = _M_before_begin._M_nxt;
2453 _M_before_begin._M_nxt = __p;
2454 __new_buckets[__bkt] = &_M_before_begin;
2456 __new_buckets[__bbegin_bkt] = __p;
2457 __bbegin_bkt = __bkt;
2461 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2462 __new_buckets[__bkt]->_M_nxt = __p;
2470 if (__check_bucket && __prev_p->_M_nxt)
2472 std::size_t __next_bkt
2473 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2475 if (__next_bkt != __prev_bkt)
2476 __new_buckets[__next_bkt] = __prev_p;
2479 _M_deallocate_buckets();
2480 _M_bucket_count = __bkt_count;
2481 _M_buckets = __new_buckets;
2484 #if __cplusplus > 201402L 2485 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2488 #if __cpp_deduction_guides >= 201606 2490 template<
typename _Hash>
2491 using _RequireNotAllocatorOrIntegral
2492 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2495 _GLIBCXX_END_NAMESPACE_VERSION
2498 #endif // _HASHTABLE_H _Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
is_nothrow_copy_constructible
is_nothrow_move_assignable
void _M_merge_unique(_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with unique keys.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
Struct holding two objects of arbitrary type.
Define a member typedef type to one of two argument types.
is_nothrow_default_constructible
void _M_merge_multi(_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with equivalent keys.
constexpr auto cbegin(const _Container &__cont) noexcept(noexcept(std::begin(__cont))) -> decltype(std::begin(__cont))
Return an iterator pointing to the first element of the const container.
_T2 second
The second member.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
node_type extract(const _Key &__k)
Extract a node.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
_T1 first
The first member.
insert_return_type _M_reinsert_node(node_type &&__nh)
Re-insert an extracted node into a container with unique keys.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
void swap(shared_lock< _Mutex > &__x, shared_lock< _Mutex > &__y) noexcept
Swap specialization for shared_lock.
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
Node handle type for maps.
Uniform interface to C++98 and C++11 allocators.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
iterator _M_reinsert_node_multi(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node into a container with equivalent keys.
Return type of insert(node_handle&&) on unique maps/sets.