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 #if __cplusplus > 201703L || defined __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_gen_t =
257 __detail::_ReuseOrAllocNode<__node_alloc_type>;
264 : _M_h(__h), _M_node(__n) { }
267 template<
typename... _Args>
270 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
274 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
276 _Scoped_node(
const _Scoped_node&) =
delete;
277 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
284 template<
typename _Cond>
285 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
287 template<
typename _Cond>
288 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
294 struct __hash_code_base_access : __hash_code_base
295 {
using __hash_code_base::_M_bucket_index; };
299 static_assert(noexcept(declval<const __hash_code_base_access&>()
302 "Cache the hash code or qualify your functors involved"
303 " in hash code and bucket index computation with noexcept");
308 "Functor used to map hash code to bucket index"
309 " must be default constructible");
311 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
312 typename _ExtractKeya,
typename _Equala,
313 typename _H1a,
typename _H2a,
typename _Hasha,
314 typename _RehashPolicya,
typename _Traitsa,
318 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
319 typename _ExtractKeya,
typename _Equala,
320 typename _H1a,
typename _H2a,
typename _Hasha,
321 typename _RehashPolicya,
typename _Traitsa>
324 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
325 typename _ExtractKeya,
typename _Equala,
326 typename _H1a,
typename _H2a,
typename _Hasha,
327 typename _RehashPolicya,
typename _Traitsa,
328 bool _Constant_iteratorsa>
332 using size_type =
typename __hashtable_base::size_type;
333 using difference_type =
typename __hashtable_base::difference_type;
339 using const_local_iterator =
typename __hashtable_base::
340 const_local_iterator;
342 #if __cplusplus > 201402L
343 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
344 using insert_return_type = _Node_insert_return<iterator, node_type>;
348 __bucket_type* _M_buckets = &_M_single_bucket;
349 size_type _M_bucket_count = 1;
350 __node_base _M_before_begin;
351 size_type _M_element_count = 0;
352 _RehashPolicy _M_rehash_policy;
360 __bucket_type _M_single_bucket =
nullptr;
363 _M_uses_single_bucket(__bucket_type* __bkts)
const
364 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
367 _M_uses_single_bucket()
const
368 {
return _M_uses_single_bucket(_M_buckets); }
371 _M_base_alloc() {
return *
this; }
374 _M_allocate_buckets(size_type __bkt_count)
376 if (__builtin_expect(__bkt_count == 1,
false))
378 _M_single_bucket =
nullptr;
379 return &_M_single_bucket;
382 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
386 _M_deallocate_buckets(__bucket_type* __bkts, size_type __bkt_count)
388 if (_M_uses_single_bucket(__bkts))
391 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
395 _M_deallocate_buckets()
396 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
401 _M_bucket_begin(size_type __bkt)
const;
405 {
return static_cast<__node_type*>(_M_before_begin._M_nxt); }
409 template<
typename _Ht,
typename _NodeGenerator>
411 _M_assign_elements(_Ht&&,
const _NodeGenerator&);
413 template<
typename _NodeGenerator>
415 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
426 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
427 const _Equal& __eq,
const _ExtractKey& __exk,
428 const allocator_type& __a)
437 const _H1&,
const _H2&,
const _Hash&,
438 const _Equal&,
const _ExtractKey&,
439 const allocator_type&);
441 template<
typename _InputIterator>
442 _Hashtable(_InputIterator __first, _InputIterator __last,
443 size_type __bkt_count_hint,
444 const _H1&,
const _H2&,
const _Hash&,
445 const _Equal&,
const _ExtractKey&,
446 const allocator_type&);
464 const _H1& __hf = _H1(),
465 const key_equal& __eql = key_equal(),
466 const allocator_type& __a = allocator_type())
467 :
_Hashtable(__bkt_count_hint, __hf, _H2(), _Hash(), __eql,
468 __key_extract(), __a)
471 template<
typename _InputIterator>
472 _Hashtable(_InputIterator __f, _InputIterator __l,
473 size_type __bkt_count_hint = 0,
474 const _H1& __hf = _H1(),
475 const key_equal& __eql = key_equal(),
476 const allocator_type& __a = allocator_type())
477 :
_Hashtable(__f, __l, __bkt_count_hint, __hf, _H2(), _Hash(), __eql,
478 __key_extract(), __a)
482 size_type __bkt_count_hint = 0,
483 const _H1& __hf = _H1(),
484 const key_equal& __eql = key_equal(),
485 const allocator_type& __a = allocator_type())
486 :
_Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
487 __hf, _H2(), _Hash(), __eql,
488 __key_extract(), __a)
496 noexcept(__node_alloc_traits::_S_nothrow_move()
500 constexpr
bool __move_storage =
501 __node_alloc_traits::_S_propagate_on_move_assign()
502 || __node_alloc_traits::_S_always_equal();
510 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
511 _M_before_begin._M_nxt =
nullptr;
513 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
521 noexcept(__and_<__is_nothrow_swappable<_H1>,
522 __is_nothrow_swappable<_Equal>>::value);
527 {
return iterator(_M_begin()); }
530 begin()
const noexcept
531 {
return const_iterator(_M_begin()); }
535 {
return iterator(
nullptr); }
539 {
return const_iterator(
nullptr); }
543 {
return const_iterator(_M_begin()); }
546 cend()
const noexcept
547 {
return const_iterator(
nullptr); }
550 size()
const noexcept
551 {
return _M_element_count; }
553 _GLIBCXX_NODISCARD
bool
554 empty()
const noexcept
555 {
return size() == 0; }
558 get_allocator()
const noexcept
559 {
return allocator_type(this->_M_node_allocator()); }
562 max_size()
const noexcept
563 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
568 {
return this->_M_eq(); }
574 bucket_count()
const noexcept
575 {
return _M_bucket_count; }
578 max_bucket_count()
const noexcept
579 {
return max_size(); }
582 bucket_size(size_type __bkt)
const
586 bucket(
const key_type& __k)
const
587 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
590 begin(size_type __bkt)
592 return local_iterator(*
this, _M_bucket_begin(__bkt),
593 __bkt, _M_bucket_count);
598 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
601 begin(size_type __bkt)
const
603 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
604 __bkt, _M_bucket_count);
608 end(size_type __bkt)
const
609 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
613 cbegin(size_type __bkt)
const
615 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
616 __bkt, _M_bucket_count);
620 cend(size_type __bkt)
const
621 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
624 load_factor()
const noexcept
626 return static_cast<float>(size()) / static_cast<float>(bucket_count());
635 __rehash_policy()
const
636 {
return _M_rehash_policy; }
639 __rehash_policy(
const _RehashPolicy& __pol)
640 { _M_rehash_policy = __pol; }
644 find(
const key_type& __k);
647 find(
const key_type& __k)
const;
650 count(
const key_type& __k)
const;
653 equal_range(
const key_type& __k);
656 equal_range(
const key_type& __k)
const;
662 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
665 _M_bucket_index(
const key_type& __k, __hash_code __c)
const
666 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
671 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
674 _M_find_node(size_type __bkt,
const key_type& __key,
675 __hash_code __c)
const
677 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
679 return static_cast<__node_type*>(__before_n->_M_nxt);
689 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
690 size_type __next_bkt);
694 _M_get_previous_node(size_type __bkt, __node_base* __n);
700 _M_insert_unique_node(
const key_type& __k, size_type __bkt,
702 size_type __n_elt = 1);
707 _M_insert_multi_node(
__node_type* __hint,
const key_type& __k,
710 template<
typename... _Args>
712 _M_emplace(
true_type, _Args&&... __args);
714 template<
typename... _Args>
716 _M_emplace(
false_type __uk, _Args&&... __args)
717 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
720 template<
typename... _Args>
722 _M_emplace(const_iterator,
true_type __uk, _Args&&... __args)
723 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
725 template<
typename... _Args>
727 _M_emplace(const_iterator,
false_type, _Args&&... __args);
729 template<
typename _Arg,
typename _NodeGenerator>
731 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type, size_type = 1);
733 template<
typename _Arg,
typename _NodeGenerator>
735 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
738 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
743 template<
typename _Arg,
typename _NodeGenerator>
745 _M_insert(const_iterator, _Arg&& __arg,
746 const _NodeGenerator& __node_gen,
true_type __uk)
749 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
753 template<
typename _Arg,
typename _NodeGenerator>
755 _M_insert(const_iterator, _Arg&&,
765 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
769 template<
typename... _Args>
771 emplace(_Args&&... __args)
772 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
774 template<
typename... _Args>
776 emplace_hint(const_iterator __hint, _Args&&... __args)
778 return _M_emplace(__hint, __unique_keys(),
779 std::forward<_Args>(__args)...);
786 erase(const_iterator);
791 {
return erase(const_iterator(__it)); }
794 erase(
const key_type& __k)
795 {
return _M_erase(__unique_keys(), __k); }
798 erase(const_iterator, const_iterator);
805 void rehash(size_type __bkt_count);
810 #if __cplusplus > 201402L
813 _M_reinsert_node(node_type&& __nh)
815 insert_return_type __ret;
817 __ret.position =
end();
820 __glibcxx_assert(get_allocator() == __nh.get_allocator());
822 const key_type& __k = __nh._M_key();
823 __hash_code __code = this->_M_hash_code(__k);
824 size_type __bkt = _M_bucket_index(__k, __code);
825 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
828 __ret.position = iterator(__n);
829 __ret.inserted =
false;
834 = _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr);
835 __nh._M_ptr =
nullptr;
836 __ret.inserted =
true;
844 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
849 __glibcxx_assert(get_allocator() == __nh.get_allocator());
851 const key_type& __k = __nh._M_key();
852 auto __code = this->_M_hash_code(__k);
854 = _M_insert_multi_node(__hint._M_cur, __k, __code, __nh._M_ptr);
855 __nh._M_ptr =
nullptr;
861 _M_extract_node(
size_t __bkt, __node_base* __prev_n)
863 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
864 if (__prev_n == _M_buckets[__bkt])
865 _M_remove_bucket_begin(__bkt, __n->_M_next(),
866 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
867 else if (__n->_M_nxt)
869 size_type __next_bkt = _M_bucket_index(__n->_M_next());
870 if (__next_bkt != __bkt)
871 _M_buckets[__next_bkt] = __prev_n;
874 __prev_n->_M_nxt = __n->_M_nxt;
875 __n->_M_nxt =
nullptr;
877 return { __n, this->_M_node_allocator() };
883 extract(const_iterator __pos)
885 size_t __bkt = _M_bucket_index(__pos._M_cur);
886 return _M_extract_node(__bkt,
887 _M_get_previous_node(__bkt, __pos._M_cur));
892 extract(
const _Key& __k)
895 __hash_code __code = this->_M_hash_code(__k);
896 std::size_t __bkt = _M_bucket_index(__k, __code);
897 if (__node_base* __prev_node = _M_find_before_node(__bkt, __k, __code))
898 __nh = _M_extract_node(__bkt, __prev_node);
903 template<
typename _Compatible_Hashtable>
905 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
907 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
908 node_type>,
"Node types are compatible");
909 __glibcxx_assert(get_allocator() == __src.get_allocator());
911 auto __n_elt = __src.size();
912 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
915 const key_type& __k = this->_M_extract()(*__pos);
916 __hash_code __code = this->_M_hash_code(__k);
917 size_type __bkt = _M_bucket_index(__k, __code);
918 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
920 auto __nh = __src.extract(__pos);
921 _M_insert_unique_node(__k, __bkt, __code, __nh._M_ptr,
923 __nh._M_ptr =
nullptr;
926 else if (__n_elt != 1)
932 template<
typename _Compatible_Hashtable>
934 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
936 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
937 node_type>,
"Node types are compatible");
938 __glibcxx_assert(get_allocator() == __src.get_allocator());
940 this->reserve(size() + __src.size());
941 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
942 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
948 void _M_rehash_aux(size_type __bkt_count,
true_type);
951 void _M_rehash_aux(size_type __bkt_count,
false_type);
955 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
960 template<
typename _Key,
typename _Value,
961 typename _Alloc,
typename _ExtractKey,
typename _Equal,
962 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
965 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
966 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
967 _M_bucket_begin(size_type __bkt)
const
970 __node_base* __n = _M_buckets[__bkt];
971 return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr;
974 template<
typename _Key,
typename _Value,
975 typename _Alloc,
typename _ExtractKey,
typename _Equal,
976 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
978 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
979 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
980 _Hashtable(size_type __bkt_count_hint,
981 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
982 const _Equal& __eq,
const _ExtractKey& __exk,
983 const allocator_type& __a)
984 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
986 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
987 if (__bkt_count > _M_bucket_count)
989 _M_buckets = _M_allocate_buckets(__bkt_count);
990 _M_bucket_count = __bkt_count;
994 template<
typename _Key,
typename _Value,
995 typename _Alloc,
typename _ExtractKey,
typename _Equal,
996 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
998 template<
typename _InputIterator>
999 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1000 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1001 _Hashtable(_InputIterator __f, _InputIterator __l,
1002 size_type __bkt_count_hint,
1003 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
1004 const _Equal& __eq,
const _ExtractKey& __exk,
1005 const allocator_type& __a)
1006 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
1008 auto __nb_elems = __detail::__distance_fw(__f, __l);
1010 _M_rehash_policy._M_next_bkt(
1011 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1014 if (__bkt_count > _M_bucket_count)
1016 _M_buckets = _M_allocate_buckets(__bkt_count);
1017 _M_bucket_count = __bkt_count;
1020 for (; __f != __l; ++__f)
1024 template<
typename _Key,
typename _Value,
1025 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1026 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1029 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1030 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1031 operator=(
const _Hashtable& __ht)
1037 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1039 auto& __this_alloc = this->_M_node_allocator();
1040 auto& __that_alloc = __ht._M_node_allocator();
1041 if (!__node_alloc_traits::_S_always_equal()
1042 && __this_alloc != __that_alloc)
1045 this->_M_deallocate_nodes(_M_begin());
1046 _M_before_begin._M_nxt =
nullptr;
1047 _M_deallocate_buckets();
1048 _M_buckets =
nullptr;
1049 std::__alloc_on_copy(__this_alloc, __that_alloc);
1050 __hashtable_base::operator=(__ht);
1051 _M_bucket_count = __ht._M_bucket_count;
1052 _M_element_count = __ht._M_element_count;
1053 _M_rehash_policy = __ht._M_rehash_policy;
1057 [
this](
const __node_type* __n)
1058 {
return this->_M_allocate_node(__n->_M_v()); });
1065 __throw_exception_again;
1069 std::__alloc_on_copy(__this_alloc, __that_alloc);
1073 _M_assign_elements(__ht,
1074 [](
const __reuse_or_alloc_node_gen_t& __roan,
const __node_type* __n)
1075 {
return __roan(__n->_M_v()); });
1079 template<
typename _Key,
typename _Value,
1080 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1081 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1083 template<
typename _Ht,
typename _NodeGenerator>
1085 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1086 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1087 _M_assign_elements(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1089 __bucket_type* __former_buckets =
nullptr;
1090 std::size_t __former_bucket_count = _M_bucket_count;
1091 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1093 if (_M_bucket_count != __ht._M_bucket_count)
1095 __former_buckets = _M_buckets;
1096 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1097 _M_bucket_count = __ht._M_bucket_count;
1100 __builtin_memset(_M_buckets, 0,
1101 _M_bucket_count *
sizeof(__bucket_type));
1105 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1106 _M_element_count = __ht._M_element_count;
1107 _M_rehash_policy = __ht._M_rehash_policy;
1108 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1109 _M_before_begin._M_nxt =
nullptr;
1111 [&__node_gen, &__roan](__node_type* __n)
1112 {
return __node_gen(__roan, __n); });
1113 if (__former_buckets)
1114 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1118 if (__former_buckets)
1121 _M_deallocate_buckets();
1122 _M_rehash_policy._M_reset(__former_state);
1123 _M_buckets = __former_buckets;
1124 _M_bucket_count = __former_bucket_count;
1126 __builtin_memset(_M_buckets, 0,
1127 _M_bucket_count *
sizeof(__bucket_type));
1128 __throw_exception_again;
1132 template<
typename _Key,
typename _Value,
1133 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1134 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1136 template<
typename _NodeGenerator>
1138 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1139 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1140 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
1142 __bucket_type* __buckets =
nullptr;
1144 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1148 if (!__ht._M_before_begin._M_nxt)
1153 __node_type* __ht_n = __ht._M_begin();
1154 __node_type* __this_n = __node_gen(__ht_n);
1155 this->_M_copy_code(__this_n, __ht_n);
1156 _M_before_begin._M_nxt = __this_n;
1157 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1160 __node_base* __prev_n = __this_n;
1161 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1163 __this_n = __node_gen(__ht_n);
1164 __prev_n->_M_nxt = __this_n;
1165 this->_M_copy_code(__this_n, __ht_n);
1166 size_type __bkt = _M_bucket_index(__this_n);
1167 if (!_M_buckets[__bkt])
1168 _M_buckets[__bkt] = __prev_n;
1169 __prev_n = __this_n;
1176 _M_deallocate_buckets();
1177 __throw_exception_again;
1181 template<
typename _Key,
typename _Value,
1182 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1183 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1186 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1187 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1190 _M_rehash_policy._M_reset();
1191 _M_bucket_count = 1;
1192 _M_single_bucket =
nullptr;
1193 _M_buckets = &_M_single_bucket;
1194 _M_before_begin._M_nxt =
nullptr;
1195 _M_element_count = 0;
1198 template<
typename _Key,
typename _Value,
1199 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1200 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1203 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1204 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1205 _M_move_assign(_Hashtable&& __ht,
true_type)
1207 this->_M_deallocate_nodes(_M_begin());
1208 _M_deallocate_buckets();
1209 __hashtable_base::operator=(
std::move(__ht));
1210 _M_rehash_policy = __ht._M_rehash_policy;
1211 if (!__ht._M_uses_single_bucket())
1212 _M_buckets = __ht._M_buckets;
1215 _M_buckets = &_M_single_bucket;
1216 _M_single_bucket = __ht._M_single_bucket;
1218 _M_bucket_count = __ht._M_bucket_count;
1219 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1220 _M_element_count = __ht._M_element_count;
1221 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1226 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1230 template<
typename _Key,
typename _Value,
1231 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1232 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1235 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1236 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1237 _M_move_assign(_Hashtable&& __ht,
false_type)
1239 if (__ht._M_node_allocator() == this->_M_node_allocator())
1245 [](
const __reuse_or_alloc_node_gen_t& __roan, __node_type* __n)
1251 template<
typename _Key,
typename _Value,
1252 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1253 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1255 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1256 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1257 _Hashtable(
const _Hashtable& __ht)
1258 : __hashtable_base(__ht),
1260 __rehash_base(__ht),
1262 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1263 _M_buckets(nullptr),
1264 _M_bucket_count(__ht._M_bucket_count),
1265 _M_element_count(__ht._M_element_count),
1266 _M_rehash_policy(__ht._M_rehash_policy)
1269 [
this](
const __node_type* __n)
1270 {
return this->_M_allocate_node(__n->_M_v()); });
1273 template<
typename _Key,
typename _Value,
1274 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1275 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1277 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1278 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1279 _Hashtable(_Hashtable&& __ht) noexcept
1280 : __hashtable_base(__ht),
1282 __rehash_base(__ht),
1283 __hashtable_alloc(
std::move(__ht._M_base_alloc())),
1284 _M_buckets(__ht._M_buckets),
1285 _M_bucket_count(__ht._M_bucket_count),
1286 _M_before_begin(__ht._M_before_begin._M_nxt),
1287 _M_element_count(__ht._M_element_count),
1288 _M_rehash_policy(__ht._M_rehash_policy)
1291 if (__ht._M_uses_single_bucket())
1293 _M_buckets = &_M_single_bucket;
1294 _M_single_bucket = __ht._M_single_bucket;
1300 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
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(
const _Hashtable& __ht,
const allocator_type& __a)
1312 : __hashtable_base(__ht),
1314 __rehash_base(__ht),
1315 __hashtable_alloc(__node_alloc_type(__a)),
1317 _M_bucket_count(__ht._M_bucket_count),
1318 _M_element_count(__ht._M_element_count),
1319 _M_rehash_policy(__ht._M_rehash_policy)
1322 [
this](
const __node_type* __n)
1323 {
return this->_M_allocate_node(__n->_M_v()); });
1326 template<
typename _Key,
typename _Value,
1327 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1328 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1330 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1331 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1332 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
1333 : __hashtable_base(__ht),
1335 __rehash_base(__ht),
1336 __hashtable_alloc(__node_alloc_type(__a)),
1337 _M_buckets(nullptr),
1338 _M_bucket_count(__ht._M_bucket_count),
1339 _M_element_count(__ht._M_element_count),
1340 _M_rehash_policy(__ht._M_rehash_policy)
1342 if (__ht._M_node_allocator() == this->_M_node_allocator())
1344 if (__ht._M_uses_single_bucket())
1346 _M_buckets = &_M_single_bucket;
1347 _M_single_bucket = __ht._M_single_bucket;
1350 _M_buckets = __ht._M_buckets;
1352 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1356 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1362 [
this](__node_type* __n)
1364 return this->_M_allocate_node(
1371 template<
typename _Key,
typename _Value,
1372 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1373 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1375 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1376 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1377 ~_Hashtable() noexcept
1380 _M_deallocate_buckets();
1383 template<
typename _Key,
typename _Value,
1384 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1385 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1388 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1389 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1390 swap(_Hashtable& __x)
1391 noexcept(__and_<__is_nothrow_swappable<_H1>,
1392 __is_nothrow_swappable<_Equal>>::value)
1399 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1400 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1403 if (this->_M_uses_single_bucket())
1405 if (!__x._M_uses_single_bucket())
1407 _M_buckets = __x._M_buckets;
1408 __x._M_buckets = &__x._M_single_bucket;
1411 else if (__x._M_uses_single_bucket())
1413 __x._M_buckets = _M_buckets;
1414 _M_buckets = &_M_single_bucket;
1417 std::swap(_M_buckets, __x._M_buckets);
1419 std::swap(_M_bucket_count, __x._M_bucket_count);
1420 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1421 std::swap(_M_element_count, __x._M_element_count);
1422 std::swap(_M_single_bucket, __x._M_single_bucket);
1427 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1430 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1431 = &__x._M_before_begin;
1434 template<
typename _Key,
typename _Value,
1435 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1436 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1439 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1440 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1441 find(
const key_type& __k)
1444 __hash_code __code = this->_M_hash_code(__k);
1445 std::size_t __bkt = _M_bucket_index(__k, __code);
1446 __node_type* __p = _M_find_node(__bkt, __k, __code);
1447 return __p ? iterator(__p) :
end();
1450 template<
typename _Key,
typename _Value,
1451 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1452 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1455 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1456 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1457 find(
const key_type& __k)
const
1460 __hash_code __code = this->_M_hash_code(__k);
1461 std::size_t __bkt = _M_bucket_index(__k, __code);
1462 __node_type* __p = _M_find_node(__bkt, __k, __code);
1463 return __p ? const_iterator(__p) :
end();
1466 template<
typename _Key,
typename _Value,
1467 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1468 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1471 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1472 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1473 count(
const key_type& __k)
const
1476 __hash_code __code = this->_M_hash_code(__k);
1477 std::size_t __bkt = _M_bucket_index(__k, __code);
1478 __node_type* __p = _M_bucket_begin(__bkt);
1482 std::size_t __result = 0;
1483 for (;; __p = __p->_M_next())
1485 if (this->_M_equals(__k, __code, __p))
1492 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
1498 template<
typename _Key,
typename _Value,
1499 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1500 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1503 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1504 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1505 equal_range(
const key_type& __k)
1506 -> pair<iterator, iterator>
1508 __hash_code __code = this->_M_hash_code(__k);
1509 std::size_t __bkt = _M_bucket_index(__k, __code);
1510 __node_type* __p = _M_find_node(__bkt, __k, __code);
1514 __node_type* __p1 = __p->_M_next();
1515 while (__p1 && _M_bucket_index(__p1) == __bkt
1516 && this->_M_equals(__k, __code, __p1))
1517 __p1 = __p1->_M_next();
1519 return std::make_pair(iterator(__p), iterator(__p1));
1522 return std::make_pair(
end(),
end());
1525 template<
typename _Key,
typename _Value,
1526 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1527 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1530 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1531 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1532 equal_range(
const key_type& __k)
const
1533 -> pair<const_iterator, const_iterator>
1535 __hash_code __code = this->_M_hash_code(__k);
1536 std::size_t __bkt = _M_bucket_index(__k, __code);
1537 __node_type* __p = _M_find_node(__bkt, __k, __code);
1541 __node_type* __p1 = __p->_M_next();
1542 while (__p1 && _M_bucket_index(__p1) == __bkt
1543 && this->_M_equals(__k, __code, __p1))
1544 __p1 = __p1->_M_next();
1546 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1549 return std::make_pair(
end(),
end());
1554 template<
typename _Key,
typename _Value,
1555 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1556 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1559 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1560 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1561 _M_find_before_node(size_type __bkt,
const key_type& __k,
1562 __hash_code __code)
const
1565 __node_base* __prev_p = _M_buckets[__bkt];
1569 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1570 __p = __p->_M_next())
1572 if (this->_M_equals(__k, __code, __p))
1575 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __bkt)
1582 template<
typename _Key,
typename _Value,
1583 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1584 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1587 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1588 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1589 _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
1591 if (_M_buckets[__bkt])
1595 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1596 _M_buckets[__bkt]->_M_nxt = __node;
1603 __node->_M_nxt = _M_before_begin._M_nxt;
1604 _M_before_begin._M_nxt = __node;
1608 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1609 _M_buckets[__bkt] = &_M_before_begin;
1613 template<
typename _Key,
typename _Value,
1614 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1615 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1618 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1619 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1620 _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
1621 size_type __next_bkt)
1623 if (!__next || __next_bkt != __bkt)
1628 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1631 if (&_M_before_begin == _M_buckets[__bkt])
1632 _M_before_begin._M_nxt = __next;
1633 _M_buckets[__bkt] =
nullptr;
1637 template<
typename _Key,
typename _Value,
1638 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1639 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1642 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1643 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1644 _M_get_previous_node(size_type __bkt, __node_base* __n)
1647 __node_base* __prev_n = _M_buckets[__bkt];
1648 while (__prev_n->_M_nxt != __n)
1649 __prev_n = __prev_n->_M_nxt;
1653 template<
typename _Key,
typename _Value,
1654 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1655 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1657 template<
typename... _Args>
1659 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1660 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1661 _M_emplace(
true_type, _Args&&... __args)
1662 -> pair<iterator, bool>
1665 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1666 const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
1667 __hash_code __code = this->_M_hash_code(__k);
1668 size_type __bkt = _M_bucket_index(__k, __code);
1669 if (__node_type* __p = _M_find_node(__bkt, __k, __code))
1671 return std::make_pair(iterator(__p),
false);
1674 auto __pos = _M_insert_unique_node(__k, __bkt, __code, __node._M_node);
1675 __node._M_node =
nullptr;
1676 return { __pos,
true };
1679 template<
typename _Key,
typename _Value,
1680 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1681 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1683 template<
typename... _Args>
1685 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1686 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1687 _M_emplace(const_iterator __hint,
false_type, _Args&&... __args)
1691 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1692 const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
1694 __hash_code __code = this->_M_hash_code(__k);
1696 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
1697 __node._M_node =
nullptr;
1701 template<
typename _Key,
typename _Value,
1702 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1703 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1706 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1707 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1708 _M_insert_unique_node(
const key_type& __k, size_type __bkt,
1709 __hash_code __code, __node_type* __node,
1713 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1715 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1718 if (__do_rehash.
first)
1720 _M_rehash(__do_rehash.
second, __saved_state);
1721 __bkt = _M_bucket_index(__k, __code);
1724 this->_M_store_code(__node, __code);
1727 _M_insert_bucket_begin(__bkt, __node);
1729 return iterator(__node);
1732 template<
typename _Key,
typename _Value,
1733 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1734 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1737 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1738 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1739 _M_insert_multi_node(__node_type* __hint,
const key_type& __k,
1740 __hash_code __code, __node_type* __node)
1743 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1745 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1747 if (__do_rehash.
first)
1748 _M_rehash(__do_rehash.
second, __saved_state);
1750 this->_M_store_code(__node, __code);
1751 size_type __bkt = _M_bucket_index(__k, __code);
1756 = __builtin_expect(__hint !=
nullptr,
false)
1757 && this->_M_equals(__k, __code, __hint)
1759 : _M_find_before_node(__bkt, __k, __code);
1763 __node->_M_nxt = __prev->_M_nxt;
1764 __prev->_M_nxt = __node;
1765 if (__builtin_expect(__prev == __hint,
false))
1769 && !this->_M_equals(__k, __code, __node->_M_next()))
1771 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1772 if (__next_bkt != __bkt)
1773 _M_buckets[__next_bkt] = __node;
1780 _M_insert_bucket_begin(__bkt, __node);
1782 return iterator(__node);
1786 template<
typename _Key,
typename _Value,
1787 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1788 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1790 template<
typename _Arg,
typename _NodeGenerator>
1792 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1793 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1794 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
true_type,
1796 -> pair<iterator, bool>
1798 const key_type& __k = this->_M_extract()(__v);
1799 __hash_code __code = this->_M_hash_code(__k);
1800 size_type __bkt = _M_bucket_index(__k, __code);
1802 if (__node_type* __node = _M_find_node(__bkt, __k, __code))
1803 return { iterator(__node),
false };
1805 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
1807 = _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
1808 __node._M_node =
nullptr;
1809 return { __pos,
true };
1813 template<
typename _Key,
typename _Value,
1814 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1815 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1817 template<
typename _Arg,
typename _NodeGenerator>
1819 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1820 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1821 _M_insert(const_iterator __hint, _Arg&& __v,
1822 const _NodeGenerator& __node_gen,
false_type)
1827 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1830 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
1831 const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
1833 = _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
1834 __node._M_node =
nullptr;
1838 template<
typename _Key,
typename _Value,
1839 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1840 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1843 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1844 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1845 erase(const_iterator __it)
1848 __node_type* __n = __it._M_cur;
1849 std::size_t __bkt = _M_bucket_index(__n);
1854 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1855 return _M_erase(__bkt, __prev_n, __n);
1858 template<
typename _Key,
typename _Value,
1859 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1860 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1863 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1864 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1865 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
1868 if (__prev_n == _M_buckets[__bkt])
1869 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1870 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1871 else if (__n->_M_nxt)
1873 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1874 if (__next_bkt != __bkt)
1875 _M_buckets[__next_bkt] = __prev_n;
1878 __prev_n->_M_nxt = __n->_M_nxt;
1879 iterator __result(__n->_M_next());
1880 this->_M_deallocate_node(__n);
1886 template<
typename _Key,
typename _Value,
1887 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1888 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1891 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1892 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1893 _M_erase(
true_type,
const key_type& __k)
1896 __hash_code __code = this->_M_hash_code(__k);
1897 std::size_t __bkt = _M_bucket_index(__k, __code);
1900 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1905 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
1906 _M_erase(__bkt, __prev_n, __n);
1910 template<
typename _Key,
typename _Value,
1911 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1912 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1915 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1916 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1920 __hash_code __code = this->_M_hash_code(__k);
1921 std::size_t __bkt = _M_bucket_index(__k, __code);
1924 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1934 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
1935 __node_type* __n_last = __n;
1936 std::size_t __n_last_bkt = __bkt;
1939 __n_last = __n_last->_M_next();
1942 __n_last_bkt = _M_bucket_index(__n_last);
1944 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1947 size_type __result = 0;
1950 __node_type* __p = __n->_M_next();
1951 this->_M_deallocate_node(__n);
1956 while (__n != __n_last);
1958 if (__prev_n == _M_buckets[__bkt])
1959 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1960 else if (__n_last && __n_last_bkt != __bkt)
1961 _M_buckets[__n_last_bkt] = __prev_n;
1962 __prev_n->_M_nxt = __n_last;
1966 template<
typename _Key,
typename _Value,
1967 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1968 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1971 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1972 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1973 erase(const_iterator __first, const_iterator __last)
1976 __node_type* __n = __first._M_cur;
1977 __node_type* __last_n = __last._M_cur;
1978 if (__n == __last_n)
1979 return iterator(__n);
1981 std::size_t __bkt = _M_bucket_index(__n);
1983 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1984 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1985 std::size_t __n_bkt = __bkt;
1990 __node_type* __tmp = __n;
1991 __n = __n->_M_next();
1992 this->_M_deallocate_node(__tmp);
1996 __n_bkt = _M_bucket_index(__n);
1998 while (__n != __last_n && __n_bkt == __bkt);
1999 if (__is_bucket_begin)
2000 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2001 if (__n == __last_n)
2003 __is_bucket_begin =
true;
2007 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2008 _M_buckets[__n_bkt] = __prev_n;
2009 __prev_n->_M_nxt = __n;
2010 return iterator(__n);
2013 template<
typename _Key,
typename _Value,
2014 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2015 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2018 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2019 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2022 this->_M_deallocate_nodes(_M_begin());
2023 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2024 _M_element_count = 0;
2025 _M_before_begin._M_nxt =
nullptr;
2028 template<
typename _Key,
typename _Value,
2029 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2030 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2033 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2034 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2035 rehash(size_type __bkt_count)
2037 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2039 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2041 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2043 if (__bkt_count != _M_bucket_count)
2044 _M_rehash(__bkt_count, __saved_state);
2048 _M_rehash_policy._M_reset(__saved_state);
2051 template<
typename _Key,
typename _Value,
2052 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2053 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2056 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2057 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2058 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2062 _M_rehash_aux(__bkt_count, __unique_keys());
2068 _M_rehash_policy._M_reset(__state);
2069 __throw_exception_again;
2074 template<
typename _Key,
typename _Value,
2075 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2076 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2079 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2080 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2081 _M_rehash_aux(size_type __bkt_count,
true_type)
2083 __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
2084 __node_type* __p = _M_begin();
2085 _M_before_begin._M_nxt =
nullptr;
2086 std::size_t __bbegin_bkt = 0;
2089 __node_type* __next = __p->_M_next();
2091 = __hash_code_base::_M_bucket_index(__p, __bkt_count);
2092 if (!__new_buckets[__bkt])
2094 __p->_M_nxt = _M_before_begin._M_nxt;
2095 _M_before_begin._M_nxt = __p;
2096 __new_buckets[__bkt] = &_M_before_begin;
2098 __new_buckets[__bbegin_bkt] = __p;
2099 __bbegin_bkt = __bkt;
2103 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2104 __new_buckets[__bkt]->_M_nxt = __p;
2109 _M_deallocate_buckets();
2110 _M_bucket_count = __bkt_count;
2111 _M_buckets = __new_buckets;
2116 template<
typename _Key,
typename _Value,
2117 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2118 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2121 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2122 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2123 _M_rehash_aux(size_type __bkt_count,
false_type)
2125 __bucket_type* __new_buckets = _M_allocate_buckets(__bkt_count);
2127 __node_type* __p = _M_begin();
2128 _M_before_begin._M_nxt =
nullptr;
2129 std::size_t __bbegin_bkt = 0;
2130 std::size_t __prev_bkt = 0;
2131 __node_type* __prev_p =
nullptr;
2132 bool __check_bucket =
false;
2136 __node_type* __next = __p->_M_next();
2138 = __hash_code_base::_M_bucket_index(__p, __bkt_count);
2140 if (__prev_p && __prev_bkt == __bkt)
2145 __p->_M_nxt = __prev_p->_M_nxt;
2146 __prev_p->_M_nxt = __p;
2153 __check_bucket =
true;
2161 if (__prev_p->_M_nxt)
2163 std::size_t __next_bkt
2164 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2166 if (__next_bkt != __prev_bkt)
2167 __new_buckets[__next_bkt] = __prev_p;
2169 __check_bucket =
false;
2172 if (!__new_buckets[__bkt])
2174 __p->_M_nxt = _M_before_begin._M_nxt;
2175 _M_before_begin._M_nxt = __p;
2176 __new_buckets[__bkt] = &_M_before_begin;
2178 __new_buckets[__bbegin_bkt] = __p;
2179 __bbegin_bkt = __bkt;
2183 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2184 __new_buckets[__bkt]->_M_nxt = __p;
2192 if (__check_bucket && __prev_p->_M_nxt)
2194 std::size_t __next_bkt
2195 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2197 if (__next_bkt != __prev_bkt)
2198 __new_buckets[__next_bkt] = __prev_p;
2201 _M_deallocate_buckets();
2202 _M_bucket_count = __bkt_count;
2203 _M_buckets = __new_buckets;
2206 #if __cplusplus > 201402L
2207 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2210 #if __cpp_deduction_guides >= 201606
2212 template<
typename _Hash>
2213 using _RequireNotAllocatorOrIntegral
2214 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2217 _GLIBCXX_END_NAMESPACE_VERSION
2220 #endif // _HASHTABLE_H