34#pragma GCC system_header
41#if __cplusplus > 201402L
45#pragma GCC diagnostic push
46#pragma GCC diagnostic ignored "-Wc++11-extensions"
48namespace std _GLIBCXX_VISIBILITY(default)
50_GLIBCXX_BEGIN_NAMESPACE_VERSION
53 template<
typename _Tp,
typename _Hash>
56 __is_fast_hash<_Hash>,
58 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
63 template<
typename _Equal,
typename _Hash,
typename _Allocator>
64 using _Hashtable_enable_default_ctor
65 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
66 is_default_constructible<_Hash>,
67 is_default_constructible<_Allocator>>{},
68 __detail::_Hash_node_base>;
185 template<
typename _Key,
typename _Value,
typename _Alloc,
186 typename _ExtractKey,
typename _Equal,
187 typename _Hash,
typename _RangeHash,
typename _Unused,
188 typename _RehashPolicy,
typename _Traits>
190 :
public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
191 _Hash, _RangeHash, _Unused, _Traits>,
192 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
193 _Hash, _RangeHash, _Unused,
194 _RehashPolicy, _Traits>,
195 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
196 _Hash, _RangeHash, _Unused,
197 _RehashPolicy, _Traits>,
198 private __detail::_Hashtable_alloc<
199 __alloc_rebind<_Alloc,
200 __detail::_Hash_node<_Value,
201 _Traits::__hash_cached::value>>>,
202 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
204 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
205 "unordered container must have a non-const, non-volatile value_type");
206#if __cplusplus > 201703L || defined __STRICT_ANSI__
207 static_assert(is_same<typename _Alloc::value_type, _Value>{},
208 "unordered container must have the same value_type as its allocator");
210 static_assert(is_copy_constructible<_Hash>::value,
211 "hash function must be copy constructible");
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 __enable_default_ctor
233 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
234 using __rehash_guard_t
235 = __detail::_RehashStateGuard<_RehashPolicy>;
238 typedef _Key key_type;
239 typedef _Value value_type;
240 typedef _Alloc allocator_type;
241 typedef _Equal key_equal;
245 typedef typename __value_alloc_traits::pointer pointer;
246 typedef typename __value_alloc_traits::const_pointer const_pointer;
247 typedef value_type& reference;
248 typedef const value_type& const_reference;
251 = __detail::_Node_iterator<_Value, __constant_iterators::value,
252 __hash_cached::value>;
255 = __detail::_Node_const_iterator<_Value, __constant_iterators::value,
256 __hash_cached::value>;
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 = __conditional_t<__unique_keys::value,
283 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
284 _Equal, _Hash, _RangeHash, _Unused,
285 _RehashPolicy, _Traits>;
287 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
289 _Hash, _RangeHash, _Unused,
290 _RehashPolicy, _Traits>;
292 using __node_builder_t = __detail::_NodeBuilder<_ExtractKey>;
298 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
299 : _M_h(__h), _M_node(__n) { }
302 template<
typename... _Args>
303 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
305 _M_node(__h->_M_allocate_node(
std::
forward<_Args>(__args)...))
309 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
311 _Scoped_node(
const _Scoped_node&) =
delete;
312 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
314 __hashtable_alloc* _M_h;
322 struct __hash_code_base_access : __hash_code_base
323 {
using __hash_code_base::_M_bucket_index; };
326 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
327 "Functor used to map hash code to bucket index"
328 " must be nothrow default constructible");
329 static_assert(
noexcept(
330 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
331 "Functor used to map hash code to bucket index must be"
335 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
336 "_ExtractKey must be nothrow default constructible");
337 static_assert(
noexcept(
338 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
339 "_ExtractKey functor must be noexcept invocable");
341 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
342 typename _ExtractKeya,
typename _Equala,
343 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
344 typename _RehashPolicya,
typename _Traitsa,
346 friend struct __detail::_Map_base;
349 using size_type =
typename __hashtable_base::size_type;
350 using difference_type =
typename __hashtable_base::difference_type;
352#if __cplusplus > 201402L
353 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
354 using insert_return_type = _Node_insert_return<iterator, node_type>;
358 __buckets_ptr _M_buckets = &_M_single_bucket;
359 size_type _M_bucket_count = 1;
360 __node_base _M_before_begin;
361 size_type _M_element_count = 0;
362 _RehashPolicy _M_rehash_policy;
370 __node_base_ptr _M_single_bucket =
nullptr;
375 if (
auto __begin = _M_begin())
376 _M_buckets[_M_bucket_index(*__begin)] = &_M_before_begin;
380 _M_update_bbegin(__node_ptr __n)
382 _M_before_begin._M_nxt = __n;
387 _M_uses_single_bucket(__buckets_ptr __bkts)
const
388 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
391 _M_uses_single_bucket()
const
392 {
return _M_uses_single_bucket(_M_buckets); }
394 static constexpr size_t
395 __small_size_threshold() noexcept
398 __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
402 _M_base_alloc() {
return *
this; }
405 _M_allocate_buckets(size_type __bkt_count)
407 if (__builtin_expect(__bkt_count == 1,
false))
409 _M_single_bucket =
nullptr;
410 return &_M_single_bucket;
413 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
417 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
419 if (_M_uses_single_bucket(__bkts))
422 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
426 _M_deallocate_buckets()
427 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
432 _M_bucket_begin(size_type __bkt)
const
434 __node_base_ptr __n = _M_buckets[__bkt];
435 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) : nullptr;
440 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
444 template<
typename _Ht>
446 _M_assign_elements(_Ht&&);
448 template<
typename _Ht>
450 _M_assign(_Ht&& __ht)
452 __detail::_AllocNode<__node_alloc_type> __alloc_node_gen(*
this);
453 _M_assign(std::forward<_Ht>(__ht), __alloc_node_gen);
456 template<
typename _Ht,
typename _NodeGenerator>
458 _M_assign(_Ht&&, _NodeGenerator&);
461 _M_move_assign(_Hashtable&&, true_type);
464 _M_move_assign(_Hashtable&&, false_type);
469 _Hashtable(const _Hash& __h, const _Equal& __eq,
470 const allocator_type& __a)
471 : __hashtable_base(__h, __eq),
472 __hashtable_alloc(__node_alloc_type(__a)),
473 __enable_default_ctor(_Enable_default_constructor_tag{})
476 template<
bool _No_realloc = true>
477 static constexpr bool
480#if __cplusplus <= 201402L
481 return __and_<__bool_constant<_No_realloc>,
482 is_nothrow_copy_constructible<_Hash>,
483 is_nothrow_copy_constructible<_Equal>>::value;
485 if constexpr (_No_realloc)
486 if constexpr (is_nothrow_copy_constructible<_Hash>())
487 return is_nothrow_copy_constructible<_Equal>();
492 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
494 noexcept(_S_nothrow_move());
496 _Hashtable(_Hashtable&&, __node_alloc_type&&,
499 template<
typename _InputIterator>
500 _Hashtable(_InputIterator __first, _InputIterator __last,
501 size_type __bkt_count_hint,
502 const _Hash&,
const _Equal&,
const allocator_type&,
505 template<
typename _InputIterator>
506 _Hashtable(_InputIterator __first, _InputIterator __last,
507 size_type __bkt_count_hint,
508 const _Hash&,
const _Equal&,
const allocator_type&,
513 _Hashtable() =
default;
515 _Hashtable(
const _Hashtable&);
517 _Hashtable(
const _Hashtable&,
const allocator_type&);
520 _Hashtable(size_type __bkt_count_hint,
521 const _Hash& __hf = _Hash(),
522 const key_equal& __eql = key_equal(),
523 const allocator_type& __a = allocator_type());
526 _Hashtable(_Hashtable&& __ht)
527 noexcept(_S_nothrow_move())
528 : _Hashtable(
std::
move(__ht),
std::
move(__ht._M_node_allocator()),
532 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
533 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
534 : _Hashtable(
std::
move(__ht), __node_alloc_type(__a),
535 typename __node_alloc_traits::is_always_equal{})
539 _Hashtable(
const allocator_type& __a)
540 : __hashtable_alloc(__node_alloc_type(__a)),
541 __enable_default_ctor(_Enable_default_constructor_tag{})
544 template<
typename _InputIterator>
545 _Hashtable(_InputIterator __f, _InputIterator __l,
546 size_type __bkt_count_hint = 0,
547 const _Hash& __hf = _Hash(),
548 const key_equal& __eql = key_equal(),
549 const allocator_type& __a = allocator_type())
550 : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
554 _Hashtable(initializer_list<value_type> __l,
555 size_type __bkt_count_hint = 0,
556 const _Hash& __hf = _Hash(),
557 const key_equal& __eql = key_equal(),
558 const allocator_type& __a = allocator_type())
559 : _Hashtable(__l.
begin(), __l.
end(), __bkt_count_hint,
560 __hf, __eql, __a, __unique_keys{})
564 operator=(
const _Hashtable& __ht);
567 operator=(_Hashtable&& __ht)
568 noexcept(__node_alloc_traits::_S_nothrow_move()
569 && is_nothrow_move_assignable<_Hash>::value
570 && is_nothrow_move_assignable<_Equal>::value)
572 constexpr bool __move_storage =
573 __node_alloc_traits::_S_propagate_on_move_assign()
574 || __node_alloc_traits::_S_always_equal();
575 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
579#pragma GCC diagnostic push
580#pragma GCC diagnostic ignored "-Wc++17-extensions"
582 operator=(initializer_list<value_type> __l)
584 using __reuse_or_alloc_node_gen_t =
585 __detail::_ReuseOrAllocNode<__node_alloc_type>;
587 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
588 _M_before_begin._M_nxt =
nullptr;
592 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
596 if (_M_bucket_count < __l_bkt_count)
597 rehash(__l_bkt_count);
601 for (
auto& __e : __l)
603 const key_type& __k = _ExtractKey{}(__e);
605 if constexpr (__unique_keys::value)
607 if (
auto __loc = _M_locate(__k))
611 __code = __loc._M_hash_code;
612 __bkt = __loc._M_bucket_index;
617 __code = this->_M_hash_code(__k);
618 __bkt = _M_bucket_index(__code);
621 _M_insert_unique_node(__bkt, __code, __roan(__e));
626#pragma GCC diagnostic pop
628 ~_Hashtable() noexcept;
632 noexcept(__and_<__is_nothrow_swappable<_Hash>,
633 __is_nothrow_swappable<_Equal>>::value);
638 {
return iterator(_M_begin()); }
641 begin() const noexcept
642 {
return const_iterator(_M_begin()); }
646 {
return iterator(
nullptr); }
650 {
return const_iterator(
nullptr); }
654 {
return const_iterator(_M_begin()); }
657 cend() const noexcept
658 {
return const_iterator(
nullptr); }
661 size() const noexcept
662 {
return _M_element_count; }
664 _GLIBCXX_NODISCARD
bool
665 empty() const noexcept
666 {
return size() == 0; }
669 get_allocator() const noexcept
670 {
return allocator_type(this->_M_node_allocator()); }
673 max_size() const noexcept
674 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
679 {
return this->_M_eq(); }
685 bucket_count() const noexcept
686 {
return _M_bucket_count; }
689 max_bucket_count() const noexcept
690 {
return max_size(); }
693 bucket_size(size_type __bkt)
const
697 bucket(
const key_type& __k)
const
698 {
return _M_bucket_index(this->_M_hash_code(__k)); }
701 begin(size_type __bkt)
703 return local_iterator(*
this, _M_bucket_begin(__bkt),
704 __bkt, _M_bucket_count);
709 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
712 begin(size_type __bkt)
const
714 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
715 __bkt, _M_bucket_count);
719 end(size_type __bkt)
const
720 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
724 cbegin(size_type __bkt)
const
726 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
727 __bkt, _M_bucket_count);
731 cend(size_type __bkt)
const
732 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
735 load_factor() const noexcept
737 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
746 __rehash_policy()
const
747 {
return _M_rehash_policy; }
750 __rehash_policy(
const _RehashPolicy& __pol)
751 { _M_rehash_policy = __pol; }
755 find(
const key_type& __k);
758 find(
const key_type& __k)
const;
761 count(
const key_type& __k)
const;
764 equal_range(
const key_type& __k);
767 equal_range(
const key_type& __k)
const;
769#ifdef __glibcxx_generic_unordered_lookup
770 template<
typename _Kt,
771 typename = __has_is_transparent_t<_Hash, _Kt>,
772 typename = __has_is_transparent_t<_Equal, _Kt>>
774 _M_find_tr(
const _Kt& __k);
776 template<
typename _Kt,
777 typename = __has_is_transparent_t<_Hash, _Kt>,
778 typename = __has_is_transparent_t<_Equal, _Kt>>
780 _M_find_tr(
const _Kt& __k)
const;
782 template<
typename _Kt,
783 typename = __has_is_transparent_t<_Hash, _Kt>,
784 typename = __has_is_transparent_t<_Equal, _Kt>>
786 _M_count_tr(
const _Kt& __k)
const;
788 template<
typename _Kt,
789 typename = __has_is_transparent_t<_Hash, _Kt>,
790 typename = __has_is_transparent_t<_Equal, _Kt>>
791 pair<iterator, iterator>
792 _M_equal_range_tr(
const _Kt& __k);
794 template<
typename _Kt,
795 typename = __has_is_transparent_t<_Hash, _Kt>,
796 typename = __has_is_transparent_t<_Equal, _Kt>>
797 pair<const_iterator, const_iterator>
798 _M_equal_range_tr(
const _Kt& __k)
const;
804 _M_bucket_index(
const __node_value_type& __n)
const noexcept
805 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
808 _M_bucket_index(__hash_code __c)
const
809 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
815 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
817 template<
typename _Kt>
819 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
823 struct __location_type
826 explicit operator bool() const noexcept
827 {
return static_cast<bool>(_M_before); }
830 explicit operator iterator() const noexcept
831 {
return iterator(_M_node()); }
834 explicit operator const_iterator() const noexcept
835 {
return const_iterator(_M_node()); }
838 __node_ptr _M_node()
const
841 return static_cast<__node_ptr
>(_M_before->_M_nxt);
845 __node_base_ptr _M_before{};
846 __hash_code _M_hash_code{};
847 size_type _M_bucket_index = size_type(-1);
865 _M_locate(
const key_type& __k)
const;
868 _M_find_node(size_type __bkt,
const key_type& __key,
869 __hash_code __c)
const
871 if (__node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c))
872 return static_cast<__node_ptr
>(__before_n->_M_nxt);
876 template<
typename _Kt>
878 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
879 __hash_code __c)
const
881 if (
auto __before_n = _M_find_before_node_tr(__bkt, __key, __c))
882 return static_cast<__node_ptr
>(__before_n->_M_nxt);
888 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
890 if (_M_buckets[__bkt])
894 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
895 _M_buckets[__bkt]->_M_nxt = __node;
902 __node->_M_nxt = _M_before_begin._M_nxt;
903 _M_before_begin._M_nxt = __node;
908 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
910 _M_buckets[__bkt] = &_M_before_begin;
916 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
917 size_type __next_bkt)
920 _M_buckets[__bkt] =
nullptr;
921 else if (__next_bkt != __bkt)
923 _M_buckets[__next_bkt] = _M_buckets[__bkt];
924 _M_buckets[__bkt] =
nullptr;
930 _M_get_previous_node(size_type __bkt, __node_ptr __n);
932 pair<__node_ptr, __hash_code>
933 _M_compute_hash_code(__node_ptr __hint,
const key_type& __k)
const;
942 _M_insert_unique_node(size_type __bkt, __hash_code,
943 __node_ptr __n, size_type __n_elt = 1);
948 _M_insert_multi_node(__node_ptr __hint,
949 __hash_code __code, __node_ptr __n);
951 template<
typename... _Args>
953 _M_emplace_uniq(_Args&&... __args);
955#pragma GCC diagnostic push
956#pragma GCC diagnostic ignored "-Wc++14-extensions"
957 template<
typename _Arg,
typename _DArg = __remove_cvref_t<_Arg>,
958 typename = _ExtractKey>
959 static constexpr bool __is_key_type =
false;
961 template<
typename _Arg>
962 static constexpr bool
963 __is_key_type<_Arg, key_type, __detail::_Identity> =
true;
965 template<
typename _Arg,
typename _Arg1,
typename _Arg2>
966 static constexpr bool
967 __is_key_type<_Arg, pair<_Arg1, _Arg2>, __detail::_Select1st>
968 = is_same<__remove_cvref_t<_Arg1>, key_type>::value;
969#pragma GCC diagnostic pop
971 template<
typename... _Args>
973 _M_emplace_multi(const_iterator, _Args&&... __args);
976 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
978 template<
typename _InputIterator>
980 _M_insert_range_multi(_InputIterator __first, _InputIterator __last);
983#pragma GCC diagnostic push
984#pragma GCC diagnostic ignored "-Wc++17-extensions"
986 template<
typename... _Args>
988 emplace(_Args&&... __args)
990 if constexpr (__unique_keys::value)
991 return _M_emplace_uniq(std::forward<_Args>(__args)...);
993 return _M_emplace_multi(
cend(), std::forward<_Args>(__args)...);
996 template<
typename... _Args>
998 emplace_hint(const_iterator __hint, _Args&&... __args)
1000 if constexpr (__unique_keys::value)
1001 return _M_emplace_uniq(std::forward<_Args>(__args)...).first;
1003 return _M_emplace_multi(__hint, std::forward<_Args>(__args)...);
1008 insert(
const value_type& __v)
1010 if constexpr (__unique_keys::value)
1011 return _M_emplace_uniq(__v);
1013 return _M_emplace_multi(
cend(), __v);
1017 insert(const_iterator __hint,
const value_type& __v)
1019 if constexpr (__unique_keys::value)
1020 return _M_emplace_uniq(__v).first;
1022 return _M_emplace_multi(__hint, __v);
1026 insert(value_type&& __v)
1028 if constexpr (__unique_keys::value)
1035 insert(const_iterator __hint, value_type&& __v)
1037 if constexpr (__unique_keys::value)
1038 return _M_emplace_uniq(
std::move(__v)).first;
1040 return _M_emplace_multi(__hint,
std::move(__v));
1043#ifdef __glibcxx_unordered_map_try_emplace
1044 template<
typename _KType,
typename... _Args>
1046 try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
1050 if (
auto __loc = _M_locate(__k))
1051 return { iterator(__loc),
false };
1054 __code = __loc._M_hash_code;
1055 __bkt = __loc._M_bucket_index;
1058 _Scoped_node __node {
1064 auto __it = _M_insert_unique_node(__bkt, __code, __node._M_node);
1065 __node._M_node =
nullptr;
1066 return { __it,
true };
1071 insert(initializer_list<value_type> __l)
1072 { this->insert(__l.begin(), __l.end()); }
1074 template<
typename _InputIterator>
1076 insert(_InputIterator __first, _InputIterator __last)
1078 if constexpr (__unique_keys::value)
1079 for (; __first != __last; ++__first)
1080 _M_emplace_uniq(*__first);
1082 return _M_insert_range_multi(__first, __last);
1086 template<
typename _Pair,
1087 typename = _Require<__not_<is_same<_Key, _Value>>,
1088 is_constructible<value_type, _Pair&&>>>
1092 if constexpr (__unique_keys::value)
1093 return _M_emplace_uniq(std::forward<_Pair>(__v));
1095 return _M_emplace_multi(
cend(), std::forward<_Pair>(__v));
1099 template<
typename _Pair,
1100 typename = _Require<__not_<is_same<_Key, _Value>>,
1101 is_constructible<value_type, _Pair&&>>>
1103 insert(const_iterator __hint, _Pair&& __v)
1105 if constexpr (__unique_keys::value)
1106 return _M_emplace_uniq(std::forward<_Pair>(__v));
1108 return _M_emplace_multi(__hint, std::forward<_Pair>(__v));
1110#pragma GCC diagnostic pop
1114 erase(const_iterator);
1119 erase(iterator __it)
1120 {
return erase(const_iterator(__it)); }
1123 erase(
const key_type& __k);
1126 erase(const_iterator, const_iterator);
1133 void rehash(size_type __bkt_count);
1138#if __glibcxx_node_extract
1141 _M_reinsert_node(node_type&& __nh)
1143 insert_return_type __ret;
1145 __ret.position =
end();
1148 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1150 if (
auto __loc = _M_locate(__nh._M_key()))
1153 __ret.position = iterator(__loc);
1154 __ret.inserted =
false;
1158 auto __code = __loc._M_hash_code;
1159 auto __bkt = __loc._M_bucket_index;
1161 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1162 __ret.inserted =
true;
1171 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1176 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1178 const key_type& __k = __nh._M_key();
1179 auto __code = this->_M_hash_code(__k);
1181 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1188 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1190 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1191 if (__prev_n == _M_buckets[__bkt])
1192 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1193 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1194 else if (__n->_M_nxt)
1196 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1197 if (__next_bkt != __bkt)
1198 _M_buckets[__next_bkt] = __prev_n;
1201 __prev_n->_M_nxt = __n->_M_nxt;
1202 __n->_M_nxt =
nullptr;
1204 return { __n, this->_M_node_allocator() };
1211 template<
typename _H2>
1213 _M_src_hash_code(
const _H2&,
const key_type& __k,
1214 const __node_value_type& __src_n)
const
1216 if constexpr (std::is_same_v<_H2, _Hash>)
1217 if constexpr (std::is_empty_v<_Hash>)
1219 return this->_M_hash_code(__src_n);
1221 return this->_M_hash_code(__k);
1227 extract(const_iterator __pos)
1229 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1230 return _M_extract_node(__bkt,
1231 _M_get_previous_node(__bkt, __pos._M_cur));
1236 extract(
const _Key& __k)
1239 __hash_code __code = this->_M_hash_code(__k);
1240 std::size_t __bkt = _M_bucket_index(__code);
1241 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1242 __nh = _M_extract_node(__bkt, __prev_node);
1248 _M_merge_unique(_Hashtable& __src)
1250 __glibcxx_assert(get_allocator() == __src.get_allocator());
1252 using _PTr = pointer_traits<__node_base_ptr>;
1254 auto __n_elt = __src.size();
1255 size_type __first = 1;
1258 auto __prev = _PTr::pointer_to(__src._M_before_begin);
1261 const auto __next = __prev->_M_nxt;
1262 const auto& __node =
static_cast<__node_type&
>(*__next);
1263 const key_type& __k = _ExtractKey{}(__node._M_v());
1264 const auto __loc = _M_locate(__k);
1271 auto __src_bkt = __src._M_bucket_index(__node);
1272 auto __nh = __src._M_extract_node(__src_bkt, __prev);
1273 _M_insert_unique_node(__loc._M_bucket_index, __loc._M_hash_code,
1274 __nh._M_ptr, __first * __n_elt + 1);
1281 template<
typename _Compatible_Hashtable>
1283 _M_merge_unique(_Compatible_Hashtable& __src)
1285 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1286 node_type>,
"Node types are compatible");
1287 __glibcxx_assert(get_allocator() == __src.get_allocator());
1289 auto __n_elt = __src.size();
1290 size_type __first = 1;
1293 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1297 const key_type& __k = _ExtractKey{}(*__pos);
1298 const auto __loc = _M_locate(__k);
1302 auto __nh = __src.extract(__pos);
1303 _M_insert_unique_node(__loc._M_bucket_index,
1304 __loc._M_hash_code, __nh._M_ptr,
1305 __first * __n_elt + 1);
1313 _M_merge_multi(_Hashtable& __src)
1315 __glibcxx_assert(get_allocator() == __src.get_allocator());
1317 if (__src.size() == 0) [[__unlikely__]]
1320 using _PTr = pointer_traits<__node_base_ptr>;
1322 __node_ptr __hint =
nullptr;
1323 this->reserve(
size() + __src.size());
1326 auto __prev = _PTr::pointer_to(__src._M_before_begin);
1329 const auto& __node =
static_cast<__node_type&
>(*__prev->_M_nxt);
1330 const key_type& __k = _ExtractKey{}(__node._M_v());
1332 auto __code = _M_src_hash_code(__src.hash_function(), __k, __node);
1334 size_type __src_bkt = __src._M_bucket_index(__node);
1335 auto __nh = __src._M_extract_node(__src_bkt, __prev);
1336 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1339 while (__prev->_M_nxt !=
nullptr);
1343 template<
typename _Compatible_Hashtable>
1345 _M_merge_multi(_Compatible_Hashtable& __src)
1347 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1348 node_type>,
"Node types are compatible");
1349 __glibcxx_assert(get_allocator() == __src.get_allocator());
1351 __node_ptr __hint =
nullptr;
1352 this->reserve(
size() + __src.size());
1355 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1358 const key_type& __k = _ExtractKey{}(*__pos);
1360 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1361 auto __nh = __src.extract(__pos);
1362 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1369 _M_equal(
const _Hashtable& __other)
const;
1373 void _M_rehash(size_type __bkt_count, true_type __uks);
1376 void _M_rehash(size_type __bkt_count, false_type __uks);
1380 template<
typename _Key,
typename _Value,
typename _Alloc,
1381 typename _ExtractKey,
typename _Equal,
1382 typename _Hash,
typename _RangeHash,
typename _Unused,
1383 typename _RehashPolicy,
typename _Traits>
1384 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1385 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1386 _Hashtable(size_type __bkt_count_hint,
1387 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1388 : _Hashtable(__h, __eq, __a)
1390 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1391 if (__bkt_count > _M_bucket_count)
1393 _M_buckets = _M_allocate_buckets(__bkt_count);
1394 _M_bucket_count = __bkt_count;
1398 template<
typename _Key,
typename _Value,
typename _Alloc,
1399 typename _ExtractKey,
typename _Equal,
1400 typename _Hash,
typename _RangeHash,
typename _Unused,
1401 typename _RehashPolicy,
typename _Traits>
1402 template<
typename _InputIterator>
1404 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1405 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1406 _Hashtable(_InputIterator __f, _InputIterator __l,
1407 size_type __bkt_count_hint,
1408 const _Hash& __h,
const _Equal& __eq,
1409 const allocator_type& __a, true_type )
1410 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1411 { this->insert(__f, __l); }
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 _InputIterator>
1418 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1419 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1420 _Hashtable(_InputIterator __f, _InputIterator __l,
1421 size_type __bkt_count_hint,
1422 const _Hash& __h,
const _Equal& __eq,
1423 const allocator_type& __a, false_type __uks)
1424 : _Hashtable(__h, __eq, __a)
1426 auto __nb_elems = __detail::__distance_fw(__f, __l);
1428 _M_rehash_policy._M_next_bkt(
1429 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1432 if (__bkt_count > _M_bucket_count)
1434 _M_buckets = _M_allocate_buckets(__bkt_count);
1435 _M_bucket_count = __bkt_count;
1438 for (; __f != __l; ++__f)
1439 _M_emplace_multi(
cend(), *__f);
1442 template<
typename _Key,
typename _Value,
typename _Alloc,
1443 typename _ExtractKey,
typename _Equal,
1444 typename _Hash,
typename _RangeHash,
typename _Unused,
1445 typename _RehashPolicy,
typename _Traits>
1447 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1448 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1449 operator=(
const _Hashtable& __ht)
1455 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1457 auto& __this_alloc = this->_M_node_allocator();
1458 auto& __that_alloc = __ht._M_node_allocator();
1459 if (!__node_alloc_traits::_S_always_equal()
1460 && __this_alloc != __that_alloc)
1463 this->_M_deallocate_nodes(_M_begin());
1464 _M_before_begin._M_nxt =
nullptr;
1465 _M_deallocate_buckets();
1466 _M_buckets =
nullptr;
1467 std::__alloc_on_copy(__this_alloc, __that_alloc);
1468 __hashtable_base::operator=(__ht);
1469 _M_bucket_count = __ht._M_bucket_count;
1470 _M_element_count = __ht._M_element_count;
1471 _M_rehash_policy = __ht._M_rehash_policy;
1475 ~_Guard() {
if (_M_ht) _M_ht->_M_reset(); }
1480 _Guard __guard{
this};
1482 __guard._M_ht =
nullptr;
1485 std::__alloc_on_copy(__this_alloc, __that_alloc);
1489 _M_assign_elements(__ht);
1493 template<
typename _Key,
typename _Value,
typename _Alloc,
1494 typename _ExtractKey,
typename _Equal,
1495 typename _Hash,
typename _RangeHash,
typename _Unused,
1496 typename _RehashPolicy,
typename _Traits>
1497 template<
typename _Ht>
1499 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1500 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1501 _M_assign_elements(_Ht&& __ht)
1503 using __reuse_or_alloc_node_gen_t =
1504 __detail::_ReuseOrAllocNode<__node_alloc_type>;
1506 __buckets_ptr __former_buckets =
nullptr;
1507 std::size_t __former_bucket_count = _M_bucket_count;
1508 __rehash_guard_t __rehash_guard(_M_rehash_policy);
1510 if (_M_bucket_count != __ht._M_bucket_count)
1512 __former_buckets = _M_buckets;
1513 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1514 _M_bucket_count = __ht._M_bucket_count;
1517 std::fill_n(_M_buckets, _M_bucket_count,
nullptr);
1521 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1522 _M_element_count = __ht._M_element_count;
1523 _M_rehash_policy = __ht._M_rehash_policy;
1524 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1525 _M_before_begin._M_nxt =
nullptr;
1526 _M_assign(std::forward<_Ht>(__ht), __roan);
1527 if (__former_buckets)
1528 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1529 __rehash_guard._M_guarded_obj =
nullptr;
1533 if (__former_buckets)
1536 _M_deallocate_buckets();
1537 _M_buckets = __former_buckets;
1538 _M_bucket_count = __former_bucket_count;
1540 std::fill_n(_M_buckets, _M_bucket_count,
nullptr);
1541 __throw_exception_again;
1545 template<
typename _Key,
typename _Value,
typename _Alloc,
1546 typename _ExtractKey,
typename _Equal,
1547 typename _Hash,
typename _RangeHash,
typename _Unused,
1548 typename _RehashPolicy,
typename _Traits>
1549 template<
typename _Ht,
typename _NodeGenerator>
1551 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1552 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1553 _M_assign(_Ht&& __ht, _NodeGenerator& __node_gen)
1562 if (_M_dealloc_buckets)
1563 _M_ht->_M_deallocate_buckets();
1566 _Hashtable* _M_ht =
nullptr;
1567 bool _M_dealloc_buckets =
false;
1573 _M_buckets = _M_allocate_buckets(_M_bucket_count);
1574 __guard._M_dealloc_buckets =
true;
1577 if (!__ht._M_before_begin._M_nxt)
1580 __guard._M_ht =
this;
1582 using _FromVal = __conditional_t<is_lvalue_reference<_Ht>::value,
1583 const value_type&, value_type&&>;
1587 __node_ptr __ht_n = __ht._M_begin();
1589 = __node_gen(
static_cast<_FromVal
>(__ht_n->_M_v()));
1590 this->_M_copy_code(*__this_n, *__ht_n);
1591 _M_update_bbegin(__this_n);
1594 __node_ptr __prev_n = __this_n;
1595 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1597 __this_n = __node_gen(
static_cast<_FromVal
>(__ht_n->_M_v()));
1598 __prev_n->_M_nxt = __this_n;
1599 this->_M_copy_code(*__this_n, *__ht_n);
1600 size_type __bkt = _M_bucket_index(*__this_n);
1601 if (!_M_buckets[__bkt])
1602 _M_buckets[__bkt] = __prev_n;
1603 __prev_n = __this_n;
1605 __guard._M_ht =
nullptr;
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>
1613 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1614 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1617 _M_rehash_policy._M_reset();
1618 _M_bucket_count = 1;
1619 _M_single_bucket =
nullptr;
1620 _M_buckets = &_M_single_bucket;
1621 _M_before_begin._M_nxt =
nullptr;
1622 _M_element_count = 0;
1625 template<
typename _Key,
typename _Value,
typename _Alloc,
1626 typename _ExtractKey,
typename _Equal,
1627 typename _Hash,
typename _RangeHash,
typename _Unused,
1628 typename _RehashPolicy,
typename _Traits>
1630 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1631 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1632 _M_move_assign(_Hashtable&& __ht, true_type)
1637 this->_M_deallocate_nodes(_M_begin());
1638 _M_deallocate_buckets();
1639 __hashtable_base::operator=(
std::move(__ht));
1640 _M_rehash_policy = __ht._M_rehash_policy;
1641 if (!__ht._M_uses_single_bucket())
1642 _M_buckets = __ht._M_buckets;
1645 _M_buckets = &_M_single_bucket;
1646 _M_single_bucket = __ht._M_single_bucket;
1649 _M_bucket_count = __ht._M_bucket_count;
1650 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1651 _M_element_count = __ht._M_element_count;
1652 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1659 template<
typename _Key,
typename _Value,
typename _Alloc,
1660 typename _ExtractKey,
typename _Equal,
1661 typename _Hash,
typename _RangeHash,
typename _Unused,
1662 typename _RehashPolicy,
typename _Traits>
1664 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1665 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1666 _M_move_assign(_Hashtable&& __ht, false_type)
1668 if (__ht._M_node_allocator() == this->_M_node_allocator())
1669 _M_move_assign(
std::move(__ht), true_type{});
1678 template<
typename _Key,
typename _Value,
typename _Alloc,
1679 typename _ExtractKey,
typename _Equal,
1680 typename _Hash,
typename _RangeHash,
typename _Unused,
1681 typename _RehashPolicy,
typename _Traits>
1683 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1684 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1685 _Hashtable(
const _Hashtable& __ht)
1686 : __hashtable_base(__ht),
1688 __rehash_base(__ht),
1690 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1691 __enable_default_ctor(__ht),
1692 _M_buckets(nullptr),
1693 _M_bucket_count(__ht._M_bucket_count),
1694 _M_element_count(__ht._M_element_count),
1695 _M_rehash_policy(__ht._M_rehash_policy)
1700 template<
typename _Key,
typename _Value,
typename _Alloc,
1701 typename _ExtractKey,
typename _Equal,
1702 typename _Hash,
typename _RangeHash,
typename _Unused,
1703 typename _RehashPolicy,
typename _Traits>
1704 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1705 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1706 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1708 noexcept(_S_nothrow_move())
1709 : __hashtable_base(__ht),
1711 __rehash_base(__ht),
1712 __hashtable_alloc(
std::
move(__a)),
1713 __enable_default_ctor(__ht),
1714 _M_buckets(__ht._M_buckets),
1715 _M_bucket_count(__ht._M_bucket_count),
1716 _M_before_begin(__ht._M_before_begin._M_nxt),
1717 _M_element_count(__ht._M_element_count),
1718 _M_rehash_policy(__ht._M_rehash_policy)
1721 if (__ht._M_uses_single_bucket())
1723 _M_buckets = &_M_single_bucket;
1724 _M_single_bucket = __ht._M_single_bucket;
1733 template<
typename _Key,
typename _Value,
typename _Alloc,
1734 typename _ExtractKey,
typename _Equal,
1735 typename _Hash,
typename _RangeHash,
typename _Unused,
1736 typename _RehashPolicy,
typename _Traits>
1738 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1739 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1740 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1741 : __hashtable_base(__ht),
1743 __rehash_base(__ht),
1744 __hashtable_alloc(__node_alloc_type(__a)),
1745 __enable_default_ctor(__ht),
1747 _M_bucket_count(__ht._M_bucket_count),
1748 _M_element_count(__ht._M_element_count),
1749 _M_rehash_policy(__ht._M_rehash_policy)
1754 template<
typename _Key,
typename _Value,
typename _Alloc,
1755 typename _ExtractKey,
typename _Equal,
1756 typename _Hash,
typename _RangeHash,
typename _Unused,
1757 typename _RehashPolicy,
typename _Traits>
1758 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1759 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1760 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1762 : __hashtable_base(__ht),
1764 __rehash_base(__ht),
1765 __hashtable_alloc(
std::
move(__a)),
1766 __enable_default_ctor(__ht),
1767 _M_buckets(nullptr),
1768 _M_bucket_count(__ht._M_bucket_count),
1769 _M_element_count(__ht._M_element_count),
1770 _M_rehash_policy(__ht._M_rehash_policy)
1772 if (__ht._M_node_allocator() == this->_M_node_allocator())
1774 if (__ht._M_uses_single_bucket())
1776 _M_buckets = &_M_single_bucket;
1777 _M_single_bucket = __ht._M_single_bucket;
1780 _M_buckets = __ht._M_buckets;
1784 _M_update_bbegin(__ht._M_begin());
1790 using _Fwd_Ht = __conditional_t<
1791 __move_if_noexcept_cond<value_type>::value,
1792 const _Hashtable&, _Hashtable&&>;
1793 _M_assign(std::forward<_Fwd_Ht>(__ht));
1798 template<
typename _Key,
typename _Value,
typename _Alloc,
1799 typename _ExtractKey,
typename _Equal,
1800 typename _Hash,
typename _RangeHash,
typename _Unused,
1801 typename _RehashPolicy,
typename _Traits>
1802 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1803 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1804 ~_Hashtable() noexcept
1811 static_assert(
noexcept(declval<const __hash_code_base_access&>()
1812 ._M_bucket_index(declval<const __node_value_type&>(),
1814 "Cache the hash code or qualify your functors involved"
1815 " in hash code and bucket index computation with noexcept");
1817 this->_M_deallocate_nodes(_M_begin());
1818 _M_deallocate_buckets();
1821 template<
typename _Key,
typename _Value,
typename _Alloc,
1822 typename _ExtractKey,
typename _Equal,
1823 typename _Hash,
typename _RangeHash,
typename _Unused,
1824 typename _RehashPolicy,
typename _Traits>
1826 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1827 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1828 swap(_Hashtable& __x)
1829 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1830 __is_nothrow_swappable<_Equal>>::value)
1833 swap(__hash_code_base::_M_hash._M_obj,
1834 __x.__hash_code_base::_M_hash._M_obj);
1835 swap(__hashtable_base::_M_equal._M_obj,
1836 __x.__hashtable_base::_M_equal._M_obj);
1838#pragma GCC diagnostic push
1839#pragma GCC diagnostic ignored "-Wc++17-extensions"
1840 if constexpr (__node_alloc_traits::propagate_on_container_swap::value)
1841 swap(this->_M_node_allocator(), __x._M_node_allocator());
1842#pragma GCC diagnostic pop
1844 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1847 if (this->_M_uses_single_bucket())
1849 if (!__x._M_uses_single_bucket())
1851 _M_buckets = __x._M_buckets;
1852 __x._M_buckets = &__x._M_single_bucket;
1855 else if (__x._M_uses_single_bucket())
1857 __x._M_buckets = _M_buckets;
1858 _M_buckets = &_M_single_bucket;
1861 std::swap(_M_buckets, __x._M_buckets);
1863 std::swap(_M_bucket_count, __x._M_bucket_count);
1864 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1865 std::swap(_M_element_count, __x._M_element_count);
1866 std::swap(_M_single_bucket, __x._M_single_bucket);
1871 __x._M_update_bbegin();
1874 template<
typename _Key,
typename _Value,
typename _Alloc,
1875 typename _ExtractKey,
typename _Equal,
1876 typename _Hash,
typename _RangeHash,
typename _Unused,
1877 typename _RehashPolicy,
typename _Traits>
1879 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1880 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1881 find(
const key_type& __k)
1883 {
return iterator(_M_locate(__k)); }
1885 template<
typename _Key,
typename _Value,
typename _Alloc,
1886 typename _ExtractKey,
typename _Equal,
1887 typename _Hash,
typename _RangeHash,
typename _Unused,
1888 typename _RehashPolicy,
typename _Traits>
1890 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1891 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1892 find(
const key_type& __k)
const
1894 {
return const_iterator(_M_locate(__k)); }
1896#if __cplusplus > 201703L
1897 template<
typename _Key,
typename _Value,
typename _Alloc,
1898 typename _ExtractKey,
typename _Equal,
1899 typename _Hash,
typename _RangeHash,
typename _Unused,
1900 typename _RehashPolicy,
typename _Traits>
1901 template<
typename _Kt,
typename,
typename>
1903 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1904 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1905 _M_find_tr(
const _Kt& __k)
1908 if (
size() <= __small_size_threshold())
1910 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1911 if (this->_M_key_equals_tr(__k, *__n))
1912 return iterator(__n);
1916 __hash_code __code = this->_M_hash_code_tr(__k);
1917 std::size_t __bkt = _M_bucket_index(__code);
1918 return iterator(_M_find_node_tr(__bkt, __k, __code));
1921 template<
typename _Key,
typename _Value,
typename _Alloc,
1922 typename _ExtractKey,
typename _Equal,
1923 typename _Hash,
typename _RangeHash,
typename _Unused,
1924 typename _RehashPolicy,
typename _Traits>
1925 template<
typename _Kt,
typename,
typename>
1927 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1928 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1929 _M_find_tr(
const _Kt& __k)
const
1932 if (
size() <= __small_size_threshold())
1934 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1935 if (this->_M_key_equals_tr(__k, *__n))
1936 return const_iterator(__n);
1940 __hash_code __code = this->_M_hash_code_tr(__k);
1941 std::size_t __bkt = _M_bucket_index(__code);
1942 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1946 template<
typename _Key,
typename _Value,
typename _Alloc,
1947 typename _ExtractKey,
typename _Equal,
1948 typename _Hash,
typename _RangeHash,
typename _Unused,
1949 typename _RehashPolicy,
typename _Traits>
1951 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1952 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1953 count(
const key_type& __k)
const
1956 auto __it = find(__k);
1960 if (__unique_keys::value)
1963 size_type __result = 1;
1964 for (
auto __ref = __it++;
1965 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1972#if __cplusplus > 201703L
1973 template<
typename _Key,
typename _Value,
typename _Alloc,
1974 typename _ExtractKey,
typename _Equal,
1975 typename _Hash,
typename _RangeHash,
typename _Unused,
1976 typename _RehashPolicy,
typename _Traits>
1977 template<
typename _Kt,
typename,
typename>
1979 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1980 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1981 _M_count_tr(
const _Kt& __k)
const
1984 if (
size() <= __small_size_threshold())
1986 size_type __result = 0;
1987 for (
auto __n = _M_begin(); __n; __n = __n->_M_next())
1989 if (this->_M_key_equals_tr(__k, *__n))
2002 __hash_code __code = this->_M_hash_code_tr(__k);
2003 std::size_t __bkt = _M_bucket_index(__code);
2004 auto __n = _M_find_node_tr(__bkt, __k, __code);
2009 size_type __result = 1;
2011 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
2019 template<
typename _Key,
typename _Value,
typename _Alloc,
2020 typename _ExtractKey,
typename _Equal,
2021 typename _Hash,
typename _RangeHash,
typename _Unused,
2022 typename _RehashPolicy,
typename _Traits>
2024 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2025 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2026 equal_range(
const key_type& __k)
2027 -> pair<iterator, iterator>
2029 auto __ite = find(__k);
2031 return { __ite, __ite };
2033 auto __beg = __ite++;
2034 if (__unique_keys::value)
2035 return { __beg, __ite };
2037 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
2040 return { __beg, __ite };
2043 template<
typename _Key,
typename _Value,
typename _Alloc,
2044 typename _ExtractKey,
typename _Equal,
2045 typename _Hash,
typename _RangeHash,
typename _Unused,
2046 typename _RehashPolicy,
typename _Traits>
2048 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2049 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2050 equal_range(
const key_type& __k)
const
2051 -> pair<const_iterator, const_iterator>
2053 auto __ite = find(__k);
2055 return { __ite, __ite };
2057 auto __beg = __ite++;
2058 if (__unique_keys::value)
2059 return { __beg, __ite };
2061 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
2064 return { __beg, __ite };
2067#if __cplusplus > 201703L
2068 template<
typename _Key,
typename _Value,
typename _Alloc,
2069 typename _ExtractKey,
typename _Equal,
2070 typename _Hash,
typename _RangeHash,
typename _Unused,
2071 typename _RehashPolicy,
typename _Traits>
2072 template<
typename _Kt,
typename,
typename>
2074 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2075 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2076 _M_equal_range_tr(
const _Kt& __k)
2077 -> pair<iterator, iterator>
2079 if (
size() <= __small_size_threshold())
2081 __node_ptr __n, __beg =
nullptr;
2082 for (__n = _M_begin(); __n; __n = __n->_M_next())
2084 if (this->_M_key_equals_tr(__k, *__n))
2095 return { iterator(__beg), iterator(__n) };
2098 __hash_code __code = this->_M_hash_code_tr(__k);
2099 std::size_t __bkt = _M_bucket_index(__code);
2100 auto __n = _M_find_node_tr(__bkt, __k, __code);
2101 iterator __ite(__n);
2103 return { __ite, __ite };
2105 auto __beg = __ite++;
2106 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
2109 return { __beg, __ite };
2112 template<
typename _Key,
typename _Value,
typename _Alloc,
2113 typename _ExtractKey,
typename _Equal,
2114 typename _Hash,
typename _RangeHash,
typename _Unused,
2115 typename _RehashPolicy,
typename _Traits>
2116 template<
typename _Kt,
typename,
typename>
2118 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2119 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2120 _M_equal_range_tr(
const _Kt& __k)
const
2121 -> pair<const_iterator, const_iterator>
2123 if (
size() <= __small_size_threshold())
2125 __node_ptr __n, __beg =
nullptr;
2126 for (__n = _M_begin(); __n; __n = __n->_M_next())
2128 if (this->_M_key_equals_tr(__k, *__n))
2139 return { const_iterator(__beg), const_iterator(__n) };
2142 __hash_code __code = this->_M_hash_code_tr(__k);
2143 std::size_t __bkt = _M_bucket_index(__code);
2144 auto __n = _M_find_node_tr(__bkt, __k, __code);
2145 const_iterator __ite(__n);
2147 return { __ite, __ite };
2149 auto __beg = __ite++;
2150 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
2153 return { __beg, __ite };
2159 template<
typename _Key,
typename _Value,
typename _Alloc,
2160 typename _ExtractKey,
typename _Equal,
2161 typename _Hash,
typename _RangeHash,
typename _Unused,
2162 typename _RehashPolicy,
typename _Traits>
2164 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2165 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2166 _M_find_before_node(size_type __bkt,
const key_type& __k,
2167 __hash_code __code)
const
2170 __node_base_ptr __prev_p = _M_buckets[__bkt];
2174 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
2175 __p = __p->_M_next())
2177 if (this->_M_equals(__k, __code, *__p))
2180 if (__builtin_expect (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt, 0))
2188 template<
typename _Key,
typename _Value,
typename _Alloc,
2189 typename _ExtractKey,
typename _Equal,
2190 typename _Hash,
typename _RangeHash,
typename _Unused,
2191 typename _RehashPolicy,
typename _Traits>
2192 template<
typename _Kt>
2194 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2195 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2196 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
2197 __hash_code __code)
const
2200 __node_base_ptr __prev_p = _M_buckets[__bkt];
2204 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
2205 __p = __p->_M_next())
2207 if (this->_M_equals_tr(__k, __code, *__p))
2210 if (__builtin_expect (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt, 0))
2218 template<
typename _Key,
typename _Value,
typename _Alloc,
2219 typename _ExtractKey,
typename _Equal,
2220 typename _Hash,
typename _RangeHash,
typename _Unused,
2221 typename _RehashPolicy,
typename _Traits>
2223 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2224 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2225 _M_locate(
const key_type& __k)
const
2228 __location_type __loc;
2229 const auto __size =
size();
2231 if (__size <= __small_size_threshold())
2233 __loc._M_before = pointer_traits<__node_base_ptr>::
2234 pointer_to(
const_cast<__node_base&
>(_M_before_begin));
2235 while (__loc._M_before->_M_nxt)
2237 if (this->_M_key_equals(__k, *__loc._M_node()))
2239 __loc._M_before = __loc._M_before->_M_nxt;
2241 __loc._M_before =
nullptr;
2244 __loc._M_hash_code = this->_M_hash_code(__k);
2245 __loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code);
2247 if (__size > __small_size_threshold())
2248 __loc._M_before = _M_find_before_node(__loc._M_bucket_index, __k,
2249 __loc._M_hash_code);
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_get_previous_node(size_type __bkt, __node_ptr __n)
2264 __node_base_ptr __prev_n = _M_buckets[__bkt];
2265 while (__prev_n->_M_nxt != __n)
2266 __prev_n = __prev_n->_M_nxt;
2270#pragma GCC diagnostic push
2271#pragma GCC diagnostic ignored "-Wc++17-extensions"
2272 template<
typename _Key,
typename _Value,
typename _Alloc,
2273 typename _ExtractKey,
typename _Equal,
2274 typename _Hash,
typename _RangeHash,
typename _Unused,
2275 typename _RehashPolicy,
typename _Traits>
2276 template<
typename... _Args>
2278 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2279 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2280 _M_emplace_uniq(_Args&&... __args)
2281 -> pair<iterator, bool>
2283 const key_type* __kp =
nullptr;
2285 if constexpr (
sizeof...(_Args) == 1)
2287 if constexpr (__is_key_type<_Args...>)
2289 const auto& __key = _ExtractKey{}(__args...);
2293 else if constexpr (
sizeof...(_Args) == 2)
2295 if constexpr (__is_key_type<pair<
const _Args&...>>)
2297 pair<
const _Args&...> __refs(__args...);
2298 const auto& __key = _ExtractKey{}(__refs);
2303 _Scoped_node __node { __node_ptr(),
this };
2304 __hash_code __code = 0;
2305 size_type __bkt = 0;
2307 if (__kp ==
nullptr)
2311 = this->_M_allocate_node(std::forward<_Args>(__args)...);
2312 const key_type& __key = _ExtractKey{}(__node._M_node->_M_v());
2316 if (
auto __loc = _M_locate(*__kp))
2318 return { iterator(__loc),
false };
2321 __code = __loc._M_hash_code;
2322 __bkt = __loc._M_bucket_index;
2325 if (!__node._M_node)
2327 = this->_M_allocate_node(std::forward<_Args>(__args)...);
2330 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2331 __node._M_node =
nullptr;
2332 return { __pos,
true };
2334#pragma GCC diagnostic pop
2336 template<
typename _Key,
typename _Value,
typename _Alloc,
2337 typename _ExtractKey,
typename _Equal,
2338 typename _Hash,
typename _RangeHash,
typename _Unused,
2339 typename _RehashPolicy,
typename _Traits>
2340 template<
typename... _Args>
2342 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2343 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2344 _M_emplace_multi(const_iterator __hint, _Args&&... __args)
2348 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2349 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2351 auto __res = this->_M_compute_hash_code(__hint._M_cur, __k);
2353 = _M_insert_multi_node(__res.first, __res.second, __node._M_node);
2354 __node._M_node =
nullptr;
2358 template<
typename _Key,
typename _Value,
typename _Alloc,
2359 typename _ExtractKey,
typename _Equal,
2360 typename _Hash,
typename _RangeHash,
typename _Unused,
2361 typename _RehashPolicy,
typename _Traits>
2362 template<
typename _InputIterator>
2364 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2365 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2366 _M_insert_range_multi(_InputIterator __first, _InputIterator __last)
2370 size_type __n_elt = __detail::__distance_fw(__first, __last);
2374 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2375 __pair_type __do_rehash
2376 = _M_rehash_policy._M_need_rehash(_M_bucket_count,
2380 if (__do_rehash.first)
2381 _M_rehash(__do_rehash.second, false_type{});
2383 __rehash_guard._M_guarded_obj =
nullptr;
2384 for (; __first != __last; ++__first)
2385 _M_emplace_multi(
cend(), *__first);
2388 template<
typename _Key,
typename _Value,
typename _Alloc,
2389 typename _ExtractKey,
typename _Equal,
2390 typename _Hash,
typename _RangeHash,
typename _Unused,
2391 typename _RehashPolicy,
typename _Traits>
2393 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2394 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2395 _M_compute_hash_code(__node_ptr __hint,
const key_type& __k)
const
2396 -> pair<__node_ptr, __hash_code>
2398 if (
size() <= __small_size_threshold())
2402 for (
auto __it = __hint; __it; __it = __it->_M_next())
2403 if (this->_M_key_equals(__k, *__it))
2404 return { __it, this->_M_hash_code(*__it) };
2407 for (
auto __it = _M_begin(); __it != __hint; __it = __it->_M_next())
2408 if (this->_M_key_equals(__k, *__it))
2409 return { __it, this->_M_hash_code(*__it) };
2414 return { __hint, this->_M_hash_code(__k) };
2417 template<
typename _Key,
typename _Value,
typename _Alloc,
2418 typename _ExtractKey,
typename _Equal,
2419 typename _Hash,
typename _RangeHash,
typename _Unused,
2420 typename _RehashPolicy,
typename _Traits>
2422 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2423 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2424 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2425 __node_ptr __node, size_type __n_elt)
2428 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2430 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2433 if (__do_rehash.
first)
2435 _M_rehash(__do_rehash.
second, true_type{});
2436 __bkt = _M_bucket_index(__code);
2439 __rehash_guard._M_guarded_obj =
nullptr;
2440 this->_M_store_code(*__node, __code);
2443 _M_insert_bucket_begin(__bkt, __node);
2445 return iterator(__node);
2448 template<
typename _Key,
typename _Value,
typename _Alloc,
2449 typename _ExtractKey,
typename _Equal,
2450 typename _Hash,
typename _RangeHash,
typename _Unused,
2451 typename _RehashPolicy,
typename _Traits>
2453 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2454 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2455 _M_insert_multi_node(__node_ptr __hint,
2456 __hash_code __code, __node_ptr __node)
2459 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2461 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2463 if (__do_rehash.
first)
2464 _M_rehash(__do_rehash.
second, false_type{});
2466 __rehash_guard._M_guarded_obj =
nullptr;
2467 this->_M_store_code(*__node, __code);
2468 const key_type& __k = _ExtractKey{}(__node->_M_v());
2469 size_type __bkt = _M_bucket_index(__code);
2473 __node_base_ptr __prev
2474 = __builtin_expect(__hint !=
nullptr,
false)
2475 && this->_M_equals(__k, __code, *__hint)
2477 : _M_find_before_node(__bkt, __k, __code);
2482 __node->_M_nxt = __prev->_M_nxt;
2483 __prev->_M_nxt = __node;
2484 if (__builtin_expect(__prev == __hint,
false))
2488 && !this->_M_equals(__k, __code, *__node->_M_next()))
2490 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2491 if (__next_bkt != __bkt)
2492 _M_buckets[__next_bkt] = __node;
2499 _M_insert_bucket_begin(__bkt, __node);
2501 return iterator(__node);
2504 template<
typename _Key,
typename _Value,
typename _Alloc,
2505 typename _ExtractKey,
typename _Equal,
2506 typename _Hash,
typename _RangeHash,
typename _Unused,
2507 typename _RehashPolicy,
typename _Traits>
2509 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2510 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2511 erase(const_iterator __it)
2514 __node_ptr __n = __it._M_cur;
2515 std::size_t __bkt = _M_bucket_index(*__n);
2520 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2521 return _M_erase(__bkt, __prev_n, __n);
2524 template<
typename _Key,
typename _Value,
typename _Alloc,
2525 typename _ExtractKey,
typename _Equal,
2526 typename _Hash,
typename _RangeHash,
typename _Unused,
2527 typename _RehashPolicy,
typename _Traits>
2529 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2530 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2531 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2534 if (__prev_n == _M_buckets[__bkt])
2535 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2536 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2537 else if (__n->_M_nxt)
2539 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2540 if (__next_bkt != __bkt)
2541 _M_buckets[__next_bkt] = __prev_n;
2544 __prev_n->_M_nxt = __n->_M_nxt;
2545 iterator __result(__n->_M_next());
2546 this->_M_deallocate_node(__n);
2552#pragma GCC diagnostic push
2553#pragma GCC diagnostic ignored "-Wc++17-extensions"
2554 template<
typename _Key,
typename _Value,
typename _Alloc,
2555 typename _ExtractKey,
typename _Equal,
2556 typename _Hash,
typename _RangeHash,
typename _Unused,
2557 typename _RehashPolicy,
typename _Traits>
2559 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2560 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2561 erase(
const key_type& __k)
2564 auto __loc = _M_locate(__k);
2568 __node_base_ptr __prev_n = __loc._M_before;
2569 __node_ptr __n = __loc._M_node();
2570 auto __bkt = __loc._M_bucket_index;
2571 if (__bkt == size_type(-1))
2572 __bkt = _M_bucket_index(*__n);
2574 if constexpr (__unique_keys::value)
2576 _M_erase(__bkt, __prev_n, __n);
2587 __node_ptr __n_last = __n->_M_next();
2588 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2589 __n_last = __n_last->_M_next();
2591 std::size_t __n_last_bkt
2592 = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2595 size_type __result = 0;
2598 __node_ptr __p = __n->_M_next();
2599 this->_M_deallocate_node(__n);
2603 while (__n != __n_last);
2605 _M_element_count -= __result;
2606 if (__prev_n == _M_buckets[__bkt])
2607 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2608 else if (__n_last_bkt != __bkt)
2609 _M_buckets[__n_last_bkt] = __prev_n;
2610 __prev_n->_M_nxt = __n_last;
2614#pragma GCC diagnostic pop
2616 template<
typename _Key,
typename _Value,
typename _Alloc,
2617 typename _ExtractKey,
typename _Equal,
2618 typename _Hash,
typename _RangeHash,
typename _Unused,
2619 typename _RehashPolicy,
typename _Traits>
2621 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2622 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2623 erase(const_iterator __first, const_iterator __last)
2626 __node_ptr __n = __first._M_cur;
2627 __node_ptr __last_n = __last._M_cur;
2628 if (__n == __last_n)
2629 return iterator(__n);
2631 std::size_t __bkt = _M_bucket_index(*__n);
2633 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2634 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2635 std::size_t __n_bkt = __bkt;
2640 __node_ptr __tmp = __n;
2641 __n = __n->_M_next();
2642 this->_M_deallocate_node(__tmp);
2646 __n_bkt = _M_bucket_index(*__n);
2648 while (__n != __last_n && __n_bkt == __bkt);
2649 if (__is_bucket_begin)
2650 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2651 if (__n == __last_n)
2653 __is_bucket_begin =
true;
2657 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2658 _M_buckets[__n_bkt] = __prev_n;
2659 __prev_n->_M_nxt = __n;
2660 return iterator(__n);
2663 template<
typename _Key,
typename _Value,
typename _Alloc,
2664 typename _ExtractKey,
typename _Equal,
2665 typename _Hash,
typename _RangeHash,
typename _Unused,
2666 typename _RehashPolicy,
typename _Traits>
2668 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2669 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2672 this->_M_deallocate_nodes(_M_begin());
2673 std::fill_n(_M_buckets, _M_bucket_count,
nullptr);
2674 _M_element_count = 0;
2675 _M_before_begin._M_nxt =
nullptr;
2678 template<
typename _Key,
typename _Value,
typename _Alloc,
2679 typename _ExtractKey,
typename _Equal,
2680 typename _Hash,
typename _RangeHash,
typename _Unused,
2681 typename _RehashPolicy,
typename _Traits>
2683 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2684 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2685 rehash(size_type __bkt_count)
2687 __rehash_guard_t __rehash_guard(_M_rehash_policy);
2689 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2691 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2693 if (__bkt_count != _M_bucket_count)
2695 _M_rehash(__bkt_count, __unique_keys{});
2696 __rehash_guard._M_guarded_obj =
nullptr;
2701 template<
typename _Key,
typename _Value,
typename _Alloc,
2702 typename _ExtractKey,
typename _Equal,
2703 typename _Hash,
typename _RangeHash,
typename _Unused,
2704 typename _RehashPolicy,
typename _Traits>
2706 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2707 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2708 _M_rehash(size_type __bkt_count, true_type )
2710 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2711 __node_ptr __p = _M_begin();
2712 _M_before_begin._M_nxt =
nullptr;
2713 std::size_t __bbegin_bkt = 0;
2716 __node_ptr __next = __p->_M_next();
2718 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2719 if (!__new_buckets[__bkt])
2721 __p->_M_nxt = _M_before_begin._M_nxt;
2722 _M_before_begin._M_nxt = __p;
2723 __new_buckets[__bkt] = &_M_before_begin;
2725 __new_buckets[__bbegin_bkt] = __p;
2726 __bbegin_bkt = __bkt;
2730 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2731 __new_buckets[__bkt]->_M_nxt = __p;
2737 _M_deallocate_buckets();
2738 _M_bucket_count = __bkt_count;
2739 _M_buckets = __new_buckets;
2744 template<
typename _Key,
typename _Value,
typename _Alloc,
2745 typename _ExtractKey,
typename _Equal,
2746 typename _Hash,
typename _RangeHash,
typename _Unused,
2747 typename _RehashPolicy,
typename _Traits>
2749 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2750 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2751 _M_rehash(size_type __bkt_count, false_type )
2753 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2754 __node_ptr __p = _M_begin();
2755 _M_before_begin._M_nxt =
nullptr;
2756 std::size_t __bbegin_bkt = 0;
2757 std::size_t __prev_bkt = 0;
2758 __node_ptr __prev_p =
nullptr;
2759 bool __check_bucket =
false;
2763 __node_ptr __next = __p->_M_next();
2765 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2767 if (__prev_p && __prev_bkt == __bkt)
2772 __p->_M_nxt = __prev_p->_M_nxt;
2773 __prev_p->_M_nxt = __p;
2780 __check_bucket =
true;
2788 if (__prev_p->_M_nxt)
2790 std::size_t __next_bkt
2791 = __hash_code_base::_M_bucket_index(
2792 *__prev_p->_M_next(), __bkt_count);
2793 if (__next_bkt != __prev_bkt)
2794 __new_buckets[__next_bkt] = __prev_p;
2796 __check_bucket =
false;
2799 if (!__new_buckets[__bkt])
2801 __p->_M_nxt = _M_before_begin._M_nxt;
2802 _M_before_begin._M_nxt = __p;
2803 __new_buckets[__bkt] = &_M_before_begin;
2805 __new_buckets[__bbegin_bkt] = __p;
2806 __bbegin_bkt = __bkt;
2810 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2811 __new_buckets[__bkt]->_M_nxt = __p;
2819 if (__check_bucket && __prev_p->_M_nxt)
2821 std::size_t __next_bkt
2822 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2824 if (__next_bkt != __prev_bkt)
2825 __new_buckets[__next_bkt] = __prev_p;
2828 _M_deallocate_buckets();
2829 _M_bucket_count = __bkt_count;
2830 _M_buckets = __new_buckets;
2833#pragma GCC diagnostic push
2834#pragma GCC diagnostic ignored "-Wc++17-extensions"
2839 template<
typename _Key,
typename _Value,
typename _Alloc,
2840 typename _ExtractKey,
typename _Equal,
2841 typename _Hash,
typename _RangeHash,
typename _Unused,
2842 typename _RehashPolicy,
typename _Traits>
2844 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2845 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2846 _M_equal(
const _Hashtable& __other)
const
2848 if (
size() != __other.size())
2851 if constexpr (__unique_keys::value)
2852 for (
auto __x_n = _M_begin(); __x_n; __x_n = __x_n->_M_next())
2854 std::size_t __ybkt = __other._M_bucket_index(*__x_n);
2855 auto __prev_n = __other._M_buckets[__ybkt];
2859 for (__node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);;
2860 __n = __n->_M_next())
2862 if (__n->_M_v() == __x_n->_M_v())
2866 || __other._M_bucket_index(*__n->_M_next()) != __ybkt)
2871 for (
auto __x_n = _M_begin(); __x_n;)
2873 std::size_t __x_count = 1;
2874 auto __x_n_end = __x_n->_M_next();
2876 && key_eq()(_ExtractKey{}(__x_n->_M_v()),
2877 _ExtractKey{}(__x_n_end->_M_v()));
2878 __x_n_end = __x_n_end->_M_next())
2881 std::size_t __ybkt = __other._M_bucket_index(*__x_n);
2882 auto __y_prev_n = __other._M_buckets[__ybkt];
2886 __node_ptr __y_n =
static_cast<__node_ptr
>(__y_prev_n->_M_nxt);
2889 if (key_eq()(_ExtractKey{}(__y_n->_M_v()),
2890 _ExtractKey{}(__x_n->_M_v())))
2893 auto __y_ref_n = __y_n;
2894 for (__y_n = __y_n->_M_next(); __y_n; __y_n = __y_n->_M_next())
2895 if (!__other._M_node_equals(*__y_ref_n, *__y_n))
2898 if (!__y_n || __other._M_bucket_index(*__y_n) != __ybkt)
2902 auto __y_n_end = __y_n;
2903 for (; __y_n_end; __y_n_end = __y_n_end->_M_next())
2904 if (--__x_count == 0)
2910 const_iterator __itx(__x_n), __itx_end(__x_n_end);
2911 const_iterator __ity(__y_n);
2912 if (!std::is_permutation(__itx, __itx_end, __ity))
2920#pragma GCC diagnostic pop
2922#if __cplusplus > 201402L
2923 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2926#if __cpp_deduction_guides >= 201606
2928 template<
typename _Hash>
2929 using _RequireNotAllocatorOrIntegral
2930 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2934_GLIBCXX_END_NAMESPACE_VERSION
2937#pragma GCC diagnostic pop
__bool_constant< true > true_type
The type used as a compile-time boolean with true value.
constexpr tuple< _Elements &&... > forward_as_tuple(_Elements &&... __args) noexcept
Create a tuple of lvalue or rvalue references to the arguments.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr piecewise_construct_t piecewise_construct
Tag for piecewise construction of std::pair objects.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
_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.