31 #define _HASHTABLE_H 1
33 #pragma GCC system_header
37 #if __cplusplus > 201402L
41 namespace std _GLIBCXX_VISIBILITY(default)
43 _GLIBCXX_BEGIN_NAMESPACE_VERSION
46 template<
typename _Tp,
typename _Hash>
49 __is_fast_hash<_Hash>,
51 __is_nothrow_invocable<const _Hash&, const _Tp&>>>;
56 template<
typename _Equal,
typename _Hash,
typename _Allocator>
57 using _Hashtable_enable_default_ctor
58 = _Enable_default_constructor<__and_<is_default_constructible<_Equal>,
59 is_default_constructible<_Hash>,
60 is_default_constructible<_Allocator>>{},
61 __detail::_Hash_node_base>;
176 template<
typename _Key,
typename _Value,
typename _Alloc,
177 typename _ExtractKey,
typename _Equal,
178 typename _Hash,
typename _RangeHash,
typename _Unused,
179 typename _RehashPolicy,
typename _Traits>
181 :
public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal,
182 _Hash, _RangeHash, _Unused, _Traits>,
183 public __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
184 _Hash, _RangeHash, _Unused,
185 _RehashPolicy, _Traits>,
186 public __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal,
187 _Hash, _RangeHash, _Unused,
188 _RehashPolicy, _Traits>,
189 public __detail::_Rehash_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
190 _Hash, _RangeHash, _Unused,
191 _RehashPolicy, _Traits>,
192 public __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
193 _Hash, _RangeHash, _Unused,
194 _RehashPolicy, _Traits>,
195 private __detail::_Hashtable_alloc<
196 __alloc_rebind<_Alloc,
197 __detail::_Hash_node<_Value,
198 _Traits::__hash_cached::value>>>,
199 private _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>
201 static_assert(is_same<
typename remove_cv<_Value>::type, _Value>::value,
202 "unordered container must have a non-const, non-volatile value_type");
203 #if __cplusplus > 201703L || defined __STRICT_ANSI__
204 static_assert(is_same<typename _Alloc::value_type, _Value>{},
205 "unordered container must have the same value_type as its allocator");
208 using __traits_type = _Traits;
209 using __hash_cached =
typename __traits_type::__hash_cached;
210 using __constant_iterators =
typename __traits_type::__constant_iterators;
211 using __node_type = __detail::_Hash_node<_Value, __hash_cached::value>;
212 using __node_alloc_type = __alloc_rebind<_Alloc, __node_type>;
214 using __hashtable_alloc = __detail::_Hashtable_alloc<__node_alloc_type>;
216 using __node_value_type =
217 __detail::_Hash_node_value<_Value, __hash_cached::value>;
218 using __node_ptr =
typename __hashtable_alloc::__node_ptr;
219 using __value_alloc_traits =
220 typename __hashtable_alloc::__value_alloc_traits;
221 using __node_alloc_traits =
222 typename __hashtable_alloc::__node_alloc_traits;
223 using __node_base =
typename __hashtable_alloc::__node_base;
224 using __node_base_ptr =
typename __hashtable_alloc::__node_base_ptr;
225 using __buckets_ptr =
typename __hashtable_alloc::__buckets_ptr;
227 using __insert_base = __detail::_Insert<_Key, _Value, _Alloc, _ExtractKey,
230 _RehashPolicy, _Traits>;
231 using __enable_default_ctor
232 = _Hashtable_enable_default_ctor<_Equal, _Hash, _Alloc>;
235 typedef _Key key_type;
236 typedef _Value value_type;
237 typedef _Alloc allocator_type;
238 typedef _Equal key_equal;
242 typedef typename __value_alloc_traits::pointer pointer;
243 typedef typename __value_alloc_traits::const_pointer const_pointer;
244 typedef value_type& reference;
245 typedef const value_type& const_reference;
247 using iterator =
typename __insert_base::iterator;
249 using const_iterator =
typename __insert_base::const_iterator;
251 using local_iterator = __detail::_Local_iterator<key_type, _Value,
252 _ExtractKey, _Hash, _RangeHash, _Unused,
253 __constant_iterators::value,
254 __hash_cached::value>;
256 using const_local_iterator = __detail::_Local_const_iterator<
258 _ExtractKey, _Hash, _RangeHash, _Unused,
259 __constant_iterators::value, __hash_cached::value>;
262 using __rehash_type = _RehashPolicy;
263 using __rehash_state =
typename __rehash_type::_State;
265 using __unique_keys =
typename __traits_type::__unique_keys;
267 using __hashtable_base = __detail::
268 _Hashtable_base<_Key, _Value, _ExtractKey,
269 _Equal, _Hash, _RangeHash, _Unused, _Traits>;
271 using __hash_code_base =
typename __hashtable_base::__hash_code_base;
272 using __hash_code =
typename __hashtable_base::__hash_code;
273 using __ireturn_type =
typename __insert_base::__ireturn_type;
275 using __map_base = __detail::_Map_base<_Key, _Value, _Alloc, _ExtractKey,
276 _Equal, _Hash, _RangeHash, _Unused,
277 _RehashPolicy, _Traits>;
279 using __rehash_base = __detail::_Rehash_base<_Key, _Value, _Alloc,
281 _Hash, _RangeHash, _Unused,
282 _RehashPolicy, _Traits>;
284 using __eq_base = __detail::_Equality<_Key, _Value, _Alloc, _ExtractKey,
285 _Equal, _Hash, _RangeHash, _Unused,
286 _RehashPolicy, _Traits>;
288 using __reuse_or_alloc_node_gen_t =
289 __detail::_ReuseOrAllocNode<__node_alloc_type>;
290 using __alloc_node_gen_t =
291 __detail::_AllocNode<__node_alloc_type>;
292 using __node_builder_t =
293 __detail::_NodeBuilder<_ExtractKey>;
299 _Scoped_node(__node_ptr __n, __hashtable_alloc* __h)
300 : _M_h(__h), _M_node(__n) { }
303 template<
typename... _Args>
304 _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
306 _M_node(__h->_M_allocate_node(
std::
forward<_Args>(__args)...))
310 ~_Scoped_node() {
if (_M_node) _M_h->_M_deallocate_node(_M_node); };
312 _Scoped_node(
const _Scoped_node&) =
delete;
313 _Scoped_node& operator=(
const _Scoped_node&) =
delete;
315 __hashtable_alloc* _M_h;
319 template<
typename _Ht>
321 __conditional_t<std::is_lvalue_reference<_Ht>::value,
322 const value_type&, value_type&&>
323 __fwd_value_for(value_type& __val) noexcept
330 struct __hash_code_base_access : __hash_code_base
331 {
using __hash_code_base::_M_bucket_index; };
334 static_assert(is_nothrow_default_constructible<_RangeHash>::value,
335 "Functor used to map hash code to bucket index"
336 " must be nothrow default constructible");
337 static_assert(noexcept(
338 std::declval<const _RangeHash&>()((std::size_t)0, (std::size_t)0)),
339 "Functor used to map hash code to bucket index must be"
343 static_assert(is_nothrow_default_constructible<_ExtractKey>::value,
344 "_ExtractKey must be nothrow default constructible");
345 static_assert(noexcept(
346 std::declval<const _ExtractKey&>()(std::declval<_Value>())),
347 "_ExtractKey functor must be noexcept invocable");
349 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
350 typename _ExtractKeya,
typename _Equala,
351 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
352 typename _RehashPolicya,
typename _Traitsa,
354 friend struct __detail::_Map_base;
356 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
357 typename _ExtractKeya,
typename _Equala,
358 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
359 typename _RehashPolicya,
typename _Traitsa>
360 friend struct __detail::_Insert_base;
362 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
363 typename _ExtractKeya,
typename _Equala,
364 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
365 typename _RehashPolicya,
typename _Traitsa,
366 bool _Constant_iteratorsa>
367 friend struct __detail::_Insert;
369 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
370 typename _ExtractKeya,
typename _Equala,
371 typename _Hasha,
typename _RangeHasha,
typename _Unuseda,
372 typename _RehashPolicya,
typename _Traitsa,
374 friend struct __detail::_Equality;
377 using size_type =
typename __hashtable_base::size_type;
378 using difference_type =
typename __hashtable_base::difference_type;
380 #if __cplusplus > 201402L
381 using node_type = _Node_handle<_Key, _Value, __node_alloc_type>;
382 using insert_return_type = _Node_insert_return<iterator, node_type>;
386 __buckets_ptr _M_buckets = &_M_single_bucket;
387 size_type _M_bucket_count = 1;
388 __node_base _M_before_begin;
389 size_type _M_element_count = 0;
390 _RehashPolicy _M_rehash_policy;
398 __node_base_ptr _M_single_bucket =
nullptr;
404 _M_buckets[_M_bucket_index(*_M_begin())] = &_M_before_begin;
408 _M_update_bbegin(__node_ptr __n)
410 _M_before_begin._M_nxt = __n;
415 _M_uses_single_bucket(__buckets_ptr __bkts)
const
416 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
419 _M_uses_single_bucket()
const
420 {
return _M_uses_single_bucket(_M_buckets); }
423 _M_base_alloc() {
return *
this; }
426 _M_allocate_buckets(size_type __bkt_count)
428 if (__builtin_expect(__bkt_count == 1,
false))
430 _M_single_bucket =
nullptr;
431 return &_M_single_bucket;
434 return __hashtable_alloc::_M_allocate_buckets(__bkt_count);
438 _M_deallocate_buckets(__buckets_ptr __bkts, size_type __bkt_count)
440 if (_M_uses_single_bucket(__bkts))
443 __hashtable_alloc::_M_deallocate_buckets(__bkts, __bkt_count);
447 _M_deallocate_buckets()
448 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
453 _M_bucket_begin(size_type __bkt)
const;
457 {
return static_cast<__node_ptr
>(_M_before_begin._M_nxt); }
461 template<
typename _Ht>
463 _M_assign_elements(_Ht&&);
465 template<
typename _Ht,
typename _NodeGenerator>
467 _M_assign(_Ht&&,
const _NodeGenerator&);
478 _Hashtable(const _Hash& __h, const _Equal& __eq,
479 const allocator_type& __a)
480 : __hashtable_base(__h, __eq),
481 __hashtable_alloc(__node_alloc_type(__a)),
482 __enable_default_ctor(_Enable_default_constructor_tag{})
485 template<
bool _No_realloc = true>
486 static constexpr
bool
489 #if __cplusplus <= 201402L
490 return __and_<__bool_constant<_No_realloc>,
491 is_nothrow_copy_constructible<_Hash>,
492 is_nothrow_copy_constructible<_Equal>>::value;
494 if constexpr (_No_realloc)
495 if constexpr (is_nothrow_copy_constructible<_Hash>())
496 return is_nothrow_copy_constructible<_Equal>();
501 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
503 noexcept(_S_nothrow_move());
505 _Hashtable(_Hashtable&&, __node_alloc_type&&,
508 template<
typename _InputIterator>
509 _Hashtable(_InputIterator __first, _InputIterator __last,
510 size_type __bkt_count_hint,
511 const _Hash&,
const _Equal&,
const allocator_type&,
514 template<
typename _InputIterator>
515 _Hashtable(_InputIterator __first, _InputIterator __last,
516 size_type __bkt_count_hint,
517 const _Hash&,
const _Equal&,
const allocator_type&,
522 _Hashtable() =
default;
524 _Hashtable(
const _Hashtable&);
526 _Hashtable(
const _Hashtable&,
const allocator_type&);
529 _Hashtable(size_type __bkt_count_hint,
530 const _Hash& __hf = _Hash(),
531 const key_equal& __eql = key_equal(),
532 const allocator_type& __a = allocator_type());
535 _Hashtable(_Hashtable&& __ht)
536 noexcept(_S_nothrow_move())
537 : _Hashtable(
std::
move(__ht),
std::
move(__ht._M_node_allocator()),
541 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
542 noexcept(_S_nothrow_move<__node_alloc_traits::_S_always_equal()>())
543 : _Hashtable(
std::
move(__ht), __node_alloc_type(__a),
544 typename __node_alloc_traits::is_always_equal{})
548 _Hashtable(
const allocator_type& __a)
549 : __hashtable_alloc(__node_alloc_type(__a)),
550 __enable_default_ctor(_Enable_default_constructor_tag{})
553 template<
typename _InputIterator>
554 _Hashtable(_InputIterator __f, _InputIterator __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(__f, __l, __bkt_count_hint, __hf, __eql, __a,
563 _Hashtable(initializer_list<value_type> __l,
564 size_type __bkt_count_hint = 0,
565 const _Hash& __hf = _Hash(),
566 const key_equal& __eql = key_equal(),
567 const allocator_type& __a = allocator_type())
568 : _Hashtable(__l.
begin(), __l.
end(), __bkt_count_hint,
569 __hf, __eql, __a, __unique_keys{})
573 operator=(
const _Hashtable& __ht);
576 operator=(_Hashtable&& __ht)
577 noexcept(__node_alloc_traits::_S_nothrow_move()
578 && is_nothrow_move_assignable<_Hash>::value
579 && is_nothrow_move_assignable<_Equal>::value)
581 constexpr
bool __move_storage =
582 __node_alloc_traits::_S_propagate_on_move_assign()
583 || __node_alloc_traits::_S_always_equal();
584 _M_move_assign(
std::move(__ht), __bool_constant<__move_storage>());
589 operator=(initializer_list<value_type> __l)
591 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
592 _M_before_begin._M_nxt =
nullptr;
596 auto __l_bkt_count = _M_rehash_policy._M_bkt_for_elements(__l.size());
599 if (_M_bucket_count < __l_bkt_count)
600 rehash(__l_bkt_count);
602 this->_M_insert_range(__l.begin(), __l.end(), __roan, __unique_keys{});
606 ~_Hashtable() noexcept;
610 noexcept(__and_<__is_nothrow_swappable<_Hash>,
611 __is_nothrow_swappable<_Equal>>::value);
616 {
return iterator(_M_begin()); }
619 begin() const noexcept
620 {
return const_iterator(_M_begin()); }
624 {
return iterator(
nullptr); }
628 {
return const_iterator(
nullptr); }
632 {
return const_iterator(_M_begin()); }
635 cend() const noexcept
636 {
return const_iterator(
nullptr); }
639 size() const noexcept
640 {
return _M_element_count; }
642 _GLIBCXX_NODISCARD
bool
643 empty() const noexcept
644 {
return size() == 0; }
647 get_allocator() const noexcept
648 {
return allocator_type(this->_M_node_allocator()); }
651 max_size() const noexcept
652 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
657 {
return this->_M_eq(); }
663 bucket_count() const noexcept
664 {
return _M_bucket_count; }
667 max_bucket_count() const noexcept
668 {
return max_size(); }
671 bucket_size(size_type __bkt)
const
675 bucket(
const key_type& __k)
const
676 {
return _M_bucket_index(this->_M_hash_code(__k)); }
679 begin(size_type __bkt)
681 return local_iterator(*
this, _M_bucket_begin(__bkt),
682 __bkt, _M_bucket_count);
687 {
return local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
690 begin(size_type __bkt)
const
692 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
693 __bkt, _M_bucket_count);
697 end(size_type __bkt)
const
698 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
702 cbegin(size_type __bkt)
const
704 return const_local_iterator(*
this, _M_bucket_begin(__bkt),
705 __bkt, _M_bucket_count);
709 cend(size_type __bkt)
const
710 {
return const_local_iterator(*
this,
nullptr, __bkt, _M_bucket_count); }
713 load_factor() const noexcept
715 return static_cast<float>(
size()) /
static_cast<float>(bucket_count());
724 __rehash_policy()
const
725 {
return _M_rehash_policy; }
728 __rehash_policy(
const _RehashPolicy& __pol)
729 { _M_rehash_policy = __pol; }
733 find(
const key_type& __k);
736 find(
const key_type& __k)
const;
739 count(
const key_type& __k)
const;
742 equal_range(
const key_type& __k);
745 equal_range(
const key_type& __k)
const;
747 #if __cplusplus >= 202002L
748 #define __cpp_lib_generic_unordered_lookup 201811L
750 template<
typename _Kt,
751 typename = __has_is_transparent_t<_Hash, _Kt>,
752 typename = __has_is_transparent_t<_Equal, _Kt>>
754 _M_find_tr(
const _Kt& __k);
756 template<
typename _Kt,
757 typename = __has_is_transparent_t<_Hash, _Kt>,
758 typename = __has_is_transparent_t<_Equal, _Kt>>
760 _M_find_tr(
const _Kt& __k)
const;
762 template<
typename _Kt,
763 typename = __has_is_transparent_t<_Hash, _Kt>,
764 typename = __has_is_transparent_t<_Equal, _Kt>>
766 _M_count_tr(
const _Kt& __k)
const;
768 template<
typename _Kt,
769 typename = __has_is_transparent_t<_Hash, _Kt>,
770 typename = __has_is_transparent_t<_Equal, _Kt>>
771 pair<iterator, iterator>
772 _M_equal_range_tr(
const _Kt& __k);
774 template<
typename _Kt,
775 typename = __has_is_transparent_t<_Hash, _Kt>,
776 typename = __has_is_transparent_t<_Equal, _Kt>>
777 pair<const_iterator, const_iterator>
778 _M_equal_range_tr(
const _Kt& __k)
const;
784 _M_bucket_index(
const __node_value_type& __n)
const noexcept
785 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
788 _M_bucket_index(__hash_code __c)
const
789 {
return __hash_code_base::_M_bucket_index(__c, _M_bucket_count); }
794 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
796 template<
typename _Kt>
798 _M_find_before_node_tr(size_type,
const _Kt&, __hash_code)
const;
801 _M_find_node(size_type __bkt,
const key_type& __key,
802 __hash_code __c)
const
804 __node_base_ptr __before_n = _M_find_before_node(__bkt, __key, __c);
806 return static_cast<__node_ptr
>(__before_n->_M_nxt);
810 template<
typename _Kt>
812 _M_find_node_tr(size_type __bkt,
const _Kt& __key,
813 __hash_code __c)
const
815 auto __before_n = _M_find_before_node_tr(__bkt, __key, __c);
817 return static_cast<__node_ptr
>(__before_n->_M_nxt);
823 _M_insert_bucket_begin(size_type, __node_ptr);
827 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next_n,
828 size_type __next_bkt);
832 _M_get_previous_node(size_type __bkt, __node_ptr __n);
838 _M_insert_unique_node(size_type __bkt, __hash_code,
839 __node_ptr __n, size_type __n_elt = 1);
844 _M_insert_multi_node(__node_ptr __hint,
845 __hash_code __code, __node_ptr __n);
847 template<
typename... _Args>
849 _M_emplace(
true_type __uks, _Args&&... __args);
851 template<
typename... _Args>
853 _M_emplace(
false_type __uks, _Args&&... __args)
854 {
return _M_emplace(
cend(), __uks, std::forward<_Args>(__args)...); }
857 template<
typename... _Args>
859 _M_emplace(const_iterator,
true_type __uks, _Args&&... __args)
860 {
return _M_emplace(__uks, std::forward<_Args>(__args)...).first; }
862 template<
typename... _Args>
864 _M_emplace(const_iterator,
false_type __uks, _Args&&... __args);
866 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
868 _M_insert_unique(_Kt&&, _Arg&&,
const _NodeGenerator&);
870 template<
typename _Kt>
871 static __conditional_t<
872 __and_<__is_nothrow_invocable<_Hash&, const key_type&>,
873 __not_<__is_nothrow_invocable<_Hash&, _Kt>>>::value,
875 _S_forward_key(_Kt&& __k)
876 {
return std::forward<_Kt>(__k); }
878 static const key_type&
879 _S_forward_key(
const key_type& __k)
883 _S_forward_key(key_type&& __k)
886 template<
typename _Arg,
typename _NodeGenerator>
888 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
891 return _M_insert_unique(
892 _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
893 std::forward<_Arg>(__arg), __node_gen);
896 template<
typename _Arg,
typename _NodeGenerator>
898 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
901 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
906 template<
typename _Arg,
typename _NodeGenerator>
908 _M_insert(const_iterator, _Arg&& __arg,
909 const _NodeGenerator& __node_gen,
true_type __uks)
912 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uks).first;
916 template<
typename _Arg,
typename _NodeGenerator>
918 _M_insert(const_iterator, _Arg&&,
922 _M_erase(
true_type __uks,
const key_type&);
928 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n);
932 template<
typename... _Args>
934 emplace(_Args&&... __args)
935 {
return _M_emplace(__unique_keys{}, std::forward<_Args>(__args)...); }
937 template<
typename... _Args>
939 emplace_hint(const_iterator __hint, _Args&&... __args)
941 return _M_emplace(__hint, __unique_keys{},
942 std::forward<_Args>(__args)...);
949 erase(const_iterator);
954 {
return erase(const_iterator(__it)); }
957 erase(
const key_type& __k)
958 {
return _M_erase(__unique_keys{}, __k); }
961 erase(const_iterator, const_iterator);
968 void rehash(size_type __bkt_count);
973 #if __cplusplus > 201402L
976 _M_reinsert_node(node_type&& __nh)
978 insert_return_type __ret;
980 __ret.position =
end();
983 __glibcxx_assert(get_allocator() == __nh.get_allocator());
985 const key_type& __k = __nh._M_key();
986 __hash_code __code = this->_M_hash_code(__k);
987 size_type __bkt = _M_bucket_index(__code);
988 if (__node_ptr __n = _M_find_node(__bkt, __k, __code))
991 __ret.position = iterator(__n);
992 __ret.inserted =
false;
997 = _M_insert_unique_node(__bkt, __code, __nh._M_ptr);
998 __nh._M_ptr =
nullptr;
999 __ret.inserted =
true;
1007 _M_reinsert_node_multi(const_iterator __hint, node_type&& __nh)
1012 __glibcxx_assert(get_allocator() == __nh.get_allocator());
1014 const key_type& __k = __nh._M_key();
1015 auto __code = this->_M_hash_code(__k);
1017 = _M_insert_multi_node(__hint._M_cur, __code, __nh._M_ptr);
1018 __nh._M_ptr =
nullptr;
1024 _M_extract_node(
size_t __bkt, __node_base_ptr __prev_n)
1026 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
1027 if (__prev_n == _M_buckets[__bkt])
1028 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1029 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
1030 else if (__n->_M_nxt)
1032 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
1033 if (__next_bkt != __bkt)
1034 _M_buckets[__next_bkt] = __prev_n;
1037 __prev_n->_M_nxt = __n->_M_nxt;
1038 __n->_M_nxt =
nullptr;
1040 return { __n, this->_M_node_allocator() };
1046 extract(const_iterator __pos)
1048 size_t __bkt = _M_bucket_index(*__pos._M_cur);
1049 return _M_extract_node(__bkt,
1050 _M_get_previous_node(__bkt, __pos._M_cur));
1055 extract(
const _Key& __k)
1058 __hash_code __code = this->_M_hash_code(__k);
1059 std::size_t __bkt = _M_bucket_index(__code);
1060 if (__node_base_ptr __prev_node = _M_find_before_node(__bkt, __k, __code))
1061 __nh = _M_extract_node(__bkt, __prev_node);
1066 template<
typename _Compatible_Hashtable>
1068 _M_merge_unique(_Compatible_Hashtable& __src)
1070 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1071 node_type>,
"Node types are compatible");
1072 __glibcxx_assert(get_allocator() == __src.get_allocator());
1074 auto __n_elt = __src.size();
1075 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1078 const key_type& __k = _ExtractKey{}(*__pos);
1080 = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
1081 size_type __bkt = _M_bucket_index(__code);
1082 if (_M_find_node(__bkt, __k, __code) ==
nullptr)
1084 auto __nh = __src.extract(__pos);
1085 _M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
1086 __nh._M_ptr =
nullptr;
1089 else if (__n_elt != 1)
1095 template<
typename _Compatible_Hashtable>
1097 _M_merge_multi(_Compatible_Hashtable& __src)
1099 static_assert(is_same_v<
typename _Compatible_Hashtable::node_type,
1100 node_type>,
"Node types are compatible");
1101 __glibcxx_assert(get_allocator() == __src.get_allocator());
1103 __node_ptr __hint =
nullptr;
1104 this->reserve(
size() + __src.size());
1105 for (
auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
1109 = this->_M_hash_code(__src.hash_function(), *__pos._M_cur);
1110 auto __nh = __src.extract(__pos);
1111 __hint = _M_insert_multi_node(__hint, __code, __nh._M_ptr)._M_cur;
1112 __nh._M_ptr =
nullptr;
1119 void _M_rehash_aux(size_type __bkt_count,
true_type __uks);
1122 void _M_rehash_aux(size_type __bkt_count,
false_type __uks);
1126 void _M_rehash(size_type __bkt_count,
const __rehash_state& __state);
1131 template<
typename _Key,
typename _Value,
typename _Alloc,
1132 typename _ExtractKey,
typename _Equal,
1133 typename _Hash,
typename _RangeHash,
typename _Unused,
1134 typename _RehashPolicy,
typename _Traits>
1136 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1137 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1138 _M_bucket_begin(size_type __bkt)
const
1141 __node_base_ptr __n = _M_buckets[__bkt];
1142 return __n ?
static_cast<__node_ptr
>(__n->_M_nxt) :
nullptr;
1145 template<
typename _Key,
typename _Value,
typename _Alloc,
1146 typename _ExtractKey,
typename _Equal,
1147 typename _Hash,
typename _RangeHash,
typename _Unused,
1148 typename _RehashPolicy,
typename _Traits>
1149 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1150 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1151 _Hashtable(size_type __bkt_count_hint,
1152 const _Hash& __h,
const _Equal& __eq,
const allocator_type& __a)
1153 : _Hashtable(__h, __eq, __a)
1155 auto __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count_hint);
1156 if (__bkt_count > _M_bucket_count)
1158 _M_buckets = _M_allocate_buckets(__bkt_count);
1159 _M_bucket_count = __bkt_count;
1163 template<
typename _Key,
typename _Value,
typename _Alloc,
1164 typename _ExtractKey,
typename _Equal,
1165 typename _Hash,
typename _RangeHash,
typename _Unused,
1166 typename _RehashPolicy,
typename _Traits>
1167 template<
typename _InputIterator>
1168 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1169 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1170 _Hashtable(_InputIterator __f, _InputIterator __l,
1171 size_type __bkt_count_hint,
1172 const _Hash& __h,
const _Equal& __eq,
1174 : _Hashtable(__bkt_count_hint, __h, __eq, __a)
1176 for (; __f != __l; ++__f)
1180 template<
typename _Key,
typename _Value,
typename _Alloc,
1181 typename _ExtractKey,
typename _Equal,
1182 typename _Hash,
typename _RangeHash,
typename _Unused,
1183 typename _RehashPolicy,
typename _Traits>
1184 template<
typename _InputIterator>
1185 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1186 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1187 _Hashtable(_InputIterator __f, _InputIterator __l,
1188 size_type __bkt_count_hint,
1189 const _Hash& __h,
const _Equal& __eq,
1191 : _Hashtable(__h, __eq, __a)
1193 auto __nb_elems = __detail::__distance_fw(__f, __l);
1195 _M_rehash_policy._M_next_bkt(
1196 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
1199 if (__bkt_count > _M_bucket_count)
1201 _M_buckets = _M_allocate_buckets(__bkt_count);
1202 _M_bucket_count = __bkt_count;
1205 for (; __f != __l; ++__f)
1209 template<
typename _Key,
typename _Value,
typename _Alloc,
1210 typename _ExtractKey,
typename _Equal,
1211 typename _Hash,
typename _RangeHash,
typename _Unused,
1212 typename _RehashPolicy,
typename _Traits>
1214 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1215 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1216 operator=(
const _Hashtable& __ht)
1222 if (__node_alloc_traits::_S_propagate_on_copy_assign())
1224 auto& __this_alloc = this->_M_node_allocator();
1225 auto& __that_alloc = __ht._M_node_allocator();
1226 if (!__node_alloc_traits::_S_always_equal()
1227 && __this_alloc != __that_alloc)
1230 this->_M_deallocate_nodes(_M_begin());
1231 _M_before_begin._M_nxt =
nullptr;
1232 _M_deallocate_buckets();
1233 _M_buckets =
nullptr;
1234 std::__alloc_on_copy(__this_alloc, __that_alloc);
1235 __hashtable_base::operator=(__ht);
1236 _M_bucket_count = __ht._M_bucket_count;
1237 _M_element_count = __ht._M_element_count;
1238 _M_rehash_policy = __ht._M_rehash_policy;
1239 __alloc_node_gen_t __alloc_node_gen(*
this);
1242 _M_assign(__ht, __alloc_node_gen);
1249 __throw_exception_again;
1253 std::__alloc_on_copy(__this_alloc, __that_alloc);
1257 _M_assign_elements(__ht);
1261 template<
typename _Key,
typename _Value,
typename _Alloc,
1262 typename _ExtractKey,
typename _Equal,
1263 typename _Hash,
typename _RangeHash,
typename _Unused,
1264 typename _RehashPolicy,
typename _Traits>
1265 template<
typename _Ht>
1267 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1268 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1269 _M_assign_elements(_Ht&& __ht)
1271 __buckets_ptr __former_buckets =
nullptr;
1272 std::size_t __former_bucket_count = _M_bucket_count;
1273 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1275 if (_M_bucket_count != __ht._M_bucket_count)
1277 __former_buckets = _M_buckets;
1278 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1279 _M_bucket_count = __ht._M_bucket_count;
1282 __builtin_memset(_M_buckets, 0,
1283 _M_bucket_count *
sizeof(__node_base_ptr));
1287 __hashtable_base::operator=(std::forward<_Ht>(__ht));
1288 _M_element_count = __ht._M_element_count;
1289 _M_rehash_policy = __ht._M_rehash_policy;
1290 __reuse_or_alloc_node_gen_t __roan(_M_begin(), *
this);
1291 _M_before_begin._M_nxt =
nullptr;
1292 _M_assign(std::forward<_Ht>(__ht), __roan);
1293 if (__former_buckets)
1294 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
1298 if (__former_buckets)
1301 _M_deallocate_buckets();
1302 _M_rehash_policy._M_reset(__former_state);
1303 _M_buckets = __former_buckets;
1304 _M_bucket_count = __former_bucket_count;
1306 __builtin_memset(_M_buckets, 0,
1307 _M_bucket_count *
sizeof(__node_base_ptr));
1308 __throw_exception_again;
1312 template<
typename _Key,
typename _Value,
typename _Alloc,
1313 typename _ExtractKey,
typename _Equal,
1314 typename _Hash,
typename _RangeHash,
typename _Unused,
1315 typename _RehashPolicy,
typename _Traits>
1316 template<
typename _Ht,
typename _NodeGenerator>
1318 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1319 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1320 _M_assign(_Ht&& __ht,
const _NodeGenerator& __node_gen)
1322 __buckets_ptr __buckets =
nullptr;
1324 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
1328 if (!__ht._M_before_begin._M_nxt)
1333 __node_ptr __ht_n = __ht._M_begin();
1335 = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1336 this->_M_copy_code(*__this_n, *__ht_n);
1337 _M_update_bbegin(__this_n);
1340 __node_ptr __prev_n = __this_n;
1341 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
1343 __this_n = __node_gen(__fwd_value_for<_Ht>(__ht_n->_M_v()));
1344 __prev_n->_M_nxt = __this_n;
1345 this->_M_copy_code(*__this_n, *__ht_n);
1346 size_type __bkt = _M_bucket_index(*__this_n);
1347 if (!_M_buckets[__bkt])
1348 _M_buckets[__bkt] = __prev_n;
1349 __prev_n = __this_n;
1356 _M_deallocate_buckets();
1357 __throw_exception_again;
1361 template<
typename _Key,
typename _Value,
typename _Alloc,
1362 typename _ExtractKey,
typename _Equal,
1363 typename _Hash,
typename _RangeHash,
typename _Unused,
1364 typename _RehashPolicy,
typename _Traits>
1366 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1367 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1370 _M_rehash_policy._M_reset();
1371 _M_bucket_count = 1;
1372 _M_single_bucket =
nullptr;
1373 _M_buckets = &_M_single_bucket;
1374 _M_before_begin._M_nxt =
nullptr;
1375 _M_element_count = 0;
1378 template<
typename _Key,
typename _Value,
typename _Alloc,
1379 typename _ExtractKey,
typename _Equal,
1380 typename _Hash,
typename _RangeHash,
typename _Unused,
1381 typename _RehashPolicy,
typename _Traits>
1383 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1384 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1385 _M_move_assign(_Hashtable&& __ht,
true_type)
1390 this->_M_deallocate_nodes(_M_begin());
1391 _M_deallocate_buckets();
1392 __hashtable_base::operator=(
std::move(__ht));
1393 _M_rehash_policy = __ht._M_rehash_policy;
1394 if (!__ht._M_uses_single_bucket())
1395 _M_buckets = __ht._M_buckets;
1398 _M_buckets = &_M_single_bucket;
1399 _M_single_bucket = __ht._M_single_bucket;
1402 _M_bucket_count = __ht._M_bucket_count;
1403 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1404 _M_element_count = __ht._M_element_count;
1405 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1412 template<
typename _Key,
typename _Value,
typename _Alloc,
1413 typename _ExtractKey,
typename _Equal,
1414 typename _Hash,
typename _RangeHash,
typename _Unused,
1415 typename _RehashPolicy,
typename _Traits>
1417 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1418 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1419 _M_move_assign(_Hashtable&& __ht,
false_type)
1421 if (__ht._M_node_allocator() == this->_M_node_allocator())
1431 template<
typename _Key,
typename _Value,
typename _Alloc,
1432 typename _ExtractKey,
typename _Equal,
1433 typename _Hash,
typename _RangeHash,
typename _Unused,
1434 typename _RehashPolicy,
typename _Traits>
1435 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1436 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1437 _Hashtable(
const _Hashtable& __ht)
1438 : __hashtable_base(__ht),
1440 __rehash_base(__ht),
1442 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1443 __enable_default_ctor(__ht),
1444 _M_buckets(nullptr),
1445 _M_bucket_count(__ht._M_bucket_count),
1446 _M_element_count(__ht._M_element_count),
1447 _M_rehash_policy(__ht._M_rehash_policy)
1449 __alloc_node_gen_t __alloc_node_gen(*
this);
1450 _M_assign(__ht, __alloc_node_gen);
1453 template<
typename _Key,
typename _Value,
typename _Alloc,
1454 typename _ExtractKey,
typename _Equal,
1455 typename _Hash,
typename _RangeHash,
typename _Unused,
1456 typename _RehashPolicy,
typename _Traits>
1457 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1458 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1459 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1461 noexcept(_S_nothrow_move())
1462 : __hashtable_base(__ht),
1464 __rehash_base(__ht),
1465 __hashtable_alloc(
std::move(__a)),
1466 __enable_default_ctor(__ht),
1467 _M_buckets(__ht._M_buckets),
1468 _M_bucket_count(__ht._M_bucket_count),
1469 _M_before_begin(__ht._M_before_begin._M_nxt),
1470 _M_element_count(__ht._M_element_count),
1471 _M_rehash_policy(__ht._M_rehash_policy)
1474 if (__ht._M_uses_single_bucket())
1476 _M_buckets = &_M_single_bucket;
1477 _M_single_bucket = __ht._M_single_bucket;
1486 template<
typename _Key,
typename _Value,
typename _Alloc,
1487 typename _ExtractKey,
typename _Equal,
1488 typename _Hash,
typename _RangeHash,
typename _Unused,
1489 typename _RehashPolicy,
typename _Traits>
1490 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1491 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1492 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1493 : __hashtable_base(__ht),
1495 __rehash_base(__ht),
1496 __hashtable_alloc(__node_alloc_type(__a)),
1497 __enable_default_ctor(__ht),
1499 _M_bucket_count(__ht._M_bucket_count),
1500 _M_element_count(__ht._M_element_count),
1501 _M_rehash_policy(__ht._M_rehash_policy)
1503 __alloc_node_gen_t __alloc_node_gen(*
this);
1504 _M_assign(__ht, __alloc_node_gen);
1507 template<
typename _Key,
typename _Value,
typename _Alloc,
1508 typename _ExtractKey,
typename _Equal,
1509 typename _Hash,
typename _RangeHash,
typename _Unused,
1510 typename _RehashPolicy,
typename _Traits>
1511 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1512 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1513 _Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a,
1515 : __hashtable_base(__ht),
1517 __rehash_base(__ht),
1518 __hashtable_alloc(
std::move(__a)),
1519 __enable_default_ctor(__ht),
1520 _M_buckets(nullptr),
1521 _M_bucket_count(__ht._M_bucket_count),
1522 _M_element_count(__ht._M_element_count),
1523 _M_rehash_policy(__ht._M_rehash_policy)
1525 if (__ht._M_node_allocator() == this->_M_node_allocator())
1527 if (__ht._M_uses_single_bucket())
1529 _M_buckets = &_M_single_bucket;
1530 _M_single_bucket = __ht._M_single_bucket;
1533 _M_buckets = __ht._M_buckets;
1537 _M_update_bbegin(__ht._M_begin());
1543 __alloc_node_gen_t __alloc_gen(*
this);
1545 using _Fwd_Ht = __conditional_t<
1546 __move_if_noexcept_cond<value_type>::value,
1547 const _Hashtable&, _Hashtable&&>;
1548 _M_assign(std::forward<_Fwd_Ht>(__ht), __alloc_gen);
1553 template<
typename _Key,
typename _Value,
typename _Alloc,
1554 typename _ExtractKey,
typename _Equal,
1555 typename _Hash,
typename _RangeHash,
typename _Unused,
1556 typename _RehashPolicy,
typename _Traits>
1557 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1558 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1559 ~_Hashtable() noexcept
1564 static_assert(noexcept(declval<const __hash_code_base_access&>()
1565 ._M_bucket_index(declval<const __node_value_type&>(),
1567 "Cache the hash code or qualify your functors involved"
1568 " in hash code and bucket index computation with noexcept");
1571 _M_deallocate_buckets();
1574 template<
typename _Key,
typename _Value,
typename _Alloc,
1575 typename _ExtractKey,
typename _Equal,
1576 typename _Hash,
typename _RangeHash,
typename _Unused,
1577 typename _RehashPolicy,
typename _Traits>
1579 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1580 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>
::
1581 swap(_Hashtable& __x)
1582 noexcept(__and_<__is_nothrow_swappable<_Hash>,
1583 __is_nothrow_swappable<_Equal>>::value)
1590 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1591 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1594 if (this->_M_uses_single_bucket())
1596 if (!__x._M_uses_single_bucket())
1598 _M_buckets = __x._M_buckets;
1599 __x._M_buckets = &__x._M_single_bucket;
1602 else if (__x._M_uses_single_bucket())
1604 __x._M_buckets = _M_buckets;
1605 _M_buckets = &_M_single_bucket;
1610 std::swap(_M_bucket_count, __x._M_bucket_count);
1611 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1612 std::swap(_M_element_count, __x._M_element_count);
1613 std::swap(_M_single_bucket, __x._M_single_bucket);
1618 __x._M_update_bbegin();
1621 template<
typename _Key,
typename _Value,
typename _Alloc,
1622 typename _ExtractKey,
typename _Equal,
1623 typename _Hash,
typename _RangeHash,
typename _Unused,
1624 typename _RehashPolicy,
typename _Traits>
1626 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1627 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1628 find(
const key_type& __k)
1631 __hash_code __code = this->_M_hash_code(__k);
1632 std::size_t __bkt = _M_bucket_index(__code);
1633 return iterator(_M_find_node(__bkt, __k, __code));
1636 template<
typename _Key,
typename _Value,
typename _Alloc,
1637 typename _ExtractKey,
typename _Equal,
1638 typename _Hash,
typename _RangeHash,
typename _Unused,
1639 typename _RehashPolicy,
typename _Traits>
1641 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1642 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1643 find(
const key_type& __k)
const
1646 __hash_code __code = this->_M_hash_code(__k);
1647 std::size_t __bkt = _M_bucket_index(__code);
1648 return const_iterator(_M_find_node(__bkt, __k, __code));
1651 #if __cplusplus > 201703L
1652 template<
typename _Key,
typename _Value,
typename _Alloc,
1653 typename _ExtractKey,
typename _Equal,
1654 typename _Hash,
typename _RangeHash,
typename _Unused,
1655 typename _RehashPolicy,
typename _Traits>
1656 template<
typename _Kt,
typename,
typename>
1658 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1659 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1660 _M_find_tr(
const _Kt& __k)
1663 __hash_code __code = this->_M_hash_code_tr(__k);
1664 std::size_t __bkt = _M_bucket_index(__code);
1665 return iterator(_M_find_node_tr(__bkt, __k, __code));
1668 template<
typename _Key,
typename _Value,
typename _Alloc,
1669 typename _ExtractKey,
typename _Equal,
1670 typename _Hash,
typename _RangeHash,
typename _Unused,
1671 typename _RehashPolicy,
typename _Traits>
1672 template<
typename _Kt,
typename,
typename>
1674 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1675 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1676 _M_find_tr(
const _Kt& __k)
const
1679 __hash_code __code = this->_M_hash_code_tr(__k);
1680 std::size_t __bkt = _M_bucket_index(__code);
1681 return const_iterator(_M_find_node_tr(__bkt, __k, __code));
1685 template<
typename _Key,
typename _Value,
typename _Alloc,
1686 typename _ExtractKey,
typename _Equal,
1687 typename _Hash,
typename _RangeHash,
typename _Unused,
1688 typename _RehashPolicy,
typename _Traits>
1690 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1691 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1692 count(
const key_type& __k)
const
1695 auto __it = find(__k);
1699 if (__unique_keys::value)
1705 size_type __result = 1;
1706 for (
auto __ref = __it++;
1707 __it._M_cur && this->_M_node_equals(*__ref._M_cur, *__it._M_cur);
1714 #if __cplusplus > 201703L
1715 template<
typename _Key,
typename _Value,
typename _Alloc,
1716 typename _ExtractKey,
typename _Equal,
1717 typename _Hash,
typename _RangeHash,
typename _Unused,
1718 typename _RehashPolicy,
typename _Traits>
1719 template<
typename _Kt,
typename,
typename>
1721 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1722 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1723 _M_count_tr(
const _Kt& __k)
const
1726 __hash_code __code = this->_M_hash_code_tr(__k);
1727 std::size_t __bkt = _M_bucket_index(__code);
1728 auto __n = _M_find_node_tr(__bkt, __k, __code);
1736 size_type __result = 1;
1738 __it._M_cur && this->_M_equals_tr(__k, __code, *__it._M_cur);
1746 template<
typename _Key,
typename _Value,
typename _Alloc,
1747 typename _ExtractKey,
typename _Equal,
1748 typename _Hash,
typename _RangeHash,
typename _Unused,
1749 typename _RehashPolicy,
typename _Traits>
1751 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1752 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1753 equal_range(
const key_type& __k)
1754 -> pair<iterator, iterator>
1756 auto __ite = find(__k);
1758 return { __ite, __ite };
1760 auto __beg = __ite++;
1761 if (__unique_keys::value)
1762 return { __beg, __ite };
1767 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1770 return { __beg, __ite };
1773 template<
typename _Key,
typename _Value,
typename _Alloc,
1774 typename _ExtractKey,
typename _Equal,
1775 typename _Hash,
typename _RangeHash,
typename _Unused,
1776 typename _RehashPolicy,
typename _Traits>
1778 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1779 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1780 equal_range(
const key_type& __k)
const
1781 -> pair<const_iterator, const_iterator>
1783 auto __ite = find(__k);
1785 return { __ite, __ite };
1787 auto __beg = __ite++;
1788 if (__unique_keys::value)
1789 return { __beg, __ite };
1794 while (__ite._M_cur && this->_M_node_equals(*__beg._M_cur, *__ite._M_cur))
1797 return { __beg, __ite };
1800 #if __cplusplus > 201703L
1801 template<
typename _Key,
typename _Value,
typename _Alloc,
1802 typename _ExtractKey,
typename _Equal,
1803 typename _Hash,
typename _RangeHash,
typename _Unused,
1804 typename _RehashPolicy,
typename _Traits>
1805 template<
typename _Kt,
typename,
typename>
1807 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1808 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1809 _M_equal_range_tr(
const _Kt& __k)
1810 -> pair<iterator, iterator>
1812 __hash_code __code = this->_M_hash_code_tr(__k);
1813 std::size_t __bkt = _M_bucket_index(__code);
1814 auto __n = _M_find_node_tr(__bkt, __k, __code);
1815 iterator __ite(__n);
1817 return { __ite, __ite };
1822 auto __beg = __ite++;
1823 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1826 return { __beg, __ite };
1829 template<
typename _Key,
typename _Value,
typename _Alloc,
1830 typename _ExtractKey,
typename _Equal,
1831 typename _Hash,
typename _RangeHash,
typename _Unused,
1832 typename _RehashPolicy,
typename _Traits>
1833 template<
typename _Kt,
typename,
typename>
1835 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1836 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1837 _M_equal_range_tr(
const _Kt& __k)
const
1838 -> pair<const_iterator, const_iterator>
1840 __hash_code __code = this->_M_hash_code_tr(__k);
1841 std::size_t __bkt = _M_bucket_index(__code);
1842 auto __n = _M_find_node_tr(__bkt, __k, __code);
1843 const_iterator __ite(__n);
1845 return { __ite, __ite };
1850 auto __beg = __ite++;
1851 while (__ite._M_cur && this->_M_equals_tr(__k, __code, *__ite._M_cur))
1854 return { __beg, __ite };
1860 template<
typename _Key,
typename _Value,
typename _Alloc,
1861 typename _ExtractKey,
typename _Equal,
1862 typename _Hash,
typename _RangeHash,
typename _Unused,
1863 typename _RehashPolicy,
typename _Traits>
1865 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1866 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1867 _M_find_before_node(size_type __bkt,
const key_type& __k,
1868 __hash_code __code)
const
1871 __node_base_ptr __prev_p = _M_buckets[__bkt];
1875 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1876 __p = __p->_M_next())
1878 if (this->_M_equals(__k, __code, *__p))
1881 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1889 template<
typename _Key,
typename _Value,
typename _Alloc,
1890 typename _ExtractKey,
typename _Equal,
1891 typename _Hash,
typename _RangeHash,
typename _Unused,
1892 typename _RehashPolicy,
typename _Traits>
1893 template<
typename _Kt>
1895 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1896 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1897 _M_find_before_node_tr(size_type __bkt,
const _Kt& __k,
1898 __hash_code __code)
const
1901 __node_base_ptr __prev_p = _M_buckets[__bkt];
1905 for (__node_ptr __p =
static_cast<__node_ptr
>(__prev_p->_M_nxt);;
1906 __p = __p->_M_next())
1908 if (this->_M_equals_tr(__k, __code, *__p))
1911 if (!__p->_M_nxt || _M_bucket_index(*__p->_M_next()) != __bkt)
1919 template<
typename _Key,
typename _Value,
typename _Alloc,
1920 typename _ExtractKey,
typename _Equal,
1921 typename _Hash,
typename _RangeHash,
typename _Unused,
1922 typename _RehashPolicy,
typename _Traits>
1924 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1925 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1926 _M_insert_bucket_begin(size_type __bkt, __node_ptr __node)
1928 if (_M_buckets[__bkt])
1932 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1933 _M_buckets[__bkt]->_M_nxt = __node;
1940 __node->_M_nxt = _M_before_begin._M_nxt;
1941 _M_before_begin._M_nxt = __node;
1946 _M_buckets[_M_bucket_index(*__node->_M_next())] = __node;
1948 _M_buckets[__bkt] = &_M_before_begin;
1952 template<
typename _Key,
typename _Value,
typename _Alloc,
1953 typename _ExtractKey,
typename _Equal,
1954 typename _Hash,
typename _RangeHash,
typename _Unused,
1955 typename _RehashPolicy,
typename _Traits>
1957 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1958 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1959 _M_remove_bucket_begin(size_type __bkt, __node_ptr __next,
1960 size_type __next_bkt)
1962 if (!__next || __next_bkt != __bkt)
1967 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1970 if (&_M_before_begin == _M_buckets[__bkt])
1971 _M_before_begin._M_nxt = __next;
1972 _M_buckets[__bkt] =
nullptr;
1976 template<
typename _Key,
typename _Value,
typename _Alloc,
1977 typename _ExtractKey,
typename _Equal,
1978 typename _Hash,
typename _RangeHash,
typename _Unused,
1979 typename _RehashPolicy,
typename _Traits>
1981 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1982 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
1983 _M_get_previous_node(size_type __bkt, __node_ptr __n)
1986 __node_base_ptr __prev_n = _M_buckets[__bkt];
1987 while (__prev_n->_M_nxt != __n)
1988 __prev_n = __prev_n->_M_nxt;
1992 template<
typename _Key,
typename _Value,
typename _Alloc,
1993 typename _ExtractKey,
typename _Equal,
1994 typename _Hash,
typename _RangeHash,
typename _Unused,
1995 typename _RehashPolicy,
typename _Traits>
1996 template<
typename... _Args>
1998 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1999 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2000 _M_emplace(
true_type , _Args&&... __args)
2001 -> pair<iterator, bool>
2004 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2005 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2006 __hash_code __code = this->_M_hash_code(__k);
2007 size_type __bkt = _M_bucket_index(__code);
2008 if (__node_ptr __p = _M_find_node(__bkt, __k, __code))
2010 return std::make_pair(iterator(__p),
false);
2013 auto __pos = _M_insert_unique_node(__bkt, __code, __node._M_node);
2014 __node._M_node =
nullptr;
2015 return { __pos,
true };
2018 template<
typename _Key,
typename _Value,
typename _Alloc,
2019 typename _ExtractKey,
typename _Equal,
2020 typename _Hash,
typename _RangeHash,
typename _Unused,
2021 typename _RehashPolicy,
typename _Traits>
2022 template<
typename... _Args>
2024 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2025 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2026 _M_emplace(const_iterator __hint,
false_type ,
2031 _Scoped_node __node {
this, std::forward<_Args>(__args)... };
2032 const key_type& __k = _ExtractKey{}(__node._M_node->_M_v());
2034 __hash_code __code = this->_M_hash_code(__k);
2036 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
2037 __node._M_node =
nullptr;
2041 template<
typename _Key,
typename _Value,
typename _Alloc,
2042 typename _ExtractKey,
typename _Equal,
2043 typename _Hash,
typename _RangeHash,
typename _Unused,
2044 typename _RehashPolicy,
typename _Traits>
2046 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2047 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2048 _M_insert_unique_node(size_type __bkt, __hash_code __code,
2049 __node_ptr __node, size_type __n_elt)
2052 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2054 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count,
2057 if (__do_rehash.
first)
2059 _M_rehash(__do_rehash.
second, __saved_state);
2060 __bkt = _M_bucket_index(__code);
2063 this->_M_store_code(*__node, __code);
2066 _M_insert_bucket_begin(__bkt, __node);
2068 return iterator(__node);
2071 template<
typename _Key,
typename _Value,
typename _Alloc,
2072 typename _ExtractKey,
typename _Equal,
2073 typename _Hash,
typename _RangeHash,
typename _Unused,
2074 typename _RehashPolicy,
typename _Traits>
2076 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2077 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2078 _M_insert_multi_node(__node_ptr __hint,
2079 __hash_code __code, __node_ptr __node)
2082 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2084 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
2086 if (__do_rehash.
first)
2087 _M_rehash(__do_rehash.
second, __saved_state);
2089 this->_M_store_code(*__node, __code);
2090 const key_type& __k = _ExtractKey{}(__node->_M_v());
2091 size_type __bkt = _M_bucket_index(__code);
2095 __node_base_ptr __prev
2096 = __builtin_expect(__hint !=
nullptr,
false)
2097 && this->_M_equals(__k, __code, *__hint)
2099 : _M_find_before_node(__bkt, __k, __code);
2104 __node->_M_nxt = __prev->_M_nxt;
2105 __prev->_M_nxt = __node;
2106 if (__builtin_expect(__prev == __hint,
false))
2110 && !this->_M_equals(__k, __code, *__node->_M_next()))
2112 size_type __next_bkt = _M_bucket_index(*__node->_M_next());
2113 if (__next_bkt != __bkt)
2114 _M_buckets[__next_bkt] = __node;
2121 _M_insert_bucket_begin(__bkt, __node);
2123 return iterator(__node);
2127 template<
typename _Key,
typename _Value,
typename _Alloc,
2128 typename _ExtractKey,
typename _Equal,
2129 typename _Hash,
typename _RangeHash,
typename _Unused,
2130 typename _RehashPolicy,
typename _Traits>
2131 template<
typename _Kt,
typename _Arg,
typename _NodeGenerator>
2133 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2134 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2135 _M_insert_unique(_Kt&& __k, _Arg&& __v,
2136 const _NodeGenerator& __node_gen)
2137 -> pair<iterator, bool>
2139 __hash_code __code = this->_M_hash_code_tr(__k);
2140 size_type __bkt = _M_bucket_index(__code);
2142 if (__node_ptr __node = _M_find_node_tr(__bkt, __k, __code))
2143 return { iterator(__node),
false };
2145 _Scoped_node __node {
2146 __node_builder_t::_S_build(std::forward<_Kt>(__k),
2147 std::forward<_Arg>(__v),
2152 = _M_insert_unique_node(__bkt, __code, __node._M_node);
2153 __node._M_node =
nullptr;
2154 return { __pos,
true };
2158 template<
typename _Key,
typename _Value,
typename _Alloc,
2159 typename _ExtractKey,
typename _Equal,
2160 typename _Hash,
typename _RangeHash,
typename _Unused,
2161 typename _RehashPolicy,
typename _Traits>
2162 template<
typename _Arg,
typename _NodeGenerator>
2164 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2165 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2166 _M_insert(const_iterator __hint, _Arg&& __v,
2167 const _NodeGenerator& __node_gen,
2172 _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)),
this };
2176 = this->_M_hash_code(_ExtractKey{}(__node._M_node->_M_v()));
2179 = _M_insert_multi_node(__hint._M_cur, __code, __node._M_node);
2180 __node._M_node =
nullptr;
2184 template<
typename _Key,
typename _Value,
typename _Alloc,
2185 typename _ExtractKey,
typename _Equal,
2186 typename _Hash,
typename _RangeHash,
typename _Unused,
2187 typename _RehashPolicy,
typename _Traits>
2189 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2190 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2191 erase(const_iterator __it)
2194 __node_ptr __n = __it._M_cur;
2195 std::size_t __bkt = _M_bucket_index(*__n);
2200 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2201 return _M_erase(__bkt, __prev_n, __n);
2204 template<
typename _Key,
typename _Value,
typename _Alloc,
2205 typename _ExtractKey,
typename _Equal,
2206 typename _Hash,
typename _RangeHash,
typename _Unused,
2207 typename _RehashPolicy,
typename _Traits>
2209 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2210 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2211 _M_erase(size_type __bkt, __node_base_ptr __prev_n, __node_ptr __n)
2214 if (__prev_n == _M_buckets[__bkt])
2215 _M_remove_bucket_begin(__bkt, __n->_M_next(),
2216 __n->_M_nxt ? _M_bucket_index(*__n->_M_next()) : 0);
2217 else if (__n->_M_nxt)
2219 size_type __next_bkt = _M_bucket_index(*__n->_M_next());
2220 if (__next_bkt != __bkt)
2221 _M_buckets[__next_bkt] = __prev_n;
2224 __prev_n->_M_nxt = __n->_M_nxt;
2225 iterator __result(__n->_M_next());
2226 this->_M_deallocate_node(__n);
2232 template<
typename _Key,
typename _Value,
typename _Alloc,
2233 typename _ExtractKey,
typename _Equal,
2234 typename _Hash,
typename _RangeHash,
typename _Unused,
2235 typename _RehashPolicy,
typename _Traits>
2237 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2238 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2239 _M_erase(
true_type ,
const key_type& __k)
2242 __hash_code __code = this->_M_hash_code(__k);
2243 std::size_t __bkt = _M_bucket_index(__code);
2246 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2251 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2252 _M_erase(__bkt, __prev_n, __n);
2256 template<
typename _Key,
typename _Value,
typename _Alloc,
2257 typename _ExtractKey,
typename _Equal,
2258 typename _Hash,
typename _RangeHash,
typename _Unused,
2259 typename _RehashPolicy,
typename _Traits>
2261 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2262 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2266 __hash_code __code = this->_M_hash_code(__k);
2267 std::size_t __bkt = _M_bucket_index(__code);
2270 __node_base_ptr __prev_n = _M_find_before_node(__bkt, __k, __code);
2280 __node_ptr __n =
static_cast<__node_ptr
>(__prev_n->_M_nxt);
2281 __node_ptr __n_last = __n->_M_next();
2282 while (__n_last && this->_M_node_equals(*__n, *__n_last))
2283 __n_last = __n_last->_M_next();
2285 std::size_t __n_last_bkt = __n_last ? _M_bucket_index(*__n_last) : __bkt;
2288 size_type __result = 0;
2291 __node_ptr __p = __n->_M_next();
2292 this->_M_deallocate_node(__n);
2296 while (__n != __n_last);
2298 _M_element_count -= __result;
2299 if (__prev_n == _M_buckets[__bkt])
2300 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
2301 else if (__n_last_bkt != __bkt)
2302 _M_buckets[__n_last_bkt] = __prev_n;
2303 __prev_n->_M_nxt = __n_last;
2307 template<
typename _Key,
typename _Value,
typename _Alloc,
2308 typename _ExtractKey,
typename _Equal,
2309 typename _Hash,
typename _RangeHash,
typename _Unused,
2310 typename _RehashPolicy,
typename _Traits>
2312 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2313 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2314 erase(const_iterator __first, const_iterator __last)
2317 __node_ptr __n = __first._M_cur;
2318 __node_ptr __last_n = __last._M_cur;
2319 if (__n == __last_n)
2320 return iterator(__n);
2322 std::size_t __bkt = _M_bucket_index(*__n);
2324 __node_base_ptr __prev_n = _M_get_previous_node(__bkt, __n);
2325 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
2326 std::size_t __n_bkt = __bkt;
2331 __node_ptr __tmp = __n;
2332 __n = __n->_M_next();
2333 this->_M_deallocate_node(__tmp);
2337 __n_bkt = _M_bucket_index(*__n);
2339 while (__n != __last_n && __n_bkt == __bkt);
2340 if (__is_bucket_begin)
2341 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
2342 if (__n == __last_n)
2344 __is_bucket_begin =
true;
2348 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
2349 _M_buckets[__n_bkt] = __prev_n;
2350 __prev_n->_M_nxt = __n;
2351 return iterator(__n);
2354 template<
typename _Key,
typename _Value,
typename _Alloc,
2355 typename _ExtractKey,
typename _Equal,
2356 typename _Hash,
typename _RangeHash,
typename _Unused,
2357 typename _RehashPolicy,
typename _Traits>
2359 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2360 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2363 this->_M_deallocate_nodes(_M_begin());
2364 __builtin_memset(_M_buckets, 0,
2365 _M_bucket_count *
sizeof(__node_base_ptr));
2366 _M_element_count = 0;
2367 _M_before_begin._M_nxt =
nullptr;
2370 template<
typename _Key,
typename _Value,
typename _Alloc,
2371 typename _ExtractKey,
typename _Equal,
2372 typename _Hash,
typename _RangeHash,
typename _Unused,
2373 typename _RehashPolicy,
typename _Traits>
2375 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2376 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2377 rehash(size_type __bkt_count)
2379 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
2381 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
2383 __bkt_count = _M_rehash_policy._M_next_bkt(__bkt_count);
2385 if (__bkt_count != _M_bucket_count)
2386 _M_rehash(__bkt_count, __saved_state);
2390 _M_rehash_policy._M_reset(__saved_state);
2393 template<
typename _Key,
typename _Value,
typename _Alloc,
2394 typename _ExtractKey,
typename _Equal,
2395 typename _Hash,
typename _RangeHash,
typename _Unused,
2396 typename _RehashPolicy,
typename _Traits>
2398 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2399 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2400 _M_rehash(size_type __bkt_count,
const __rehash_state& __state)
2404 _M_rehash_aux(__bkt_count, __unique_keys{});
2410 _M_rehash_policy._M_reset(__state);
2411 __throw_exception_again;
2416 template<
typename _Key,
typename _Value,
typename _Alloc,
2417 typename _ExtractKey,
typename _Equal,
2418 typename _Hash,
typename _RangeHash,
typename _Unused,
2419 typename _RehashPolicy,
typename _Traits>
2421 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2422 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2423 _M_rehash_aux(size_type __bkt_count,
true_type )
2425 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2426 __node_ptr __p = _M_begin();
2427 _M_before_begin._M_nxt =
nullptr;
2428 std::size_t __bbegin_bkt = 0;
2431 __node_ptr __next = __p->_M_next();
2433 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2434 if (!__new_buckets[__bkt])
2436 __p->_M_nxt = _M_before_begin._M_nxt;
2437 _M_before_begin._M_nxt = __p;
2438 __new_buckets[__bkt] = &_M_before_begin;
2440 __new_buckets[__bbegin_bkt] = __p;
2441 __bbegin_bkt = __bkt;
2445 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2446 __new_buckets[__bkt]->_M_nxt = __p;
2452 _M_deallocate_buckets();
2453 _M_bucket_count = __bkt_count;
2454 _M_buckets = __new_buckets;
2459 template<
typename _Key,
typename _Value,
typename _Alloc,
2460 typename _ExtractKey,
typename _Equal,
2461 typename _Hash,
typename _RangeHash,
typename _Unused,
2462 typename _RehashPolicy,
typename _Traits>
2464 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2465 _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
2466 _M_rehash_aux(size_type __bkt_count,
false_type )
2468 __buckets_ptr __new_buckets = _M_allocate_buckets(__bkt_count);
2469 __node_ptr __p = _M_begin();
2470 _M_before_begin._M_nxt =
nullptr;
2471 std::size_t __bbegin_bkt = 0;
2472 std::size_t __prev_bkt = 0;
2473 __node_ptr __prev_p =
nullptr;
2474 bool __check_bucket =
false;
2478 __node_ptr __next = __p->_M_next();
2480 = __hash_code_base::_M_bucket_index(*__p, __bkt_count);
2482 if (__prev_p && __prev_bkt == __bkt)
2487 __p->_M_nxt = __prev_p->_M_nxt;
2488 __prev_p->_M_nxt = __p;
2495 __check_bucket =
true;
2503 if (__prev_p->_M_nxt)
2505 std::size_t __next_bkt
2506 = __hash_code_base::_M_bucket_index(
2507 *__prev_p->_M_next(), __bkt_count);
2508 if (__next_bkt != __prev_bkt)
2509 __new_buckets[__next_bkt] = __prev_p;
2511 __check_bucket =
false;
2514 if (!__new_buckets[__bkt])
2516 __p->_M_nxt = _M_before_begin._M_nxt;
2517 _M_before_begin._M_nxt = __p;
2518 __new_buckets[__bkt] = &_M_before_begin;
2520 __new_buckets[__bbegin_bkt] = __p;
2521 __bbegin_bkt = __bkt;
2525 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2526 __new_buckets[__bkt]->_M_nxt = __p;
2534 if (__check_bucket && __prev_p->_M_nxt)
2536 std::size_t __next_bkt
2537 = __hash_code_base::_M_bucket_index(*__prev_p->_M_next(),
2539 if (__next_bkt != __prev_bkt)
2540 __new_buckets[__next_bkt] = __prev_p;
2543 _M_deallocate_buckets();
2544 _M_bucket_count = __bkt_count;
2545 _M_buckets = __new_buckets;
2548 #if __cplusplus > 201402L
2549 template<
typename,
typename,
typename>
class _Hash_merge_helper { };
2552 #if __cpp_deduction_guides >= 201606
2554 template<
typename _Hash>
2555 using _RequireNotAllocatorOrIntegral
2556 = __enable_if_t<!__or_<is_integral<_Hash>, __is_allocator<_Hash>>::value>;
2560 _GLIBCXX_END_NAMESPACE_VERSION
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
integral_constant< bool, false > false_type
The type used as a compile-time boolean with false value.
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
constexpr std::remove_reference< _Tp >::type && move(_Tp &&__t) noexcept
Convert a value to an rvalue.
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
_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.
void swap(shared_lock< _Mutex > &__x, shared_lock< _Mutex > &__y) noexcept
Swap specialization for shared_lock.
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.