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&>>>;
164 template<
typename _Key,
typename _Value,
typename _Alloc,
165 typename _ExtractKey,
typename _Equal,
166 typename _Hash,
typename _RangeHash,
typename _Unused,
167 typename _RehashPolicy,
typename _Traits>
170 _Hash, _RangeHash, _Unused, _Traits>,
172 _Hash, _RangeHash, _Unused,
173 _RehashPolicy, _Traits>,
175 _Hash, _RangeHash, _Unused,
176 _RehashPolicy, _Traits>,
178 _Hash, _RangeHash, _Unused,
179 _RehashPolicy, _Traits>,
181 _Hash, _RangeHash, _Unused,
182 _RehashPolicy, _Traits>,
184 __alloc_rebind<_Alloc,
185 __detail::_Hash_node<_Value,
186 _Traits::__hash_cached::value>>>
188 static_assert(
is_same<
typename remove_cv<_Value>::type, _Value>::value,
189 "unordered container must have a non-const, non-volatile value_type");
190 #if __cplusplus > 201703L || defined __STRICT_ANSI__
192 "unordered container must have the same value_type as its allocator");
195 using __traits_type = _Traits;
196 using __hash_cached =
typename __traits_type::__hash_cached;
197 using __constant_iterators =
typename __traits_type::__constant_iterators;
199 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
203 using __node_value_type =
204 __detail::_Hash_node_value<_Value, __hash_cached::value>;
205 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
206 using __value_alloc_traits =
207 typename __hashtable_alloc::__value_alloc_traits;
208 using __node_alloc_traits =
217 _RehashPolicy, _Traits>;
220 typedef _Key key_type;
221 typedef _Value value_type;
222 typedef _Alloc allocator_type;
223 typedef _Equal key_equal;
227 typedef typename __value_alloc_traits::pointer pointer;
228 typedef typename __value_alloc_traits::const_pointer const_pointer;
229 typedef value_type& reference;
230 typedef const value_type& const_reference;
232 using iterator =
typename __insert_base::iterator;
234 using const_iterator =
typename __insert_base::const_iterator;
237 _ExtractKey, _Hash, _RangeHash, _Unused,
238 __constant_iterators::value,
239 __hash_cached::value>;
243 _ExtractKey, _Hash, _RangeHash, _Unused,
244 __constant_iterators::value, __hash_cached::value>;
247 using __rehash_type = _RehashPolicy;
248 using __rehash_state =
typename __rehash_type::_State;
250 using __unique_keys =
typename __traits_type::__unique_keys;
253 _Hashtable_base<_Key, _Value, _ExtractKey,
254 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
257 using __hash_code =
typename __hashtable_base::__hash_code;
258 using __ireturn_type =
typename __insert_base::__ireturn_type;
261 _Equal, _Hash, _RangeHash, _Unused,
262 _RehashPolicy, _Traits>;
266 _Hash, _RangeHash, _Unused,
267 _RehashPolicy, _Traits>;
270 _Equal, _Hash, _RangeHash, _Unused,
271 _RehashPolicy, _Traits>;
273 using __reuse_or_alloc_node_gen_t =
274 __detail::_ReuseOrAllocNode<__node_alloc_type>;
275 using __alloc_node_gen_t =
276 __detail::_AllocNode<__node_alloc_type>;
283 : _M_h(__h), _M_node(__n) { }
286 template<
typename... _Args>
289 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
293 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
295 _Scoped_node(
const _Scoped_node&) =
delete;
296 _Scoped_node&
operator=(
const _Scoped_node&) =
delete;
302 template<
typename _Ht>
305 const value_type&, value_type&&>::type
306 __fwd_value_for(value_type& __val) noexcept
313 struct __hash_code_base_access : __hash_code_base
314 {
using __hash_code_base::_M_bucket_index; };
318 static_assert(noexcept(declval<const __hash_code_base_access&>()
319 ._M_bucket_index(declval<const __node_value_type&>(),
321 "Cache the hash code or qualify your functors involved"
322 " in hash code and bucket index computation with noexcept");
326 "Functor used to map hash code to bucket index"
327 " must be nothrow default constructible");
328 static_assert(noexcept(
329 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
330 "Functor used to map hash code to bucket index must be"
335 "_ExtractKey must be nothrow default constructible");
336 static_assert(noexcept(
337 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
338 "_ExtractKey functor must be noexcept invocable");
340 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
341 typename _ExtractKeya,
typename _Equala,
342 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
343 typename _RehashPolicya,
typename _Traitsa,
347 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
348 typename _ExtractKeya,
typename _Equala,
349 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
350 typename _RehashPolicya,
typename _Traitsa>
353 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
354 typename _ExtractKeya,
typename _Equala,
355 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
356 typename _RehashPolicya,
typename _Traitsa,
357 bool _Constant_iteratorsa>
360 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
361 typename _ExtractKeya,
typename _Equala,
362 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
363 typename _RehashPolicya,
typename _Traitsa,
368 using size_type =
typename __hashtable_base::size_type;
369 using difference_type =
typename __hashtable_base::difference_type;
371 #if __cplusplus > 201402L
377 __buckets_ptr _M_buckets = &_M_single_bucket;
378 size_type _M_bucket_count = 1;
379 __node_base _M_before_begin;
380 size_type _M_element_count = 0;
381 _RehashPolicy _M_rehash_policy;
389 __node_base_ptr _M_single_bucket =
nullptr;
395 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
399 _M_update_bbegin(__node_ptr __n)
401 _M_before_begin._M_nxt = __n;
406 _M_uses_single_bucket(__buckets_ptr __bkts)
const
407 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
410 _M_uses_single_bucket()
const
411 {
return _M_uses_single_bucket(_M_buckets); }
414 _M_base_alloc() {
return *
this; }
417 _M_allocate_buckets(size_type __bkt_count)
419 if (__builtin_expect(__bkt_count == 1,
false))
421 _M_single_bucket =
nullptr;
422 return &_M_single_bucket;
425 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
429 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
431 if (_M_uses_single_bucket(__bkts))
434 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
438 _M_deallocate_buckets()
439 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
444 _M_bucket_begin(size_type __bkt)
const;
448 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
452 template<
typename _Ht>
454 _M_assign_elements(_Ht&&);
456 template<
typename _Ht,
typename _NodeGenerator>
458 _M_assign(_Ht&&,
const _NodeGenerator&);
469 _Hashtable(
const _Hash& __h,
const _Equal& __eq,
470 const allocator_type& __a)
475 template<
bool _No_realloc = true>
476 static constexpr
bool
479 #if __cplusplus <= 201402L
480 return __and_<__bool_constant<_No_realloc>,
484 if constexpr (_No_realloc)
493 noexcept(_S_nothrow_move());
498 template<
typename _InputIterator>
499 _Hashtable(_InputIterator __first, _InputIterator __last,
500 size_type __bkt_count_hint,
501 const _Hash&,
const _Equal&,
const allocator_type&,
504 template<
typename _InputIterator>
505 _Hashtable(_InputIterator __first, _InputIterator __last,
506 size_type __bkt_count_hint,
507 const _Hash&,
const _Equal&,
const allocator_type&,
520 const _Hash& __hf = _Hash(),
521 const key_equal& __eql = key_equal(),
522 const allocator_type& __a = allocator_type());
526 noexcept(_S_nothrow_move())
532 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
534 typename __node_alloc_traits::is_always_equal{})
542 template<
typename _InputIterator>
543 _Hashtable(_InputIterator __f, _InputIterator __l,
544 size_type __bkt_count_hint = 0,
545 const _Hash& __hf = _Hash(),
546 const key_equal& __eql = key_equal(),
547 const allocator_type& __a = allocator_type())
548 :
_Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
553 size_type __bkt_count_hint = 0,
554 const _Hash& __hf = _Hash(),
555 const key_equal& __eql = key_equal(),
556 const allocator_type& __a = allocator_type())
557 :
_Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
558 __hf, __eql, __a, __unique_keys{})
566 noexcept(__node_alloc_traits::_S_nothrow_move()
570 constexpr
bool __move_storage =
571 __node_alloc_traits::_S_propagate_on_move_assign()
572 || __node_alloc_traits::_S_always_equal();
580 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
581 _M_before_begin._M_nxt =
nullptr;
585 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
588 if (_M_bucket_count < __l_bkt_count)
589 rehash(__l_bkt_count);
591 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
599 noexcept(__and_<__is_nothrow_swappable<_Hash>,
600 __is_nothrow_swappable<_Equal>>::value);
605 {
return iterator(_M_begin()); }
608 begin()
const noexcept
609 {
return const_iterator(_M_begin()); }
613 {
return iterator(
nullptr); }
617 {
return const_iterator(
nullptr); }
621 {
return const_iterator(_M_begin()); }
624 cend()
const noexcept
625 {
return const_iterator(
nullptr); }
628 size()
const noexcept
629 {
return _M_element_count; }
631 _GLIBCXX_NODISCARD
bool
632 empty()
const noexcept
633 {
return size() == 0; }
636 get_allocator()
const noexcept
637 {
return allocator_type(this->_M_node_allocator()); }
640 max_size()
const noexcept
641 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
646 {
return this->_M_eq(); }
652 bucket_count()
const noexcept
653 {
return _M_bucket_count; }
656 max_bucket_count()
const noexcept
657 {
return max_size(); }
660 bucket_size(size_type __bkt)
const
661 {
return std::distance(
begin(__bkt),
end(__bkt)); }
664 bucket(
const key_type& __k)
const
665 {
return _M_bucket_index(this->_M_hash_code(__k)); }
668 begin(size_type __bkt)
671 __bkt, _M_bucket_count);
676 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
679 begin(size_type __bkt)
const
682 __bkt, _M_bucket_count);
686 end(size_type __bkt)
const
691 cbegin(size_type __bkt)
const
694 __bkt, _M_bucket_count);
698 cend(size_type __bkt)
const
702 load_factor()
const noexcept
704 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
713 __rehash_policy()
const
714 {
return _M_rehash_policy; }
717 __rehash_policy(
const _RehashPolicy& __pol)
718 { _M_rehash_policy = __pol; }
722 find(
const key_type& __k);
725 find(
const key_type& __k)
const;
728 count(
const key_type& __k)
const;
731 equal_range(
const key_type& __k);
734 equal_range(
const key_type& __k)
const;
736 #if __cplusplus > 201702L
737 template<
typename _Kt,
738 typename = __has_is_transparent_t<_Hash, _Kt>,
739 typename = __has_is_transparent_t<_Equal, _Kt>>
741 _M_find_tr(
const _Kt& __k);
743 template<
typename _Kt,
744 typename = __has_is_transparent_t<_Hash, _Kt>,
745 typename = __has_is_transparent_t<_Equal, _Kt>>
747 _M_find_tr(
const _Kt& __k)
const;
749 template<
typename _Kt,
750 typename = __has_is_transparent_t<_Hash, _Kt>,
751 typename = __has_is_transparent_t<_Equal, _Kt>>
753 _M_count_tr(
const _Kt& __k)
const;
755 template<
typename _Kt,
756 typename = __has_is_transparent_t<_Hash, _Kt>,
757 typename = __has_is_transparent_t<_Equal, _Kt>>
759 _M_equal_range_tr(
const _Kt& __k);
761 template<
typename _Kt,
762 typename = __has_is_transparent_t<_Hash, _Kt>,
763 typename = __has_is_transparent_t<_Equal, _Kt>>
765 _M_equal_range_tr(
const _Kt& __k)
const;
771 _M_bucket_index(
const __node_value_type& __n)
const noexcept
772 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
775 _M_bucket_index(__hash_code __c)
const
776 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
781 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
783 template<
typename _Kt>
785 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
788 _M_find_node(size_type __bkt,
const key_type& __key,
789 __hash_code __c)
const
791 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
793 return static_cast<__node_ptr
>(__before_n->_M_nxt);
797 template<
typename _Kt>
799 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
800 __hash_code __c)
const
802 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
804 return static_cast<__node_ptr
>(__before_n->_M_nxt);
810 _M_insert_bucket_begin(size_type, __node_ptr);
814 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
815 size_type __next_bkt);
819 _M_get_previous_node(size_type __bkt, __node_ptr __n);
825 _M_insert_unique_node(size_type __bkt, __hash_code,
826 __node_ptr __n, size_type __n_elt = 1);
831 _M_insert_multi_node(__node_ptr __hint,
832 __hash_code __code, __node_ptr __n);
834 template<
typename... _Args>
836 _M_emplace(
true_type __uks, _Args&&... __args);
838 template<
typename... _Args>
840 _M_emplace(
false_type __uks, _Args&&... __args)
841 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
844 template<
typename... _Args>
846 _M_emplace(const_iterator,
true_type __uks, _Args&&... __args)
847 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
849 template<
typename... _Args>
851 _M_emplace(const_iterator,
false_type __uks, _Args&&... __args);
853 template<
typename _Arg,
typename _NodeGenerator>
855 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type __uks);
857 template<
typename _Arg,
typename _NodeGenerator>
859 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
862 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
867 template<
typename _Arg,
typename _NodeGenerator>
869 _M_insert(const_iterator, _Arg&& __arg,
870 const _NodeGenerator& __node_gen,
true_type __uks)
873 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).
first;
877 template<
typename _Arg,
typename _NodeGenerator>
879 _M_insert(const_iterator, _Arg&&,
883 _M_erase(
true_type __uks,
const key_type&);
889 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
893 template<
typename... _Args>
895 emplace(_Args&&... __args)
896 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
898 template<
typename... _Args>
900 emplace_hint(const_iterator __hint, _Args&&... __args)
902 return _M_emplace(__hint, __unique_keys{},
903 std::forward<_Args>(__args)...);
910 erase(const_iterator);
915 {
return erase(const_iterator(__it)); }
918 erase(
const key_type& __k)
919 {
return _M_erase(__unique_keys{}, __k); }
922 erase(const_iterator, const_iterator);
929 void rehash(size_type __bkt_count);
934 #if __cplusplus > 201402L
941 __ret.position =
end();
944 __glibcxx_assert(get_allocator() == __nh.get_allocator());
946 const key_type& __k = __nh._M_key();
947 __hash_code __code = this->_M_hash_code(__k);
948 size_type __bkt = _M_bucket_index(__code);
949 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
952 __ret.position = iterator(__n);
953 __ret.inserted =
false;
958 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
959 __nh._M_ptr =
nullptr;
960 __ret.inserted =
true;
973 __glibcxx_assert(get_allocator() == __nh.get_allocator());
975 const key_type& __k = __nh._M_key();
976 auto __code = this->_M_hash_code(__k);
978 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
979 __nh._M_ptr =
nullptr;
985 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
987 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
988 if (__prev_n == _M_buckets[__bkt])
989 _M_remove_bucket_begin(__bkt, __n->_M_next(),
990 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
991 else if (__n->_M_nxt)
993 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
994 if (__next_bkt != __bkt)
995 _M_buckets[__next_bkt] = __prev_n;
998 __prev_n->_M_nxt = __n->_M_nxt;
999 __n->_M_nxt =
nullptr;
1001 return { __n, this->_M_node_allocator() };
1007 extract(const_iterator __pos)
1009 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1010 return _M_extract_node(__bkt,
1011 _M_get_previous_node(__bkt, __pos._M_cur));
1019 __hash_code __code = this->_M_hash_code(__k);
1020 std::size_t __bkt = _M_bucket_index(__code);
1021 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1022 __nh = _M_extract_node(__bkt, __prev_node);
1027 template<
typename _Compatible_Hashtable>
1031 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1032 node_type>,
"Node types are compatible");
1033 __glibcxx_assert(get_allocator() == __src.get_allocator());
1035 auto __n_elt = __src.size();
1036 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1039 const key_type& __k = _ExtractKey{}(*__pos);
1040 __hash_code __code = this->_M_hash_code(__k);
1041 size_type __bkt = _M_bucket_index(__code);
1042 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1044 auto __nh = __src.extract(__pos);
1045 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1046 __nh._M_ptr =
nullptr;
1049 else if (__n_elt != 1)
1055 template<
typename _Compatible_Hashtable>
1059 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1060 node_type>,
"Node types are compatible");
1061 __glibcxx_assert(get_allocator() == __src.get_allocator());
1063 this->reserve(
size() + __src.size());
1064 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1071 void _M_rehash_aux(size_type __bkt_count,
true_type __uks);
1074 void _M_rehash_aux(size_type __bkt_count,
false_type __uks);
1078 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1083 template<
typename _Key,
typename _Value,
typename _Alloc,
1084 typename _ExtractKey,
typename _Equal,
1085 typename _Hash,
typename _RangeHash,
typename _Unused,
1086 typename _RehashPolicy,
typename _Traits>
1088 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1089 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1090 _M_bucket_begin(size_type __bkt)
const
1093 __node_base_ptr __n = _M_buckets[__bkt];
1094 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
1097 template<
typename _Key,
typename _Value,
typename _Alloc,
1098 typename _ExtractKey,
typename _Equal,
1099 typename _Hash,
typename _RangeHash,
typename _Unused,
1100 typename _RehashPolicy,
typename _Traits>
1101 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1102 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1103 _Hashtable(size_type __bkt_count_hint,
1104 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1105 : _Hashtable(__h, __eq, __a)
1107 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1108 if (__bkt_count > _M_bucket_count)
1110 _M_buckets = _M_allocate_buckets(__bkt_count);
1111 _M_bucket_count = __bkt_count;
1115 template<
typename _Key,
typename _Value,
typename _Alloc,
1116 typename _ExtractKey,
typename _Equal,
1117 typename _Hash,
typename _RangeHash,
typename _Unused,
1118 typename _RehashPolicy,
typename _Traits>
1119 template<
typename _InputIterator>
1120 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1121 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1122 _Hashtable(_InputIterator __f, _InputIterator __l,
1123 size_type __bkt_count_hint,
1124 const _Hash& __h,
const _Equal& __eq,
1126 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1128 for (; __f != __l; ++__f)
1132 template<
typename _Key,
typename _Value,
typename _Alloc,
1133 typename _ExtractKey,
typename _Equal,
1134 typename _Hash,
typename _RangeHash,
typename _Unused,
1135 typename _RehashPolicy,
typename _Traits>
1136 template<
typename _InputIterator>
1137 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1138 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1139 _Hashtable(_InputIterator __f, _InputIterator __l,
1140 size_type __bkt_count_hint,
1141 const _Hash& __h,
const _Equal& __eq,
1143 : _Hashtable(__h, __eq, __a)
1145 auto __nb_elems = __detail::__distance_fw(__f, __l);
1147 _M_rehash_policy._M_next_bkt(
1148 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1151 if (__bkt_count > _M_bucket_count)
1153 _M_buckets = _M_allocate_buckets(__bkt_count);
1154 _M_bucket_count = __bkt_count;
1157 for (; __f != __l; ++__f)
1161 template<
typename _Key,
typename _Value,
typename _Alloc,
1162 typename _ExtractKey,
typename _Equal,
1163 typename _Hash,
typename _RangeHash,
typename _Unused,
1164 typename _RehashPolicy,
typename _Traits>
1166 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1167 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1168 operator=(
const _Hashtable& __ht)
1174 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1176 auto& __this_alloc = this->_M_node_allocator();
1177 auto& __that_alloc = __ht._M_node_allocator();
1178 if (!__node_alloc_traits::_S_always_equal()
1179 && __this_alloc != __that_alloc)
1182 this->_M_deallocate_nodes(_M_begin());
1183 _M_before_begin._M_nxt =
nullptr;
1184 _M_deallocate_buckets();
1185 _M_buckets =
nullptr;
1186 std::__alloc_on_copy(__this_alloc, __that_alloc);
1188 _M_bucket_count = __ht._M_bucket_count;
1189 _M_element_count = __ht._M_element_count;
1190 _M_rehash_policy = __ht._M_rehash_policy;
1191 __alloc_node_gen_t __alloc_node_gen(*
this);
1194 _M_assign(__ht, __alloc_node_gen);
1201 __throw_exception_again;
1205 std::__alloc_on_copy(__this_alloc, __that_alloc);
1209 _M_assign_elements(__ht);
1213 template<
typename _Key,
typename _Value,
typename _Alloc,
1214 typename _ExtractKey,
typename _Equal,
1215 typename _Hash,
typename _RangeHash,
typename _Unused,
1216 typename _RehashPolicy,
typename _Traits>
1217 template<
typename _Ht>
1219 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1220 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1221 _M_assign_elements(_Ht&& __ht)
1223 __buckets_ptr __former_buckets =
nullptr;
1224 std::size_t __former_bucket_count = _M_bucket_count;
1225 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1227 if (_M_bucket_count != __ht._M_bucket_count)
1229 __former_buckets = _M_buckets;
1230 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1231 _M_bucket_count = __ht._M_bucket_count;
1234 __builtin_memset(_M_buckets, 0,
1235 _M_bucket_count *
sizeof(__node_base_ptr));
1240 _M_element_count = __ht._M_element_count;
1241 _M_rehash_policy = __ht._M_rehash_policy;
1242 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1243 _M_before_begin._M_nxt =
nullptr;
1244 _M_assign(std::forward<_Ht>(__ht), __roan);
1245 if (__former_buckets)
1246 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1250 if (__former_buckets)
1253 _M_deallocate_buckets();
1254 _M_rehash_policy._M_reset(__former_state);
1255 _M_buckets = __former_buckets;
1256 _M_bucket_count = __former_bucket_count;
1258 __builtin_memset(_M_buckets, 0,
1259 _M_bucket_count *
sizeof(__node_base_ptr));
1260 __throw_exception_again;
1264 template<
typename _Key,
typename _Value,
typename _Alloc,
1265 typename _ExtractKey,
typename _Equal,
1266 typename _Hash,
typename _RangeHash,
typename _Unused,
1267 typename _RehashPolicy,
typename _Traits>
1268 template<
typename _Ht,
typename _NodeGenerator>
1270 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1271 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1272 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1274 __buckets_ptr __buckets =
nullptr;
1276 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1280 if (!__ht._M_before_begin._M_nxt)
1285 __node_ptr __ht_n = __ht._M_begin();
1287 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1288 this->_M_copy_code(*__this_n, *__ht_n);
1289 _M_update_bbegin(__this_n);
1292 __node_ptr __prev_n = __this_n;
1293 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1295 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1296 __prev_n->_M_nxt = __this_n;
1297 this->_M_copy_code(*__this_n, *__ht_n);
1298 size_type __bkt = _M_bucket_index(*__this_n);
1299 if (!_M_buckets[__bkt])
1300 _M_buckets[__bkt] = __prev_n;
1301 __prev_n = __this_n;
1308 _M_deallocate_buckets();
1309 __throw_exception_again;
1313 template<
typename _Key,
typename _Value,
typename _Alloc,
1314 typename _ExtractKey,
typename _Equal,
1315 typename _Hash,
typename _RangeHash,
typename _Unused,
1316 typename _RehashPolicy,
typename _Traits>
1318 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1319 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1322 _M_rehash_policy._M_reset();
1323 _M_bucket_count = 1;
1324 _M_single_bucket =
nullptr;
1325 _M_buckets = &_M_single_bucket;
1326 _M_before_begin._M_nxt =
nullptr;
1327 _M_element_count = 0;
1330 template<
typename _Key,
typename _Value,
typename _Alloc,
1331 typename _ExtractKey,
typename _Equal,
1332 typename _Hash,
typename _RangeHash,
typename _Unused,
1333 typename _RehashPolicy,
typename _Traits>
1335 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1336 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1337 _M_move_assign(_Hashtable&& __ht,
true_type)
1342 this->_M_deallocate_nodes(_M_begin());
1343 _M_deallocate_buckets();
1345 _M_rehash_policy = __ht._M_rehash_policy;
1346 if (!__ht._M_uses_single_bucket())
1347 _M_buckets = __ht._M_buckets;
1350 _M_buckets = &_M_single_bucket;
1351 _M_single_bucket = __ht._M_single_bucket;
1354 _M_bucket_count = __ht._M_bucket_count;
1355 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1356 _M_element_count = __ht._M_element_count;
1357 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1364 template<
typename _Key,
typename _Value,
typename _Alloc,
1365 typename _ExtractKey,
typename _Equal,
1366 typename _Hash,
typename _RangeHash,
typename _Unused,
1367 typename _RehashPolicy,
typename _Traits>
1369 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1370 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1371 _M_move_assign(_Hashtable&& __ht,
false_type)
1373 if (__ht._M_node_allocator() == this->_M_node_allocator())
1383 template<
typename _Key,
typename _Value,
typename _Alloc,
1384 typename _ExtractKey,
typename _Equal,
1385 typename _Hash,
typename _RangeHash,
typename _Unused,
1386 typename _RehashPolicy,
typename _Traits>
1387 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1388 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1389 _Hashtable(
const _Hashtable& __ht)
1390 : __hashtable_base(__ht),
1392 __rehash_base(__ht),
1394 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1395 _M_buckets(nullptr),
1396 _M_bucket_count(__ht._M_bucket_count),
1397 _M_element_count(__ht._M_element_count),
1398 _M_rehash_policy(__ht._M_rehash_policy)
1400 __alloc_node_gen_t __alloc_node_gen(*
this);
1401 _M_assign(__ht, __alloc_node_gen);
1404 template<
typename _Key,
typename _Value,
typename _Alloc,
1405 typename _ExtractKey,
typename _Equal,
1406 typename _Hash,
typename _RangeHash,
typename _Unused,
1407 typename _RehashPolicy,
typename _Traits>
1408 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1409 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1410 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1412 noexcept(_S_nothrow_move())
1413 : __hashtable_base(__ht),
1415 __rehash_base(__ht),
1416 __hashtable_alloc(
std::
move(__a)),
1417 _M_buckets(__ht._M_buckets),
1418 _M_bucket_count(__ht._M_bucket_count),
1419 _M_before_begin(__ht._M_before_begin._M_nxt),
1420 _M_element_count(__ht._M_element_count),
1421 _M_rehash_policy(__ht._M_rehash_policy)
1424 if (__ht._M_uses_single_bucket())
1426 _M_buckets = &_M_single_bucket;
1427 _M_single_bucket = __ht._M_single_bucket;
1436 template<
typename _Key,
typename _Value,
typename _Alloc,
1437 typename _ExtractKey,
typename _Equal,
1438 typename _Hash,
typename _RangeHash,
typename _Unused,
1439 typename _RehashPolicy,
typename _Traits>
1440 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1441 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1442 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1443 : __hashtable_base(__ht),
1445 __rehash_base(__ht),
1446 __hashtable_alloc(__node_alloc_type(__a)),
1448 _M_bucket_count(__ht._M_bucket_count),
1449 _M_element_count(__ht._M_element_count),
1450 _M_rehash_policy(__ht._M_rehash_policy)
1452 __alloc_node_gen_t __alloc_node_gen(*
this);
1453 _M_assign(__ht, __alloc_node_gen);
1456 template<
typename _Key,
typename _Value,
typename _Alloc,
1457 typename _ExtractKey,
typename _Equal,
1458 typename _Hash,
typename _RangeHash,
typename _Unused,
1459 typename _RehashPolicy,
typename _Traits>
1460 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1461 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1462 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1464 : __hashtable_base(__ht),
1466 __rehash_base(__ht),
1467 __hashtable_alloc(
std::
move(__a)),
1468 _M_buckets(nullptr),
1469 _M_bucket_count(__ht._M_bucket_count),
1470 _M_element_count(__ht._M_element_count),
1471 _M_rehash_policy(__ht._M_rehash_policy)
1473 if (__ht._M_node_allocator() == this->_M_node_allocator())
1475 if (__ht._M_uses_single_bucket())
1477 _M_buckets = &_M_single_bucket;
1478 _M_single_bucket = __ht._M_single_bucket;
1481 _M_buckets = __ht._M_buckets;
1485 _M_update_bbegin(__ht._M_begin());
1491 __alloc_node_gen_t __alloc_gen(*
this);
1493 using _Fwd_Ht =
typename
1494 conditional<__move_if_noexcept_cond<value_type>::value,
1495 const _Hashtable&, _Hashtable&&>::type;
1496 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1501 template<
typename _Key,
typename _Value,
typename _Alloc,
1502 typename _ExtractKey,
typename _Equal,
1503 typename _Hash,
typename _RangeHash,
typename _Unused,
1504 typename _RehashPolicy,
typename _Traits>
1505 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1506 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1507 ~_Hashtable() noexcept
1510 _M_deallocate_buckets();
1513 template<
typename _Key,
typename _Value,
typename _Alloc,
1514 typename _ExtractKey,
typename _Equal,
1515 typename _Hash,
typename _RangeHash,
typename _Unused,
1516 typename _RehashPolicy,
typename _Traits>
1518 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1519 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
::
1520 swap(_Hashtable& __x)
1521 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1522 __is_nothrow_swappable<_Equal>>::value)
1529 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1530 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1533 if (this->_M_uses_single_bucket())
1535 if (!__x._M_uses_single_bucket())
1537 _M_buckets = __x._M_buckets;
1538 __x._M_buckets = &__x._M_single_bucket;
1541 else if (__x._M_uses_single_bucket())
1543 __x._M_buckets = _M_buckets;
1544 _M_buckets = &_M_single_bucket;
1549 std::swap(_M_bucket_count, __x._M_bucket_count);
1550 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1551 std::swap(_M_element_count, __x._M_element_count);
1552 std::swap(_M_single_bucket, __x._M_single_bucket);
1557 __x._M_update_bbegin();
1560 template<
typename _Key,
typename _Value,
typename _Alloc,
1561 typename _ExtractKey,
typename _Equal,
1562 typename _Hash,
typename _RangeHash,
typename _Unused,
1563 typename _RehashPolicy,
typename _Traits>
1565 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1566 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1567 find(
const key_type& __k)
1570 __hash_code __code = this->_M_hash_code(__k);
1571 std::size_t __bkt = _M_bucket_index(__code);
1572 return iterator(_M_find_node(__bkt, __k, __code));
1575 template<
typename _Key,
typename _Value,
typename _Alloc,
1576 typename _ExtractKey,
typename _Equal,
1577 typename _Hash,
typename _RangeHash,
typename _Unused,
1578 typename _RehashPolicy,
typename _Traits>
1580 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1581 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1582 find(
const key_type& __k)
const
1585 __hash_code __code = this->_M_hash_code(__k);
1586 std::size_t __bkt = _M_bucket_index(__code);
1587 return const_iterator(_M_find_node(__bkt, __k, __code));
1590 #if __cplusplus > 201703L
1591 template<
typename _Key,
typename _Value,
typename _Alloc,
1592 typename _ExtractKey,
typename _Equal,
1593 typename _Hash,
typename _RangeHash,
typename _Unused,
1594 typename _RehashPolicy,
typename _Traits>
1595 template<
typename _Kt,
typename,
typename>
1597 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1598 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1599 _M_find_tr(
const _Kt& __k)
1602 __hash_code __code = this->_M_hash_code_tr(__k);
1603 std::size_t __bkt = _M_bucket_index(__code);
1604 return iterator(_M_find_node_tr(__bkt, __k, __code));
1607 template<
typename _Key,
typename _Value,
typename _Alloc,
1608 typename _ExtractKey,
typename _Equal,
1609 typename _Hash,
typename _RangeHash,
typename _Unused,
1610 typename _RehashPolicy,
typename _Traits>
1611 template<
typename _Kt,
typename,
typename>
1613 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1614 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1615 _M_find_tr(
const _Kt& __k)
const
1618 __hash_code __code = this->_M_hash_code_tr(__k);
1619 std::size_t __bkt = _M_bucket_index(__code);
1620 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1624 template<
typename _Key,
typename _Value,
typename _Alloc,
1625 typename _ExtractKey,
typename _Equal,
1626 typename _Hash,
typename _RangeHash,
typename _Unused,
1627 typename _RehashPolicy,
typename _Traits>
1629 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1630 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1631 count(
const key_type& __k)
const
1634 auto __it = find(__k);
1638 if (__unique_keys::value)
1644 size_type __result = 1;
1645 for (
auto __ref = __it++;
1646 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1653 #if __cplusplus > 201703L
1654 template<
typename _Key,
typename _Value,
typename _Alloc,
1655 typename _ExtractKey,
typename _Equal,
1656 typename _Hash,
typename _RangeHash,
typename _Unused,
1657 typename _RehashPolicy,
typename _Traits>
1658 template<
typename _Kt,
typename,
typename>
1660 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1661 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1662 _M_count_tr(
const _Kt& __k)
const
1665 __hash_code __code = this->_M_hash_code_tr(__k);
1666 std::size_t __bkt = _M_bucket_index(__code);
1667 auto __n = _M_find_node_tr(__bkt, __k, __code);
1675 size_type __result = 1;
1677 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1685 template<
typename _Key,
typename _Value,
typename _Alloc,
1686 typename _ExtractKey,
typename _Equal,
1687 typename _Hash,
typename _RangeHash,
typename _Unused,
1688 typename _RehashPolicy,
typename _Traits>
1690 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1691 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1692 equal_range(
const key_type& __k)
1693 -> pair<iterator, iterator>
1695 auto __ite = find(__k);
1697 return { __ite, __ite };
1699 auto __beg = __ite++;
1700 if (__unique_keys::value)
1701 return { __beg, __ite };
1706 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1709 return { __beg, __ite };
1712 template<
typename _Key,
typename _Value,
typename _Alloc,
1713 typename _ExtractKey,
typename _Equal,
1714 typename _Hash,
typename _RangeHash,
typename _Unused,
1715 typename _RehashPolicy,
typename _Traits>
1717 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1718 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1719 equal_range(
const key_type& __k)
const
1720 -> pair<const_iterator, const_iterator>
1722 auto __ite = find(__k);
1724 return { __ite, __ite };
1726 auto __beg = __ite++;
1727 if (__unique_keys::value)
1728 return { __beg, __ite };
1733 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1736 return { __beg, __ite };
1739 #if __cplusplus > 201703L
1740 template<
typename _Key,
typename _Value,
typename _Alloc,
1741 typename _ExtractKey,
typename _Equal,
1742 typename _Hash,
typename _RangeHash,
typename _Unused,
1743 typename _RehashPolicy,
typename _Traits>
1744 template<
typename _Kt,
typename,
typename>
1746 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1747 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1748 _M_equal_range_tr(
const _Kt& __k)
1749 -> pair<iterator, iterator>
1751 __hash_code __code = this->_M_hash_code_tr(__k);
1752 std::size_t __bkt = _M_bucket_index(__code);
1753 auto __n = _M_find_node_tr(__bkt, __k, __code);
1754 iterator __ite(__n);
1756 return { __ite, __ite };
1761 auto __beg = __ite++;
1762 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1765 return { __beg, __ite };
1768 template<
typename _Key,
typename _Value,
typename _Alloc,
1769 typename _ExtractKey,
typename _Equal,
1770 typename _Hash,
typename _RangeHash,
typename _Unused,
1771 typename _RehashPolicy,
typename _Traits>
1772 template<
typename _Kt,
typename,
typename>
1774 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1775 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1776 _M_equal_range_tr(
const _Kt& __k)
const
1777 -> pair<const_iterator, const_iterator>
1779 __hash_code __code = this->_M_hash_code_tr(__k);
1780 std::size_t __bkt = _M_bucket_index(__code);
1781 auto __n = _M_find_node_tr(__bkt, __k, __code);
1782 const_iterator __ite(__n);
1784 return { __ite, __ite };
1789 auto __beg = __ite++;
1790 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1793 return { __beg, __ite };
1799 template<
typename _Key,
typename _Value,
typename _Alloc,
1800 typename _ExtractKey,
typename _Equal,
1801 typename _Hash,
typename _RangeHash,
typename _Unused,
1802 typename _RehashPolicy,
typename _Traits>
1804 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1805 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1806 _M_find_before_node(size_type __bkt,
const key_type& __k,
1807 __hash_code __code)
const
1810 __node_base_ptr __prev_p = _M_buckets[__bkt];
1814 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1815 __p = __p->_M_next())
1817 if (this->_M_equals(__k, __code, *__p))
1820 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1828 template<
typename _Key,
typename _Value,
typename _Alloc,
1829 typename _ExtractKey,
typename _Equal,
1830 typename _Hash,
typename _RangeHash,
typename _Unused,
1831 typename _RehashPolicy,
typename _Traits>
1832 template<
typename _Kt>
1834 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1835 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1836 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1837 __hash_code __code)
const
1840 __node_base_ptr __prev_p = _M_buckets[__bkt];
1844 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1845 __p = __p->_M_next())
1847 if (this->_M_equals_tr(__k, __code, *__p))
1850 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1858 template<
typename _Key,
typename _Value,
typename _Alloc,
1859 typename _ExtractKey,
typename _Equal,
1860 typename _Hash,
typename _RangeHash,
typename _Unused,
1861 typename _RehashPolicy,
typename _Traits>
1863 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1864 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1865 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1867 if (_M_buckets[__bkt])
1871 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1872 _M_buckets[__bkt]->_M_nxt = __node;
1879 __node->_M_nxt = _M_before_begin._M_nxt;
1880 _M_before_begin._M_nxt = __node;
1885 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
1887 _M_buckets[__bkt] = &_M_before_begin;
1891 template<
typename _Key,
typename _Value,
typename _Alloc,
1892 typename _ExtractKey,
typename _Equal,
1893 typename _Hash,
typename _RangeHash,
typename _Unused,
1894 typename _RehashPolicy,
typename _Traits>
1896 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1897 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1898 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
1899 size_type __next_bkt)
1901 if (!__next || __next_bkt != __bkt)
1906 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1909 if (&_M_before_begin == _M_buckets[__bkt])
1910 _M_before_begin._M_nxt = __next;
1911 _M_buckets[__bkt] =
nullptr;
1915 template<
typename _Key,
typename _Value,
typename _Alloc,
1916 typename _ExtractKey,
typename _Equal,
1917 typename _Hash,
typename _RangeHash,
typename _Unused,
1918 typename _RehashPolicy,
typename _Traits>
1920 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1921 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1922 _M_get_previous_node(size_type __bkt, __node_ptr __n)
1925 __node_base_ptr __prev_n = _M_buckets[__bkt];
1926 while (__prev_n->_M_nxt != __n)
1927 __prev_n = __prev_n->_M_nxt;
1931 template<
typename _Key,
typename _Value,
typename _Alloc,
1932 typename _ExtractKey,
typename _Equal,
1933 typename _Hash,
typename _RangeHash,
typename _Unused,
1934 typename _RehashPolicy,
typename _Traits>
1935 template<
typename... _Args>
1937 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1938 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1939 _M_emplace(
true_type , _Args&&... __args)
1940 -> pair<iterator, bool>
1943 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1944 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1945 __hash_code __code = this->_M_hash_code(__k);
1946 size_type __bkt = _M_bucket_index(__code);
1947 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
1949 return std::make_pair(iterator(__p),
false);
1952 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
1953 __node._M_node =
nullptr;
1954 return { __pos,
true };
1957 template<
typename _Key,
typename _Value,
typename _Alloc,
1958 typename _ExtractKey,
typename _Equal,
1959 typename _Hash,
typename _RangeHash,
typename _Unused,
1960 typename _RehashPolicy,
typename _Traits>
1961 template<
typename... _Args>
1963 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1964 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1965 _M_emplace(const_iterator __hint,
false_type ,
1970 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1971 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1973 __hash_code __code = this->_M_hash_code(__k);
1975 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
1976 __node._M_node =
nullptr;
1980 template<
typename _Key,
typename _Value,
typename _Alloc,
1981 typename _ExtractKey,
typename _Equal,
1982 typename _Hash,
typename _RangeHash,
typename _Unused,
1983 typename _RehashPolicy,
typename _Traits>
1985 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1986 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1987 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1988 __node_ptr __node, size_type __n_elt)
1991 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1993 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1996 if (__do_rehash.
first)
1998 _M_rehash(__do_rehash.
second, __saved_state);
1999 __bkt = _M_bucket_index(__code);
2002 this->_M_store_code(*__node, __code);
2005 _M_insert_bucket_begin(__bkt, __node);
2007 return iterator(__node);
2010 template<
typename _Key,
typename _Value,
typename _Alloc,
2011 typename _ExtractKey,
typename _Equal,
2012 typename _Hash,
typename _RangeHash,
typename _Unused,
2013 typename _RehashPolicy,
typename _Traits>
2015 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2016 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2017 _M_insert_multi_node(__node_ptr __hint,
2018 __hash_code __code, __node_ptr __node)
2021 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2023 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2025 if (__do_rehash.
first)
2026 _M_rehash(__do_rehash.
second, __saved_state);
2028 this->_M_store_code(*__node, __code);
2029 const key_type& __k = _ExtractKey{}(__node->_M_v());
2030 size_type __bkt = _M_bucket_index(__code);
2034 __node_base_ptr __prev
2035 = __builtin_expect(__hint !=
nullptr,
false)
2036 && this->_M_equals(__k, __code, *__hint)
2038 : _M_find_before_node(__bkt, __k, __code);
2043 __node->_M_nxt = __prev->_M_nxt;
2044 __prev->_M_nxt = __node;
2045 if (__builtin_expect(__prev == __hint,
false))
2049 && !this->_M_equals(__k, __code, *__node->_M_next()))
2051 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2052 if (__next_bkt != __bkt)
2053 _M_buckets[__next_bkt] = __node;
2060 _M_insert_bucket_begin(__bkt, __node);
2062 return iterator(__node);
2066 template<
typename _Key,
typename _Value,
typename _Alloc,
2067 typename _ExtractKey,
typename _Equal,
2068 typename _Hash,
typename _RangeHash,
typename _Unused,
2069 typename _RehashPolicy,
typename _Traits>
2070 template<
typename _Arg,
typename _NodeGenerator>
2072 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2073 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2074 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
2076 -> pair<iterator, bool>
2078 const key_type& __k = _ExtractKey{}(__v);
2079 __hash_code __code = this->_M_hash_code(__k);
2080 size_type __bkt = _M_bucket_index(__code);
2082 if (__node_ptr __node = _M_find_node(__bkt, __k, __code))
2083 return { iterator(__node),
false };
2085 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2087 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2088 __node._M_node =
nullptr;
2089 return { __pos,
true };
2093 template<
typename _Key,
typename _Value,
typename _Alloc,
2094 typename _ExtractKey,
typename _Equal,
2095 typename _Hash,
typename _RangeHash,
typename _Unused,
2096 typename _RehashPolicy,
typename _Traits>
2097 template<
typename _Arg,
typename _NodeGenerator>
2099 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2100 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2101 _M_insert(const_iterator __hint, _Arg&& __v,
2102 const _NodeGenerator& __node_gen,
2108 __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
2111 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2113 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
2114 __node._M_node =
nullptr;
2118 template<
typename _Key,
typename _Value,
typename _Alloc,
2119 typename _ExtractKey,
typename _Equal,
2120 typename _Hash,
typename _RangeHash,
typename _Unused,
2121 typename _RehashPolicy,
typename _Traits>
2123 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2124 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2125 erase(const_iterator __it)
2128 __node_ptr __n = __it._M_cur;
2129 std::size_t __bkt = _M_bucket_index(*__n);
2134 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2135 return _M_erase(__bkt, __prev_n, __n);
2138 template<
typename _Key,
typename _Value,
typename _Alloc,
2139 typename _ExtractKey,
typename _Equal,
2140 typename _Hash,
typename _RangeHash,
typename _Unused,
2141 typename _RehashPolicy,
typename _Traits>
2143 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2144 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2145 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2148 if (__prev_n == _M_buckets[__bkt])
2149 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2150 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2151 else if (__n->_M_nxt)
2153 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2154 if (__next_bkt != __bkt)
2155 _M_buckets[__next_bkt] = __prev_n;
2158 __prev_n->_M_nxt = __n->_M_nxt;
2159 iterator __result(__n->_M_next());
2160 this->_M_deallocate_node(__n);
2166 template<
typename _Key,
typename _Value,
typename _Alloc,
2167 typename _ExtractKey,
typename _Equal,
2168 typename _Hash,
typename _RangeHash,
typename _Unused,
2169 typename _RehashPolicy,
typename _Traits>
2171 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2172 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2173 _M_erase(
true_type ,
const key_type& __k)
2176 __hash_code __code = this->_M_hash_code(__k);
2177 std::size_t __bkt = _M_bucket_index(__code);
2180 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2185 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2186 _M_erase(__bkt, __prev_n, __n);
2190 template<
typename _Key,
typename _Value,
typename _Alloc,
2191 typename _ExtractKey,
typename _Equal,
2192 typename _Hash,
typename _RangeHash,
typename _Unused,
2193 typename _RehashPolicy,
typename _Traits>
2195 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2196 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2200 __hash_code __code = this->_M_hash_code(__k);
2201 std::size_t __bkt = _M_bucket_index(__code);
2204 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2214 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2215 __node_ptr __n_last = __n->_M_next();
2216 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2217 __n_last = __n_last->_M_next();
2219 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2222 size_type __result = 0;
2225 __node_ptr __p = __n->_M_next();
2226 this->_M_deallocate_node(__n);
2230 while (__n != __n_last);
2232 _M_element_count -= __result;
2233 if (__prev_n == _M_buckets[__bkt])
2234 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2235 else if (__n_last_bkt != __bkt)
2236 _M_buckets[__n_last_bkt] = __prev_n;
2237 __prev_n->_M_nxt = __n_last;
2241 template<
typename _Key,
typename _Value,
typename _Alloc,
2242 typename _ExtractKey,
typename _Equal,
2243 typename _Hash,
typename _RangeHash,
typename _Unused,
2244 typename _RehashPolicy,
typename _Traits>
2246 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2247 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2248 erase(const_iterator __first, const_iterator __last)
2251 __node_ptr __n = __first._M_cur;
2252 __node_ptr __last_n = __last._M_cur;
2253 if (__n == __last_n)
2254 return iterator(__n);
2256 std::size_t __bkt = _M_bucket_index(*__n);
2258 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2259 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2260 std::size_t __n_bkt = __bkt;
2265 __node_ptr __tmp = __n;
2266 __n = __n->_M_next();
2267 this->_M_deallocate_node(__tmp);
2271 __n_bkt = _M_bucket_index(*__n);
2273 while (__n != __last_n && __n_bkt == __bkt);
2274 if (__is_bucket_begin)
2275 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2276 if (__n == __last_n)
2278 __is_bucket_begin =
true;
2282 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2283 _M_buckets[__n_bkt] = __prev_n;
2284 __prev_n->_M_nxt = __n;
2285 return iterator(__n);
2288 template<
typename _Key,
typename _Value,
typename _Alloc,
2289 typename _ExtractKey,
typename _Equal,
2290 typename _Hash,
typename _RangeHash,
typename _Unused,
2291 typename _RehashPolicy,
typename _Traits>
2293 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2294 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2297 this->_M_deallocate_nodes(_M_begin());
2298 __builtin_memset(_M_buckets, 0,
2299 _M_bucket_count *
sizeof(__node_base_ptr));
2300 _M_element_count = 0;
2301 _M_before_begin._M_nxt =
nullptr;
2304 template<
typename _Key,
typename _Value,
typename _Alloc,
2305 typename _ExtractKey,
typename _Equal,
2306 typename _Hash,
typename _RangeHash,
typename _Unused,
2307 typename _RehashPolicy,
typename _Traits>
2309 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2310 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2311 rehash(size_type __bkt_count)
2313 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2315 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2317 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2319 if (__bkt_count != _M_bucket_count)
2320 _M_rehash(__bkt_count, __saved_state);
2324 _M_rehash_policy._M_reset(__saved_state);
2327 template<
typename _Key,
typename _Value,
typename _Alloc,
2328 typename _ExtractKey,
typename _Equal,
2329 typename _Hash,
typename _RangeHash,
typename _Unused,
2330 typename _RehashPolicy,
typename _Traits>
2332 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2333 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2334 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2338 _M_rehash_aux(__bkt_count, __unique_keys{});
2344 _M_rehash_policy._M_reset(__state);
2345 __throw_exception_again;
2350 template<
typename _Key,
typename _Value,
typename _Alloc,
2351 typename _ExtractKey,
typename _Equal,
2352 typename _Hash,
typename _RangeHash,
typename _Unused,
2353 typename _RehashPolicy,
typename _Traits>
2355 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2356 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2357 _M_rehash_aux(size_type __bkt_count,
true_type )
2359 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2360 __node_ptr __p = _M_begin();
2361 _M_before_begin._M_nxt =
nullptr;
2362 std::size_t __bbegin_bkt = 0;
2365 __node_ptr __next = __p->_M_next();
2367 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2368 if (!__new_buckets[__bkt])
2370 __p->_M_nxt = _M_before_begin._M_nxt;
2371 _M_before_begin._M_nxt = __p;
2372 __new_buckets[__bkt] = &_M_before_begin;
2374 __new_buckets[__bbegin_bkt] = __p;
2375 __bbegin_bkt = __bkt;
2379 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2380 __new_buckets[__bkt]->_M_nxt = __p;
2386 _M_deallocate_buckets();
2387 _M_bucket_count = __bkt_count;
2388 _M_buckets = __new_buckets;
2393 template<
typename _Key,
typename _Value,
typename _Alloc,
2394 typename _ExtractKey,
typename _Equal,
2395 typename _Hash,
typename _RangeHash,
typename _Unused,
2396 typename _RehashPolicy,
typename _Traits>
2398 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2399 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2400 _M_rehash_aux(size_type __bkt_count,
false_type )
2402 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2403 __node_ptr __p = _M_begin();
2404 _M_before_begin._M_nxt =
nullptr;
2405 std::size_t __bbegin_bkt = 0;
2406 std::size_t __prev_bkt = 0;
2407 __node_ptr __prev_p =
nullptr;
2408 bool __check_bucket =
false;
2412 __node_ptr __next = __p->_M_next();
2414 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2416 if (__prev_p && __prev_bkt == __bkt)
2421 __p->_M_nxt = __prev_p->_M_nxt;
2422 __prev_p->_M_nxt = __p;
2429 __check_bucket =
true;
2437 if (__prev_p->_M_nxt)
2439 std::size_t __next_bkt
2440 = __hash_code_base::_M_bucket_index(
2441 *__prev_p->_M_next(), __bkt_count);
2442 if (__next_bkt != __prev_bkt)
2443 __new_buckets[__next_bkt] = __prev_p;
2445 __check_bucket =
false;
2448 if (!__new_buckets[__bkt])
2450 __p->_M_nxt = _M_before_begin._M_nxt;
2451 _M_before_begin._M_nxt = __p;
2452 __new_buckets[__bkt] = &_M_before_begin;
2454 __new_buckets[__bbegin_bkt] = __p;
2455 __bbegin_bkt = __bkt;
2459 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2460 __new_buckets[__bkt]->_M_nxt = __p;
2468 if (__check_bucket && __prev_p->_M_nxt)
2470 std::size_t __next_bkt
2471 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2473 if (__next_bkt != __prev_bkt)
2474 __new_buckets[__next_bkt] = __prev_p;
2477 _M_deallocate_buckets();
2478 _M_bucket_count = __bkt_count;
2479 _M_buckets = __new_buckets;
2482 #if __cplusplus > 201402L
2483 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2486 #if __cpp_deduction_guides >= 201606
2488 template<
typename _Hash>
2489 using _RequireNotAllocatorOrIntegral
2490 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2493 _GLIBCXX_END_NAMESPACE_VERSION
auto_ptr & operator=(auto_ptr &__a)
auto_ptr assignment operator.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
_Tp * begin(valarray< _Tp > &__va)
Return an iterator pointing to the first element of the valarray.
_Tp * end(valarray< _Tp > &__va)
Return an iterator pointing to one past the last element of the valarray.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
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 auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
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.
Define a member typedef type to one of two argument types.
is_nothrow_default_constructible
is_nothrow_copy_constructible
is_nothrow_move_assignable
node_type extract(const _Key &__k)
Extract a node.
void _M_merge_unique(_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with unique keys.
void _M_merge_multi(_Compatible_Hashtable &__src) noexcept
Merge from a compatible container into one with equivalent keys.
insert_return_type _M_reinsert_node(node_type &&__nh)
Re-insert an extracted node into a container with unique keys.
iterator _M_reinsert_node_multi(const_iterator __hint, node_type &&__nh)
Re-insert an extracted node into a container with equivalent keys.
Node handle type for maps.
Return type of insert(node_handle&&) on unique maps/sets.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.
Uniform interface to C++98 and C++11 allocators.