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;
1210 if (__former_buckets)
1211 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1216 if (__former_buckets)
1218 _M_deallocate_buckets();
1219 _M_rehash_policy._M_reset(__former_state);
1220 _M_buckets = __former_buckets;
1221 _M_bucket_count = __former_bucket_count;
1223 __builtin_memset(_M_buckets, 0,
1224 _M_bucket_count *
sizeof(__bucket_type));
1225 __throw_exception_again;
1230 template<
typename _Key,
typename _Value,
1231 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1232 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1234 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1235 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1241 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1242 _M_buckets(
nullptr),
1243 _M_bucket_count(__ht._M_bucket_count),
1244 _M_element_count(__ht._M_element_count),
1245 _M_rehash_policy(__ht._M_rehash_policy)
1249 {
return this->_M_allocate_node(__n->_M_v()); });
1252 template<
typename _Key,
typename _Value,
1253 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1254 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1256 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1257 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1263 _M_buckets(__ht._M_buckets),
1264 _M_bucket_count(__ht._M_bucket_count),
1265 _M_before_begin(__ht._M_before_begin._M_nxt),
1266 _M_element_count(__ht._M_element_count),
1267 _M_rehash_policy(__ht._M_rehash_policy)
1270 if (__ht._M_uses_single_bucket())
1272 _M_buckets = &_M_single_bucket;
1273 _M_single_bucket = __ht._M_single_bucket;
1279 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1284 template<
typename _Key,
typename _Value,
1285 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1286 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1288 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1289 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1290 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1296 _M_bucket_count(__ht._M_bucket_count),
1297 _M_element_count(__ht._M_element_count),
1298 _M_rehash_policy(__ht._M_rehash_policy)
1302 {
return this->_M_allocate_node(__n->_M_v()); });
1305 template<
typename _Key,
typename _Value,
1306 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1307 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1309 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1310 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1311 _Hashtable(
_Hashtable&& __ht,
const allocator_type& __a)
1316 _M_buckets(
nullptr),
1317 _M_bucket_count(__ht._M_bucket_count),
1318 _M_element_count(__ht._M_element_count),
1319 _M_rehash_policy(__ht._M_rehash_policy)
1321 if (__ht._M_node_allocator() == this->_M_node_allocator())
1323 if (__ht._M_uses_single_bucket())
1325 _M_buckets = &_M_single_bucket;
1326 _M_single_bucket = __ht._M_single_bucket;
1329 _M_buckets = __ht._M_buckets;
1331 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1335 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1343 return this->_M_allocate_node(
1350 template<
typename _Key,
typename _Value,
1351 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1352 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1354 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1355 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1356 ~_Hashtable() noexcept
1359 _M_deallocate_buckets();
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>::
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);
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)
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);
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 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);
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>::
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>::
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,
1710 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1712 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1716 if (__do_rehash.
first)
1718 _M_rehash(__do_rehash.
second, __saved_state);
1719 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1722 this->_M_store_code(__node, __code);
1725 _M_insert_bucket_begin(__bkt, __node);
1727 return iterator(__node);
1731 this->_M_deallocate_node(__node);
1732 __throw_exception_again;
1738 template<
typename _Key,
typename _Value,
1739 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1740 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1743 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1744 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1745 _M_insert_multi_node(
__node_type* __hint, __hash_code __code,
1749 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1751 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1755 if (__do_rehash.
first)
1756 _M_rehash(__do_rehash.
second, __saved_state);
1758 this->_M_store_code(__node, __code);
1759 const key_type& __k = this->_M_extract()(__node->_M_v());
1760 size_type __bkt = _M_bucket_index(__k, __code);
1765 = __builtin_expect(__hint !=
nullptr,
false)
1766 && this->_M_equals(__k, __code, __hint)
1768 : _M_find_before_node(__bkt, __k, __code);
1772 __node->_M_nxt = __prev->_M_nxt;
1773 __prev->_M_nxt = __node;
1774 if (__builtin_expect(__prev == __hint,
false))
1778 && !this->_M_equals(__k, __code, __node->_M_next()))
1780 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1781 if (__next_bkt != __bkt)
1782 _M_buckets[__next_bkt] = __node;
1790 _M_insert_bucket_begin(__bkt, __node);
1792 return iterator(__node);
1796 this->_M_deallocate_node(__node);
1797 __throw_exception_again;
1802 template<
typename _Key,
typename _Value,
1803 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1804 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1806 template<
typename _Arg,
typename _NodeGenerator>
1808 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1809 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1810 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
std::true_type)
1813 const key_type& __k = this->_M_extract()(__v);
1814 __hash_code __code = this->_M_hash_code(__k);
1815 size_type __bkt = _M_bucket_index(__k, __code);
1817 __node_type* __n = _M_find_node(__bkt, __k, __code);
1821 __n = __node_gen(std::forward<_Arg>(__v));
1822 return std::make_pair(_M_insert_unique_node(__bkt, __code, __n),
true);
1826 template<
typename _Key,
typename _Value,
1827 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1828 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1830 template<
typename _Arg,
typename _NodeGenerator>
1832 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1833 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1834 _M_insert(const_iterator __hint, _Arg&& __v,
1840 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1843 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1845 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1848 template<
typename _Key,
typename _Value,
1849 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1850 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1853 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1854 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1855 erase(const_iterator __it)
1859 std::size_t __bkt = _M_bucket_index(__n);
1864 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1865 return _M_erase(__bkt, __prev_n, __n);
1868 template<
typename _Key,
typename _Value,
1869 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1870 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1873 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1874 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1875 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n)
1878 if (__prev_n == _M_buckets[__bkt])
1879 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1880 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1881 else if (__n->_M_nxt)
1883 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1884 if (__next_bkt != __bkt)
1885 _M_buckets[__next_bkt] = __prev_n;
1888 __prev_n->_M_nxt = __n->_M_nxt;
1889 iterator __result(__n->_M_next());
1890 this->_M_deallocate_node(__n);
1896 template<
typename _Key,
typename _Value,
1897 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1898 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1901 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1902 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1906 __hash_code __code = this->_M_hash_code(__k);
1907 std::size_t __bkt = _M_bucket_index(__k, __code);
1910 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1916 _M_erase(__bkt, __prev_n, __n);
1920 template<
typename _Key,
typename _Value,
1921 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1922 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1925 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1926 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1930 __hash_code __code = this->_M_hash_code(__k);
1931 std::size_t __bkt = _M_bucket_index(__k, __code);
1934 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1946 std::size_t __n_last_bkt = __bkt;
1949 __n_last = __n_last->_M_next();
1952 __n_last_bkt = _M_bucket_index(__n_last);
1954 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1957 size_type __result = 0;
1961 this->_M_deallocate_node(__n);
1966 while (__n != __n_last);
1968 if (__prev_n == _M_buckets[__bkt])
1969 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1970 else if (__n_last && __n_last_bkt != __bkt)
1971 _M_buckets[__n_last_bkt] = __prev_n;
1972 __prev_n->_M_nxt = __n_last;
1976 template<
typename _Key,
typename _Value,
1977 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1978 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1981 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1982 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1983 erase(const_iterator __first, const_iterator __last)
1988 if (__n == __last_n)
1989 return iterator(__n);
1991 std::size_t __bkt = _M_bucket_index(__n);
1993 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1994 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1995 std::size_t __n_bkt = __bkt;
2001 __n = __n->_M_next();
2002 this->_M_deallocate_node(__tmp);
2006 __n_bkt = _M_bucket_index(__n);
2008 while (__n != __last_n && __n_bkt == __bkt);
2009 if (__is_bucket_begin)
2010 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2011 if (__n == __last_n)
2013 __is_bucket_begin =
true;
2017 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2018 _M_buckets[__n_bkt] = __prev_n;
2019 __prev_n->_M_nxt = __n;
2020 return iterator(__n);
2023 template<
typename _Key,
typename _Value,
2024 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2025 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2028 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2029 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2032 this->_M_deallocate_nodes(_M_begin());
2033 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2034 _M_element_count = 0;
2035 _M_before_begin._M_nxt =
nullptr;
2038 template<
typename _Key,
typename _Value,
2039 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2040 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2043 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2044 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2045 rehash(size_type __n)
2047 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2048 std::size_t __buckets
2049 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2051 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2053 if (__buckets != _M_bucket_count)
2054 _M_rehash(__buckets, __saved_state);
2057 _M_rehash_policy._M_reset(__saved_state);
2060 template<
typename _Key,
typename _Value,
2061 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2062 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2065 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2066 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2067 _M_rehash(size_type __n,
const __rehash_state& __state)
2071 _M_rehash_aux(__n, __unique_keys());
2077 _M_rehash_policy._M_reset(__state);
2078 __throw_exception_again;
2083 template<
typename _Key,
typename _Value,
2084 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2085 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2088 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2089 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2092 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2094 _M_before_begin._M_nxt =
nullptr;
2095 std::size_t __bbegin_bkt = 0;
2099 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2100 if (!__new_buckets[__bkt])
2102 __p->_M_nxt = _M_before_begin._M_nxt;
2103 _M_before_begin._M_nxt = __p;
2104 __new_buckets[__bkt] = &_M_before_begin;
2106 __new_buckets[__bbegin_bkt] = __p;
2107 __bbegin_bkt = __bkt;
2111 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2112 __new_buckets[__bkt]->_M_nxt = __p;
2117 _M_deallocate_buckets();
2118 _M_bucket_count = __n;
2119 _M_buckets = __new_buckets;
2124 template<
typename _Key,
typename _Value,
2125 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2126 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2129 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2130 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2133 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2136 _M_before_begin._M_nxt =
nullptr;
2137 std::size_t __bbegin_bkt = 0;
2138 std::size_t __prev_bkt = 0;
2140 bool __check_bucket =
false;
2145 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2147 if (__prev_p && __prev_bkt == __bkt)
2152 __p->_M_nxt = __prev_p->_M_nxt;
2153 __prev_p->_M_nxt = __p;
2160 __check_bucket =
true;
2168 if (__prev_p->_M_nxt)
2170 std::size_t __next_bkt
2171 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2173 if (__next_bkt != __prev_bkt)
2174 __new_buckets[__next_bkt] = __prev_p;
2176 __check_bucket =
false;
2179 if (!__new_buckets[__bkt])
2181 __p->_M_nxt = _M_before_begin._M_nxt;
2182 _M_before_begin._M_nxt = __p;
2183 __new_buckets[__bkt] = &_M_before_begin;
2185 __new_buckets[__bbegin_bkt] = __p;
2186 __bbegin_bkt = __bkt;
2190 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2191 __new_buckets[__bkt]->_M_nxt = __p;
2199 if (__check_bucket && __prev_p->_M_nxt)
2201 std::size_t __next_bkt
2202 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2203 if (__next_bkt != __prev_bkt)
2204 __new_buckets[__next_bkt] = __prev_p;
2207 _M_deallocate_buckets();
2208 _M_bucket_count = __n;
2209 _M_buckets = __new_buckets;
2212 #if __cplusplus > 201402L 2213 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2216 _GLIBCXX_END_NAMESPACE_VERSION
2219 #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.