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(
344 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
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(
352 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
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;
892 _M_insert_unique_node(size_type __bkt, __hash_code,
893 __node_ptr __n, size_type __n_elt = 1);
898 _M_insert_multi_node(__node_ptr __hint,
899 __hash_code __code, __node_ptr __n);
901 template<
typename... _Args>
903 _M_emplace(true_type __uks, _Args&&... __args);
905 template<
typename... _Args>
907 _M_emplace(false_type __uks, _Args&&... __args)
908 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
911 template<
typename... _Args>
913 _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
914 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
916 template<
typename... _Args>
918 _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
920 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
922 _M_insert_unique(_Kt&&, _Arg&&,
const _NodeGenerator&);
924 template<
typename _Kt>
925 static __conditional_t<
926 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
927 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
929 _S_forward_key(_Kt&& __k)
930 {
return std::forward<_Kt>(__k); }
932 static const key_type&
933 _S_forward_key(
const key_type& __k)
937 _S_forward_key(key_type&& __k)
940 template<
typename _Arg,
typename _NodeGenerator>
942 _M_insert_unique_aux(_Arg&& __arg,
const _NodeGenerator& __node_gen)
944 return _M_insert_unique(
945 _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
946 std::forward<_Arg>(__arg), __node_gen);
949 template<
typename _Arg,
typename _NodeGenerator>
951 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
955 = __detail::_ConvertToValueType<_ExtractKey, value_type>;
956 return _M_insert_unique_aux(
957 __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
960 template<
typename _Arg,
typename _NodeGenerator>
962 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
966 = __detail::_ConvertToValueType<_ExtractKey, value_type>;
967 return _M_insert(
cend(),
968 __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
972 template<
typename _Arg,
typename _NodeGenerator>
974 _M_insert(const_iterator, _Arg&& __arg,
975 const _NodeGenerator& __node_gen, true_type __uks)
978 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
982 template<
typename _Arg,
typename _NodeGenerator>
984 _M_insert(const_iterator, _Arg&&,
985 const _NodeGenerator&, false_type __uks);
988 _M_erase(true_type __uks,
const key_type&);
991 _M_erase(false_type __uks,
const key_type&);
994 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
998 template<
typename... _Args>
1000 emplace(_Args&&... __args)
1001 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
1003 template<
typename... _Args>
1005 emplace_hint(const_iterator __hint, _Args&&... __args)
1007 return _M_emplace(__hint, __unique_keys{},
1008 std::forward<_Args>(__args)...);
1015 erase(const_iterator);
1019 erase(iterator __it)
1020 {
return erase(const_iterator(__it)); }
1023 erase(
const key_type& __k)
1024 {
return _M_erase(__unique_keys{}, __k); }
1027 erase(const_iterator, const_iterator);
1034 void rehash(size_type __bkt_count);
1039#if __cplusplus > 201402L
1042 _M_reinsert_node(node_type&& __nh)
1044 insert_return_type __ret;
1046 __ret.position =
end();
1049 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1051 __node_ptr __n =
nullptr;
1052 const key_type& __k = __nh._M_key();
1053 const size_type __size =
size();
1054 if (__size <= __small_size_threshold())
1056 for (__n = _M_begin(); __n; __n = __n->_M_next())
1057 if (this->_M_key_equals(__k, *__n))
1065 __code = this->_M_hash_code(__k);
1066 __bkt = _M_bucket_index(__code);
1067 if (__size > __small_size_threshold())
1068 __n = _M_find_node(__bkt, __k, __code);
1074 __ret.position = iterator(__n);
1075 __ret.inserted =
false;
1080 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1081 __nh._M_ptr =
nullptr;
1082 __ret.inserted =
true;
1090 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1095 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1097 const key_type& __k = __nh._M_key();
1098 auto __code = this->_M_hash_code(__k);
1100 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1101 __nh._M_ptr =
nullptr;
1107 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1109 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1110 if (__prev_n == _M_buckets[__bkt])
1111 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1112 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1113 else if (__n->_M_nxt)
1115 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1116 if (__next_bkt != __bkt)
1117 _M_buckets[__next_bkt] = __prev_n;
1120 __prev_n->_M_nxt = __n->_M_nxt;
1121 __n->_M_nxt =
nullptr;
1123 return { __n, this->_M_node_allocator() };
1128 template<
typename _H2>
1130 _M_src_hash_code(
const _H2&,
const key_type& __k,
1131 const __node_value_type& __src_n)
const
1133 if constexpr (std::is_same_v<_H2, _Hash>)
1134 if constexpr (std::is_empty_v<_Hash>)
1135 return this->_M_hash_code(__src_n);
1137 return this->_M_hash_code(__k);
1143 extract(const_iterator __pos)
1145 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1146 return _M_extract_node(__bkt,
1147 _M_get_previous_node(__bkt, __pos._M_cur));
1152 extract(
const _Key& __k)
1155 __hash_code __code = this->_M_hash_code(__k);
1156 std::size_t __bkt = _M_bucket_index(__code);
1157 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1158 __nh = _M_extract_node(__bkt, __prev_node);
1163 template<
typename _Compatible_Hashtable>
1165 _M_merge_unique(_Compatible_Hashtable& __src)
1167 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1168 node_type>,
"Node types are compatible");
1169 __glibcxx_assert(get_allocator() == __src.get_allocator());
1171 auto __n_elt = __src.size();
1172 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1175 const size_type __size =
size();
1176 const key_type& __k = _ExtractKey{}(*__pos);
1177 if (__size <= __small_size_threshold())
1179 bool __found =
false;
1180 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1181 if (this->_M_key_equals(__k, *__n))
1196 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1197 size_type __bkt = _M_bucket_index(__code);
1198 if (__size <= __small_size_threshold()
1199 || _M_find_node(__bkt, __k, __code) ==
nullptr)
1201 auto __nh = __src.extract(__pos);
1202 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1203 __nh._M_ptr =
nullptr;
1206 else if (__n_elt != 1)
1212 template<
typename _Compatible_Hashtable>
1214 _M_merge_multi(_Compatible_Hashtable& __src)
1216 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1217 node_type>,
"Node types are compatible");
1218 __glibcxx_assert(get_allocator() == __src.get_allocator());
1220 __node_ptr __hint =
nullptr;
1221 this->reserve(
size() + __src.size());
1222 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1225 const key_type& __k = _ExtractKey{}(*__pos);
1227 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1228 auto __nh = __src.extract(__pos);
1229 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1230 __nh._M_ptr =
nullptr;
1237 void _M_rehash(size_type __bkt_count, true_type __uks);
1240 void _M_rehash(size_type __bkt_count, false_type __uks);
1244 template<
typename _Key,
typename _Value,
typename _Alloc,
1245 typename _ExtractKey,
typename _Equal,
1246 typename _Hash,
typename _RangeHash,
typename _Unused,
1247 typename _RehashPolicy,
typename _Traits>
1248 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1249 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1250 _Hashtable(size_type __bkt_count_hint,
1251 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1252 : _Hashtable(__h, __eq, __a)
1254 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1255 if (__bkt_count > _M_bucket_count)
1257 _M_buckets = _M_allocate_buckets(__bkt_count);
1258 _M_bucket_count = __bkt_count;
1262 template<
typename _Key,
typename _Value,
typename _Alloc,
1263 typename _ExtractKey,
typename _Equal,
1264 typename _Hash,
typename _RangeHash,
typename _Unused,
1265 typename _RehashPolicy,
typename _Traits>
1266 template<
typename _InputIterator>
1267 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1268 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1269 _Hashtable(_InputIterator __f, _InputIterator __l,
1270 size_type __bkt_count_hint,
1271 const _Hash& __h,
const _Equal& __eq,
1272 const allocator_type& __a, true_type )
1273 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1274 { this->insert(__f, __l); }
1276 template<
typename _Key,
typename _Value,
typename _Alloc,
1277 typename _ExtractKey,
typename _Equal,
1278 typename _Hash,
typename _RangeHash,
typename _Unused,
1279 typename _RehashPolicy,
typename _Traits>
1280 template<
typename _InputIterator>
1281 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1282 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1283 _Hashtable(_InputIterator __f, _InputIterator __l,
1284 size_type __bkt_count_hint,
1285 const _Hash& __h,
const _Equal& __eq,
1286 const allocator_type& __a, false_type __uks)
1287 : _Hashtable(__h, __eq, __a)
1289 auto __nb_elems = __detail::__distance_fw(__f, __l);
1291 _M_rehash_policy._M_next_bkt(
1292 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1295 if (__bkt_count > _M_bucket_count)
1297 _M_buckets = _M_allocate_buckets(__bkt_count);
1298 _M_bucket_count = __bkt_count;
1301 __alloc_node_gen_t __node_gen(*
this);
1302 for (; __f != __l; ++__f)
1303 _M_insert(*__f, __node_gen, __uks);
1306 template<
typename _Key,
typename _Value,
typename _Alloc,
1307 typename _ExtractKey,
typename _Equal,
1308 typename _Hash,
typename _RangeHash,
typename _Unused,
1309 typename _RehashPolicy,
typename _Traits>
1311 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1312 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1313 operator=(
const _Hashtable& __ht)
1319 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1321 auto& __this_alloc = this->_M_node_allocator();
1322 auto& __that_alloc = __ht._M_node_allocator();
1323 if (!__node_alloc_traits::_S_always_equal()
1324 && __this_alloc != __that_alloc)
1327 this->_M_deallocate_nodes(_M_begin());
1328 _M_before_begin._M_nxt =
nullptr;
1329 _M_deallocate_buckets();
1330 _M_buckets =
nullptr;
1331 std::__alloc_on_copy(__this_alloc, __that_alloc);
1332 __hashtable_base::operator=(__ht);
1333 _M_bucket_count = __ht._M_bucket_count;
1334 _M_element_count = __ht._M_element_count;
1335 _M_rehash_policy = __ht._M_rehash_policy;
1336 __alloc_node_gen_t __alloc_node_gen(*
this);
1339 _M_assign(__ht, __alloc_node_gen);
1346 __throw_exception_again;
1350 std::__alloc_on_copy(__this_alloc, __that_alloc);
1354 _M_assign_elements(__ht);
1358 template<
typename _Key,
typename _Value,
typename _Alloc,
1359 typename _ExtractKey,
typename _Equal,
1360 typename _Hash,
typename _RangeHash,
typename _Unused,
1361 typename _RehashPolicy,
typename _Traits>
1362 template<
typename _Ht>
1364 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1365 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1366 _M_assign_elements(_Ht&& __ht)
1368 __buckets_ptr __former_buckets =
nullptr;
1369 std::size_t __former_bucket_count = _M_bucket_count;
1370 __rehash_guard_t __rehash_guard(_M_rehash_policy);
1372 if (_M_bucket_count != __ht._M_bucket_count)
1374 __former_buckets = _M_buckets;
1375 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1376 _M_bucket_count = __ht._M_bucket_count;
1379 __builtin_memset(_M_buckets, 0,
1380 _M_bucket_count *
sizeof(__node_base_ptr));
1384 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1385 _M_element_count = __ht._M_element_count;
1386 _M_rehash_policy = __ht._M_rehash_policy;
1387 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1388 _M_before_begin._M_nxt =
nullptr;
1389 _M_assign(std::forward<_Ht>(__ht), __roan);
1390 if (__former_buckets)
1391 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1392 __rehash_guard._M_guarded_obj =
nullptr;
1396 if (__former_buckets)
1399 _M_deallocate_buckets();
1400 _M_buckets = __former_buckets;
1401 _M_bucket_count = __former_bucket_count;
1403 __builtin_memset(_M_buckets, 0,
1404 _M_bucket_count *
sizeof(__node_base_ptr));
1405 __throw_exception_again;
1409 template<
typename _Key,
typename _Value,
typename _Alloc,
1410 typename _ExtractKey,
typename _Equal,
1411 typename _Hash,
typename _RangeHash,
typename _Unused,
1412 typename _RehashPolicy,
typename _Traits>
1413 template<
typename _Ht,
typename _NodeGenerator>
1415 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1416 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1417 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1419 __buckets_ptr __buckets =
nullptr;
1421 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1425 if (!__ht._M_before_begin._M_nxt)
1430 __node_ptr __ht_n = __ht._M_begin();
1432 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1433 this->_M_copy_code(*__this_n, *__ht_n);
1434 _M_update_bbegin(__this_n);
1437 __node_ptr __prev_n = __this_n;
1438 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1440 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1441 __prev_n->_M_nxt = __this_n;
1442 this->_M_copy_code(*__this_n, *__ht_n);
1443 size_type __bkt = _M_bucket_index(*__this_n);
1444 if (!_M_buckets[__bkt])
1445 _M_buckets[__bkt] = __prev_n;
1446 __prev_n = __this_n;
1453 _M_deallocate_buckets();
1454 __throw_exception_again;
1458 template<
typename _Key,
typename _Value,
typename _Alloc,
1459 typename _ExtractKey,
typename _Equal,
1460 typename _Hash,
typename _RangeHash,
typename _Unused,
1461 typename _RehashPolicy,
typename _Traits>
1463 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1464 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1467 _M_rehash_policy._M_reset();
1468 _M_bucket_count = 1;
1469 _M_single_bucket =
nullptr;
1470 _M_buckets = &_M_single_bucket;
1471 _M_before_begin._M_nxt =
nullptr;
1472 _M_element_count = 0;
1475 template<
typename _Key,
typename _Value,
typename _Alloc,
1476 typename _ExtractKey,
typename _Equal,
1477 typename _Hash,
typename _RangeHash,
typename _Unused,
1478 typename _RehashPolicy,
typename _Traits>
1480 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1481 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1482 _M_move_assign(_Hashtable&& __ht, true_type)
1487 this->_M_deallocate_nodes(_M_begin());
1488 _M_deallocate_buckets();
1489 __hashtable_base::operator=(
std::move(__ht));
1490 _M_rehash_policy = __ht._M_rehash_policy;
1491 if (!__ht._M_uses_single_bucket())
1492 _M_buckets = __ht._M_buckets;
1495 _M_buckets = &_M_single_bucket;
1496 _M_single_bucket = __ht._M_single_bucket;
1499 _M_bucket_count = __ht._M_bucket_count;
1500 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1501 _M_element_count = __ht._M_element_count;
1502 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1509 template<
typename _Key,
typename _Value,
typename _Alloc,
1510 typename _ExtractKey,
typename _Equal,
1511 typename _Hash,
typename _RangeHash,
typename _Unused,
1512 typename _RehashPolicy,
typename _Traits>
1514 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1515 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1516 _M_move_assign(_Hashtable&& __ht, false_type)
1518 if (__ht._M_node_allocator() == this->_M_node_allocator())
1519 _M_move_assign(
std::move(__ht), true_type{});
1528 template<
typename _Key,
typename _Value,
typename _Alloc,
1529 typename _ExtractKey,
typename _Equal,
1530 typename _Hash,
typename _RangeHash,
typename _Unused,
1531 typename _RehashPolicy,
typename _Traits>
1532 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1533 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1534 _Hashtable(
const _Hashtable& __ht)
1535 : __hashtable_base(__ht),
1537 __rehash_base(__ht),
1539 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1540 __enable_default_ctor(__ht),
1541 _M_buckets(nullptr),
1542 _M_bucket_count(__ht._M_bucket_count),
1543 _M_element_count(__ht._M_element_count),
1544 _M_rehash_policy(__ht._M_rehash_policy)
1546 __alloc_node_gen_t __alloc_node_gen(*
this);
1547 _M_assign(__ht, __alloc_node_gen);
1550 template<
typename _Key,
typename _Value,
typename _Alloc,
1551 typename _ExtractKey,
typename _Equal,
1552 typename _Hash,
typename _RangeHash,
typename _Unused,
1553 typename _RehashPolicy,
typename _Traits>
1554 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1555 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1556 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1558 noexcept(_S_nothrow_move())
1559 : __hashtable_base(__ht),
1561 __rehash_base(__ht),
1562 __hashtable_alloc(
std::
move(__a)),
1563 __enable_default_ctor(__ht),
1564 _M_buckets(__ht._M_buckets),
1565 _M_bucket_count(__ht._M_bucket_count),
1566 _M_before_begin(__ht._M_before_begin._M_nxt),
1567 _M_element_count(__ht._M_element_count),
1568 _M_rehash_policy(__ht._M_rehash_policy)
1571 if (__ht._M_uses_single_bucket())
1573 _M_buckets = &_M_single_bucket;
1574 _M_single_bucket = __ht._M_single_bucket;
1583 template<
typename _Key,
typename _Value,
typename _Alloc,
1584 typename _ExtractKey,
typename _Equal,
1585 typename _Hash,
typename _RangeHash,
typename _Unused,
1586 typename _RehashPolicy,
typename _Traits>
1587 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1588 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1589 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1590 : __hashtable_base(__ht),
1592 __rehash_base(__ht),
1593 __hashtable_alloc(__node_alloc_type(__a)),
1594 __enable_default_ctor(__ht),
1596 _M_bucket_count(__ht._M_bucket_count),
1597 _M_element_count(__ht._M_element_count),
1598 _M_rehash_policy(__ht._M_rehash_policy)
1600 __alloc_node_gen_t __alloc_node_gen(*
this);
1601 _M_assign(__ht, __alloc_node_gen);
1604 template<
typename _Key,
typename _Value,
typename _Alloc,
1605 typename _ExtractKey,
typename _Equal,
1606 typename _Hash,
typename _RangeHash,
typename _Unused,
1607 typename _RehashPolicy,
typename _Traits>
1608 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1609 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1610 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1612 : __hashtable_base(__ht),
1614 __rehash_base(__ht),
1615 __hashtable_alloc(
std::
move(__a)),
1616 __enable_default_ctor(__ht),
1617 _M_buckets(nullptr),
1618 _M_bucket_count(__ht._M_bucket_count),
1619 _M_element_count(__ht._M_element_count),
1620 _M_rehash_policy(__ht._M_rehash_policy)
1622 if (__ht._M_node_allocator() == this->_M_node_allocator())
1624 if (__ht._M_uses_single_bucket())
1626 _M_buckets = &_M_single_bucket;
1627 _M_single_bucket = __ht._M_single_bucket;
1630 _M_buckets = __ht._M_buckets;
1634 _M_update_bbegin(__ht._M_begin());
1640 __alloc_node_gen_t __alloc_gen(*
this);
1642 using _Fwd_Ht = __conditional_t<
1643 __move_if_noexcept_cond<value_type>::value,
1644 const _Hashtable&, _Hashtable&&>;
1645 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
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>
1654 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1655 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1656 ~_Hashtable() noexcept
1661 static_assert(
noexcept(declval<const __hash_code_base_access&>()
1662 ._M_bucket_index(declval<const __node_value_type&>(),
1664 "Cache the hash code or qualify your functors involved"
1665 " in hash code and bucket index computation with noexcept");
1668 _M_deallocate_buckets();
1671 template<
typename _Key,
typename _Value,
typename _Alloc,
1672 typename _ExtractKey,
typename _Equal,
1673 typename _Hash,
typename _RangeHash,
typename _Unused,
1674 typename _RehashPolicy,
typename _Traits>
1676 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1677 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1678 swap(_Hashtable& __x)
1679 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1680 __is_nothrow_swappable<_Equal>>::value)
1687 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1688 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1691 if (this->_M_uses_single_bucket())
1693 if (!__x._M_uses_single_bucket())
1695 _M_buckets = __x._M_buckets;
1696 __x._M_buckets = &__x._M_single_bucket;
1699 else if (__x._M_uses_single_bucket())
1701 __x._M_buckets = _M_buckets;
1702 _M_buckets = &_M_single_bucket;
1705 std::swap(_M_buckets, __x._M_buckets);
1707 std::swap(_M_bucket_count, __x._M_bucket_count);
1708 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1709 std::swap(_M_element_count, __x._M_element_count);
1710 std::swap(_M_single_bucket, __x._M_single_bucket);
1715 __x._M_update_bbegin();
1718 template<
typename _Key,
typename _Value,
typename _Alloc,
1719 typename _ExtractKey,
typename _Equal,
1720 typename _Hash,
typename _RangeHash,
typename _Unused,
1721 typename _RehashPolicy,
typename _Traits>
1723 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1724 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1725 find(
const key_type& __k)
1728 if (
size() <= __small_size_threshold())
1730 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
1731 if (this->_M_key_equals(__k, *__it))
1732 return iterator(__it);
1736 __hash_code __code = this->_M_hash_code(__k);
1737 std::size_t __bkt = _M_bucket_index(__code);
1738 return iterator(_M_find_node(__bkt, __k, __code));
1741 template<
typename _Key,
typename _Value,
typename _Alloc,
1742 typename _ExtractKey,
typename _Equal,
1743 typename _Hash,
typename _RangeHash,
typename _Unused,
1744 typename _RehashPolicy,
typename _Traits>
1746 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1747 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1748 find(
const key_type& __k)
const
1751 if (
size() <= __small_size_threshold())
1753 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
1754 if (this->_M_key_equals(__k, *__it))
1755 return const_iterator(__it);
1759 __hash_code __code = this->_M_hash_code(__k);
1760 std::size_t __bkt = _M_bucket_index(__code);
1761 return const_iterator(_M_find_node(__bkt, __k, __code));
1764#if __cplusplus > 201703L
1765 template<
typename _Key,
typename _Value,
typename _Alloc,
1766 typename _ExtractKey,
typename _Equal,
1767 typename _Hash,
typename _RangeHash,
typename _Unused,
1768 typename _RehashPolicy,
typename _Traits>
1769 template<
typename _Kt,
typename,
typename>
1771 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1772 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1773 _M_find_tr(
const _Kt& __k)
1776 if (
size() <= __small_size_threshold())
1778 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1779 if (this->_M_key_equals_tr(__k, *__n))
1780 return iterator(__n);
1784 __hash_code __code = this->_M_hash_code_tr(__k);
1785 std::size_t __bkt = _M_bucket_index(__code);
1786 return iterator(_M_find_node_tr(__bkt, __k, __code));
1789 template<
typename _Key,
typename _Value,
typename _Alloc,
1790 typename _ExtractKey,
typename _Equal,
1791 typename _Hash,
typename _RangeHash,
typename _Unused,
1792 typename _RehashPolicy,
typename _Traits>
1793 template<
typename _Kt,
typename,
typename>
1795 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1796 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1797 _M_find_tr(
const _Kt& __k)
const
1800 if (
size() <= __small_size_threshold())
1802 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1803 if (this->_M_key_equals_tr(__k, *__n))
1804 return const_iterator(__n);
1808 __hash_code __code = this->_M_hash_code_tr(__k);
1809 std::size_t __bkt = _M_bucket_index(__code);
1810 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1814 template<
typename _Key,
typename _Value,
typename _Alloc,
1815 typename _ExtractKey,
typename _Equal,
1816 typename _Hash,
typename _RangeHash,
typename _Unused,
1817 typename _RehashPolicy,
typename _Traits>
1819 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1820 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1821 count(
const key_type& __k)
const
1824 auto __it = find(__k);
1828 if (__unique_keys::value)
1831 size_type __result = 1;
1832 for (
auto __ref = __it++;
1833 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1840#if __cplusplus > 201703L
1841 template<
typename _Key,
typename _Value,
typename _Alloc,
1842 typename _ExtractKey,
typename _Equal,
1843 typename _Hash,
typename _RangeHash,
typename _Unused,
1844 typename _RehashPolicy,
typename _Traits>
1845 template<
typename _Kt,
typename,
typename>
1847 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1848 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1849 _M_count_tr(
const _Kt& __k)
const
1852 if (
size() <= __small_size_threshold())
1854 size_type __result = 0;
1855 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1857 if (this->_M_key_equals_tr(__k, *__n))
1870 __hash_code __code = this->_M_hash_code_tr(__k);
1871 std::size_t __bkt = _M_bucket_index(__code);
1872 auto __n = _M_find_node_tr(__bkt, __k, __code);
1877 size_type __result = 1;
1879 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1887 template<
typename _Key,
typename _Value,
typename _Alloc,
1888 typename _ExtractKey,
typename _Equal,
1889 typename _Hash,
typename _RangeHash,
typename _Unused,
1890 typename _RehashPolicy,
typename _Traits>
1892 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1893 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1894 equal_range(
const key_type& __k)
1895 -> pair<iterator, iterator>
1897 auto __ite = find(__k);
1899 return { __ite, __ite };
1901 auto __beg = __ite++;
1902 if (__unique_keys::value)
1903 return { __beg, __ite };
1905 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1908 return { __beg, __ite };
1911 template<
typename _Key,
typename _Value,
typename _Alloc,
1912 typename _ExtractKey,
typename _Equal,
1913 typename _Hash,
typename _RangeHash,
typename _Unused,
1914 typename _RehashPolicy,
typename _Traits>
1916 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1917 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1918 equal_range(
const key_type& __k)
const
1919 -> pair<const_iterator, const_iterator>
1921 auto __ite = find(__k);
1923 return { __ite, __ite };
1925 auto __beg = __ite++;
1926 if (__unique_keys::value)
1927 return { __beg, __ite };
1929 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1932 return { __beg, __ite };
1935#if __cplusplus > 201703L
1936 template<
typename _Key,
typename _Value,
typename _Alloc,
1937 typename _ExtractKey,
typename _Equal,
1938 typename _Hash,
typename _RangeHash,
typename _Unused,
1939 typename _RehashPolicy,
typename _Traits>
1940 template<
typename _Kt,
typename,
typename>
1942 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1943 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1944 _M_equal_range_tr(
const _Kt& __k)
1945 -> pair<iterator, iterator>
1947 if (
size() <= __small_size_threshold())
1949 __node_ptr __n, __beg =
nullptr;
1950 for (__n = _M_begin(); __n; __n = __n->_M_next())
1952 if (this->_M_key_equals_tr(__k, *__n))
1963 return { iterator(__beg), iterator(__n) };
1966 __hash_code __code = this->_M_hash_code_tr(__k);
1967 std::size_t __bkt = _M_bucket_index(__code);
1968 auto __n = _M_find_node_tr(__bkt, __k, __code);
1969 iterator __ite(__n);
1971 return { __ite, __ite };
1973 auto __beg = __ite++;
1974 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1977 return { __beg, __ite };
1980 template<
typename _Key,
typename _Value,
typename _Alloc,
1981 typename _ExtractKey,
typename _Equal,
1982 typename _Hash,
typename _RangeHash,
typename _Unused,
1983 typename _RehashPolicy,
typename _Traits>
1984 template<
typename _Kt,
typename,
typename>
1986 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1987 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1988 _M_equal_range_tr(
const _Kt& __k)
const
1989 -> pair<const_iterator, const_iterator>
1991 if (
size() <= __small_size_threshold())
1993 __node_ptr __n, __beg =
nullptr;
1994 for (__n = _M_begin(); __n; __n = __n->_M_next())
1996 if (this->_M_key_equals_tr(__k, *__n))
2007 return { const_iterator(__beg), const_iterator(__n) };
2010 __hash_code __code = this->_M_hash_code_tr(__k);
2011 std::size_t __bkt = _M_bucket_index(__code);
2012 auto __n = _M_find_node_tr(__bkt, __k, __code);
2013 const_iterator __ite(__n);
2015 return { __ite, __ite };
2017 auto __beg = __ite++;
2018 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
2021 return { __beg, __ite };
2027 template<
typename _Key,
typename _Value,
typename _Alloc,
2028 typename _ExtractKey,
typename _Equal,
2029 typename _Hash,
typename _RangeHash,
typename _Unused,
2030 typename _RehashPolicy,
typename _Traits>
2032 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2033 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2034 _M_find_before_node(
const key_type& __k)
2037 __node_base_ptr __prev_p = &_M_before_begin;
2038 if (!__prev_p->_M_nxt)
2041 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);
2043 __p = __p->_M_next())
2045 if (this->_M_key_equals(__k, *__p))
2056 template<
typename _Key,
typename _Value,
typename _Alloc,
2057 typename _ExtractKey,
typename _Equal,
2058 typename _Hash,
typename _RangeHash,
typename _Unused,
2059 typename _RehashPolicy,
typename _Traits>
2061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2062 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2063 _M_find_before_node(size_type __bkt,
const key_type& __k,
2064 __hash_code __code)
const
2067 __node_base_ptr __prev_p = _M_buckets[__bkt];
2071 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
2072 __p = __p->_M_next())
2074 if (this->_M_equals(__k, __code, *__p))
2077 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
2085 template<
typename _Key,
typename _Value,
typename _Alloc,
2086 typename _ExtractKey,
typename _Equal,
2087 typename _Hash,
typename _RangeHash,
typename _Unused,
2088 typename _RehashPolicy,
typename _Traits>
2089 template<
typename _Kt>
2091 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2092 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2093 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
2094 __hash_code __code)
const
2097 __node_base_ptr __prev_p = _M_buckets[__bkt];
2101 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
2102 __p = __p->_M_next())
2104 if (this->_M_equals_tr(__k, __code, *__p))
2107 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
2115 template<
typename _Key,
typename _Value,
typename _Alloc,
2116 typename _ExtractKey,
typename _Equal,
2117 typename _Hash,
typename _RangeHash,
typename _Unused,
2118 typename _RehashPolicy,
typename _Traits>
2120 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2121 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2122 _M_get_previous_node(size_type __bkt, __node_ptr __n)
2125 __node_base_ptr __prev_n = _M_buckets[__bkt];
2126 while (__prev_n->_M_nxt != __n)
2127 __prev_n = __prev_n->_M_nxt;
2131 template<
typename _Key,
typename _Value,
typename _Alloc,
2132 typename _ExtractKey,
typename _Equal,
2133 typename _Hash,
typename _RangeHash,
typename _Unused,
2134 typename _RehashPolicy,
typename _Traits>
2135 template<
typename... _Args>
2137 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2138 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2139 _M_emplace(true_type , _Args&&... __args)
2140 -> pair<iterator, bool>
2143 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2144 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2145 const size_type __size =
size();
2146 if (__size <= __small_size_threshold())
2148 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
2149 if (this->_M_key_equals(__k, *__it))
2151 return { iterator(__it),
false };
2154 __hash_code __code = this->_M_hash_code(__k);
2155 size_type __bkt = _M_bucket_index(__code);
2156 if (__size > __small_size_threshold())
2157 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2159 return { iterator(__p),
false };
2162 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2163 __node._M_node =
nullptr;
2164 return { __pos,
true };
2167 template<
typename _Key,
typename _Value,
typename _Alloc,
2168 typename _ExtractKey,
typename _Equal,
2169 typename _Hash,
typename _RangeHash,
typename _Unused,
2170 typename _RehashPolicy,
typename _Traits>
2171 template<
typename... _Args>
2173 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2174 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2175 _M_emplace(const_iterator __hint, false_type ,
2180 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2181 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2183 auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
2185 = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
2186 __node._M_node =
nullptr;
2190 template<
typename _Key,
typename _Value,
typename _Alloc,
2191 typename _ExtractKey,
typename _Equal,
2192 typename _Hash,
typename _RangeHash,
typename _Unused,
2193 typename _RehashPolicy,
typename _Traits>
2195 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2196 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2197 _M_compute_hash_code(__node_ptr __hint,
const key_type& __k)
const
2198 -> pair<__node_ptr, __hash_code>
2200 if (
size() <= __small_size_threshold())
2204 for (
auto __it = __hint; __it; __it = __it->_M_next())
2205 if (this->_M_key_equals(__k, *__it))
2206 return { __it, this->_M_hash_code(*__it) };
2209 for (
auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
2210 if (this->_M_key_equals(__k, *__it))
2211 return { __it, this->_M_hash_code(*__it) };
2216 return { __hint, this->_M_hash_code(__k) };
2219 template<
typename _Key,
typename _Value,
typename _Alloc,
2220 typename _ExtractKey,
typename _Equal,
2221 typename _Hash,
typename _RangeHash,
typename _Unused,
2222 typename _RehashPolicy,
typename _Traits>
2224 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2225 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2226 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2227 __node_ptr __node, size_type __n_elt)
2230 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2232 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2235 if (__do_rehash.
first)
2237 _M_rehash(__do_rehash.
second, true_type{});
2238 __bkt = _M_bucket_index(__code);
2241 __rehash_guard._M_guarded_obj =
nullptr;
2242 this->_M_store_code(*__node, __code);
2245 _M_insert_bucket_begin(__bkt, __node);
2247 return iterator(__node);
2250 template<
typename _Key,
typename _Value,
typename _Alloc,
2251 typename _ExtractKey,
typename _Equal,
2252 typename _Hash,
typename _RangeHash,
typename _Unused,
2253 typename _RehashPolicy,
typename _Traits>
2255 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2256 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2257 _M_insert_multi_node(__node_ptr __hint,
2258 __hash_code __code, __node_ptr __node)
2261 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2263 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2265 if (__do_rehash.
first)
2266 _M_rehash(__do_rehash.
second, false_type{});
2268 __rehash_guard._M_guarded_obj =
nullptr;
2269 this->_M_store_code(*__node, __code);
2270 const key_type& __k = _ExtractKey{}(__node->_M_v());
2271 size_type __bkt = _M_bucket_index(__code);
2275 __node_base_ptr __prev
2276 = __builtin_expect(__hint !=
nullptr,
false)
2277 && this->_M_equals(__k, __code, *__hint)
2279 : _M_find_before_node(__bkt, __k, __code);
2284 __node->_M_nxt = __prev->_M_nxt;
2285 __prev->_M_nxt = __node;
2286 if (__builtin_expect(__prev == __hint,
false))
2290 && !this->_M_equals(__k, __code, *__node->_M_next()))
2292 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2293 if (__next_bkt != __bkt)
2294 _M_buckets[__next_bkt] = __node;
2301 _M_insert_bucket_begin(__bkt, __node);
2303 return iterator(__node);
2307 template<
typename _Key,
typename _Value,
typename _Alloc,
2308 typename _ExtractKey,
typename _Equal,
2309 typename _Hash,
typename _RangeHash,
typename _Unused,
2310 typename _RehashPolicy,
typename _Traits>
2311 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
2313 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2314 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2315 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2316 const _NodeGenerator& __node_gen)
2317 -> pair<iterator, bool>
2319 const size_type __size =
size();
2320 if (__size <= __small_size_threshold())
2321 for (
auto __it = _M_begin(); __it; __it = __it->_M_next())
2322 if (this->_M_key_equals_tr(__k, *__it))
2323 return { iterator(__it),
false };
2325 __hash_code __code = this->_M_hash_code_tr(__k);
2326 size_type __bkt = _M_bucket_index(__code);
2328 if (__size > __small_size_threshold())
2329 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2330 return { iterator(__node),
false };
2332 _Scoped_node __node {
2333 __node_builder_t::_S_build(std::forward<_Kt>(__k),
2334 std::forward<_Arg>(__v),
2339 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2340 __node._M_node =
nullptr;
2341 return { __pos,
true };
2345 template<
typename _Key,
typename _Value,
typename _Alloc,
2346 typename _ExtractKey,
typename _Equal,
2347 typename _Hash,
typename _RangeHash,
typename _Unused,
2348 typename _RehashPolicy,
typename _Traits>
2349 template<
typename _Arg,
typename _NodeGenerator>
2351 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2352 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2353 _M_insert(const_iterator __hint, _Arg&& __v,
2354 const _NodeGenerator& __node_gen,
2359 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2362 auto __res = this->_M_compute_hash_code(
2363 __hint._M_cur, _ExtractKey{}(__node._M_node->_M_v()));
2366 = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
2367 __node._M_node =
nullptr;
2371 template<
typename _Key,
typename _Value,
typename _Alloc,
2372 typename _ExtractKey,
typename _Equal,
2373 typename _Hash,
typename _RangeHash,
typename _Unused,
2374 typename _RehashPolicy,
typename _Traits>
2376 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2377 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2378 erase(const_iterator __it)
2381 __node_ptr __n = __it._M_cur;
2382 std::size_t __bkt = _M_bucket_index(*__n);
2387 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2388 return _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(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2401 if (__prev_n == _M_buckets[__bkt])
2402 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2403 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2404 else if (__n->_M_nxt)
2406 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2407 if (__next_bkt != __bkt)
2408 _M_buckets[__next_bkt] = __prev_n;
2411 __prev_n->_M_nxt = __n->_M_nxt;
2412 iterator __result(__n->_M_next());
2413 this->_M_deallocate_node(__n);
2419 template<
typename _Key,
typename _Value,
typename _Alloc,
2420 typename _ExtractKey,
typename _Equal,
2421 typename _Hash,
typename _RangeHash,
typename _Unused,
2422 typename _RehashPolicy,
typename _Traits>
2424 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2425 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2426 _M_erase(true_type ,
const key_type& __k)
2429 __node_base_ptr __prev_n;
2432 if (
size() <= __small_size_threshold())
2434 __prev_n = _M_find_before_node(__k);
2439 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2440 __bkt = _M_bucket_index(*__n);
2444 __hash_code __code = this->_M_hash_code(__k);
2445 __bkt = _M_bucket_index(__code);
2448 __prev_n = _M_find_before_node(__bkt, __k, __code);
2453 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2456 _M_erase(__bkt, __prev_n, __n);
2460 template<
typename _Key,
typename _Value,
typename _Alloc,
2461 typename _ExtractKey,
typename _Equal,
2462 typename _Hash,
typename _RangeHash,
typename _Unused,
2463 typename _RehashPolicy,
typename _Traits>
2465 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2466 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2467 _M_erase(false_type ,
const key_type& __k)
2471 __node_base_ptr __prev_n;
2473 if (
size() <= __small_size_threshold())
2475 __prev_n = _M_find_before_node(__k);
2480 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2481 __bkt = _M_bucket_index(*__n);
2485 __hash_code __code = this->_M_hash_code(__k);
2486 __bkt = _M_bucket_index(__code);
2489 __prev_n = _M_find_before_node(__bkt, __k, __code);
2493 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2502 __node_ptr __n_last = __n->_M_next();
2503 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2504 __n_last = __n_last->_M_next();
2506 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2509 size_type __result = 0;
2512 __node_ptr __p = __n->_M_next();
2513 this->_M_deallocate_node(__n);
2517 while (__n != __n_last);
2519 _M_element_count -= __result;
2520 if (__prev_n == _M_buckets[__bkt])
2521 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2522 else if (__n_last_bkt != __bkt)
2523 _M_buckets[__n_last_bkt] = __prev_n;
2524 __prev_n->_M_nxt = __n_last;
2528 template<
typename _Key,
typename _Value,
typename _Alloc,
2529 typename _ExtractKey,
typename _Equal,
2530 typename _Hash,
typename _RangeHash,
typename _Unused,
2531 typename _RehashPolicy,
typename _Traits>
2533 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2534 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2535 erase(const_iterator __first, const_iterator __last)
2538 __node_ptr __n = __first._M_cur;
2539 __node_ptr __last_n = __last._M_cur;
2540 if (__n == __last_n)
2541 return iterator(__n);
2543 std::size_t __bkt = _M_bucket_index(*__n);
2545 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2546 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2547 std::size_t __n_bkt = __bkt;
2552 __node_ptr __tmp = __n;
2553 __n = __n->_M_next();
2554 this->_M_deallocate_node(__tmp);
2558 __n_bkt = _M_bucket_index(*__n);
2560 while (__n != __last_n && __n_bkt == __bkt);
2561 if (__is_bucket_begin)
2562 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2563 if (__n == __last_n)
2565 __is_bucket_begin =
true;
2569 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2570 _M_buckets[__n_bkt] = __prev_n;
2571 __prev_n->_M_nxt = __n;
2572 return iterator(__n);
2575 template<
typename _Key,
typename _Value,
typename _Alloc,
2576 typename _ExtractKey,
typename _Equal,
2577 typename _Hash,
typename _RangeHash,
typename _Unused,
2578 typename _RehashPolicy,
typename _Traits>
2580 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2581 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2584 this->_M_deallocate_nodes(_M_begin());
2585 __builtin_memset(_M_buckets, 0,
2586 _M_bucket_count *
sizeof(__node_base_ptr));
2587 _M_element_count = 0;
2588 _M_before_begin._M_nxt =
nullptr;
2591 template<
typename _Key,
typename _Value,
typename _Alloc,
2592 typename _ExtractKey,
typename _Equal,
2593 typename _Hash,
typename _RangeHash,
typename _Unused,
2594 typename _RehashPolicy,
typename _Traits>
2596 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2597 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2598 rehash(size_type __bkt_count)
2600 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2602 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2604 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2606 if (__bkt_count != _M_bucket_count)
2608 _M_rehash(__bkt_count, __unique_keys{});
2609 __rehash_guard._M_guarded_obj =
nullptr;
2614 template<
typename _Key,
typename _Value,
typename _Alloc,
2615 typename _ExtractKey,
typename _Equal,
2616 typename _Hash,
typename _RangeHash,
typename _Unused,
2617 typename _RehashPolicy,
typename _Traits>
2619 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2620 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2621 _M_rehash(size_type __bkt_count, true_type )
2623 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2624 __node_ptr __p = _M_begin();
2625 _M_before_begin._M_nxt =
nullptr;
2626 std::size_t __bbegin_bkt = 0;
2629 __node_ptr __next = __p->_M_next();
2631 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2632 if (!__new_buckets[__bkt])
2634 __p->_M_nxt = _M_before_begin._M_nxt;
2635 _M_before_begin._M_nxt = __p;
2636 __new_buckets[__bkt] = &_M_before_begin;
2638 __new_buckets[__bbegin_bkt] = __p;
2639 __bbegin_bkt = __bkt;
2643 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2644 __new_buckets[__bkt]->_M_nxt = __p;
2650 _M_deallocate_buckets();
2651 _M_bucket_count = __bkt_count;
2652 _M_buckets = __new_buckets;
2657 template<
typename _Key,
typename _Value,
typename _Alloc,
2658 typename _ExtractKey,
typename _Equal,
2659 typename _Hash,
typename _RangeHash,
typename _Unused,
2660 typename _RehashPolicy,
typename _Traits>
2662 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2663 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2664 _M_rehash(size_type __bkt_count, false_type )
2666 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2667 __node_ptr __p = _M_begin();
2668 _M_before_begin._M_nxt =
nullptr;
2669 std::size_t __bbegin_bkt = 0;
2670 std::size_t __prev_bkt = 0;
2671 __node_ptr __prev_p =
nullptr;
2672 bool __check_bucket =
false;
2676 __node_ptr __next = __p->_M_next();
2678 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2680 if (__prev_p && __prev_bkt == __bkt)
2685 __p->_M_nxt = __prev_p->_M_nxt;
2686 __prev_p->_M_nxt = __p;
2693 __check_bucket =
true;
2701 if (__prev_p->_M_nxt)
2703 std::size_t __next_bkt
2704 = __hash_code_base::_M_bucket_index(
2705 *__prev_p->_M_next(), __bkt_count);
2706 if (__next_bkt != __prev_bkt)
2707 __new_buckets[__next_bkt] = __prev_p;
2709 __check_bucket =
false;
2712 if (!__new_buckets[__bkt])
2714 __p->_M_nxt = _M_before_begin._M_nxt;
2715 _M_before_begin._M_nxt = __p;
2716 __new_buckets[__bkt] = &_M_before_begin;
2718 __new_buckets[__bbegin_bkt] = __p;
2719 __bbegin_bkt = __bkt;
2723 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2724 __new_buckets[__bkt]->_M_nxt = __p;
2732 if (__check_bucket && __prev_p->_M_nxt)
2734 std::size_t __next_bkt
2735 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2737 if (__next_bkt != __prev_bkt)
2738 __new_buckets[__next_bkt] = __prev_p;
2741 _M_deallocate_buckets();
2742 _M_bucket_count = __bkt_count;
2743 _M_buckets = __new_buckets;
2746#if __cplusplus > 201402L
2747 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2750#if __cpp_deduction_guides >= 201606
2752 template<
typename _Hash>
2753 using _RequireNotAllocatorOrIntegral
2754 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2758_GLIBCXX_END_NAMESPACE_VERSION
__bool_constant< 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.
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.