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");
195 static_assert(__is_invocable<const _H1&, const _Key&>{},
196 "hash function must be invocable with an argument of key type");
197 static_assert(__is_invocable<const _Equal&, const _Key&, const _Key&>{},
198 "key equality predicate must be invocable with two arguments of " 201 using __traits_type = _Traits;
202 using __hash_cached =
typename __traits_type::__hash_cached;
204 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
208 using __value_alloc_traits =
209 typename __hashtable_alloc::__value_alloc_traits;
210 using __node_alloc_traits =
216 typedef _Key key_type;
217 typedef _Value value_type;
218 typedef _Alloc allocator_type;
219 typedef _Equal key_equal;
223 typedef typename __value_alloc_traits::pointer pointer;
224 typedef typename __value_alloc_traits::const_pointer const_pointer;
225 typedef value_type& reference;
226 typedef const value_type& const_reference;
229 using __rehash_type = _RehashPolicy;
230 using __rehash_state =
typename __rehash_type::_State;
232 using __constant_iterators =
typename __traits_type::__constant_iterators;
233 using __unique_keys =
typename __traits_type::__unique_keys;
236 __constant_iterators::value,
238 __detail::_Select1st>::type;
241 _Hashtable_base<_Key, _Value, _ExtractKey,
242 _Equal, _H1, _H2, _Hash, _Traits>;
245 using __hash_code =
typename __hashtable_base::__hash_code;
246 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
249 _Equal, _H1, _H2, _Hash,
250 _RehashPolicy, _Traits>;
255 _RehashPolicy, _Traits>;
258 _Equal, _H1, _H2, _Hash,
259 _RehashPolicy, _Traits>;
261 using __reuse_or_alloc_node_type =
262 __detail::_ReuseOrAllocNode<__node_alloc_type>;
265 template<
typename _Cond>
266 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
268 template<
typename _Cond>
269 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
275 struct __hash_code_base_access : __hash_code_base
276 {
using __hash_code_base::_M_bucket_index; };
280 static_assert(noexcept(declval<const __hash_code_base_access&>()
283 "Cache the hash code or qualify your functors involved" 284 " in hash code and bucket index computation with noexcept");
292 "Functor used to map hash code to bucket index" 293 " must be default constructible");
295 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
296 typename _ExtractKeya,
typename _Equala,
297 typename _H1a,
typename _H2a,
typename _Hasha,
298 typename _RehashPolicya,
typename _Traitsa,
302 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
303 typename _ExtractKeya,
typename _Equala,
304 typename _H1a,
typename _H2a,
typename _Hasha,
305 typename _RehashPolicya,
typename _Traitsa>
308 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
309 typename _ExtractKeya,
typename _Equala,
310 typename _H1a,
typename _H2a,
typename _Hasha,
311 typename _RehashPolicya,
typename _Traitsa,
312 bool _Constant_iteratorsa>
316 using size_type =
typename __hashtable_base::size_type;
317 using difference_type =
typename __hashtable_base::difference_type;
323 using const_local_iterator =
typename __hashtable_base::
324 const_local_iterator;
326 #if __cplusplus > 201402L 327 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
328 using insert_return_type = _Node_insert_return<iterator, node_type>;
332 __bucket_type* _M_buckets = &_M_single_bucket;
333 size_type _M_bucket_count = 1;
334 __node_base _M_before_begin;
335 size_type _M_element_count = 0;
336 _RehashPolicy _M_rehash_policy;
344 __bucket_type _M_single_bucket =
nullptr;
347 _M_uses_single_bucket(__bucket_type* __bkts)
const 348 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
351 _M_uses_single_bucket()
const 352 {
return _M_uses_single_bucket(_M_buckets); }
355 _M_base_alloc() {
return *
this; }
358 _M_allocate_buckets(size_type __n)
360 if (__builtin_expect(__n == 1,
false))
362 _M_single_bucket =
nullptr;
363 return &_M_single_bucket;
366 return __hashtable_alloc::_M_allocate_buckets(__n);
370 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
372 if (_M_uses_single_bucket(__bkts))
375 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
379 _M_deallocate_buckets()
380 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
385 _M_bucket_begin(size_type __bkt)
const;
389 {
return static_cast<__node_type*>(_M_before_begin._M_nxt); }
393 template<
typename _Ht,
typename _NodeGenerator>
395 _M_assign_elements(_Ht&&,
const _NodeGenerator&);
397 template<
typename _NodeGenerator>
399 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
410 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
411 const _Equal& __eq,
const _ExtractKey& __exk,
412 const allocator_type& __a)
421 const _H1&,
const _H2&,
const _Hash&,
422 const _Equal&,
const _ExtractKey&,
423 const allocator_type&);
425 template<
typename _InputIterator>
426 _Hashtable(_InputIterator __first, _InputIterator __last,
427 size_type __bucket_hint,
428 const _H1&,
const _H2&,
const _Hash&,
429 const _Equal&,
const _ExtractKey&,
430 const allocator_type&);
448 const _H1& __hf = _H1(),
449 const key_equal& __eql = key_equal(),
450 const allocator_type& __a = allocator_type())
451 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
452 __key_extract(), __a)
455 template<
typename _InputIterator>
456 _Hashtable(_InputIterator __f, _InputIterator __l,
458 const _H1& __hf = _H1(),
459 const key_equal& __eql = key_equal(),
460 const allocator_type& __a = allocator_type())
461 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
462 __key_extract(), __a)
467 const _H1& __hf = _H1(),
468 const key_equal& __eql = key_equal(),
469 const allocator_type& __a = allocator_type())
470 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
471 __key_extract(), __a)
479 noexcept(__node_alloc_traits::_S_nothrow_move()
483 constexpr
bool __move_storage =
484 __node_alloc_traits::_S_propagate_on_move_assign()
485 || __node_alloc_traits::_S_always_equal();
493 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
494 _M_before_begin._M_nxt =
nullptr;
496 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys());
504 noexcept(__and_<__is_nothrow_swappable<_H1>,
505 __is_nothrow_swappable<_Equal>>::value);
510 {
return iterator(_M_begin()); }
513 begin()
const noexcept
514 {
return const_iterator(_M_begin()); }
518 {
return iterator(
nullptr); }
522 {
return const_iterator(
nullptr); }
526 {
return const_iterator(_M_begin()); }
529 cend()
const noexcept
530 {
return const_iterator(
nullptr); }
533 size()
const noexcept
534 {
return _M_element_count; }
536 _GLIBCXX_NODISCARD
bool 537 empty()
const noexcept
538 {
return size() == 0; }
541 get_allocator()
const noexcept
542 {
return allocator_type(this->_M_node_allocator()); }
545 max_size()
const noexcept
546 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
551 {
return this->_M_eq(); }
557 bucket_count()
const noexcept
558 {
return _M_bucket_count; }
561 max_bucket_count()
const noexcept
562 {
return max_size(); }
565 bucket_size(size_type __n)
const 569 bucket(
const key_type& __k)
const 570 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
575 return local_iterator(*
this, _M_bucket_begin(__n),
576 __n, _M_bucket_count);
581 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
584 begin(size_type __n)
const 586 return const_local_iterator(*
this, _M_bucket_begin(__n),
587 __n, _M_bucket_count);
591 end(size_type __n)
const 592 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
596 cbegin(size_type __n)
const 598 return const_local_iterator(*
this, _M_bucket_begin(__n),
599 __n, _M_bucket_count);
603 cend(size_type __n)
const 604 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
607 load_factor()
const noexcept
609 return static_cast<float>(size()) / static_cast<float>(bucket_count());
618 __rehash_policy()
const 619 {
return _M_rehash_policy; }
622 __rehash_policy(
const _RehashPolicy& __pol)
623 { _M_rehash_policy = __pol; }
627 find(
const key_type& __k);
630 find(
const key_type& __k)
const;
633 count(
const key_type& __k)
const;
636 equal_range(
const key_type& __k);
639 equal_range(
const key_type& __k)
const;
645 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
648 _M_bucket_index(
const key_type& __k, __hash_code __c)
const 649 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
654 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
657 _M_find_node(size_type __bkt,
const key_type& __key,
658 __hash_code __c)
const 660 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
662 return static_cast<__node_type*>(__before_n->_M_nxt);
672 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
673 size_type __next_bkt);
677 _M_get_previous_node(size_type __bkt, __node_base* __n);
683 _M_insert_unique_node(size_type __bkt, __hash_code __code,
692 template<
typename... _Args>
696 template<
typename... _Args>
699 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
702 template<
typename... _Args>
704 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
705 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
707 template<
typename... _Args>
711 template<
typename _Arg,
typename _NodeGenerator>
713 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type, size_type = 1);
715 template<
typename _Arg,
typename _NodeGenerator>
717 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
720 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
725 template<
typename _Arg,
typename _NodeGenerator>
727 _M_insert(const_iterator, _Arg&& __arg,
728 const _NodeGenerator& __node_gen,
true_type __uk)
731 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
735 template<
typename _Arg,
typename _NodeGenerator>
737 _M_insert(const_iterator, _Arg&&,
747 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
751 template<
typename... _Args>
753 emplace(_Args&&... __args)
754 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
756 template<
typename... _Args>
758 emplace_hint(const_iterator __hint, _Args&&... __args)
760 return _M_emplace(__hint, __unique_keys(),
761 std::forward<_Args>(__args)...);
768 erase(const_iterator);
773 {
return erase(const_iterator(__it)); }
776 erase(
const key_type& __k)
777 {
return _M_erase(__unique_keys(), __k); }
780 erase(const_iterator, const_iterator);
786 void rehash(size_type __n);
791 #if __cplusplus > 201402L 794 _M_reinsert_node(node_type&& __nh)
796 insert_return_type __ret;
798 __ret.position =
end();
801 __glibcxx_assert(get_allocator() == __nh.get_allocator());
803 const key_type& __k = __nh._M_key();
804 __hash_code __code = this->_M_hash_code(__k);
805 size_type __bkt = _M_bucket_index(__k, __code);
806 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
808 __ret.node = std::move(__nh);
809 __ret.position = iterator(__n);
810 __ret.inserted =
false;
815 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
816 __nh._M_ptr =
nullptr;
817 __ret.inserted =
true;
825 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
832 __glibcxx_assert(get_allocator() == __nh.get_allocator());
834 auto __code = this->_M_hash_code(__nh._M_key());
837 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
844 extract(const_iterator __pos)
847 size_t __bkt = _M_bucket_index(__n);
852 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
854 if (__prev_n == _M_buckets[__bkt])
855 _M_remove_bucket_begin(__bkt, __n->_M_next(),
856 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
857 else if (__n->_M_nxt)
859 size_type __next_bkt = _M_bucket_index(__n->_M_next());
860 if (__next_bkt != __bkt)
861 _M_buckets[__next_bkt] = __prev_n;
864 __prev_n->_M_nxt = __n->_M_nxt;
865 __n->_M_nxt =
nullptr;
867 return { __n, this->_M_node_allocator() };
872 extract(
const _Key& __k)
875 auto __pos = find(__k);
877 __nh = extract(const_iterator(__pos));
882 template<
typename _Compatible_Hashtable>
884 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
886 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
887 node_type>,
"Node types are compatible");
888 __glibcxx_assert(get_allocator() == __src.get_allocator());
890 auto __n_elt = __src.size();
891 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
894 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
895 __hash_code __code = this->_M_hash_code(__k);
896 size_type __bkt = _M_bucket_index(__k, __code);
897 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
899 auto __nh = __src.extract(__pos);
900 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
901 __nh._M_ptr =
nullptr;
904 else if (__n_elt != 1)
910 template<
typename _Compatible_Hashtable>
912 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
914 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
915 node_type>,
"Node types are compatible");
916 __glibcxx_assert(get_allocator() == __src.get_allocator());
918 this->reserve(size() + __src.size());
919 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
920 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
933 void _M_rehash(size_type __n,
const __rehash_state& __state);
938 template<
typename _Key,
typename _Value,
939 typename _Alloc,
typename _ExtractKey,
typename _Equal,
940 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
943 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
944 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
945 _M_bucket_begin(size_type __bkt)
const 948 __node_base* __n = _M_buckets[__bkt];
949 return __n ? static_cast<__node_type*>(__n->_M_nxt) : nullptr;
952 template<
typename _Key,
typename _Value,
953 typename _Alloc,
typename _ExtractKey,
typename _Equal,
954 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
956 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
957 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
958 _Hashtable(size_type __bucket_hint,
959 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
960 const _Equal& __eq,
const _ExtractKey& __exk,
961 const allocator_type& __a)
962 : _Hashtable(__h1, __h2, __h, __eq, __exk, __a)
964 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
965 if (__bkt > _M_bucket_count)
967 _M_buckets = _M_allocate_buckets(__bkt);
968 _M_bucket_count = __bkt;
972 template<
typename _Key,
typename _Value,
973 typename _Alloc,
typename _ExtractKey,
typename _Equal,
974 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
976 template<
typename _InputIterator>
977 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
978 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
979 _Hashtable(_InputIterator __f, _InputIterator __l,
980 size_type __bucket_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 __nb_elems = __detail::__distance_fw(__f, __l);
988 _M_rehash_policy._M_next_bkt(
989 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
992 if (__bkt_count > _M_bucket_count)
994 _M_buckets = _M_allocate_buckets(__bkt_count);
995 _M_bucket_count = __bkt_count;
998 for (; __f != __l; ++__f)
1002 template<
typename _Key,
typename _Value,
1003 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1004 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1007 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1008 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1009 operator=(
const _Hashtable& __ht)
1015 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1017 auto& __this_alloc = this->_M_node_allocator();
1018 auto& __that_alloc = __ht._M_node_allocator();
1019 if (!__node_alloc_traits::_S_always_equal()
1020 && __this_alloc != __that_alloc)
1023 this->_M_deallocate_nodes(_M_begin());
1024 _M_before_begin._M_nxt =
nullptr;
1025 _M_deallocate_buckets();
1026 _M_buckets =
nullptr;
1027 std::__alloc_on_copy(__this_alloc, __that_alloc);
1028 __hashtable_base::operator=(__ht);
1029 _M_bucket_count = __ht._M_bucket_count;
1030 _M_element_count = __ht._M_element_count;
1031 _M_rehash_policy = __ht._M_rehash_policy;
1035 [
this](
const __node_type* __n)
1036 {
return this->_M_allocate_node(__n->_M_v()); });
1043 __throw_exception_again;
1047 std::__alloc_on_copy(__this_alloc, __that_alloc);
1051 _M_assign_elements(__ht,
1052 [](
const __reuse_or_alloc_node_type& __roan,
const __node_type* __n)
1053 {
return __roan(__n->_M_v()); });
1057 template<
typename _Key,
typename _Value,
1058 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1059 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1061 template<
typename _Ht,
typename _NodeGenerator>
1063 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1064 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1065 _M_assign_elements(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1067 __bucket_type* __former_buckets =
nullptr;
1068 std::size_t __former_bucket_count = _M_bucket_count;
1069 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1071 if (_M_bucket_count != __ht._M_bucket_count)
1073 __former_buckets = _M_buckets;
1074 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1075 _M_bucket_count = __ht._M_bucket_count;
1078 __builtin_memset(_M_buckets, 0,
1079 _M_bucket_count *
sizeof(__bucket_type));
1083 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1084 _M_element_count = __ht._M_element_count;
1085 _M_rehash_policy = __ht._M_rehash_policy;
1086 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1087 _M_before_begin._M_nxt =
nullptr;
1089 [&__node_gen, &__roan](__node_type* __n)
1090 {
return __node_gen(__roan, __n); });
1091 if (__former_buckets)
1092 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1096 if (__former_buckets)
1099 _M_deallocate_buckets();
1100 _M_rehash_policy._M_reset(__former_state);
1101 _M_buckets = __former_buckets;
1102 _M_bucket_count = __former_bucket_count;
1104 __builtin_memset(_M_buckets, 0,
1105 _M_bucket_count *
sizeof(__bucket_type));
1106 __throw_exception_again;
1110 template<
typename _Key,
typename _Value,
1111 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1112 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1114 template<
typename _NodeGenerator>
1116 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1117 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1118 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
1120 __bucket_type* __buckets =
nullptr;
1122 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1126 if (!__ht._M_before_begin._M_nxt)
1131 __node_type* __ht_n = __ht._M_begin();
1132 __node_type* __this_n = __node_gen(__ht_n);
1133 this->_M_copy_code(__this_n, __ht_n);
1134 _M_before_begin._M_nxt = __this_n;
1135 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1138 __node_base* __prev_n = __this_n;
1139 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1141 __this_n = __node_gen(__ht_n);
1142 __prev_n->_M_nxt = __this_n;
1143 this->_M_copy_code(__this_n, __ht_n);
1144 size_type __bkt = _M_bucket_index(__this_n);
1145 if (!_M_buckets[__bkt])
1146 _M_buckets[__bkt] = __prev_n;
1147 __prev_n = __this_n;
1154 _M_deallocate_buckets();
1155 __throw_exception_again;
1159 template<
typename _Key,
typename _Value,
1160 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1161 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1164 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1165 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1168 _M_rehash_policy._M_reset();
1169 _M_bucket_count = 1;
1170 _M_single_bucket =
nullptr;
1171 _M_buckets = &_M_single_bucket;
1172 _M_before_begin._M_nxt =
nullptr;
1173 _M_element_count = 0;
1176 template<
typename _Key,
typename _Value,
1177 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1178 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1181 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1182 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1185 this->_M_deallocate_nodes(_M_begin());
1186 _M_deallocate_buckets();
1187 __hashtable_base::operator=(std::move(__ht));
1188 _M_rehash_policy = __ht._M_rehash_policy;
1189 if (!__ht._M_uses_single_bucket())
1190 _M_buckets = __ht._M_buckets;
1193 _M_buckets = &_M_single_bucket;
1194 _M_single_bucket = __ht._M_single_bucket;
1196 _M_bucket_count = __ht._M_bucket_count;
1197 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1198 _M_element_count = __ht._M_element_count;
1199 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1204 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1208 template<
typename _Key,
typename _Value,
1209 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1210 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1213 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1214 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1217 if (__ht._M_node_allocator() == this->_M_node_allocator())
1222 _M_assign_elements(std::move(__ht),
1223 [](
const __reuse_or_alloc_node_type& __roan, __node_type* __n)
1229 template<
typename _Key,
typename _Value,
1230 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1231 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1233 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1234 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1235 _Hashtable(
const _Hashtable& __ht)
1236 : __hashtable_base(__ht),
1238 __rehash_base(__ht),
1240 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1241 _M_buckets(nullptr),
1242 _M_bucket_count(__ht._M_bucket_count),
1243 _M_element_count(__ht._M_element_count),
1244 _M_rehash_policy(__ht._M_rehash_policy)
1247 [
this](
const __node_type* __n)
1248 {
return this->_M_allocate_node(__n->_M_v()); });
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(_Hashtable&& __ht) noexcept
1258 : __hashtable_base(__ht),
1260 __rehash_base(__ht),
1261 __hashtable_alloc(std::move(__ht._M_base_alloc())),
1262 _M_buckets(__ht._M_buckets),
1263 _M_bucket_count(__ht._M_bucket_count),
1264 _M_before_begin(__ht._M_before_begin._M_nxt),
1265 _M_element_count(__ht._M_element_count),
1266 _M_rehash_policy(__ht._M_rehash_policy)
1269 if (__ht._M_uses_single_bucket())
1271 _M_buckets = &_M_single_bucket;
1272 _M_single_bucket = __ht._M_single_bucket;
1278 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1283 template<
typename _Key,
typename _Value,
1284 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1285 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1287 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1288 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1289 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1290 : __hashtable_base(__ht),
1292 __rehash_base(__ht),
1293 __hashtable_alloc(__node_alloc_type(__a)),
1295 _M_bucket_count(__ht._M_bucket_count),
1296 _M_element_count(__ht._M_element_count),
1297 _M_rehash_policy(__ht._M_rehash_policy)
1300 [
this](
const __node_type* __n)
1301 {
return this->_M_allocate_node(__n->_M_v()); });
1304 template<
typename _Key,
typename _Value,
1305 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1306 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1308 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1309 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1310 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
1311 : __hashtable_base(__ht),
1313 __rehash_base(__ht),
1314 __hashtable_alloc(__node_alloc_type(__a)),
1315 _M_buckets(nullptr),
1316 _M_bucket_count(__ht._M_bucket_count),
1317 _M_element_count(__ht._M_element_count),
1318 _M_rehash_policy(__ht._M_rehash_policy)
1320 if (__ht._M_node_allocator() == this->_M_node_allocator())
1322 if (__ht._M_uses_single_bucket())
1324 _M_buckets = &_M_single_bucket;
1325 _M_single_bucket = __ht._M_single_bucket;
1328 _M_buckets = __ht._M_buckets;
1330 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1334 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1340 [
this](__node_type* __n)
1342 return this->_M_allocate_node(
1349 template<
typename _Key,
typename _Value,
1350 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1351 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1353 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1354 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1355 ~_Hashtable() noexcept
1358 _M_deallocate_buckets();
1361 template<
typename _Key,
typename _Value,
1362 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1363 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1366 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1367 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1368 swap(_Hashtable& __x)
1369 noexcept(__and_<__is_nothrow_swappable<_H1>,
1370 __is_nothrow_swappable<_Equal>>::value)
1377 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1378 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1381 if (this->_M_uses_single_bucket())
1383 if (!__x._M_uses_single_bucket())
1385 _M_buckets = __x._M_buckets;
1386 __x._M_buckets = &__x._M_single_bucket;
1389 else if (__x._M_uses_single_bucket())
1391 __x._M_buckets = _M_buckets;
1392 _M_buckets = &_M_single_bucket;
1395 std::swap(_M_buckets, __x._M_buckets);
1397 std::swap(_M_bucket_count, __x._M_bucket_count);
1398 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1399 std::swap(_M_element_count, __x._M_element_count);
1400 std::swap(_M_single_bucket, __x._M_single_bucket);
1405 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1408 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1409 = &__x._M_before_begin;
1412 template<
typename _Key,
typename _Value,
1413 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1414 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1417 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1418 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1419 find(
const key_type& __k)
1422 __hash_code __code = this->_M_hash_code(__k);
1423 std::size_t __n = _M_bucket_index(__k, __code);
1424 __node_type* __p = _M_find_node(__n, __k, __code);
1425 return __p ? iterator(__p) :
end();
1428 template<
typename _Key,
typename _Value,
1429 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1430 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1433 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1434 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1435 find(
const key_type& __k)
const 1438 __hash_code __code = this->_M_hash_code(__k);
1439 std::size_t __n = _M_bucket_index(__k, __code);
1440 __node_type* __p = _M_find_node(__n, __k, __code);
1441 return __p ? const_iterator(__p) :
end();
1444 template<
typename _Key,
typename _Value,
1445 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1446 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1449 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1450 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1451 count(
const key_type& __k)
const 1454 __hash_code __code = this->_M_hash_code(__k);
1455 std::size_t __n = _M_bucket_index(__k, __code);
1456 __node_type* __p = _M_bucket_begin(__n);
1460 std::size_t __result = 0;
1461 for (;; __p = __p->_M_next())
1463 if (this->_M_equals(__k, __code, __p))
1470 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1476 template<
typename _Key,
typename _Value,
1477 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1478 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1481 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1482 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1483 equal_range(
const key_type& __k)
1484 -> pair<iterator, iterator>
1486 __hash_code __code = this->_M_hash_code(__k);
1487 std::size_t __n = _M_bucket_index(__k, __code);
1488 __node_type* __p = _M_find_node(__n, __k, __code);
1492 __node_type* __p1 = __p->_M_next();
1493 while (__p1 && _M_bucket_index(__p1) == __n
1494 && this->_M_equals(__k, __code, __p1))
1495 __p1 = __p1->_M_next();
1503 template<
typename _Key,
typename _Value,
1504 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1505 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1508 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1509 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1510 equal_range(
const key_type& __k)
const 1511 -> pair<const_iterator, const_iterator>
1513 __hash_code __code = this->_M_hash_code(__k);
1514 std::size_t __n = _M_bucket_index(__k, __code);
1515 __node_type* __p = _M_find_node(__n, __k, __code);
1519 __node_type* __p1 = __p->_M_next();
1520 while (__p1 && _M_bucket_index(__p1) == __n
1521 && this->_M_equals(__k, __code, __p1))
1522 __p1 = __p1->_M_next();
1524 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1532 template<
typename _Key,
typename _Value,
1533 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1534 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1537 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1538 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1539 _M_find_before_node(size_type __n,
const key_type& __k,
1540 __hash_code __code)
const 1543 __node_base* __prev_p = _M_buckets[__n];
1547 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1548 __p = __p->_M_next())
1550 if (this->_M_equals(__k, __code, __p))
1553 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1560 template<
typename _Key,
typename _Value,
1561 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1562 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1565 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1566 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1567 _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
1569 if (_M_buckets[__bkt])
1573 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1574 _M_buckets[__bkt]->_M_nxt = __node;
1581 __node->_M_nxt = _M_before_begin._M_nxt;
1582 _M_before_begin._M_nxt = __node;
1586 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1587 _M_buckets[__bkt] = &_M_before_begin;
1591 template<
typename _Key,
typename _Value,
1592 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1593 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1596 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1597 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1598 _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
1599 size_type __next_bkt)
1601 if (!__next || __next_bkt != __bkt)
1606 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1609 if (&_M_before_begin == _M_buckets[__bkt])
1610 _M_before_begin._M_nxt = __next;
1611 _M_buckets[__bkt] =
nullptr;
1615 template<
typename _Key,
typename _Value,
1616 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1617 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1620 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1621 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1622 _M_get_previous_node(size_type __bkt, __node_base* __n)
1625 __node_base* __prev_n = _M_buckets[__bkt];
1626 while (__prev_n->_M_nxt != __n)
1627 __prev_n = __prev_n->_M_nxt;
1631 template<
typename _Key,
typename _Value,
1632 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1633 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1635 template<
typename... _Args>
1637 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1638 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1640 -> pair<iterator, bool>
1643 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1644 const key_type& __k = this->_M_extract()(__node->_M_v());
1648 __code = this->_M_hash_code(__k);
1652 this->_M_deallocate_node(__node);
1653 __throw_exception_again;
1656 size_type __bkt = _M_bucket_index(__k, __code);
1657 if (__node_type* __p = _M_find_node(__bkt, __k, __code))
1660 this->_M_deallocate_node(__node);
1665 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1669 template<
typename _Key,
typename _Value,
1670 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1671 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1673 template<
typename... _Args>
1675 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1676 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1681 __node_type* __node =
1682 this->_M_allocate_node(std::forward<_Args>(__args)...);
1687 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1691 this->_M_deallocate_node(__node);
1692 __throw_exception_again;
1695 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1698 template<
typename _Key,
typename _Value,
1699 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1700 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1703 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1704 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1705 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1706 __node_type* __node, size_type __n_elt)
1709 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1711 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1716 if (__do_rehash.
first)
1718 _M_rehash(__do_rehash.
second, __saved_state);
1719 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1722 this->_M_store_code(__node, __code);
1725 _M_insert_bucket_begin(__bkt, __node);
1727 return iterator(__node);
1731 this->_M_deallocate_node(__node);
1732 __throw_exception_again;
1738 template<
typename _Key,
typename _Value,
1739 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1740 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1743 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1744 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1745 _M_insert_multi_node(__node_type* __hint, __hash_code __code,
1746 __node_type* __node)
1749 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1751 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1755 if (__do_rehash.
first)
1756 _M_rehash(__do_rehash.
second, __saved_state);
1758 this->_M_store_code(__node, __code);
1759 const key_type& __k = this->_M_extract()(__node->_M_v());
1760 size_type __bkt = _M_bucket_index(__k, __code);
1765 = __builtin_expect(__hint !=
nullptr,
false)
1766 && this->_M_equals(__k, __code, __hint)
1768 : _M_find_before_node(__bkt, __k, __code);
1772 __node->_M_nxt = __prev->_M_nxt;
1773 __prev->_M_nxt = __node;
1774 if (__builtin_expect(__prev == __hint,
false))
1778 && !this->_M_equals(__k, __code, __node->_M_next()))
1780 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1781 if (__next_bkt != __bkt)
1782 _M_buckets[__next_bkt] = __node;
1790 _M_insert_bucket_begin(__bkt, __node);
1792 return iterator(__node);
1796 this->_M_deallocate_node(__node);
1797 __throw_exception_again;
1802 template<
typename _Key,
typename _Value,
1803 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1804 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1806 template<
typename _Arg,
typename _NodeGenerator>
1808 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1809 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1810 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
true_type,
1812 -> pair<iterator, bool>
1814 const key_type& __k = this->_M_extract()(__v);
1815 __hash_code __code = this->_M_hash_code(__k);
1816 size_type __bkt = _M_bucket_index(__k, __code);
1818 __node_type* __n = _M_find_node(__bkt, __k, __code);
1822 __n = __node_gen(std::forward<_Arg>(__v));
1823 return { _M_insert_unique_node(__bkt, __code, __n, __n_elt),
true };
1827 template<
typename _Key,
typename _Value,
1828 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1829 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1831 template<
typename _Arg,
typename _NodeGenerator>
1833 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1834 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1835 _M_insert(const_iterator __hint, _Arg&& __v,
1836 const _NodeGenerator& __node_gen,
false_type)
1841 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1844 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1846 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1849 template<
typename _Key,
typename _Value,
1850 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1851 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1854 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1855 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1856 erase(const_iterator __it)
1859 __node_type* __n = __it._M_cur;
1860 std::size_t __bkt = _M_bucket_index(__n);
1865 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1866 return _M_erase(__bkt, __prev_n, __n);
1869 template<
typename _Key,
typename _Value,
1870 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1871 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1874 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1875 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1876 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
1879 if (__prev_n == _M_buckets[__bkt])
1880 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1881 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1882 else if (__n->_M_nxt)
1884 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1885 if (__next_bkt != __bkt)
1886 _M_buckets[__next_bkt] = __prev_n;
1889 __prev_n->_M_nxt = __n->_M_nxt;
1890 iterator __result(__n->_M_next());
1891 this->_M_deallocate_node(__n);
1897 template<
typename _Key,
typename _Value,
1898 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1899 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1902 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1903 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1907 __hash_code __code = this->_M_hash_code(__k);
1908 std::size_t __bkt = _M_bucket_index(__k, __code);
1911 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1916 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
1917 _M_erase(__bkt, __prev_n, __n);
1921 template<
typename _Key,
typename _Value,
1922 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1923 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1926 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1927 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1931 __hash_code __code = this->_M_hash_code(__k);
1932 std::size_t __bkt = _M_bucket_index(__k, __code);
1935 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1945 __node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);
1946 __node_type* __n_last = __n;
1947 std::size_t __n_last_bkt = __bkt;
1950 __n_last = __n_last->_M_next();
1953 __n_last_bkt = _M_bucket_index(__n_last);
1955 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1958 size_type __result = 0;
1961 __node_type* __p = __n->_M_next();
1962 this->_M_deallocate_node(__n);
1967 while (__n != __n_last);
1969 if (__prev_n == _M_buckets[__bkt])
1970 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1971 else if (__n_last && __n_last_bkt != __bkt)
1972 _M_buckets[__n_last_bkt] = __prev_n;
1973 __prev_n->_M_nxt = __n_last;
1977 template<
typename _Key,
typename _Value,
1978 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1979 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1982 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1983 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1984 erase(const_iterator __first, const_iterator __last)
1987 __node_type* __n = __first._M_cur;
1988 __node_type* __last_n = __last._M_cur;
1989 if (__n == __last_n)
1990 return iterator(__n);
1992 std::size_t __bkt = _M_bucket_index(__n);
1994 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1995 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1996 std::size_t __n_bkt = __bkt;
2001 __node_type* __tmp = __n;
2002 __n = __n->_M_next();
2003 this->_M_deallocate_node(__tmp);
2007 __n_bkt = _M_bucket_index(__n);
2009 while (__n != __last_n && __n_bkt == __bkt);
2010 if (__is_bucket_begin)
2011 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2012 if (__n == __last_n)
2014 __is_bucket_begin =
true;
2018 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2019 _M_buckets[__n_bkt] = __prev_n;
2020 __prev_n->_M_nxt = __n;
2021 return iterator(__n);
2024 template<
typename _Key,
typename _Value,
2025 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2026 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2029 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2030 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2033 this->_M_deallocate_nodes(_M_begin());
2034 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2035 _M_element_count = 0;
2036 _M_before_begin._M_nxt =
nullptr;
2039 template<
typename _Key,
typename _Value,
2040 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2041 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2044 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2045 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2046 rehash(size_type __n)
2048 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2049 std::size_t __buckets
2050 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2052 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2054 if (__buckets != _M_bucket_count)
2055 _M_rehash(__buckets, __saved_state);
2058 _M_rehash_policy._M_reset(__saved_state);
2061 template<
typename _Key,
typename _Value,
2062 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2063 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2066 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2067 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2068 _M_rehash(size_type __n,
const __rehash_state& __state)
2072 _M_rehash_aux(__n, __unique_keys());
2078 _M_rehash_policy._M_reset(__state);
2079 __throw_exception_again;
2084 template<
typename _Key,
typename _Value,
2085 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2086 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2089 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2090 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2093 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2094 __node_type* __p = _M_begin();
2095 _M_before_begin._M_nxt =
nullptr;
2096 std::size_t __bbegin_bkt = 0;
2099 __node_type* __next = __p->_M_next();
2100 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2101 if (!__new_buckets[__bkt])
2103 __p->_M_nxt = _M_before_begin._M_nxt;
2104 _M_before_begin._M_nxt = __p;
2105 __new_buckets[__bkt] = &_M_before_begin;
2107 __new_buckets[__bbegin_bkt] = __p;
2108 __bbegin_bkt = __bkt;
2112 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2113 __new_buckets[__bkt]->_M_nxt = __p;
2118 _M_deallocate_buckets();
2119 _M_bucket_count = __n;
2120 _M_buckets = __new_buckets;
2125 template<
typename _Key,
typename _Value,
2126 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2127 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2130 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2131 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2134 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2136 __node_type* __p = _M_begin();
2137 _M_before_begin._M_nxt =
nullptr;
2138 std::size_t __bbegin_bkt = 0;
2139 std::size_t __prev_bkt = 0;
2140 __node_type* __prev_p =
nullptr;
2141 bool __check_bucket =
false;
2145 __node_type* __next = __p->_M_next();
2146 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2148 if (__prev_p && __prev_bkt == __bkt)
2153 __p->_M_nxt = __prev_p->_M_nxt;
2154 __prev_p->_M_nxt = __p;
2161 __check_bucket =
true;
2169 if (__prev_p->_M_nxt)
2171 std::size_t __next_bkt
2172 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2174 if (__next_bkt != __prev_bkt)
2175 __new_buckets[__next_bkt] = __prev_p;
2177 __check_bucket =
false;
2180 if (!__new_buckets[__bkt])
2182 __p->_M_nxt = _M_before_begin._M_nxt;
2183 _M_before_begin._M_nxt = __p;
2184 __new_buckets[__bkt] = &_M_before_begin;
2186 __new_buckets[__bbegin_bkt] = __p;
2187 __bbegin_bkt = __bkt;
2191 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2192 __new_buckets[__bkt]->_M_nxt = __p;
2200 if (__check_bucket && __prev_p->_M_nxt)
2202 std::size_t __next_bkt
2203 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2204 if (__next_bkt != __prev_bkt)
2205 __new_buckets[__next_bkt] = __prev_p;
2208 _M_deallocate_buckets();
2209 _M_bucket_count = __n;
2210 _M_buckets = __new_buckets;
2213 #if __cplusplus > 201402L 2214 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2217 _GLIBCXX_END_NAMESPACE_VERSION
2220 #endif // _HASHTABLE_H
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list.
constexpr auto cend(const _Container &__cont) noexcept(noexcept(std::end(__cont))) -> decltype(std::end(__cont))
Return an iterator pointing to one past the last element of the const container.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
ISO C++ entities toplevel namespace is std.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Define a member typedef type to one of two argument types.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_Tp exchange(_Tp &__obj, _Up &&__new_val)
Assign __new_val to __obj and return its previous value.
_T2 second
first is a copy of the first object
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
is_nothrow_move_assignable
Node const_iterators, used to iterate through all the hashtable.
Uniform interface to C++98 and C++11 allocators.
_T1 first
second_type is the second bound type
constexpr conditional< __move_if_noexcept_cond< _Tp >::value, const _Tp &, _Tp && >::type move_if_noexcept(_Tp &__x) noexcept
Conditionally convert a value to an rvalue.
Struct holding two objects of arbitrary type.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
Node iterators, used to iterate through all the hashtable.
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.