31 #define _HASHTABLE_H 1 33 #pragma GCC system_header 36 #if __cplusplus > 201402L 40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 template<
typename _Tp,
typename _Hash>
47 __is_fast_hash<_Hash>,
49 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
169 template<
typename _Key,
typename _Value,
typename _Alloc,
170 typename _ExtractKey,
typename _Equal,
171 typename _H1,
typename _H2,
typename _Hash,
172 typename _RehashPolicy,
typename _Traits>
175 _H1, _H2, _Hash, _Traits>,
177 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
179 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
181 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
183 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
185 __alloc_rebind<_Alloc,
186 __detail::_Hash_node<_Value,
187 _Traits::__hash_cached::value>>>
189 static_assert(
is_same<
typename remove_cv<_Value>::type, _Value>::value,
190 "unordered container must have a non-const, non-volatile value_type");
191 #ifdef __STRICT_ANSI__ 193 "unordered container must have the same value_type as its allocator");
196 using __traits_type = _Traits;
197 using __hash_cached =
typename __traits_type::__hash_cached;
199 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
203 using __value_alloc_traits =
204 typename __hashtable_alloc::__value_alloc_traits;
205 using __node_alloc_traits =
211 typedef _Key key_type;
212 typedef _Value value_type;
213 typedef _Alloc allocator_type;
214 typedef _Equal key_equal;
218 typedef typename __value_alloc_traits::pointer pointer;
219 typedef typename __value_alloc_traits::const_pointer const_pointer;
220 typedef value_type& reference;
221 typedef const value_type& const_reference;
224 using __rehash_type = _RehashPolicy;
225 using __rehash_state =
typename __rehash_type::_State;
227 using __constant_iterators =
typename __traits_type::__constant_iterators;
228 using __unique_keys =
typename __traits_type::__unique_keys;
231 __constant_iterators::value,
233 __detail::_Select1st>::type;
236 _Hashtable_base<_Key, _Value, _ExtractKey,
237 _Equal, _H1, _H2, _Hash, _Traits>;
240 using __hash_code =
typename __hashtable_base::__hash_code;
241 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
244 _Equal, _H1, _H2, _Hash,
245 _RehashPolicy, _Traits>;
250 _RehashPolicy, _Traits>;
253 _Equal, _H1, _H2, _Hash,
254 _RehashPolicy, _Traits>;
256 using __reuse_or_alloc_node_type =
257 __detail::_ReuseOrAllocNode<__node_alloc_type>;
260 template<
typename _Cond>
261 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
263 template<
typename _Cond>
264 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
270 struct __hash_code_base_access : __hash_code_base
271 {
using __hash_code_base::_M_bucket_index; };
275 static_assert(noexcept(declval<const __hash_code_base_access&>()
278 "Cache the hash code or qualify your functors involved" 279 " in hash code and bucket index computation with noexcept");
287 "Functor used to map hash code to bucket index" 288 " must be default constructible");
290 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
291 typename _ExtractKeya,
typename _Equala,
292 typename _H1a,
typename _H2a,
typename _Hasha,
293 typename _RehashPolicya,
typename _Traitsa,
297 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
298 typename _ExtractKeya,
typename _Equala,
299 typename _H1a,
typename _H2a,
typename _Hasha,
300 typename _RehashPolicya,
typename _Traitsa>
303 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
304 typename _ExtractKeya,
typename _Equala,
305 typename _H1a,
typename _H2a,
typename _Hasha,
306 typename _RehashPolicya,
typename _Traitsa,
307 bool _Constant_iteratorsa>
311 using size_type =
typename __hashtable_base::size_type;
312 using difference_type =
typename __hashtable_base::difference_type;
318 using const_local_iterator =
typename __hashtable_base::
319 const_local_iterator;
321 #if __cplusplus > 201402L 322 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
323 using insert_return_type = _Node_insert_return<iterator, node_type>;
327 __bucket_type* _M_buckets = &_M_single_bucket;
328 size_type _M_bucket_count = 1;
329 __node_base _M_before_begin;
330 size_type _M_element_count = 0;
331 _RehashPolicy _M_rehash_policy;
339 __bucket_type _M_single_bucket =
nullptr;
342 _M_uses_single_bucket(__bucket_type* __bkts)
const 343 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
346 _M_uses_single_bucket()
const 347 {
return _M_uses_single_bucket(_M_buckets); }
350 _M_base_alloc() {
return *
this; }
353 _M_allocate_buckets(size_type __n)
355 if (__builtin_expect(__n == 1,
false))
357 _M_single_bucket =
nullptr;
358 return &_M_single_bucket;
361 return __hashtable_alloc::_M_allocate_buckets(__n);
365 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
367 if (_M_uses_single_bucket(__bkts))
370 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
374 _M_deallocate_buckets()
375 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
380 _M_bucket_begin(size_type __bkt)
const;
384 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
386 template<
typename _NodeGenerator>
388 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
399 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
400 const _Equal& __eq,
const _ExtractKey& __exk,
401 const allocator_type& __a)
410 const _H1&,
const _H2&,
const _Hash&,
411 const _Equal&,
const _ExtractKey&,
412 const allocator_type&);
414 template<
typename _InputIterator>
415 _Hashtable(_InputIterator __first, _InputIterator __last,
416 size_type __bucket_hint,
417 const _H1&,
const _H2&,
const _Hash&,
418 const _Equal&,
const _ExtractKey&,
419 const allocator_type&);
437 const _H1& __hf = _H1(),
438 const key_equal& __eql = key_equal(),
439 const allocator_type& __a = allocator_type())
440 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
441 __key_extract(), __a)
444 template<
typename _InputIterator>
445 _Hashtable(_InputIterator __f, _InputIterator __l,
447 const _H1& __hf = _H1(),
448 const key_equal& __eql = key_equal(),
449 const allocator_type& __a = allocator_type())
450 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
451 __key_extract(), __a)
456 const _H1& __hf = _H1(),
457 const key_equal& __eql = key_equal(),
458 const allocator_type& __a = allocator_type())
459 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
460 __key_extract(), __a)
468 noexcept(__node_alloc_traits::_S_nothrow_move()
472 constexpr
bool __move_storage =
473 __node_alloc_traits::_S_propagate_on_move_assign()
474 || __node_alloc_traits::_S_always_equal();
482 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
483 _M_before_begin._M_nxt =
nullptr;
485 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
493 noexcept(__and_<__is_nothrow_swappable<_H1>,
494 __is_nothrow_swappable<_Equal>>::value);
499 {
return iterator(_M_begin()); }
502 begin()
const noexcept
503 {
return const_iterator(_M_begin()); }
507 {
return iterator(
nullptr); }
511 {
return const_iterator(
nullptr); }
515 {
return const_iterator(_M_begin()); }
518 cend()
const noexcept
519 {
return const_iterator(
nullptr); }
522 size()
const noexcept
523 {
return _M_element_count; }
526 empty()
const noexcept
527 {
return size() == 0; }
530 get_allocator()
const noexcept
531 {
return allocator_type(this->_M_node_allocator()); }
534 max_size()
const noexcept
535 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
540 {
return this->_M_eq(); }
546 bucket_count()
const noexcept
547 {
return _M_bucket_count; }
550 max_bucket_count()
const noexcept
551 {
return max_size(); }
554 bucket_size(size_type __n)
const 558 bucket(
const key_type& __k)
const 559 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
564 return local_iterator(*
this, _M_bucket_begin(__n),
565 __n, _M_bucket_count);
570 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
573 begin(size_type __n)
const 575 return const_local_iterator(*
this, _M_bucket_begin(__n),
576 __n, _M_bucket_count);
580 end(size_type __n)
const 581 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
585 cbegin(size_type __n)
const 587 return const_local_iterator(*
this, _M_bucket_begin(__n),
588 __n, _M_bucket_count);
592 cend(size_type __n)
const 593 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
596 load_factor()
const noexcept
598 return static_cast<float>(size()) / static_cast<float>(bucket_count());
607 __rehash_policy()
const 608 {
return _M_rehash_policy; }
611 __rehash_policy(
const _RehashPolicy& __pol)
612 { _M_rehash_policy = __pol; }
616 find(
const key_type& __k);
619 find(
const key_type& __k)
const;
622 count(
const key_type& __k)
const;
625 equal_range(
const key_type& __k);
628 equal_range(
const key_type& __k)
const;
634 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
637 _M_bucket_index(
const key_type& __k, __hash_code __c)
const 638 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
643 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
646 _M_find_node(size_type __bkt,
const key_type& __key,
647 __hash_code __c)
const 649 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
651 return static_cast<__node_type*
>(__before_n->_M_nxt);
661 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
662 size_type __next_bkt);
666 _M_get_previous_node(size_type __bkt, __node_base* __n);
672 _M_insert_unique_node(size_type __bkt, __hash_code __code,
681 template<
typename... _Args>
685 template<
typename... _Args>
688 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
691 template<
typename... _Args>
693 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
694 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
696 template<
typename... _Args>
700 template<
typename _Arg,
typename _NodeGenerator>
702 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type, size_type = 1);
704 template<
typename _Arg,
typename _NodeGenerator>
706 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
709 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
714 template<
typename _Arg,
typename _NodeGenerator>
716 _M_insert(const_iterator, _Arg&& __arg,
717 const _NodeGenerator& __node_gen,
true_type __uk)
720 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
724 template<
typename _Arg,
typename _NodeGenerator>
726 _M_insert(const_iterator, _Arg&&,
736 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
740 template<
typename... _Args>
742 emplace(_Args&&... __args)
743 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
745 template<
typename... _Args>
747 emplace_hint(const_iterator __hint, _Args&&... __args)
749 return _M_emplace(__hint, __unique_keys(),
750 std::forward<_Args>(__args)...);
757 erase(const_iterator);
762 {
return erase(const_iterator(__it)); }
765 erase(
const key_type& __k)
766 {
return _M_erase(__unique_keys(), __k); }
769 erase(const_iterator, const_iterator);
775 void rehash(size_type __n);
780 #if __cplusplus > 201402L 783 _M_reinsert_node(node_type&& __nh)
785 insert_return_type __ret;
787 __ret.position =
end();
790 __glibcxx_assert(get_allocator() == __nh.get_allocator());
792 const key_type& __k = __nh._M_key();
793 __hash_code __code = this->_M_hash_code(__k);
794 size_type __bkt = _M_bucket_index(__k, __code);
795 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
797 __ret.node = std::move(__nh);
798 __ret.position = iterator(__n);
799 __ret.inserted =
false;
804 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
805 __nh._M_ptr =
nullptr;
806 __ret.inserted =
true;
814 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
821 __glibcxx_assert(get_allocator() == __nh.get_allocator());
823 auto __code = this->_M_hash_code(__nh._M_key());
826 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
833 extract(const_iterator __pos)
836 size_t __bkt = _M_bucket_index(__n);
841 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
843 if (__prev_n == _M_buckets[__bkt])
844 _M_remove_bucket_begin(__bkt, __n->_M_next(),
845 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
846 else if (__n->_M_nxt)
848 size_type __next_bkt = _M_bucket_index(__n->_M_next());
849 if (__next_bkt != __bkt)
850 _M_buckets[__next_bkt] = __prev_n;
853 __prev_n->_M_nxt = __n->_M_nxt;
854 __n->_M_nxt =
nullptr;
856 return { __n, this->_M_node_allocator() };
861 extract(
const _Key& __k)
864 auto __pos = find(__k);
866 __nh = extract(const_iterator(__pos));
871 template<
typename _Compatible_Hashtable>
873 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
875 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
876 node_type>,
"Node types are compatible");
877 __glibcxx_assert(get_allocator() == __src.get_allocator());
879 auto __n_elt = __src.size();
880 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
883 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
884 __hash_code __code = this->_M_hash_code(__k);
885 size_type __bkt = _M_bucket_index(__k, __code);
886 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
888 auto __nh = __src.extract(__pos);
889 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
890 __nh._M_ptr =
nullptr;
893 else if (__n_elt != 1)
899 template<
typename _Compatible_Hashtable>
901 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
903 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
904 node_type>,
"Node types are compatible");
905 __glibcxx_assert(get_allocator() == __src.get_allocator());
907 this->reserve(size() + __src.size());
908 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
909 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
922 void _M_rehash(size_type __n,
const __rehash_state& __state);
927 template<
typename _Key,
typename _Value,
928 typename _Alloc,
typename _ExtractKey,
typename _Equal,
929 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
932 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
933 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
934 _M_bucket_begin(size_type __bkt)
const 937 __node_base* __n = _M_buckets[__bkt];
938 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
941 template<
typename _Key,
typename _Value,
942 typename _Alloc,
typename _ExtractKey,
typename _Equal,
943 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
945 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
946 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
947 _Hashtable(size_type __bucket_hint,
948 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
949 const _Equal& __eq,
const _ExtractKey& __exk,
950 const allocator_type& __a)
951 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
953 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
954 if (__bkt > _M_bucket_count)
956 _M_buckets = _M_allocate_buckets(__bkt);
957 _M_bucket_count = __bkt;
961 template<
typename _Key,
typename _Value,
962 typename _Alloc,
typename _ExtractKey,
typename _Equal,
963 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
965 template<
typename _InputIterator>
966 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
967 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
968 _Hashtable(_InputIterator __f, _InputIterator __l,
969 size_type __bucket_hint,
970 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
971 const _Equal& __eq,
const _ExtractKey& __exk,
972 const allocator_type& __a)
973 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
975 auto __nb_elems = __detail::__distance_fw(__f, __l);
977 _M_rehash_policy._M_next_bkt(
978 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
981 if (__bkt_count > _M_bucket_count)
983 _M_buckets = _M_allocate_buckets(__bkt_count);
984 _M_bucket_count = __bkt_count;
987 for (; __f != __l; ++__f)
991 template<
typename _Key,
typename _Value,
992 typename _Alloc,
typename _ExtractKey,
typename _Equal,
993 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
996 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
997 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1004 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1006 auto& __this_alloc = this->_M_node_allocator();
1007 auto& __that_alloc = __ht._M_node_allocator();
1008 if (!__node_alloc_traits::_S_always_equal()
1009 && __this_alloc != __that_alloc)
1012 this->_M_deallocate_nodes(_M_begin());
1013 _M_before_begin._M_nxt =
nullptr;
1014 _M_deallocate_buckets();
1015 _M_buckets =
nullptr;
1016 std::__alloc_on_copy(__this_alloc, __that_alloc);
1017 __hashtable_base::operator=(__ht);
1018 _M_bucket_count = __ht._M_bucket_count;
1019 _M_element_count = __ht._M_element_count;
1020 _M_rehash_policy = __ht._M_rehash_policy;
1025 {
return this->_M_allocate_node(__n->_M_v()); });
1032 __throw_exception_again;
1036 std::__alloc_on_copy(__this_alloc, __that_alloc);
1040 __bucket_type* __former_buckets =
nullptr;
1041 std::size_t __former_bucket_count = _M_bucket_count;
1042 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1044 if (_M_bucket_count != __ht._M_bucket_count)
1046 __former_buckets = _M_buckets;
1047 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1048 _M_bucket_count = __ht._M_bucket_count;
1051 __builtin_memset(_M_buckets, 0,
1052 _M_bucket_count *
sizeof(__bucket_type));
1056 __hashtable_base::operator=(__ht);
1057 _M_element_count = __ht._M_element_count;
1058 _M_rehash_policy = __ht._M_rehash_policy;
1059 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1060 _M_before_begin._M_nxt =
nullptr;
1063 {
return __roan(__n->_M_v()); });
1064 if (__former_buckets)
1065 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1069 if (__former_buckets)
1072 _M_deallocate_buckets();
1073 _M_rehash_policy._M_reset(__former_state);
1074 _M_buckets = __former_buckets;
1075 _M_bucket_count = __former_bucket_count;
1077 __builtin_memset(_M_buckets, 0,
1078 _M_bucket_count *
sizeof(__bucket_type));
1079 __throw_exception_again;
1084 template<
typename _Key,
typename _Value,
1085 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1086 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1088 template<
typename _NodeGenerator>
1090 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1091 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1092 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
1094 __bucket_type* __buckets =
nullptr;
1096 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1100 if (!__ht._M_before_begin._M_nxt)
1107 this->_M_copy_code(__this_n, __ht_n);
1108 _M_before_begin._M_nxt = __this_n;
1109 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1112 __node_base* __prev_n = __this_n;
1113 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1115 __this_n = __node_gen(__ht_n);
1116 __prev_n->_M_nxt = __this_n;
1117 this->_M_copy_code(__this_n, __ht_n);
1118 size_type __bkt = _M_bucket_index(__this_n);
1119 if (!_M_buckets[__bkt])
1120 _M_buckets[__bkt] = __prev_n;
1121 __prev_n = __this_n;
1128 _M_deallocate_buckets();
1129 __throw_exception_again;
1133 template<
typename _Key,
typename _Value,
1134 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1135 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1138 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1139 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1142 _M_rehash_policy._M_reset();
1143 _M_bucket_count = 1;
1144 _M_single_bucket =
nullptr;
1145 _M_buckets = &_M_single_bucket;
1146 _M_before_begin._M_nxt =
nullptr;
1147 _M_element_count = 0;
1150 template<
typename _Key,
typename _Value,
1151 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1152 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1155 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1156 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1159 this->_M_deallocate_nodes(_M_begin());
1160 _M_deallocate_buckets();
1161 __hashtable_base::operator=(std::move(__ht));
1162 _M_rehash_policy = __ht._M_rehash_policy;
1163 if (!__ht._M_uses_single_bucket())
1164 _M_buckets = __ht._M_buckets;
1167 _M_buckets = &_M_single_bucket;
1168 _M_single_bucket = __ht._M_single_bucket;
1170 _M_bucket_count = __ht._M_bucket_count;
1171 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1172 _M_element_count = __ht._M_element_count;
1173 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1178 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1182 template<
typename _Key,
typename _Value,
1183 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1184 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1187 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1188 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1191 if (__ht._M_node_allocator() == this->_M_node_allocator())
1196 __bucket_type* __former_buckets =
nullptr;
1197 size_type __former_bucket_count = _M_bucket_count;
1198 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1200 if (_M_bucket_count != __ht._M_bucket_count)
1202 __former_buckets = _M_buckets;
1203 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1204 _M_bucket_count = __ht._M_bucket_count;
1207 __builtin_memset(_M_buckets, 0,
1208 _M_bucket_count *
sizeof(__bucket_type));
1212 __hashtable_base::operator=(std::move(__ht));
1213 _M_element_count = __ht._M_element_count;
1214 _M_rehash_policy = __ht._M_rehash_policy;
1215 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1216 _M_before_begin._M_nxt =
nullptr;
1221 if (__former_buckets)
1222 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1227 if (__former_buckets)
1229 _M_deallocate_buckets();
1230 _M_rehash_policy._M_reset(__former_state);
1231 _M_buckets = __former_buckets;
1232 _M_bucket_count = __former_bucket_count;
1234 __builtin_memset(_M_buckets, 0,
1235 _M_bucket_count *
sizeof(__bucket_type));
1236 __throw_exception_again;
1241 template<
typename _Key,
typename _Value,
1242 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1243 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1245 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1246 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1252 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1253 _M_buckets(
nullptr),
1254 _M_bucket_count(__ht._M_bucket_count),
1255 _M_element_count(__ht._M_element_count),
1256 _M_rehash_policy(__ht._M_rehash_policy)
1260 {
return this->_M_allocate_node(__n->_M_v()); });
1263 template<
typename _Key,
typename _Value,
1264 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1265 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1267 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1268 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1274 _M_buckets(__ht._M_buckets),
1275 _M_bucket_count(__ht._M_bucket_count),
1276 _M_before_begin(__ht._M_before_begin._M_nxt),
1277 _M_element_count(__ht._M_element_count),
1278 _M_rehash_policy(__ht._M_rehash_policy)
1281 if (__ht._M_uses_single_bucket())
1283 _M_buckets = &_M_single_bucket;
1284 _M_single_bucket = __ht._M_single_bucket;
1290 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1295 template<
typename _Key,
typename _Value,
1296 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1297 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1299 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1300 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1301 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1307 _M_bucket_count(__ht._M_bucket_count),
1308 _M_element_count(__ht._M_element_count),
1309 _M_rehash_policy(__ht._M_rehash_policy)
1313 {
return this->_M_allocate_node(__n->_M_v()); });
1316 template<
typename _Key,
typename _Value,
1317 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1318 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1320 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1321 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1322 _Hashtable(
_Hashtable&& __ht,
const allocator_type& __a)
1327 _M_buckets(
nullptr),
1328 _M_bucket_count(__ht._M_bucket_count),
1329 _M_element_count(__ht._M_element_count),
1330 _M_rehash_policy(__ht._M_rehash_policy)
1332 if (__ht._M_node_allocator() == this->_M_node_allocator())
1334 if (__ht._M_uses_single_bucket())
1336 _M_buckets = &_M_single_bucket;
1337 _M_single_bucket = __ht._M_single_bucket;
1340 _M_buckets = __ht._M_buckets;
1342 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1346 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1354 return this->_M_allocate_node(
1361 template<
typename _Key,
typename _Value,
1362 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1363 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1365 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1366 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1367 ~_Hashtable() noexcept
1370 _M_deallocate_buckets();
1372 static_assert(__is_invocable<const _H1&, const _Key&>{},
1373 "hash function must be invocable with an argument of key type");
1374 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
1375 "key equality predicate must be invocable with two arguments of " 1379 template<
typename _Key,
typename _Value,
1380 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1381 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1384 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1385 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1387 noexcept(__and_<__is_nothrow_swappable<_H1>,
1388 __is_nothrow_swappable<_Equal>>::value)
1395 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1396 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1399 if (this->_M_uses_single_bucket())
1401 if (!__x._M_uses_single_bucket())
1403 _M_buckets = __x._M_buckets;
1404 __x._M_buckets = &__x._M_single_bucket;
1407 else if (__x._M_uses_single_bucket())
1409 __x._M_buckets = _M_buckets;
1410 _M_buckets = &_M_single_bucket;
1413 std::swap(_M_buckets, __x._M_buckets);
1415 std::swap(_M_bucket_count, __x._M_bucket_count);
1416 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1417 std::swap(_M_element_count, __x._M_element_count);
1418 std::swap(_M_single_bucket, __x._M_single_bucket);
1423 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1426 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1427 = &__x._M_before_begin;
1430 template<
typename _Key,
typename _Value,
1431 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1432 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1435 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1436 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1437 find(
const key_type& __k)
1440 __hash_code __code = this->_M_hash_code(__k);
1441 std::size_t __n = _M_bucket_index(__k, __code);
1442 __node_type* __p = _M_find_node(__n, __k, __code);
1443 return __p ? iterator(__p) :
end();
1446 template<
typename _Key,
typename _Value,
1447 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1448 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1451 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1452 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1453 find(
const key_type& __k)
const 1456 __hash_code __code = this->_M_hash_code(__k);
1457 std::size_t __n = _M_bucket_index(__k, __code);
1458 __node_type* __p = _M_find_node(__n, __k, __code);
1459 return __p ? const_iterator(__p) :
end();
1462 template<
typename _Key,
typename _Value,
1463 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1464 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1467 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1468 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1469 count(
const key_type& __k)
const 1472 __hash_code __code = this->_M_hash_code(__k);
1473 std::size_t __n = _M_bucket_index(__k, __code);
1478 std::size_t __result = 0;
1479 for (;; __p = __p->_M_next())
1481 if (this->_M_equals(__k, __code, __p))
1488 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1494 template<
typename _Key,
typename _Value,
1495 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1496 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1499 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1500 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1501 equal_range(
const key_type& __k)
1504 __hash_code __code = this->_M_hash_code(__k);
1505 std::size_t __n = _M_bucket_index(__k, __code);
1506 __node_type* __p = _M_find_node(__n, __k, __code);
1511 while (__p1 && _M_bucket_index(__p1) == __n
1512 && this->_M_equals(__k, __code, __p1))
1513 __p1 = __p1->_M_next();
1521 template<
typename _Key,
typename _Value,
1522 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1523 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1526 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1527 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1528 equal_range(
const key_type& __k)
const 1531 __hash_code __code = this->_M_hash_code(__k);
1532 std::size_t __n = _M_bucket_index(__k, __code);
1533 __node_type* __p = _M_find_node(__n, __k, __code);
1538 while (__p1 && _M_bucket_index(__p1) == __n
1539 && this->_M_equals(__k, __code, __p1))
1540 __p1 = __p1->_M_next();
1542 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1550 template<
typename _Key,
typename _Value,
1551 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1552 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1555 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1556 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1557 _M_find_before_node(size_type __n,
const key_type& __k,
1558 __hash_code __code)
const 1561 __node_base* __prev_p = _M_buckets[__n];
1565 for (
__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1566 __p = __p->_M_next())
1568 if (this->_M_equals(__k, __code, __p))
1571 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1578 template<
typename _Key,
typename _Value,
1579 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1580 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1583 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1584 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1585 _M_insert_bucket_begin(size_type __bkt,
__node_type* __node)
1587 if (_M_buckets[__bkt])
1591 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1592 _M_buckets[__bkt]->_M_nxt = __node;
1599 __node->_M_nxt = _M_before_begin._M_nxt;
1600 _M_before_begin._M_nxt = __node;
1604 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1605 _M_buckets[__bkt] = &_M_before_begin;
1609 template<
typename _Key,
typename _Value,
1610 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1611 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1614 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1615 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1616 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next,
1617 size_type __next_bkt)
1619 if (!__next || __next_bkt != __bkt)
1624 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1627 if (&_M_before_begin == _M_buckets[__bkt])
1628 _M_before_begin._M_nxt = __next;
1629 _M_buckets[__bkt] =
nullptr;
1633 template<
typename _Key,
typename _Value,
1634 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1635 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1638 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1639 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1640 _M_get_previous_node(size_type __bkt, __node_base* __n)
1643 __node_base* __prev_n = _M_buckets[__bkt];
1644 while (__prev_n->_M_nxt != __n)
1645 __prev_n = __prev_n->_M_nxt;
1649 template<
typename _Key,
typename _Value,
1650 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1651 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1653 template<
typename... _Args>
1655 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1656 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1661 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1662 const key_type& __k = this->_M_extract()(__node->_M_v());
1666 __code = this->_M_hash_code(__k);
1670 this->_M_deallocate_node(__node);
1671 __throw_exception_again;
1674 size_type __bkt = _M_bucket_index(__k, __code);
1675 if (
__node_type* __p = _M_find_node(__bkt, __k, __code))
1678 this->_M_deallocate_node(__node);
1683 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1687 template<
typename _Key,
typename _Value,
1688 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1689 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1691 template<
typename... _Args>
1693 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1694 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1700 this->_M_allocate_node(std::forward<_Args>(__args)...);
1705 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1709 this->_M_deallocate_node(__node);
1710 __throw_exception_again;
1713 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1716 template<
typename _Key,
typename _Value,
1717 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1718 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1721 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1722 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1723 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1727 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1729 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1734 if (__do_rehash.
first)
1736 _M_rehash(__do_rehash.
second, __saved_state);
1737 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1740 this->_M_store_code(__node, __code);
1743 _M_insert_bucket_begin(__bkt, __node);
1745 return iterator(__node);
1749 this->_M_deallocate_node(__node);
1750 __throw_exception_again;
1756 template<
typename _Key,
typename _Value,
1757 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1758 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1761 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1762 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1763 _M_insert_multi_node(
__node_type* __hint, __hash_code __code,
1767 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1769 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1773 if (__do_rehash.
first)
1774 _M_rehash(__do_rehash.
second, __saved_state);
1776 this->_M_store_code(__node, __code);
1777 const key_type& __k = this->_M_extract()(__node->_M_v());
1778 size_type __bkt = _M_bucket_index(__k, __code);
1783 = __builtin_expect(__hint !=
nullptr,
false)
1784 && this->_M_equals(__k, __code, __hint)
1786 : _M_find_before_node(__bkt, __k, __code);
1790 __node->_M_nxt = __prev->_M_nxt;
1791 __prev->_M_nxt = __node;
1792 if (__builtin_expect(__prev == __hint,
false))
1796 && !this->_M_equals(__k, __code, __node->_M_next()))
1798 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1799 if (__next_bkt != __bkt)
1800 _M_buckets[__next_bkt] = __node;
1808 _M_insert_bucket_begin(__bkt, __node);
1810 return iterator(__node);
1814 this->_M_deallocate_node(__node);
1815 __throw_exception_again;
1820 template<
typename _Key,
typename _Value,
1821 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1822 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1824 template<
typename _Arg,
typename _NodeGenerator>
1826 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1827 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1828 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
true_type,
1832 const key_type& __k = this->_M_extract()(__v);
1833 __hash_code __code = this->_M_hash_code(__k);
1834 size_type __bkt = _M_bucket_index(__k, __code);
1836 __node_type* __n = _M_find_node(__bkt, __k, __code);
1840 __n = __node_gen(std::forward<_Arg>(__v));
1841 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt),
true };
1845 template<
typename _Key,
typename _Value,
1846 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1847 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1849 template<
typename _Arg,
typename _NodeGenerator>
1851 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1852 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1853 _M_insert(const_iterator __hint, _Arg&& __v,
1854 const _NodeGenerator& __node_gen,
false_type)
1859 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1862 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1864 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1867 template<
typename _Key,
typename _Value,
1868 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1869 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1872 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1873 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1874 erase(const_iterator __it)
1878 std::size_t __bkt = _M_bucket_index(__n);
1883 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1884 return _M_erase(__bkt, __prev_n, __n);
1887 template<
typename _Key,
typename _Value,
1888 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1889 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1892 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1893 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1894 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n)
1897 if (__prev_n == _M_buckets[__bkt])
1898 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1899 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1900 else if (__n->_M_nxt)
1902 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1903 if (__next_bkt != __bkt)
1904 _M_buckets[__next_bkt] = __prev_n;
1907 __prev_n->_M_nxt = __n->_M_nxt;
1908 iterator __result(__n->_M_next());
1909 this->_M_deallocate_node(__n);
1915 template<
typename _Key,
typename _Value,
1916 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1917 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1920 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1921 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1925 __hash_code __code = this->_M_hash_code(__k);
1926 std::size_t __bkt = _M_bucket_index(__k, __code);
1929 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1935 _M_erase(__bkt, __prev_n, __n);
1939 template<
typename _Key,
typename _Value,
1940 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1941 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1944 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1945 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1949 __hash_code __code = this->_M_hash_code(__k);
1950 std::size_t __bkt = _M_bucket_index(__k, __code);
1953 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1965 std::size_t __n_last_bkt = __bkt;
1968 __n_last = __n_last->_M_next();
1971 __n_last_bkt = _M_bucket_index(__n_last);
1973 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1976 size_type __result = 0;
1980 this->_M_deallocate_node(__n);
1985 while (__n != __n_last);
1987 if (__prev_n == _M_buckets[__bkt])
1988 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1989 else if (__n_last && __n_last_bkt != __bkt)
1990 _M_buckets[__n_last_bkt] = __prev_n;
1991 __prev_n->_M_nxt = __n_last;
1995 template<
typename _Key,
typename _Value,
1996 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1997 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2000 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2001 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2002 erase(const_iterator __first, const_iterator __last)
2007 if (__n == __last_n)
2008 return iterator(__n);
2010 std::size_t __bkt = _M_bucket_index(__n);
2012 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
2013 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2014 std::size_t __n_bkt = __bkt;
2020 __n = __n->_M_next();
2021 this->_M_deallocate_node(__tmp);
2025 __n_bkt = _M_bucket_index(__n);
2027 while (__n != __last_n && __n_bkt == __bkt);
2028 if (__is_bucket_begin)
2029 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2030 if (__n == __last_n)
2032 __is_bucket_begin =
true;
2036 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2037 _M_buckets[__n_bkt] = __prev_n;
2038 __prev_n->_M_nxt = __n;
2039 return iterator(__n);
2042 template<
typename _Key,
typename _Value,
2043 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2044 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2047 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2048 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2051 this->_M_deallocate_nodes(_M_begin());
2052 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2053 _M_element_count = 0;
2054 _M_before_begin._M_nxt =
nullptr;
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 rehash(size_type __n)
2066 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2067 std::size_t __buckets
2068 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2070 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2072 if (__buckets != _M_bucket_count)
2073 _M_rehash(__buckets, __saved_state);
2076 _M_rehash_policy._M_reset(__saved_state);
2079 template<
typename _Key,
typename _Value,
2080 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2081 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2084 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2085 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2086 _M_rehash(size_type __n,
const __rehash_state& __state)
2090 _M_rehash_aux(__n, __unique_keys());
2096 _M_rehash_policy._M_reset(__state);
2097 __throw_exception_again;
2102 template<
typename _Key,
typename _Value,
2103 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2104 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2107 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2108 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2111 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2113 _M_before_begin._M_nxt =
nullptr;
2114 std::size_t __bbegin_bkt = 0;
2118 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2119 if (!__new_buckets[__bkt])
2121 __p->_M_nxt = _M_before_begin._M_nxt;
2122 _M_before_begin._M_nxt = __p;
2123 __new_buckets[__bkt] = &_M_before_begin;
2125 __new_buckets[__bbegin_bkt] = __p;
2126 __bbegin_bkt = __bkt;
2130 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2131 __new_buckets[__bkt]->_M_nxt = __p;
2136 _M_deallocate_buckets();
2137 _M_bucket_count = __n;
2138 _M_buckets = __new_buckets;
2143 template<
typename _Key,
typename _Value,
2144 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2145 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2148 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2149 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2152 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2155 _M_before_begin._M_nxt =
nullptr;
2156 std::size_t __bbegin_bkt = 0;
2157 std::size_t __prev_bkt = 0;
2159 bool __check_bucket =
false;
2164 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2166 if (__prev_p && __prev_bkt == __bkt)
2171 __p->_M_nxt = __prev_p->_M_nxt;
2172 __prev_p->_M_nxt = __p;
2179 __check_bucket =
true;
2187 if (__prev_p->_M_nxt)
2189 std::size_t __next_bkt
2190 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2192 if (__next_bkt != __prev_bkt)
2193 __new_buckets[__next_bkt] = __prev_p;
2195 __check_bucket =
false;
2198 if (!__new_buckets[__bkt])
2200 __p->_M_nxt = _M_before_begin._M_nxt;
2201 _M_before_begin._M_nxt = __p;
2202 __new_buckets[__bkt] = &_M_before_begin;
2204 __new_buckets[__bbegin_bkt] = __p;
2205 __bbegin_bkt = __bkt;
2209 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2210 __new_buckets[__bkt]->_M_nxt = __p;
2218 if (__check_bucket && __prev_p->_M_nxt)
2220 std::size_t __next_bkt
2221 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2222 if (__next_bkt != __prev_bkt)
2223 __new_buckets[__next_bkt] = __prev_p;
2226 _M_deallocate_buckets();
2227 _M_bucket_count = __n;
2228 _M_buckets = __new_buckets;
2231 #if __cplusplus > 201402L 2232 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2235 _GLIBCXX_END_NAMESPACE_VERSION
2238 #endif // _HASHTABLE_H
_T2 second
first is a copy of the first object
Node iterators, used to iterate through all the hashtable.
_T1 first
second_type is the second bound type
_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. ...
Define a member typedef type to one of two argument types.
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.
is_nothrow_move_assignable
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.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Uniform interface to C++98 and C++11 allocators.
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.
Struct holding two objects of arbitrary type.