31 #define _HASHTABLE_H 1 33 #pragma GCC system_header 36 #if __cplusplus > 201402L 40 namespace std _GLIBCXX_VISIBILITY(default)
42 _GLIBCXX_BEGIN_NAMESPACE_VERSION
44 template<
typename _Tp,
typename _Hash>
47 __is_fast_hash<_Hash>,
49 __detail::__is_noexcept_hash<_Tp, _Hash>>>;
169 template<
typename _Key,
typename _Value,
typename _Alloc,
170 typename _ExtractKey,
typename _Equal,
171 typename _H1,
typename _H2,
typename _Hash,
172 typename _RehashPolicy,
typename _Traits>
175 _H1, _H2, _Hash, _Traits>,
177 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
179 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
181 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
183 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
185 __alloc_rebind<_Alloc,
186 __detail::_Hash_node<_Value,
187 _Traits::__hash_cached::value>>>
189 using __traits_type = _Traits;
190 using __hash_cached =
typename __traits_type::__hash_cached;
192 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
196 using __value_alloc_traits =
198 using __node_alloc_traits =
204 typedef _Key key_type;
205 typedef _Value value_type;
206 typedef _Alloc allocator_type;
207 typedef _Equal key_equal;
211 typedef typename __value_alloc_traits::pointer pointer;
212 typedef typename __value_alloc_traits::const_pointer const_pointer;
213 typedef value_type& reference;
214 typedef const value_type& const_reference;
217 using __rehash_type = _RehashPolicy;
218 using __rehash_state =
typename __rehash_type::_State;
220 using __constant_iterators =
typename __traits_type::__constant_iterators;
221 using __unique_keys =
typename __traits_type::__unique_keys;
223 using __key_extract =
typename std::conditional<
224 __constant_iterators::value,
226 __detail::_Select1st>::type;
229 _Hashtable_base<_Key, _Value, _ExtractKey,
230 _Equal, _H1, _H2, _Hash, _Traits>;
233 using __hash_code =
typename __hashtable_base::__hash_code;
234 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
237 _Equal, _H1, _H2, _Hash,
238 _RehashPolicy, _Traits>;
243 _RehashPolicy, _Traits>;
246 _Equal, _H1, _H2, _Hash,
247 _RehashPolicy, _Traits>;
249 using __reuse_or_alloc_node_type =
250 __detail::_ReuseOrAllocNode<__node_alloc_type>;
253 template<
typename _Cond>
254 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
256 template<
typename _Cond>
257 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
263 struct __hash_code_base_access : __hash_code_base
264 {
using __hash_code_base::_M_bucket_index; };
268 static_assert(noexcept(declval<const __hash_code_base_access&>()
271 "Cache the hash code or qualify your functors involved" 272 " in hash code and bucket index computation with noexcept");
279 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
280 "Functor used to map hash code to bucket index" 281 " must be default constructible");
283 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
284 typename _ExtractKeya,
typename _Equala,
285 typename _H1a,
typename _H2a,
typename _Hasha,
286 typename _RehashPolicya,
typename _Traitsa,
290 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
291 typename _ExtractKeya,
typename _Equala,
292 typename _H1a,
typename _H2a,
typename _Hasha,
293 typename _RehashPolicya,
typename _Traitsa>
296 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
297 typename _ExtractKeya,
typename _Equala,
298 typename _H1a,
typename _H2a,
typename _Hasha,
299 typename _RehashPolicya,
typename _Traitsa,
300 bool _Constant_iteratorsa>
304 using size_type =
typename __hashtable_base::size_type;
305 using difference_type =
typename __hashtable_base::difference_type;
311 using const_local_iterator =
typename __hashtable_base::
312 const_local_iterator;
314 #if __cplusplus > 201402L 315 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
316 using insert_return_type = _Node_insert_return<iterator, node_type>;
320 __bucket_type* _M_buckets = &_M_single_bucket;
321 size_type _M_bucket_count = 1;
322 __node_base _M_before_begin;
323 size_type _M_element_count = 0;
324 _RehashPolicy _M_rehash_policy;
332 __bucket_type _M_single_bucket =
nullptr;
335 _M_uses_single_bucket(__bucket_type* __bkts)
const 336 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
339 _M_uses_single_bucket()
const 340 {
return _M_uses_single_bucket(_M_buckets); }
343 _M_base_alloc() {
return *
this; }
346 _M_allocate_buckets(size_type __n)
348 if (__builtin_expect(__n == 1,
false))
350 _M_single_bucket =
nullptr;
351 return &_M_single_bucket;
354 return __hashtable_alloc::_M_allocate_buckets(__n);
358 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
360 if (_M_uses_single_bucket(__bkts))
363 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
367 _M_deallocate_buckets()
368 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
373 _M_bucket_begin(size_type __bkt)
const;
377 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
379 template<
typename _NodeGenerator>
381 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
392 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
393 const _Equal& __eq,
const _ExtractKey& __exk,
394 const allocator_type& __a)
403 const _H1&,
const _H2&,
const _Hash&,
404 const _Equal&,
const _ExtractKey&,
405 const allocator_type&);
407 template<
typename _InputIterator>
408 _Hashtable(_InputIterator __first, _InputIterator __last,
409 size_type __bucket_hint,
410 const _H1&,
const _H2&,
const _Hash&,
411 const _Equal&,
const _ExtractKey&,
412 const allocator_type&);
430 const _H1& __hf = _H1(),
431 const key_equal& __eql = key_equal(),
432 const allocator_type& __a = allocator_type())
433 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
434 __key_extract(), __a)
437 template<
typename _InputIterator>
438 _Hashtable(_InputIterator __f, _InputIterator __l,
440 const _H1& __hf = _H1(),
441 const key_equal& __eql = key_equal(),
442 const allocator_type& __a = allocator_type())
443 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
444 __key_extract(), __a)
449 const _H1& __hf = _H1(),
450 const key_equal& __eql = key_equal(),
451 const allocator_type& __a = allocator_type())
452 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
453 __key_extract(), __a)
461 noexcept(__node_alloc_traits::_S_nothrow_move()
462 && is_nothrow_move_assignable<_H1>::value
463 && is_nothrow_move_assignable<_Equal>::value)
465 constexpr
bool __move_storage =
466 __node_alloc_traits::_S_propagate_on_move_assign()
467 || __node_alloc_traits::_S_always_equal();
475 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
476 _M_before_begin._M_nxt =
nullptr;
478 this->_M_insert_range(__l.begin(), __l.end(), __roan);
486 noexcept(__and_<__is_nothrow_swappable<_H1>,
487 __is_nothrow_swappable<_Equal>>::value);
492 {
return iterator(_M_begin()); }
495 begin()
const noexcept
496 {
return const_iterator(_M_begin()); }
500 {
return iterator(
nullptr); }
504 {
return const_iterator(
nullptr); }
508 {
return const_iterator(_M_begin()); }
511 cend()
const noexcept
512 {
return const_iterator(
nullptr); }
515 size()
const noexcept
516 {
return _M_element_count; }
519 empty()
const noexcept
520 {
return size() == 0; }
523 get_allocator()
const noexcept
524 {
return allocator_type(this->_M_node_allocator()); }
527 max_size()
const noexcept
528 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
533 {
return this->_M_eq(); }
539 bucket_count()
const noexcept
540 {
return _M_bucket_count; }
543 max_bucket_count()
const noexcept
544 {
return max_size(); }
547 bucket_size(size_type __n)
const 551 bucket(
const key_type& __k)
const 552 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
557 return local_iterator(*
this, _M_bucket_begin(__n),
558 __n, _M_bucket_count);
563 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
566 begin(size_type __n)
const 568 return const_local_iterator(*
this, _M_bucket_begin(__n),
569 __n, _M_bucket_count);
573 end(size_type __n)
const 574 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
578 cbegin(size_type __n)
const 580 return const_local_iterator(*
this, _M_bucket_begin(__n),
581 __n, _M_bucket_count);
585 cend(size_type __n)
const 586 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
589 load_factor()
const noexcept
591 return static_cast<float>(size()) / static_cast<float>(bucket_count());
600 __rehash_policy()
const 601 {
return _M_rehash_policy; }
604 __rehash_policy(
const _RehashPolicy& __pol)
605 { _M_rehash_policy = __pol; }
609 find(
const key_type& __k);
612 find(
const key_type& __k)
const;
615 count(
const key_type& __k)
const;
618 equal_range(
const key_type& __k);
621 equal_range(
const key_type& __k)
const;
627 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
630 _M_bucket_index(
const key_type& __k, __hash_code __c)
const 631 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
636 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
639 _M_find_node(size_type __bkt,
const key_type& __key,
640 __hash_code __c)
const 642 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
644 return static_cast<__node_type*
>(__before_n->_M_nxt);
654 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
655 size_type __next_bkt);
659 _M_get_previous_node(size_type __bkt, __node_base* __n);
665 _M_insert_unique_node(size_type __bkt, __hash_code __code,
674 template<
typename... _Args>
678 template<
typename... _Args>
681 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
684 template<
typename... _Args>
686 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
687 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
689 template<
typename... _Args>
693 template<
typename _Arg,
typename _NodeGenerator>
697 template<
typename _Arg,
typename _NodeGenerator>
699 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
702 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
707 template<
typename _Arg,
typename _NodeGenerator>
709 _M_insert(const_iterator, _Arg&& __arg,
713 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
717 template<
typename _Arg,
typename _NodeGenerator>
719 _M_insert(const_iterator, _Arg&&,
729 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
733 template<
typename... _Args>
735 emplace(_Args&&... __args)
736 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
738 template<
typename... _Args>
740 emplace_hint(const_iterator __hint, _Args&&... __args)
742 return _M_emplace(__hint, __unique_keys(),
743 std::forward<_Args>(__args)...);
750 erase(const_iterator);
755 {
return erase(const_iterator(__it)); }
758 erase(
const key_type& __k)
759 {
return _M_erase(__unique_keys(), __k); }
762 erase(const_iterator, const_iterator);
768 void rehash(size_type __n);
773 #if __cplusplus > 201402L 776 _M_reinsert_node(node_type&& __nh)
778 insert_return_type __ret;
780 __ret.position =
end();
783 __glibcxx_assert(get_allocator() == __nh.get_allocator());
785 const key_type& __k = __nh._M_key();
786 __hash_code __code = this->_M_hash_code(__k);
787 size_type __bkt = _M_bucket_index(__k, __code);
788 if (
__node_type* __n = _M_find_node(__bkt, __k, __code))
790 __ret.node = std::move(__nh);
791 __ret.position = iterator(__n);
792 __ret.inserted =
false;
797 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
798 __nh._M_ptr =
nullptr;
799 __ret.inserted =
true;
807 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
814 __glibcxx_assert(get_allocator() == __nh.get_allocator());
816 auto __code = this->_M_hash_code(__nh._M_key());
819 __ret = _M_insert_multi_node(__hint._M_cur, __code, __node);
826 extract(const_iterator __pos)
829 size_t __bkt = _M_bucket_index(__n);
834 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
836 if (__prev_n == _M_buckets[__bkt])
837 _M_remove_bucket_begin(__bkt, __n->_M_next(),
838 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
839 else if (__n->_M_nxt)
841 size_type __next_bkt = _M_bucket_index(__n->_M_next());
842 if (__next_bkt != __bkt)
843 _M_buckets[__next_bkt] = __prev_n;
846 __prev_n->_M_nxt = __n->_M_nxt;
847 __n->_M_nxt =
nullptr;
849 return { __n, this->_M_node_allocator() };
854 extract(
const _Key& __k)
857 auto __pos = find(__k);
859 __nh = extract(const_iterator(__pos));
864 template<
typename _Compatible_Hashtable>
866 _M_merge_unique(_Compatible_Hashtable& __src) noexcept
868 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
869 node_type>,
"Node types are compatible");
870 __glibcxx_assert(get_allocator() == __src.get_allocator());
872 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
875 const key_type& __k = this->_M_extract()(__pos._M_cur->_M_v());
876 __hash_code __code = this->_M_hash_code(__k);
877 size_type __bkt = _M_bucket_index(__k, __code);
878 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
880 auto __nh = __src.extract(__pos);
881 _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
882 __nh._M_ptr =
nullptr;
888 template<
typename _Compatible_Hashtable>
890 _M_merge_multi(_Compatible_Hashtable& __src) noexcept
892 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
893 node_type>,
"Node types are compatible");
894 __glibcxx_assert(get_allocator() == __src.get_allocator());
896 this->reserve(size() + __src.size());
897 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
898 _M_reinsert_node_multi(
cend(), __src.extract(__i++));
911 void _M_rehash(size_type __n,
const __rehash_state& __state);
916 template<
typename _Key,
typename _Value,
917 typename _Alloc,
typename _ExtractKey,
typename _Equal,
918 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
921 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
922 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
923 _M_bucket_begin(size_type __bkt)
const 926 __node_base* __n = _M_buckets[__bkt];
927 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
930 template<
typename _Key,
typename _Value,
931 typename _Alloc,
typename _ExtractKey,
typename _Equal,
932 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
934 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
935 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
936 _Hashtable(size_type __bucket_hint,
937 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
938 const _Equal& __eq,
const _ExtractKey& __exk,
939 const allocator_type& __a)
940 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
942 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
943 if (__bkt > _M_bucket_count)
945 _M_buckets = _M_allocate_buckets(__bkt);
946 _M_bucket_count = __bkt;
950 template<
typename _Key,
typename _Value,
951 typename _Alloc,
typename _ExtractKey,
typename _Equal,
952 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
954 template<
typename _InputIterator>
955 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
956 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
957 _Hashtable(_InputIterator __f, _InputIterator __l,
958 size_type __bucket_hint,
959 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
960 const _Equal& __eq,
const _ExtractKey& __exk,
961 const allocator_type& __a)
962 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
964 auto __nb_elems = __detail::__distance_fw(__f, __l);
966 _M_rehash_policy._M_next_bkt(
967 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
970 if (__bkt_count > _M_bucket_count)
972 _M_buckets = _M_allocate_buckets(__bkt_count);
973 _M_bucket_count = __bkt_count;
978 for (; __f != __l; ++__f)
984 _M_deallocate_buckets();
985 __throw_exception_again;
989 template<
typename _Key,
typename _Value,
990 typename _Alloc,
typename _ExtractKey,
typename _Equal,
991 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
994 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
995 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1002 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1004 auto& __this_alloc = this->_M_node_allocator();
1005 auto& __that_alloc = __ht._M_node_allocator();
1006 if (!__node_alloc_traits::_S_always_equal()
1007 && __this_alloc != __that_alloc)
1010 this->_M_deallocate_nodes(_M_begin());
1011 _M_before_begin._M_nxt =
nullptr;
1012 _M_deallocate_buckets();
1013 _M_buckets =
nullptr;
1014 std::__alloc_on_copy(__this_alloc, __that_alloc);
1015 __hashtable_base::operator=(__ht);
1016 _M_bucket_count = __ht._M_bucket_count;
1017 _M_element_count = __ht._M_element_count;
1018 _M_rehash_policy = __ht._M_rehash_policy;
1023 {
return this->_M_allocate_node(__n->_M_v()); });
1030 __throw_exception_again;
1034 std::__alloc_on_copy(__this_alloc, __that_alloc);
1038 __bucket_type* __former_buckets =
nullptr;
1039 std::size_t __former_bucket_count = _M_bucket_count;
1040 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1042 if (_M_bucket_count != __ht._M_bucket_count)
1044 __former_buckets = _M_buckets;
1045 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1046 _M_bucket_count = __ht._M_bucket_count;
1049 __builtin_memset(_M_buckets, 0,
1050 _M_bucket_count *
sizeof(__bucket_type));
1054 __hashtable_base::operator=(__ht);
1055 _M_element_count = __ht._M_element_count;
1056 _M_rehash_policy = __ht._M_rehash_policy;
1057 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1058 _M_before_begin._M_nxt =
nullptr;
1061 {
return __roan(__n->_M_v()); });
1062 if (__former_buckets)
1063 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1067 if (__former_buckets)
1070 _M_deallocate_buckets();
1071 _M_rehash_policy._M_reset(__former_state);
1072 _M_buckets = __former_buckets;
1073 _M_bucket_count = __former_bucket_count;
1075 __builtin_memset(_M_buckets, 0,
1076 _M_bucket_count *
sizeof(__bucket_type));
1077 __throw_exception_again;
1082 template<
typename _Key,
typename _Value,
1083 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1084 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1086 template<
typename _NodeGenerator>
1088 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1089 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1090 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
1092 __bucket_type* __buckets =
nullptr;
1094 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1098 if (!__ht._M_before_begin._M_nxt)
1105 this->_M_copy_code(__this_n, __ht_n);
1106 _M_before_begin._M_nxt = __this_n;
1107 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
1110 __node_base* __prev_n = __this_n;
1111 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1113 __this_n = __node_gen(__ht_n);
1114 __prev_n->_M_nxt = __this_n;
1115 this->_M_copy_code(__this_n, __ht_n);
1116 size_type __bkt = _M_bucket_index(__this_n);
1117 if (!_M_buckets[__bkt])
1118 _M_buckets[__bkt] = __prev_n;
1119 __prev_n = __this_n;
1126 _M_deallocate_buckets();
1127 __throw_exception_again;
1131 template<
typename _Key,
typename _Value,
1132 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1133 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1136 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1137 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1140 _M_rehash_policy._M_reset();
1141 _M_bucket_count = 1;
1142 _M_single_bucket =
nullptr;
1143 _M_buckets = &_M_single_bucket;
1144 _M_before_begin._M_nxt =
nullptr;
1145 _M_element_count = 0;
1148 template<
typename _Key,
typename _Value,
1149 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1150 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1153 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1154 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1157 this->_M_deallocate_nodes(_M_begin());
1158 _M_deallocate_buckets();
1159 __hashtable_base::operator=(std::move(__ht));
1160 _M_rehash_policy = __ht._M_rehash_policy;
1161 if (!__ht._M_uses_single_bucket())
1162 _M_buckets = __ht._M_buckets;
1165 _M_buckets = &_M_single_bucket;
1166 _M_single_bucket = __ht._M_single_bucket;
1168 _M_bucket_count = __ht._M_bucket_count;
1169 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1170 _M_element_count = __ht._M_element_count;
1171 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1176 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1180 template<
typename _Key,
typename _Value,
1181 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1182 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1185 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1186 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1189 if (__ht._M_node_allocator() == this->_M_node_allocator())
1194 __bucket_type* __former_buckets =
nullptr;
1195 size_type __former_bucket_count = _M_bucket_count;
1196 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1198 if (_M_bucket_count != __ht._M_bucket_count)
1200 __former_buckets = _M_buckets;
1201 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1202 _M_bucket_count = __ht._M_bucket_count;
1205 __builtin_memset(_M_buckets, 0,
1206 _M_bucket_count *
sizeof(__bucket_type));
1210 __hashtable_base::operator=(std::move(__ht));
1211 _M_element_count = __ht._M_element_count;
1212 _M_rehash_policy = __ht._M_rehash_policy;
1213 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1214 _M_before_begin._M_nxt =
nullptr;
1222 if (__former_buckets)
1224 _M_deallocate_buckets();
1225 _M_rehash_policy._M_reset(__former_state);
1226 _M_buckets = __former_buckets;
1227 _M_bucket_count = __former_bucket_count;
1229 __builtin_memset(_M_buckets, 0,
1230 _M_bucket_count *
sizeof(__bucket_type));
1231 __throw_exception_again;
1236 template<
typename _Key,
typename _Value,
1237 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1238 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1240 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1241 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1247 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1248 _M_buckets(
nullptr),
1249 _M_bucket_count(__ht._M_bucket_count),
1250 _M_element_count(__ht._M_element_count),
1251 _M_rehash_policy(__ht._M_rehash_policy)
1255 {
return this->_M_allocate_node(__n->_M_v()); });
1258 template<
typename _Key,
typename _Value,
1259 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1260 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1262 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1263 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1269 _M_buckets(__ht._M_buckets),
1270 _M_bucket_count(__ht._M_bucket_count),
1271 _M_before_begin(__ht._M_before_begin._M_nxt),
1272 _M_element_count(__ht._M_element_count),
1273 _M_rehash_policy(__ht._M_rehash_policy)
1276 if (__ht._M_uses_single_bucket())
1278 _M_buckets = &_M_single_bucket;
1279 _M_single_bucket = __ht._M_single_bucket;
1285 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1290 template<
typename _Key,
typename _Value,
1291 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1292 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1294 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1295 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1296 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1302 _M_bucket_count(__ht._M_bucket_count),
1303 _M_element_count(__ht._M_element_count),
1304 _M_rehash_policy(__ht._M_rehash_policy)
1308 {
return this->_M_allocate_node(__n->_M_v()); });
1311 template<
typename _Key,
typename _Value,
1312 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1313 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1315 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1316 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1317 _Hashtable(
_Hashtable&& __ht,
const allocator_type& __a)
1322 _M_buckets(
nullptr),
1323 _M_bucket_count(__ht._M_bucket_count),
1324 _M_element_count(__ht._M_element_count),
1325 _M_rehash_policy(__ht._M_rehash_policy)
1327 if (__ht._M_node_allocator() == this->_M_node_allocator())
1329 if (__ht._M_uses_single_bucket())
1331 _M_buckets = &_M_single_bucket;
1332 _M_single_bucket = __ht._M_single_bucket;
1335 _M_buckets = __ht._M_buckets;
1337 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1341 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1349 return this->_M_allocate_node(
1356 template<
typename _Key,
typename _Value,
1357 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1358 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1360 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1361 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1362 ~_Hashtable() noexcept
1365 _M_deallocate_buckets();
1368 template<
typename _Key,
typename _Value,
1369 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1370 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1373 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1374 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1376 noexcept(__and_<__is_nothrow_swappable<_H1>,
1377 __is_nothrow_swappable<_Equal>>::value)
1384 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1385 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1388 if (this->_M_uses_single_bucket())
1390 if (!__x._M_uses_single_bucket())
1392 _M_buckets = __x._M_buckets;
1393 __x._M_buckets = &__x._M_single_bucket;
1396 else if (__x._M_uses_single_bucket())
1398 __x._M_buckets = _M_buckets;
1399 _M_buckets = &_M_single_bucket;
1402 std::swap(_M_buckets, __x._M_buckets);
1404 std::swap(_M_bucket_count, __x._M_bucket_count);
1405 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1406 std::swap(_M_element_count, __x._M_element_count);
1407 std::swap(_M_single_bucket, __x._M_single_bucket);
1412 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1415 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1416 = &__x._M_before_begin;
1419 template<
typename _Key,
typename _Value,
1420 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1421 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1424 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1425 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1426 find(
const key_type& __k)
1429 __hash_code __code = this->_M_hash_code(__k);
1430 std::size_t __n = _M_bucket_index(__k, __code);
1431 __node_type* __p = _M_find_node(__n, __k, __code);
1432 return __p ? iterator(__p) :
end();
1435 template<
typename _Key,
typename _Value,
1436 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1437 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1440 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1441 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1442 find(
const key_type& __k)
const 1445 __hash_code __code = this->_M_hash_code(__k);
1446 std::size_t __n = _M_bucket_index(__k, __code);
1447 __node_type* __p = _M_find_node(__n, __k, __code);
1448 return __p ? const_iterator(__p) :
end();
1451 template<
typename _Key,
typename _Value,
1452 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1453 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1456 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1457 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1458 count(
const key_type& __k)
const 1461 __hash_code __code = this->_M_hash_code(__k);
1462 std::size_t __n = _M_bucket_index(__k, __code);
1467 std::size_t __result = 0;
1468 for (;; __p = __p->_M_next())
1470 if (this->_M_equals(__k, __code, __p))
1477 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1483 template<
typename _Key,
typename _Value,
1484 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1485 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1488 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1489 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1490 equal_range(
const key_type& __k)
1493 __hash_code __code = this->_M_hash_code(__k);
1494 std::size_t __n = _M_bucket_index(__k, __code);
1495 __node_type* __p = _M_find_node(__n, __k, __code);
1500 while (__p1 && _M_bucket_index(__p1) == __n
1501 && this->_M_equals(__k, __code, __p1))
1502 __p1 = __p1->_M_next();
1510 template<
typename _Key,
typename _Value,
1511 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1512 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1515 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1516 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1517 equal_range(
const key_type& __k)
const 1520 __hash_code __code = this->_M_hash_code(__k);
1521 std::size_t __n = _M_bucket_index(__k, __code);
1522 __node_type* __p = _M_find_node(__n, __k, __code);
1527 while (__p1 && _M_bucket_index(__p1) == __n
1528 && this->_M_equals(__k, __code, __p1))
1529 __p1 = __p1->_M_next();
1531 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1539 template<
typename _Key,
typename _Value,
1540 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1541 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1544 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1545 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1546 _M_find_before_node(size_type __n,
const key_type& __k,
1547 __hash_code __code)
const 1550 __node_base* __prev_p = _M_buckets[__n];
1554 for (
__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1555 __p = __p->_M_next())
1557 if (this->_M_equals(__k, __code, __p))
1560 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1567 template<
typename _Key,
typename _Value,
1568 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1569 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1572 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1573 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1574 _M_insert_bucket_begin(size_type __bkt,
__node_type* __node)
1576 if (_M_buckets[__bkt])
1580 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1581 _M_buckets[__bkt]->_M_nxt = __node;
1588 __node->_M_nxt = _M_before_begin._M_nxt;
1589 _M_before_begin._M_nxt = __node;
1593 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1594 _M_buckets[__bkt] = &_M_before_begin;
1598 template<
typename _Key,
typename _Value,
1599 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1600 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1603 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1604 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1605 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next,
1606 size_type __next_bkt)
1608 if (!__next || __next_bkt != __bkt)
1613 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1616 if (&_M_before_begin == _M_buckets[__bkt])
1617 _M_before_begin._M_nxt = __next;
1618 _M_buckets[__bkt] =
nullptr;
1622 template<
typename _Key,
typename _Value,
1623 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1624 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1627 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1628 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1629 _M_get_previous_node(size_type __bkt, __node_base* __n)
1632 __node_base* __prev_n = _M_buckets[__bkt];
1633 while (__prev_n->_M_nxt != __n)
1634 __prev_n = __prev_n->_M_nxt;
1638 template<
typename _Key,
typename _Value,
1639 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1640 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1642 template<
typename... _Args>
1644 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1645 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1650 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1651 const key_type& __k = this->_M_extract()(__node->_M_v());
1655 __code = this->_M_hash_code(__k);
1659 this->_M_deallocate_node(__node);
1660 __throw_exception_again;
1663 size_type __bkt = _M_bucket_index(__k, __code);
1664 if (
__node_type* __p = _M_find_node(__bkt, __k, __code))
1667 this->_M_deallocate_node(__node);
1672 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1676 template<
typename _Key,
typename _Value,
1677 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1678 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1680 template<
typename... _Args>
1682 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1683 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1689 this->_M_allocate_node(std::forward<_Args>(__args)...);
1694 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1698 this->_M_deallocate_node(__node);
1699 __throw_exception_again;
1702 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1705 template<
typename _Key,
typename _Value,
1706 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1707 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1710 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1711 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1712 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1716 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1718 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1722 if (__do_rehash.
first)
1724 _M_rehash(__do_rehash.
second, __saved_state);
1725 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1728 this->_M_store_code(__node, __code);
1731 _M_insert_bucket_begin(__bkt, __node);
1733 return iterator(__node);
1737 this->_M_deallocate_node(__node);
1738 __throw_exception_again;
1744 template<
typename _Key,
typename _Value,
1745 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1746 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1749 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1750 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1751 _M_insert_multi_node(
__node_type* __hint, __hash_code __code,
1755 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1757 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1761 if (__do_rehash.
first)
1762 _M_rehash(__do_rehash.
second, __saved_state);
1764 this->_M_store_code(__node, __code);
1765 const key_type& __k = this->_M_extract()(__node->_M_v());
1766 size_type __bkt = _M_bucket_index(__k, __code);
1771 = __builtin_expect(__hint !=
nullptr,
false)
1772 && this->_M_equals(__k, __code, __hint)
1774 : _M_find_before_node(__bkt, __k, __code);
1778 __node->_M_nxt = __prev->_M_nxt;
1779 __prev->_M_nxt = __node;
1780 if (__builtin_expect(__prev == __hint,
false))
1784 && !this->_M_equals(__k, __code, __node->_M_next()))
1786 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1787 if (__next_bkt != __bkt)
1788 _M_buckets[__next_bkt] = __node;
1796 _M_insert_bucket_begin(__bkt, __node);
1798 return iterator(__node);
1802 this->_M_deallocate_node(__node);
1803 __throw_exception_again;
1808 template<
typename _Key,
typename _Value,
1809 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1810 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1812 template<
typename _Arg,
typename _NodeGenerator>
1814 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1815 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1816 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
std::true_type)
1819 const key_type& __k = this->_M_extract()(__v);
1820 __hash_code __code = this->_M_hash_code(__k);
1821 size_type __bkt = _M_bucket_index(__k, __code);
1823 __node_type* __n = _M_find_node(__bkt, __k, __code);
1827 __n = __node_gen(std::forward<_Arg>(__v));
1828 return std::make_pair(_M_insert_unique_node(__bkt, __code, __n),
true);
1832 template<
typename _Key,
typename _Value,
1833 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1834 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1836 template<
typename _Arg,
typename _NodeGenerator>
1838 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1839 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1840 _M_insert(const_iterator __hint, _Arg&& __v,
1846 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1849 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1851 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1854 template<
typename _Key,
typename _Value,
1855 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1856 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1859 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1860 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1861 erase(const_iterator __it)
1865 std::size_t __bkt = _M_bucket_index(__n);
1870 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1871 return _M_erase(__bkt, __prev_n, __n);
1874 template<
typename _Key,
typename _Value,
1875 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1876 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1879 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1880 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1881 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n)
1884 if (__prev_n == _M_buckets[__bkt])
1885 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1886 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1887 else if (__n->_M_nxt)
1889 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1890 if (__next_bkt != __bkt)
1891 _M_buckets[__next_bkt] = __prev_n;
1894 __prev_n->_M_nxt = __n->_M_nxt;
1895 iterator __result(__n->_M_next());
1896 this->_M_deallocate_node(__n);
1902 template<
typename _Key,
typename _Value,
1903 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1904 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1907 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1908 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1912 __hash_code __code = this->_M_hash_code(__k);
1913 std::size_t __bkt = _M_bucket_index(__k, __code);
1916 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1922 _M_erase(__bkt, __prev_n, __n);
1926 template<
typename _Key,
typename _Value,
1927 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1928 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1931 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1932 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1936 __hash_code __code = this->_M_hash_code(__k);
1937 std::size_t __bkt = _M_bucket_index(__k, __code);
1940 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1952 std::size_t __n_last_bkt = __bkt;
1955 __n_last = __n_last->_M_next();
1958 __n_last_bkt = _M_bucket_index(__n_last);
1960 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1963 size_type __result = 0;
1967 this->_M_deallocate_node(__n);
1972 while (__n != __n_last);
1974 if (__prev_n == _M_buckets[__bkt])
1975 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1976 else if (__n_last && __n_last_bkt != __bkt)
1977 _M_buckets[__n_last_bkt] = __prev_n;
1978 __prev_n->_M_nxt = __n_last;
1982 template<
typename _Key,
typename _Value,
1983 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1984 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1987 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1988 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1989 erase(const_iterator __first, const_iterator __last)
1994 if (__n == __last_n)
1995 return iterator(__n);
1997 std::size_t __bkt = _M_bucket_index(__n);
1999 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
2000 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2001 std::size_t __n_bkt = __bkt;
2007 __n = __n->_M_next();
2008 this->_M_deallocate_node(__tmp);
2012 __n_bkt = _M_bucket_index(__n);
2014 while (__n != __last_n && __n_bkt == __bkt);
2015 if (__is_bucket_begin)
2016 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2017 if (__n == __last_n)
2019 __is_bucket_begin =
true;
2023 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2024 _M_buckets[__n_bkt] = __prev_n;
2025 __prev_n->_M_nxt = __n;
2026 return iterator(__n);
2029 template<
typename _Key,
typename _Value,
2030 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2031 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2034 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2035 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2038 this->_M_deallocate_nodes(_M_begin());
2039 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
2040 _M_element_count = 0;
2041 _M_before_begin._M_nxt =
nullptr;
2044 template<
typename _Key,
typename _Value,
2045 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2046 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2049 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2050 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2051 rehash(size_type __n)
2053 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2054 std::size_t __buckets
2055 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2057 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
2059 if (__buckets != _M_bucket_count)
2060 _M_rehash(__buckets, __saved_state);
2063 _M_rehash_policy._M_reset(__saved_state);
2066 template<
typename _Key,
typename _Value,
2067 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2068 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2071 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2072 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2073 _M_rehash(size_type __n,
const __rehash_state& __state)
2077 _M_rehash_aux(__n, __unique_keys());
2083 _M_rehash_policy._M_reset(__state);
2084 __throw_exception_again;
2089 template<
typename _Key,
typename _Value,
2090 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2091 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2094 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2095 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2098 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2100 _M_before_begin._M_nxt =
nullptr;
2101 std::size_t __bbegin_bkt = 0;
2105 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2106 if (!__new_buckets[__bkt])
2108 __p->_M_nxt = _M_before_begin._M_nxt;
2109 _M_before_begin._M_nxt = __p;
2110 __new_buckets[__bkt] = &_M_before_begin;
2112 __new_buckets[__bbegin_bkt] = __p;
2113 __bbegin_bkt = __bkt;
2117 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2118 __new_buckets[__bkt]->_M_nxt = __p;
2123 _M_deallocate_buckets();
2124 _M_bucket_count = __n;
2125 _M_buckets = __new_buckets;
2130 template<
typename _Key,
typename _Value,
2131 typename _Alloc,
typename _ExtractKey,
typename _Equal,
2132 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2135 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2136 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2139 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2142 _M_before_begin._M_nxt =
nullptr;
2143 std::size_t __bbegin_bkt = 0;
2144 std::size_t __prev_bkt = 0;
2146 bool __check_bucket =
false;
2151 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2153 if (__prev_p && __prev_bkt == __bkt)
2158 __p->_M_nxt = __prev_p->_M_nxt;
2159 __prev_p->_M_nxt = __p;
2166 __check_bucket =
true;
2174 if (__prev_p->_M_nxt)
2176 std::size_t __next_bkt
2177 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2179 if (__next_bkt != __prev_bkt)
2180 __new_buckets[__next_bkt] = __prev_p;
2182 __check_bucket =
false;
2185 if (!__new_buckets[__bkt])
2187 __p->_M_nxt = _M_before_begin._M_nxt;
2188 _M_before_begin._M_nxt = __p;
2189 __new_buckets[__bkt] = &_M_before_begin;
2191 __new_buckets[__bbegin_bkt] = __p;
2192 __bbegin_bkt = __bkt;
2196 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2197 __new_buckets[__bkt]->_M_nxt = __p;
2205 if (__check_bucket && __prev_p->_M_nxt)
2207 std::size_t __next_bkt
2208 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2209 if (__next_bkt != __prev_bkt)
2210 __new_buckets[__next_bkt] = __prev_p;
2213 _M_deallocate_buckets();
2214 _M_bucket_count = __n;
2215 _M_buckets = __new_buckets;
2218 #if __cplusplus > 201402L 2219 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2222 _GLIBCXX_END_NAMESPACE_VERSION
2225 #endif // _HASHTABLE_H
_T2 second
first is a copy of the first object
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.
Node const_iterators, used to iterate through all the hashtable.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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.
_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.
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.
_T1 first
second_type is the second bound type
Struct holding two objects of arbitrary type.
Uniform interface to all allocator types.
Node iterators, used to iterate through all the hashtable.
Uniform interface to C++98 and C++11 allocators.
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.