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&>>>;
169 template<
typename _Key,
typename _Value,
typename _Alloc,
170 typename _ExtractKey,
typename _Equal,
171 typename _H1,
typename _H2,
typename _Hash,
172 typename _RehashPolicy,
typename _Traits>
175 _H1, _H2, _Hash, _Traits>,
177 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
179 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
181 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
183 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
185 __alloc_rebind<_Alloc,
186 __detail::_Hash_node<_Value,
187 _Traits::__hash_cached::value>>>
189 static_assert(
is_same<
typename remove_cv<_Value>::type, _Value>::value,
190 "unordered container must have a non-const, non-volatile value_type");
191 #ifdef __STRICT_ANSI__ 193 "unordered container must have the same value_type as its allocator");
196 using __traits_type = _Traits;
197 using __hash_cached =
typename __traits_type::__hash_cached;
199 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
203 using __value_alloc_traits =
204 typename __hashtable_alloc::__value_alloc_traits;
205 using __node_alloc_traits =
211 typedef _Key key_type;
212 typedef _Value value_type;
213 typedef _Alloc allocator_type;
214 typedef _Equal key_equal;
218 typedef typename __value_alloc_traits::pointer pointer;
219 typedef typename __value_alloc_traits::const_pointer const_pointer;
220 typedef value_type& reference;
221 typedef const value_type& const_reference;
224 using __rehash_type = _RehashPolicy;
225 using __rehash_state =
typename __rehash_type::_State;
227 using __constant_iterators =
typename __traits_type::__constant_iterators;
228 using __unique_keys =
typename __traits_type::__unique_keys;
231 __constant_iterators::value,
233 __detail::_Select1st>::type;
236 _Hashtable_base<_Key, _Value, _ExtractKey,
237 _Equal, _H1, _H2, _Hash, _Traits>;
240 using __hash_code =
typename __hashtable_base::__hash_code;
241 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
244 _Equal, _H1, _H2, _Hash,
245 _RehashPolicy, _Traits>;
250 _RehashPolicy, _Traits>;
253 _Equal, _H1, _H2, _Hash,
254 _RehashPolicy, _Traits>;
256 using __reuse_or_alloc_node_type =
257 __detail::_ReuseOrAllocNode<__node_alloc_type>;
260 template<
typename _Cond>
261 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
263 template<
typename _Cond>
264 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
270 struct __hash_code_base_access : __hash_code_base
271 {
using __hash_code_base::_M_bucket_index; };
275 static_assert(noexcept(declval<const __hash_code_base_access&>()
278 "Cache the hash code or qualify your functors involved" 279 " in hash code and bucket index computation with noexcept");
287 "Functor used to map hash code to bucket index" 288 " must be default constructible");
290 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
291 typename _ExtractKeya,
typename _Equala,
292 typename _H1a,
typename _H2a,
typename _Hasha,
293 typename _RehashPolicya,
typename _Traitsa,
297 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
298 typename _ExtractKeya,
typename _Equala,
299 typename _H1a,
typename _H2a,
typename _Hasha,
300 typename _RehashPolicya,
typename _Traitsa>
303 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
304 typename _ExtractKeya,
typename _Equala,
305 typename _H1a,
typename _H2a,
typename _Hasha,
306 typename _RehashPolicya,
typename _Traitsa,
307 bool _Constant_iteratorsa>
311 using size_type =
typename __hashtable_base::size_type;
312 using difference_type =
typename __hashtable_base::difference_type;
318 using const_local_iterator =
typename __hashtable_base::
319 const_local_iterator;
321 #if __cplusplus > 201402L 322 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
323 using insert_return_type = _Node_insert_return<iterator, node_type>;
327 __bucket_type* _M_buckets = &_M_single_bucket;
328 size_type _M_bucket_count = 1;
329 __node_base _M_before_begin;
330 size_type _M_element_count = 0;
331 _RehashPolicy _M_rehash_policy;
339 __bucket_type _M_single_bucket =
nullptr;
342 _M_uses_single_bucket(__bucket_type* __bkts)
const 343 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
346 _M_uses_single_bucket()
const 347 {
return _M_uses_single_bucket(_M_buckets); }
350 _M_base_alloc() {
return *
this; }
353 _M_allocate_buckets(size_type __n)
355 if (__builtin_expect(__n == 1,
false))
357 _M_single_bucket =
nullptr;
358 return &_M_single_bucket;
361 return __hashtable_alloc::_M_allocate_buckets(__n);
365 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
367 if (_M_uses_single_bucket(__bkts))
370 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
374 _M_deallocate_buckets()
375 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
380 _M_bucket_begin(size_type __bkt)
const;
384 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
388 template<
typename _Ht,
typename _NodeGenerator>
390 _M_assign_elements(_Ht&&,
const _NodeGenerator&);
392 template<
typename _NodeGenerator>
394 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
405 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
406 const _Equal& __eq,
const _ExtractKey& __exk,
407 const allocator_type& __a)
416 const _H1&,
const _H2&,
const _Hash&,
417 const _Equal&,
const _ExtractKey&,
418 const allocator_type&);
420 template<
typename _InputIterator>
421 _Hashtable(_InputIterator __first, _InputIterator __last,
422 size_type __bucket_hint,
423 const _H1&,
const _H2&,
const _Hash&,
424 const _Equal&,
const _ExtractKey&,
425 const allocator_type&);
443 const _H1& __hf = _H1(),
444 const key_equal& __eql = key_equal(),
445 const allocator_type& __a = allocator_type())
446 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
447 __key_extract(), __a)
450 template<
typename _InputIterator>
451 _Hashtable(_InputIterator __f, _InputIterator __l,
453 const _H1& __hf = _H1(),
454 const key_equal& __eql = key_equal(),
455 const allocator_type& __a = allocator_type())
456 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
457 __key_extract(), __a)
462 const _H1& __hf = _H1(),
463 const key_equal& __eql = key_equal(),
464 const allocator_type& __a = allocator_type())
465 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
466 __key_extract(), __a)
474 noexcept(__node_alloc_traits::_S_nothrow_move()
478 constexpr
bool __move_storage =
479 __node_alloc_traits::_S_propagate_on_move_assign()
480 || __node_alloc_traits::_S_always_equal();
488 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
489 _M_before_begin._M_nxt =
nullptr;
491 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
499 noexcept(__and_<__is_nothrow_swappable<_H1>,
500 __is_nothrow_swappable<_Equal>>::value);
505 {
return iterator(_M_begin()); }
508 begin()
const noexcept
509 {
return const_iterator(_M_begin()); }
513 {
return iterator(
nullptr); }
517 {
return const_iterator(
nullptr); }
521 {
return const_iterator(_M_begin()); }
524 cend()
const noexcept
525 {
return const_iterator(
nullptr); }
528 size()
const noexcept
529 {
return _M_element_count; }
531 _GLIBCXX_NODISCARD
bool 532 empty()
const noexcept
533 {
return size() == 0; }
536 get_allocator()
const noexcept
537 {
return allocator_type(this->_M_node_allocator()); }
540 max_size()
const noexcept
541 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
546 {
return this->_M_eq(); }
552 bucket_count()
const noexcept
553 {
return _M_bucket_count; }
556 max_bucket_count()
const noexcept
557 {
return max_size(); }
560 bucket_size(size_type __n)
const 564 bucket(
const key_type& __k)
const 565 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
570 return local_iterator(*
this, _M_bucket_begin(__n),
571 __n, _M_bucket_count);
576 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
579 begin(size_type __n)
const 581 return const_local_iterator(*
this, _M_bucket_begin(__n),
582 __n, _M_bucket_count);
586 end(size_type __n)
const 587 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
591 cbegin(size_type __n)
const 593 return const_local_iterator(*
this, _M_bucket_begin(__n),
594 __n, _M_bucket_count);
598 cend(size_type __n)
const 599 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
602 load_factor()
const noexcept
604 return static_cast<float>(size()) / static_cast<float>(bucket_count());
613 __rehash_policy()
const 614 {
return _M_rehash_policy; }
617 __rehash_policy(
const _RehashPolicy& __pol)
618 { _M_rehash_policy = __pol; }
622 find(
const key_type& __k);
625 find(
const key_type& __k)
const;
628 count(
const key_type& __k)
const;
631 equal_range(
const key_type& __k);
634 equal_range(
const key_type& __k)
const;
640 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
643 _M_bucket_index(
const key_type& __k, __hash_code __c)
const 644 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
649 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
652 _M_find_node(size_type __bkt,
const key_type& __key,
653 __hash_code __c)
const 655 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
657 return static_cast<__node_type*
>(__before_n->_M_nxt);
667 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
668 size_type __next_bkt);
672 _M_get_previous_node(size_type __bkt, __node_base* __n);
678 _M_insert_unique_node(size_type __bkt, __hash_code __code,
687 template<
typename... _Args>
691 template<
typename... _Args>
694 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
697 template<
typename... _Args>
699 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
700 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
702 template<
typename... _Args>
706 template<
typename _Arg,
typename _NodeGenerator>
708 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type, size_type = 1);
710 template<
typename _Arg,
typename _NodeGenerator>
712 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
715 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
720 template<
typename _Arg,
typename _NodeGenerator>
722 _M_insert(const_iterator, _Arg&& __arg,
723 const _NodeGenerator& __node_gen,
true_type __uk)
726 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
730 template<
typename _Arg,
typename _NodeGenerator>
732 _M_insert(const_iterator, _Arg&&,
742 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
746 template<
typename... _Args>
748 emplace(_Args&&... __args)
749 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
751 template<
typename... _Args>
753 emplace_hint(const_iterator __hint, _Args&&... __args)
755 return _M_emplace(__hint, __unique_keys(),
756 std::forward<_Args>(__args)...);
763 erase(const_iterator);
768 {
return erase(const_iterator(__it)); }
771 erase(
const key_type& __k)
772 {
return _M_erase(__unique_keys(), __k); }
775 erase(const_iterator, const_iterator);
781 void rehash(size_type __n);
786 #if __cplusplus > 201402L 789 _M_reinsert_node(node_type&& __nh)
791 insert_return_type __ret;
793 __ret.position =
end();
796 __glibcxx_assert(get_allocator() == __nh.get_allocator());
798 const key_type& __k = __nh._M_key();
799 __hash_code __code = this->_M_hash_code(__k);
800 size_type __bkt = _M_bucket_index(__k, __code);
801 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
803 __ret.node = std::move(__nh);
804 __ret.position = iterator(__n);
805 __ret.inserted =
false;
810 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
811 __nh._M_ptr =
nullptr;
812 __ret.inserted =
true;
820 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
827 __glibcxx_assert(get_allocator() == __nh.get_allocator());
829 auto __code = this->_M_hash_code(__nh._M_key());
832 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
839 extract(const_iterator __pos)
842 size_t __bkt = _M_bucket_index(__n);
847 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
849 if (__prev_n == _M_buckets[__bkt])
850 _M_remove_bucket_begin(__bkt, __n->_M_next(),
851 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
852 else if (__n->_M_nxt)
854 size_type __next_bkt = _M_bucket_index(__n->_M_next());
855 if (__next_bkt != __bkt)
856 _M_buckets[__next_bkt] = __prev_n;
859 __prev_n->_M_nxt = __n->_M_nxt;
860 __n->_M_nxt =
nullptr;
862 return { __n, this->_M_node_allocator() };
867 extract(
const _Key& __k)
870 auto __pos = find(__k);
872 __nh = extract(const_iterator(__pos));
877 template<
typename _Compatible_Hashtable>
879 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
881 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
882 node_type>,
"Node types are compatible");
883 __glibcxx_assert(get_allocator() == __src.get_allocator());
885 auto __n_elt = __src.size();
886 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
889 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
890 __hash_code __code = this->_M_hash_code(__k);
891 size_type __bkt = _M_bucket_index(__k, __code);
892 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
894 auto __nh = __src.extract(__pos);
895 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
896 __nh._M_ptr =
nullptr;
899 else if (__n_elt != 1)
905 template<
typename _Compatible_Hashtable>
907 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
909 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
910 node_type>,
"Node types are compatible");
911 __glibcxx_assert(get_allocator() == __src.get_allocator());
913 this->reserve(size() + __src.size());
914 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
915 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
928 void _M_rehash(size_type __n,
const __rehash_state& __state);
933 template<
typename _Key,
typename _Value,
934 typename _Alloc,
typename _ExtractKey,
typename _Equal,
935 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
938 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
939 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
940 _M_bucket_begin(size_type __bkt)
const 943 __node_base* __n = _M_buckets[__bkt];
944 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
947 template<
typename _Key,
typename _Value,
948 typename _Alloc,
typename _ExtractKey,
typename _Equal,
949 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
951 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
952 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
953 _Hashtable(size_type __bucket_hint,
954 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
955 const _Equal& __eq,
const _ExtractKey& __exk,
956 const allocator_type& __a)
957 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
959 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
960 if (__bkt > _M_bucket_count)
962 _M_buckets = _M_allocate_buckets(__bkt);
963 _M_bucket_count = __bkt;
967 template<
typename _Key,
typename _Value,
968 typename _Alloc,
typename _ExtractKey,
typename _Equal,
969 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
971 template<
typename _InputIterator>
972 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
973 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
974 _Hashtable(_InputIterator __f, _InputIterator __l,
975 size_type __bucket_hint,
976 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
977 const _Equal& __eq,
const _ExtractKey& __exk,
978 const allocator_type& __a)
979 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
981 auto __nb_elems = __detail::__distance_fw(__f, __l);
983 _M_rehash_policy._M_next_bkt(
984 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
987 if (__bkt_count > _M_bucket_count)
989 _M_buckets = _M_allocate_buckets(__bkt_count);
990 _M_bucket_count = __bkt_count;
993 for (; __f != __l; ++__f)
997 template<
typename _Key,
typename _Value,
998 typename _Alloc,
typename _ExtractKey,
typename _Equal,
999 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1002 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1003 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1004 operator=(
const _Hashtable& __ht)
1010 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1012 auto& __this_alloc = this->_M_node_allocator();
1013 auto& __that_alloc = __ht._M_node_allocator();
1014 if (!__node_alloc_traits::_S_always_equal()
1015 && __this_alloc != __that_alloc)
1018 this->_M_deallocate_nodes(_M_begin());
1019 _M_before_begin._M_nxt =
nullptr;
1020 _M_deallocate_buckets();
1021 _M_buckets =
nullptr;
1022 std::__alloc_on_copy(__this_alloc, __that_alloc);
1023 __hashtable_base::operator=(__ht);
1024 _M_bucket_count = __ht._M_bucket_count;
1025 _M_element_count = __ht._M_element_count;
1026 _M_rehash_policy = __ht._M_rehash_policy;
1030 [
this](
const __node_type* __n)
1031 {
return this->_M_allocate_node(__n->_M_v()); });
1038 __throw_exception_again;
1042 std::__alloc_on_copy(__this_alloc, __that_alloc);
1046 _M_assign_elements(__ht,
1047 [](
const __reuse_or_alloc_node_type& __roan,
const __node_type* __n)
1048 {
return __roan(__n->_M_v()); });
1052 template<
typename _Key,
typename _Value,
1053 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1054 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1056 template<
typename _Ht,
typename _NodeGenerator>
1058 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1059 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1060 _M_assign_elements(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1062 __bucket_type* __former_buckets =
nullptr;
1063 std::size_t __former_bucket_count = _M_bucket_count;
1064 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1066 if (_M_bucket_count != __ht._M_bucket_count)
1068 __former_buckets = _M_buckets;
1069 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1070 _M_bucket_count = __ht._M_bucket_count;
1073 __builtin_memset(_M_buckets, 0,
1074 _M_bucket_count *
sizeof(__bucket_type));
1078 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1079 _M_element_count = __ht._M_element_count;
1080 _M_rehash_policy = __ht._M_rehash_policy;
1081 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1082 _M_before_begin._M_nxt =
nullptr;
1084 [&__node_gen, &__roan](__node_type* __n)
1085 {
return __node_gen(__roan, __n); });
1086 if (__former_buckets)
1087 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1091 if (__former_buckets)
1094 _M_deallocate_buckets();
1095 _M_rehash_policy._M_reset(__former_state);
1096 _M_buckets = __former_buckets;
1097 _M_bucket_count = __former_bucket_count;
1099 __builtin_memset(_M_buckets, 0,
1100 _M_bucket_count *
sizeof(__bucket_type));
1101 __throw_exception_again;
1105 template<
typename _Key,
typename _Value,
1106 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1107 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1109 template<
typename _NodeGenerator>
1111 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1112 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1113 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
1115 __bucket_type* __buckets =
nullptr;
1117 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1121 if (!__ht._M_before_begin._M_nxt)
1126 __node_type* __ht_n = __ht._M_begin();
1127 __node_type* __this_n = __node_gen(__ht_n);
1128 this->_M_copy_code(__this_n, __ht_n);
1129 _M_before_begin._M_nxt = __this_n;
1130 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1133 __node_base* __prev_n = __this_n;
1134 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1136 __this_n = __node_gen(__ht_n);
1137 __prev_n->_M_nxt = __this_n;
1138 this->_M_copy_code(__this_n, __ht_n);
1139 size_type __bkt = _M_bucket_index(__this_n);
1140 if (!_M_buckets[__bkt])
1141 _M_buckets[__bkt] = __prev_n;
1142 __prev_n = __this_n;
1149 _M_deallocate_buckets();
1150 __throw_exception_again;
1154 template<
typename _Key,
typename _Value,
1155 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1156 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1159 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1160 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1163 _M_rehash_policy._M_reset();
1164 _M_bucket_count = 1;
1165 _M_single_bucket =
nullptr;
1166 _M_buckets = &_M_single_bucket;
1167 _M_before_begin._M_nxt =
nullptr;
1168 _M_element_count = 0;
1171 template<
typename _Key,
typename _Value,
1172 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1173 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1176 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1177 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1180 this->_M_deallocate_nodes(_M_begin());
1181 _M_deallocate_buckets();
1182 __hashtable_base::operator=(std::move(__ht));
1183 _M_rehash_policy = __ht._M_rehash_policy;
1184 if (!__ht._M_uses_single_bucket())
1185 _M_buckets = __ht._M_buckets;
1188 _M_buckets = &_M_single_bucket;
1189 _M_single_bucket = __ht._M_single_bucket;
1191 _M_bucket_count = __ht._M_bucket_count;
1192 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1193 _M_element_count = __ht._M_element_count;
1194 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1199 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1203 template<
typename _Key,
typename _Value,
1204 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1205 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1208 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1209 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1212 if (__ht._M_node_allocator() == this->_M_node_allocator())
1217 _M_assign_elements(std::move(__ht),
1218 [](
const __reuse_or_alloc_node_type& __roan, __node_type* __n)
1224 template<
typename _Key,
typename _Value,
1225 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1226 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1228 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1229 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1230 _Hashtable(
const _Hashtable& __ht)
1231 : __hashtable_base(__ht),
1233 __rehash_base(__ht),
1235 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1236 _M_buckets(nullptr),
1237 _M_bucket_count(__ht._M_bucket_count),
1238 _M_element_count(__ht._M_element_count),
1239 _M_rehash_policy(__ht._M_rehash_policy)
1242 [
this](
const __node_type* __n)
1243 {
return this->_M_allocate_node(__n->_M_v()); });
1246 template<
typename _Key,
typename _Value,
1247 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1248 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1250 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1251 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1252 _Hashtable(_Hashtable&& __ht) noexcept
1253 : __hashtable_base(__ht),
1255 __rehash_base(__ht),
1256 __hashtable_alloc(std::move(__ht._M_base_alloc())),
1257 _M_buckets(__ht._M_buckets),
1258 _M_bucket_count(__ht._M_bucket_count),
1259 _M_before_begin(__ht._M_before_begin._M_nxt),
1260 _M_element_count(__ht._M_element_count),
1261 _M_rehash_policy(__ht._M_rehash_policy)
1264 if (__ht._M_uses_single_bucket())
1266 _M_buckets = &_M_single_bucket;
1267 _M_single_bucket = __ht._M_single_bucket;
1273 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1278 template<
typename _Key,
typename _Value,
1279 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1280 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1282 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1283 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1284 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1285 : __hashtable_base(__ht),
1287 __rehash_base(__ht),
1288 __hashtable_alloc(__node_alloc_type(__a)),
1290 _M_bucket_count(__ht._M_bucket_count),
1291 _M_element_count(__ht._M_element_count),
1292 _M_rehash_policy(__ht._M_rehash_policy)
1295 [
this](
const __node_type* __n)
1296 {
return this->_M_allocate_node(__n->_M_v()); });
1299 template<
typename _Key,
typename _Value,
1300 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1301 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1303 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1304 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1305 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
1306 : __hashtable_base(__ht),
1308 __rehash_base(__ht),
1309 __hashtable_alloc(__node_alloc_type(__a)),
1310 _M_buckets(nullptr),
1311 _M_bucket_count(__ht._M_bucket_count),
1312 _M_element_count(__ht._M_element_count),
1313 _M_rehash_policy(__ht._M_rehash_policy)
1315 if (__ht._M_node_allocator() == this->_M_node_allocator())
1317 if (__ht._M_uses_single_bucket())
1319 _M_buckets = &_M_single_bucket;
1320 _M_single_bucket = __ht._M_single_bucket;
1323 _M_buckets = __ht._M_buckets;
1325 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1329 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1335 [
this](__node_type* __n)
1337 return this->_M_allocate_node(
1344 template<
typename _Key,
typename _Value,
1345 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1346 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1348 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1349 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1350 ~_Hashtable() noexcept
1353 _M_deallocate_buckets();
1355 static_assert(__is_invocable<const _H1&, const _Key&>{},
1356 "hash function must be invocable with an argument of key type");
1357 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1358 "key equality predicate must be invocable with two arguments of " 1362 template<
typename _Key,
typename _Value,
1363 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1364 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1367 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1368 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1369 swap(_Hashtable& __x)
1370 noexcept(__and_<__is_nothrow_swappable<_H1>,
1371 __is_nothrow_swappable<_Equal>>::value)
1378 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1379 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1382 if (this->_M_uses_single_bucket())
1384 if (!__x._M_uses_single_bucket())
1386 _M_buckets = __x._M_buckets;
1387 __x._M_buckets = &__x._M_single_bucket;
1390 else if (__x._M_uses_single_bucket())
1392 __x._M_buckets = _M_buckets;
1393 _M_buckets = &_M_single_bucket;
1396 std::swap(_M_buckets, __x._M_buckets);
1398 std::swap(_M_bucket_count, __x._M_bucket_count);
1399 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1400 std::swap(_M_element_count, __x._M_element_count);
1401 std::swap(_M_single_bucket, __x._M_single_bucket);
1406 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1409 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1410 = &__x._M_before_begin;
1413 template<
typename _Key,
typename _Value,
1414 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1415 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1418 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1419 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1420 find(
const key_type& __k)
1423 __hash_code __code = this->_M_hash_code(__k);
1424 std::size_t __n = _M_bucket_index(__k, __code);
1425 __node_type* __p = _M_find_node(__n, __k, __code);
1426 return __p ? iterator(__p) :
end();
1429 template<
typename _Key,
typename _Value,
1430 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1431 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1434 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1435 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1436 find(
const key_type& __k)
const 1439 __hash_code __code = this->_M_hash_code(__k);
1440 std::size_t __n = _M_bucket_index(__k, __code);
1441 __node_type* __p = _M_find_node(__n, __k, __code);
1442 return __p ? const_iterator(__p) :
end();
1445 template<
typename _Key,
typename _Value,
1446 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1447 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1450 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1451 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1452 count(
const key_type& __k)
const 1455 __hash_code __code = this->_M_hash_code(__k);
1456 std::size_t __n = _M_bucket_index(__k, __code);
1457 __node_type* __p = _M_bucket_begin(__n);
1461 std::size_t __result = 0;
1462 for (;; __p = __p->_M_next())
1464 if (this->_M_equals(__k, __code, __p))
1471 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1477 template<
typename _Key,
typename _Value,
1478 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1479 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1482 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1483 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1484 equal_range(
const key_type& __k)
1485 -> pair<iterator, iterator>
1487 __hash_code __code = this->_M_hash_code(__k);
1488 std::size_t __n = _M_bucket_index(__k, __code);
1489 __node_type* __p = _M_find_node(__n, __k, __code);
1493 __node_type* __p1 = __p->_M_next();
1494 while (__p1 && _M_bucket_index(__p1) == __n
1495 && this->_M_equals(__k, __code, __p1))
1496 __p1 = __p1->_M_next();
1504 template<
typename _Key,
typename _Value,
1505 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1506 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1509 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1510 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1511 equal_range(
const key_type& __k)
const 1512 -> pair<const_iterator, const_iterator>
1514 __hash_code __code = this->_M_hash_code(__k);
1515 std::size_t __n = _M_bucket_index(__k, __code);
1516 __node_type* __p = _M_find_node(__n, __k, __code);
1520 __node_type* __p1 = __p->_M_next();
1521 while (__p1 && _M_bucket_index(__p1) == __n
1522 && this->_M_equals(__k, __code, __p1))
1523 __p1 = __p1->_M_next();
1525 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1533 template<
typename _Key,
typename _Value,
1534 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1535 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1538 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1539 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1540 _M_find_before_node(size_type __n,
const key_type& __k,
1541 __hash_code __code)
const 1544 __node_base* __prev_p = _M_buckets[__n];
1548 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1549 __p = __p->_M_next())
1551 if (this->_M_equals(__k, __code, __p))
1554 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1561 template<
typename _Key,
typename _Value,
1562 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1563 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1566 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1567 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1568 _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
1570 if (_M_buckets[__bkt])
1574 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1575 _M_buckets[__bkt]->_M_nxt = __node;
1582 __node->_M_nxt = _M_before_begin._M_nxt;
1583 _M_before_begin._M_nxt = __node;
1587 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1588 _M_buckets[__bkt] = &_M_before_begin;
1592 template<
typename _Key,
typename _Value,
1593 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1594 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1597 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1598 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1599 _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
1600 size_type __next_bkt)
1602 if (!__next || __next_bkt != __bkt)
1607 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1610 if (&_M_before_begin == _M_buckets[__bkt])
1611 _M_before_begin._M_nxt = __next;
1612 _M_buckets[__bkt] =
nullptr;
1616 template<
typename _Key,
typename _Value,
1617 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1618 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1621 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1622 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1623 _M_get_previous_node(size_type __bkt, __node_base* __n)
1626 __node_base* __prev_n = _M_buckets[__bkt];
1627 while (__prev_n->_M_nxt != __n)
1628 __prev_n = __prev_n->_M_nxt;
1632 template<
typename _Key,
typename _Value,
1633 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1634 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1636 template<
typename... _Args>
1638 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1639 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1641 -> pair<iterator, bool>
1644 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1645 const key_type& __k = this->_M_extract()(__node->_M_v());
1649 __code = this->_M_hash_code(__k);
1653 this->_M_deallocate_node(__node);
1654 __throw_exception_again;
1657 size_type __bkt = _M_bucket_index(__k, __code);
1658 if (__node_type* __p = _M_find_node(__bkt, __k, __code))
1661 this->_M_deallocate_node(__node);
1666 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1670 template<
typename _Key,
typename _Value,
1671 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1672 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1674 template<
typename... _Args>
1676 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1677 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1682 __node_type* __node =
1683 this->_M_allocate_node(std::forward<_Args>(__args)...);
1688 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1692 this->_M_deallocate_node(__node);
1693 __throw_exception_again;
1696 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1699 template<
typename _Key,
typename _Value,
1700 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1701 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1704 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1705 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1706 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1707 __node_type* __node, size_type __n_elt)
1710 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1712 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1717 if (__do_rehash.
first)
1719 _M_rehash(__do_rehash.
second, __saved_state);
1720 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1723 this->_M_store_code(__node, __code);
1726 _M_insert_bucket_begin(__bkt, __node);
1728 return iterator(__node);
1732 this->_M_deallocate_node(__node);
1733 __throw_exception_again;
1739 template<
typename _Key,
typename _Value,
1740 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1741 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1744 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1745 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1746 _M_insert_multi_node(__node_type* __hint, __hash_code __code,
1747 __node_type* __node)
1750 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1752 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1756 if (__do_rehash.
first)
1757 _M_rehash(__do_rehash.
second, __saved_state);
1759 this->_M_store_code(__node, __code);
1760 const key_type& __k = this->_M_extract()(__node->_M_v());
1761 size_type __bkt = _M_bucket_index(__k, __code);
1766 = __builtin_expect(__hint !=
nullptr,
false)
1767 && this->_M_equals(__k, __code, __hint)
1769 : _M_find_before_node(__bkt, __k, __code);
1773 __node->_M_nxt = __prev->_M_nxt;
1774 __prev->_M_nxt = __node;
1775 if (__builtin_expect(__prev == __hint,
false))
1779 && !this->_M_equals(__k, __code, __node->_M_next()))
1781 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1782 if (__next_bkt != __bkt)
1783 _M_buckets[__next_bkt] = __node;
1791 _M_insert_bucket_begin(__bkt, __node);
1793 return iterator(__node);
1797 this->_M_deallocate_node(__node);
1798 __throw_exception_again;
1803 template<
typename _Key,
typename _Value,
1804 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1805 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1807 template<
typename _Arg,
typename _NodeGenerator>
1809 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1810 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1811 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
true_type,
1813 -> pair<iterator, bool>
1815 const key_type& __k = this->_M_extract()(__v);
1816 __hash_code __code = this->_M_hash_code(__k);
1817 size_type __bkt = _M_bucket_index(__k, __code);
1819 __node_type* __n = _M_find_node(__bkt, __k, __code);
1823 __n = __node_gen(std::forward<_Arg>(__v));
1824 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt),
true };
1828 template<
typename _Key,
typename _Value,
1829 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1830 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1832 template<
typename _Arg,
typename _NodeGenerator>
1834 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1835 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1836 _M_insert(const_iterator __hint, _Arg&& __v,
1837 const _NodeGenerator& __node_gen,
false_type)
1842 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1845 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1847 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1850 template<
typename _Key,
typename _Value,
1851 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1852 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1855 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1856 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1857 erase(const_iterator __it)
1860 __node_type* __n = __it._M_cur;
1861 std::size_t __bkt = _M_bucket_index(__n);
1866 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1867 return _M_erase(__bkt, __prev_n, __n);
1870 template<
typename _Key,
typename _Value,
1871 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1872 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1875 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1876 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1877 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
1880 if (__prev_n == _M_buckets[__bkt])
1881 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1882 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1883 else if (__n->_M_nxt)
1885 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1886 if (__next_bkt != __bkt)
1887 _M_buckets[__next_bkt] = __prev_n;
1890 __prev_n->_M_nxt = __n->_M_nxt;
1891 iterator __result(__n->_M_next());
1892 this->_M_deallocate_node(__n);
1898 template<
typename _Key,
typename _Value,
1899 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1900 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1903 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1904 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1908 __hash_code __code = this->_M_hash_code(__k);
1909 std::size_t __bkt = _M_bucket_index(__k, __code);
1912 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1917 __node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);
1918 _M_erase(__bkt, __prev_n, __n);
1922 template<
typename _Key,
typename _Value,
1923 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1924 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1927 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1928 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1932 __hash_code __code = this->_M_hash_code(__k);
1933 std::size_t __bkt = _M_bucket_index(__k, __code);
1936 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1946 __node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);
1947 __node_type* __n_last = __n;
1948 std::size_t __n_last_bkt = __bkt;
1951 __n_last = __n_last->_M_next();
1954 __n_last_bkt = _M_bucket_index(__n_last);
1956 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1959 size_type __result = 0;
1962 __node_type* __p = __n->_M_next();
1963 this->_M_deallocate_node(__n);
1968 while (__n != __n_last);
1970 if (__prev_n == _M_buckets[__bkt])
1971 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1972 else if (__n_last && __n_last_bkt != __bkt)
1973 _M_buckets[__n_last_bkt] = __prev_n;
1974 __prev_n->_M_nxt = __n_last;
1978 template<
typename _Key,
typename _Value,
1979 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1980 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1983 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1984 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1985 erase(const_iterator __first, const_iterator __last)
1988 __node_type* __n = __first._M_cur;
1989 __node_type* __last_n = __last._M_cur;
1990 if (__n == __last_n)
1991 return iterator(__n);
1993 std::size_t __bkt = _M_bucket_index(__n);
1995 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1996 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1997 std::size_t __n_bkt = __bkt;
2002 __node_type* __tmp = __n;
2003 __n = __n->_M_next();
2004 this->_M_deallocate_node(__tmp);
2008 __n_bkt = _M_bucket_index(__n);
2010 while (__n != __last_n && __n_bkt == __bkt);
2011 if (__is_bucket_begin)
2012 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2013 if (__n == __last_n)
2015 __is_bucket_begin =
true;
2019 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2020 _M_buckets[__n_bkt] = __prev_n;
2021 __prev_n->_M_nxt = __n;
2022 return iterator(__n);
2025 template<
typename _Key,
typename _Value,
2026 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2027 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2030 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2031 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2034 this->_M_deallocate_nodes(_M_begin());
2035 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2036 _M_element_count = 0;
2037 _M_before_begin._M_nxt =
nullptr;
2040 template<
typename _Key,
typename _Value,
2041 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2042 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2045 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2046 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2047 rehash(size_type __n)
2049 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2050 std::size_t __buckets
2051 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2053 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2055 if (__buckets != _M_bucket_count)
2056 _M_rehash(__buckets, __saved_state);
2059 _M_rehash_policy._M_reset(__saved_state);
2062 template<
typename _Key,
typename _Value,
2063 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2064 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2067 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2068 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2069 _M_rehash(size_type __n,
const __rehash_state& __state)
2073 _M_rehash_aux(__n, __unique_keys());
2079 _M_rehash_policy._M_reset(__state);
2080 __throw_exception_again;
2085 template<
typename _Key,
typename _Value,
2086 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2087 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2090 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2091 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2094 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2095 __node_type* __p = _M_begin();
2096 _M_before_begin._M_nxt =
nullptr;
2097 std::size_t __bbegin_bkt = 0;
2100 __node_type* __next = __p->_M_next();
2101 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2102 if (!__new_buckets[__bkt])
2104 __p->_M_nxt = _M_before_begin._M_nxt;
2105 _M_before_begin._M_nxt = __p;
2106 __new_buckets[__bkt] = &_M_before_begin;
2108 __new_buckets[__bbegin_bkt] = __p;
2109 __bbegin_bkt = __bkt;
2113 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2114 __new_buckets[__bkt]->_M_nxt = __p;
2119 _M_deallocate_buckets();
2120 _M_bucket_count = __n;
2121 _M_buckets = __new_buckets;
2126 template<
typename _Key,
typename _Value,
2127 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2128 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2131 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2132 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2135 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2137 __node_type* __p = _M_begin();
2138 _M_before_begin._M_nxt =
nullptr;
2139 std::size_t __bbegin_bkt = 0;
2140 std::size_t __prev_bkt = 0;
2141 __node_type* __prev_p =
nullptr;
2142 bool __check_bucket =
false;
2146 __node_type* __next = __p->_M_next();
2147 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2149 if (__prev_p && __prev_bkt == __bkt)
2154 __p->_M_nxt = __prev_p->_M_nxt;
2155 __prev_p->_M_nxt = __p;
2162 __check_bucket =
true;
2170 if (__prev_p->_M_nxt)
2172 std::size_t __next_bkt
2173 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2175 if (__next_bkt != __prev_bkt)
2176 __new_buckets[__next_bkt] = __prev_p;
2178 __check_bucket =
false;
2181 if (!__new_buckets[__bkt])
2183 __p->_M_nxt = _M_before_begin._M_nxt;
2184 _M_before_begin._M_nxt = __p;
2185 __new_buckets[__bkt] = &_M_before_begin;
2187 __new_buckets[__bbegin_bkt] = __p;
2188 __bbegin_bkt = __bkt;
2192 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2193 __new_buckets[__bkt]->_M_nxt = __p;
2201 if (__check_bucket && __prev_p->_M_nxt)
2203 std::size_t __next_bkt
2204 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2205 if (__next_bkt != __prev_bkt)
2206 __new_buckets[__next_bkt] = __prev_p;
2209 _M_deallocate_buckets();
2210 _M_bucket_count = __n;
2211 _M_buckets = __new_buckets;
2214 #if __cplusplus > 201402L 2215 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2218 #if __cpp_deduction_guides >= 201606 2220 template<
typename _Hash>
2221 using _RequireNotAllocatorOrIntegral
2222 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2225 _GLIBCXX_END_NAMESPACE_VERSION
2228 #endif // _HASHTABLE_H
Node const_iterators, used to iterate through all the hashtable.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
_T2 second
first is a copy of the first object
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.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Define a member typedef type to one of two argument types.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_Tp exchange(_Tp &__obj, _Up &&__new_val)
Assign __new_val to __obj and return its previous value.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
is_nothrow_move_assignable
Uniform interface to C++98 and C++11 allocators.
_T1 first
second_type is the second bound type
constexpr conditional< __move_if_noexcept_cond< _Tp >::value, const _Tp &, _Tp && >::type move_if_noexcept(_Tp &__x) noexcept
Conditionally convert a value to an rvalue.
Struct holding two objects of arbitrary type.
Node iterators, used to iterate through all the hashtable.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
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.