33#pragma GCC system_header
38#if __cplusplus > 201402L
42namespace std _GLIBCXX_VISIBILITY(default)
44_GLIBCXX_BEGIN_NAMESPACE_VERSION
47 template<
typename _Tp,
typename _Hash>
50 __is_fast_hash<_Hash>,
52 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
57 template<
typename _Equal,
typename _Hash,
typename _Allocator>
58 using _Hashtable_enable_default_ctor
59 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
60 is_default_constructible<_Hash>,
61 is_default_constructible<_Allocator>>{},
62 __detail::_Hash_node_base>;
181 template<
typename _Key,
typename _Value,
typename _Alloc,
182 typename _ExtractKey,
typename _Equal,
183 typename _Hash,
typename _RangeHash,
typename _Unused,
184 typename _RehashPolicy,
typename _Traits>
186 :
public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
187 _Hash, _RangeHash, _Unused, _Traits>,
188 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
189 _Hash, _RangeHash, _Unused,
190 _RehashPolicy, _Traits>,
191 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
192 _Hash, _RangeHash, _Unused,
193 _RehashPolicy, _Traits>,
194 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
195 _Hash, _RangeHash, _Unused,
196 _RehashPolicy, _Traits>,
197 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
198 _Hash, _RangeHash, _Unused,
199 _RehashPolicy, _Traits>,
200 private __detail::_Hashtable_alloc<
201 __alloc_rebind<_Alloc,
202 __detail::_Hash_node<_Value,
203 _Traits::__hash_cached::value>>>,
204 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
206 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
207 "unordered container must have a non-const, non-volatile value_type");
208#if __cplusplus > 201703L || defined __STRICT_ANSI__
209 static_assert(is_same<typename _Alloc::value_type, _Value>{},
210 "unordered container must have the same value_type as its allocator");
213 using __traits_type = _Traits;
214 using __hash_cached =
typename __traits_type::__hash_cached;
215 using __constant_iterators =
typename __traits_type::__constant_iterators;
216 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
217 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
219 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
221 using __node_value_type =
222 __detail::_Hash_node_value<_Value, __hash_cached::value>;
223 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
224 using __value_alloc_traits =
225 typename __hashtable_alloc::__value_alloc_traits;
226 using __node_alloc_traits =
227 typename __hashtable_alloc::__node_alloc_traits;
228 using __node_base =
typename __hashtable_alloc::__node_base;
229 using __node_base_ptr =
typename __hashtable_alloc::__node_base_ptr;
230 using __buckets_ptr =
typename __hashtable_alloc::__buckets_ptr;
232 using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
235 _RehashPolicy, _Traits>;
236 using __enable_default_ctor
237 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
238 using __rehash_guard_t
239 = __detail::_RehashStateGuard<_RehashPolicy>;
242 typedef _Key key_type;
243 typedef _Value value_type;
244 typedef _Alloc allocator_type;
245 typedef _Equal key_equal;
249 typedef typename __value_alloc_traits::pointer pointer;
250 typedef typename __value_alloc_traits::const_pointer const_pointer;
251 typedef value_type& reference;
252 typedef const value_type& const_reference;
254 using iterator =
typename __insert_base::iterator;
256 using const_iterator =
typename __insert_base::const_iterator;
258 using local_iterator = __detail::_Local_iterator<key_type, _Value,
259 _ExtractKey, _Hash, _RangeHash, _Unused,
260 __constant_iterators::value,
261 __hash_cached::value>;
263 using const_local_iterator = __detail::_Local_const_iterator<
265 _ExtractKey, _Hash, _RangeHash, _Unused,
266 __constant_iterators::value, __hash_cached::value>;
269 using __rehash_type = _RehashPolicy;
271 using __unique_keys =
typename __traits_type::__unique_keys;
273 using __hashtable_base = __detail::
274 _Hashtable_base<_Key, _Value, _ExtractKey,
275 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
277 using __hash_code_base =
typename __hashtable_base::__hash_code_base;
278 using __hash_code =
typename __hashtable_base::__hash_code;
279 using __ireturn_type =
typename __insert_base::__ireturn_type;
281 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
282 _Equal, _Hash, _RangeHash, _Unused,
283 _RehashPolicy, _Traits>;
285 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
287 _Hash, _RangeHash, _Unused,
288 _RehashPolicy, _Traits>;
290 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
291 _Equal, _Hash, _RangeHash, _Unused,
292 _RehashPolicy, _Traits>;
294 using __reuse_or_alloc_node_gen_t =
295 __detail::_ReuseOrAllocNode<__node_alloc_type>;
296 using __alloc_node_gen_t =
297 __detail::_AllocNode<__node_alloc_type>;
298 using __node_builder_t =
299 __detail::_NodeBuilder<_ExtractKey>;
305 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
306 : _M_h(__h), _M_node(__n) { }
309 template<
typename... _Args>
310 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
312 _M_node(__h->_M_allocate_node(
std::
forward<_Args>(__args)...))
316 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
318 _Scoped_node(
const _Scoped_node&) =
delete;
319 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
321 __hashtable_alloc* _M_h;
325 template<
typename _Ht>
327 __conditional_t<std::is_lvalue_reference<_Ht>::value,
328 const value_type&, value_type&&>
329 __fwd_value_for(value_type& __val)
noexcept
336 struct __hash_code_base_access : __hash_code_base
337 {
using __hash_code_base::_M_bucket_index; };
340 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
341 "Functor used to map hash code to bucket index"
342 " must be nothrow default constructible");
343 static_assert(
noexcept(
345 "Functor used to map hash code to bucket index must be"
349 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
350 "_ExtractKey must be nothrow default constructible");
351 static_assert(
noexcept(
353 "_ExtractKey functor must be noexcept invocable");
355 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
356 typename _ExtractKeya,
typename _Equala,
357 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
358 typename _RehashPolicya,
typename _Traitsa,
360 friend struct __detail::_Map_base;
362 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
363 typename _ExtractKeya,
typename _Equala,
364 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
365 typename _RehashPolicya,
typename _Traitsa>
366 friend struct __detail::_Insert_base;
368 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
369 typename _ExtractKeya,
typename _Equala,
370 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
371 typename _RehashPolicya,
typename _Traitsa,
372 bool _Constant_iteratorsa>
373 friend struct __detail::_Insert;
375 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
376 typename _ExtractKeya,
typename _Equala,
377 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
378 typename _RehashPolicya,
typename _Traitsa,
380 friend struct __detail::_Equality;
383 using size_type =
typename __hashtable_base::size_type;
384 using difference_type =
typename __hashtable_base::difference_type;
386#if __cplusplus > 201402L
387 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
388 using insert_return_type = _Node_insert_return<iterator, node_type>;
392 __buckets_ptr _M_buckets = &_M_single_bucket;
393 size_type _M_bucket_count = 1;
394 __node_base _M_before_begin;
395 size_type _M_element_count = 0;
396 _RehashPolicy _M_rehash_policy;
404 __node_base_ptr _M_single_bucket =
nullptr;
409 if (
auto __begin = _M_begin())
410 _M_buckets[_M_bucket_index(*__begin)] = &_M_before_begin;
414 _M_update_bbegin(__node_ptr __n)
416 _M_before_begin._M_nxt = __n;
421 _M_uses_single_bucket(__buckets_ptr __bkts)
const
422 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
425 _M_uses_single_bucket()
const
426 {
return _M_uses_single_bucket(_M_buckets); }
428 static constexpr size_t
429 __small_size_threshold() noexcept
432 __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
436 _M_base_alloc() {
return *
this; }
439 _M_allocate_buckets(size_type __bkt_count)
441 if (__builtin_expect(__bkt_count == 1,
false))
443 _M_single_bucket =
nullptr;
444 return &_M_single_bucket;
447 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
451 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
453 if (_M_uses_single_bucket(__bkts))
456 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
460 _M_deallocate_buckets()
461 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
466 _M_bucket_begin(size_type __bkt)
const
468 __node_base_ptr __n = _M_buckets[__bkt];
469 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) : nullptr;
474 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
478 template<
typename _Ht>
480 _M_assign_elements(_Ht&&);
482 template<
typename _Ht,
typename _NodeGenerator>
484 _M_assign(_Ht&&,
const _NodeGenerator&);
487 _M_move_assign(_Hashtable&&, true_type);
490 _M_move_assign(_Hashtable&&, false_type);
495 _Hashtable(const _Hash& __h, const _Equal& __eq,
496 const allocator_type& __a)
497 : __hashtable_base(__h, __eq),
498 __hashtable_alloc(__node_alloc_type(__a)),
499 __enable_default_ctor(_Enable_default_constructor_tag{})
502 template<
bool _No_realloc = true>
503 static constexpr bool
506#if __cplusplus <= 201402L
507 return __and_<__bool_constant<_No_realloc>,
508 is_nothrow_copy_constructible<_Hash>,
509 is_nothrow_copy_constructible<_Equal>>::value;
511 if constexpr (_No_realloc)
512 if constexpr (is_nothrow_copy_constructible<_Hash>())
513 return is_nothrow_copy_constructible<_Equal>();
518 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
520 noexcept(_S_nothrow_move());
522 _Hashtable(_Hashtable&&, __node_alloc_type&&,
525 template<
typename _InputIterator>
526 _Hashtable(_InputIterator __first, _InputIterator __last,
527 size_type __bkt_count_hint,
528 const _Hash&,
const _Equal&,
const allocator_type&,
531 template<
typename _InputIterator>
532 _Hashtable(_InputIterator __first, _InputIterator __last,
533 size_type __bkt_count_hint,
534 const _Hash&,
const _Equal&,
const allocator_type&,
539 _Hashtable() =
default;
541 _Hashtable(
const _Hashtable&);
543 _Hashtable(
const _Hashtable&,
const allocator_type&);
546 _Hashtable(size_type __bkt_count_hint,
547 const _Hash& __hf = _Hash(),
548 const key_equal& __eql = key_equal(),
549 const allocator_type& __a = allocator_type());
552 _Hashtable(_Hashtable&& __ht)
553 noexcept(_S_nothrow_move())
554 : _Hashtable(
std::
move(__ht),
std::
move(__ht._M_node_allocator()),
558 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
559 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
560 : _Hashtable(
std::
move(__ht), __node_alloc_type(__a),
561 typename __node_alloc_traits::is_always_equal{})
565 _Hashtable(
const allocator_type& __a)
566 : __hashtable_alloc(__node_alloc_type(__a)),
567 __enable_default_ctor(_Enable_default_constructor_tag{})
570 template<
typename _InputIterator>
571 _Hashtable(_InputIterator __f, _InputIterator __l,
572 size_type __bkt_count_hint = 0,
573 const _Hash& __hf = _Hash(),
574 const key_equal& __eql = key_equal(),
575 const allocator_type& __a = allocator_type())
576 : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
580 _Hashtable(initializer_list<value_type> __l,
581 size_type __bkt_count_hint = 0,
582 const _Hash& __hf = _Hash(),
583 const key_equal& __eql = key_equal(),
584 const allocator_type& __a = allocator_type())
585 : _Hashtable(__l.
begin(), __l.
end(), __bkt_count_hint,
586 __hf, __eql, __a, __unique_keys{})
590 operator=(
const _Hashtable& __ht);
593 operator=(_Hashtable&& __ht)
594 noexcept(__node_alloc_traits::_S_nothrow_move()
595 && is_nothrow_move_assignable<_Hash>::value
596 && is_nothrow_move_assignable<_Equal>::value)
598 constexpr bool __move_storage =
599 __node_alloc_traits::_S_propagate_on_move_assign()
600 || __node_alloc_traits::_S_always_equal();
601 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
606 operator=(initializer_list<value_type> __l)
608 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
609 _M_before_begin._M_nxt =
nullptr;
613 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
616 if (_M_bucket_count < __l_bkt_count)
617 rehash(__l_bkt_count);
619 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
623 ~_Hashtable() noexcept;
627 noexcept(__and_<__is_nothrow_swappable<_Hash>,
628 __is_nothrow_swappable<_Equal>>::value);
633 {
return iterator(_M_begin()); }
636 begin() const noexcept
637 {
return const_iterator(_M_begin()); }
641 {
return iterator(
nullptr); }
645 {
return const_iterator(
nullptr); }
649 {
return const_iterator(_M_begin()); }
652 cend() const noexcept
653 {
return const_iterator(
nullptr); }
656 size() const noexcept
657 {
return _M_element_count; }
659 _GLIBCXX_NODISCARD
bool
660 empty() const noexcept
661 {
return size() == 0; }
664 get_allocator() const noexcept
665 {
return allocator_type(this->_M_node_allocator()); }
668 max_size() const noexcept
669 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
674 {
return this->_M_eq(); }
680 bucket_count() const noexcept
681 {
return _M_bucket_count; }
684 max_bucket_count() const noexcept
685 {
return max_size(); }
688 bucket_size(size_type __bkt)
const
692 bucket(
const key_type& __k)
const
693 {
return _M_bucket_index(this->_M_hash_code(__k)); }
696 begin(size_type __bkt)
698 return local_iterator(*
this, _M_bucket_begin(__bkt),
699 __bkt, _M_bucket_count);
704 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
707 begin(size_type __bkt)
const
709 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
710 __bkt, _M_bucket_count);
714 end(size_type __bkt)
const
715 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
719 cbegin(size_type __bkt)
const
721 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
722 __bkt, _M_bucket_count);
726 cend(size_type __bkt)
const
727 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
730 load_factor() const noexcept
732 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
741 __rehash_policy()
const
742 {
return _M_rehash_policy; }
745 __rehash_policy(
const _RehashPolicy& __pol)
746 { _M_rehash_policy = __pol; }
750 find(
const key_type& __k);
753 find(
const key_type& __k)
const;
756 count(
const key_type& __k)
const;
759 equal_range(
const key_type& __k);
762 equal_range(
const key_type& __k)
const;
764#ifdef __glibcxx_generic_unordered_lookup
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);
771 template<
typename _Kt,
772 typename = __has_is_transparent_t<_Hash, _Kt>,
773 typename = __has_is_transparent_t<_Equal, _Kt>>
775 _M_find_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>>
781 _M_count_tr(
const _Kt& __k)
const;
783 template<
typename _Kt,
784 typename = __has_is_transparent_t<_Hash, _Kt>,
785 typename = __has_is_transparent_t<_Equal, _Kt>>
786 pair<iterator, iterator>
787 _M_equal_range_tr(
const _Kt& __k);
789 template<
typename _Kt,
790 typename = __has_is_transparent_t<_Hash, _Kt>,
791 typename = __has_is_transparent_t<_Equal, _Kt>>
792 pair<const_iterator, const_iterator>
793 _M_equal_range_tr(
const _Kt& __k)
const;
799 _M_bucket_index(
const __node_value_type& __n)
const noexcept
800 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
803 _M_bucket_index(__hash_code __c)
const
804 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
807 _M_find_before_node(
const key_type&);
812 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
814 template<
typename _Kt>
816 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
819 _M_find_node(size_type __bkt,
const key_type& __key,
820 __hash_code __c)
const
822 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
824 return static_cast<__node_ptr
>(__before_n->_M_nxt);
828 template<
typename _Kt>
830 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
831 __hash_code __c)
const
833 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
835 return static_cast<__node_ptr
>(__before_n->_M_nxt);
841 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
843 if (_M_buckets[__bkt])
847 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
848 _M_buckets[__bkt]->_M_nxt = __node;
855 __node->_M_nxt = _M_before_begin._M_nxt;
856 _M_before_begin._M_nxt = __node;
861 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
863 _M_buckets[__bkt] = &_M_before_begin;
869 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
870 size_type __next_bkt)
873 _M_buckets[__bkt] =
nullptr;
874 else if (__next_bkt != __bkt)
876 _M_buckets[__next_bkt] = _M_buckets[__bkt];
877 _M_buckets[__bkt] =
nullptr;
883 _M_get_previous_node(size_type __bkt, __node_ptr __n);
885 pair<__node_ptr, __hash_code>
886 _M_compute_hash_code(__node_ptr __hint,
const key_type& __k)
const;
895 _M_insert_unique_node(size_type __bkt, __hash_code,
896 __node_ptr __n, size_type __n_elt = 1);
901 _M_insert_multi_node(__node_ptr __hint,
902 __hash_code __code, __node_ptr __n);
904 template<
typename... _Args>
906 _M_emplace(true_type __uks, _Args&&... __args);
908 template<
typename... _Args>
910 _M_emplace(false_type __uks, _Args&&... __args)
914 template<
typename... _Args>
916 _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
919 template<
typename... _Args>
921 _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
923 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
925 _M_insert_unique(_Kt&&, _Arg&&,
const _NodeGenerator&);
927 template<
typename _Kt>
928 static __conditional_t<
929 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
930 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
932 _S_forward_key(_Kt&& __k)
935 static const key_type&
936 _S_forward_key(
const key_type& __k)
940 _S_forward_key(key_type&& __k)
943 template<
typename _Arg,
typename _NodeGenerator>
945 _M_insert_unique_aux(_Arg&& __arg,
const _NodeGenerator& __node_gen)
947 return _M_insert_unique(
952 template<
typename _Arg,
typename _NodeGenerator>
954 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
958 = __detail::_ConvertToValueType<_ExtractKey, value_type>;
959 return _M_insert_unique_aux(
963 template<
typename _Arg,
typename _NodeGenerator>
965 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
969 = __detail::_ConvertToValueType<_ExtractKey, value_type>;
970 return _M_insert(
cend(),
975 template<
typename _Arg,
typename _NodeGenerator>
977 _M_insert(const_iterator, _Arg&& __arg,
978 const _NodeGenerator& __node_gen, true_type __uks)
985 template<
typename _Arg,
typename _NodeGenerator>
987 _M_insert(const_iterator, _Arg&&,
988 const _NodeGenerator&, false_type __uks);
991 _M_erase(true_type __uks,
const key_type&);
994 _M_erase(false_type __uks,
const key_type&);
997 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
1001 template<
typename... _Args>
1003 emplace(_Args&&... __args)
1006 template<
typename... _Args>
1008 emplace_hint(const_iterator __hint, _Args&&... __args)
1010 return _M_emplace(__hint, __unique_keys{},
1018 erase(const_iterator);
1023 erase(iterator __it)
1024 {
return erase(const_iterator(__it)); }
1027 erase(
const key_type& __k)
1028 {
return _M_erase(__unique_keys{}, __k); }
1031 erase(const_iterator, const_iterator);
1038 void rehash(size_type __bkt_count);
1043#if __glibcxx_node_extract
1046 _M_reinsert_node(node_type&& __nh)
1048 insert_return_type __ret;
1050 __ret.position =
end();
1053 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1055 __node_ptr __n =
nullptr;
1056 const key_type& __k = __nh._M_key();
1057 const size_type __size =
size();
1058 if (__size <= __small_size_threshold())
1060 for (__n = _M_begin(); __n; __n = __n->_M_next())
1061 if (this->_M_key_equals(__k, *__n))
1069 __code = this->_M_hash_code(__k);
1070 __bkt = _M_bucket_index(__code);
1071 if (__size > __small_size_threshold())
1072 __n = _M_find_node(__bkt, __k, __code);
1078 __ret.position = iterator(__n);
1079 __ret.inserted =
false;
1084 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1086 __ret.inserted =
true;
1094 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1099 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1101 const key_type& __k = __nh._M_key();
1102 auto __code = this->_M_hash_code(__k);
1104 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1111 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1113 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1114 if (__prev_n == _M_buckets[__bkt])
1115 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1116 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1117 else if (__n->_M_nxt)
1119 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1120 if (__next_bkt != __bkt)
1121 _M_buckets[__next_bkt] = __prev_n;
1124 __prev_n->_M_nxt = __n->_M_nxt;
1125 __n->_M_nxt =
nullptr;
1127 return { __n, this->_M_node_allocator() };
1132 template<
typename _H2>
1134 _M_src_hash_code(
const _H2&,
const key_type& __k,
1135 const __node_value_type& __src_n)
const
1137 if constexpr (std::is_same_v<_H2, _Hash>)
1138 if constexpr (std::is_empty_v<_Hash>)
1139 return this->_M_hash_code(__src_n);
1141 return this->_M_hash_code(__k);
1147 extract(const_iterator __pos)
1149 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1150 return _M_extract_node(__bkt,
1151 _M_get_previous_node(__bkt, __pos._M_cur));
1156 extract(
const _Key& __k)
1159 __hash_code __code = this->_M_hash_code(__k);
1160 std::size_t __bkt = _M_bucket_index(__code);
1161 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1162 __nh = _M_extract_node(__bkt, __prev_node);
1167 template<
typename _Compatible_Hashtable>
1169 _M_merge_unique(_Compatible_Hashtable& __src)
1171 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1172 node_type>,
"Node types are compatible");
1173 __glibcxx_assert(get_allocator() == __src.get_allocator());
1175 auto __n_elt = __src.size();
1176 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1179 const size_type __size =
size();
1180 const key_type& __k = _ExtractKey{}(*__pos);
1181 if (__size <= __small_size_threshold())
1183 bool __found =
false;
1184 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1185 if (this->_M_key_equals(__k, *__n))
1200 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1201 size_type __bkt = _M_bucket_index(__code);
1202 if (__size <= __small_size_threshold()
1203 || _M_find_node(__bkt, __k, __code) ==
nullptr)
1205 auto __nh = __src.extract(__pos);
1206 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1210 else if (__n_elt != 1)
1216 template<
typename _Compatible_Hashtable>
1218 _M_merge_multi(_Compatible_Hashtable& __src)
1220 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1221 node_type>,
"Node types are compatible");
1222 __glibcxx_assert(get_allocator() == __src.get_allocator());
1224 __node_ptr __hint =
nullptr;
1225 this->reserve(
size() + __src.size());
1226 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1229 const key_type& __k = _ExtractKey{}(*__pos);
1231 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1232 auto __nh = __src.extract(__pos);
1233 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1241 void _M_rehash(size_type __bkt_count, true_type __uks);
1244 void _M_rehash(size_type __bkt_count, false_type __uks);
1248 template<
typename _Key,
typename _Value,
typename _Alloc,
1249 typename _ExtractKey,
typename _Equal,
1250 typename _Hash,
typename _RangeHash,
typename _Unused,
1251 typename _RehashPolicy,
typename _Traits>
1252 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1253 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1254 _Hashtable(size_type __bkt_count_hint,
1255 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1256 : _Hashtable(__h, __eq, __a)
1258 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1259 if (__bkt_count > _M_bucket_count)
1261 _M_buckets = _M_allocate_buckets(__bkt_count);
1262 _M_bucket_count = __bkt_count;
1266 template<
typename _Key,
typename _Value,
typename _Alloc,
1267 typename _ExtractKey,
typename _Equal,
1268 typename _Hash,
typename _RangeHash,
typename _Unused,
1269 typename _RehashPolicy,
typename _Traits>
1270 template<
typename _InputIterator>
1271 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1272 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1273 _Hashtable(_InputIterator __f, _InputIterator __l,
1274 size_type __bkt_count_hint,
1275 const _Hash& __h,
const _Equal& __eq,
1276 const allocator_type& __a, true_type )
1277 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1278 { this->insert(__f, __l); }
1280 template<
typename _Key,
typename _Value,
typename _Alloc,
1281 typename _ExtractKey,
typename _Equal,
1282 typename _Hash,
typename _RangeHash,
typename _Unused,
1283 typename _RehashPolicy,
typename _Traits>
1284 template<
typename _InputIterator>
1285 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1286 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1287 _Hashtable(_InputIterator __f, _InputIterator __l,
1288 size_type __bkt_count_hint,
1289 const _Hash& __h,
const _Equal& __eq,
1290 const allocator_type& __a, false_type __uks)
1291 : _Hashtable(__h, __eq, __a)
1293 auto __nb_elems = __detail::__distance_fw(__f, __l);
1295 _M_rehash_policy._M_next_bkt(
1296 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1299 if (__bkt_count > _M_bucket_count)
1301 _M_buckets = _M_allocate_buckets(__bkt_count);
1302 _M_bucket_count = __bkt_count;
1305 __alloc_node_gen_t __node_gen(*
this);
1306 for (; __f != __l; ++__f)
1307 _M_insert(*__f, __node_gen, __uks);
1310 template<
typename _Key,
typename _Value,
typename _Alloc,
1311 typename _ExtractKey,
typename _Equal,
1312 typename _Hash,
typename _RangeHash,
typename _Unused,
1313 typename _RehashPolicy,
typename _Traits>
1315 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1316 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1317 operator=(
const _Hashtable& __ht)
1323 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1325 auto& __this_alloc = this->_M_node_allocator();
1326 auto& __that_alloc = __ht._M_node_allocator();
1327 if (!__node_alloc_traits::_S_always_equal()
1328 && __this_alloc != __that_alloc)
1331 this->_M_deallocate_nodes(_M_begin());
1332 _M_before_begin._M_nxt =
nullptr;
1333 _M_deallocate_buckets();
1334 _M_buckets =
nullptr;
1335 std::__alloc_on_copy(__this_alloc, __that_alloc);
1336 __hashtable_base::operator=(__ht);
1337 _M_bucket_count = __ht._M_bucket_count;
1338 _M_element_count = __ht._M_element_count;
1339 _M_rehash_policy = __ht._M_rehash_policy;
1340 __alloc_node_gen_t __alloc_node_gen(*
this);
1343 _M_assign(__ht, __alloc_node_gen);
1350 __throw_exception_again;
1354 std::__alloc_on_copy(__this_alloc, __that_alloc);
1358 _M_assign_elements(__ht);
1362 template<
typename _Key,
typename _Value,
typename _Alloc,
1363 typename _ExtractKey,
typename _Equal,
1364 typename _Hash,
typename _RangeHash,
typename _Unused,
1365 typename _RehashPolicy,
typename _Traits>
1366 template<
typename _Ht>
1368 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1369 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1370 _M_assign_elements(_Ht&& __ht)
1372 __buckets_ptr __former_buckets =
nullptr;
1373 std::size_t __former_bucket_count = _M_bucket_count;
1374 __rehash_guard_t __rehash_guard(_M_rehash_policy);
1376 if (_M_bucket_count != __ht._M_bucket_count)
1378 __former_buckets = _M_buckets;
1379 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1380 _M_bucket_count = __ht._M_bucket_count;
1383 __builtin_memset(_M_buckets, 0,
1384 _M_bucket_count *
sizeof(__node_base_ptr));
1389 _M_element_count = __ht._M_element_count;
1390 _M_rehash_policy = __ht._M_rehash_policy;
1391 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1392 _M_before_begin._M_nxt =
nullptr;
1394 if (__former_buckets)
1395 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1396 __rehash_guard._M_guarded_obj =
nullptr;
1400 if (__former_buckets)
1403 _M_deallocate_buckets();
1404 _M_buckets = __former_buckets;
1405 _M_bucket_count = __former_bucket_count;
1407 __builtin_memset(_M_buckets, 0,
1408 _M_bucket_count *
sizeof(__node_base_ptr));
1409 __throw_exception_again;
1413 template<
typename _Key,
typename _Value,
typename _Alloc,
1414 typename _ExtractKey,
typename _Equal,
1415 typename _Hash,
typename _RangeHash,
typename _Unused,
1416 typename _RehashPolicy,
typename _Traits>
1417 template<
typename _Ht,
typename _NodeGenerator>
1419 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1420 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1421 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1423 __buckets_ptr __buckets =
nullptr;
1425 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1429 if (!__ht._M_before_begin._M_nxt)
1434 __node_ptr __ht_n = __ht._M_begin();
1436 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1437 this->_M_copy_code(*__this_n, *__ht_n);
1438 _M_update_bbegin(__this_n);
1441 __node_ptr __prev_n = __this_n;
1442 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1444 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1445 __prev_n->_M_nxt = __this_n;
1446 this->_M_copy_code(*__this_n, *__ht_n);
1447 size_type __bkt = _M_bucket_index(*__this_n);
1448 if (!_M_buckets[__bkt])
1449 _M_buckets[__bkt] = __prev_n;
1450 __prev_n = __this_n;
1457 _M_deallocate_buckets();
1458 __throw_exception_again;
1462 template<
typename _Key,
typename _Value,
typename _Alloc,
1463 typename _ExtractKey,
typename _Equal,
1464 typename _Hash,
typename _RangeHash,
typename _Unused,
1465 typename _RehashPolicy,
typename _Traits>
1467 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1468 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1471 _M_rehash_policy._M_reset();
1472 _M_bucket_count = 1;
1473 _M_single_bucket =
nullptr;
1474 _M_buckets = &_M_single_bucket;
1475 _M_before_begin._M_nxt =
nullptr;
1476 _M_element_count = 0;
1479 template<
typename _Key,
typename _Value,
typename _Alloc,
1480 typename _ExtractKey,
typename _Equal,
1481 typename _Hash,
typename _RangeHash,
typename _Unused,
1482 typename _RehashPolicy,
typename _Traits>
1484 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1485 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1486 _M_move_assign(_Hashtable&& __ht, true_type)
1491 this->_M_deallocate_nodes(_M_begin());
1492 _M_deallocate_buckets();
1493 __hashtable_base::operator=(
std::move(__ht));
1494 _M_rehash_policy = __ht._M_rehash_policy;
1495 if (!__ht._M_uses_single_bucket())
1496 _M_buckets = __ht._M_buckets;
1499 _M_buckets = &_M_single_bucket;
1500 _M_single_bucket = __ht._M_single_bucket;
1503 _M_bucket_count = __ht._M_bucket_count;
1504 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1505 _M_element_count = __ht._M_element_count;
1506 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1513 template<
typename _Key,
typename _Value,
typename _Alloc,
1514 typename _ExtractKey,
typename _Equal,
1515 typename _Hash,
typename _RangeHash,
typename _Unused,
1516 typename _RehashPolicy,
typename _Traits>
1518 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1519 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1520 _M_move_assign(_Hashtable&& __ht, false_type)
1522 if (__ht._M_node_allocator() == this->_M_node_allocator())
1523 _M_move_assign(
std::move(__ht), true_type{});
1532 template<
typename _Key,
typename _Value,
typename _Alloc,
1533 typename _ExtractKey,
typename _Equal,
1534 typename _Hash,
typename _RangeHash,
typename _Unused,
1535 typename _RehashPolicy,
typename _Traits>
1536 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1537 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1538 _Hashtable(
const _Hashtable& __ht)
1539 : __hashtable_base(__ht),
1541 __rehash_base(__ht),
1543 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1544 __enable_default_ctor(__ht),
1545 _M_buckets(nullptr),
1546 _M_bucket_count(__ht._M_bucket_count),
1547 _M_element_count(__ht._M_element_count),
1548 _M_rehash_policy(__ht._M_rehash_policy)
1550 __alloc_node_gen_t __alloc_node_gen(*
this);
1551 _M_assign(__ht, __alloc_node_gen);
1554 template<
typename _Key,
typename _Value,
typename _Alloc,
1555 typename _ExtractKey,
typename _Equal,
1556 typename _Hash,
typename _RangeHash,
typename _Unused,
1557 typename _RehashPolicy,
typename _Traits>
1558 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1559 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1560 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1562 noexcept(_S_nothrow_move())
1563 : __hashtable_base(__ht),
1565 __rehash_base(__ht),
1566 __hashtable_alloc(
std::
move(__a)),
1567 __enable_default_ctor(__ht),
1568 _M_buckets(__ht._M_buckets),
1569 _M_bucket_count(__ht._M_bucket_count),
1570 _M_before_begin(__ht._M_before_begin._M_nxt),
1571 _M_element_count(__ht._M_element_count),
1572 _M_rehash_policy(__ht._M_rehash_policy)
1575 if (__ht._M_uses_single_bucket())
1577 _M_buckets = &_M_single_bucket;
1578 _M_single_bucket = __ht._M_single_bucket;
1587 template<
typename _Key,
typename _Value,
typename _Alloc,
1588 typename _ExtractKey,
typename _Equal,
1589 typename _Hash,
typename _RangeHash,
typename _Unused,
1590 typename _RehashPolicy,
typename _Traits>
1591 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1592 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1593 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1594 : __hashtable_base(__ht),
1596 __rehash_base(__ht),
1597 __hashtable_alloc(__node_alloc_type(__a)),
1598 __enable_default_ctor(__ht),
1600 _M_bucket_count(__ht._M_bucket_count),
1601 _M_element_count(__ht._M_element_count),
1602 _M_rehash_policy(__ht._M_rehash_policy)
1604 __alloc_node_gen_t __alloc_node_gen(*
this);
1605 _M_assign(__ht, __alloc_node_gen);
1608 template<
typename _Key,
typename _Value,
typename _Alloc,
1609 typename _ExtractKey,
typename _Equal,
1610 typename _Hash,
typename _RangeHash,
typename _Unused,
1611 typename _RehashPolicy,
typename _Traits>
1612 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1613 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1614 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1616 : __hashtable_base(__ht),
1618 __rehash_base(__ht),
1619 __hashtable_alloc(
std::
move(__a)),
1620 __enable_default_ctor(__ht),
1621 _M_buckets(nullptr),
1622 _M_bucket_count(__ht._M_bucket_count),
1623 _M_element_count(__ht._M_element_count),
1624 _M_rehash_policy(__ht._M_rehash_policy)
1626 if (__ht._M_node_allocator() == this->_M_node_allocator())
1628 if (__ht._M_uses_single_bucket())
1630 _M_buckets = &_M_single_bucket;
1631 _M_single_bucket = __ht._M_single_bucket;
1634 _M_buckets = __ht._M_buckets;
1638 _M_update_bbegin(__ht._M_begin());
1644 __alloc_node_gen_t __alloc_gen(*
this);
1646 using _Fwd_Ht = __conditional_t<
1647 __move_if_noexcept_cond<value_type>::value,
1648 const _Hashtable&, _Hashtable&&>;
1654 template<
typename _Key,
typename _Value,
typename _Alloc,
1655 typename _ExtractKey,
typename _Equal,
1656 typename _Hash,
typename _RangeHash,
typename _Unused,
1657 typename _RehashPolicy,
typename _Traits>
1658 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1659 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1660 ~_Hashtable() noexcept
1665 static_assert(
noexcept(declval<const __hash_code_base_access&>()
1666 ._M_bucket_index(declval<const __node_value_type&>(),
1668 "Cache the hash code or qualify your functors involved"
1669 " in hash code and bucket index computation with noexcept");
1672 _M_deallocate_buckets();
1675 template<
typename _Key,
typename _Value,
typename _Alloc,
1676 typename _ExtractKey,
typename _Equal,
1677 typename _Hash,
typename _RangeHash,
typename _Unused,
1678 typename _RehashPolicy,
typename _Traits>
1680 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1681 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1682 swap(_Hashtable& __x)
1683 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1684 __is_nothrow_swappable<_Equal>>::value)
1691 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1692 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1695 if (this->_M_uses_single_bucket())
1697 if (!__x._M_uses_single_bucket())
1699 _M_buckets = __x._M_buckets;
1700 __x._M_buckets = &__x._M_single_bucket;
1703 else if (__x._M_uses_single_bucket())
1705 __x._M_buckets = _M_buckets;
1706 _M_buckets = &_M_single_bucket;
1709 std::swap(_M_buckets, __x._M_buckets);
1711 std::swap(_M_bucket_count, __x._M_bucket_count);
1712 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1713 std::swap(_M_element_count, __x._M_element_count);
1714 std::swap(_M_single_bucket, __x._M_single_bucket);
1719 __x._M_update_bbegin();
1722 template<
typename _Key,
typename _Value,
typename _Alloc,
1723 typename _ExtractKey,
typename _Equal,
1724 typename _Hash,
typename _RangeHash,
typename _Unused,
1725 typename _RehashPolicy,
typename _Traits>
1727 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1728 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1729 find(
const key_type& __k)
1732 if (
size() <= __small_size_threshold())
1734 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
1735 if (this->_M_key_equals(__k, *__it))
1736 return iterator(__it);
1740 __hash_code __code = this->_M_hash_code(__k);
1741 std::size_t __bkt = _M_bucket_index(__code);
1742 return iterator(_M_find_node(__bkt, __k, __code));
1745 template<
typename _Key,
typename _Value,
typename _Alloc,
1746 typename _ExtractKey,
typename _Equal,
1747 typename _Hash,
typename _RangeHash,
typename _Unused,
1748 typename _RehashPolicy,
typename _Traits>
1750 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1751 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1752 find(
const key_type& __k)
const
1755 if (
size() <= __small_size_threshold())
1757 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
1758 if (this->_M_key_equals(__k, *__it))
1759 return const_iterator(__it);
1763 __hash_code __code = this->_M_hash_code(__k);
1764 std::size_t __bkt = _M_bucket_index(__code);
1765 return const_iterator(_M_find_node(__bkt, __k, __code));
1768#if __cplusplus > 201703L
1769 template<
typename _Key,
typename _Value,
typename _Alloc,
1770 typename _ExtractKey,
typename _Equal,
1771 typename _Hash,
typename _RangeHash,
typename _Unused,
1772 typename _RehashPolicy,
typename _Traits>
1773 template<
typename _Kt,
typename,
typename>
1775 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1776 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1777 _M_find_tr(
const _Kt& __k)
1780 if (
size() <= __small_size_threshold())
1782 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1783 if (this->_M_key_equals_tr(__k, *__n))
1784 return iterator(__n);
1788 __hash_code __code = this->_M_hash_code_tr(__k);
1789 std::size_t __bkt = _M_bucket_index(__code);
1790 return iterator(_M_find_node_tr(__bkt, __k, __code));
1793 template<
typename _Key,
typename _Value,
typename _Alloc,
1794 typename _ExtractKey,
typename _Equal,
1795 typename _Hash,
typename _RangeHash,
typename _Unused,
1796 typename _RehashPolicy,
typename _Traits>
1797 template<
typename _Kt,
typename,
typename>
1799 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1800 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1801 _M_find_tr(
const _Kt& __k)
const
1804 if (
size() <= __small_size_threshold())
1806 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1807 if (this->_M_key_equals_tr(__k, *__n))
1808 return const_iterator(__n);
1812 __hash_code __code = this->_M_hash_code_tr(__k);
1813 std::size_t __bkt = _M_bucket_index(__code);
1814 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
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 count(
const key_type& __k)
const
1828 auto __it = find(__k);
1832 if (__unique_keys::value)
1835 size_type __result = 1;
1836 for (
auto __ref = __it++;
1837 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1844#if __cplusplus > 201703L
1845 template<
typename _Key,
typename _Value,
typename _Alloc,
1846 typename _ExtractKey,
typename _Equal,
1847 typename _Hash,
typename _RangeHash,
typename _Unused,
1848 typename _RehashPolicy,
typename _Traits>
1849 template<
typename _Kt,
typename,
typename>
1851 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1852 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1853 _M_count_tr(
const _Kt& __k)
const
1856 if (
size() <= __small_size_threshold())
1858 size_type __result = 0;
1859 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1861 if (this->_M_key_equals_tr(__k, *__n))
1874 __hash_code __code = this->_M_hash_code_tr(__k);
1875 std::size_t __bkt = _M_bucket_index(__code);
1876 auto __n = _M_find_node_tr(__bkt, __k, __code);
1881 size_type __result = 1;
1883 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1891 template<
typename _Key,
typename _Value,
typename _Alloc,
1892 typename _ExtractKey,
typename _Equal,
1893 typename _Hash,
typename _RangeHash,
typename _Unused,
1894 typename _RehashPolicy,
typename _Traits>
1896 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1897 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1898 equal_range(
const key_type& __k)
1899 -> pair<iterator, iterator>
1901 auto __ite = find(__k);
1903 return { __ite, __ite };
1905 auto __beg = __ite++;
1906 if (__unique_keys::value)
1907 return { __beg, __ite };
1909 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1912 return { __beg, __ite };
1915 template<
typename _Key,
typename _Value,
typename _Alloc,
1916 typename _ExtractKey,
typename _Equal,
1917 typename _Hash,
typename _RangeHash,
typename _Unused,
1918 typename _RehashPolicy,
typename _Traits>
1920 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1921 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1922 equal_range(
const key_type& __k)
const
1923 -> pair<const_iterator, const_iterator>
1925 auto __ite = find(__k);
1927 return { __ite, __ite };
1929 auto __beg = __ite++;
1930 if (__unique_keys::value)
1931 return { __beg, __ite };
1933 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1936 return { __beg, __ite };
1939#if __cplusplus > 201703L
1940 template<
typename _Key,
typename _Value,
typename _Alloc,
1941 typename _ExtractKey,
typename _Equal,
1942 typename _Hash,
typename _RangeHash,
typename _Unused,
1943 typename _RehashPolicy,
typename _Traits>
1944 template<
typename _Kt,
typename,
typename>
1946 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1947 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1948 _M_equal_range_tr(
const _Kt& __k)
1949 -> pair<iterator, iterator>
1951 if (
size() <= __small_size_threshold())
1953 __node_ptr __n, __beg =
nullptr;
1954 for (__n = _M_begin(); __n; __n = __n->_M_next())
1956 if (this->_M_key_equals_tr(__k, *__n))
1967 return { iterator(__beg), iterator(__n) };
1970 __hash_code __code = this->_M_hash_code_tr(__k);
1971 std::size_t __bkt = _M_bucket_index(__code);
1972 auto __n = _M_find_node_tr(__bkt, __k, __code);
1973 iterator __ite(__n);
1975 return { __ite, __ite };
1977 auto __beg = __ite++;
1978 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1981 return { __beg, __ite };
1984 template<
typename _Key,
typename _Value,
typename _Alloc,
1985 typename _ExtractKey,
typename _Equal,
1986 typename _Hash,
typename _RangeHash,
typename _Unused,
1987 typename _RehashPolicy,
typename _Traits>
1988 template<
typename _Kt,
typename,
typename>
1990 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1991 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1992 _M_equal_range_tr(
const _Kt& __k)
const
1993 -> pair<const_iterator, const_iterator>
1995 if (
size() <= __small_size_threshold())
1997 __node_ptr __n, __beg =
nullptr;
1998 for (__n = _M_begin(); __n; __n = __n->_M_next())
2000 if (this->_M_key_equals_tr(__k, *__n))
2011 return { const_iterator(__beg), const_iterator(__n) };
2014 __hash_code __code = this->_M_hash_code_tr(__k);
2015 std::size_t __bkt = _M_bucket_index(__code);
2016 auto __n = _M_find_node_tr(__bkt, __k, __code);
2017 const_iterator __ite(__n);
2019 return { __ite, __ite };
2021 auto __beg = __ite++;
2022 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
2025 return { __beg, __ite };
2031 template<
typename _Key,
typename _Value,
typename _Alloc,
2032 typename _ExtractKey,
typename _Equal,
2033 typename _Hash,
typename _RangeHash,
typename _Unused,
2034 typename _RehashPolicy,
typename _Traits>
2036 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2037 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2038 _M_find_before_node(
const key_type& __k)
2041 __node_base_ptr __prev_p = &_M_before_begin;
2042 if (!__prev_p->_M_nxt)
2045 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);
2047 __p = __p->_M_next())
2049 if (this->_M_key_equals(__k, *__p))
2060 template<
typename _Key,
typename _Value,
typename _Alloc,
2061 typename _ExtractKey,
typename _Equal,
2062 typename _Hash,
typename _RangeHash,
typename _Unused,
2063 typename _RehashPolicy,
typename _Traits>
2065 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2066 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2067 _M_find_before_node(size_type __bkt,
const key_type& __k,
2068 __hash_code __code)
const
2071 __node_base_ptr __prev_p = _M_buckets[__bkt];
2075 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
2076 __p = __p->_M_next())
2078 if (this->_M_equals(__k, __code, *__p))
2081 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
2089 template<
typename _Key,
typename _Value,
typename _Alloc,
2090 typename _ExtractKey,
typename _Equal,
2091 typename _Hash,
typename _RangeHash,
typename _Unused,
2092 typename _RehashPolicy,
typename _Traits>
2093 template<
typename _Kt>
2095 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2096 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2097 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
2098 __hash_code __code)
const
2101 __node_base_ptr __prev_p = _M_buckets[__bkt];
2105 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
2106 __p = __p->_M_next())
2108 if (this->_M_equals_tr(__k, __code, *__p))
2111 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
2119 template<
typename _Key,
typename _Value,
typename _Alloc,
2120 typename _ExtractKey,
typename _Equal,
2121 typename _Hash,
typename _RangeHash,
typename _Unused,
2122 typename _RehashPolicy,
typename _Traits>
2124 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2125 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2126 _M_get_previous_node(size_type __bkt, __node_ptr __n)
2129 __node_base_ptr __prev_n = _M_buckets[__bkt];
2130 while (__prev_n->_M_nxt != __n)
2131 __prev_n = __prev_n->_M_nxt;
2135 template<
typename _Key,
typename _Value,
typename _Alloc,
2136 typename _ExtractKey,
typename _Equal,
2137 typename _Hash,
typename _RangeHash,
typename _Unused,
2138 typename _RehashPolicy,
typename _Traits>
2139 template<
typename... _Args>
2141 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2142 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2143 _M_emplace(true_type , _Args&&... __args)
2144 -> pair<iterator, bool>
2148 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2149 const size_type __size =
size();
2150 if (__size <= __small_size_threshold())
2152 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
2153 if (this->_M_key_equals(__k, *__it))
2155 return { iterator(__it),
false };
2158 __hash_code __code = this->_M_hash_code(__k);
2159 size_type __bkt = _M_bucket_index(__code);
2160 if (__size > __small_size_threshold())
2161 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2163 return { iterator(__p),
false };
2166 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2167 __node._M_node =
nullptr;
2168 return { __pos,
true };
2171 template<
typename _Key,
typename _Value,
typename _Alloc,
2172 typename _ExtractKey,
typename _Equal,
2173 typename _Hash,
typename _RangeHash,
typename _Unused,
2174 typename _RehashPolicy,
typename _Traits>
2175 template<
typename... _Args>
2177 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2178 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2179 _M_emplace(const_iterator __hint, false_type ,
2185 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2187 auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
2189 = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
2190 __node._M_node =
nullptr;
2194 template<
typename _Key,
typename _Value,
typename _Alloc,
2195 typename _ExtractKey,
typename _Equal,
2196 typename _Hash,
typename _RangeHash,
typename _Unused,
2197 typename _RehashPolicy,
typename _Traits>
2199 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2200 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2201 _M_compute_hash_code(__node_ptr __hint,
const key_type& __k)
const
2202 -> pair<__node_ptr, __hash_code>
2204 if (
size() <= __small_size_threshold())
2208 for (
auto __it = __hint; __it; __it = __it->_M_next())
2209 if (this->_M_key_equals(__k, *__it))
2210 return { __it, this->_M_hash_code(*__it) };
2213 for (
auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
2214 if (this->_M_key_equals(__k, *__it))
2215 return { __it, this->_M_hash_code(*__it) };
2220 return { __hint, this->_M_hash_code(__k) };
2223 template<
typename _Key,
typename _Value,
typename _Alloc,
2224 typename _ExtractKey,
typename _Equal,
2225 typename _Hash,
typename _RangeHash,
typename _Unused,
2226 typename _RehashPolicy,
typename _Traits>
2228 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2229 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2230 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2231 __node_ptr __node, size_type __n_elt)
2234 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2236 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2239 if (__do_rehash.
first)
2241 _M_rehash(__do_rehash.
second, true_type{});
2242 __bkt = _M_bucket_index(__code);
2245 __rehash_guard._M_guarded_obj =
nullptr;
2246 this->_M_store_code(*__node, __code);
2249 _M_insert_bucket_begin(__bkt, __node);
2251 return iterator(__node);
2254 template<
typename _Key,
typename _Value,
typename _Alloc,
2255 typename _ExtractKey,
typename _Equal,
2256 typename _Hash,
typename _RangeHash,
typename _Unused,
2257 typename _RehashPolicy,
typename _Traits>
2259 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2260 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2261 _M_insert_multi_node(__node_ptr __hint,
2262 __hash_code __code, __node_ptr __node)
2265 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2267 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2269 if (__do_rehash.
first)
2270 _M_rehash(__do_rehash.
second, false_type{});
2272 __rehash_guard._M_guarded_obj =
nullptr;
2273 this->_M_store_code(*__node, __code);
2274 const key_type& __k = _ExtractKey{}(__node->_M_v());
2275 size_type __bkt = _M_bucket_index(__code);
2279 __node_base_ptr __prev
2280 = __builtin_expect(__hint !=
nullptr,
false)
2281 && this->_M_equals(__k, __code, *__hint)
2283 : _M_find_before_node(__bkt, __k, __code);
2288 __node->_M_nxt = __prev->_M_nxt;
2289 __prev->_M_nxt = __node;
2290 if (__builtin_expect(__prev == __hint,
false))
2294 && !this->_M_equals(__k, __code, *__node->_M_next()))
2296 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2297 if (__next_bkt != __bkt)
2298 _M_buckets[__next_bkt] = __node;
2305 _M_insert_bucket_begin(__bkt, __node);
2307 return iterator(__node);
2311 template<
typename _Key,
typename _Value,
typename _Alloc,
2312 typename _ExtractKey,
typename _Equal,
2313 typename _Hash,
typename _RangeHash,
typename _Unused,
2314 typename _RehashPolicy,
typename _Traits>
2315 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
2317 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2318 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2319 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2320 const _NodeGenerator& __node_gen)
2321 -> pair<iterator, bool>
2323 const size_type __size =
size();
2324 if (__size <= __small_size_threshold())
2325 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
2326 if (this->_M_key_equals_tr(__k, *__it))
2327 return { iterator(__it),
false };
2329 __hash_code __code = this->_M_hash_code_tr(__k);
2330 size_type __bkt = _M_bucket_index(__code);
2332 if (__size > __small_size_threshold())
2333 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2334 return { iterator(__node),
false };
2336 _Scoped_node __node {
2343 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2344 __node._M_node =
nullptr;
2345 return { __pos,
true };
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>
2353 template<
typename _Arg,
typename _NodeGenerator>
2355 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2356 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2357 _M_insert(const_iterator __hint, _Arg&& __v,
2358 const _NodeGenerator& __node_gen,
2366 auto __res = this->_M_compute_hash_code(
2367 __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v()));
2370 = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
2371 __node._M_node =
nullptr;
2375 template<
typename _Key,
typename _Value,
typename _Alloc,
2376 typename _ExtractKey,
typename _Equal,
2377 typename _Hash,
typename _RangeHash,
typename _Unused,
2378 typename _RehashPolicy,
typename _Traits>
2380 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2381 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2382 erase(const_iterator __it)
2385 __node_ptr __n = __it._M_cur;
2386 std::size_t __bkt = _M_bucket_index(*__n);
2391 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2392 return _M_erase(__bkt, __prev_n, __n);
2395 template<
typename _Key,
typename _Value,
typename _Alloc,
2396 typename _ExtractKey,
typename _Equal,
2397 typename _Hash,
typename _RangeHash,
typename _Unused,
2398 typename _RehashPolicy,
typename _Traits>
2400 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2401 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2402 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2405 if (__prev_n == _M_buckets[__bkt])
2406 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2407 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2408 else if (__n->_M_nxt)
2410 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2411 if (__next_bkt != __bkt)
2412 _M_buckets[__next_bkt] = __prev_n;
2415 __prev_n->_M_nxt = __n->_M_nxt;
2416 iterator __result(__n->_M_next());
2417 this->_M_deallocate_node(__n);
2423 template<
typename _Key,
typename _Value,
typename _Alloc,
2424 typename _ExtractKey,
typename _Equal,
2425 typename _Hash,
typename _RangeHash,
typename _Unused,
2426 typename _RehashPolicy,
typename _Traits>
2428 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2429 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2430 _M_erase(true_type ,
const key_type& __k)
2433 __node_base_ptr __prev_n;
2436 if (
size() <= __small_size_threshold())
2438 __prev_n = _M_find_before_node(__k);
2443 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2444 __bkt = _M_bucket_index(*__n);
2448 __hash_code __code = this->_M_hash_code(__k);
2449 __bkt = _M_bucket_index(__code);
2452 __prev_n = _M_find_before_node(__bkt, __k, __code);
2457 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2460 _M_erase(__bkt, __prev_n, __n);
2464 template<
typename _Key,
typename _Value,
typename _Alloc,
2465 typename _ExtractKey,
typename _Equal,
2466 typename _Hash,
typename _RangeHash,
typename _Unused,
2467 typename _RehashPolicy,
typename _Traits>
2469 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2470 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2471 _M_erase(false_type ,
const key_type& __k)
2475 __node_base_ptr __prev_n;
2477 if (
size() <= __small_size_threshold())
2479 __prev_n = _M_find_before_node(__k);
2484 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2485 __bkt = _M_bucket_index(*__n);
2489 __hash_code __code = this->_M_hash_code(__k);
2490 __bkt = _M_bucket_index(__code);
2493 __prev_n = _M_find_before_node(__bkt, __k, __code);
2497 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2506 __node_ptr __n_last = __n->_M_next();
2507 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2508 __n_last = __n_last->_M_next();
2510 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2513 size_type __result = 0;
2516 __node_ptr __p = __n->_M_next();
2517 this->_M_deallocate_node(__n);
2521 while (__n != __n_last);
2523 _M_element_count -= __result;
2524 if (__prev_n == _M_buckets[__bkt])
2525 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2526 else if (__n_last_bkt != __bkt)
2527 _M_buckets[__n_last_bkt] = __prev_n;
2528 __prev_n->_M_nxt = __n_last;
2532 template<
typename _Key,
typename _Value,
typename _Alloc,
2533 typename _ExtractKey,
typename _Equal,
2534 typename _Hash,
typename _RangeHash,
typename _Unused,
2535 typename _RehashPolicy,
typename _Traits>
2537 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2538 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2539 erase(const_iterator __first, const_iterator __last)
2542 __node_ptr __n = __first._M_cur;
2543 __node_ptr __last_n = __last._M_cur;
2544 if (__n == __last_n)
2545 return iterator(__n);
2547 std::size_t __bkt = _M_bucket_index(*__n);
2549 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2550 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2551 std::size_t __n_bkt = __bkt;
2556 __node_ptr __tmp = __n;
2557 __n = __n->_M_next();
2558 this->_M_deallocate_node(__tmp);
2562 __n_bkt = _M_bucket_index(*__n);
2564 while (__n != __last_n && __n_bkt == __bkt);
2565 if (__is_bucket_begin)
2566 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2567 if (__n == __last_n)
2569 __is_bucket_begin =
true;
2573 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2574 _M_buckets[__n_bkt] = __prev_n;
2575 __prev_n->_M_nxt = __n;
2576 return iterator(__n);
2579 template<
typename _Key,
typename _Value,
typename _Alloc,
2580 typename _ExtractKey,
typename _Equal,
2581 typename _Hash,
typename _RangeHash,
typename _Unused,
2582 typename _RehashPolicy,
typename _Traits>
2584 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2585 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2588 this->_M_deallocate_nodes(_M_begin());
2589 __builtin_memset(_M_buckets, 0,
2590 _M_bucket_count *
sizeof(__node_base_ptr));
2591 _M_element_count = 0;
2592 _M_before_begin._M_nxt =
nullptr;
2595 template<
typename _Key,
typename _Value,
typename _Alloc,
2596 typename _ExtractKey,
typename _Equal,
2597 typename _Hash,
typename _RangeHash,
typename _Unused,
2598 typename _RehashPolicy,
typename _Traits>
2600 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2601 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2602 rehash(size_type __bkt_count)
2604 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2606 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2608 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2610 if (__bkt_count != _M_bucket_count)
2612 _M_rehash(__bkt_count, __unique_keys{});
2613 __rehash_guard._M_guarded_obj =
nullptr;
2618 template<
typename _Key,
typename _Value,
typename _Alloc,
2619 typename _ExtractKey,
typename _Equal,
2620 typename _Hash,
typename _RangeHash,
typename _Unused,
2621 typename _RehashPolicy,
typename _Traits>
2623 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2624 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2625 _M_rehash(size_type __bkt_count, true_type )
2627 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2628 __node_ptr __p = _M_begin();
2629 _M_before_begin._M_nxt =
nullptr;
2630 std::size_t __bbegin_bkt = 0;
2633 __node_ptr __next = __p->_M_next();
2635 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2636 if (!__new_buckets[__bkt])
2638 __p->_M_nxt = _M_before_begin._M_nxt;
2639 _M_before_begin._M_nxt = __p;
2640 __new_buckets[__bkt] = &_M_before_begin;
2642 __new_buckets[__bbegin_bkt] = __p;
2643 __bbegin_bkt = __bkt;
2647 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2648 __new_buckets[__bkt]->_M_nxt = __p;
2654 _M_deallocate_buckets();
2655 _M_bucket_count = __bkt_count;
2656 _M_buckets = __new_buckets;
2661 template<
typename _Key,
typename _Value,
typename _Alloc,
2662 typename _ExtractKey,
typename _Equal,
2663 typename _Hash,
typename _RangeHash,
typename _Unused,
2664 typename _RehashPolicy,
typename _Traits>
2666 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2667 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2668 _M_rehash(size_type __bkt_count, false_type )
2670 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2671 __node_ptr __p = _M_begin();
2672 _M_before_begin._M_nxt =
nullptr;
2673 std::size_t __bbegin_bkt = 0;
2674 std::size_t __prev_bkt = 0;
2675 __node_ptr __prev_p =
nullptr;
2676 bool __check_bucket =
false;
2680 __node_ptr __next = __p->_M_next();
2682 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2684 if (__prev_p && __prev_bkt == __bkt)
2689 __p->_M_nxt = __prev_p->_M_nxt;
2690 __prev_p->_M_nxt = __p;
2697 __check_bucket =
true;
2705 if (__prev_p->_M_nxt)
2707 std::size_t __next_bkt
2708 = __hash_code_base::_M_bucket_index(
2709 *__prev_p->_M_next(), __bkt_count);
2710 if (__next_bkt != __prev_bkt)
2711 __new_buckets[__next_bkt] = __prev_p;
2713 __check_bucket =
false;
2716 if (!__new_buckets[__bkt])
2718 __p->_M_nxt = _M_before_begin._M_nxt;
2719 _M_before_begin._M_nxt = __p;
2720 __new_buckets[__bkt] = &_M_before_begin;
2722 __new_buckets[__bbegin_bkt] = __p;
2723 __bbegin_bkt = __bkt;
2727 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2728 __new_buckets[__bkt]->_M_nxt = __p;
2736 if (__check_bucket && __prev_p->_M_nxt)
2738 std::size_t __next_bkt
2739 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2741 if (__next_bkt != __prev_bkt)
2742 __new_buckets[__next_bkt] = __prev_p;
2745 _M_deallocate_buckets();
2746 _M_bucket_count = __bkt_count;
2747 _M_buckets = __new_buckets;
2750#if __cplusplus > 201402L
2751 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2754#if __cpp_deduction_guides >= 201606
2756 template<
typename _Hash>
2757 using _RequireNotAllocatorOrIntegral
2758 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2762_GLIBCXX_END_NAMESPACE_VERSION
auto declval() noexcept -> decltype(__declval< _Tp >(0))
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
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.
_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.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.