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)
483 template<
typename _InputIterator>
484 _Hashtable(_InputIterator __first, _InputIterator __last,
485 size_type __bkt_count_hint,
486 const _Hash&,
const _Equal&,
const allocator_type&,
489 template<
typename _InputIterator>
490 _Hashtable(_InputIterator __first, _InputIterator __last,
491 size_type __bkt_count_hint,
492 const _Hash&,
const _Equal&,
const allocator_type&,
505 const _Hash& __hf = _Hash(),
506 const key_equal& __eql = key_equal(),
507 const allocator_type& __a = allocator_type());
513 std::declval<__node_alloc_type>(),
522 std::declval<__node_alloc_type>(),
523 typename __node_alloc_traits::is_always_equal{})) )
525 typename __node_alloc_traits::is_always_equal{})
533 template<
typename _InputIterator>
534 _Hashtable(_InputIterator __f, _InputIterator __l,
535 size_type __bkt_count_hint = 0,
536 const _Hash& __hf = _Hash(),
537 const key_equal& __eql = key_equal(),
538 const allocator_type& __a = allocator_type())
539 :
_Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
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(__l.begin(), __l.end(), __bkt_count_hint,
549 __hf, __eql, __a, __unique_keys{})
557 noexcept(__node_alloc_traits::_S_nothrow_move()
561 constexpr
bool __move_storage =
562 __node_alloc_traits::_S_propagate_on_move_assign()
563 || __node_alloc_traits::_S_always_equal();
571 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
572 _M_before_begin._M_nxt =
nullptr;
576 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
579 if (_M_bucket_count < __l_bkt_count)
580 rehash(__l_bkt_count);
582 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
590 noexcept(__and_<__is_nothrow_swappable<_Hash>,
591 __is_nothrow_swappable<_Equal>>::value);
596 {
return iterator(_M_begin()); }
599 begin()
const noexcept
600 {
return const_iterator(_M_begin()); }
604 {
return iterator(
nullptr); }
608 {
return const_iterator(
nullptr); }
612 {
return const_iterator(_M_begin()); }
615 cend()
const noexcept
616 {
return const_iterator(
nullptr); }
619 size()
const noexcept
620 {
return _M_element_count; }
622 _GLIBCXX_NODISCARD
bool
623 empty()
const noexcept
624 {
return size() == 0; }
627 get_allocator()
const noexcept
628 {
return allocator_type(this->_M_node_allocator()); }
631 max_size()
const noexcept
632 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
637 {
return this->_M_eq(); }
643 bucket_count()
const noexcept
644 {
return _M_bucket_count; }
647 max_bucket_count()
const noexcept
648 {
return max_size(); }
651 bucket_size(size_type __bkt)
const
652 {
return std::distance(
begin(__bkt),
end(__bkt)); }
655 bucket(
const key_type& __k)
const
656 {
return _M_bucket_index(this->_M_hash_code(__k)); }
659 begin(size_type __bkt)
662 __bkt, _M_bucket_count);
667 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
670 begin(size_type __bkt)
const
673 __bkt, _M_bucket_count);
677 end(size_type __bkt)
const
682 cbegin(size_type __bkt)
const
685 __bkt, _M_bucket_count);
689 cend(size_type __bkt)
const
693 load_factor()
const noexcept
695 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
704 __rehash_policy()
const
705 {
return _M_rehash_policy; }
708 __rehash_policy(
const _RehashPolicy& __pol)
709 { _M_rehash_policy = __pol; }
713 find(
const key_type& __k);
716 find(
const key_type& __k)
const;
719 count(
const key_type& __k)
const;
722 equal_range(
const key_type& __k);
725 equal_range(
const key_type& __k)
const;
727 #if __cplusplus > 201702L
728 template<
typename _Kt,
729 typename = __has_is_transparent_t<_Hash, _Kt>,
730 typename = __has_is_transparent_t<_Equal, _Kt>>
732 _M_find_tr(
const _Kt& __k);
734 template<
typename _Kt,
735 typename = __has_is_transparent_t<_Hash, _Kt>,
736 typename = __has_is_transparent_t<_Equal, _Kt>>
738 _M_find_tr(
const _Kt& __k)
const;
740 template<
typename _Kt,
741 typename = __has_is_transparent_t<_Hash, _Kt>,
742 typename = __has_is_transparent_t<_Equal, _Kt>>
744 _M_count_tr(
const _Kt& __k)
const;
746 template<
typename _Kt,
747 typename = __has_is_transparent_t<_Hash, _Kt>,
748 typename = __has_is_transparent_t<_Equal, _Kt>>
750 _M_equal_range_tr(
const _Kt& __k);
752 template<
typename _Kt,
753 typename = __has_is_transparent_t<_Hash, _Kt>,
754 typename = __has_is_transparent_t<_Equal, _Kt>>
756 _M_equal_range_tr(
const _Kt& __k)
const;
762 _M_bucket_index(
const __node_value_type& __n)
const noexcept
763 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
766 _M_bucket_index(__hash_code __c)
const
767 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
772 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
774 template<
typename _Kt>
776 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
779 _M_find_node(size_type __bkt,
const key_type& __key,
780 __hash_code __c)
const
782 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
784 return static_cast<__node_ptr
>(__before_n->_M_nxt);
788 template<
typename _Kt>
790 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
791 __hash_code __c)
const
793 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
795 return static_cast<__node_ptr
>(__before_n->_M_nxt);
801 _M_insert_bucket_begin(size_type, __node_ptr);
805 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
806 size_type __next_bkt);
810 _M_get_previous_node(size_type __bkt, __node_ptr __n);
816 _M_insert_unique_node(size_type __bkt, __hash_code,
817 __node_ptr __n, size_type __n_elt = 1);
822 _M_insert_multi_node(__node_ptr __hint,
823 __hash_code __code, __node_ptr __n);
825 template<
typename... _Args>
827 _M_emplace(
true_type __uks, _Args&&... __args);
829 template<
typename... _Args>
831 _M_emplace(
false_type __uks, _Args&&... __args)
832 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
835 template<
typename... _Args>
837 _M_emplace(const_iterator,
true_type __uks, _Args&&... __args)
838 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
840 template<
typename... _Args>
842 _M_emplace(const_iterator,
false_type __uks, _Args&&... __args);
844 template<
typename _Arg,
typename _NodeGenerator>
846 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type __uks);
848 template<
typename _Arg,
typename _NodeGenerator>
850 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
853 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
858 template<
typename _Arg,
typename _NodeGenerator>
860 _M_insert(const_iterator, _Arg&& __arg,
861 const _NodeGenerator& __node_gen,
true_type __uks)
864 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).
first;
868 template<
typename _Arg,
typename _NodeGenerator>
870 _M_insert(const_iterator, _Arg&&,
874 _M_erase(
true_type __uks,
const key_type&);
880 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
884 template<
typename... _Args>
886 emplace(_Args&&... __args)
887 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
889 template<
typename... _Args>
891 emplace_hint(const_iterator __hint, _Args&&... __args)
893 return _M_emplace(__hint, __unique_keys{},
894 std::forward<_Args>(__args)...);
901 erase(const_iterator);
906 {
return erase(const_iterator(__it)); }
909 erase(
const key_type& __k)
910 {
return _M_erase(__unique_keys{}, __k); }
913 erase(const_iterator, const_iterator);
920 void rehash(size_type __bkt_count);
925 #if __cplusplus > 201402L
932 __ret.position =
end();
935 __glibcxx_assert(get_allocator() == __nh.get_allocator());
937 const key_type& __k = __nh._M_key();
938 __hash_code __code = this->_M_hash_code(__k);
939 size_type __bkt = _M_bucket_index(__code);
940 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
943 __ret.position = iterator(__n);
944 __ret.inserted =
false;
949 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
950 __nh._M_ptr =
nullptr;
951 __ret.inserted =
true;
964 __glibcxx_assert(get_allocator() == __nh.get_allocator());
966 const key_type& __k = __nh._M_key();
967 auto __code = this->_M_hash_code(__k);
969 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
970 __nh._M_ptr =
nullptr;
976 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
978 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
979 if (__prev_n == _M_buckets[__bkt])
980 _M_remove_bucket_begin(__bkt, __n->_M_next(),
981 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
982 else if (__n->_M_nxt)
984 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
985 if (__next_bkt != __bkt)
986 _M_buckets[__next_bkt] = __prev_n;
989 __prev_n->_M_nxt = __n->_M_nxt;
990 __n->_M_nxt =
nullptr;
992 return { __n, this->_M_node_allocator() };
998 extract(const_iterator __pos)
1000 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1001 return _M_extract_node(__bkt,
1002 _M_get_previous_node(__bkt, __pos._M_cur));
1010 __hash_code __code = this->_M_hash_code(__k);
1011 std::size_t __bkt = _M_bucket_index(__code);
1012 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1013 __nh = _M_extract_node(__bkt, __prev_node);
1018 template<
typename _Compatible_Hashtable>
1022 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1023 node_type>,
"Node types are compatible");
1024 __glibcxx_assert(get_allocator() == __src.get_allocator());
1026 auto __n_elt = __src.size();
1027 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1030 const key_type& __k = _ExtractKey{}(*__pos);
1031 __hash_code __code = this->_M_hash_code(__k);
1032 size_type __bkt = _M_bucket_index(__code);
1033 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1035 auto __nh = __src.extract(__pos);
1036 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1037 __nh._M_ptr =
nullptr;
1040 else if (__n_elt != 1)
1046 template<
typename _Compatible_Hashtable>
1050 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1051 node_type>,
"Node types are compatible");
1052 __glibcxx_assert(get_allocator() == __src.get_allocator());
1054 this->reserve(
size() + __src.size());
1055 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1062 void _M_rehash_aux(size_type __bkt_count,
true_type __uks);
1065 void _M_rehash_aux(size_type __bkt_count,
false_type __uks);
1069 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1074 template<
typename _Key,
typename _Value,
typename _Alloc,
1075 typename _ExtractKey,
typename _Equal,
1076 typename _Hash,
typename _RangeHash,
typename _Unused,
1077 typename _RehashPolicy,
typename _Traits>
1079 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1080 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1081 _M_bucket_begin(size_type __bkt)
const
1084 __node_base_ptr __n = _M_buckets[__bkt];
1085 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
1088 template<
typename _Key,
typename _Value,
typename _Alloc,
1089 typename _ExtractKey,
typename _Equal,
1090 typename _Hash,
typename _RangeHash,
typename _Unused,
1091 typename _RehashPolicy,
typename _Traits>
1092 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1093 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1094 _Hashtable(size_type __bkt_count_hint,
1095 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1096 : _Hashtable(__h, __eq, __a)
1098 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1099 if (__bkt_count > _M_bucket_count)
1101 _M_buckets = _M_allocate_buckets(__bkt_count);
1102 _M_bucket_count = __bkt_count;
1106 template<
typename _Key,
typename _Value,
typename _Alloc,
1107 typename _ExtractKey,
typename _Equal,
1108 typename _Hash,
typename _RangeHash,
typename _Unused,
1109 typename _RehashPolicy,
typename _Traits>
1110 template<
typename _InputIterator>
1111 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1112 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1113 _Hashtable(_InputIterator __f, _InputIterator __l,
1114 size_type __bkt_count_hint,
1115 const _Hash& __h,
const _Equal& __eq,
1117 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1119 for (; __f != __l; ++__f)
1123 template<
typename _Key,
typename _Value,
typename _Alloc,
1124 typename _ExtractKey,
typename _Equal,
1125 typename _Hash,
typename _RangeHash,
typename _Unused,
1126 typename _RehashPolicy,
typename _Traits>
1127 template<
typename _InputIterator>
1128 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1129 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1130 _Hashtable(_InputIterator __f, _InputIterator __l,
1131 size_type __bkt_count_hint,
1132 const _Hash& __h,
const _Equal& __eq,
1134 : _Hashtable(__h, __eq, __a)
1136 auto __nb_elems = __detail::__distance_fw(__f, __l);
1138 _M_rehash_policy._M_next_bkt(
1139 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1142 if (__bkt_count > _M_bucket_count)
1144 _M_buckets = _M_allocate_buckets(__bkt_count);
1145 _M_bucket_count = __bkt_count;
1148 for (; __f != __l; ++__f)
1152 template<
typename _Key,
typename _Value,
typename _Alloc,
1153 typename _ExtractKey,
typename _Equal,
1154 typename _Hash,
typename _RangeHash,
typename _Unused,
1155 typename _RehashPolicy,
typename _Traits>
1157 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1158 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1159 operator=(
const _Hashtable& __ht)
1165 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1167 auto& __this_alloc = this->_M_node_allocator();
1168 auto& __that_alloc = __ht._M_node_allocator();
1169 if (!__node_alloc_traits::_S_always_equal()
1170 && __this_alloc != __that_alloc)
1173 this->_M_deallocate_nodes(_M_begin());
1174 _M_before_begin._M_nxt =
nullptr;
1175 _M_deallocate_buckets();
1176 _M_buckets =
nullptr;
1177 std::__alloc_on_copy(__this_alloc, __that_alloc);
1179 _M_bucket_count = __ht._M_bucket_count;
1180 _M_element_count = __ht._M_element_count;
1181 _M_rehash_policy = __ht._M_rehash_policy;
1182 __alloc_node_gen_t __alloc_node_gen(*
this);
1185 _M_assign(__ht, __alloc_node_gen);
1192 __throw_exception_again;
1196 std::__alloc_on_copy(__this_alloc, __that_alloc);
1200 _M_assign_elements(__ht);
1204 template<
typename _Key,
typename _Value,
typename _Alloc,
1205 typename _ExtractKey,
typename _Equal,
1206 typename _Hash,
typename _RangeHash,
typename _Unused,
1207 typename _RehashPolicy,
typename _Traits>
1208 template<
typename _Ht>
1210 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1211 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1212 _M_assign_elements(_Ht&& __ht)
1214 __buckets_ptr __former_buckets =
nullptr;
1215 std::size_t __former_bucket_count = _M_bucket_count;
1216 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1218 if (_M_bucket_count != __ht._M_bucket_count)
1220 __former_buckets = _M_buckets;
1221 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1222 _M_bucket_count = __ht._M_bucket_count;
1225 __builtin_memset(_M_buckets, 0,
1226 _M_bucket_count *
sizeof(__node_base_ptr));
1231 _M_element_count = __ht._M_element_count;
1232 _M_rehash_policy = __ht._M_rehash_policy;
1233 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1234 _M_before_begin._M_nxt =
nullptr;
1235 _M_assign(std::forward<_Ht>(__ht), __roan);
1236 if (__former_buckets)
1237 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1241 if (__former_buckets)
1244 _M_deallocate_buckets();
1245 _M_rehash_policy._M_reset(__former_state);
1246 _M_buckets = __former_buckets;
1247 _M_bucket_count = __former_bucket_count;
1249 __builtin_memset(_M_buckets, 0,
1250 _M_bucket_count *
sizeof(__node_base_ptr));
1251 __throw_exception_again;
1255 template<
typename _Key,
typename _Value,
typename _Alloc,
1256 typename _ExtractKey,
typename _Equal,
1257 typename _Hash,
typename _RangeHash,
typename _Unused,
1258 typename _RehashPolicy,
typename _Traits>
1259 template<
typename _Ht,
typename _NodeGenerator>
1261 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1262 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1263 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1265 __buckets_ptr __buckets =
nullptr;
1267 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1271 if (!__ht._M_before_begin._M_nxt)
1276 __node_ptr __ht_n = __ht._M_begin();
1278 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1279 this->_M_copy_code(*__this_n, *__ht_n);
1280 _M_update_bbegin(__this_n);
1283 __node_ptr __prev_n = __this_n;
1284 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1286 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1287 __prev_n->_M_nxt = __this_n;
1288 this->_M_copy_code(*__this_n, *__ht_n);
1289 size_type __bkt = _M_bucket_index(*__this_n);
1290 if (!_M_buckets[__bkt])
1291 _M_buckets[__bkt] = __prev_n;
1292 __prev_n = __this_n;
1299 _M_deallocate_buckets();
1300 __throw_exception_again;
1304 template<
typename _Key,
typename _Value,
typename _Alloc,
1305 typename _ExtractKey,
typename _Equal,
1306 typename _Hash,
typename _RangeHash,
typename _Unused,
1307 typename _RehashPolicy,
typename _Traits>
1309 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1310 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1313 _M_rehash_policy._M_reset();
1314 _M_bucket_count = 1;
1315 _M_single_bucket =
nullptr;
1316 _M_buckets = &_M_single_bucket;
1317 _M_before_begin._M_nxt =
nullptr;
1318 _M_element_count = 0;
1321 template<
typename _Key,
typename _Value,
typename _Alloc,
1322 typename _ExtractKey,
typename _Equal,
1323 typename _Hash,
typename _RangeHash,
typename _Unused,
1324 typename _RehashPolicy,
typename _Traits>
1326 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1327 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1328 _M_move_assign(_Hashtable&& __ht,
true_type)
1333 this->_M_deallocate_nodes(_M_begin());
1334 _M_deallocate_buckets();
1336 _M_rehash_policy = __ht._M_rehash_policy;
1337 if (!__ht._M_uses_single_bucket())
1338 _M_buckets = __ht._M_buckets;
1341 _M_buckets = &_M_single_bucket;
1342 _M_single_bucket = __ht._M_single_bucket;
1345 _M_bucket_count = __ht._M_bucket_count;
1346 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1347 _M_element_count = __ht._M_element_count;
1348 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1355 template<
typename _Key,
typename _Value,
typename _Alloc,
1356 typename _ExtractKey,
typename _Equal,
1357 typename _Hash,
typename _RangeHash,
typename _Unused,
1358 typename _RehashPolicy,
typename _Traits>
1360 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1361 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1362 _M_move_assign(_Hashtable&& __ht,
false_type)
1364 if (__ht._M_node_allocator() == this->_M_node_allocator())
1374 template<
typename _Key,
typename _Value,
typename _Alloc,
1375 typename _ExtractKey,
typename _Equal,
1376 typename _Hash,
typename _RangeHash,
typename _Unused,
1377 typename _RehashPolicy,
typename _Traits>
1378 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1379 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1380 _Hashtable(
const _Hashtable& __ht)
1381 : __hashtable_base(__ht),
1383 __rehash_base(__ht),
1385 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1386 _M_buckets(nullptr),
1387 _M_bucket_count(__ht._M_bucket_count),
1388 _M_element_count(__ht._M_element_count),
1389 _M_rehash_policy(__ht._M_rehash_policy)
1391 __alloc_node_gen_t __alloc_node_gen(*
this);
1392 _M_assign(__ht, __alloc_node_gen);
1395 template<
typename _Key,
typename _Value,
typename _Alloc,
1396 typename _ExtractKey,
typename _Equal,
1397 typename _Hash,
typename _RangeHash,
typename _Unused,
1398 typename _RehashPolicy,
typename _Traits>
1399 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1400 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1401 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1405 : __hashtable_base(__ht),
1407 __rehash_base(__ht),
1408 __hashtable_alloc(
std::
move(__a)),
1409 _M_buckets(__ht._M_buckets),
1410 _M_bucket_count(__ht._M_bucket_count),
1411 _M_before_begin(__ht._M_before_begin._M_nxt),
1412 _M_element_count(__ht._M_element_count),
1413 _M_rehash_policy(__ht._M_rehash_policy)
1416 if (__ht._M_uses_single_bucket())
1418 _M_buckets = &_M_single_bucket;
1419 _M_single_bucket = __ht._M_single_bucket;
1428 template<
typename _Key,
typename _Value,
typename _Alloc,
1429 typename _ExtractKey,
typename _Equal,
1430 typename _Hash,
typename _RangeHash,
typename _Unused,
1431 typename _RehashPolicy,
typename _Traits>
1432 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1433 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1434 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1435 : __hashtable_base(__ht),
1437 __rehash_base(__ht),
1438 __hashtable_alloc(__node_alloc_type(__a)),
1440 _M_bucket_count(__ht._M_bucket_count),
1441 _M_element_count(__ht._M_element_count),
1442 _M_rehash_policy(__ht._M_rehash_policy)
1444 __alloc_node_gen_t __alloc_node_gen(*
this);
1445 _M_assign(__ht, __alloc_node_gen);
1448 template<
typename _Key,
typename _Value,
typename _Alloc,
1449 typename _ExtractKey,
typename _Equal,
1450 typename _Hash,
typename _RangeHash,
typename _Unused,
1451 typename _RehashPolicy,
typename _Traits>
1452 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1453 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1454 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1456 : __hashtable_base(__ht),
1458 __rehash_base(__ht),
1459 __hashtable_alloc(
std::
move(__a)),
1460 _M_buckets(nullptr),
1461 _M_bucket_count(__ht._M_bucket_count),
1462 _M_element_count(__ht._M_element_count),
1463 _M_rehash_policy(__ht._M_rehash_policy)
1465 if (__ht._M_node_allocator() == this->_M_node_allocator())
1467 if (__ht._M_uses_single_bucket())
1469 _M_buckets = &_M_single_bucket;
1470 _M_single_bucket = __ht._M_single_bucket;
1473 _M_buckets = __ht._M_buckets;
1477 _M_update_bbegin(__ht._M_begin());
1483 __alloc_node_gen_t __alloc_gen(*
this);
1485 using _Fwd_Ht =
typename
1486 conditional<__move_if_noexcept_cond<value_type>::value,
1487 const _Hashtable&, _Hashtable&&>::type;
1488 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1493 template<
typename _Key,
typename _Value,
typename _Alloc,
1494 typename _ExtractKey,
typename _Equal,
1495 typename _Hash,
typename _RangeHash,
typename _Unused,
1496 typename _RehashPolicy,
typename _Traits>
1497 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1498 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1499 ~_Hashtable() noexcept
1502 _M_deallocate_buckets();
1505 template<
typename _Key,
typename _Value,
typename _Alloc,
1506 typename _ExtractKey,
typename _Equal,
1507 typename _Hash,
typename _RangeHash,
typename _Unused,
1508 typename _RehashPolicy,
typename _Traits>
1510 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1511 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
::
1512 swap(_Hashtable& __x)
1513 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1514 __is_nothrow_swappable<_Equal>>::value)
1521 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1522 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1525 if (this->_M_uses_single_bucket())
1527 if (!__x._M_uses_single_bucket())
1529 _M_buckets = __x._M_buckets;
1530 __x._M_buckets = &__x._M_single_bucket;
1533 else if (__x._M_uses_single_bucket())
1535 __x._M_buckets = _M_buckets;
1536 _M_buckets = &_M_single_bucket;
1541 std::swap(_M_bucket_count, __x._M_bucket_count);
1542 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1543 std::swap(_M_element_count, __x._M_element_count);
1544 std::swap(_M_single_bucket, __x._M_single_bucket);
1549 __x._M_update_bbegin();
1552 template<
typename _Key,
typename _Value,
typename _Alloc,
1553 typename _ExtractKey,
typename _Equal,
1554 typename _Hash,
typename _RangeHash,
typename _Unused,
1555 typename _RehashPolicy,
typename _Traits>
1557 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1558 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1559 find(
const key_type& __k)
1562 __hash_code __code = this->_M_hash_code(__k);
1563 std::size_t __bkt = _M_bucket_index(__code);
1564 return iterator(_M_find_node(__bkt, __k, __code));
1567 template<
typename _Key,
typename _Value,
typename _Alloc,
1568 typename _ExtractKey,
typename _Equal,
1569 typename _Hash,
typename _RangeHash,
typename _Unused,
1570 typename _RehashPolicy,
typename _Traits>
1572 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1573 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1574 find(
const key_type& __k)
const
1577 __hash_code __code = this->_M_hash_code(__k);
1578 std::size_t __bkt = _M_bucket_index(__code);
1579 return const_iterator(_M_find_node(__bkt, __k, __code));
1582 #if __cplusplus > 201703L
1583 template<
typename _Key,
typename _Value,
typename _Alloc,
1584 typename _ExtractKey,
typename _Equal,
1585 typename _Hash,
typename _RangeHash,
typename _Unused,
1586 typename _RehashPolicy,
typename _Traits>
1587 template<
typename _Kt,
typename,
typename>
1589 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1590 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1591 _M_find_tr(
const _Kt& __k)
1594 __hash_code __code = this->_M_hash_code_tr(__k);
1595 std::size_t __bkt = _M_bucket_index(__code);
1596 return iterator(_M_find_node_tr(__bkt, __k, __code));
1599 template<
typename _Key,
typename _Value,
typename _Alloc,
1600 typename _ExtractKey,
typename _Equal,
1601 typename _Hash,
typename _RangeHash,
typename _Unused,
1602 typename _RehashPolicy,
typename _Traits>
1603 template<
typename _Kt,
typename,
typename>
1605 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1606 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1607 _M_find_tr(
const _Kt& __k)
const
1610 __hash_code __code = this->_M_hash_code_tr(__k);
1611 std::size_t __bkt = _M_bucket_index(__code);
1612 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1616 template<
typename _Key,
typename _Value,
typename _Alloc,
1617 typename _ExtractKey,
typename _Equal,
1618 typename _Hash,
typename _RangeHash,
typename _Unused,
1619 typename _RehashPolicy,
typename _Traits>
1621 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1622 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1623 count(
const key_type& __k)
const
1626 auto __it = find(__k);
1630 if (__unique_keys::value)
1636 size_type __result = 1;
1637 for (
auto __ref = __it++;
1638 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1645 #if __cplusplus > 201703L
1646 template<
typename _Key,
typename _Value,
typename _Alloc,
1647 typename _ExtractKey,
typename _Equal,
1648 typename _Hash,
typename _RangeHash,
typename _Unused,
1649 typename _RehashPolicy,
typename _Traits>
1650 template<
typename _Kt,
typename,
typename>
1652 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1653 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1654 _M_count_tr(
const _Kt& __k)
const
1657 __hash_code __code = this->_M_hash_code_tr(__k);
1658 std::size_t __bkt = _M_bucket_index(__code);
1659 auto __n = _M_find_node_tr(__bkt, __k, __code);
1667 size_type __result = 1;
1669 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1677 template<
typename _Key,
typename _Value,
typename _Alloc,
1678 typename _ExtractKey,
typename _Equal,
1679 typename _Hash,
typename _RangeHash,
typename _Unused,
1680 typename _RehashPolicy,
typename _Traits>
1682 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1683 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1684 equal_range(
const key_type& __k)
1685 -> pair<iterator, iterator>
1687 auto __ite = find(__k);
1689 return { __ite, __ite };
1691 auto __beg = __ite++;
1692 if (__unique_keys::value)
1693 return { __beg, __ite };
1698 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1701 return { __beg, __ite };
1704 template<
typename _Key,
typename _Value,
typename _Alloc,
1705 typename _ExtractKey,
typename _Equal,
1706 typename _Hash,
typename _RangeHash,
typename _Unused,
1707 typename _RehashPolicy,
typename _Traits>
1709 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1710 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1711 equal_range(
const key_type& __k)
const
1712 -> pair<const_iterator, const_iterator>
1714 auto __ite = find(__k);
1716 return { __ite, __ite };
1718 auto __beg = __ite++;
1719 if (__unique_keys::value)
1720 return { __beg, __ite };
1725 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1728 return { __beg, __ite };
1731 #if __cplusplus > 201703L
1732 template<
typename _Key,
typename _Value,
typename _Alloc,
1733 typename _ExtractKey,
typename _Equal,
1734 typename _Hash,
typename _RangeHash,
typename _Unused,
1735 typename _RehashPolicy,
typename _Traits>
1736 template<
typename _Kt,
typename,
typename>
1738 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1739 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1740 _M_equal_range_tr(
const _Kt& __k)
1741 -> pair<iterator, iterator>
1743 __hash_code __code = this->_M_hash_code_tr(__k);
1744 std::size_t __bkt = _M_bucket_index(__code);
1745 auto __n = _M_find_node_tr(__bkt, __k, __code);
1746 iterator __ite(__n);
1748 return { __ite, __ite };
1753 auto __beg = __ite++;
1754 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1757 return { __beg, __ite };
1760 template<
typename _Key,
typename _Value,
typename _Alloc,
1761 typename _ExtractKey,
typename _Equal,
1762 typename _Hash,
typename _RangeHash,
typename _Unused,
1763 typename _RehashPolicy,
typename _Traits>
1764 template<
typename _Kt,
typename,
typename>
1766 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1767 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1768 _M_equal_range_tr(
const _Kt& __k)
const
1769 -> pair<const_iterator, const_iterator>
1771 __hash_code __code = this->_M_hash_code_tr(__k);
1772 std::size_t __bkt = _M_bucket_index(__code);
1773 auto __n = _M_find_node_tr(__bkt, __k, __code);
1774 const_iterator __ite(__n);
1776 return { __ite, __ite };
1781 auto __beg = __ite++;
1782 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1785 return { __beg, __ite };
1791 template<
typename _Key,
typename _Value,
typename _Alloc,
1792 typename _ExtractKey,
typename _Equal,
1793 typename _Hash,
typename _RangeHash,
typename _Unused,
1794 typename _RehashPolicy,
typename _Traits>
1796 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1797 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1798 _M_find_before_node(size_type __bkt,
const key_type& __k,
1799 __hash_code __code)
const
1802 __node_base_ptr __prev_p = _M_buckets[__bkt];
1806 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1807 __p = __p->_M_next())
1809 if (this->_M_equals(__k, __code, *__p))
1812 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1820 template<
typename _Key,
typename _Value,
typename _Alloc,
1821 typename _ExtractKey,
typename _Equal,
1822 typename _Hash,
typename _RangeHash,
typename _Unused,
1823 typename _RehashPolicy,
typename _Traits>
1824 template<
typename _Kt>
1826 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1827 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1828 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1829 __hash_code __code)
const
1832 __node_base_ptr __prev_p = _M_buckets[__bkt];
1836 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1837 __p = __p->_M_next())
1839 if (this->_M_equals_tr(__k, __code, *__p))
1842 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1850 template<
typename _Key,
typename _Value,
typename _Alloc,
1851 typename _ExtractKey,
typename _Equal,
1852 typename _Hash,
typename _RangeHash,
typename _Unused,
1853 typename _RehashPolicy,
typename _Traits>
1855 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1856 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1857 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1859 if (_M_buckets[__bkt])
1863 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1864 _M_buckets[__bkt]->_M_nxt = __node;
1871 __node->_M_nxt = _M_before_begin._M_nxt;
1872 _M_before_begin._M_nxt = __node;
1877 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
1879 _M_buckets[__bkt] = &_M_before_begin;
1883 template<
typename _Key,
typename _Value,
typename _Alloc,
1884 typename _ExtractKey,
typename _Equal,
1885 typename _Hash,
typename _RangeHash,
typename _Unused,
1886 typename _RehashPolicy,
typename _Traits>
1888 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1889 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1890 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
1891 size_type __next_bkt)
1893 if (!__next || __next_bkt != __bkt)
1898 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1901 if (&_M_before_begin == _M_buckets[__bkt])
1902 _M_before_begin._M_nxt = __next;
1903 _M_buckets[__bkt] =
nullptr;
1907 template<
typename _Key,
typename _Value,
typename _Alloc,
1908 typename _ExtractKey,
typename _Equal,
1909 typename _Hash,
typename _RangeHash,
typename _Unused,
1910 typename _RehashPolicy,
typename _Traits>
1912 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1913 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1914 _M_get_previous_node(size_type __bkt, __node_ptr __n)
1917 __node_base_ptr __prev_n = _M_buckets[__bkt];
1918 while (__prev_n->_M_nxt != __n)
1919 __prev_n = __prev_n->_M_nxt;
1923 template<
typename _Key,
typename _Value,
typename _Alloc,
1924 typename _ExtractKey,
typename _Equal,
1925 typename _Hash,
typename _RangeHash,
typename _Unused,
1926 typename _RehashPolicy,
typename _Traits>
1927 template<
typename... _Args>
1929 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1930 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1931 _M_emplace(
true_type , _Args&&... __args)
1932 -> pair<iterator, bool>
1935 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1936 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1937 __hash_code __code = this->_M_hash_code(__k);
1938 size_type __bkt = _M_bucket_index(__code);
1939 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
1941 return std::make_pair(iterator(__p),
false);
1944 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
1945 __node._M_node =
nullptr;
1946 return { __pos,
true };
1949 template<
typename _Key,
typename _Value,
typename _Alloc,
1950 typename _ExtractKey,
typename _Equal,
1951 typename _Hash,
typename _RangeHash,
typename _Unused,
1952 typename _RehashPolicy,
typename _Traits>
1953 template<
typename... _Args>
1955 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1956 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1957 _M_emplace(const_iterator __hint,
false_type ,
1962 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1963 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1965 __hash_code __code = this->_M_hash_code(__k);
1967 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
1968 __node._M_node =
nullptr;
1972 template<
typename _Key,
typename _Value,
typename _Alloc,
1973 typename _ExtractKey,
typename _Equal,
1974 typename _Hash,
typename _RangeHash,
typename _Unused,
1975 typename _RehashPolicy,
typename _Traits>
1977 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1978 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1979 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1980 __node_ptr __node, size_type __n_elt)
1983 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1985 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
1988 if (__do_rehash.
first)
1990 _M_rehash(__do_rehash.
second, __saved_state);
1991 __bkt = _M_bucket_index(__code);
1994 this->_M_store_code(*__node, __code);
1997 _M_insert_bucket_begin(__bkt, __node);
1999 return iterator(__node);
2002 template<
typename _Key,
typename _Value,
typename _Alloc,
2003 typename _ExtractKey,
typename _Equal,
2004 typename _Hash,
typename _RangeHash,
typename _Unused,
2005 typename _RehashPolicy,
typename _Traits>
2007 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2008 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2009 _M_insert_multi_node(__node_ptr __hint,
2010 __hash_code __code, __node_ptr __node)
2013 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2015 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2017 if (__do_rehash.
first)
2018 _M_rehash(__do_rehash.
second, __saved_state);
2020 this->_M_store_code(*__node, __code);
2021 const key_type& __k = _ExtractKey{}(__node->_M_v());
2022 size_type __bkt = _M_bucket_index(__code);
2026 __node_base_ptr __prev
2027 = __builtin_expect(__hint !=
nullptr,
false)
2028 && this->_M_equals(__k, __code, *__hint)
2030 : _M_find_before_node(__bkt, __k, __code);
2035 __node->_M_nxt = __prev->_M_nxt;
2036 __prev->_M_nxt = __node;
2037 if (__builtin_expect(__prev == __hint,
false))
2041 && !this->_M_equals(__k, __code, *__node->_M_next()))
2043 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2044 if (__next_bkt != __bkt)
2045 _M_buckets[__next_bkt] = __node;
2052 _M_insert_bucket_begin(__bkt, __node);
2054 return iterator(__node);
2058 template<
typename _Key,
typename _Value,
typename _Alloc,
2059 typename _ExtractKey,
typename _Equal,
2060 typename _Hash,
typename _RangeHash,
typename _Unused,
2061 typename _RehashPolicy,
typename _Traits>
2062 template<
typename _Arg,
typename _NodeGenerator>
2064 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2065 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2066 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
2068 -> pair<iterator, bool>
2070 const key_type& __k = _ExtractKey{}(__v);
2071 __hash_code __code = this->_M_hash_code(__k);
2072 size_type __bkt = _M_bucket_index(__code);
2074 if (__node_ptr __node = _M_find_node(__bkt, __k, __code))
2075 return { iterator(__node),
false };
2077 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2079 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2080 __node._M_node =
nullptr;
2081 return { __pos,
true };
2085 template<
typename _Key,
typename _Value,
typename _Alloc,
2086 typename _ExtractKey,
typename _Equal,
2087 typename _Hash,
typename _RangeHash,
typename _Unused,
2088 typename _RehashPolicy,
typename _Traits>
2089 template<
typename _Arg,
typename _NodeGenerator>
2091 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2092 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2093 _M_insert(const_iterator __hint, _Arg&& __v,
2094 const _NodeGenerator& __node_gen,
2100 __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
2103 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2105 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
2106 __node._M_node =
nullptr;
2110 template<
typename _Key,
typename _Value,
typename _Alloc,
2111 typename _ExtractKey,
typename _Equal,
2112 typename _Hash,
typename _RangeHash,
typename _Unused,
2113 typename _RehashPolicy,
typename _Traits>
2115 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2116 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2117 erase(const_iterator __it)
2120 __node_ptr __n = __it._M_cur;
2121 std::size_t __bkt = _M_bucket_index(*__n);
2126 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2127 return _M_erase(__bkt, __prev_n, __n);
2130 template<
typename _Key,
typename _Value,
typename _Alloc,
2131 typename _ExtractKey,
typename _Equal,
2132 typename _Hash,
typename _RangeHash,
typename _Unused,
2133 typename _RehashPolicy,
typename _Traits>
2135 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2136 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2137 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2140 if (__prev_n == _M_buckets[__bkt])
2141 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2142 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2143 else if (__n->_M_nxt)
2145 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2146 if (__next_bkt != __bkt)
2147 _M_buckets[__next_bkt] = __prev_n;
2150 __prev_n->_M_nxt = __n->_M_nxt;
2151 iterator __result(__n->_M_next());
2152 this->_M_deallocate_node(__n);
2158 template<
typename _Key,
typename _Value,
typename _Alloc,
2159 typename _ExtractKey,
typename _Equal,
2160 typename _Hash,
typename _RangeHash,
typename _Unused,
2161 typename _RehashPolicy,
typename _Traits>
2163 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2164 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2165 _M_erase(
true_type ,
const key_type& __k)
2168 __hash_code __code = this->_M_hash_code(__k);
2169 std::size_t __bkt = _M_bucket_index(__code);
2172 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2177 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2178 _M_erase(__bkt, __prev_n, __n);
2182 template<
typename _Key,
typename _Value,
typename _Alloc,
2183 typename _ExtractKey,
typename _Equal,
2184 typename _Hash,
typename _RangeHash,
typename _Unused,
2185 typename _RehashPolicy,
typename _Traits>
2187 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2188 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2192 __hash_code __code = this->_M_hash_code(__k);
2193 std::size_t __bkt = _M_bucket_index(__code);
2196 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2206 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2207 __node_ptr __n_last = __n->_M_next();
2208 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2209 __n_last = __n_last->_M_next();
2211 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2214 size_type __result = 0;
2217 __node_ptr __p = __n->_M_next();
2218 this->_M_deallocate_node(__n);
2222 while (__n != __n_last);
2224 _M_element_count -= __result;
2225 if (__prev_n == _M_buckets[__bkt])
2226 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2227 else if (__n_last_bkt != __bkt)
2228 _M_buckets[__n_last_bkt] = __prev_n;
2229 __prev_n->_M_nxt = __n_last;
2233 template<
typename _Key,
typename _Value,
typename _Alloc,
2234 typename _ExtractKey,
typename _Equal,
2235 typename _Hash,
typename _RangeHash,
typename _Unused,
2236 typename _RehashPolicy,
typename _Traits>
2238 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2239 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2240 erase(const_iterator __first, const_iterator __last)
2243 __node_ptr __n = __first._M_cur;
2244 __node_ptr __last_n = __last._M_cur;
2245 if (__n == __last_n)
2246 return iterator(__n);
2248 std::size_t __bkt = _M_bucket_index(*__n);
2250 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2251 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2252 std::size_t __n_bkt = __bkt;
2257 __node_ptr __tmp = __n;
2258 __n = __n->_M_next();
2259 this->_M_deallocate_node(__tmp);
2263 __n_bkt = _M_bucket_index(*__n);
2265 while (__n != __last_n && __n_bkt == __bkt);
2266 if (__is_bucket_begin)
2267 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2268 if (__n == __last_n)
2270 __is_bucket_begin =
true;
2274 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2275 _M_buckets[__n_bkt] = __prev_n;
2276 __prev_n->_M_nxt = __n;
2277 return iterator(__n);
2280 template<
typename _Key,
typename _Value,
typename _Alloc,
2281 typename _ExtractKey,
typename _Equal,
2282 typename _Hash,
typename _RangeHash,
typename _Unused,
2283 typename _RehashPolicy,
typename _Traits>
2285 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2286 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2289 this->_M_deallocate_nodes(_M_begin());
2290 __builtin_memset(_M_buckets, 0,
2291 _M_bucket_count *
sizeof(__node_base_ptr));
2292 _M_element_count = 0;
2293 _M_before_begin._M_nxt =
nullptr;
2296 template<
typename _Key,
typename _Value,
typename _Alloc,
2297 typename _ExtractKey,
typename _Equal,
2298 typename _Hash,
typename _RangeHash,
typename _Unused,
2299 typename _RehashPolicy,
typename _Traits>
2301 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2302 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2303 rehash(size_type __bkt_count)
2305 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2307 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2309 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2311 if (__bkt_count != _M_bucket_count)
2312 _M_rehash(__bkt_count, __saved_state);
2316 _M_rehash_policy._M_reset(__saved_state);
2319 template<
typename _Key,
typename _Value,
typename _Alloc,
2320 typename _ExtractKey,
typename _Equal,
2321 typename _Hash,
typename _RangeHash,
typename _Unused,
2322 typename _RehashPolicy,
typename _Traits>
2324 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2325 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2326 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2330 _M_rehash_aux(__bkt_count, __unique_keys{});
2336 _M_rehash_policy._M_reset(__state);
2337 __throw_exception_again;
2342 template<
typename _Key,
typename _Value,
typename _Alloc,
2343 typename _ExtractKey,
typename _Equal,
2344 typename _Hash,
typename _RangeHash,
typename _Unused,
2345 typename _RehashPolicy,
typename _Traits>
2347 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2348 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2349 _M_rehash_aux(size_type __bkt_count,
true_type )
2351 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2352 __node_ptr __p = _M_begin();
2353 _M_before_begin._M_nxt =
nullptr;
2354 std::size_t __bbegin_bkt = 0;
2357 __node_ptr __next = __p->_M_next();
2359 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2360 if (!__new_buckets[__bkt])
2362 __p->_M_nxt = _M_before_begin._M_nxt;
2363 _M_before_begin._M_nxt = __p;
2364 __new_buckets[__bkt] = &_M_before_begin;
2366 __new_buckets[__bbegin_bkt] = __p;
2367 __bbegin_bkt = __bkt;
2371 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2372 __new_buckets[__bkt]->_M_nxt = __p;
2378 _M_deallocate_buckets();
2379 _M_bucket_count = __bkt_count;
2380 _M_buckets = __new_buckets;
2385 template<
typename _Key,
typename _Value,
typename _Alloc,
2386 typename _ExtractKey,
typename _Equal,
2387 typename _Hash,
typename _RangeHash,
typename _Unused,
2388 typename _RehashPolicy,
typename _Traits>
2390 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2391 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2392 _M_rehash_aux(size_type __bkt_count,
false_type )
2394 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2395 __node_ptr __p = _M_begin();
2396 _M_before_begin._M_nxt =
nullptr;
2397 std::size_t __bbegin_bkt = 0;
2398 std::size_t __prev_bkt = 0;
2399 __node_ptr __prev_p =
nullptr;
2400 bool __check_bucket =
false;
2404 __node_ptr __next = __p->_M_next();
2406 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2408 if (__prev_p && __prev_bkt == __bkt)
2413 __p->_M_nxt = __prev_p->_M_nxt;
2414 __prev_p->_M_nxt = __p;
2421 __check_bucket =
true;
2429 if (__prev_p->_M_nxt)
2431 std::size_t __next_bkt
2432 = __hash_code_base::_M_bucket_index(
2433 *__prev_p->_M_next(), __bkt_count);
2434 if (__next_bkt != __prev_bkt)
2435 __new_buckets[__next_bkt] = __prev_p;
2437 __check_bucket =
false;
2440 if (!__new_buckets[__bkt])
2442 __p->_M_nxt = _M_before_begin._M_nxt;
2443 _M_before_begin._M_nxt = __p;
2444 __new_buckets[__bkt] = &_M_before_begin;
2446 __new_buckets[__bbegin_bkt] = __p;
2447 __bbegin_bkt = __bkt;
2451 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2452 __new_buckets[__bkt]->_M_nxt = __p;
2460 if (__check_bucket && __prev_p->_M_nxt)
2462 std::size_t __next_bkt
2463 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2465 if (__next_bkt != __prev_bkt)
2466 __new_buckets[__next_bkt] = __prev_p;
2469 _M_deallocate_buckets();
2470 _M_bucket_count = __bkt_count;
2471 _M_buckets = __new_buckets;
2474 #if __cplusplus > 201402L
2475 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2478 #if __cpp_deduction_guides >= 201606
2480 template<
typename _Hash>
2481 using _RequireNotAllocatorOrIntegral
2482 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2485 _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.
_T1 first
The first member.
_T2 second
The second member.
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.
Uniform interface to C++98 and C++11 allocators.