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 __detail::__is_noexcept_hash<_Tp, _Hash>>>;
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 using __traits_type = _Traits;
190 using __hash_cached =
typename __traits_type::__hash_cached;
192 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
196 using __value_alloc_traits =
198 using __node_alloc_traits =
204 typedef _Key key_type;
205 typedef _Value value_type;
206 typedef _Alloc allocator_type;
207 typedef _Equal key_equal;
211 typedef typename __value_alloc_traits::pointer pointer;
212 typedef typename __value_alloc_traits::const_pointer const_pointer;
213 typedef value_type& reference;
214 typedef const value_type& const_reference;
217 using __rehash_type = _RehashPolicy;
218 using __rehash_state =
typename __rehash_type::_State;
220 using __constant_iterators =
typename __traits_type::__constant_iterators;
221 using __unique_keys =
typename __traits_type::__unique_keys;
223 using __key_extract =
typename std::conditional<
224 __constant_iterators::value,
226 __detail::_Select1st>::type;
229 _Hashtable_base<_Key, _Value, _ExtractKey,
230 _Equal, _H1, _H2, _Hash, _Traits>;
233 using __hash_code =
typename __hashtable_base::__hash_code;
234 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
237 _Equal, _H1, _H2, _Hash,
238 _RehashPolicy, _Traits>;
243 _RehashPolicy, _Traits>;
246 _Equal, _H1, _H2, _Hash,
247 _RehashPolicy, _Traits>;
249 using __reuse_or_alloc_node_type =
250 __detail::_ReuseOrAllocNode<__node_alloc_type>;
253 template<
typename _Cond>
254 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
256 template<
typename _Cond>
257 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
263 struct __hash_code_base_access : __hash_code_base
264 {
using __hash_code_base::_M_bucket_index; };
268 static_assert(noexcept(declval<const __hash_code_base_access&>()
271 "Cache the hash code or qualify your functors involved" 272 " in hash code and bucket index computation with noexcept");
279 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
280 "Functor used to map hash code to bucket index" 281 " must be default constructible");
283 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
284 typename _ExtractKeya,
typename _Equala,
285 typename _H1a,
typename _H2a,
typename _Hasha,
286 typename _RehashPolicya,
typename _Traitsa,
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>
296 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
297 typename _ExtractKeya,
typename _Equala,
298 typename _H1a,
typename _H2a,
typename _Hasha,
299 typename _RehashPolicya,
typename _Traitsa,
300 bool _Constant_iteratorsa>
304 using size_type =
typename __hashtable_base::size_type;
305 using difference_type =
typename __hashtable_base::difference_type;
311 using const_local_iterator =
typename __hashtable_base::
312 const_local_iterator;
314 #if __cplusplus > 201402L 315 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
316 using insert_return_type = _Node_insert_return<iterator, node_type>;
320 __bucket_type* _M_buckets = &_M_single_bucket;
321 size_type _M_bucket_count = 1;
322 __node_base _M_before_begin;
323 size_type _M_element_count = 0;
324 _RehashPolicy _M_rehash_policy;
332 __bucket_type _M_single_bucket =
nullptr;
335 _M_uses_single_bucket(__bucket_type* __bkts)
const 336 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
339 _M_uses_single_bucket()
const 340 {
return _M_uses_single_bucket(_M_buckets); }
343 _M_base_alloc() {
return *
this; }
346 _M_allocate_buckets(size_type __n)
348 if (__builtin_expect(__n == 1,
false))
350 _M_single_bucket =
nullptr;
351 return &_M_single_bucket;
354 return __hashtable_alloc::_M_allocate_buckets(__n);
358 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
360 if (_M_uses_single_bucket(__bkts))
363 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
367 _M_deallocate_buckets()
368 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
373 _M_bucket_begin(size_type __bkt)
const;
377 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
379 template<
typename _NodeGenerator>
381 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
392 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
393 const _Equal& __eq,
const _ExtractKey& __exk,
394 const allocator_type& __a)
403 const _H1&,
const _H2&,
const _Hash&,
404 const _Equal&,
const _ExtractKey&,
405 const allocator_type&);
407 template<
typename _InputIterator>
408 _Hashtable(_InputIterator __first, _InputIterator __last,
409 size_type __bucket_hint,
410 const _H1&,
const _H2&,
const _Hash&,
411 const _Equal&,
const _ExtractKey&,
412 const allocator_type&);
430 const _H1& __hf = _H1(),
431 const key_equal& __eql = key_equal(),
432 const allocator_type& __a = allocator_type())
433 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
434 __key_extract(), __a)
437 template<
typename _InputIterator>
438 _Hashtable(_InputIterator __f, _InputIterator __l,
440 const _H1& __hf = _H1(),
441 const key_equal& __eql = key_equal(),
442 const allocator_type& __a = allocator_type())
443 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
444 __key_extract(), __a)
449 const _H1& __hf = _H1(),
450 const key_equal& __eql = key_equal(),
451 const allocator_type& __a = allocator_type())
452 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
453 __key_extract(), __a)
461 noexcept(__node_alloc_traits::_S_nothrow_move()
462 && is_nothrow_move_assignable<_H1>::value
463 && is_nothrow_move_assignable<_Equal>::value)
465 constexpr
bool __move_storage =
466 __node_alloc_traits::_S_propagate_on_move_assign()
467 || __node_alloc_traits::_S_always_equal();
475 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
476 _M_before_begin._M_nxt =
nullptr;
478 this->_M_insert_range(__l.begin(), __l.end(), __roan);
486 noexcept(__and_<__is_nothrow_swappable<_H1>,
487 __is_nothrow_swappable<_Equal>>::value);
492 {
return iterator(_M_begin()); }
495 begin()
const noexcept
496 {
return const_iterator(_M_begin()); }
500 {
return iterator(
nullptr); }
504 {
return const_iterator(
nullptr); }
508 {
return const_iterator(_M_begin()); }
511 cend()
const noexcept
512 {
return const_iterator(
nullptr); }
515 size()
const noexcept
516 {
return _M_element_count; }
519 empty()
const noexcept
520 {
return size() == 0; }
523 get_allocator()
const noexcept
524 {
return allocator_type(this->_M_node_allocator()); }
527 max_size()
const noexcept
528 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
533 {
return this->_M_eq(); }
539 bucket_count()
const noexcept
540 {
return _M_bucket_count; }
543 max_bucket_count()
const noexcept
544 {
return max_size(); }
547 bucket_size(size_type __n)
const 551 bucket(
const key_type& __k)
const 552 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
557 return local_iterator(*
this, _M_bucket_begin(__n),
558 __n, _M_bucket_count);
563 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
566 begin(size_type __n)
const 568 return const_local_iterator(*
this, _M_bucket_begin(__n),
569 __n, _M_bucket_count);
573 end(size_type __n)
const 574 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
578 cbegin(size_type __n)
const 580 return const_local_iterator(*
this, _M_bucket_begin(__n),
581 __n, _M_bucket_count);
585 cend(size_type __n)
const 586 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
589 load_factor()
const noexcept
591 return static_cast<float>(size()) / static_cast<float>(bucket_count());
600 __rehash_policy()
const 601 {
return _M_rehash_policy; }
604 __rehash_policy(
const _RehashPolicy& __pol)
605 { _M_rehash_policy = __pol; }
609 find(
const key_type& __k);
612 find(
const key_type& __k)
const;
615 count(
const key_type& __k)
const;
618 equal_range(
const key_type& __k);
621 equal_range(
const key_type& __k)
const;
627 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
630 _M_bucket_index(
const key_type& __k, __hash_code __c)
const 631 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
636 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
639 _M_find_node(size_type __bkt,
const key_type& __key,
640 __hash_code __c)
const 642 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
644 return static_cast<__node_type*
>(__before_n->_M_nxt);
654 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
655 size_type __next_bkt);
659 _M_get_previous_node(size_type __bkt, __node_base* __n);
665 _M_insert_unique_node(size_type __bkt, __hash_code __code,
674 template<
typename... _Args>
678 template<
typename... _Args>
681 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
684 template<
typename... _Args>
686 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
687 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
689 template<
typename... _Args>
693 template<
typename _Arg,
typename _NodeGenerator>
697 template<
typename _Arg,
typename _NodeGenerator>
699 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
702 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
707 template<
typename _Arg,
typename _NodeGenerator>
709 _M_insert(const_iterator, _Arg&& __arg,
713 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
717 template<
typename _Arg,
typename _NodeGenerator>
719 _M_insert(const_iterator, _Arg&&,
729 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
733 template<
typename... _Args>
735 emplace(_Args&&... __args)
736 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
738 template<
typename... _Args>
740 emplace_hint(const_iterator __hint, _Args&&... __args)
742 return _M_emplace(__hint, __unique_keys(),
743 std::forward<_Args>(__args)...);
750 erase(const_iterator);
755 {
return erase(const_iterator(__it)); }
758 erase(
const key_type& __k)
759 {
return _M_erase(__unique_keys(), __k); }
762 erase(const_iterator, const_iterator);
768 void rehash(size_type __n);
773 #if __cplusplus > 201402L 776 _M_reinsert_node(node_type&& __nh)
778 insert_return_type __ret;
780 __ret.position =
end();
783 __glibcxx_assert(get_allocator() == __nh.get_allocator());
785 const key_type& __k = __nh._M_key();
786 __hash_code __code = this->_M_hash_code(__k);
787 size_type __bkt = _M_bucket_index(__k, __code);
788 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
790 __ret.node = std::move(__nh);
791 __ret.position = iterator(__n);
792 __ret.inserted =
false;
797 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
798 __nh._M_ptr =
nullptr;
799 __ret.inserted =
true;
807 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
814 __glibcxx_assert(get_allocator() == __nh.get_allocator());
816 auto __code = this->_M_hash_code(__nh._M_key());
819 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
826 extract(const_iterator __pos)
829 size_t __bkt = _M_bucket_index(__n);
834 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
836 if (__prev_n == _M_buckets[__bkt])
837 _M_remove_bucket_begin(__bkt, __n->_M_next(),
838 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
839 else if (__n->_M_nxt)
841 size_type __next_bkt = _M_bucket_index(__n->_M_next());
842 if (__next_bkt != __bkt)
843 _M_buckets[__next_bkt] = __prev_n;
846 __prev_n->_M_nxt = __n->_M_nxt;
847 __n->_M_nxt =
nullptr;
849 return { __n, this->_M_node_allocator() };
854 extract(
const _Key& __k)
857 auto __pos = find(__k);
859 __nh = extract(const_iterator(__pos));
864 template<
typename _Compatible_Hashtable>
866 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
868 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
869 node_type>,
"Node types are compatible");
870 __glibcxx_assert(get_allocator() == __src.get_allocator());
872 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
875 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
876 __hash_code __code = this->_M_hash_code(__k);
877 size_type __bkt = _M_bucket_index(__k, __code);
878 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
880 auto __nh = __src.extract(__pos);
881 _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
882 __nh._M_ptr =
nullptr;
888 template<
typename _Compatible_Hashtable>
890 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
892 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
893 node_type>,
"Node types are compatible");
894 __glibcxx_assert(get_allocator() == __src.get_allocator());
896 this->reserve(size() + __src.size());
897 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
898 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
911 void _M_rehash(size_type __n,
const __rehash_state& __state);
916 template<
typename _Key,
typename _Value,
917 typename _Alloc,
typename _ExtractKey,
typename _Equal,
918 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
921 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
922 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
923 _M_bucket_begin(size_type __bkt)
const 926 __node_base* __n = _M_buckets[__bkt];
927 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
930 template<
typename _Key,
typename _Value,
931 typename _Alloc,
typename _ExtractKey,
typename _Equal,
932 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
934 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
935 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
936 _Hashtable(size_type __bucket_hint,
937 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
938 const _Equal& __eq,
const _ExtractKey& __exk,
939 const allocator_type& __a)
940 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
942 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
943 if (__bkt > _M_bucket_count)
945 _M_buckets = _M_allocate_buckets(__bkt);
946 _M_bucket_count = __bkt;
950 template<
typename _Key,
typename _Value,
951 typename _Alloc,
typename _ExtractKey,
typename _Equal,
952 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
954 template<
typename _InputIterator>
955 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
956 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
957 _Hashtable(_InputIterator __f, _InputIterator __l,
958 size_type __bucket_hint,
959 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
960 const _Equal& __eq,
const _ExtractKey& __exk,
961 const allocator_type& __a)
962 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
964 auto __nb_elems = __detail::__distance_fw(__f, __l);
966 _M_rehash_policy._M_next_bkt(
967 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
970 if (__bkt_count > _M_bucket_count)
972 _M_buckets = _M_allocate_buckets(__bkt_count);
973 _M_bucket_count = __bkt_count;
976 for (; __f != __l; ++__f)
980 template<
typename _Key,
typename _Value,
981 typename _Alloc,
typename _ExtractKey,
typename _Equal,
982 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
985 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
986 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
993 if (__node_alloc_traits::_S_propagate_on_copy_assign())
995 auto& __this_alloc = this->_M_node_allocator();
996 auto& __that_alloc = __ht._M_node_allocator();
997 if (!__node_alloc_traits::_S_always_equal()
998 && __this_alloc != __that_alloc)
1001 this->_M_deallocate_nodes(_M_begin());
1002 _M_before_begin._M_nxt =
nullptr;
1003 _M_deallocate_buckets();
1004 _M_buckets =
nullptr;
1005 std::__alloc_on_copy(__this_alloc, __that_alloc);
1006 __hashtable_base::operator=(__ht);
1007 _M_bucket_count = __ht._M_bucket_count;
1008 _M_element_count = __ht._M_element_count;
1009 _M_rehash_policy = __ht._M_rehash_policy;
1014 {
return this->_M_allocate_node(__n->_M_v()); });
1021 __throw_exception_again;
1025 std::__alloc_on_copy(__this_alloc, __that_alloc);
1029 __bucket_type* __former_buckets =
nullptr;
1030 std::size_t __former_bucket_count = _M_bucket_count;
1031 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1033 if (_M_bucket_count != __ht._M_bucket_count)
1035 __former_buckets = _M_buckets;
1036 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1037 _M_bucket_count = __ht._M_bucket_count;
1040 __builtin_memset(_M_buckets, 0,
1041 _M_bucket_count *
sizeof(__bucket_type));
1045 __hashtable_base::operator=(__ht);
1046 _M_element_count = __ht._M_element_count;
1047 _M_rehash_policy = __ht._M_rehash_policy;
1048 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1049 _M_before_begin._M_nxt =
nullptr;
1052 {
return __roan(__n->_M_v()); });
1053 if (__former_buckets)
1054 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1058 if (__former_buckets)
1061 _M_deallocate_buckets();
1062 _M_rehash_policy._M_reset(__former_state);
1063 _M_buckets = __former_buckets;
1064 _M_bucket_count = __former_bucket_count;
1066 __builtin_memset(_M_buckets, 0,
1067 _M_bucket_count *
sizeof(__bucket_type));
1068 __throw_exception_again;
1073 template<
typename _Key,
typename _Value,
1074 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1075 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1077 template<
typename _NodeGenerator>
1079 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1080 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1081 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
1083 __bucket_type* __buckets =
nullptr;
1085 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1089 if (!__ht._M_before_begin._M_nxt)
1096 this->_M_copy_code(__this_n, __ht_n);
1097 _M_before_begin._M_nxt = __this_n;
1098 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1101 __node_base* __prev_n = __this_n;
1102 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1104 __this_n = __node_gen(__ht_n);
1105 __prev_n->_M_nxt = __this_n;
1106 this->_M_copy_code(__this_n, __ht_n);
1107 size_type __bkt = _M_bucket_index(__this_n);
1108 if (!_M_buckets[__bkt])
1109 _M_buckets[__bkt] = __prev_n;
1110 __prev_n = __this_n;
1117 _M_deallocate_buckets();
1118 __throw_exception_again;
1122 template<
typename _Key,
typename _Value,
1123 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1124 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1127 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1128 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1131 _M_rehash_policy._M_reset();
1132 _M_bucket_count = 1;
1133 _M_single_bucket =
nullptr;
1134 _M_buckets = &_M_single_bucket;
1135 _M_before_begin._M_nxt =
nullptr;
1136 _M_element_count = 0;
1139 template<
typename _Key,
typename _Value,
1140 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1141 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1144 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1145 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1148 this->_M_deallocate_nodes(_M_begin());
1149 _M_deallocate_buckets();
1150 __hashtable_base::operator=(std::move(__ht));
1151 _M_rehash_policy = __ht._M_rehash_policy;
1152 if (!__ht._M_uses_single_bucket())
1153 _M_buckets = __ht._M_buckets;
1156 _M_buckets = &_M_single_bucket;
1157 _M_single_bucket = __ht._M_single_bucket;
1159 _M_bucket_count = __ht._M_bucket_count;
1160 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1161 _M_element_count = __ht._M_element_count;
1162 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1167 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
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 if (__ht._M_node_allocator() == this->_M_node_allocator())
1185 __bucket_type* __former_buckets =
nullptr;
1186 size_type __former_bucket_count = _M_bucket_count;
1187 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1189 if (_M_bucket_count != __ht._M_bucket_count)
1191 __former_buckets = _M_buckets;
1192 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1193 _M_bucket_count = __ht._M_bucket_count;
1196 __builtin_memset(_M_buckets, 0,
1197 _M_bucket_count *
sizeof(__bucket_type));
1201 __hashtable_base::operator=(std::move(__ht));
1202 _M_element_count = __ht._M_element_count;
1203 _M_rehash_policy = __ht._M_rehash_policy;
1204 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1205 _M_before_begin._M_nxt =
nullptr;
1213 if (__former_buckets)
1215 _M_deallocate_buckets();
1216 _M_rehash_policy._M_reset(__former_state);
1217 _M_buckets = __former_buckets;
1218 _M_bucket_count = __former_bucket_count;
1220 __builtin_memset(_M_buckets, 0,
1221 _M_bucket_count *
sizeof(__bucket_type));
1222 __throw_exception_again;
1227 template<
typename _Key,
typename _Value,
1228 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1229 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1231 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1232 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1238 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1239 _M_buckets(
nullptr),
1240 _M_bucket_count(__ht._M_bucket_count),
1241 _M_element_count(__ht._M_element_count),
1242 _M_rehash_policy(__ht._M_rehash_policy)
1246 {
return this->_M_allocate_node(__n->_M_v()); });
1249 template<
typename _Key,
typename _Value,
1250 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1251 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1253 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1254 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1260 _M_buckets(__ht._M_buckets),
1261 _M_bucket_count(__ht._M_bucket_count),
1262 _M_before_begin(__ht._M_before_begin._M_nxt),
1263 _M_element_count(__ht._M_element_count),
1264 _M_rehash_policy(__ht._M_rehash_policy)
1267 if (__ht._M_uses_single_bucket())
1269 _M_buckets = &_M_single_bucket;
1270 _M_single_bucket = __ht._M_single_bucket;
1276 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1281 template<
typename _Key,
typename _Value,
1282 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1283 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1285 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1286 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1287 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1293 _M_bucket_count(__ht._M_bucket_count),
1294 _M_element_count(__ht._M_element_count),
1295 _M_rehash_policy(__ht._M_rehash_policy)
1299 {
return this->_M_allocate_node(__n->_M_v()); });
1302 template<
typename _Key,
typename _Value,
1303 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1304 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1306 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1307 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1308 _Hashtable(
_Hashtable&& __ht,
const allocator_type& __a)
1313 _M_buckets(
nullptr),
1314 _M_bucket_count(__ht._M_bucket_count),
1315 _M_element_count(__ht._M_element_count),
1316 _M_rehash_policy(__ht._M_rehash_policy)
1318 if (__ht._M_node_allocator() == this->_M_node_allocator())
1320 if (__ht._M_uses_single_bucket())
1322 _M_buckets = &_M_single_bucket;
1323 _M_single_bucket = __ht._M_single_bucket;
1326 _M_buckets = __ht._M_buckets;
1328 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1332 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1340 return this->_M_allocate_node(
1347 template<
typename _Key,
typename _Value,
1348 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1349 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1351 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1352 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1353 ~_Hashtable() noexcept
1356 _M_deallocate_buckets();
1359 template<
typename _Key,
typename _Value,
1360 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1361 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1364 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1365 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1367 noexcept(__and_<__is_nothrow_swappable<_H1>,
1368 __is_nothrow_swappable<_Equal>>::value)
1375 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1376 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1379 if (this->_M_uses_single_bucket())
1381 if (!__x._M_uses_single_bucket())
1383 _M_buckets = __x._M_buckets;
1384 __x._M_buckets = &__x._M_single_bucket;
1387 else if (__x._M_uses_single_bucket())
1389 __x._M_buckets = _M_buckets;
1390 _M_buckets = &_M_single_bucket;
1393 std::swap(_M_buckets, __x._M_buckets);
1395 std::swap(_M_bucket_count, __x._M_bucket_count);
1396 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1397 std::swap(_M_element_count, __x._M_element_count);
1398 std::swap(_M_single_bucket, __x._M_single_bucket);
1403 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1406 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1407 = &__x._M_before_begin;
1410 template<
typename _Key,
typename _Value,
1411 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1412 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1415 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1416 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1417 find(
const key_type& __k)
1420 __hash_code __code = this->_M_hash_code(__k);
1421 std::size_t __n = _M_bucket_index(__k, __code);
1422 __node_type* __p = _M_find_node(__n, __k, __code);
1423 return __p ? iterator(__p) :
end();
1426 template<
typename _Key,
typename _Value,
1427 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1428 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1431 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1432 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1433 find(
const key_type& __k)
const 1436 __hash_code __code = this->_M_hash_code(__k);
1437 std::size_t __n = _M_bucket_index(__k, __code);
1438 __node_type* __p = _M_find_node(__n, __k, __code);
1439 return __p ? const_iterator(__p) :
end();
1442 template<
typename _Key,
typename _Value,
1443 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1444 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1448 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1449 count(
const key_type& __k)
const 1452 __hash_code __code = this->_M_hash_code(__k);
1453 std::size_t __n = _M_bucket_index(__k, __code);
1458 std::size_t __result = 0;
1459 for (;; __p = __p->_M_next())
1461 if (this->_M_equals(__k, __code, __p))
1468 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1474 template<
typename _Key,
typename _Value,
1475 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1476 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1479 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1480 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1481 equal_range(
const key_type& __k)
1484 __hash_code __code = this->_M_hash_code(__k);
1485 std::size_t __n = _M_bucket_index(__k, __code);
1486 __node_type* __p = _M_find_node(__n, __k, __code);
1491 while (__p1 && _M_bucket_index(__p1) == __n
1492 && this->_M_equals(__k, __code, __p1))
1493 __p1 = __p1->_M_next();
1501 template<
typename _Key,
typename _Value,
1502 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1503 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1506 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1507 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1508 equal_range(
const key_type& __k)
const 1511 __hash_code __code = this->_M_hash_code(__k);
1512 std::size_t __n = _M_bucket_index(__k, __code);
1513 __node_type* __p = _M_find_node(__n, __k, __code);
1518 while (__p1 && _M_bucket_index(__p1) == __n
1519 && this->_M_equals(__k, __code, __p1))
1520 __p1 = __p1->_M_next();
1522 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1530 template<
typename _Key,
typename _Value,
1531 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1532 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1535 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1536 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1537 _M_find_before_node(size_type __n,
const key_type& __k,
1538 __hash_code __code)
const 1541 __node_base* __prev_p = _M_buckets[__n];
1545 for (
__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1546 __p = __p->_M_next())
1548 if (this->_M_equals(__k, __code, __p))
1551 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1558 template<
typename _Key,
typename _Value,
1559 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1560 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1563 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1564 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1565 _M_insert_bucket_begin(size_type __bkt,
__node_type* __node)
1567 if (_M_buckets[__bkt])
1571 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1572 _M_buckets[__bkt]->_M_nxt = __node;
1579 __node->_M_nxt = _M_before_begin._M_nxt;
1580 _M_before_begin._M_nxt = __node;
1584 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1585 _M_buckets[__bkt] = &_M_before_begin;
1589 template<
typename _Key,
typename _Value,
1590 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1591 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1594 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1595 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1596 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next,
1597 size_type __next_bkt)
1599 if (!__next || __next_bkt != __bkt)
1604 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1607 if (&_M_before_begin == _M_buckets[__bkt])
1608 _M_before_begin._M_nxt = __next;
1609 _M_buckets[__bkt] =
nullptr;
1613 template<
typename _Key,
typename _Value,
1614 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1615 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1618 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1619 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1620 _M_get_previous_node(size_type __bkt, __node_base* __n)
1623 __node_base* __prev_n = _M_buckets[__bkt];
1624 while (__prev_n->_M_nxt != __n)
1625 __prev_n = __prev_n->_M_nxt;
1629 template<
typename _Key,
typename _Value,
1630 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1631 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1633 template<
typename... _Args>
1635 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1636 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1641 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1642 const key_type& __k = this->_M_extract()(__node->_M_v());
1646 __code = this->_M_hash_code(__k);
1650 this->_M_deallocate_node(__node);
1651 __throw_exception_again;
1654 size_type __bkt = _M_bucket_index(__k, __code);
1655 if (
__node_type* __p = _M_find_node(__bkt, __k, __code))
1658 this->_M_deallocate_node(__node);
1663 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1667 template<
typename _Key,
typename _Value,
1668 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1669 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1671 template<
typename... _Args>
1673 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1674 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1680 this->_M_allocate_node(std::forward<_Args>(__args)...);
1685 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1689 this->_M_deallocate_node(__node);
1690 __throw_exception_again;
1693 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1696 template<
typename _Key,
typename _Value,
1697 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1698 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1701 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1702 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1703 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1707 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1709 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1713 if (__do_rehash.
first)
1715 _M_rehash(__do_rehash.
second, __saved_state);
1716 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1719 this->_M_store_code(__node, __code);
1722 _M_insert_bucket_begin(__bkt, __node);
1724 return iterator(__node);
1728 this->_M_deallocate_node(__node);
1729 __throw_exception_again;
1735 template<
typename _Key,
typename _Value,
1736 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1737 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1740 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1741 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1742 _M_insert_multi_node(
__node_type* __hint, __hash_code __code,
1746 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1748 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1752 if (__do_rehash.
first)
1753 _M_rehash(__do_rehash.
second, __saved_state);
1755 this->_M_store_code(__node, __code);
1756 const key_type& __k = this->_M_extract()(__node->_M_v());
1757 size_type __bkt = _M_bucket_index(__k, __code);
1762 = __builtin_expect(__hint !=
nullptr,
false)
1763 && this->_M_equals(__k, __code, __hint)
1765 : _M_find_before_node(__bkt, __k, __code);
1769 __node->_M_nxt = __prev->_M_nxt;
1770 __prev->_M_nxt = __node;
1771 if (__builtin_expect(__prev == __hint,
false))
1775 && !this->_M_equals(__k, __code, __node->_M_next()))
1777 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1778 if (__next_bkt != __bkt)
1779 _M_buckets[__next_bkt] = __node;
1787 _M_insert_bucket_begin(__bkt, __node);
1789 return iterator(__node);
1793 this->_M_deallocate_node(__node);
1794 __throw_exception_again;
1799 template<
typename _Key,
typename _Value,
1800 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1801 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1803 template<
typename _Arg,
typename _NodeGenerator>
1805 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1806 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1807 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
std::true_type)
1810 const key_type& __k = this->_M_extract()(__v);
1811 __hash_code __code = this->_M_hash_code(__k);
1812 size_type __bkt = _M_bucket_index(__k, __code);
1814 __node_type* __n = _M_find_node(__bkt, __k, __code);
1818 __n = __node_gen(std::forward<_Arg>(__v));
1819 return std::make_pair(_M_insert_unique_node(__bkt, __code, __n),
true);
1823 template<
typename _Key,
typename _Value,
1824 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1825 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1827 template<
typename _Arg,
typename _NodeGenerator>
1829 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1830 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1831 _M_insert(const_iterator __hint, _Arg&& __v,
1837 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1840 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1842 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1845 template<
typename _Key,
typename _Value,
1846 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1847 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1850 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1851 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1852 erase(const_iterator __it)
1856 std::size_t __bkt = _M_bucket_index(__n);
1861 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1862 return _M_erase(__bkt, __prev_n, __n);
1865 template<
typename _Key,
typename _Value,
1866 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1867 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1870 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1871 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1872 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n)
1875 if (__prev_n == _M_buckets[__bkt])
1876 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1877 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1878 else if (__n->_M_nxt)
1880 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1881 if (__next_bkt != __bkt)
1882 _M_buckets[__next_bkt] = __prev_n;
1885 __prev_n->_M_nxt = __n->_M_nxt;
1886 iterator __result(__n->_M_next());
1887 this->_M_deallocate_node(__n);
1893 template<
typename _Key,
typename _Value,
1894 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1895 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1898 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1899 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1903 __hash_code __code = this->_M_hash_code(__k);
1904 std::size_t __bkt = _M_bucket_index(__k, __code);
1907 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1913 _M_erase(__bkt, __prev_n, __n);
1917 template<
typename _Key,
typename _Value,
1918 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1919 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1922 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1923 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1927 __hash_code __code = this->_M_hash_code(__k);
1928 std::size_t __bkt = _M_bucket_index(__k, __code);
1931 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1943 std::size_t __n_last_bkt = __bkt;
1946 __n_last = __n_last->_M_next();
1949 __n_last_bkt = _M_bucket_index(__n_last);
1951 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1954 size_type __result = 0;
1958 this->_M_deallocate_node(__n);
1963 while (__n != __n_last);
1965 if (__prev_n == _M_buckets[__bkt])
1966 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1967 else if (__n_last && __n_last_bkt != __bkt)
1968 _M_buckets[__n_last_bkt] = __prev_n;
1969 __prev_n->_M_nxt = __n_last;
1973 template<
typename _Key,
typename _Value,
1974 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1975 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1978 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1979 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1980 erase(const_iterator __first, const_iterator __last)
1985 if (__n == __last_n)
1986 return iterator(__n);
1988 std::size_t __bkt = _M_bucket_index(__n);
1990 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1991 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1992 std::size_t __n_bkt = __bkt;
1998 __n = __n->_M_next();
1999 this->_M_deallocate_node(__tmp);
2003 __n_bkt = _M_bucket_index(__n);
2005 while (__n != __last_n && __n_bkt == __bkt);
2006 if (__is_bucket_begin)
2007 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2008 if (__n == __last_n)
2010 __is_bucket_begin =
true;
2014 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2015 _M_buckets[__n_bkt] = __prev_n;
2016 __prev_n->_M_nxt = __n;
2017 return iterator(__n);
2020 template<
typename _Key,
typename _Value,
2021 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2022 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2025 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2026 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2029 this->_M_deallocate_nodes(_M_begin());
2030 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2031 _M_element_count = 0;
2032 _M_before_begin._M_nxt =
nullptr;
2035 template<
typename _Key,
typename _Value,
2036 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2037 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2040 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2041 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2042 rehash(size_type __n)
2044 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2045 std::size_t __buckets
2046 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2048 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2050 if (__buckets != _M_bucket_count)
2051 _M_rehash(__buckets, __saved_state);
2054 _M_rehash_policy._M_reset(__saved_state);
2057 template<
typename _Key,
typename _Value,
2058 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2059 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2062 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2063 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2064 _M_rehash(size_type __n,
const __rehash_state& __state)
2068 _M_rehash_aux(__n, __unique_keys());
2074 _M_rehash_policy._M_reset(__state);
2075 __throw_exception_again;
2080 template<
typename _Key,
typename _Value,
2081 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2082 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2085 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2086 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2089 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2091 _M_before_begin._M_nxt =
nullptr;
2092 std::size_t __bbegin_bkt = 0;
2096 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2097 if (!__new_buckets[__bkt])
2099 __p->_M_nxt = _M_before_begin._M_nxt;
2100 _M_before_begin._M_nxt = __p;
2101 __new_buckets[__bkt] = &_M_before_begin;
2103 __new_buckets[__bbegin_bkt] = __p;
2104 __bbegin_bkt = __bkt;
2108 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2109 __new_buckets[__bkt]->_M_nxt = __p;
2114 _M_deallocate_buckets();
2115 _M_bucket_count = __n;
2116 _M_buckets = __new_buckets;
2121 template<
typename _Key,
typename _Value,
2122 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2123 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2126 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2127 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2130 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2133 _M_before_begin._M_nxt =
nullptr;
2134 std::size_t __bbegin_bkt = 0;
2135 std::size_t __prev_bkt = 0;
2137 bool __check_bucket =
false;
2142 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2144 if (__prev_p && __prev_bkt == __bkt)
2149 __p->_M_nxt = __prev_p->_M_nxt;
2150 __prev_p->_M_nxt = __p;
2157 __check_bucket =
true;
2165 if (__prev_p->_M_nxt)
2167 std::size_t __next_bkt
2168 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2170 if (__next_bkt != __prev_bkt)
2171 __new_buckets[__next_bkt] = __prev_p;
2173 __check_bucket =
false;
2176 if (!__new_buckets[__bkt])
2178 __p->_M_nxt = _M_before_begin._M_nxt;
2179 _M_before_begin._M_nxt = __p;
2180 __new_buckets[__bkt] = &_M_before_begin;
2182 __new_buckets[__bbegin_bkt] = __p;
2183 __bbegin_bkt = __bkt;
2187 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2188 __new_buckets[__bkt]->_M_nxt = __p;
2196 if (__check_bucket && __prev_p->_M_nxt)
2198 std::size_t __next_bkt
2199 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2200 if (__next_bkt != __prev_bkt)
2201 __new_buckets[__next_bkt] = __prev_p;
2204 _M_deallocate_buckets();
2205 _M_bucket_count = __n;
2206 _M_buckets = __new_buckets;
2209 #if __cplusplus > 201402L 2210 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2213 _GLIBCXX_END_NAMESPACE_VERSION
2216 #endif // _HASHTABLE_H _T2 second
first is a copy of the first object
_Tp exchange(_Tp &__obj, _Up &&__new_val)
Assign __new_val to __obj and return its previous value.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
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.
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.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
Struct holding two objects of arbitrary type.
Uniform interface to all allocator types.
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.
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.
Node iterators, used to iterate through all the hashtable.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
ISO C++ entities toplevel namespace is std.
Uniform interface to C++98 and C++11 allocators.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_T1 first
second_type is the second bound type
Node const_iterators, used to iterate through all the hashtable.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.