33#pragma GCC system_header
37#if __cplusplus > 201402L
43namespace std _GLIBCXX_VISIBILITY(default)
45_GLIBCXX_BEGIN_NAMESPACE_VERSION
48 template<
typename _Tp,
typename _Hash>
51 __is_fast_hash<_Hash>,
53 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
58 template<
typename _Equal,
typename _Hash,
typename _Allocator>
59 using _Hashtable_enable_default_ctor
60 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
61 is_default_constructible<_Hash>,
62 is_default_constructible<_Allocator>>{},
63 __detail::_Hash_node_base>;
178 template<
typename _Key,
typename _Value,
typename _Alloc,
179 typename _ExtractKey,
typename _Equal,
180 typename _Hash,
typename _RangeHash,
typename _Unused,
181 typename _RehashPolicy,
typename _Traits>
183 :
public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
184 _Hash, _RangeHash, _Unused, _Traits>,
185 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
186 _Hash, _RangeHash, _Unused,
187 _RehashPolicy, _Traits>,
188 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
189 _Hash, _RangeHash, _Unused,
190 _RehashPolicy, _Traits>,
191 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
192 _Hash, _RangeHash, _Unused,
193 _RehashPolicy, _Traits>,
194 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
195 _Hash, _RangeHash, _Unused,
196 _RehashPolicy, _Traits>,
197 private __detail::_Hashtable_alloc<
198 __alloc_rebind<_Alloc,
199 __detail::_Hash_node<_Value,
200 _Traits::__hash_cached::value>>>,
201 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
203 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
204 "unordered container must have a non-const, non-volatile value_type");
205#if __cplusplus > 201703L || defined __STRICT_ANSI__
206 static_assert(is_same<typename _Alloc::value_type, _Value>{},
207 "unordered container must have the same value_type as its allocator");
210 using __traits_type = _Traits;
211 using __hash_cached =
typename __traits_type::__hash_cached;
212 using __constant_iterators =
typename __traits_type::__constant_iterators;
213 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
214 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
216 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
218 using __node_value_type =
219 __detail::_Hash_node_value<_Value, __hash_cached::value>;
220 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
221 using __value_alloc_traits =
222 typename __hashtable_alloc::__value_alloc_traits;
223 using __node_alloc_traits =
224 typename __hashtable_alloc::__node_alloc_traits;
225 using __node_base =
typename __hashtable_alloc::__node_base;
226 using __node_base_ptr =
typename __hashtable_alloc::__node_base_ptr;
227 using __buckets_ptr =
typename __hashtable_alloc::__buckets_ptr;
229 using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
232 _RehashPolicy, _Traits>;
233 using __enable_default_ctor
234 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
237 typedef _Key key_type;
238 typedef _Value value_type;
239 typedef _Alloc allocator_type;
240 typedef _Equal key_equal;
244 typedef typename __value_alloc_traits::pointer pointer;
245 typedef typename __value_alloc_traits::const_pointer const_pointer;
246 typedef value_type& reference;
247 typedef const value_type& const_reference;
249 using iterator =
typename __insert_base::iterator;
251 using const_iterator =
typename __insert_base::const_iterator;
253 using local_iterator = __detail::_Local_iterator<key_type, _Value,
254 _ExtractKey, _Hash, _RangeHash, _Unused,
255 __constant_iterators::value,
256 __hash_cached::value>;
258 using const_local_iterator = __detail::_Local_const_iterator<
260 _ExtractKey, _Hash, _RangeHash, _Unused,
261 __constant_iterators::value, __hash_cached::value>;
264 using __rehash_type = _RehashPolicy;
265 using __rehash_state =
typename __rehash_type::_State;
267 using __unique_keys =
typename __traits_type::__unique_keys;
269 using __hashtable_base = __detail::
270 _Hashtable_base<_Key, _Value, _ExtractKey,
271 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
273 using __hash_code_base =
typename __hashtable_base::__hash_code_base;
274 using __hash_code =
typename __hashtable_base::__hash_code;
275 using __ireturn_type =
typename __insert_base::__ireturn_type;
277 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
278 _Equal, _Hash, _RangeHash, _Unused,
279 _RehashPolicy, _Traits>;
281 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
283 _Hash, _RangeHash, _Unused,
284 _RehashPolicy, _Traits>;
286 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
287 _Equal, _Hash, _RangeHash, _Unused,
288 _RehashPolicy, _Traits>;
290 using __reuse_or_alloc_node_gen_t =
291 __detail::_ReuseOrAllocNode<__node_alloc_type>;
292 using __alloc_node_gen_t =
293 __detail::_AllocNode<__node_alloc_type>;
294 using __node_builder_t =
295 __detail::_NodeBuilder<_ExtractKey>;
301 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
302 : _M_h(__h), _M_node(__n) { }
305 template<
typename... _Args>
306 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
308 _M_node(__h->_M_allocate_node(
std::
forward<_Args>(__args)...))
312 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
314 _Scoped_node(
const _Scoped_node&) =
delete;
315 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
317 __hashtable_alloc* _M_h;
321 template<
typename _Ht>
323 __conditional_t<std::is_lvalue_reference<_Ht>::value,
324 const value_type&, value_type&&>
325 __fwd_value_for(value_type& __val)
noexcept
332 struct __hash_code_base_access : __hash_code_base
333 {
using __hash_code_base::_M_bucket_index; };
336 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
337 "Functor used to map hash code to bucket index"
338 " must be nothrow default constructible");
339 static_assert(
noexcept(
341 "Functor used to map hash code to bucket index must be"
345 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
346 "_ExtractKey must be nothrow default constructible");
347 static_assert(
noexcept(
349 "_ExtractKey functor must be noexcept invocable");
351 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
352 typename _ExtractKeya,
typename _Equala,
353 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
354 typename _RehashPolicya,
typename _Traitsa,
356 friend struct __detail::_Map_base;
358 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
359 typename _ExtractKeya,
typename _Equala,
360 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
361 typename _RehashPolicya,
typename _Traitsa>
362 friend struct __detail::_Insert_base;
364 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
365 typename _ExtractKeya,
typename _Equala,
366 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
367 typename _RehashPolicya,
typename _Traitsa,
368 bool _Constant_iteratorsa>
369 friend struct __detail::_Insert;
371 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
372 typename _ExtractKeya,
typename _Equala,
373 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
374 typename _RehashPolicya,
typename _Traitsa,
376 friend struct __detail::_Equality;
379 using size_type =
typename __hashtable_base::size_type;
380 using difference_type =
typename __hashtable_base::difference_type;
382#if __cplusplus > 201402L
383 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
384 using insert_return_type = _Node_insert_return<iterator, node_type>;
388 __buckets_ptr _M_buckets = &_M_single_bucket;
389 size_type _M_bucket_count = 1;
390 __node_base _M_before_begin;
391 size_type _M_element_count = 0;
392 _RehashPolicy _M_rehash_policy;
400 __node_base_ptr _M_single_bucket =
nullptr;
406 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
410 _M_update_bbegin(__node_ptr __n)
412 _M_before_begin._M_nxt = __n;
417 _M_uses_single_bucket(__buckets_ptr __bkts)
const
418 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
421 _M_uses_single_bucket()
const
422 {
return _M_uses_single_bucket(_M_buckets); }
424 static constexpr size_t
425 __small_size_threshold() noexcept
428 __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
432 _M_base_alloc() {
return *
this; }
435 _M_allocate_buckets(size_type __bkt_count)
437 if (__builtin_expect(__bkt_count == 1,
false))
439 _M_single_bucket =
nullptr;
440 return &_M_single_bucket;
443 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
447 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
449 if (_M_uses_single_bucket(__bkts))
452 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
456 _M_deallocate_buckets()
457 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
462 _M_bucket_begin(size_type __bkt)
const;
466 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
470 template<
typename _Ht>
472 _M_assign_elements(_Ht&&);
474 template<
typename _Ht,
typename _NodeGenerator>
476 _M_assign(_Ht&&,
const _NodeGenerator&);
479 _M_move_assign(_Hashtable&&, true_type);
482 _M_move_assign(_Hashtable&&, false_type);
487 _Hashtable(const _Hash& __h, const _Equal& __eq,
488 const allocator_type& __a)
489 : __hashtable_base(__h, __eq),
490 __hashtable_alloc(__node_alloc_type(__a)),
491 __enable_default_ctor(_Enable_default_constructor_tag{})
494 template<
bool _No_realloc = true>
495 static constexpr bool
498#if __cplusplus <= 201402L
499 return __and_<__bool_constant<_No_realloc>,
500 is_nothrow_copy_constructible<_Hash>,
501 is_nothrow_copy_constructible<_Equal>>::value;
503 if constexpr (_No_realloc)
504 if constexpr (is_nothrow_copy_constructible<_Hash>())
505 return is_nothrow_copy_constructible<_Equal>();
510 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
512 noexcept(_S_nothrow_move());
514 _Hashtable(_Hashtable&&, __node_alloc_type&&,
517 template<
typename _InputIterator>
518 _Hashtable(_InputIterator __first, _InputIterator __last,
519 size_type __bkt_count_hint,
520 const _Hash&,
const _Equal&,
const allocator_type&,
523 template<
typename _InputIterator>
524 _Hashtable(_InputIterator __first, _InputIterator __last,
525 size_type __bkt_count_hint,
526 const _Hash&,
const _Equal&,
const allocator_type&,
531 _Hashtable() =
default;
533 _Hashtable(
const _Hashtable&);
535 _Hashtable(
const _Hashtable&,
const allocator_type&);
538 _Hashtable(size_type __bkt_count_hint,
539 const _Hash& __hf = _Hash(),
540 const key_equal& __eql = key_equal(),
541 const allocator_type& __a = allocator_type());
544 _Hashtable(_Hashtable&& __ht)
545 noexcept(_S_nothrow_move())
546 : _Hashtable(
std::move(__ht),
std::move(__ht._M_node_allocator()),
550 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
551 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
552 : _Hashtable(
std::move(__ht), __node_alloc_type(__a),
553 typename __node_alloc_traits::is_always_equal{})
557 _Hashtable(
const allocator_type& __a)
558 : __hashtable_alloc(__node_alloc_type(__a)),
559 __enable_default_ctor(_Enable_default_constructor_tag{})
562 template<
typename _InputIterator>
563 _Hashtable(_InputIterator __f, _InputIterator __l,
564 size_type __bkt_count_hint = 0,
565 const _Hash& __hf = _Hash(),
566 const key_equal& __eql = key_equal(),
567 const allocator_type& __a = allocator_type())
568 : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
572 _Hashtable(initializer_list<value_type> __l,
573 size_type __bkt_count_hint = 0,
574 const _Hash& __hf = _Hash(),
575 const key_equal& __eql = key_equal(),
576 const allocator_type& __a = allocator_type())
577 : _Hashtable(__l.begin(), __l.end(), __bkt_count_hint,
578 __hf, __eql, __a, __unique_keys{})
582 operator=(
const _Hashtable& __ht);
585 operator=(_Hashtable&& __ht)
586 noexcept(__node_alloc_traits::_S_nothrow_move()
587 && is_nothrow_move_assignable<_Hash>::value
588 && is_nothrow_move_assignable<_Equal>::value)
590 constexpr bool __move_storage =
591 __node_alloc_traits::_S_propagate_on_move_assign()
592 || __node_alloc_traits::_S_always_equal();
593 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
598 operator=(initializer_list<value_type> __l)
600 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
601 _M_before_begin._M_nxt =
nullptr;
605 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
608 if (_M_bucket_count < __l_bkt_count)
609 rehash(__l_bkt_count);
611 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
615 ~_Hashtable() noexcept;
619 noexcept(__and_<__is_nothrow_swappable<_Hash>,
620 __is_nothrow_swappable<_Equal>>::value);
625 {
return iterator(_M_begin()); }
628 begin() const noexcept
629 {
return const_iterator(_M_begin()); }
633 {
return iterator(
nullptr); }
637 {
return const_iterator(
nullptr); }
640 cbegin() const noexcept
641 {
return const_iterator(_M_begin()); }
644 cend() const noexcept
645 {
return const_iterator(
nullptr); }
648 size() const noexcept
649 {
return _M_element_count; }
651 _GLIBCXX_NODISCARD
bool
652 empty() const noexcept
653 {
return size() == 0; }
656 get_allocator() const noexcept
657 {
return allocator_type(this->_M_node_allocator()); }
660 max_size() const noexcept
661 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
666 {
return this->_M_eq(); }
672 bucket_count() const noexcept
673 {
return _M_bucket_count; }
676 max_bucket_count() const noexcept
677 {
return max_size(); }
680 bucket_size(size_type __bkt)
const
684 bucket(
const key_type& __k)
const
685 {
return _M_bucket_index(this->_M_hash_code(__k)); }
688 begin(size_type __bkt)
690 return local_iterator(*
this, _M_bucket_begin(__bkt),
691 __bkt, _M_bucket_count);
696 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
699 begin(size_type __bkt)
const
701 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
702 __bkt, _M_bucket_count);
706 end(size_type __bkt)
const
707 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
711 cbegin(size_type __bkt)
const
713 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
714 __bkt, _M_bucket_count);
718 cend(size_type __bkt)
const
719 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
722 load_factor() const noexcept
724 return static_cast<float>(size()) /
static_cast<float>(bucket_count());
733 __rehash_policy()
const
734 {
return _M_rehash_policy; }
737 __rehash_policy(
const _RehashPolicy& __pol)
738 { _M_rehash_policy = __pol; }
742 find(
const key_type& __k);
745 find(
const key_type& __k)
const;
748 count(
const key_type& __k)
const;
751 equal_range(
const key_type& __k);
754 equal_range(
const key_type& __k)
const;
756#if __cplusplus >= 202002L
757#define __cpp_lib_generic_unordered_lookup 201811L
759 template<
typename _Kt,
760 typename = __has_is_transparent_t<_Hash, _Kt>,
761 typename = __has_is_transparent_t<_Equal, _Kt>>
763 _M_find_tr(
const _Kt& __k);
765 template<
typename _Kt,
766 typename = __has_is_transparent_t<_Hash, _Kt>,
767 typename = __has_is_transparent_t<_Equal, _Kt>>
769 _M_find_tr(
const _Kt& __k)
const;
771 template<
typename _Kt,
772 typename = __has_is_transparent_t<_Hash, _Kt>,
773 typename = __has_is_transparent_t<_Equal, _Kt>>
775 _M_count_tr(
const _Kt& __k)
const;
777 template<
typename _Kt,
778 typename = __has_is_transparent_t<_Hash, _Kt>,
779 typename = __has_is_transparent_t<_Equal, _Kt>>
780 pair<iterator, iterator>
781 _M_equal_range_tr(
const _Kt& __k);
783 template<
typename _Kt,
784 typename = __has_is_transparent_t<_Hash, _Kt>,
785 typename = __has_is_transparent_t<_Equal, _Kt>>
786 pair<const_iterator, const_iterator>
787 _M_equal_range_tr(
const _Kt& __k)
const;
793 _M_bucket_index(
const __node_value_type& __n)
const noexcept
794 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
797 _M_bucket_index(__hash_code __c)
const
798 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
801 _M_find_before_node(
const key_type&);
806 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
808 template<
typename _Kt>
810 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
813 _M_find_node(size_type __bkt,
const key_type& __key,
814 __hash_code __c)
const
816 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
818 return static_cast<__node_ptr
>(__before_n->_M_nxt);
822 template<
typename _Kt>
824 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
825 __hash_code __c)
const
827 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
829 return static_cast<__node_ptr
>(__before_n->_M_nxt);
835 _M_insert_bucket_begin(size_type, __node_ptr);
839 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
840 size_type __next_bkt);
844 _M_get_previous_node(size_type __bkt, __node_ptr __n);
846 pair<const_iterator, __hash_code>
847 _M_compute_hash_code(const_iterator __hint,
const key_type& __k)
const;
853 _M_insert_unique_node(size_type __bkt, __hash_code,
854 __node_ptr __n, size_type __n_elt = 1);
859 _M_insert_multi_node(__node_ptr __hint,
860 __hash_code __code, __node_ptr __n);
862 template<
typename... _Args>
864 _M_emplace(true_type __uks, _Args&&... __args);
866 template<
typename... _Args>
868 _M_emplace(false_type __uks, _Args&&... __args)
872 template<
typename... _Args>
874 _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
877 template<
typename... _Args>
879 _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
881 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
883 _M_insert_unique(_Kt&&, _Arg&&,
const _NodeGenerator&);
885 template<
typename _Kt>
886 static __conditional_t<
887 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
888 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
890 _S_forward_key(_Kt&& __k)
893 static const key_type&
894 _S_forward_key(
const key_type& __k)
898 _S_forward_key(key_type&& __k)
901 template<
typename _Arg,
typename _NodeGenerator>
903 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
906 return _M_insert_unique(
911 template<
typename _Arg,
typename _NodeGenerator>
913 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
921 template<
typename _Arg,
typename _NodeGenerator>
923 _M_insert(const_iterator, _Arg&& __arg,
924 const _NodeGenerator& __node_gen, true_type __uks)
931 template<
typename _Arg,
typename _NodeGenerator>
933 _M_insert(const_iterator, _Arg&&,
934 const _NodeGenerator&, false_type __uks);
937 _M_erase(true_type __uks,
const key_type&);
940 _M_erase(false_type __uks,
const key_type&);
943 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
947 template<
typename... _Args>
949 emplace(_Args&&... __args)
952 template<
typename... _Args>
954 emplace_hint(const_iterator __hint, _Args&&... __args)
956 return _M_emplace(__hint, __unique_keys{},
964 erase(const_iterator);
969 {
return erase(const_iterator(__it)); }
972 erase(
const key_type& __k)
973 {
return _M_erase(__unique_keys{}, __k); }
976 erase(const_iterator, const_iterator);
983 void rehash(size_type __bkt_count);
988#if __cplusplus > 201404L
991 _M_reinsert_node(node_type&& __nh)
993 insert_return_type __ret;
995 __ret.position = end();
998 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1000 const key_type& __k = __nh._M_key();
1001 __hash_code __code = this->_M_hash_code(__k);
1002 size_type __bkt = _M_bucket_index(__code);
1003 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
1006 __ret.position = iterator(__n);
1007 __ret.inserted =
false;
1012 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1014 __ret.inserted =
true;
1022 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1027 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1029 const key_type& __k = __nh._M_key();
1030 auto __code = this->_M_hash_code(__k);
1032 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1039 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1041 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1042 if (__prev_n == _M_buckets[__bkt])
1043 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1044 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1045 else if (__n->_M_nxt)
1047 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1048 if (__next_bkt != __bkt)
1049 _M_buckets[__next_bkt] = __prev_n;
1052 __prev_n->_M_nxt = __n->_M_nxt;
1053 __n->_M_nxt =
nullptr;
1055 return { __n, this->_M_node_allocator() };
1060 template<
typename _H2>
1062 _M_src_hash_code(
const _H2&,
const key_type& __k,
1063 const __node_value_type& __src_n)
const
1067 return this->_M_hash_code(__src_n);
1069 return this->_M_hash_code(__k);
1075 extract(const_iterator __pos)
1077 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1078 return _M_extract_node(__bkt,
1079 _M_get_previous_node(__bkt, __pos._M_cur));
1084 extract(
const _Key& __k)
1087 __hash_code __code = this->_M_hash_code(__k);
1088 std::size_t __bkt = _M_bucket_index(__code);
1089 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1090 __nh = _M_extract_node(__bkt, __prev_node);
1095 template<
typename _Compatible_Hashtable>
1097 _M_merge_unique(_Compatible_Hashtable& __src)
1099 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1100 node_type>,
"Node types are compatible");
1101 __glibcxx_assert(get_allocator() == __src.get_allocator());
1103 auto __n_elt = __src.size();
1104 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1107 const key_type& __k = _ExtractKey{}(*__pos);
1109 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1110 size_type __bkt = _M_bucket_index(__code);
1111 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1113 auto __nh = __src.extract(__pos);
1114 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1118 else if (__n_elt != 1)
1124 template<
typename _Compatible_Hashtable>
1126 _M_merge_multi(_Compatible_Hashtable& __src)
1128 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1129 node_type>,
"Node types are compatible");
1130 __glibcxx_assert(get_allocator() == __src.get_allocator());
1132 __node_ptr __hint =
nullptr;
1133 this->reserve(size() + __src.size());
1134 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1137 const key_type& __k = _ExtractKey{}(*__pos);
1139 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1140 auto __nh = __src.extract(__pos);
1141 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1149 void _M_rehash_aux(size_type __bkt_count, true_type __uks);
1152 void _M_rehash_aux(size_type __bkt_count, false_type __uks);
1156 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1160 template<
typename _Key,
typename _Value,
typename _Alloc,
1161 typename _ExtractKey,
typename _Equal,
1162 typename _Hash,
typename _RangeHash,
typename _Unused,
1163 typename _RehashPolicy,
typename _Traits>
1165 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1166 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1167 _M_bucket_begin(size_type __bkt)
const
1170 __node_base_ptr __n = _M_buckets[__bkt];
1171 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) : nullptr;
1174 template<
typename _Key,
typename _Value,
typename _Alloc,
1175 typename _ExtractKey,
typename _Equal,
1176 typename _Hash,
typename _RangeHash,
typename _Unused,
1177 typename _RehashPolicy,
typename _Traits>
1178 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1179 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1180 _Hashtable(size_type __bkt_count_hint,
1181 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1182 : _Hashtable(__h, __eq, __a)
1184 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1185 if (__bkt_count > _M_bucket_count)
1187 _M_buckets = _M_allocate_buckets(__bkt_count);
1188 _M_bucket_count = __bkt_count;
1192 template<
typename _Key,
typename _Value,
typename _Alloc,
1193 typename _ExtractKey,
typename _Equal,
1194 typename _Hash,
typename _RangeHash,
typename _Unused,
1195 typename _RehashPolicy,
typename _Traits>
1196 template<
typename _InputIterator>
1197 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1198 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1199 _Hashtable(_InputIterator __f, _InputIterator __l,
1200 size_type __bkt_count_hint,
1201 const _Hash& __h,
const _Equal& __eq,
1202 const allocator_type& __a, true_type )
1203 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1205 for (; __f != __l; ++__f)
1209 template<
typename _Key,
typename _Value,
typename _Alloc,
1210 typename _ExtractKey,
typename _Equal,
1211 typename _Hash,
typename _RangeHash,
typename _Unused,
1212 typename _RehashPolicy,
typename _Traits>
1213 template<
typename _InputIterator>
1214 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1215 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1216 _Hashtable(_InputIterator __f, _InputIterator __l,
1217 size_type __bkt_count_hint,
1218 const _Hash& __h,
const _Equal& __eq,
1219 const allocator_type& __a, false_type )
1220 : _Hashtable(__h, __eq, __a)
1222 auto __nb_elems = __detail::__distance_fw(__f, __l);
1224 _M_rehash_policy._M_next_bkt(
1225 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1228 if (__bkt_count > _M_bucket_count)
1230 _M_buckets = _M_allocate_buckets(__bkt_count);
1231 _M_bucket_count = __bkt_count;
1234 for (; __f != __l; ++__f)
1238 template<
typename _Key,
typename _Value,
typename _Alloc,
1239 typename _ExtractKey,
typename _Equal,
1240 typename _Hash,
typename _RangeHash,
typename _Unused,
1241 typename _RehashPolicy,
typename _Traits>
1243 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1244 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1245 operator=(
const _Hashtable& __ht)
1251 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1253 auto& __this_alloc = this->_M_node_allocator();
1254 auto& __that_alloc = __ht._M_node_allocator();
1255 if (!__node_alloc_traits::_S_always_equal()
1256 && __this_alloc != __that_alloc)
1259 this->_M_deallocate_nodes(_M_begin());
1260 _M_before_begin._M_nxt =
nullptr;
1261 _M_deallocate_buckets();
1262 _M_buckets =
nullptr;
1264 __hashtable_base::operator=(__ht);
1265 _M_bucket_count = __ht._M_bucket_count;
1266 _M_element_count = __ht._M_element_count;
1267 _M_rehash_policy = __ht._M_rehash_policy;
1268 __alloc_node_gen_t __alloc_node_gen(*
this);
1271 _M_assign(__ht, __alloc_node_gen);
1278 __throw_exception_again;
1286 _M_assign_elements(__ht);
1290 template<
typename _Key,
typename _Value,
typename _Alloc,
1291 typename _ExtractKey,
typename _Equal,
1292 typename _Hash,
typename _RangeHash,
typename _Unused,
1293 typename _RehashPolicy,
typename _Traits>
1294 template<
typename _Ht>
1296 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1297 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1298 _M_assign_elements(_Ht&& __ht)
1300 __buckets_ptr __former_buckets =
nullptr;
1301 std::size_t __former_bucket_count = _M_bucket_count;
1302 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1304 if (_M_bucket_count != __ht._M_bucket_count)
1306 __former_buckets = _M_buckets;
1307 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1308 _M_bucket_count = __ht._M_bucket_count;
1311 __builtin_memset(_M_buckets, 0,
1312 _M_bucket_count *
sizeof(__node_base_ptr));
1317 _M_element_count = __ht._M_element_count;
1318 _M_rehash_policy = __ht._M_rehash_policy;
1319 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1320 _M_before_begin._M_nxt =
nullptr;
1322 if (__former_buckets)
1323 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1327 if (__former_buckets)
1330 _M_deallocate_buckets();
1331 _M_rehash_policy._M_reset(__former_state);
1332 _M_buckets = __former_buckets;
1333 _M_bucket_count = __former_bucket_count;
1335 __builtin_memset(_M_buckets, 0,
1336 _M_bucket_count *
sizeof(__node_base_ptr));
1337 __throw_exception_again;
1341 template<
typename _Key,
typename _Value,
typename _Alloc,
1342 typename _ExtractKey,
typename _Equal,
1343 typename _Hash,
typename _RangeHash,
typename _Unused,
1344 typename _RehashPolicy,
typename _Traits>
1345 template<
typename _Ht,
typename _NodeGenerator>
1347 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1348 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1349 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1351 __buckets_ptr __buckets =
nullptr;
1353 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1357 if (!__ht._M_before_begin._M_nxt)
1362 __node_ptr __ht_n = __ht._M_begin();
1364 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1365 this->_M_copy_code(*__this_n, *__ht_n);
1366 _M_update_bbegin(__this_n);
1369 __node_ptr __prev_n = __this_n;
1370 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1372 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1373 __prev_n->_M_nxt = __this_n;
1374 this->_M_copy_code(*__this_n, *__ht_n);
1375 size_type __bkt = _M_bucket_index(*__this_n);
1376 if (!_M_buckets[__bkt])
1377 _M_buckets[__bkt] = __prev_n;
1378 __prev_n = __this_n;
1385 _M_deallocate_buckets();
1386 __throw_exception_again;
1390 template<
typename _Key,
typename _Value,
typename _Alloc,
1391 typename _ExtractKey,
typename _Equal,
1392 typename _Hash,
typename _RangeHash,
typename _Unused,
1393 typename _RehashPolicy,
typename _Traits>
1395 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1396 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1399 _M_rehash_policy._M_reset();
1400 _M_bucket_count = 1;
1401 _M_single_bucket =
nullptr;
1402 _M_buckets = &_M_single_bucket;
1403 _M_before_begin._M_nxt =
nullptr;
1404 _M_element_count = 0;
1407 template<
typename _Key,
typename _Value,
typename _Alloc,
1408 typename _ExtractKey,
typename _Equal,
1409 typename _Hash,
typename _RangeHash,
typename _Unused,
1410 typename _RehashPolicy,
typename _Traits>
1412 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1413 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1414 _M_move_assign(_Hashtable&& __ht, true_type)
1419 this->_M_deallocate_nodes(_M_begin());
1420 _M_deallocate_buckets();
1421 __hashtable_base::operator=(
std::move(__ht));
1422 _M_rehash_policy = __ht._M_rehash_policy;
1423 if (!__ht._M_uses_single_bucket())
1424 _M_buckets = __ht._M_buckets;
1427 _M_buckets = &_M_single_bucket;
1428 _M_single_bucket = __ht._M_single_bucket;
1431 _M_bucket_count = __ht._M_bucket_count;
1432 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1433 _M_element_count = __ht._M_element_count;
1441 template<
typename _Key,
typename _Value,
typename _Alloc,
1442 typename _ExtractKey,
typename _Equal,
1443 typename _Hash,
typename _RangeHash,
typename _Unused,
1444 typename _RehashPolicy,
typename _Traits>
1446 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1447 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1448 _M_move_assign(_Hashtable&& __ht, false_type)
1450 if (__ht._M_node_allocator() == this->_M_node_allocator())
1451 _M_move_assign(
std::move(__ht), true_type{});
1460 template<
typename _Key,
typename _Value,
typename _Alloc,
1461 typename _ExtractKey,
typename _Equal,
1462 typename _Hash,
typename _RangeHash,
typename _Unused,
1463 typename _RehashPolicy,
typename _Traits>
1464 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1465 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1466 _Hashtable(
const _Hashtable& __ht)
1467 : __hashtable_base(__ht),
1469 __rehash_base(__ht),
1471 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1472 __enable_default_ctor(__ht),
1473 _M_buckets(nullptr),
1474 _M_bucket_count(__ht._M_bucket_count),
1475 _M_element_count(__ht._M_element_count),
1476 _M_rehash_policy(__ht._M_rehash_policy)
1478 __alloc_node_gen_t __alloc_node_gen(*
this);
1479 _M_assign(__ht, __alloc_node_gen);
1482 template<
typename _Key,
typename _Value,
typename _Alloc,
1483 typename _ExtractKey,
typename _Equal,
1484 typename _Hash,
typename _RangeHash,
typename _Unused,
1485 typename _RehashPolicy,
typename _Traits>
1486 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1487 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1488 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1490 noexcept(_S_nothrow_move())
1491 : __hashtable_base(__ht),
1493 __rehash_base(__ht),
1494 __hashtable_alloc(
std::move(__a)),
1495 __enable_default_ctor(__ht),
1496 _M_buckets(__ht._M_buckets),
1497 _M_bucket_count(__ht._M_bucket_count),
1498 _M_before_begin(__ht._M_before_begin._M_nxt),
1499 _M_element_count(__ht._M_element_count),
1500 _M_rehash_policy(__ht._M_rehash_policy)
1503 if (__ht._M_uses_single_bucket())
1505 _M_buckets = &_M_single_bucket;
1506 _M_single_bucket = __ht._M_single_bucket;
1515 template<
typename _Key,
typename _Value,
typename _Alloc,
1516 typename _ExtractKey,
typename _Equal,
1517 typename _Hash,
typename _RangeHash,
typename _Unused,
1518 typename _RehashPolicy,
typename _Traits>
1519 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1520 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1521 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1522 : __hashtable_base(__ht),
1524 __rehash_base(__ht),
1525 __hashtable_alloc(__node_alloc_type(__a)),
1526 __enable_default_ctor(__ht),
1528 _M_bucket_count(__ht._M_bucket_count),
1529 _M_element_count(__ht._M_element_count),
1530 _M_rehash_policy(__ht._M_rehash_policy)
1532 __alloc_node_gen_t __alloc_node_gen(*
this);
1533 _M_assign(__ht, __alloc_node_gen);
1536 template<
typename _Key,
typename _Value,
typename _Alloc,
1537 typename _ExtractKey,
typename _Equal,
1538 typename _Hash,
typename _RangeHash,
typename _Unused,
1539 typename _RehashPolicy,
typename _Traits>
1540 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1541 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1542 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1544 : __hashtable_base(__ht),
1546 __rehash_base(__ht),
1547 __hashtable_alloc(
std::move(__a)),
1548 __enable_default_ctor(__ht),
1549 _M_buckets(nullptr),
1550 _M_bucket_count(__ht._M_bucket_count),
1551 _M_element_count(__ht._M_element_count),
1552 _M_rehash_policy(__ht._M_rehash_policy)
1554 if (__ht._M_node_allocator() == this->_M_node_allocator())
1556 if (__ht._M_uses_single_bucket())
1558 _M_buckets = &_M_single_bucket;
1559 _M_single_bucket = __ht._M_single_bucket;
1562 _M_buckets = __ht._M_buckets;
1566 _M_update_bbegin(__ht._M_begin());
1572 __alloc_node_gen_t __alloc_gen(*
this);
1574 using _Fwd_Ht = __conditional_t<
1575 __move_if_noexcept_cond<value_type>::value,
1576 const _Hashtable&, _Hashtable&&>;
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>
1586 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1587 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1588 ~_Hashtable() noexcept
1593 static_assert(
noexcept(declval<const __hash_code_base_access&>()
1594 ._M_bucket_index(declval<const __node_value_type&>(),
1596 "Cache the hash code or qualify your functors involved"
1597 " in hash code and bucket index computation with noexcept");
1600 _M_deallocate_buckets();
1603 template<
typename _Key,
typename _Value,
typename _Alloc,
1604 typename _ExtractKey,
typename _Equal,
1605 typename _Hash,
typename _RangeHash,
typename _Unused,
1606 typename _RehashPolicy,
typename _Traits>
1608 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1609 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1610 swap(_Hashtable& __x)
1611 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1612 __is_nothrow_swappable<_Equal>>::value)
1620 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1623 if (this->_M_uses_single_bucket())
1625 if (!__x._M_uses_single_bucket())
1627 _M_buckets = __x._M_buckets;
1628 __x._M_buckets = &__x._M_single_bucket;
1631 else if (__x._M_uses_single_bucket())
1633 __x._M_buckets = _M_buckets;
1634 _M_buckets = &_M_single_bucket;
1639 std::swap(_M_bucket_count, __x._M_bucket_count);
1640 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1641 std::swap(_M_element_count, __x._M_element_count);
1642 std::swap(_M_single_bucket, __x._M_single_bucket);
1647 __x._M_update_bbegin();
1650 template<
typename _Key,
typename _Value,
typename _Alloc,
1651 typename _ExtractKey,
typename _Equal,
1652 typename _Hash,
typename _RangeHash,
typename _Unused,
1653 typename _RehashPolicy,
typename _Traits>
1655 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1656 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1657 find(
const key_type& __k)
1660 if (size() <= __small_size_threshold())
1662 for (
auto __it = begin(); __it != end(); ++__it)
1663 if (this->_M_key_equals(__k, *__it._M_cur))
1668 __hash_code __code = this->_M_hash_code(__k);
1669 std::size_t __bkt = _M_bucket_index(__code);
1670 return iterator(_M_find_node(__bkt, __k, __code));
1673 template<
typename _Key,
typename _Value,
typename _Alloc,
1674 typename _ExtractKey,
typename _Equal,
1675 typename _Hash,
typename _RangeHash,
typename _Unused,
1676 typename _RehashPolicy,
typename _Traits>
1678 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1679 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1680 find(
const key_type& __k)
const
1683 if (size() <= __small_size_threshold())
1685 for (
auto __it = begin(); __it != end(); ++__it)
1686 if (this->_M_key_equals(__k, *__it._M_cur))
1691 __hash_code __code = this->_M_hash_code(__k);
1692 std::size_t __bkt = _M_bucket_index(__code);
1693 return const_iterator(_M_find_node(__bkt, __k, __code));
1696#if __cplusplus > 201703L
1697 template<
typename _Key,
typename _Value,
typename _Alloc,
1698 typename _ExtractKey,
typename _Equal,
1699 typename _Hash,
typename _RangeHash,
typename _Unused,
1700 typename _RehashPolicy,
typename _Traits>
1701 template<
typename _Kt,
typename,
typename>
1703 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1704 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1705 _M_find_tr(
const _Kt& __k)
1708 __hash_code __code = this->_M_hash_code_tr(__k);
1709 std::size_t __bkt = _M_bucket_index(__code);
1710 return iterator(_M_find_node_tr(__bkt, __k, __code));
1713 template<
typename _Key,
typename _Value,
typename _Alloc,
1714 typename _ExtractKey,
typename _Equal,
1715 typename _Hash,
typename _RangeHash,
typename _Unused,
1716 typename _RehashPolicy,
typename _Traits>
1717 template<
typename _Kt,
typename,
typename>
1719 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1720 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1721 _M_find_tr(
const _Kt& __k)
const
1724 __hash_code __code = this->_M_hash_code_tr(__k);
1725 std::size_t __bkt = _M_bucket_index(__code);
1726 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1730 template<
typename _Key,
typename _Value,
typename _Alloc,
1731 typename _ExtractKey,
typename _Equal,
1732 typename _Hash,
typename _RangeHash,
typename _Unused,
1733 typename _RehashPolicy,
typename _Traits>
1735 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1736 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1737 count(
const key_type& __k)
const
1740 auto __it = find(__k);
1744 if (__unique_keys::value)
1750 size_type __result = 1;
1751 for (
auto __ref = __it++;
1752 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1759#if __cplusplus > 201703L
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_count_tr(
const _Kt& __k)
const
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);
1781 size_type __result = 1;
1783 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
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 equal_range(
const key_type& __k)
1799 -> pair<iterator, iterator>
1801 auto __ite = find(__k);
1803 return { __ite, __ite };
1805 auto __beg = __ite++;
1806 if (__unique_keys::value)
1807 return { __beg, __ite };
1812 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1815 return { __beg, __ite };
1818 template<
typename _Key,
typename _Value,
typename _Alloc,
1819 typename _ExtractKey,
typename _Equal,
1820 typename _Hash,
typename _RangeHash,
typename _Unused,
1821 typename _RehashPolicy,
typename _Traits>
1823 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1824 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1825 equal_range(
const key_type& __k)
const
1826 -> pair<const_iterator, const_iterator>
1828 auto __ite = find(__k);
1830 return { __ite, __ite };
1832 auto __beg = __ite++;
1833 if (__unique_keys::value)
1834 return { __beg, __ite };
1839 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1842 return { __beg, __ite };
1845#if __cplusplus > 201703L
1846 template<
typename _Key,
typename _Value,
typename _Alloc,
1847 typename _ExtractKey,
typename _Equal,
1848 typename _Hash,
typename _RangeHash,
typename _Unused,
1849 typename _RehashPolicy,
typename _Traits>
1850 template<
typename _Kt,
typename,
typename>
1852 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1853 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1854 _M_equal_range_tr(
const _Kt& __k)
1855 -> pair<iterator, iterator>
1857 __hash_code __code = this->_M_hash_code_tr(__k);
1858 std::size_t __bkt = _M_bucket_index(__code);
1859 auto __n = _M_find_node_tr(__bkt, __k, __code);
1860 iterator __ite(__n);
1862 return { __ite, __ite };
1867 auto __beg = __ite++;
1868 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1871 return { __beg, __ite };
1874 template<
typename _Key,
typename _Value,
typename _Alloc,
1875 typename _ExtractKey,
typename _Equal,
1876 typename _Hash,
typename _RangeHash,
typename _Unused,
1877 typename _RehashPolicy,
typename _Traits>
1878 template<
typename _Kt,
typename,
typename>
1880 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1881 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1882 _M_equal_range_tr(
const _Kt& __k)
const
1883 -> pair<const_iterator, const_iterator>
1885 __hash_code __code = this->_M_hash_code_tr(__k);
1886 std::size_t __bkt = _M_bucket_index(__code);
1887 auto __n = _M_find_node_tr(__bkt, __k, __code);
1888 const_iterator __ite(__n);
1890 return { __ite, __ite };
1895 auto __beg = __ite++;
1896 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1899 return { __beg, __ite };
1905 template<
typename _Key,
typename _Value,
typename _Alloc,
1906 typename _ExtractKey,
typename _Equal,
1907 typename _Hash,
typename _RangeHash,
typename _Unused,
1908 typename _RehashPolicy,
typename _Traits>
1910 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1911 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1912 _M_find_before_node(
const key_type& __k)
1915 __node_base_ptr __prev_p = &_M_before_begin;
1916 if (!__prev_p->_M_nxt)
1919 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);
1921 __p = __p->_M_next())
1923 if (this->_M_key_equals(__k, *__p))
1934 template<
typename _Key,
typename _Value,
typename _Alloc,
1935 typename _ExtractKey,
typename _Equal,
1936 typename _Hash,
typename _RangeHash,
typename _Unused,
1937 typename _RehashPolicy,
typename _Traits>
1939 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1940 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1941 _M_find_before_node(size_type __bkt,
const key_type& __k,
1942 __hash_code __code)
const
1945 __node_base_ptr __prev_p = _M_buckets[__bkt];
1949 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1950 __p = __p->_M_next())
1952 if (this->_M_equals(__k, __code, *__p))
1955 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1963 template<
typename _Key,
typename _Value,
typename _Alloc,
1964 typename _ExtractKey,
typename _Equal,
1965 typename _Hash,
typename _RangeHash,
typename _Unused,
1966 typename _RehashPolicy,
typename _Traits>
1967 template<
typename _Kt>
1969 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1970 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1971 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1972 __hash_code __code)
const
1975 __node_base_ptr __prev_p = _M_buckets[__bkt];
1979 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1980 __p = __p->_M_next())
1982 if (this->_M_equals_tr(__k, __code, *__p))
1985 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1993 template<
typename _Key,
typename _Value,
typename _Alloc,
1994 typename _ExtractKey,
typename _Equal,
1995 typename _Hash,
typename _RangeHash,
typename _Unused,
1996 typename _RehashPolicy,
typename _Traits>
1998 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1999 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2000 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
2002 if (_M_buckets[__bkt])
2006 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
2007 _M_buckets[__bkt]->_M_nxt = __node;
2014 __node->_M_nxt = _M_before_begin._M_nxt;
2015 _M_before_begin._M_nxt = __node;
2020 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
2022 _M_buckets[__bkt] = &_M_before_begin;
2026 template<
typename _Key,
typename _Value,
typename _Alloc,
2027 typename _ExtractKey,
typename _Equal,
2028 typename _Hash,
typename _RangeHash,
typename _Unused,
2029 typename _RehashPolicy,
typename _Traits>
2031 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2032 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2033 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
2034 size_type __next_bkt)
2036 if (!__next || __next_bkt != __bkt)
2041 _M_buckets[__next_bkt] = _M_buckets[__bkt];
2044 if (&_M_before_begin == _M_buckets[__bkt])
2045 _M_before_begin._M_nxt = __next;
2046 _M_buckets[__bkt] =
nullptr;
2050 template<
typename _Key,
typename _Value,
typename _Alloc,
2051 typename _ExtractKey,
typename _Equal,
2052 typename _Hash,
typename _RangeHash,
typename _Unused,
2053 typename _RehashPolicy,
typename _Traits>
2055 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2056 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2057 _M_get_previous_node(size_type __bkt, __node_ptr __n)
2060 __node_base_ptr __prev_n = _M_buckets[__bkt];
2061 while (__prev_n->_M_nxt != __n)
2062 __prev_n = __prev_n->_M_nxt;
2066 template<
typename _Key,
typename _Value,
typename _Alloc,
2067 typename _ExtractKey,
typename _Equal,
2068 typename _Hash,
typename _RangeHash,
typename _Unused,
2069 typename _RehashPolicy,
typename _Traits>
2070 template<
typename... _Args>
2072 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2073 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2074 _M_emplace(true_type , _Args&&... __args)
2075 -> pair<iterator, bool>
2079 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2080 if (size() <= __small_size_threshold())
2082 for (
auto __it = begin(); __it != end(); ++__it)
2083 if (this->_M_key_equals(__k, *__it._M_cur))
2085 return { __it,
false };
2088 __hash_code __code = this->_M_hash_code(__k);
2089 size_type __bkt = _M_bucket_index(__code);
2090 if (size() > __small_size_threshold())
2091 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2093 return { iterator(__p),
false };
2096 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2097 __node._M_node =
nullptr;
2098 return { __pos,
true };
2101 template<
typename _Key,
typename _Value,
typename _Alloc,
2102 typename _ExtractKey,
typename _Equal,
2103 typename _Hash,
typename _RangeHash,
typename _Unused,
2104 typename _RehashPolicy,
typename _Traits>
2105 template<
typename... _Args>
2107 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2108 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2109 _M_emplace(const_iterator __hint, false_type ,
2115 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2117 auto __res = this->_M_compute_hash_code(__hint, __k);
2119 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2121 __node._M_node =
nullptr;
2125 template<
typename _Key,
typename _Value,
typename _Alloc,
2126 typename _ExtractKey,
typename _Equal,
2127 typename _Hash,
typename _RangeHash,
typename _Unused,
2128 typename _RehashPolicy,
typename _Traits>
2130 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2131 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2132 _M_compute_hash_code(const_iterator __hint,
const key_type& __k)
const
2133 -> pair<const_iterator, __hash_code>
2135 if (size() <= __small_size_threshold())
2137 if (__hint != cend())
2139 for (
auto __it = __hint; __it != cend(); ++__it)
2140 if (this->_M_key_equals(__k, *__it._M_cur))
2141 return { __it, this->_M_hash_code(*__it._M_cur) };
2144 for (
auto __it = cbegin(); __it != __hint; ++__it)
2145 if (this->_M_key_equals(__k, *__it._M_cur))
2146 return { __it, this->_M_hash_code(*__it._M_cur) };
2149 return { __hint, this->_M_hash_code(__k) };
2152 template<
typename _Key,
typename _Value,
typename _Alloc,
2153 typename _ExtractKey,
typename _Equal,
2154 typename _Hash,
typename _RangeHash,
typename _Unused,
2155 typename _RehashPolicy,
typename _Traits>
2157 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2158 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2159 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2160 __node_ptr __node, size_type __n_elt)
2163 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2165 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2168 if (__do_rehash.first)
2170 _M_rehash(__do_rehash.second, __saved_state);
2171 __bkt = _M_bucket_index(__code);
2174 this->_M_store_code(*__node, __code);
2177 _M_insert_bucket_begin(__bkt, __node);
2179 return iterator(__node);
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>::
2189 _M_insert_multi_node(__node_ptr __hint,
2190 __hash_code __code, __node_ptr __node)
2193 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2195 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2197 if (__do_rehash.first)
2198 _M_rehash(__do_rehash.second, __saved_state);
2200 this->_M_store_code(*__node, __code);
2201 const key_type& __k = _ExtractKey{}(__node->_M_v());
2202 size_type __bkt = _M_bucket_index(__code);
2206 __node_base_ptr __prev
2207 = __builtin_expect(__hint !=
nullptr,
false)
2208 && this->_M_equals(__k, __code, *__hint)
2210 : _M_find_before_node(__bkt, __k, __code);
2215 __node->_M_nxt = __prev->_M_nxt;
2216 __prev->_M_nxt = __node;
2217 if (__builtin_expect(__prev == __hint,
false))
2221 && !this->_M_equals(__k, __code, *__node->_M_next()))
2223 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2224 if (__next_bkt != __bkt)
2225 _M_buckets[__next_bkt] = __node;
2232 _M_insert_bucket_begin(__bkt, __node);
2234 return iterator(__node);
2238 template<
typename _Key,
typename _Value,
typename _Alloc,
2239 typename _ExtractKey,
typename _Equal,
2240 typename _Hash,
typename _RangeHash,
typename _Unused,
2241 typename _RehashPolicy,
typename _Traits>
2242 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
2244 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2245 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2246 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2247 const _NodeGenerator& __node_gen)
2248 -> pair<iterator, bool>
2250 if (size() <= __small_size_threshold())
2251 for (
auto __it = begin(); __it != end(); ++__it)
2252 if (this->_M_key_equals_tr(__k, *__it._M_cur))
2253 return { __it,
false };
2255 __hash_code __code = this->_M_hash_code_tr(__k);
2256 size_type __bkt = _M_bucket_index(__code);
2258 if (size() > __small_size_threshold())
2259 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2260 return { iterator(__node),
false };
2262 _Scoped_node __node {
2269 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2270 __node._M_node =
nullptr;
2271 return { __pos,
true };
2275 template<
typename _Key,
typename _Value,
typename _Alloc,
2276 typename _ExtractKey,
typename _Equal,
2277 typename _Hash,
typename _RangeHash,
typename _Unused,
2278 typename _RehashPolicy,
typename _Traits>
2279 template<
typename _Arg,
typename _NodeGenerator>
2281 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2282 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2283 _M_insert(const_iterator __hint, _Arg&& __v,
2284 const _NodeGenerator& __node_gen,
2292 auto __res = this->_M_compute_hash_code(
2293 __hint, _ExtractKey{}(__node._M_node->_M_v()));
2296 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2298 __node._M_node =
nullptr;
2302 template<
typename _Key,
typename _Value,
typename _Alloc,
2303 typename _ExtractKey,
typename _Equal,
2304 typename _Hash,
typename _RangeHash,
typename _Unused,
2305 typename _RehashPolicy,
typename _Traits>
2307 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2308 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2309 erase(const_iterator __it)
2312 __node_ptr __n = __it._M_cur;
2313 std::size_t __bkt = _M_bucket_index(*__n);
2318 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2319 return _M_erase(__bkt, __prev_n, __n);
2322 template<
typename _Key,
typename _Value,
typename _Alloc,
2323 typename _ExtractKey,
typename _Equal,
2324 typename _Hash,
typename _RangeHash,
typename _Unused,
2325 typename _RehashPolicy,
typename _Traits>
2327 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2328 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2329 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2332 if (__prev_n == _M_buckets[__bkt])
2333 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2334 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2335 else if (__n->_M_nxt)
2337 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2338 if (__next_bkt != __bkt)
2339 _M_buckets[__next_bkt] = __prev_n;
2342 __prev_n->_M_nxt = __n->_M_nxt;
2343 iterator __result(__n->_M_next());
2344 this->_M_deallocate_node(__n);
2350 template<
typename _Key,
typename _Value,
typename _Alloc,
2351 typename _ExtractKey,
typename _Equal,
2352 typename _Hash,
typename _RangeHash,
typename _Unused,
2353 typename _RehashPolicy,
typename _Traits>
2355 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2356 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2357 _M_erase(true_type ,
const key_type& __k)
2360 __node_base_ptr __prev_n;
2363 if (size() <= __small_size_threshold())
2365 __prev_n = _M_find_before_node(__k);
2370 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2371 __bkt = _M_bucket_index(*__n);
2375 __hash_code __code = this->_M_hash_code(__k);
2376 __bkt = _M_bucket_index(__code);
2379 __prev_n = _M_find_before_node(__bkt, __k, __code);
2384 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2387 _M_erase(__bkt, __prev_n, __n);
2391 template<
typename _Key,
typename _Value,
typename _Alloc,
2392 typename _ExtractKey,
typename _Equal,
2393 typename _Hash,
typename _RangeHash,
typename _Unused,
2394 typename _RehashPolicy,
typename _Traits>
2396 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2397 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2398 _M_erase(false_type ,
const key_type& __k)
2402 __node_base_ptr __prev_n;
2404 if (size() <= __small_size_threshold())
2406 __prev_n = _M_find_before_node(__k);
2411 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2412 __bkt = _M_bucket_index(*__n);
2416 __hash_code __code = this->_M_hash_code(__k);
2417 __bkt = _M_bucket_index(__code);
2420 __prev_n = _M_find_before_node(__bkt, __k, __code);
2424 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2433 __node_ptr __n_last = __n->_M_next();
2434 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2435 __n_last = __n_last->_M_next();
2437 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2440 size_type __result = 0;
2443 __node_ptr __p = __n->_M_next();
2444 this->_M_deallocate_node(__n);
2448 while (__n != __n_last);
2450 _M_element_count -= __result;
2451 if (__prev_n == _M_buckets[__bkt])
2452 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2453 else if (__n_last_bkt != __bkt)
2454 _M_buckets[__n_last_bkt] = __prev_n;
2455 __prev_n->_M_nxt = __n_last;
2459 template<
typename _Key,
typename _Value,
typename _Alloc,
2460 typename _ExtractKey,
typename _Equal,
2461 typename _Hash,
typename _RangeHash,
typename _Unused,
2462 typename _RehashPolicy,
typename _Traits>
2464 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2465 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2466 erase(const_iterator __first, const_iterator __last)
2469 __node_ptr __n = __first._M_cur;
2470 __node_ptr __last_n = __last._M_cur;
2471 if (__n == __last_n)
2472 return iterator(__n);
2474 std::size_t __bkt = _M_bucket_index(*__n);
2476 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2477 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2478 std::size_t __n_bkt = __bkt;
2483 __node_ptr __tmp = __n;
2484 __n = __n->_M_next();
2485 this->_M_deallocate_node(__tmp);
2489 __n_bkt = _M_bucket_index(*__n);
2491 while (__n != __last_n && __n_bkt == __bkt);
2492 if (__is_bucket_begin)
2493 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2494 if (__n == __last_n)
2496 __is_bucket_begin =
true;
2500 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2501 _M_buckets[__n_bkt] = __prev_n;
2502 __prev_n->_M_nxt = __n;
2503 return iterator(__n);
2506 template<
typename _Key,
typename _Value,
typename _Alloc,
2507 typename _ExtractKey,
typename _Equal,
2508 typename _Hash,
typename _RangeHash,
typename _Unused,
2509 typename _RehashPolicy,
typename _Traits>
2511 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2512 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2515 this->_M_deallocate_nodes(_M_begin());
2516 __builtin_memset(_M_buckets, 0,
2517 _M_bucket_count *
sizeof(__node_base_ptr));
2518 _M_element_count = 0;
2519 _M_before_begin._M_nxt =
nullptr;
2522 template<
typename _Key,
typename _Value,
typename _Alloc,
2523 typename _ExtractKey,
typename _Equal,
2524 typename _Hash,
typename _RangeHash,
typename _Unused,
2525 typename _RehashPolicy,
typename _Traits>
2527 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2528 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2529 rehash(size_type __bkt_count)
2531 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2533 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2535 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2537 if (__bkt_count != _M_bucket_count)
2538 _M_rehash(__bkt_count, __saved_state);
2542 _M_rehash_policy._M_reset(__saved_state);
2545 template<
typename _Key,
typename _Value,
typename _Alloc,
2546 typename _ExtractKey,
typename _Equal,
2547 typename _Hash,
typename _RangeHash,
typename _Unused,
2548 typename _RehashPolicy,
typename _Traits>
2550 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2551 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2552 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2556 _M_rehash_aux(__bkt_count, __unique_keys{});
2562 _M_rehash_policy._M_reset(__state);
2563 __throw_exception_again;
2568 template<
typename _Key,
typename _Value,
typename _Alloc,
2569 typename _ExtractKey,
typename _Equal,
2570 typename _Hash,
typename _RangeHash,
typename _Unused,
2571 typename _RehashPolicy,
typename _Traits>
2573 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2574 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2575 _M_rehash_aux(size_type __bkt_count, true_type )
2577 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2578 __node_ptr __p = _M_begin();
2579 _M_before_begin._M_nxt =
nullptr;
2580 std::size_t __bbegin_bkt = 0;
2583 __node_ptr __next = __p->_M_next();
2585 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2586 if (!__new_buckets[__bkt])
2588 __p->_M_nxt = _M_before_begin._M_nxt;
2589 _M_before_begin._M_nxt = __p;
2590 __new_buckets[__bkt] = &_M_before_begin;
2592 __new_buckets[__bbegin_bkt] = __p;
2593 __bbegin_bkt = __bkt;
2597 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2598 __new_buckets[__bkt]->_M_nxt = __p;
2604 _M_deallocate_buckets();
2605 _M_bucket_count = __bkt_count;
2606 _M_buckets = __new_buckets;
2611 template<
typename _Key,
typename _Value,
typename _Alloc,
2612 typename _ExtractKey,
typename _Equal,
2613 typename _Hash,
typename _RangeHash,
typename _Unused,
2614 typename _RehashPolicy,
typename _Traits>
2616 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2617 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2618 _M_rehash_aux(size_type __bkt_count, false_type )
2620 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2621 __node_ptr __p = _M_begin();
2622 _M_before_begin._M_nxt =
nullptr;
2623 std::size_t __bbegin_bkt = 0;
2624 std::size_t __prev_bkt = 0;
2625 __node_ptr __prev_p =
nullptr;
2626 bool __check_bucket =
false;
2630 __node_ptr __next = __p->_M_next();
2632 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2634 if (__prev_p && __prev_bkt == __bkt)
2639 __p->_M_nxt = __prev_p->_M_nxt;
2640 __prev_p->_M_nxt = __p;
2647 __check_bucket =
true;
2655 if (__prev_p->_M_nxt)
2657 std::size_t __next_bkt
2658 = __hash_code_base::_M_bucket_index(
2659 *__prev_p->_M_next(), __bkt_count);
2660 if (__next_bkt != __prev_bkt)
2661 __new_buckets[__next_bkt] = __prev_p;
2663 __check_bucket =
false;
2666 if (!__new_buckets[__bkt])
2668 __p->_M_nxt = _M_before_begin._M_nxt;
2669 _M_before_begin._M_nxt = __p;
2670 __new_buckets[__bkt] = &_M_before_begin;
2672 __new_buckets[__bbegin_bkt] = __p;
2673 __bbegin_bkt = __bkt;
2677 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2678 __new_buckets[__bkt]->_M_nxt = __p;
2686 if (__check_bucket && __prev_p->_M_nxt)
2688 std::size_t __next_bkt
2689 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2691 if (__next_bkt != __prev_bkt)
2692 __new_buckets[__next_bkt] = __prev_p;
2695 _M_deallocate_buckets();
2696 _M_bucket_count = __bkt_count;
2697 _M_buckets = __new_buckets;
2700#if __cplusplus > 201402L
2701 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2704#if __cpp_deduction_guides >= 201606
2706 template<
typename _Hash>
2707 using _RequireNotAllocatorOrIntegral
2708 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2712_GLIBCXX_END_NAMESPACE_VERSION
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
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.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
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.