31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
37 #if __cplusplus > 201402L
41 namespace std _GLIBCXX_VISIBILITY(default)
43 _GLIBCXX_BEGIN_NAMESPACE_VERSION
45 template<
typename _Tp,
typename _Hash>
48 __is_fast_hash<_Hash>,
50 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
55 template<
typename _Equal,
typename _Hash,
typename _Allocator>
56 using _Hashtable_enable_default_ctor
57 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
58 is_default_constructible<_Hash>,
59 is_default_constructible<_Allocator>>{},
60 __detail::_Hash_node_base>;
175 template<
typename _Key,
typename _Value,
typename _Alloc,
176 typename _ExtractKey,
typename _Equal,
177 typename _Hash,
typename _RangeHash,
typename _Unused,
178 typename _RehashPolicy,
typename _Traits>
181 _Hash, _RangeHash, _Unused, _Traits>,
183 _Hash, _RangeHash, _Unused,
184 _RehashPolicy, _Traits>,
186 _Hash, _RangeHash, _Unused,
187 _RehashPolicy, _Traits>,
189 _Hash, _RangeHash, _Unused,
190 _RehashPolicy, _Traits>,
192 _Hash, _RangeHash, _Unused,
193 _RehashPolicy, _Traits>,
195 __alloc_rebind<_Alloc,
196 __detail::_Hash_node<_Value,
197 _Traits::__hash_cached::value>>>,
200 static_assert(
is_same<
typename remove_cv<_Value>::type, _Value>::value,
201 "unordered container must have a non-const, non-volatile value_type");
202 #if __cplusplus > 201703L || defined __STRICT_ANSI__
204 "unordered container must have the same value_type as its allocator");
207 using __traits_type = _Traits;
208 using __hash_cached =
typename __traits_type::__hash_cached;
209 using __constant_iterators =
typename __traits_type::__constant_iterators;
211 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
215 using __node_value_type =
216 __detail::_Hash_node_value<_Value, __hash_cached::value>;
217 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
218 using __value_alloc_traits =
219 typename __hashtable_alloc::__value_alloc_traits;
220 using __node_alloc_traits =
229 _RehashPolicy, _Traits>;
234 typedef _Key key_type;
235 typedef _Value value_type;
236 typedef _Alloc allocator_type;
237 typedef _Equal key_equal;
241 typedef typename __value_alloc_traits::pointer pointer;
242 typedef typename __value_alloc_traits::const_pointer const_pointer;
243 typedef value_type& reference;
244 typedef const value_type& const_reference;
246 using iterator =
typename __insert_base::iterator;
248 using const_iterator =
typename __insert_base::const_iterator;
251 _ExtractKey, _Hash, _RangeHash, _Unused,
252 __constant_iterators::value,
253 __hash_cached::value>;
257 _ExtractKey, _Hash, _RangeHash, _Unused,
258 __constant_iterators::value, __hash_cached::value>;
261 using __rehash_type = _RehashPolicy;
262 using __rehash_state =
typename __rehash_type::_State;
264 using __unique_keys =
typename __traits_type::__unique_keys;
267 _Hashtable_base<_Key, _Value, _ExtractKey,
268 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
271 using __hash_code =
typename __hashtable_base::__hash_code;
272 using __ireturn_type =
typename __insert_base::__ireturn_type;
275 _Equal, _Hash, _RangeHash, _Unused,
276 _RehashPolicy, _Traits>;
280 _Hash, _RangeHash, _Unused,
281 _RehashPolicy, _Traits>;
284 _Equal, _Hash, _RangeHash, _Unused,
285 _RehashPolicy, _Traits>;
287 using __reuse_or_alloc_node_gen_t =
288 __detail::_ReuseOrAllocNode<__node_alloc_type>;
289 using __alloc_node_gen_t =
290 __detail::_AllocNode<__node_alloc_type>;
297 : _M_h(__h), _M_node(__n) { }
300 template<
typename... _Args>
303 _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
307 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
309 _Scoped_node(
const _Scoped_node&) =
delete;
310 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
316 template<
typename _Ht>
319 const value_type&, value_type&&>::type
320 __fwd_value_for(value_type& __val) noexcept
327 struct __hash_code_base_access : __hash_code_base
328 {
using __hash_code_base::_M_bucket_index; };
332 static_assert(noexcept(declval<const __hash_code_base_access&>()
333 ._M_bucket_index(declval<const __node_value_type&>(),
335 "Cache the hash code or qualify your functors involved"
336 " in hash code and bucket index computation with noexcept");
340 "Functor used to map hash code to bucket index"
341 " must be nothrow default constructible");
342 static_assert(noexcept(
343 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
344 "Functor used to map hash code to bucket index must be"
349 "_ExtractKey must be nothrow default constructible");
350 static_assert(noexcept(
351 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
352 "_ExtractKey functor must be noexcept invocable");
354 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
355 typename _ExtractKeya,
typename _Equala,
356 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
357 typename _RehashPolicya,
typename _Traitsa,
361 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
362 typename _ExtractKeya,
typename _Equala,
363 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
364 typename _RehashPolicya,
typename _Traitsa>
367 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
368 typename _ExtractKeya,
typename _Equala,
369 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
370 typename _RehashPolicya,
typename _Traitsa,
371 bool _Constant_iteratorsa>
374 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
375 typename _ExtractKeya,
typename _Equala,
376 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
377 typename _RehashPolicya,
typename _Traitsa,
382 using size_type =
typename __hashtable_base::size_type;
383 using difference_type =
typename __hashtable_base::difference_type;
385 #if __cplusplus > 201402L
391 __buckets_ptr _M_buckets = &_M_single_bucket;
392 size_type _M_bucket_count = 1;
393 __node_base _M_before_begin;
394 size_type _M_element_count = 0;
395 _RehashPolicy _M_rehash_policy;
403 __node_base_ptr _M_single_bucket =
nullptr;
409 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
413 _M_update_bbegin(__node_ptr __n)
415 _M_before_begin._M_nxt = __n;
420 _M_uses_single_bucket(__buckets_ptr __bkts)
const
421 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
424 _M_uses_single_bucket()
const
425 {
return _M_uses_single_bucket(_M_buckets); }
428 _M_base_alloc() {
return *
this; }
431 _M_allocate_buckets(size_type __bkt_count)
433 if (__builtin_expect(__bkt_count == 1,
false))
435 _M_single_bucket =
nullptr;
436 return &_M_single_bucket;
439 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
443 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
445 if (_M_uses_single_bucket(__bkts))
448 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
452 _M_deallocate_buckets()
453 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
458 _M_bucket_begin(size_type __bkt)
const;
462 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
466 template<
typename _Ht>
468 _M_assign_elements(_Ht&&);
470 template<
typename _Ht,
typename _NodeGenerator>
472 _M_assign(_Ht&&,
const _NodeGenerator&);
483 _Hashtable(
const _Hash& __h,
const _Equal& __eq,
484 const allocator_type& __a)
490 template<
bool _No_realloc = true>
491 static constexpr
bool
494 #if __cplusplus <= 201402L
495 return __and_<__bool_constant<_No_realloc>,
499 if constexpr (_No_realloc)
508 noexcept(_S_nothrow_move());
513 template<
typename _InputIterator>
514 _Hashtable(_InputIterator __first, _InputIterator __last,
515 size_type __bkt_count_hint,
516 const _Hash&,
const _Equal&,
const allocator_type&,
519 template<
typename _InputIterator>
520 _Hashtable(_InputIterator __first, _InputIterator __last,
521 size_type __bkt_count_hint,
522 const _Hash&,
const _Equal&,
const allocator_type&,
535 const _Hash& __hf = _Hash(),
536 const key_equal& __eql = key_equal(),
537 const allocator_type& __a = allocator_type());
541 noexcept(_S_nothrow_move())
547 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
549 typename __node_alloc_traits::is_always_equal{})
558 template<
typename _InputIterator>
559 _Hashtable(_InputIterator __f, _InputIterator __l,
560 size_type __bkt_count_hint = 0,
561 const _Hash& __hf = _Hash(),
562 const key_equal& __eql = key_equal(),
563 const allocator_type& __a = allocator_type())
564 :
_Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
569 size_type __bkt_count_hint = 0,
570 const _Hash& __hf = _Hash(),
571 const key_equal& __eql = key_equal(),
572 const allocator_type& __a = allocator_type())
573 :
_Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
574 __hf, __eql, __a, __unique_keys{})
582 noexcept(__node_alloc_traits::_S_nothrow_move()
586 constexpr
bool __move_storage =
587 __node_alloc_traits::_S_propagate_on_move_assign()
588 || __node_alloc_traits::_S_always_equal();
589 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
596 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
597 _M_before_begin._M_nxt =
nullptr;
601 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
604 if (_M_bucket_count < __l_bkt_count)
605 rehash(__l_bkt_count);
607 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
615 noexcept(__and_<__is_nothrow_swappable<_Hash>,
616 __is_nothrow_swappable<_Equal>>::value);
621 {
return iterator(_M_begin()); }
624 begin()
const noexcept
625 {
return const_iterator(_M_begin()); }
629 {
return iterator(
nullptr); }
633 {
return const_iterator(
nullptr); }
637 {
return const_iterator(_M_begin()); }
640 cend()
const noexcept
641 {
return const_iterator(
nullptr); }
644 size()
const noexcept
645 {
return _M_element_count; }
647 _GLIBCXX_NODISCARD
bool
648 empty()
const noexcept
649 {
return size() == 0; }
652 get_allocator()
const noexcept
653 {
return allocator_type(this->_M_node_allocator()); }
656 max_size()
const noexcept
657 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
662 {
return this->_M_eq(); }
668 bucket_count()
const noexcept
669 {
return _M_bucket_count; }
672 max_bucket_count()
const noexcept
673 {
return max_size(); }
676 bucket_size(size_type __bkt)
const
680 bucket(
const key_type& __k)
const
681 {
return _M_bucket_index(this->_M_hash_code(__k)); }
684 begin(size_type __bkt)
687 __bkt, _M_bucket_count);
692 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
695 begin(size_type __bkt)
const
698 __bkt, _M_bucket_count);
702 end(size_type __bkt)
const
707 cbegin(size_type __bkt)
const
710 __bkt, _M_bucket_count);
714 cend(size_type __bkt)
const
718 load_factor()
const noexcept
720 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
729 __rehash_policy()
const
730 {
return _M_rehash_policy; }
733 __rehash_policy(
const _RehashPolicy& __pol)
734 { _M_rehash_policy = __pol; }
738 find(
const key_type& __k);
741 find(
const key_type& __k)
const;
744 count(
const key_type& __k)
const;
747 equal_range(
const key_type& __k);
750 equal_range(
const key_type& __k)
const;
752 #if __cplusplus >= 202002L
753 #define __cpp_lib_generic_unordered_lookup 201811L
755 template<
typename _Kt,
756 typename = __has_is_transparent_t<_Hash, _Kt>,
757 typename = __has_is_transparent_t<_Equal, _Kt>>
759 _M_find_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_find_tr(
const _Kt& __k)
const;
767 template<
typename _Kt,
768 typename = __has_is_transparent_t<_Hash, _Kt>,
769 typename = __has_is_transparent_t<_Equal, _Kt>>
771 _M_count_tr(
const _Kt& __k)
const;
773 template<
typename _Kt,
774 typename = __has_is_transparent_t<_Hash, _Kt>,
775 typename = __has_is_transparent_t<_Equal, _Kt>>
777 _M_equal_range_tr(
const _Kt& __k);
779 template<
typename _Kt,
780 typename = __has_is_transparent_t<_Hash, _Kt>,
781 typename = __has_is_transparent_t<_Equal, _Kt>>
783 _M_equal_range_tr(
const _Kt& __k)
const;
789 _M_bucket_index(
const __node_value_type& __n)
const noexcept
790 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
793 _M_bucket_index(__hash_code __c)
const
794 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
799 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
801 template<
typename _Kt>
803 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
806 _M_find_node(size_type __bkt,
const key_type& __key,
807 __hash_code __c)
const
809 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
811 return static_cast<__node_ptr
>(__before_n->_M_nxt);
815 template<
typename _Kt>
817 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
818 __hash_code __c)
const
820 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
822 return static_cast<__node_ptr
>(__before_n->_M_nxt);
828 _M_insert_bucket_begin(size_type, __node_ptr);
832 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
833 size_type __next_bkt);
837 _M_get_previous_node(size_type __bkt, __node_ptr __n);
843 _M_insert_unique_node(size_type __bkt, __hash_code,
844 __node_ptr __n, size_type __n_elt = 1);
849 _M_insert_multi_node(__node_ptr __hint,
850 __hash_code __code, __node_ptr __n);
852 template<
typename... _Args>
854 _M_emplace(
true_type __uks, _Args&&... __args);
856 template<
typename... _Args>
858 _M_emplace(
false_type __uks, _Args&&... __args)
859 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
862 template<
typename... _Args>
864 _M_emplace(const_iterator,
true_type __uks, _Args&&... __args)
865 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
867 template<
typename... _Args>
869 _M_emplace(const_iterator,
false_type __uks, _Args&&... __args);
871 template<
typename _Arg,
typename _NodeGenerator>
873 _M_insert(_Arg&&,
const _NodeGenerator&,
true_type __uks);
875 template<
typename _Arg,
typename _NodeGenerator>
877 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
880 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
885 template<
typename _Arg,
typename _NodeGenerator>
887 _M_insert(const_iterator, _Arg&& __arg,
888 const _NodeGenerator& __node_gen,
true_type __uks)
891 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).
first;
895 template<
typename _Arg,
typename _NodeGenerator>
897 _M_insert(const_iterator, _Arg&&,
901 _M_erase(
true_type __uks,
const key_type&);
907 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
911 template<
typename... _Args>
913 emplace(_Args&&... __args)
914 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
916 template<
typename... _Args>
918 emplace_hint(const_iterator __hint, _Args&&... __args)
920 return _M_emplace(__hint, __unique_keys{},
921 std::forward<_Args>(__args)...);
928 erase(const_iterator);
933 {
return erase(const_iterator(__it)); }
936 erase(
const key_type& __k)
937 {
return _M_erase(__unique_keys{}, __k); }
940 erase(const_iterator, const_iterator);
947 void rehash(size_type __bkt_count);
952 #if __cplusplus > 201402L
959 __ret.position =
end();
962 __glibcxx_assert(get_allocator() == __nh.get_allocator());
964 const key_type& __k = __nh._M_key();
965 __hash_code __code = this->_M_hash_code(__k);
966 size_type __bkt = _M_bucket_index(__code);
967 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
970 __ret.position = iterator(__n);
971 __ret.inserted =
false;
976 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
977 __nh._M_ptr =
nullptr;
978 __ret.inserted =
true;
991 __glibcxx_assert(get_allocator() == __nh.get_allocator());
993 const key_type& __k = __nh._M_key();
994 auto __code = this->_M_hash_code(__k);
996 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
997 __nh._M_ptr =
nullptr;
1003 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1005 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1006 if (__prev_n == _M_buckets[__bkt])
1007 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1008 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1009 else if (__n->_M_nxt)
1011 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1012 if (__next_bkt != __bkt)
1013 _M_buckets[__next_bkt] = __prev_n;
1016 __prev_n->_M_nxt = __n->_M_nxt;
1017 __n->_M_nxt =
nullptr;
1019 return { __n, this->_M_node_allocator() };
1025 extract(const_iterator __pos)
1027 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1028 return _M_extract_node(__bkt,
1029 _M_get_previous_node(__bkt, __pos._M_cur));
1037 __hash_code __code = this->_M_hash_code(__k);
1038 std::size_t __bkt = _M_bucket_index(__code);
1039 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1040 __nh = _M_extract_node(__bkt, __prev_node);
1045 template<
typename _Compatible_Hashtable>
1049 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1050 node_type>,
"Node types are compatible");
1051 __glibcxx_assert(get_allocator() == __src.get_allocator());
1053 auto __n_elt = __src.size();
1054 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1057 const key_type& __k = _ExtractKey{}(*__pos);
1058 __hash_code __code = this->_M_hash_code(__k);
1059 size_type __bkt = _M_bucket_index(__code);
1060 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1062 auto __nh = __src.extract(__pos);
1063 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1064 __nh._M_ptr =
nullptr;
1067 else if (__n_elt != 1)
1073 template<
typename _Compatible_Hashtable>
1077 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1078 node_type>,
"Node types are compatible");
1079 __glibcxx_assert(get_allocator() == __src.get_allocator());
1081 this->reserve(
size() + __src.size());
1082 for (
auto __i = __src.begin(), __end = __src.end(); __i != __end;)
1089 void _M_rehash_aux(size_type __bkt_count,
true_type __uks);
1092 void _M_rehash_aux(size_type __bkt_count,
false_type __uks);
1096 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1101 template<
typename _Key,
typename _Value,
typename _Alloc,
1102 typename _ExtractKey,
typename _Equal,
1103 typename _Hash,
typename _RangeHash,
typename _Unused,
1104 typename _RehashPolicy,
typename _Traits>
1106 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1107 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1108 _M_bucket_begin(size_type __bkt)
const
1111 __node_base_ptr __n = _M_buckets[__bkt];
1112 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
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 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1120 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1121 _Hashtable(size_type __bkt_count_hint,
1122 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1123 : _Hashtable(__h, __eq, __a)
1125 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1126 if (__bkt_count > _M_bucket_count)
1128 _M_buckets = _M_allocate_buckets(__bkt_count);
1129 _M_bucket_count = __bkt_count;
1133 template<
typename _Key,
typename _Value,
typename _Alloc,
1134 typename _ExtractKey,
typename _Equal,
1135 typename _Hash,
typename _RangeHash,
typename _Unused,
1136 typename _RehashPolicy,
typename _Traits>
1137 template<
typename _InputIterator>
1138 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1139 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1140 _Hashtable(_InputIterator __f, _InputIterator __l,
1141 size_type __bkt_count_hint,
1142 const _Hash& __h,
const _Equal& __eq,
1144 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1146 for (; __f != __l; ++__f)
1150 template<
typename _Key,
typename _Value,
typename _Alloc,
1151 typename _ExtractKey,
typename _Equal,
1152 typename _Hash,
typename _RangeHash,
typename _Unused,
1153 typename _RehashPolicy,
typename _Traits>
1154 template<
typename _InputIterator>
1155 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1156 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1157 _Hashtable(_InputIterator __f, _InputIterator __l,
1158 size_type __bkt_count_hint,
1159 const _Hash& __h,
const _Equal& __eq,
1161 : _Hashtable(__h, __eq, __a)
1163 auto __nb_elems = __detail::__distance_fw(__f, __l);
1165 _M_rehash_policy._M_next_bkt(
1166 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1169 if (__bkt_count > _M_bucket_count)
1171 _M_buckets = _M_allocate_buckets(__bkt_count);
1172 _M_bucket_count = __bkt_count;
1175 for (; __f != __l; ++__f)
1179 template<
typename _Key,
typename _Value,
typename _Alloc,
1180 typename _ExtractKey,
typename _Equal,
1181 typename _Hash,
typename _RangeHash,
typename _Unused,
1182 typename _RehashPolicy,
typename _Traits>
1184 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1185 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1186 operator=(
const _Hashtable& __ht)
1192 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1194 auto& __this_alloc = this->_M_node_allocator();
1195 auto& __that_alloc = __ht._M_node_allocator();
1196 if (!__node_alloc_traits::_S_always_equal()
1197 && __this_alloc != __that_alloc)
1200 this->_M_deallocate_nodes(_M_begin());
1201 _M_before_begin._M_nxt =
nullptr;
1202 _M_deallocate_buckets();
1203 _M_buckets =
nullptr;
1204 std::__alloc_on_copy(__this_alloc, __that_alloc);
1205 __hashtable_base::operator=(__ht);
1206 _M_bucket_count = __ht._M_bucket_count;
1207 _M_element_count = __ht._M_element_count;
1208 _M_rehash_policy = __ht._M_rehash_policy;
1209 __alloc_node_gen_t __alloc_node_gen(*
this);
1212 _M_assign(__ht, __alloc_node_gen);
1219 __throw_exception_again;
1223 std::__alloc_on_copy(__this_alloc, __that_alloc);
1227 _M_assign_elements(__ht);
1231 template<
typename _Key,
typename _Value,
typename _Alloc,
1232 typename _ExtractKey,
typename _Equal,
1233 typename _Hash,
typename _RangeHash,
typename _Unused,
1234 typename _RehashPolicy,
typename _Traits>
1235 template<
typename _Ht>
1237 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1238 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1239 _M_assign_elements(_Ht&& __ht)
1241 __buckets_ptr __former_buckets =
nullptr;
1242 std::size_t __former_bucket_count = _M_bucket_count;
1243 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1245 if (_M_bucket_count != __ht._M_bucket_count)
1247 __former_buckets = _M_buckets;
1248 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1249 _M_bucket_count = __ht._M_bucket_count;
1252 __builtin_memset(_M_buckets, 0,
1253 _M_bucket_count *
sizeof(__node_base_ptr));
1257 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1258 _M_element_count = __ht._M_element_count;
1259 _M_rehash_policy = __ht._M_rehash_policy;
1260 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1261 _M_before_begin._M_nxt =
nullptr;
1262 _M_assign(std::forward<_Ht>(__ht), __roan);
1263 if (__former_buckets)
1264 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1268 if (__former_buckets)
1271 _M_deallocate_buckets();
1272 _M_rehash_policy._M_reset(__former_state);
1273 _M_buckets = __former_buckets;
1274 _M_bucket_count = __former_bucket_count;
1276 __builtin_memset(_M_buckets, 0,
1277 _M_bucket_count *
sizeof(__node_base_ptr));
1278 __throw_exception_again;
1282 template<
typename _Key,
typename _Value,
typename _Alloc,
1283 typename _ExtractKey,
typename _Equal,
1284 typename _Hash,
typename _RangeHash,
typename _Unused,
1285 typename _RehashPolicy,
typename _Traits>
1286 template<
typename _Ht,
typename _NodeGenerator>
1288 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1289 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1290 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1292 __buckets_ptr __buckets =
nullptr;
1294 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1298 if (!__ht._M_before_begin._M_nxt)
1303 __node_ptr __ht_n = __ht._M_begin();
1305 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1306 this->_M_copy_code(*__this_n, *__ht_n);
1307 _M_update_bbegin(__this_n);
1310 __node_ptr __prev_n = __this_n;
1311 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1313 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1314 __prev_n->_M_nxt = __this_n;
1315 this->_M_copy_code(*__this_n, *__ht_n);
1316 size_type __bkt = _M_bucket_index(*__this_n);
1317 if (!_M_buckets[__bkt])
1318 _M_buckets[__bkt] = __prev_n;
1319 __prev_n = __this_n;
1326 _M_deallocate_buckets();
1327 __throw_exception_again;
1331 template<
typename _Key,
typename _Value,
typename _Alloc,
1332 typename _ExtractKey,
typename _Equal,
1333 typename _Hash,
typename _RangeHash,
typename _Unused,
1334 typename _RehashPolicy,
typename _Traits>
1336 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1337 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1340 _M_rehash_policy._M_reset();
1341 _M_bucket_count = 1;
1342 _M_single_bucket =
nullptr;
1343 _M_buckets = &_M_single_bucket;
1344 _M_before_begin._M_nxt =
nullptr;
1345 _M_element_count = 0;
1348 template<
typename _Key,
typename _Value,
typename _Alloc,
1349 typename _ExtractKey,
typename _Equal,
1350 typename _Hash,
typename _RangeHash,
typename _Unused,
1351 typename _RehashPolicy,
typename _Traits>
1353 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1354 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1355 _M_move_assign(_Hashtable&& __ht,
true_type)
1360 this->_M_deallocate_nodes(_M_begin());
1361 _M_deallocate_buckets();
1362 __hashtable_base::operator=(
std::move(__ht));
1363 _M_rehash_policy = __ht._M_rehash_policy;
1364 if (!__ht._M_uses_single_bucket())
1365 _M_buckets = __ht._M_buckets;
1368 _M_buckets = &_M_single_bucket;
1369 _M_single_bucket = __ht._M_single_bucket;
1372 _M_bucket_count = __ht._M_bucket_count;
1373 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1374 _M_element_count = __ht._M_element_count;
1375 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1382 template<
typename _Key,
typename _Value,
typename _Alloc,
1383 typename _ExtractKey,
typename _Equal,
1384 typename _Hash,
typename _RangeHash,
typename _Unused,
1385 typename _RehashPolicy,
typename _Traits>
1387 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1388 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1389 _M_move_assign(_Hashtable&& __ht,
false_type)
1391 if (__ht._M_node_allocator() == this->_M_node_allocator())
1401 template<
typename _Key,
typename _Value,
typename _Alloc,
1402 typename _ExtractKey,
typename _Equal,
1403 typename _Hash,
typename _RangeHash,
typename _Unused,
1404 typename _RehashPolicy,
typename _Traits>
1405 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1406 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1407 _Hashtable(
const _Hashtable& __ht)
1408 : __hashtable_base(__ht),
1410 __rehash_base(__ht),
1412 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1413 __enable_default_ctor(__ht),
1414 _M_buckets(nullptr),
1415 _M_bucket_count(__ht._M_bucket_count),
1416 _M_element_count(__ht._M_element_count),
1417 _M_rehash_policy(__ht._M_rehash_policy)
1419 __alloc_node_gen_t __alloc_node_gen(*
this);
1420 _M_assign(__ht, __alloc_node_gen);
1423 template<
typename _Key,
typename _Value,
typename _Alloc,
1424 typename _ExtractKey,
typename _Equal,
1425 typename _Hash,
typename _RangeHash,
typename _Unused,
1426 typename _RehashPolicy,
typename _Traits>
1427 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1428 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1429 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1431 noexcept(_S_nothrow_move())
1432 : __hashtable_base(__ht),
1434 __rehash_base(__ht),
1435 __hashtable_alloc(
std::
move(__a)),
1436 __enable_default_ctor(__ht),
1437 _M_buckets(__ht._M_buckets),
1438 _M_bucket_count(__ht._M_bucket_count),
1439 _M_before_begin(__ht._M_before_begin._M_nxt),
1440 _M_element_count(__ht._M_element_count),
1441 _M_rehash_policy(__ht._M_rehash_policy)
1444 if (__ht._M_uses_single_bucket())
1446 _M_buckets = &_M_single_bucket;
1447 _M_single_bucket = __ht._M_single_bucket;
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(
const _Hashtable& __ht,
const allocator_type& __a)
1463 : __hashtable_base(__ht),
1465 __rehash_base(__ht),
1466 __hashtable_alloc(__node_alloc_type(__a)),
1467 __enable_default_ctor(__ht),
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 __alloc_node_gen_t __alloc_node_gen(*
this);
1474 _M_assign(__ht, __alloc_node_gen);
1477 template<
typename _Key,
typename _Value,
typename _Alloc,
1478 typename _ExtractKey,
typename _Equal,
1479 typename _Hash,
typename _RangeHash,
typename _Unused,
1480 typename _RehashPolicy,
typename _Traits>
1481 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1482 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1483 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1485 : __hashtable_base(__ht),
1487 __rehash_base(__ht),
1488 __hashtable_alloc(
std::
move(__a)),
1489 __enable_default_ctor(__ht),
1490 _M_buckets(nullptr),
1491 _M_bucket_count(__ht._M_bucket_count),
1492 _M_element_count(__ht._M_element_count),
1493 _M_rehash_policy(__ht._M_rehash_policy)
1495 if (__ht._M_node_allocator() == this->_M_node_allocator())
1497 if (__ht._M_uses_single_bucket())
1499 _M_buckets = &_M_single_bucket;
1500 _M_single_bucket = __ht._M_single_bucket;
1503 _M_buckets = __ht._M_buckets;
1507 _M_update_bbegin(__ht._M_begin());
1513 __alloc_node_gen_t __alloc_gen(*
this);
1515 using _Fwd_Ht =
typename
1516 conditional<__move_if_noexcept_cond<value_type>::value,
1517 const _Hashtable&, _Hashtable&&>::type;
1518 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1523 template<
typename _Key,
typename _Value,
typename _Alloc,
1524 typename _ExtractKey,
typename _Equal,
1525 typename _Hash,
typename _RangeHash,
typename _Unused,
1526 typename _RehashPolicy,
typename _Traits>
1527 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1528 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1529 ~_Hashtable() noexcept
1532 _M_deallocate_buckets();
1535 template<
typename _Key,
typename _Value,
typename _Alloc,
1536 typename _ExtractKey,
typename _Equal,
1537 typename _Hash,
typename _RangeHash,
typename _Unused,
1538 typename _RehashPolicy,
typename _Traits>
1540 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1541 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
::
1542 swap(_Hashtable& __x)
1543 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1544 __is_nothrow_swappable<_Equal>>::value)
1551 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1552 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1555 if (this->_M_uses_single_bucket())
1557 if (!__x._M_uses_single_bucket())
1559 _M_buckets = __x._M_buckets;
1560 __x._M_buckets = &__x._M_single_bucket;
1563 else if (__x._M_uses_single_bucket())
1565 __x._M_buckets = _M_buckets;
1566 _M_buckets = &_M_single_bucket;
1571 std::swap(_M_bucket_count, __x._M_bucket_count);
1572 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1573 std::swap(_M_element_count, __x._M_element_count);
1574 std::swap(_M_single_bucket, __x._M_single_bucket);
1579 __x._M_update_bbegin();
1582 template<
typename _Key,
typename _Value,
typename _Alloc,
1583 typename _ExtractKey,
typename _Equal,
1584 typename _Hash,
typename _RangeHash,
typename _Unused,
1585 typename _RehashPolicy,
typename _Traits>
1587 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1588 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1589 find(
const key_type& __k)
1592 __hash_code __code = this->_M_hash_code(__k);
1593 std::size_t __bkt = _M_bucket_index(__code);
1594 return iterator(_M_find_node(__bkt, __k, __code));
1597 template<
typename _Key,
typename _Value,
typename _Alloc,
1598 typename _ExtractKey,
typename _Equal,
1599 typename _Hash,
typename _RangeHash,
typename _Unused,
1600 typename _RehashPolicy,
typename _Traits>
1602 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1603 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1604 find(
const key_type& __k)
const
1607 __hash_code __code = this->_M_hash_code(__k);
1608 std::size_t __bkt = _M_bucket_index(__code);
1609 return const_iterator(_M_find_node(__bkt, __k, __code));
1612 #if __cplusplus > 201703L
1613 template<
typename _Key,
typename _Value,
typename _Alloc,
1614 typename _ExtractKey,
typename _Equal,
1615 typename _Hash,
typename _RangeHash,
typename _Unused,
1616 typename _RehashPolicy,
typename _Traits>
1617 template<
typename _Kt,
typename,
typename>
1619 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1620 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1621 _M_find_tr(
const _Kt& __k)
1624 __hash_code __code = this->_M_hash_code_tr(__k);
1625 std::size_t __bkt = _M_bucket_index(__code);
1626 return iterator(_M_find_node_tr(__bkt, __k, __code));
1629 template<
typename _Key,
typename _Value,
typename _Alloc,
1630 typename _ExtractKey,
typename _Equal,
1631 typename _Hash,
typename _RangeHash,
typename _Unused,
1632 typename _RehashPolicy,
typename _Traits>
1633 template<
typename _Kt,
typename,
typename>
1635 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1636 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1637 _M_find_tr(
const _Kt& __k)
const
1640 __hash_code __code = this->_M_hash_code_tr(__k);
1641 std::size_t __bkt = _M_bucket_index(__code);
1642 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
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>
1651 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1652 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1653 count(
const key_type& __k)
const
1656 auto __it = find(__k);
1660 if (__unique_keys::value)
1666 size_type __result = 1;
1667 for (
auto __ref = __it++;
1668 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1675 #if __cplusplus > 201703L
1676 template<
typename _Key,
typename _Value,
typename _Alloc,
1677 typename _ExtractKey,
typename _Equal,
1678 typename _Hash,
typename _RangeHash,
typename _Unused,
1679 typename _RehashPolicy,
typename _Traits>
1680 template<
typename _Kt,
typename,
typename>
1682 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1683 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1684 _M_count_tr(
const _Kt& __k)
const
1687 __hash_code __code = this->_M_hash_code_tr(__k);
1688 std::size_t __bkt = _M_bucket_index(__code);
1689 auto __n = _M_find_node_tr(__bkt, __k, __code);
1697 size_type __result = 1;
1699 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1707 template<
typename _Key,
typename _Value,
typename _Alloc,
1708 typename _ExtractKey,
typename _Equal,
1709 typename _Hash,
typename _RangeHash,
typename _Unused,
1710 typename _RehashPolicy,
typename _Traits>
1712 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1713 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1714 equal_range(
const key_type& __k)
1715 -> pair<iterator, iterator>
1717 auto __ite = find(__k);
1719 return { __ite, __ite };
1721 auto __beg = __ite++;
1722 if (__unique_keys::value)
1723 return { __beg, __ite };
1728 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1731 return { __beg, __ite };
1734 template<
typename _Key,
typename _Value,
typename _Alloc,
1735 typename _ExtractKey,
typename _Equal,
1736 typename _Hash,
typename _RangeHash,
typename _Unused,
1737 typename _RehashPolicy,
typename _Traits>
1739 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1740 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1741 equal_range(
const key_type& __k)
const
1742 -> pair<const_iterator, const_iterator>
1744 auto __ite = find(__k);
1746 return { __ite, __ite };
1748 auto __beg = __ite++;
1749 if (__unique_keys::value)
1750 return { __beg, __ite };
1755 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1758 return { __beg, __ite };
1761 #if __cplusplus > 201703L
1762 template<
typename _Key,
typename _Value,
typename _Alloc,
1763 typename _ExtractKey,
typename _Equal,
1764 typename _Hash,
typename _RangeHash,
typename _Unused,
1765 typename _RehashPolicy,
typename _Traits>
1766 template<
typename _Kt,
typename,
typename>
1768 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1769 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1770 _M_equal_range_tr(
const _Kt& __k)
1771 -> pair<iterator, iterator>
1773 __hash_code __code = this->_M_hash_code_tr(__k);
1774 std::size_t __bkt = _M_bucket_index(__code);
1775 auto __n = _M_find_node_tr(__bkt, __k, __code);
1776 iterator __ite(__n);
1778 return { __ite, __ite };
1783 auto __beg = __ite++;
1784 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1787 return { __beg, __ite };
1790 template<
typename _Key,
typename _Value,
typename _Alloc,
1791 typename _ExtractKey,
typename _Equal,
1792 typename _Hash,
typename _RangeHash,
typename _Unused,
1793 typename _RehashPolicy,
typename _Traits>
1794 template<
typename _Kt,
typename,
typename>
1796 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1797 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1798 _M_equal_range_tr(
const _Kt& __k)
const
1799 -> pair<const_iterator, const_iterator>
1801 __hash_code __code = this->_M_hash_code_tr(__k);
1802 std::size_t __bkt = _M_bucket_index(__code);
1803 auto __n = _M_find_node_tr(__bkt, __k, __code);
1804 const_iterator __ite(__n);
1806 return { __ite, __ite };
1811 auto __beg = __ite++;
1812 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1815 return { __beg, __ite };
1821 template<
typename _Key,
typename _Value,
typename _Alloc,
1822 typename _ExtractKey,
typename _Equal,
1823 typename _Hash,
typename _RangeHash,
typename _Unused,
1824 typename _RehashPolicy,
typename _Traits>
1826 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1827 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1828 _M_find_before_node(size_type __bkt,
const key_type& __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(__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>
1854 template<
typename _Kt>
1856 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1857 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1858 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1859 __hash_code __code)
const
1862 __node_base_ptr __prev_p = _M_buckets[__bkt];
1866 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1867 __p = __p->_M_next())
1869 if (this->_M_equals_tr(__k, __code, *__p))
1872 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1880 template<
typename _Key,
typename _Value,
typename _Alloc,
1881 typename _ExtractKey,
typename _Equal,
1882 typename _Hash,
typename _RangeHash,
typename _Unused,
1883 typename _RehashPolicy,
typename _Traits>
1885 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1886 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1887 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1889 if (_M_buckets[__bkt])
1893 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1894 _M_buckets[__bkt]->_M_nxt = __node;
1901 __node->_M_nxt = _M_before_begin._M_nxt;
1902 _M_before_begin._M_nxt = __node;
1907 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
1909 _M_buckets[__bkt] = &_M_before_begin;
1913 template<
typename _Key,
typename _Value,
typename _Alloc,
1914 typename _ExtractKey,
typename _Equal,
1915 typename _Hash,
typename _RangeHash,
typename _Unused,
1916 typename _RehashPolicy,
typename _Traits>
1918 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1919 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1920 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
1921 size_type __next_bkt)
1923 if (!__next || __next_bkt != __bkt)
1928 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1931 if (&_M_before_begin == _M_buckets[__bkt])
1932 _M_before_begin._M_nxt = __next;
1933 _M_buckets[__bkt] =
nullptr;
1937 template<
typename _Key,
typename _Value,
typename _Alloc,
1938 typename _ExtractKey,
typename _Equal,
1939 typename _Hash,
typename _RangeHash,
typename _Unused,
1940 typename _RehashPolicy,
typename _Traits>
1942 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1943 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1944 _M_get_previous_node(size_type __bkt, __node_ptr __n)
1947 __node_base_ptr __prev_n = _M_buckets[__bkt];
1948 while (__prev_n->_M_nxt != __n)
1949 __prev_n = __prev_n->_M_nxt;
1953 template<
typename _Key,
typename _Value,
typename _Alloc,
1954 typename _ExtractKey,
typename _Equal,
1955 typename _Hash,
typename _RangeHash,
typename _Unused,
1956 typename _RehashPolicy,
typename _Traits>
1957 template<
typename... _Args>
1959 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1960 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1961 _M_emplace(
true_type , _Args&&... __args)
1962 -> pair<iterator, bool>
1965 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1966 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1967 __hash_code __code = this->_M_hash_code(__k);
1968 size_type __bkt = _M_bucket_index(__code);
1969 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
1971 return std::make_pair(iterator(__p),
false);
1974 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
1975 __node._M_node =
nullptr;
1976 return { __pos,
true };
1979 template<
typename _Key,
typename _Value,
typename _Alloc,
1980 typename _ExtractKey,
typename _Equal,
1981 typename _Hash,
typename _RangeHash,
typename _Unused,
1982 typename _RehashPolicy,
typename _Traits>
1983 template<
typename... _Args>
1985 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1986 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1987 _M_emplace(const_iterator __hint,
false_type ,
1992 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
1993 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
1995 __hash_code __code = this->_M_hash_code(__k);
1997 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
1998 __node._M_node =
nullptr;
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_unique_node(size_type __bkt, __hash_code __code,
2010 __node_ptr __node, size_type __n_elt)
2013 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2015 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2018 if (__do_rehash.
first)
2020 _M_rehash(__do_rehash.
second, __saved_state);
2021 __bkt = _M_bucket_index(__code);
2024 this->_M_store_code(*__node, __code);
2027 _M_insert_bucket_begin(__bkt, __node);
2029 return iterator(__node);
2032 template<
typename _Key,
typename _Value,
typename _Alloc,
2033 typename _ExtractKey,
typename _Equal,
2034 typename _Hash,
typename _RangeHash,
typename _Unused,
2035 typename _RehashPolicy,
typename _Traits>
2037 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2038 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2039 _M_insert_multi_node(__node_ptr __hint,
2040 __hash_code __code, __node_ptr __node)
2043 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2045 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2047 if (__do_rehash.
first)
2048 _M_rehash(__do_rehash.
second, __saved_state);
2050 this->_M_store_code(*__node, __code);
2051 const key_type& __k = _ExtractKey{}(__node->_M_v());
2052 size_type __bkt = _M_bucket_index(__code);
2056 __node_base_ptr __prev
2057 = __builtin_expect(__hint !=
nullptr,
false)
2058 && this->_M_equals(__k, __code, *__hint)
2060 : _M_find_before_node(__bkt, __k, __code);
2065 __node->_M_nxt = __prev->_M_nxt;
2066 __prev->_M_nxt = __node;
2067 if (__builtin_expect(__prev == __hint,
false))
2071 && !this->_M_equals(__k, __code, *__node->_M_next()))
2073 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2074 if (__next_bkt != __bkt)
2075 _M_buckets[__next_bkt] = __node;
2082 _M_insert_bucket_begin(__bkt, __node);
2084 return iterator(__node);
2088 template<
typename _Key,
typename _Value,
typename _Alloc,
2089 typename _ExtractKey,
typename _Equal,
2090 typename _Hash,
typename _RangeHash,
typename _Unused,
2091 typename _RehashPolicy,
typename _Traits>
2092 template<
typename _Arg,
typename _NodeGenerator>
2094 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2095 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2096 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
2098 -> pair<iterator, bool>
2100 const key_type& __k = _ExtractKey{}(__v);
2101 __hash_code __code = this->_M_hash_code(__k);
2102 size_type __bkt = _M_bucket_index(__code);
2104 if (__node_ptr __node = _M_find_node(__bkt, __k, __code))
2105 return { iterator(__node),
false };
2107 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2109 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2110 __node._M_node =
nullptr;
2111 return { __pos,
true };
2115 template<
typename _Key,
typename _Value,
typename _Alloc,
2116 typename _ExtractKey,
typename _Equal,
2117 typename _Hash,
typename _RangeHash,
typename _Unused,
2118 typename _RehashPolicy,
typename _Traits>
2119 template<
typename _Arg,
typename _NodeGenerator>
2121 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2122 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2123 _M_insert(const_iterator __hint, _Arg&& __v,
2124 const _NodeGenerator& __node_gen,
2130 __hash_code __code = this->_M_hash_code(_ExtractKey{}(__v));
2133 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2135 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
2136 __node._M_node =
nullptr;
2140 template<
typename _Key,
typename _Value,
typename _Alloc,
2141 typename _ExtractKey,
typename _Equal,
2142 typename _Hash,
typename _RangeHash,
typename _Unused,
2143 typename _RehashPolicy,
typename _Traits>
2145 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2146 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2147 erase(const_iterator __it)
2150 __node_ptr __n = __it._M_cur;
2151 std::size_t __bkt = _M_bucket_index(*__n);
2156 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2157 return _M_erase(__bkt, __prev_n, __n);
2160 template<
typename _Key,
typename _Value,
typename _Alloc,
2161 typename _ExtractKey,
typename _Equal,
2162 typename _Hash,
typename _RangeHash,
typename _Unused,
2163 typename _RehashPolicy,
typename _Traits>
2165 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2166 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2167 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2170 if (__prev_n == _M_buckets[__bkt])
2171 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2172 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2173 else if (__n->_M_nxt)
2175 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2176 if (__next_bkt != __bkt)
2177 _M_buckets[__next_bkt] = __prev_n;
2180 __prev_n->_M_nxt = __n->_M_nxt;
2181 iterator __result(__n->_M_next());
2182 this->_M_deallocate_node(__n);
2188 template<
typename _Key,
typename _Value,
typename _Alloc,
2189 typename _ExtractKey,
typename _Equal,
2190 typename _Hash,
typename _RangeHash,
typename _Unused,
2191 typename _RehashPolicy,
typename _Traits>
2193 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2194 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2195 _M_erase(
true_type ,
const key_type& __k)
2198 __hash_code __code = this->_M_hash_code(__k);
2199 std::size_t __bkt = _M_bucket_index(__code);
2202 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2207 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2208 _M_erase(__bkt, __prev_n, __n);
2212 template<
typename _Key,
typename _Value,
typename _Alloc,
2213 typename _ExtractKey,
typename _Equal,
2214 typename _Hash,
typename _RangeHash,
typename _Unused,
2215 typename _RehashPolicy,
typename _Traits>
2217 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2218 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2222 __hash_code __code = this->_M_hash_code(__k);
2223 std::size_t __bkt = _M_bucket_index(__code);
2226 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2236 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2237 __node_ptr __n_last = __n->_M_next();
2238 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2239 __n_last = __n_last->_M_next();
2241 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2244 size_type __result = 0;
2247 __node_ptr __p = __n->_M_next();
2248 this->_M_deallocate_node(__n);
2252 while (__n != __n_last);
2254 _M_element_count -= __result;
2255 if (__prev_n == _M_buckets[__bkt])
2256 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2257 else if (__n_last_bkt != __bkt)
2258 _M_buckets[__n_last_bkt] = __prev_n;
2259 __prev_n->_M_nxt = __n_last;
2263 template<
typename _Key,
typename _Value,
typename _Alloc,
2264 typename _ExtractKey,
typename _Equal,
2265 typename _Hash,
typename _RangeHash,
typename _Unused,
2266 typename _RehashPolicy,
typename _Traits>
2268 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2269 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2270 erase(const_iterator __first, const_iterator __last)
2273 __node_ptr __n = __first._M_cur;
2274 __node_ptr __last_n = __last._M_cur;
2275 if (__n == __last_n)
2276 return iterator(__n);
2278 std::size_t __bkt = _M_bucket_index(*__n);
2280 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2281 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2282 std::size_t __n_bkt = __bkt;
2287 __node_ptr __tmp = __n;
2288 __n = __n->_M_next();
2289 this->_M_deallocate_node(__tmp);
2293 __n_bkt = _M_bucket_index(*__n);
2295 while (__n != __last_n && __n_bkt == __bkt);
2296 if (__is_bucket_begin)
2297 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2298 if (__n == __last_n)
2300 __is_bucket_begin =
true;
2304 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2305 _M_buckets[__n_bkt] = __prev_n;
2306 __prev_n->_M_nxt = __n;
2307 return iterator(__n);
2310 template<
typename _Key,
typename _Value,
typename _Alloc,
2311 typename _ExtractKey,
typename _Equal,
2312 typename _Hash,
typename _RangeHash,
typename _Unused,
2313 typename _RehashPolicy,
typename _Traits>
2315 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2316 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2319 this->_M_deallocate_nodes(_M_begin());
2320 __builtin_memset(_M_buckets, 0,
2321 _M_bucket_count *
sizeof(__node_base_ptr));
2322 _M_element_count = 0;
2323 _M_before_begin._M_nxt =
nullptr;
2326 template<
typename _Key,
typename _Value,
typename _Alloc,
2327 typename _ExtractKey,
typename _Equal,
2328 typename _Hash,
typename _RangeHash,
typename _Unused,
2329 typename _RehashPolicy,
typename _Traits>
2331 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2332 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2333 rehash(size_type __bkt_count)
2335 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2337 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2339 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2341 if (__bkt_count != _M_bucket_count)
2342 _M_rehash(__bkt_count, __saved_state);
2346 _M_rehash_policy._M_reset(__saved_state);
2349 template<
typename _Key,
typename _Value,
typename _Alloc,
2350 typename _ExtractKey,
typename _Equal,
2351 typename _Hash,
typename _RangeHash,
typename _Unused,
2352 typename _RehashPolicy,
typename _Traits>
2354 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2355 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2356 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2360 _M_rehash_aux(__bkt_count, __unique_keys{});
2366 _M_rehash_policy._M_reset(__state);
2367 __throw_exception_again;
2372 template<
typename _Key,
typename _Value,
typename _Alloc,
2373 typename _ExtractKey,
typename _Equal,
2374 typename _Hash,
typename _RangeHash,
typename _Unused,
2375 typename _RehashPolicy,
typename _Traits>
2377 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2378 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2379 _M_rehash_aux(size_type __bkt_count,
true_type )
2381 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2382 __node_ptr __p = _M_begin();
2383 _M_before_begin._M_nxt =
nullptr;
2384 std::size_t __bbegin_bkt = 0;
2387 __node_ptr __next = __p->_M_next();
2389 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2390 if (!__new_buckets[__bkt])
2392 __p->_M_nxt = _M_before_begin._M_nxt;
2393 _M_before_begin._M_nxt = __p;
2394 __new_buckets[__bkt] = &_M_before_begin;
2396 __new_buckets[__bbegin_bkt] = __p;
2397 __bbegin_bkt = __bkt;
2401 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2402 __new_buckets[__bkt]->_M_nxt = __p;
2408 _M_deallocate_buckets();
2409 _M_bucket_count = __bkt_count;
2410 _M_buckets = __new_buckets;
2415 template<
typename _Key,
typename _Value,
typename _Alloc,
2416 typename _ExtractKey,
typename _Equal,
2417 typename _Hash,
typename _RangeHash,
typename _Unused,
2418 typename _RehashPolicy,
typename _Traits>
2420 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2421 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2422 _M_rehash_aux(size_type __bkt_count,
false_type )
2424 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2425 __node_ptr __p = _M_begin();
2426 _M_before_begin._M_nxt =
nullptr;
2427 std::size_t __bbegin_bkt = 0;
2428 std::size_t __prev_bkt = 0;
2429 __node_ptr __prev_p =
nullptr;
2430 bool __check_bucket =
false;
2434 __node_ptr __next = __p->_M_next();
2436 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2438 if (__prev_p && __prev_bkt == __bkt)
2443 __p->_M_nxt = __prev_p->_M_nxt;
2444 __prev_p->_M_nxt = __p;
2451 __check_bucket =
true;
2459 if (__prev_p->_M_nxt)
2461 std::size_t __next_bkt
2462 = __hash_code_base::_M_bucket_index(
2463 *__prev_p->_M_next(), __bkt_count);
2464 if (__next_bkt != __prev_bkt)
2465 __new_buckets[__next_bkt] = __prev_p;
2467 __check_bucket =
false;
2470 if (!__new_buckets[__bkt])
2472 __p->_M_nxt = _M_before_begin._M_nxt;
2473 _M_before_begin._M_nxt = __p;
2474 __new_buckets[__bkt] = &_M_before_begin;
2476 __new_buckets[__bbegin_bkt] = __p;
2477 __bbegin_bkt = __bkt;
2481 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2482 __new_buckets[__bkt]->_M_nxt = __p;
2490 if (__check_bucket && __prev_p->_M_nxt)
2492 std::size_t __next_bkt
2493 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2495 if (__next_bkt != __prev_bkt)
2496 __new_buckets[__next_bkt] = __prev_p;
2499 _M_deallocate_buckets();
2500 _M_bucket_count = __bkt_count;
2501 _M_buckets = __new_buckets;
2504 #if __cplusplus > 201402L
2505 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2508 #if __cpp_deduction_guides >= 201606
2510 template<
typename _Hash>
2511 using _RequireNotAllocatorOrIntegral
2512 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2515 _GLIBCXX_END_NAMESPACE_VERSION
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 * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first 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 iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
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
A mixin helper to conditionally enable or disable the default constructor.
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.