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>;
177 template<
typename _Key,
typename _Value,
typename _Alloc,
178 typename _ExtractKey,
typename _Equal,
179 typename _Hash,
typename _RangeHash,
typename _Unused,
180 typename _RehashPolicy,
typename _Traits>
182 :
public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
183 _Hash, _RangeHash, _Unused, _Traits>,
184 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
185 _Hash, _RangeHash, _Unused,
186 _RehashPolicy, _Traits>,
187 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
188 _Hash, _RangeHash, _Unused,
189 _RehashPolicy, _Traits>,
190 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
191 _Hash, _RangeHash, _Unused,
192 _RehashPolicy, _Traits>,
193 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
194 _Hash, _RangeHash, _Unused,
195 _RehashPolicy, _Traits>,
196 private __detail::_Hashtable_alloc<
197 __alloc_rebind<_Alloc,
198 __detail::_Hash_node<_Value,
199 _Traits::__hash_cached::value>>>,
200 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
202 static_assert(is_same<typename remove_cv<_Value>::type, _Value>::value,
203 "unordered container must have a non-const, non-volatile value_type");
204#if __cplusplus > 201703L || defined __STRICT_ANSI__
205 static_assert(is_same<typename _Alloc::value_type, _Value>{},
206 "unordered container must have the same value_type as its allocator");
209 using __traits_type = _Traits;
210 using __hash_cached =
typename __traits_type::__hash_cached;
211 using __constant_iterators =
typename __traits_type::__constant_iterators;
212 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
213 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
215 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
217 using __node_value_type =
218 __detail::_Hash_node_value<_Value, __hash_cached::value>;
219 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
220 using __value_alloc_traits =
221 typename __hashtable_alloc::__value_alloc_traits;
222 using __node_alloc_traits =
223 typename __hashtable_alloc::__node_alloc_traits;
224 using __node_base =
typename __hashtable_alloc::__node_base;
225 using __node_base_ptr =
typename __hashtable_alloc::__node_base_ptr;
226 using __buckets_ptr =
typename __hashtable_alloc::__buckets_ptr;
228 using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
231 _RehashPolicy, _Traits>;
232 using __enable_default_ctor
233 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
236 typedef _Key key_type;
237 typedef _Value value_type;
238 typedef _Alloc allocator_type;
239 typedef _Equal key_equal;
243 typedef typename __value_alloc_traits::pointer pointer;
244 typedef typename __value_alloc_traits::const_pointer const_pointer;
245 typedef value_type& reference;
246 typedef const value_type& const_reference;
248 using iterator =
typename __insert_base::iterator;
250 using const_iterator =
typename __insert_base::const_iterator;
252 using local_iterator = __detail::_Local_iterator<key_type, _Value,
253 _ExtractKey, _Hash, _RangeHash, _Unused,
254 __constant_iterators::value,
255 __hash_cached::value>;
257 using const_local_iterator = __detail::_Local_const_iterator<
259 _ExtractKey, _Hash, _RangeHash, _Unused,
260 __constant_iterators::value, __hash_cached::value>;
263 using __rehash_type = _RehashPolicy;
264 using __rehash_state =
typename __rehash_type::_State;
266 using __unique_keys =
typename __traits_type::__unique_keys;
268 using __hashtable_base = __detail::
269 _Hashtable_base<_Key, _Value, _ExtractKey,
270 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
272 using __hash_code_base =
typename __hashtable_base::__hash_code_base;
273 using __hash_code =
typename __hashtable_base::__hash_code;
274 using __ireturn_type =
typename __insert_base::__ireturn_type;
276 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
277 _Equal, _Hash, _RangeHash, _Unused,
278 _RehashPolicy, _Traits>;
280 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
282 _Hash, _RangeHash, _Unused,
283 _RehashPolicy, _Traits>;
285 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
286 _Equal, _Hash, _RangeHash, _Unused,
287 _RehashPolicy, _Traits>;
289 using __reuse_or_alloc_node_gen_t =
290 __detail::_ReuseOrAllocNode<__node_alloc_type>;
291 using __alloc_node_gen_t =
292 __detail::_AllocNode<__node_alloc_type>;
293 using __node_builder_t =
294 __detail::_NodeBuilder<_ExtractKey>;
300 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
301 : _M_h(__h), _M_node(__n) { }
304 template<
typename... _Args>
305 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
307 _M_node(__h->_M_allocate_node(
std::
forward<_Args>(__args)...))
311 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
313 _Scoped_node(
const _Scoped_node&) =
delete;
314 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
316 __hashtable_alloc* _M_h;
320 template<
typename _Ht>
322 __conditional_t<std::is_lvalue_reference<_Ht>::value,
323 const value_type&, value_type&&>
324 __fwd_value_for(value_type& __val)
noexcept
331 struct __hash_code_base_access : __hash_code_base
332 {
using __hash_code_base::_M_bucket_index; };
335 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
336 "Functor used to map hash code to bucket index"
337 " must be nothrow default constructible");
338 static_assert(
noexcept(
339 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
340 "Functor used to map hash code to bucket index must be"
344 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
345 "_ExtractKey must be nothrow default constructible");
346 static_assert(
noexcept(
347 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
348 "_ExtractKey functor must be noexcept invocable");
350 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
351 typename _ExtractKeya,
typename _Equala,
352 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
353 typename _RehashPolicya,
typename _Traitsa,
355 friend struct __detail::_Map_base;
357 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
358 typename _ExtractKeya,
typename _Equala,
359 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
360 typename _RehashPolicya,
typename _Traitsa>
361 friend struct __detail::_Insert_base;
363 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
364 typename _ExtractKeya,
typename _Equala,
365 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
366 typename _RehashPolicya,
typename _Traitsa,
367 bool _Constant_iteratorsa>
368 friend struct __detail::_Insert;
370 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
371 typename _ExtractKeya,
typename _Equala,
372 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
373 typename _RehashPolicya,
typename _Traitsa,
375 friend struct __detail::_Equality;
378 using size_type =
typename __hashtable_base::size_type;
379 using difference_type =
typename __hashtable_base::difference_type;
381#if __cplusplus > 201402L
382 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
383 using insert_return_type = _Node_insert_return<iterator, node_type>;
387 __buckets_ptr _M_buckets = &_M_single_bucket;
388 size_type _M_bucket_count = 1;
389 __node_base _M_before_begin;
390 size_type _M_element_count = 0;
391 _RehashPolicy _M_rehash_policy;
399 __node_base_ptr _M_single_bucket =
nullptr;
405 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
409 _M_update_bbegin(__node_ptr __n)
411 _M_before_begin._M_nxt = __n;
416 _M_uses_single_bucket(__buckets_ptr __bkts)
const
417 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
420 _M_uses_single_bucket()
const
421 {
return _M_uses_single_bucket(_M_buckets); }
423 static constexpr size_t
424 __small_size_threshold() noexcept
427 __detail::_Hashtable_hash_traits<_Hash>::__small_size_threshold();
431 _M_base_alloc() {
return *
this; }
434 _M_allocate_buckets(size_type __bkt_count)
436 if (__builtin_expect(__bkt_count == 1,
false))
438 _M_single_bucket =
nullptr;
439 return &_M_single_bucket;
442 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
446 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
448 if (_M_uses_single_bucket(__bkts))
451 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
455 _M_deallocate_buckets()
456 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
461 _M_bucket_begin(size_type __bkt)
const;
465 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
469 template<
typename _Ht>
471 _M_assign_elements(_Ht&&);
473 template<
typename _Ht,
typename _NodeGenerator>
475 _M_assign(_Ht&&,
const _NodeGenerator&);
478 _M_move_assign(_Hashtable&&, true_type);
481 _M_move_assign(_Hashtable&&, false_type);
486 _Hashtable(const _Hash& __h, const _Equal& __eq,
487 const allocator_type& __a)
488 : __hashtable_base(__h, __eq),
489 __hashtable_alloc(__node_alloc_type(__a)),
490 __enable_default_ctor(_Enable_default_constructor_tag{})
493 template<
bool _No_realloc = true>
494 static constexpr bool
497#if __cplusplus <= 201402L
498 return __and_<__bool_constant<_No_realloc>,
499 is_nothrow_copy_constructible<_Hash>,
500 is_nothrow_copy_constructible<_Equal>>::value;
502 if constexpr (_No_realloc)
503 if constexpr (is_nothrow_copy_constructible<_Hash>())
504 return is_nothrow_copy_constructible<_Equal>();
509 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
511 noexcept(_S_nothrow_move());
513 _Hashtable(_Hashtable&&, __node_alloc_type&&,
516 template<
typename _InputIterator>
517 _Hashtable(_InputIterator __first, _InputIterator __last,
518 size_type __bkt_count_hint,
519 const _Hash&,
const _Equal&,
const allocator_type&,
522 template<
typename _InputIterator>
523 _Hashtable(_InputIterator __first, _InputIterator __last,
524 size_type __bkt_count_hint,
525 const _Hash&,
const _Equal&,
const allocator_type&,
530 _Hashtable() =
default;
532 _Hashtable(
const _Hashtable&);
534 _Hashtable(
const _Hashtable&,
const allocator_type&);
537 _Hashtable(size_type __bkt_count_hint,
538 const _Hash& __hf = _Hash(),
539 const key_equal& __eql = key_equal(),
540 const allocator_type& __a = allocator_type());
543 _Hashtable(_Hashtable&& __ht)
544 noexcept(_S_nothrow_move())
549 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
550 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
551 : _Hashtable(
std::move(__ht), __node_alloc_type(__a),
552 typename __node_alloc_traits::is_always_equal{})
556 _Hashtable(
const allocator_type& __a)
557 : __hashtable_alloc(__node_alloc_type(__a)),
558 __enable_default_ctor(_Enable_default_constructor_tag{})
561 template<
typename _InputIterator>
562 _Hashtable(_InputIterator __f, _InputIterator __l,
563 size_type __bkt_count_hint = 0,
564 const _Hash& __hf = _Hash(),
565 const key_equal& __eql = key_equal(),
566 const allocator_type& __a = allocator_type())
567 : _Hashtable(__f, __l, __bkt_count_hint, __hf, __eql, __a,
571 _Hashtable(initializer_list<value_type> __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(__l.begin(), __l.end(), __bkt_count_hint,
577 __hf, __eql, __a, __unique_keys{})
581 operator=(
const _Hashtable& __ht);
584 operator=(_Hashtable&& __ht)
585 noexcept(__node_alloc_traits::_S_nothrow_move()
586 && is_nothrow_move_assignable<_Hash>::value
587 && is_nothrow_move_assignable<_Equal>::value)
589 constexpr bool __move_storage =
590 __node_alloc_traits::_S_propagate_on_move_assign()
591 || __node_alloc_traits::_S_always_equal();
592 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
597 operator=(initializer_list<value_type> __l)
599 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
600 _M_before_begin._M_nxt =
nullptr;
604 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
607 if (_M_bucket_count < __l_bkt_count)
608 rehash(__l_bkt_count);
610 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
614 ~_Hashtable() noexcept;
618 noexcept(__and_<__is_nothrow_swappable<_Hash>,
619 __is_nothrow_swappable<_Equal>>::value);
624 {
return iterator(_M_begin()); }
627 begin() const noexcept
628 {
return const_iterator(_M_begin()); }
632 {
return iterator(
nullptr); }
636 {
return const_iterator(
nullptr); }
639 cbegin() const noexcept
640 {
return const_iterator(_M_begin()); }
643 cend() const noexcept
644 {
return const_iterator(
nullptr); }
647 size() const noexcept
648 {
return _M_element_count; }
650 _GLIBCXX_NODISCARD
bool
651 empty() const noexcept
652 {
return size() == 0; }
655 get_allocator() const noexcept
656 {
return allocator_type(this->_M_node_allocator()); }
659 max_size() const noexcept
660 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
665 {
return this->_M_eq(); }
671 bucket_count() const noexcept
672 {
return _M_bucket_count; }
675 max_bucket_count() const noexcept
676 {
return max_size(); }
679 bucket_size(size_type __bkt)
const
683 bucket(
const key_type& __k)
const
684 {
return _M_bucket_index(this->_M_hash_code(__k)); }
687 begin(size_type __bkt)
689 return local_iterator(*
this, _M_bucket_begin(__bkt),
690 __bkt, _M_bucket_count);
695 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
698 begin(size_type __bkt)
const
700 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
701 __bkt, _M_bucket_count);
705 end(size_type __bkt)
const
706 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
710 cbegin(size_type __bkt)
const
712 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
713 __bkt, _M_bucket_count);
717 cend(size_type __bkt)
const
718 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
721 load_factor() const noexcept
723 return static_cast<float>(size()) /
static_cast<float>(bucket_count());
732 __rehash_policy()
const
733 {
return _M_rehash_policy; }
736 __rehash_policy(
const _RehashPolicy& __pol)
737 { _M_rehash_policy = __pol; }
741 find(
const key_type& __k);
744 find(
const key_type& __k)
const;
747 count(
const key_type& __k)
const;
750 equal_range(
const key_type& __k);
753 equal_range(
const key_type& __k)
const;
755#if __cplusplus >= 202002L
756#define __cpp_lib_generic_unordered_lookup 201811L
758 template<
typename _Kt,
759 typename = __has_is_transparent_t<_Hash, _Kt>,
760 typename = __has_is_transparent_t<_Equal, _Kt>>
762 _M_find_tr(
const _Kt& __k);
764 template<
typename _Kt,
765 typename = __has_is_transparent_t<_Hash, _Kt>,
766 typename = __has_is_transparent_t<_Equal, _Kt>>
768 _M_find_tr(
const _Kt& __k)
const;
770 template<
typename _Kt,
771 typename = __has_is_transparent_t<_Hash, _Kt>,
772 typename = __has_is_transparent_t<_Equal, _Kt>>
774 _M_count_tr(
const _Kt& __k)
const;
776 template<
typename _Kt,
777 typename = __has_is_transparent_t<_Hash, _Kt>,
778 typename = __has_is_transparent_t<_Equal, _Kt>>
779 pair<iterator, iterator>
780 _M_equal_range_tr(
const _Kt& __k);
782 template<
typename _Kt,
783 typename = __has_is_transparent_t<_Hash, _Kt>,
784 typename = __has_is_transparent_t<_Equal, _Kt>>
785 pair<const_iterator, const_iterator>
786 _M_equal_range_tr(
const _Kt& __k)
const;
792 _M_bucket_index(
const __node_value_type& __n)
const noexcept
793 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
796 _M_bucket_index(__hash_code __c)
const
797 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
800 _M_find_before_node(
const key_type&);
805 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
807 template<
typename _Kt>
809 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
812 _M_find_node(size_type __bkt,
const key_type& __key,
813 __hash_code __c)
const
815 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
817 return static_cast<__node_ptr
>(__before_n->_M_nxt);
821 template<
typename _Kt>
823 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
824 __hash_code __c)
const
826 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
828 return static_cast<__node_ptr
>(__before_n->_M_nxt);
834 _M_insert_bucket_begin(size_type, __node_ptr);
838 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
839 size_type __next_bkt);
843 _M_get_previous_node(size_type __bkt, __node_ptr __n);
845 pair<const_iterator, __hash_code>
846 _M_compute_hash_code(const_iterator __hint,
const key_type& __k)
const;
852 _M_insert_unique_node(size_type __bkt, __hash_code,
853 __node_ptr __n, size_type __n_elt = 1);
858 _M_insert_multi_node(__node_ptr __hint,
859 __hash_code __code, __node_ptr __n);
861 template<
typename... _Args>
863 _M_emplace(true_type __uks, _Args&&... __args);
865 template<
typename... _Args>
867 _M_emplace(false_type __uks, _Args&&... __args)
868 {
return _M_emplace(cend(), __uks, std::forward<_Args>(__args)...); }
871 template<
typename... _Args>
873 _M_emplace(const_iterator, true_type __uks, _Args&&... __args)
874 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
876 template<
typename... _Args>
878 _M_emplace(const_iterator, false_type __uks, _Args&&... __args);
880 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
882 _M_insert_unique(_Kt&&, _Arg&&,
const _NodeGenerator&);
884 template<
typename _Kt>
885 static __conditional_t<
886 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
887 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
889 _S_forward_key(_Kt&& __k)
890 {
return std::forward<_Kt>(__k); }
892 static const key_type&
893 _S_forward_key(
const key_type& __k)
897 _S_forward_key(key_type&& __k)
900 template<
typename _Arg,
typename _NodeGenerator>
902 _M_insert_unique_aux(_Arg&& __arg,
const _NodeGenerator& __node_gen)
904 return _M_insert_unique(
905 _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
906 std::forward<_Arg>(__arg), __node_gen);
909 template<
typename _Arg,
typename _NodeGenerator>
911 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
915 = __detail::_ConvertToValueType<_ExtractKey, value_type>;
916 return _M_insert_unique_aux(
917 __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
920 template<
typename _Arg,
typename _NodeGenerator>
922 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
926 = __detail::_ConvertToValueType<_ExtractKey, value_type>;
927 return _M_insert(cend(),
928 __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
932 template<
typename _Arg,
typename _NodeGenerator>
934 _M_insert(const_iterator, _Arg&& __arg,
935 const _NodeGenerator& __node_gen, true_type __uks)
938 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
942 template<
typename _Arg,
typename _NodeGenerator>
944 _M_insert(const_iterator, _Arg&&,
945 const _NodeGenerator&, false_type __uks);
948 _M_erase(true_type __uks,
const key_type&);
951 _M_erase(false_type __uks,
const key_type&);
954 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
958 template<
typename... _Args>
960 emplace(_Args&&... __args)
961 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
963 template<
typename... _Args>
965 emplace_hint(const_iterator __hint, _Args&&... __args)
967 return _M_emplace(__hint, __unique_keys{},
968 std::forward<_Args>(__args)...);
975 erase(const_iterator);
980 {
return erase(const_iterator(__it)); }
983 erase(
const key_type& __k)
984 {
return _M_erase(__unique_keys{}, __k); }
987 erase(const_iterator, const_iterator);
994 void rehash(size_type __bkt_count);
999#if __cplusplus > 201402L
1002 _M_reinsert_node(node_type&& __nh)
1004 insert_return_type __ret;
1006 __ret.position = end();
1009 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1011 const key_type& __k = __nh._M_key();
1012 __hash_code __code = this->_M_hash_code(__k);
1013 size_type __bkt = _M_bucket_index(__code);
1014 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
1017 __ret.position = iterator(__n);
1018 __ret.inserted =
false;
1023 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
1024 __nh._M_ptr =
nullptr;
1025 __ret.inserted =
true;
1033 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1038 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1040 const key_type& __k = __nh._M_key();
1041 auto __code = this->_M_hash_code(__k);
1043 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1044 __nh._M_ptr =
nullptr;
1050 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1052 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1053 if (__prev_n == _M_buckets[__bkt])
1054 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1055 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1056 else if (__n->_M_nxt)
1058 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1059 if (__next_bkt != __bkt)
1060 _M_buckets[__next_bkt] = __prev_n;
1063 __prev_n->_M_nxt = __n->_M_nxt;
1064 __n->_M_nxt =
nullptr;
1066 return { __n, this->_M_node_allocator() };
1071 template<
typename _H2>
1073 _M_src_hash_code(
const _H2&,
const key_type& __k,
1074 const __node_value_type& __src_n)
const
1076 if constexpr (std::is_same_v<_H2, _Hash>)
1077 if constexpr (std::is_empty_v<_Hash>)
1078 return this->_M_hash_code(__src_n);
1080 return this->_M_hash_code(__k);
1086 extract(const_iterator __pos)
1088 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1089 return _M_extract_node(__bkt,
1090 _M_get_previous_node(__bkt, __pos._M_cur));
1095 extract(
const _Key& __k)
1098 __hash_code __code = this->_M_hash_code(__k);
1099 std::size_t __bkt = _M_bucket_index(__code);
1100 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1101 __nh = _M_extract_node(__bkt, __prev_node);
1106 template<
typename _Compatible_Hashtable>
1108 _M_merge_unique(_Compatible_Hashtable& __src)
1110 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1111 node_type>,
"Node types are compatible");
1112 __glibcxx_assert(get_allocator() == __src.get_allocator());
1114 auto __n_elt = __src.size();
1115 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1118 const key_type& __k = _ExtractKey{}(*__pos);
1120 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1121 size_type __bkt = _M_bucket_index(__code);
1122 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1124 auto __nh = __src.extract(__pos);
1125 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1126 __nh._M_ptr =
nullptr;
1129 else if (__n_elt != 1)
1135 template<
typename _Compatible_Hashtable>
1137 _M_merge_multi(_Compatible_Hashtable& __src)
1139 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1140 node_type>,
"Node types are compatible");
1141 __glibcxx_assert(get_allocator() == __src.get_allocator());
1143 __node_ptr __hint =
nullptr;
1144 this->reserve(size() + __src.size());
1145 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1148 const key_type& __k = _ExtractKey{}(*__pos);
1150 = _M_src_hash_code(__src.hash_function(), __k, *__pos._M_cur);
1151 auto __nh = __src.extract(__pos);
1152 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1153 __nh._M_ptr =
nullptr;
1160 void _M_rehash_aux(size_type __bkt_count, true_type __uks);
1163 void _M_rehash_aux(size_type __bkt_count, false_type __uks);
1167 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1171 template<
typename _Key,
typename _Value,
typename _Alloc,
1172 typename _ExtractKey,
typename _Equal,
1173 typename _Hash,
typename _RangeHash,
typename _Unused,
1174 typename _RehashPolicy,
typename _Traits>
1176 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1177 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1178 _M_bucket_begin(size_type __bkt)
const
1181 __node_base_ptr __n = _M_buckets[__bkt];
1182 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
1185 template<
typename _Key,
typename _Value,
typename _Alloc,
1186 typename _ExtractKey,
typename _Equal,
1187 typename _Hash,
typename _RangeHash,
typename _Unused,
1188 typename _RehashPolicy,
typename _Traits>
1189 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1190 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1191 _Hashtable(size_type __bkt_count_hint,
1192 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1193 : _Hashtable(__h, __eq, __a)
1195 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1196 if (__bkt_count > _M_bucket_count)
1198 _M_buckets = _M_allocate_buckets(__bkt_count);
1199 _M_bucket_count = __bkt_count;
1203 template<
typename _Key,
typename _Value,
typename _Alloc,
1204 typename _ExtractKey,
typename _Equal,
1205 typename _Hash,
typename _RangeHash,
typename _Unused,
1206 typename _RehashPolicy,
typename _Traits>
1207 template<
typename _InputIterator>
1208 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1209 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1210 _Hashtable(_InputIterator __f, _InputIterator __l,
1211 size_type __bkt_count_hint,
1212 const _Hash& __h,
const _Equal& __eq,
1213 const allocator_type& __a, true_type )
1214 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1215 { this->insert(__f, __l); }
1217 template<
typename _Key,
typename _Value,
typename _Alloc,
1218 typename _ExtractKey,
typename _Equal,
1219 typename _Hash,
typename _RangeHash,
typename _Unused,
1220 typename _RehashPolicy,
typename _Traits>
1221 template<
typename _InputIterator>
1222 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1223 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1224 _Hashtable(_InputIterator __f, _InputIterator __l,
1225 size_type __bkt_count_hint,
1226 const _Hash& __h,
const _Equal& __eq,
1227 const allocator_type& __a, false_type __uks)
1228 : _Hashtable(__h, __eq, __a)
1230 auto __nb_elems = __detail::__distance_fw(__f, __l);
1232 _M_rehash_policy._M_next_bkt(
1233 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1236 if (__bkt_count > _M_bucket_count)
1238 _M_buckets = _M_allocate_buckets(__bkt_count);
1239 _M_bucket_count = __bkt_count;
1242 __alloc_node_gen_t __node_gen(*
this);
1243 for (; __f != __l; ++__f)
1244 _M_insert(*__f, __node_gen, __uks);
1247 template<
typename _Key,
typename _Value,
typename _Alloc,
1248 typename _ExtractKey,
typename _Equal,
1249 typename _Hash,
typename _RangeHash,
typename _Unused,
1250 typename _RehashPolicy,
typename _Traits>
1252 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1253 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1254 operator=(
const _Hashtable& __ht)
1260 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1262 auto& __this_alloc = this->_M_node_allocator();
1263 auto& __that_alloc = __ht._M_node_allocator();
1264 if (!__node_alloc_traits::_S_always_equal()
1265 && __this_alloc != __that_alloc)
1268 this->_M_deallocate_nodes(_M_begin());
1269 _M_before_begin._M_nxt =
nullptr;
1270 _M_deallocate_buckets();
1271 _M_buckets =
nullptr;
1272 std::__alloc_on_copy(__this_alloc, __that_alloc);
1273 __hashtable_base::operator=(__ht);
1274 _M_bucket_count = __ht._M_bucket_count;
1275 _M_element_count = __ht._M_element_count;
1276 _M_rehash_policy = __ht._M_rehash_policy;
1277 __alloc_node_gen_t __alloc_node_gen(*
this);
1280 _M_assign(__ht, __alloc_node_gen);
1287 __throw_exception_again;
1291 std::__alloc_on_copy(__this_alloc, __that_alloc);
1295 _M_assign_elements(__ht);
1299 template<
typename _Key,
typename _Value,
typename _Alloc,
1300 typename _ExtractKey,
typename _Equal,
1301 typename _Hash,
typename _RangeHash,
typename _Unused,
1302 typename _RehashPolicy,
typename _Traits>
1303 template<
typename _Ht>
1305 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1306 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1307 _M_assign_elements(_Ht&& __ht)
1309 __buckets_ptr __former_buckets =
nullptr;
1310 std::size_t __former_bucket_count = _M_bucket_count;
1311 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1313 if (_M_bucket_count != __ht._M_bucket_count)
1315 __former_buckets = _M_buckets;
1316 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1317 _M_bucket_count = __ht._M_bucket_count;
1320 __builtin_memset(_M_buckets, 0,
1321 _M_bucket_count *
sizeof(__node_base_ptr));
1325 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1326 _M_element_count = __ht._M_element_count;
1327 _M_rehash_policy = __ht._M_rehash_policy;
1328 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1329 _M_before_begin._M_nxt =
nullptr;
1330 _M_assign(std::forward<_Ht>(__ht), __roan);
1331 if (__former_buckets)
1332 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1336 if (__former_buckets)
1339 _M_deallocate_buckets();
1340 _M_rehash_policy._M_reset(__former_state);
1341 _M_buckets = __former_buckets;
1342 _M_bucket_count = __former_bucket_count;
1344 __builtin_memset(_M_buckets, 0,
1345 _M_bucket_count *
sizeof(__node_base_ptr));
1346 __throw_exception_again;
1350 template<
typename _Key,
typename _Value,
typename _Alloc,
1351 typename _ExtractKey,
typename _Equal,
1352 typename _Hash,
typename _RangeHash,
typename _Unused,
1353 typename _RehashPolicy,
typename _Traits>
1354 template<
typename _Ht,
typename _NodeGenerator>
1356 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1357 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1358 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1360 __buckets_ptr __buckets =
nullptr;
1362 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1366 if (!__ht._M_before_begin._M_nxt)
1371 __node_ptr __ht_n = __ht._M_begin();
1373 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1374 this->_M_copy_code(*__this_n, *__ht_n);
1375 _M_update_bbegin(__this_n);
1378 __node_ptr __prev_n = __this_n;
1379 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1381 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1382 __prev_n->_M_nxt = __this_n;
1383 this->_M_copy_code(*__this_n, *__ht_n);
1384 size_type __bkt = _M_bucket_index(*__this_n);
1385 if (!_M_buckets[__bkt])
1386 _M_buckets[__bkt] = __prev_n;
1387 __prev_n = __this_n;
1394 _M_deallocate_buckets();
1395 __throw_exception_again;
1399 template<
typename _Key,
typename _Value,
typename _Alloc,
1400 typename _ExtractKey,
typename _Equal,
1401 typename _Hash,
typename _RangeHash,
typename _Unused,
1402 typename _RehashPolicy,
typename _Traits>
1404 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1405 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1408 _M_rehash_policy._M_reset();
1409 _M_bucket_count = 1;
1410 _M_single_bucket =
nullptr;
1411 _M_buckets = &_M_single_bucket;
1412 _M_before_begin._M_nxt =
nullptr;
1413 _M_element_count = 0;
1416 template<
typename _Key,
typename _Value,
typename _Alloc,
1417 typename _ExtractKey,
typename _Equal,
1418 typename _Hash,
typename _RangeHash,
typename _Unused,
1419 typename _RehashPolicy,
typename _Traits>
1421 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1422 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1423 _M_move_assign(_Hashtable&& __ht, true_type)
1428 this->_M_deallocate_nodes(_M_begin());
1429 _M_deallocate_buckets();
1430 __hashtable_base::operator=(
std::move(__ht));
1431 _M_rehash_policy = __ht._M_rehash_policy;
1432 if (!__ht._M_uses_single_bucket())
1433 _M_buckets = __ht._M_buckets;
1436 _M_buckets = &_M_single_bucket;
1437 _M_single_bucket = __ht._M_single_bucket;
1440 _M_bucket_count = __ht._M_bucket_count;
1441 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1442 _M_element_count = __ht._M_element_count;
1443 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1450 template<
typename _Key,
typename _Value,
typename _Alloc,
1451 typename _ExtractKey,
typename _Equal,
1452 typename _Hash,
typename _RangeHash,
typename _Unused,
1453 typename _RehashPolicy,
typename _Traits>
1455 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1456 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1457 _M_move_assign(_Hashtable&& __ht, false_type)
1459 if (__ht._M_node_allocator() == this->_M_node_allocator())
1460 _M_move_assign(
std::move(__ht), true_type{});
1469 template<
typename _Key,
typename _Value,
typename _Alloc,
1470 typename _ExtractKey,
typename _Equal,
1471 typename _Hash,
typename _RangeHash,
typename _Unused,
1472 typename _RehashPolicy,
typename _Traits>
1473 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1474 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1475 _Hashtable(
const _Hashtable& __ht)
1476 : __hashtable_base(__ht),
1478 __rehash_base(__ht),
1480 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1481 __enable_default_ctor(__ht),
1482 _M_buckets(nullptr),
1483 _M_bucket_count(__ht._M_bucket_count),
1484 _M_element_count(__ht._M_element_count),
1485 _M_rehash_policy(__ht._M_rehash_policy)
1487 __alloc_node_gen_t __alloc_node_gen(*
this);
1488 _M_assign(__ht, __alloc_node_gen);
1491 template<
typename _Key,
typename _Value,
typename _Alloc,
1492 typename _ExtractKey,
typename _Equal,
1493 typename _Hash,
typename _RangeHash,
typename _Unused,
1494 typename _RehashPolicy,
typename _Traits>
1495 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1496 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1497 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1499 noexcept(_S_nothrow_move())
1500 : __hashtable_base(__ht),
1502 __rehash_base(__ht),
1504 __enable_default_ctor(__ht),
1505 _M_buckets(__ht._M_buckets),
1506 _M_bucket_count(__ht._M_bucket_count),
1507 _M_before_begin(__ht._M_before_begin._M_nxt),
1508 _M_element_count(__ht._M_element_count),
1509 _M_rehash_policy(__ht._M_rehash_policy)
1512 if (__ht._M_uses_single_bucket())
1514 _M_buckets = &_M_single_bucket;
1515 _M_single_bucket = __ht._M_single_bucket;
1524 template<
typename _Key,
typename _Value,
typename _Alloc,
1525 typename _ExtractKey,
typename _Equal,
1526 typename _Hash,
typename _RangeHash,
typename _Unused,
1527 typename _RehashPolicy,
typename _Traits>
1528 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1529 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1530 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1531 : __hashtable_base(__ht),
1533 __rehash_base(__ht),
1534 __hashtable_alloc(__node_alloc_type(__a)),
1535 __enable_default_ctor(__ht),
1537 _M_bucket_count(__ht._M_bucket_count),
1538 _M_element_count(__ht._M_element_count),
1539 _M_rehash_policy(__ht._M_rehash_policy)
1541 __alloc_node_gen_t __alloc_node_gen(*
this);
1542 _M_assign(__ht, __alloc_node_gen);
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 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1550 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1551 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1553 : __hashtable_base(__ht),
1555 __rehash_base(__ht),
1556 __hashtable_alloc(
std::move(__a)),
1557 __enable_default_ctor(__ht),
1558 _M_buckets(nullptr),
1559 _M_bucket_count(__ht._M_bucket_count),
1560 _M_element_count(__ht._M_element_count),
1561 _M_rehash_policy(__ht._M_rehash_policy)
1563 if (__ht._M_node_allocator() == this->_M_node_allocator())
1565 if (__ht._M_uses_single_bucket())
1567 _M_buckets = &_M_single_bucket;
1568 _M_single_bucket = __ht._M_single_bucket;
1571 _M_buckets = __ht._M_buckets;
1575 _M_update_bbegin(__ht._M_begin());
1581 __alloc_node_gen_t __alloc_gen(*
this);
1583 using _Fwd_Ht = __conditional_t<
1584 __move_if_noexcept_cond<value_type>::value,
1585 const _Hashtable&, _Hashtable&&>;
1586 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1591 template<
typename _Key,
typename _Value,
typename _Alloc,
1592 typename _ExtractKey,
typename _Equal,
1593 typename _Hash,
typename _RangeHash,
typename _Unused,
1594 typename _RehashPolicy,
typename _Traits>
1595 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1596 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1597 ~_Hashtable() noexcept
1602 static_assert(
noexcept(declval<const __hash_code_base_access&>()
1603 ._M_bucket_index(declval<const __node_value_type&>(),
1605 "Cache the hash code or qualify your functors involved"
1606 " in hash code and bucket index computation with noexcept");
1609 _M_deallocate_buckets();
1612 template<
typename _Key,
typename _Value,
typename _Alloc,
1613 typename _ExtractKey,
typename _Equal,
1614 typename _Hash,
typename _RangeHash,
typename _Unused,
1615 typename _RehashPolicy,
typename _Traits>
1617 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1618 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1619 swap(_Hashtable& __x)
1620 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1621 __is_nothrow_swappable<_Equal>>::value)
1628 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1629 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1632 if (this->_M_uses_single_bucket())
1634 if (!__x._M_uses_single_bucket())
1636 _M_buckets = __x._M_buckets;
1637 __x._M_buckets = &__x._M_single_bucket;
1640 else if (__x._M_uses_single_bucket())
1642 __x._M_buckets = _M_buckets;
1643 _M_buckets = &_M_single_bucket;
1648 std::swap(_M_bucket_count, __x._M_bucket_count);
1649 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1650 std::swap(_M_element_count, __x._M_element_count);
1651 std::swap(_M_single_bucket, __x._M_single_bucket);
1656 __x._M_update_bbegin();
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 find(
const key_type& __k)
1669 if (size() <= __small_size_threshold())
1671 for (
auto __it = begin(); __it != end(); ++__it)
1672 if (this->_M_key_equals(__k, *__it._M_cur))
1677 __hash_code __code = this->_M_hash_code(__k);
1678 std::size_t __bkt = _M_bucket_index(__code);
1679 return iterator(_M_find_node(__bkt, __k, __code));
1682 template<
typename _Key,
typename _Value,
typename _Alloc,
1683 typename _ExtractKey,
typename _Equal,
1684 typename _Hash,
typename _RangeHash,
typename _Unused,
1685 typename _RehashPolicy,
typename _Traits>
1687 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1688 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1689 find(
const key_type& __k)
const
1692 if (size() <= __small_size_threshold())
1694 for (
auto __it = begin(); __it != end(); ++__it)
1695 if (this->_M_key_equals(__k, *__it._M_cur))
1700 __hash_code __code = this->_M_hash_code(__k);
1701 std::size_t __bkt = _M_bucket_index(__code);
1702 return const_iterator(_M_find_node(__bkt, __k, __code));
1705#if __cplusplus > 201703L
1706 template<
typename _Key,
typename _Value,
typename _Alloc,
1707 typename _ExtractKey,
typename _Equal,
1708 typename _Hash,
typename _RangeHash,
typename _Unused,
1709 typename _RehashPolicy,
typename _Traits>
1710 template<
typename _Kt,
typename,
typename>
1712 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1713 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1714 _M_find_tr(
const _Kt& __k)
1717 __hash_code __code = this->_M_hash_code_tr(__k);
1718 std::size_t __bkt = _M_bucket_index(__code);
1719 return iterator(_M_find_node_tr(__bkt, __k, __code));
1722 template<
typename _Key,
typename _Value,
typename _Alloc,
1723 typename _ExtractKey,
typename _Equal,
1724 typename _Hash,
typename _RangeHash,
typename _Unused,
1725 typename _RehashPolicy,
typename _Traits>
1726 template<
typename _Kt,
typename,
typename>
1728 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1729 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1730 _M_find_tr(
const _Kt& __k)
const
1733 __hash_code __code = this->_M_hash_code_tr(__k);
1734 std::size_t __bkt = _M_bucket_index(__code);
1735 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1739 template<
typename _Key,
typename _Value,
typename _Alloc,
1740 typename _ExtractKey,
typename _Equal,
1741 typename _Hash,
typename _RangeHash,
typename _Unused,
1742 typename _RehashPolicy,
typename _Traits>
1744 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1745 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1746 count(
const key_type& __k)
const
1749 auto __it = find(__k);
1753 if (__unique_keys::value)
1759 size_type __result = 1;
1760 for (
auto __ref = __it++;
1761 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1768#if __cplusplus > 201703L
1769 template<
typename _Key,
typename _Value,
typename _Alloc,
1770 typename _ExtractKey,
typename _Equal,
1771 typename _Hash,
typename _RangeHash,
typename _Unused,
1772 typename _RehashPolicy,
typename _Traits>
1773 template<
typename _Kt,
typename,
typename>
1775 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1776 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1777 _M_count_tr(
const _Kt& __k)
const
1780 __hash_code __code = this->_M_hash_code_tr(__k);
1781 std::size_t __bkt = _M_bucket_index(__code);
1782 auto __n = _M_find_node_tr(__bkt, __k, __code);
1790 size_type __result = 1;
1792 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1800 template<
typename _Key,
typename _Value,
typename _Alloc,
1801 typename _ExtractKey,
typename _Equal,
1802 typename _Hash,
typename _RangeHash,
typename _Unused,
1803 typename _RehashPolicy,
typename _Traits>
1805 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1806 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1807 equal_range(
const key_type& __k)
1808 -> pair<iterator, iterator>
1810 auto __ite = find(__k);
1812 return { __ite, __ite };
1814 auto __beg = __ite++;
1815 if (__unique_keys::value)
1816 return { __beg, __ite };
1821 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1824 return { __beg, __ite };
1827 template<
typename _Key,
typename _Value,
typename _Alloc,
1828 typename _ExtractKey,
typename _Equal,
1829 typename _Hash,
typename _RangeHash,
typename _Unused,
1830 typename _RehashPolicy,
typename _Traits>
1832 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1833 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1834 equal_range(
const key_type& __k)
const
1835 -> pair<const_iterator, const_iterator>
1837 auto __ite = find(__k);
1839 return { __ite, __ite };
1841 auto __beg = __ite++;
1842 if (__unique_keys::value)
1843 return { __beg, __ite };
1848 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1851 return { __beg, __ite };
1854#if __cplusplus > 201703L
1855 template<
typename _Key,
typename _Value,
typename _Alloc,
1856 typename _ExtractKey,
typename _Equal,
1857 typename _Hash,
typename _RangeHash,
typename _Unused,
1858 typename _RehashPolicy,
typename _Traits>
1859 template<
typename _Kt,
typename,
typename>
1861 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1862 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1863 _M_equal_range_tr(
const _Kt& __k)
1864 -> pair<iterator, iterator>
1866 __hash_code __code = this->_M_hash_code_tr(__k);
1867 std::size_t __bkt = _M_bucket_index(__code);
1868 auto __n = _M_find_node_tr(__bkt, __k, __code);
1869 iterator __ite(__n);
1871 return { __ite, __ite };
1876 auto __beg = __ite++;
1877 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1880 return { __beg, __ite };
1883 template<
typename _Key,
typename _Value,
typename _Alloc,
1884 typename _ExtractKey,
typename _Equal,
1885 typename _Hash,
typename _RangeHash,
typename _Unused,
1886 typename _RehashPolicy,
typename _Traits>
1887 template<
typename _Kt,
typename,
typename>
1889 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1890 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1891 _M_equal_range_tr(
const _Kt& __k)
const
1892 -> pair<const_iterator, const_iterator>
1894 __hash_code __code = this->_M_hash_code_tr(__k);
1895 std::size_t __bkt = _M_bucket_index(__code);
1896 auto __n = _M_find_node_tr(__bkt, __k, __code);
1897 const_iterator __ite(__n);
1899 return { __ite, __ite };
1904 auto __beg = __ite++;
1905 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1908 return { __beg, __ite };
1914 template<
typename _Key,
typename _Value,
typename _Alloc,
1915 typename _ExtractKey,
typename _Equal,
1916 typename _Hash,
typename _RangeHash,
typename _Unused,
1917 typename _RehashPolicy,
typename _Traits>
1919 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1920 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1921 _M_find_before_node(
const key_type& __k)
1924 __node_base_ptr __prev_p = &_M_before_begin;
1925 if (!__prev_p->_M_nxt)
1928 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);
1930 __p = __p->_M_next())
1932 if (this->_M_key_equals(__k, *__p))
1943 template<
typename _Key,
typename _Value,
typename _Alloc,
1944 typename _ExtractKey,
typename _Equal,
1945 typename _Hash,
typename _RangeHash,
typename _Unused,
1946 typename _RehashPolicy,
typename _Traits>
1948 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1949 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1950 _M_find_before_node(size_type __bkt,
const key_type& __k,
1951 __hash_code __code)
const
1954 __node_base_ptr __prev_p = _M_buckets[__bkt];
1958 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1959 __p = __p->_M_next())
1961 if (this->_M_equals(__k, __code, *__p))
1964 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1972 template<
typename _Key,
typename _Value,
typename _Alloc,
1973 typename _ExtractKey,
typename _Equal,
1974 typename _Hash,
typename _RangeHash,
typename _Unused,
1975 typename _RehashPolicy,
typename _Traits>
1976 template<
typename _Kt>
1978 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1979 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1980 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1981 __hash_code __code)
const
1984 __node_base_ptr __prev_p = _M_buckets[__bkt];
1988 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1989 __p = __p->_M_next())
1991 if (this->_M_equals_tr(__k, __code, *__p))
1994 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
2002 template<
typename _Key,
typename _Value,
typename _Alloc,
2003 typename _ExtractKey,
typename _Equal,
2004 typename _Hash,
typename _RangeHash,
typename _Unused,
2005 typename _RehashPolicy,
typename _Traits>
2007 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2008 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2009 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
2011 if (_M_buckets[__bkt])
2015 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
2016 _M_buckets[__bkt]->_M_nxt = __node;
2023 __node->_M_nxt = _M_before_begin._M_nxt;
2024 _M_before_begin._M_nxt = __node;
2029 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
2031 _M_buckets[__bkt] = &_M_before_begin;
2035 template<
typename _Key,
typename _Value,
typename _Alloc,
2036 typename _ExtractKey,
typename _Equal,
2037 typename _Hash,
typename _RangeHash,
typename _Unused,
2038 typename _RehashPolicy,
typename _Traits>
2040 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2041 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2042 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
2043 size_type __next_bkt)
2045 if (!__next || __next_bkt != __bkt)
2050 _M_buckets[__next_bkt] = _M_buckets[__bkt];
2053 if (&_M_before_begin == _M_buckets[__bkt])
2054 _M_before_begin._M_nxt = __next;
2055 _M_buckets[__bkt] =
nullptr;
2059 template<
typename _Key,
typename _Value,
typename _Alloc,
2060 typename _ExtractKey,
typename _Equal,
2061 typename _Hash,
typename _RangeHash,
typename _Unused,
2062 typename _RehashPolicy,
typename _Traits>
2064 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2065 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2066 _M_get_previous_node(size_type __bkt, __node_ptr __n)
2069 __node_base_ptr __prev_n = _M_buckets[__bkt];
2070 while (__prev_n->_M_nxt != __n)
2071 __prev_n = __prev_n->_M_nxt;
2075 template<
typename _Key,
typename _Value,
typename _Alloc,
2076 typename _ExtractKey,
typename _Equal,
2077 typename _Hash,
typename _RangeHash,
typename _Unused,
2078 typename _RehashPolicy,
typename _Traits>
2079 template<
typename... _Args>
2081 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2082 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2083 _M_emplace(true_type , _Args&&... __args)
2084 -> pair<iterator, bool>
2087 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2088 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2089 if (size() <= __small_size_threshold())
2091 for (
auto __it = begin(); __it != end(); ++__it)
2092 if (this->_M_key_equals(__k, *__it._M_cur))
2094 return { __it,
false };
2097 __hash_code __code = this->_M_hash_code(__k);
2098 size_type __bkt = _M_bucket_index(__code);
2099 if (size() > __small_size_threshold())
2100 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2102 return { iterator(__p),
false };
2105 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2106 __node._M_node =
nullptr;
2107 return { __pos,
true };
2110 template<
typename _Key,
typename _Value,
typename _Alloc,
2111 typename _ExtractKey,
typename _Equal,
2112 typename _Hash,
typename _RangeHash,
typename _Unused,
2113 typename _RehashPolicy,
typename _Traits>
2114 template<
typename... _Args>
2116 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2117 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2118 _M_emplace(const_iterator __hint, false_type ,
2123 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2124 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2126 auto __res = this->_M_compute_hash_code(__hint, __k);
2128 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2130 __node._M_node =
nullptr;
2134 template<
typename _Key,
typename _Value,
typename _Alloc,
2135 typename _ExtractKey,
typename _Equal,
2136 typename _Hash,
typename _RangeHash,
typename _Unused,
2137 typename _RehashPolicy,
typename _Traits>
2139 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2140 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2141 _M_compute_hash_code(const_iterator __hint,
const key_type& __k)
const
2142 -> pair<const_iterator, __hash_code>
2144 if (size() <= __small_size_threshold())
2146 if (__hint != cend())
2148 for (
auto __it = __hint; __it != cend(); ++__it)
2149 if (this->_M_key_equals(__k, *__it._M_cur))
2150 return { __it, this->_M_hash_code(*__it._M_cur) };
2153 for (
auto __it = cbegin(); __it != __hint; ++__it)
2154 if (this->_M_key_equals(__k, *__it._M_cur))
2155 return { __it, this->_M_hash_code(*__it._M_cur) };
2158 return { __hint, this->_M_hash_code(__k) };
2161 template<
typename _Key,
typename _Value,
typename _Alloc,
2162 typename _ExtractKey,
typename _Equal,
2163 typename _Hash,
typename _RangeHash,
typename _Unused,
2164 typename _RehashPolicy,
typename _Traits>
2166 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2167 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2168 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2169 __node_ptr __node, size_type __n_elt)
2172 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2174 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2177 if (__do_rehash.
first)
2179 _M_rehash(__do_rehash.
second, __saved_state);
2180 __bkt = _M_bucket_index(__code);
2183 this->_M_store_code(*__node, __code);
2186 _M_insert_bucket_begin(__bkt, __node);
2188 return iterator(__node);
2191 template<
typename _Key,
typename _Value,
typename _Alloc,
2192 typename _ExtractKey,
typename _Equal,
2193 typename _Hash,
typename _RangeHash,
typename _Unused,
2194 typename _RehashPolicy,
typename _Traits>
2196 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2197 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2198 _M_insert_multi_node(__node_ptr __hint,
2199 __hash_code __code, __node_ptr __node)
2202 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2204 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2206 if (__do_rehash.
first)
2207 _M_rehash(__do_rehash.
second, __saved_state);
2209 this->_M_store_code(*__node, __code);
2210 const key_type& __k = _ExtractKey{}(__node->_M_v());
2211 size_type __bkt = _M_bucket_index(__code);
2215 __node_base_ptr __prev
2216 = __builtin_expect(__hint !=
nullptr,
false)
2217 && this->_M_equals(__k, __code, *__hint)
2219 : _M_find_before_node(__bkt, __k, __code);
2224 __node->_M_nxt = __prev->_M_nxt;
2225 __prev->_M_nxt = __node;
2226 if (__builtin_expect(__prev == __hint,
false))
2230 && !this->_M_equals(__k, __code, *__node->_M_next()))
2232 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2233 if (__next_bkt != __bkt)
2234 _M_buckets[__next_bkt] = __node;
2241 _M_insert_bucket_begin(__bkt, __node);
2243 return iterator(__node);
2247 template<
typename _Key,
typename _Value,
typename _Alloc,
2248 typename _ExtractKey,
typename _Equal,
2249 typename _Hash,
typename _RangeHash,
typename _Unused,
2250 typename _RehashPolicy,
typename _Traits>
2251 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
2253 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2254 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2255 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2256 const _NodeGenerator& __node_gen)
2257 -> pair<iterator, bool>
2259 if (size() <= __small_size_threshold())
2260 for (
auto __it = begin(); __it != end(); ++__it)
2261 if (this->_M_key_equals_tr(__k, *__it._M_cur))
2262 return { __it,
false };
2264 __hash_code __code = this->_M_hash_code_tr(__k);
2265 size_type __bkt = _M_bucket_index(__code);
2267 if (size() > __small_size_threshold())
2268 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2269 return { iterator(__node),
false };
2271 _Scoped_node __node {
2272 __node_builder_t::_S_build(std::forward<_Kt>(__k),
2273 std::forward<_Arg>(__v),
2278 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2279 __node._M_node =
nullptr;
2280 return { __pos,
true };
2284 template<
typename _Key,
typename _Value,
typename _Alloc,
2285 typename _ExtractKey,
typename _Equal,
2286 typename _Hash,
typename _RangeHash,
typename _Unused,
2287 typename _RehashPolicy,
typename _Traits>
2288 template<
typename _Arg,
typename _NodeGenerator>
2290 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2291 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2292 _M_insert(const_iterator __hint, _Arg&& __v,
2293 const _NodeGenerator& __node_gen,
2298 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2301 auto __res = this->_M_compute_hash_code(
2302 __hint, _ExtractKey{}(__node._M_node->_M_v()));
2305 = _M_insert_multi_node(__res.first._M_cur, __res.second,
2307 __node._M_node =
nullptr;
2311 template<
typename _Key,
typename _Value,
typename _Alloc,
2312 typename _ExtractKey,
typename _Equal,
2313 typename _Hash,
typename _RangeHash,
typename _Unused,
2314 typename _RehashPolicy,
typename _Traits>
2316 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2317 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2318 erase(const_iterator __it)
2321 __node_ptr __n = __it._M_cur;
2322 std::size_t __bkt = _M_bucket_index(*__n);
2327 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2328 return _M_erase(__bkt, __prev_n, __n);
2331 template<
typename _Key,
typename _Value,
typename _Alloc,
2332 typename _ExtractKey,
typename _Equal,
2333 typename _Hash,
typename _RangeHash,
typename _Unused,
2334 typename _RehashPolicy,
typename _Traits>
2336 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2337 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2338 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2341 if (__prev_n == _M_buckets[__bkt])
2342 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2343 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2344 else if (__n->_M_nxt)
2346 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2347 if (__next_bkt != __bkt)
2348 _M_buckets[__next_bkt] = __prev_n;
2351 __prev_n->_M_nxt = __n->_M_nxt;
2352 iterator __result(__n->_M_next());
2353 this->_M_deallocate_node(__n);
2359 template<
typename _Key,
typename _Value,
typename _Alloc,
2360 typename _ExtractKey,
typename _Equal,
2361 typename _Hash,
typename _RangeHash,
typename _Unused,
2362 typename _RehashPolicy,
typename _Traits>
2364 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2365 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2366 _M_erase(true_type ,
const key_type& __k)
2369 __node_base_ptr __prev_n;
2372 if (size() <= __small_size_threshold())
2374 __prev_n = _M_find_before_node(__k);
2379 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2380 __bkt = _M_bucket_index(*__n);
2384 __hash_code __code = this->_M_hash_code(__k);
2385 __bkt = _M_bucket_index(__code);
2388 __prev_n = _M_find_before_node(__bkt, __k, __code);
2393 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2396 _M_erase(__bkt, __prev_n, __n);
2400 template<
typename _Key,
typename _Value,
typename _Alloc,
2401 typename _ExtractKey,
typename _Equal,
2402 typename _Hash,
typename _RangeHash,
typename _Unused,
2403 typename _RehashPolicy,
typename _Traits>
2405 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2406 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2407 _M_erase(false_type ,
const key_type& __k)
2411 __node_base_ptr __prev_n;
2413 if (size() <= __small_size_threshold())
2415 __prev_n = _M_find_before_node(__k);
2420 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2421 __bkt = _M_bucket_index(*__n);
2425 __hash_code __code = this->_M_hash_code(__k);
2426 __bkt = _M_bucket_index(__code);
2429 __prev_n = _M_find_before_node(__bkt, __k, __code);
2433 __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2442 __node_ptr __n_last = __n->_M_next();
2443 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2444 __n_last = __n_last->_M_next();
2446 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2449 size_type __result = 0;
2452 __node_ptr __p = __n->_M_next();
2453 this->_M_deallocate_node(__n);
2457 while (__n != __n_last);
2459 _M_element_count -= __result;
2460 if (__prev_n == _M_buckets[__bkt])
2461 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2462 else if (__n_last_bkt != __bkt)
2463 _M_buckets[__n_last_bkt] = __prev_n;
2464 __prev_n->_M_nxt = __n_last;
2468 template<
typename _Key,
typename _Value,
typename _Alloc,
2469 typename _ExtractKey,
typename _Equal,
2470 typename _Hash,
typename _RangeHash,
typename _Unused,
2471 typename _RehashPolicy,
typename _Traits>
2473 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2474 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2475 erase(const_iterator __first, const_iterator __last)
2478 __node_ptr __n = __first._M_cur;
2479 __node_ptr __last_n = __last._M_cur;
2480 if (__n == __last_n)
2481 return iterator(__n);
2483 std::size_t __bkt = _M_bucket_index(*__n);
2485 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2486 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2487 std::size_t __n_bkt = __bkt;
2492 __node_ptr __tmp = __n;
2493 __n = __n->_M_next();
2494 this->_M_deallocate_node(__tmp);
2498 __n_bkt = _M_bucket_index(*__n);
2500 while (__n != __last_n && __n_bkt == __bkt);
2501 if (__is_bucket_begin)
2502 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2503 if (__n == __last_n)
2505 __is_bucket_begin =
true;
2509 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2510 _M_buckets[__n_bkt] = __prev_n;
2511 __prev_n->_M_nxt = __n;
2512 return iterator(__n);
2515 template<
typename _Key,
typename _Value,
typename _Alloc,
2516 typename _ExtractKey,
typename _Equal,
2517 typename _Hash,
typename _RangeHash,
typename _Unused,
2518 typename _RehashPolicy,
typename _Traits>
2520 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2521 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2524 this->_M_deallocate_nodes(_M_begin());
2525 __builtin_memset(_M_buckets, 0,
2526 _M_bucket_count *
sizeof(__node_base_ptr));
2527 _M_element_count = 0;
2528 _M_before_begin._M_nxt =
nullptr;
2531 template<
typename _Key,
typename _Value,
typename _Alloc,
2532 typename _ExtractKey,
typename _Equal,
2533 typename _Hash,
typename _RangeHash,
typename _Unused,
2534 typename _RehashPolicy,
typename _Traits>
2536 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2537 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2538 rehash(size_type __bkt_count)
2540 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2542 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2544 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2546 if (__bkt_count != _M_bucket_count)
2547 _M_rehash(__bkt_count, __saved_state);
2551 _M_rehash_policy._M_reset(__saved_state);
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 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2565 _M_rehash_aux(__bkt_count, __unique_keys{});
2571 _M_rehash_policy._M_reset(__state);
2572 __throw_exception_again;
2577 template<
typename _Key,
typename _Value,
typename _Alloc,
2578 typename _ExtractKey,
typename _Equal,
2579 typename _Hash,
typename _RangeHash,
typename _Unused,
2580 typename _RehashPolicy,
typename _Traits>
2582 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2583 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2584 _M_rehash_aux(size_type __bkt_count, true_type )
2586 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2587 __node_ptr __p = _M_begin();
2588 _M_before_begin._M_nxt =
nullptr;
2589 std::size_t __bbegin_bkt = 0;
2592 __node_ptr __next = __p->_M_next();
2594 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2595 if (!__new_buckets[__bkt])
2597 __p->_M_nxt = _M_before_begin._M_nxt;
2598 _M_before_begin._M_nxt = __p;
2599 __new_buckets[__bkt] = &_M_before_begin;
2601 __new_buckets[__bbegin_bkt] = __p;
2602 __bbegin_bkt = __bkt;
2606 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2607 __new_buckets[__bkt]->_M_nxt = __p;
2613 _M_deallocate_buckets();
2614 _M_bucket_count = __bkt_count;
2615 _M_buckets = __new_buckets;
2620 template<
typename _Key,
typename _Value,
typename _Alloc,
2621 typename _ExtractKey,
typename _Equal,
2622 typename _Hash,
typename _RangeHash,
typename _Unused,
2623 typename _RehashPolicy,
typename _Traits>
2625 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2626 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2627 _M_rehash_aux(size_type __bkt_count, false_type )
2629 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2630 __node_ptr __p = _M_begin();
2631 _M_before_begin._M_nxt =
nullptr;
2632 std::size_t __bbegin_bkt = 0;
2633 std::size_t __prev_bkt = 0;
2634 __node_ptr __prev_p =
nullptr;
2635 bool __check_bucket =
false;
2639 __node_ptr __next = __p->_M_next();
2641 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2643 if (__prev_p && __prev_bkt == __bkt)
2648 __p->_M_nxt = __prev_p->_M_nxt;
2649 __prev_p->_M_nxt = __p;
2656 __check_bucket =
true;
2664 if (__prev_p->_M_nxt)
2666 std::size_t __next_bkt
2667 = __hash_code_base::_M_bucket_index(
2668 *__prev_p->_M_next(), __bkt_count);
2669 if (__next_bkt != __prev_bkt)
2670 __new_buckets[__next_bkt] = __prev_p;
2672 __check_bucket =
false;
2675 if (!__new_buckets[__bkt])
2677 __p->_M_nxt = _M_before_begin._M_nxt;
2678 _M_before_begin._M_nxt = __p;
2679 __new_buckets[__bkt] = &_M_before_begin;
2681 __new_buckets[__bbegin_bkt] = __p;
2682 __bbegin_bkt = __bkt;
2686 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2687 __new_buckets[__bkt]->_M_nxt = __p;
2695 if (__check_bucket && __prev_p->_M_nxt)
2697 std::size_t __next_bkt
2698 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2700 if (__next_bkt != __prev_bkt)
2701 __new_buckets[__next_bkt] = __prev_p;
2704 _M_deallocate_buckets();
2705 _M_bucket_count = __bkt_count;
2706 _M_buckets = __new_buckets;
2709#if __cplusplus > 201402L
2710 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2713#if __cpp_deduction_guides >= 201606
2715 template<
typename _Hash>
2716 using _RequireNotAllocatorOrIntegral
2717 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2721_GLIBCXX_END_NAMESPACE_VERSION
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
ISO C++ entities toplevel namespace is std.
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
Struct holding two objects of arbitrary type.
_T1 first
The first member.
_T2 second
The second member.