31 #define _HASHTABLE_H 1 33 #pragma GCC system_header 37 namespace std _GLIBCXX_VISIBILITY(default)
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
41 template<
typename _Tp,
typename _Hash>
44 __is_fast_hash<_Hash>,
46 __detail::__is_noexcept_hash<_Tp, _Hash>>>;
166 template<
typename _Key,
typename _Value,
typename _Alloc,
167 typename _ExtractKey,
typename _Equal,
168 typename _H1,
typename _H2,
typename _Hash,
169 typename _RehashPolicy,
typename _Traits>
172 _H1, _H2, _Hash, _Traits>,
174 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
176 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
178 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
180 _H1, _H2, _Hash, _RehashPolicy, _Traits>,
182 typename __alloctr_rebind<_Alloc,
183 __detail::_Hash_node<_Value,
184 _Traits::__hash_cached::value> >::__type>
186 using __traits_type = _Traits;
187 using __hash_cached =
typename __traits_type::__hash_cached;
189 using __node_alloc_type =
190 typename __alloctr_rebind<_Alloc, __node_type>::__type;
194 using __value_alloc_traits =
196 using __node_alloc_traits =
202 typedef _Key key_type;
203 typedef _Value value_type;
204 typedef _Alloc allocator_type;
205 typedef _Equal key_equal;
209 typedef typename __value_alloc_traits::pointer pointer;
210 typedef typename __value_alloc_traits::const_pointer const_pointer;
211 typedef value_type& reference;
212 typedef const value_type& const_reference;
215 using __rehash_type = _RehashPolicy;
216 using __rehash_state =
typename __rehash_type::_State;
218 using __constant_iterators =
typename __traits_type::__constant_iterators;
219 using __unique_keys =
typename __traits_type::__unique_keys;
221 using __key_extract =
typename std::conditional<
222 __constant_iterators::value,
224 __detail::_Select1st>::type;
227 _Hashtable_base<_Key, _Value, _ExtractKey,
228 _Equal, _H1, _H2, _Hash, _Traits>;
231 using __hash_code =
typename __hashtable_base::__hash_code;
232 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
235 _Equal, _H1, _H2, _Hash,
236 _RehashPolicy, _Traits>;
241 _RehashPolicy, _Traits>;
244 _Equal, _H1, _H2, _Hash,
245 _RehashPolicy, _Traits>;
247 using __reuse_or_alloc_node_type =
248 __detail::_ReuseOrAllocNode<__node_alloc_type>;
251 template<
typename _Cond>
252 using __if_hash_cached = __or_<__not_<__hash_cached>, _Cond>;
254 template<
typename _Cond>
255 using __if_hash_not_cached = __or_<__hash_cached, _Cond>;
261 struct __hash_code_base_access : __hash_code_base
262 {
using __hash_code_base::_M_bucket_index; };
266 static_assert(noexcept(declval<const __hash_code_base_access&>()
269 "Cache the hash code or qualify your functors involved" 270 " in hash code and bucket index computation with noexcept");
277 static_assert(__if_hash_cached<is_default_constructible<_H2>>::value,
278 "Functor used to map hash code to bucket index" 279 " must be default constructible");
281 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
282 typename _ExtractKeya,
typename _Equala,
283 typename _H1a,
typename _H2a,
typename _Hasha,
284 typename _RehashPolicya,
typename _Traitsa,
288 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
289 typename _ExtractKeya,
typename _Equala,
290 typename _H1a,
typename _H2a,
typename _Hasha,
291 typename _RehashPolicya,
typename _Traitsa>
294 template<
typename _Keya,
typename _Valuea,
typename _Alloca,
295 typename _ExtractKeya,
typename _Equala,
296 typename _H1a,
typename _H2a,
typename _Hasha,
297 typename _RehashPolicya,
typename _Traitsa,
298 bool _Constant_iteratorsa,
bool _Unique_keysa>
302 using size_type =
typename __hashtable_base::size_type;
303 using difference_type =
typename __hashtable_base::difference_type;
309 using const_local_iterator =
typename __hashtable_base::
310 const_local_iterator;
313 __bucket_type* _M_buckets = &_M_single_bucket;
314 size_type _M_bucket_count = 1;
315 __node_base _M_before_begin;
316 size_type _M_element_count = 0;
317 _RehashPolicy _M_rehash_policy;
325 __bucket_type _M_single_bucket =
nullptr;
328 _M_uses_single_bucket(__bucket_type* __bkts)
const 329 {
return __builtin_expect(__bkts == &_M_single_bucket,
false); }
332 _M_uses_single_bucket()
const 333 {
return _M_uses_single_bucket(_M_buckets); }
336 _M_base_alloc() {
return *
this; }
339 _M_allocate_buckets(size_type __n)
341 if (__builtin_expect(__n == 1,
false))
343 _M_single_bucket =
nullptr;
344 return &_M_single_bucket;
347 return __hashtable_alloc::_M_allocate_buckets(__n);
351 _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
353 if (_M_uses_single_bucket(__bkts))
356 __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
360 _M_deallocate_buckets()
361 { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
366 _M_bucket_begin(size_type __bkt)
const;
370 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
372 template<
typename _NodeGenerator>
374 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
385 _Hashtable(
const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
386 const _Equal& __eq,
const _ExtractKey& __exk,
387 const allocator_type& __a)
396 const _H1&,
const _H2&,
const _Hash&,
397 const _Equal&,
const _ExtractKey&,
398 const allocator_type&);
400 template<
typename _InputIterator>
401 _Hashtable(_InputIterator __first, _InputIterator __last,
402 size_type __bucket_hint,
403 const _H1&,
const _H2&,
const _Hash&,
404 const _Equal&,
const _ExtractKey&,
405 const allocator_type&);
423 const _H1& __hf = _H1(),
424 const key_equal& __eql = key_equal(),
425 const allocator_type& __a = allocator_type())
426 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
427 __key_extract(), __a)
430 template<
typename _InputIterator>
431 _Hashtable(_InputIterator __f, _InputIterator __l,
433 const _H1& __hf = _H1(),
434 const key_equal& __eql = key_equal(),
435 const allocator_type& __a = allocator_type())
436 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
437 __key_extract(), __a)
442 const _H1& __hf = _H1(),
443 const key_equal& __eql = key_equal(),
444 const allocator_type& __a = allocator_type())
445 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
446 __key_extract(), __a)
454 noexcept(__node_alloc_traits::_S_nothrow_move())
456 constexpr
bool __move_storage =
457 __node_alloc_traits::_S_propagate_on_move_assign()
458 || __node_alloc_traits::_S_always_equal();
459 _M_move_assign(std::move(__ht),
467 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
468 _M_before_begin._M_nxt =
nullptr;
470 this->_M_insert_range(__l.begin(), __l.end(), __roan);
478 noexcept(__node_alloc_traits::_S_nothrow_swap());
483 {
return iterator(_M_begin()); }
486 begin()
const noexcept
487 {
return const_iterator(_M_begin()); }
491 {
return iterator(
nullptr); }
495 {
return const_iterator(
nullptr); }
499 {
return const_iterator(_M_begin()); }
502 cend()
const noexcept
503 {
return const_iterator(
nullptr); }
506 size()
const noexcept
507 {
return _M_element_count; }
510 empty()
const noexcept
511 {
return size() == 0; }
514 get_allocator()
const noexcept
515 {
return allocator_type(this->_M_node_allocator()); }
518 max_size()
const noexcept
519 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
524 {
return this->_M_eq(); }
530 bucket_count()
const noexcept
531 {
return _M_bucket_count; }
534 max_bucket_count()
const noexcept
535 {
return max_size(); }
538 bucket_size(size_type __n)
const 542 bucket(
const key_type& __k)
const 543 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
548 return local_iterator(*
this, _M_bucket_begin(__n),
549 __n, _M_bucket_count);
554 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
557 begin(size_type __n)
const 559 return const_local_iterator(*
this, _M_bucket_begin(__n),
560 __n, _M_bucket_count);
564 end(size_type __n)
const 565 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
569 cbegin(size_type __n)
const 571 return const_local_iterator(*
this, _M_bucket_begin(__n),
572 __n, _M_bucket_count);
576 cend(size_type __n)
const 577 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
580 load_factor()
const noexcept
582 return static_cast<float>(size()) / static_cast<float>(bucket_count());
591 __rehash_policy()
const 592 {
return _M_rehash_policy; }
595 __rehash_policy(
const _RehashPolicy&);
599 find(
const key_type& __k);
602 find(
const key_type& __k)
const;
605 count(
const key_type& __k)
const;
608 equal_range(
const key_type& __k);
611 equal_range(
const key_type& __k)
const;
617 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
620 _M_bucket_index(
const key_type& __k, __hash_code __c)
const 621 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
626 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
629 _M_find_node(size_type __bkt,
const key_type& __key,
630 __hash_code __c)
const 632 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
634 return static_cast<__node_type*
>(__before_n->_M_nxt);
644 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
645 size_type __next_bkt);
649 _M_get_previous_node(size_type __bkt, __node_base* __n);
655 _M_insert_unique_node(size_type __bkt, __hash_code __code,
664 template<
typename... _Args>
668 template<
typename... _Args>
671 {
return _M_emplace(
cend(), __uk, std::forward<_Args>(__args)...); }
674 template<
typename... _Args>
676 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
677 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
679 template<
typename... _Args>
683 template<
typename _Arg,
typename _NodeGenerator>
687 template<
typename _Arg,
typename _NodeGenerator>
689 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
692 return _M_insert(
cend(), std::forward<_Arg>(__arg), __node_gen,
697 template<
typename _Arg,
typename _NodeGenerator>
699 _M_insert(const_iterator, _Arg&& __arg,
703 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
707 template<
typename _Arg,
typename _NodeGenerator>
709 _M_insert(const_iterator, _Arg&&,
719 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
723 template<
typename... _Args>
725 emplace(_Args&&... __args)
726 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
728 template<
typename... _Args>
730 emplace_hint(const_iterator __hint, _Args&&... __args)
732 return _M_emplace(__hint, __unique_keys(),
733 std::forward<_Args>(__args)...);
740 erase(const_iterator);
745 {
return erase(const_iterator(__it)); }
748 erase(
const key_type& __k)
749 {
return _M_erase(__unique_keys(), __k); }
752 erase(const_iterator, const_iterator);
758 void rehash(size_type __n);
772 void _M_rehash(size_type __n,
const __rehash_state& __state);
777 template<
typename _Key,
typename _Value,
778 typename _Alloc,
typename _ExtractKey,
typename _Equal,
779 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
782 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
783 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
784 _M_bucket_begin(size_type __bkt)
const 787 __node_base* __n = _M_buckets[__bkt];
788 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
791 template<
typename _Key,
typename _Value,
792 typename _Alloc,
typename _ExtractKey,
typename _Equal,
793 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
795 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
796 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
797 _Hashtable(size_type __bucket_hint,
798 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
799 const _Equal& __eq,
const _ExtractKey& __exk,
800 const allocator_type& __a)
801 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
803 auto __bkt = _M_rehash_policy._M_next_bkt(__bucket_hint);
804 if (__bkt > _M_bucket_count)
806 _M_buckets = _M_allocate_buckets(__bkt);
807 _M_bucket_count = __bkt;
811 template<
typename _Key,
typename _Value,
812 typename _Alloc,
typename _ExtractKey,
typename _Equal,
813 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
815 template<
typename _InputIterator>
816 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
817 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
818 _Hashtable(_InputIterator __f, _InputIterator __l,
819 size_type __bucket_hint,
820 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
821 const _Equal& __eq,
const _ExtractKey& __exk,
822 const allocator_type& __a)
823 :
_Hashtable(__h1, __h2, __h, __eq, __exk, __a)
825 auto __nb_elems = __detail::__distance_fw(__f, __l);
827 _M_rehash_policy._M_next_bkt(
828 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
831 if (__bkt_count > _M_bucket_count)
833 _M_buckets = _M_allocate_buckets(__bkt_count);
834 _M_bucket_count = __bkt_count;
837 for (; __f != __l; ++__f)
841 template<
typename _Key,
typename _Value,
842 typename _Alloc,
typename _ExtractKey,
typename _Equal,
843 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
846 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
847 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
854 if (__node_alloc_traits::_S_propagate_on_copy_assign())
856 auto& __this_alloc = this->_M_node_allocator();
857 auto& __that_alloc = __ht._M_node_allocator();
858 if (!__node_alloc_traits::_S_always_equal()
859 && __this_alloc != __that_alloc)
862 this->_M_deallocate_nodes(_M_begin());
863 _M_before_begin._M_nxt =
nullptr;
864 _M_deallocate_buckets();
865 _M_buckets =
nullptr;
866 std::__alloc_on_copy(__this_alloc, __that_alloc);
867 __hashtable_base::operator=(__ht);
868 _M_bucket_count = __ht._M_bucket_count;
869 _M_element_count = __ht._M_element_count;
870 _M_rehash_policy = __ht._M_rehash_policy;
875 {
return this->_M_allocate_node(__n->_M_v()); });
882 __throw_exception_again;
886 std::__alloc_on_copy(__this_alloc, __that_alloc);
890 __bucket_type* __former_buckets =
nullptr;
891 std::size_t __former_bucket_count = _M_bucket_count;
892 const __rehash_state& __former_state = _M_rehash_policy._M_state();
894 if (_M_bucket_count != __ht._M_bucket_count)
896 __former_buckets = _M_buckets;
897 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
898 _M_bucket_count = __ht._M_bucket_count;
901 __builtin_memset(_M_buckets, 0,
902 _M_bucket_count *
sizeof(__bucket_type));
906 __hashtable_base::operator=(__ht);
907 _M_element_count = __ht._M_element_count;
908 _M_rehash_policy = __ht._M_rehash_policy;
909 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
910 _M_before_begin._M_nxt =
nullptr;
913 {
return __roan(__n->_M_v()); });
914 if (__former_buckets)
915 _M_deallocate_buckets(__former_buckets, __former_bucket_count);
919 if (__former_buckets)
922 _M_deallocate_buckets();
923 _M_rehash_policy._M_reset(__former_state);
924 _M_buckets = __former_buckets;
925 _M_bucket_count = __former_bucket_count;
927 __builtin_memset(_M_buckets, 0,
928 _M_bucket_count *
sizeof(__bucket_type));
929 __throw_exception_again;
934 template<
typename _Key,
typename _Value,
935 typename _Alloc,
typename _ExtractKey,
typename _Equal,
936 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
938 template<
typename _NodeGenerator>
940 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
941 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
942 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
944 __bucket_type* __buckets =
nullptr;
946 _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
950 if (!__ht._M_before_begin._M_nxt)
957 this->_M_copy_code(__this_n, __ht_n);
958 _M_before_begin._M_nxt = __this_n;
959 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
962 __node_base* __prev_n = __this_n;
963 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
965 __this_n = __node_gen(__ht_n);
966 __prev_n->_M_nxt = __this_n;
967 this->_M_copy_code(__this_n, __ht_n);
968 size_type __bkt = _M_bucket_index(__this_n);
969 if (!_M_buckets[__bkt])
970 _M_buckets[__bkt] = __prev_n;
978 _M_deallocate_buckets();
979 __throw_exception_again;
983 template<
typename _Key,
typename _Value,
984 typename _Alloc,
typename _ExtractKey,
typename _Equal,
985 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
988 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
989 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
992 _M_rehash_policy._M_reset();
994 _M_single_bucket =
nullptr;
995 _M_buckets = &_M_single_bucket;
996 _M_before_begin._M_nxt =
nullptr;
997 _M_element_count = 0;
1000 template<
typename _Key,
typename _Value,
1001 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1002 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1005 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1006 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1009 this->_M_deallocate_nodes(_M_begin());
1010 _M_deallocate_buckets();
1011 __hashtable_base::operator=(std::move(__ht));
1012 _M_rehash_policy = __ht._M_rehash_policy;
1013 if (!__ht._M_uses_single_bucket())
1014 _M_buckets = __ht._M_buckets;
1017 _M_buckets = &_M_single_bucket;
1018 _M_single_bucket = __ht._M_single_bucket;
1020 _M_bucket_count = __ht._M_bucket_count;
1021 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1022 _M_element_count = __ht._M_element_count;
1023 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
1028 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1032 template<
typename _Key,
typename _Value,
1033 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1034 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1037 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1038 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1041 if (__ht._M_node_allocator() == this->_M_node_allocator())
1046 __bucket_type* __former_buckets =
nullptr;
1047 size_type __former_bucket_count = _M_bucket_count;
1048 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1050 if (_M_bucket_count != __ht._M_bucket_count)
1052 __former_buckets = _M_buckets;
1053 _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
1054 _M_bucket_count = __ht._M_bucket_count;
1057 __builtin_memset(_M_buckets, 0,
1058 _M_bucket_count *
sizeof(__bucket_type));
1062 __hashtable_base::operator=(std::move(__ht));
1063 _M_element_count = __ht._M_element_count;
1064 _M_rehash_policy = __ht._M_rehash_policy;
1065 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1066 _M_before_begin._M_nxt =
nullptr;
1074 if (__former_buckets)
1076 _M_deallocate_buckets();
1077 _M_rehash_policy._M_reset(__former_state);
1078 _M_buckets = __former_buckets;
1079 _M_bucket_count = __former_bucket_count;
1081 __builtin_memset(_M_buckets, 0,
1082 _M_bucket_count *
sizeof(__bucket_type));
1083 __throw_exception_again;
1088 template<
typename _Key,
typename _Value,
1089 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1090 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1092 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1093 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1099 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1100 _M_buckets(
nullptr),
1101 _M_bucket_count(__ht._M_bucket_count),
1102 _M_element_count(__ht._M_element_count),
1103 _M_rehash_policy(__ht._M_rehash_policy)
1107 {
return this->_M_allocate_node(__n->_M_v()); });
1110 template<
typename _Key,
typename _Value,
1111 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1112 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1114 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1115 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1121 _M_buckets(__ht._M_buckets),
1122 _M_bucket_count(__ht._M_bucket_count),
1123 _M_before_begin(__ht._M_before_begin._M_nxt),
1124 _M_element_count(__ht._M_element_count),
1125 _M_rehash_policy(__ht._M_rehash_policy)
1128 if (__ht._M_uses_single_bucket())
1130 _M_buckets = &_M_single_bucket;
1131 _M_single_bucket = __ht._M_single_bucket;
1137 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1142 template<
typename _Key,
typename _Value,
1143 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1144 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1146 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1147 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1148 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1154 _M_bucket_count(__ht._M_bucket_count),
1155 _M_element_count(__ht._M_element_count),
1156 _M_rehash_policy(__ht._M_rehash_policy)
1160 {
return this->_M_allocate_node(__n->_M_v()); });
1163 template<
typename _Key,
typename _Value,
1164 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1165 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1167 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1168 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1169 _Hashtable(
_Hashtable&& __ht,
const allocator_type& __a)
1174 _M_buckets(
nullptr),
1175 _M_bucket_count(__ht._M_bucket_count),
1176 _M_element_count(__ht._M_element_count),
1177 _M_rehash_policy(__ht._M_rehash_policy)
1179 if (__ht._M_node_allocator() == this->_M_node_allocator())
1181 if (__ht._M_uses_single_bucket())
1183 _M_buckets = &_M_single_bucket;
1184 _M_single_bucket = __ht._M_single_bucket;
1187 _M_buckets = __ht._M_buckets;
1189 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1193 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1201 return this->_M_allocate_node(
1208 template<
typename _Key,
typename _Value,
1209 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1210 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1212 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1213 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1214 ~_Hashtable() noexcept
1217 _M_deallocate_buckets();
1220 template<
typename _Key,
typename _Value,
1221 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1222 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1225 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1226 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1228 noexcept(__node_alloc_traits::_S_nothrow_swap())
1235 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1236 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1239 if (this->_M_uses_single_bucket())
1241 if (!__x._M_uses_single_bucket())
1243 _M_buckets = __x._M_buckets;
1244 __x._M_buckets = &__x._M_single_bucket;
1247 else if (__x._M_uses_single_bucket())
1249 __x._M_buckets = _M_buckets;
1250 _M_buckets = &_M_single_bucket;
1253 std::swap(_M_buckets, __x._M_buckets);
1255 std::swap(_M_bucket_count, __x._M_bucket_count);
1256 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1257 std::swap(_M_element_count, __x._M_element_count);
1258 std::swap(_M_single_bucket, __x._M_single_bucket);
1263 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1266 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1267 = &__x._M_before_begin;
1270 template<
typename _Key,
typename _Value,
1271 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1272 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1275 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1276 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1277 __rehash_policy(
const _RehashPolicy& __pol)
1280 __pol._M_need_rehash(_M_bucket_count, _M_element_count, 0);
1281 if (__do_rehash.first)
1282 _M_rehash(__do_rehash.second, _M_rehash_policy._M_state());
1283 _M_rehash_policy = __pol;
1286 template<
typename _Key,
typename _Value,
1287 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1288 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1291 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1292 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1293 find(
const key_type& __k)
1296 __hash_code __code = this->_M_hash_code(__k);
1297 std::size_t __n = _M_bucket_index(__k, __code);
1298 __node_type* __p = _M_find_node(__n, __k, __code);
1299 return __p ? iterator(__p) :
end();
1302 template<
typename _Key,
typename _Value,
1303 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1304 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1307 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1308 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1309 find(
const key_type& __k)
const 1312 __hash_code __code = this->_M_hash_code(__k);
1313 std::size_t __n = _M_bucket_index(__k, __code);
1314 __node_type* __p = _M_find_node(__n, __k, __code);
1315 return __p ? const_iterator(__p) :
end();
1318 template<
typename _Key,
typename _Value,
1319 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1320 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1323 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1324 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1325 count(
const key_type& __k)
const 1328 __hash_code __code = this->_M_hash_code(__k);
1329 std::size_t __n = _M_bucket_index(__k, __code);
1334 std::size_t __result = 0;
1335 for (;; __p = __p->_M_next())
1337 if (this->_M_equals(__k, __code, __p))
1344 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1350 template<
typename _Key,
typename _Value,
1351 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1352 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1355 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1356 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1357 equal_range(
const key_type& __k)
1360 __hash_code __code = this->_M_hash_code(__k);
1361 std::size_t __n = _M_bucket_index(__k, __code);
1362 __node_type* __p = _M_find_node(__n, __k, __code);
1367 while (__p1 && _M_bucket_index(__p1) == __n
1368 && this->_M_equals(__k, __code, __p1))
1369 __p1 = __p1->_M_next();
1377 template<
typename _Key,
typename _Value,
1378 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1379 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1382 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1383 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1384 equal_range(
const key_type& __k)
const 1387 __hash_code __code = this->_M_hash_code(__k);
1388 std::size_t __n = _M_bucket_index(__k, __code);
1389 __node_type* __p = _M_find_node(__n, __k, __code);
1394 while (__p1 && _M_bucket_index(__p1) == __n
1395 && this->_M_equals(__k, __code, __p1))
1396 __p1 = __p1->_M_next();
1398 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1406 template<
typename _Key,
typename _Value,
1407 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1408 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1411 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1412 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1413 _M_find_before_node(size_type __n,
const key_type& __k,
1414 __hash_code __code)
const 1417 __node_base* __prev_p = _M_buckets[__n];
1421 for (
__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1422 __p = __p->_M_next())
1424 if (this->_M_equals(__k, __code, __p))
1427 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1434 template<
typename _Key,
typename _Value,
1435 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1436 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1439 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1440 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1441 _M_insert_bucket_begin(size_type __bkt,
__node_type* __node)
1443 if (_M_buckets[__bkt])
1447 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1448 _M_buckets[__bkt]->_M_nxt = __node;
1455 __node->_M_nxt = _M_before_begin._M_nxt;
1456 _M_before_begin._M_nxt = __node;
1460 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1461 _M_buckets[__bkt] = &_M_before_begin;
1465 template<
typename _Key,
typename _Value,
1466 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1467 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1470 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1471 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1472 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next,
1473 size_type __next_bkt)
1475 if (!__next || __next_bkt != __bkt)
1480 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1483 if (&_M_before_begin == _M_buckets[__bkt])
1484 _M_before_begin._M_nxt = __next;
1485 _M_buckets[__bkt] =
nullptr;
1489 template<
typename _Key,
typename _Value,
1490 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1491 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1494 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1495 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1496 _M_get_previous_node(size_type __bkt, __node_base* __n)
1499 __node_base* __prev_n = _M_buckets[__bkt];
1500 while (__prev_n->_M_nxt != __n)
1501 __prev_n = __prev_n->_M_nxt;
1505 template<
typename _Key,
typename _Value,
1506 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1507 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1509 template<
typename... _Args>
1511 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1512 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1517 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1518 const key_type& __k = this->_M_extract()(__node->_M_v());
1522 __code = this->_M_hash_code(__k);
1526 this->_M_deallocate_node(__node);
1527 __throw_exception_again;
1530 size_type __bkt = _M_bucket_index(__k, __code);
1531 if (
__node_type* __p = _M_find_node(__bkt, __k, __code))
1534 this->_M_deallocate_node(__node);
1539 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1543 template<
typename _Key,
typename _Value,
1544 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1545 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1547 template<
typename... _Args>
1549 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1550 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1556 this->_M_allocate_node(std::forward<_Args>(__args)...);
1561 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1565 this->_M_deallocate_node(__node);
1566 __throw_exception_again;
1569 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1572 template<
typename _Key,
typename _Value,
1573 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1574 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1577 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1578 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1579 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1583 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1585 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1589 if (__do_rehash.
first)
1591 _M_rehash(__do_rehash.
second, __saved_state);
1592 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1595 this->_M_store_code(__node, __code);
1598 _M_insert_bucket_begin(__bkt, __node);
1600 return iterator(__node);
1604 this->_M_deallocate_node(__node);
1605 __throw_exception_again;
1611 template<
typename _Key,
typename _Value,
1612 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1613 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1616 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1617 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1618 _M_insert_multi_node(
__node_type* __hint, __hash_code __code,
1622 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1624 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1628 if (__do_rehash.
first)
1629 _M_rehash(__do_rehash.
second, __saved_state);
1631 this->_M_store_code(__node, __code);
1632 const key_type& __k = this->_M_extract()(__node->_M_v());
1633 size_type __bkt = _M_bucket_index(__k, __code);
1638 = __builtin_expect(__hint !=
nullptr,
false)
1639 && this->_M_equals(__k, __code, __hint)
1641 : _M_find_before_node(__bkt, __k, __code);
1645 __node->_M_nxt = __prev->_M_nxt;
1646 __prev->_M_nxt = __node;
1647 if (__builtin_expect(__prev == __hint,
false))
1651 && !this->_M_equals(__k, __code, __node->_M_next()))
1653 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1654 if (__next_bkt != __bkt)
1655 _M_buckets[__next_bkt] = __node;
1663 _M_insert_bucket_begin(__bkt, __node);
1665 return iterator(__node);
1669 this->_M_deallocate_node(__node);
1670 __throw_exception_again;
1675 template<
typename _Key,
typename _Value,
1676 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1677 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1679 template<
typename _Arg,
typename _NodeGenerator>
1681 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1682 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1683 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
std::true_type)
1686 const key_type& __k = this->_M_extract()(__v);
1687 __hash_code __code = this->_M_hash_code(__k);
1688 size_type __bkt = _M_bucket_index(__k, __code);
1690 __node_type* __n = _M_find_node(__bkt, __k, __code);
1694 __n = __node_gen(std::forward<_Arg>(__v));
1695 return std::make_pair(_M_insert_unique_node(__bkt, __code, __n),
true);
1699 template<
typename _Key,
typename _Value,
1700 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1701 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1703 template<
typename _Arg,
typename _NodeGenerator>
1705 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1706 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1707 _M_insert(const_iterator __hint, _Arg&& __v,
1713 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1716 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1718 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1721 template<
typename _Key,
typename _Value,
1722 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1723 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1726 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1727 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1728 erase(const_iterator __it)
1732 std::size_t __bkt = _M_bucket_index(__n);
1737 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1738 return _M_erase(__bkt, __prev_n, __n);
1741 template<
typename _Key,
typename _Value,
1742 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1743 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1746 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1747 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1748 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n)
1751 if (__prev_n == _M_buckets[__bkt])
1752 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1753 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1754 else if (__n->_M_nxt)
1756 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1757 if (__next_bkt != __bkt)
1758 _M_buckets[__next_bkt] = __prev_n;
1761 __prev_n->_M_nxt = __n->_M_nxt;
1762 iterator __result(__n->_M_next());
1763 this->_M_deallocate_node(__n);
1769 template<
typename _Key,
typename _Value,
1770 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1771 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1774 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1775 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1779 __hash_code __code = this->_M_hash_code(__k);
1780 std::size_t __bkt = _M_bucket_index(__k, __code);
1783 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1789 _M_erase(__bkt, __prev_n, __n);
1793 template<
typename _Key,
typename _Value,
1794 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1795 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1798 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1799 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1803 __hash_code __code = this->_M_hash_code(__k);
1804 std::size_t __bkt = _M_bucket_index(__k, __code);
1807 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1819 std::size_t __n_last_bkt = __bkt;
1822 __n_last = __n_last->_M_next();
1825 __n_last_bkt = _M_bucket_index(__n_last);
1827 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1830 size_type __result = 0;
1834 this->_M_deallocate_node(__n);
1839 while (__n != __n_last);
1841 if (__prev_n == _M_buckets[__bkt])
1842 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1843 else if (__n_last && __n_last_bkt != __bkt)
1844 _M_buckets[__n_last_bkt] = __prev_n;
1845 __prev_n->_M_nxt = __n_last;
1849 template<
typename _Key,
typename _Value,
1850 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1851 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1854 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1855 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1856 erase(const_iterator __first, const_iterator __last)
1861 if (__n == __last_n)
1862 return iterator(__n);
1864 std::size_t __bkt = _M_bucket_index(__n);
1866 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1867 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1868 std::size_t __n_bkt = __bkt;
1874 __n = __n->_M_next();
1875 this->_M_deallocate_node(__tmp);
1879 __n_bkt = _M_bucket_index(__n);
1881 while (__n != __last_n && __n_bkt == __bkt);
1882 if (__is_bucket_begin)
1883 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1884 if (__n == __last_n)
1886 __is_bucket_begin =
true;
1890 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1891 _M_buckets[__n_bkt] = __prev_n;
1892 __prev_n->_M_nxt = __n;
1893 return iterator(__n);
1896 template<
typename _Key,
typename _Value,
1897 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1898 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1901 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1902 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1905 this->_M_deallocate_nodes(_M_begin());
1906 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
1907 _M_element_count = 0;
1908 _M_before_begin._M_nxt =
nullptr;
1911 template<
typename _Key,
typename _Value,
1912 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1913 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1916 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1917 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1918 rehash(size_type __n)
1920 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1921 std::size_t __buckets
1922 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
1924 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
1926 if (__buckets != _M_bucket_count)
1927 _M_rehash(__buckets, __saved_state);
1930 _M_rehash_policy._M_reset(__saved_state);
1933 template<
typename _Key,
typename _Value,
1934 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1935 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1938 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1939 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1940 _M_rehash(size_type __n,
const __rehash_state& __state)
1944 _M_rehash_aux(__n, __unique_keys());
1950 _M_rehash_policy._M_reset(__state);
1951 __throw_exception_again;
1956 template<
typename _Key,
typename _Value,
1957 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1958 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1961 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1962 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1965 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
1967 _M_before_begin._M_nxt =
nullptr;
1968 std::size_t __bbegin_bkt = 0;
1972 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
1973 if (!__new_buckets[__bkt])
1975 __p->_M_nxt = _M_before_begin._M_nxt;
1976 _M_before_begin._M_nxt = __p;
1977 __new_buckets[__bkt] = &_M_before_begin;
1979 __new_buckets[__bbegin_bkt] = __p;
1980 __bbegin_bkt = __bkt;
1984 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1985 __new_buckets[__bkt]->_M_nxt = __p;
1990 _M_deallocate_buckets();
1991 _M_bucket_count = __n;
1992 _M_buckets = __new_buckets;
1997 template<
typename _Key,
typename _Value,
1998 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1999 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
2002 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
2003 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
2006 __bucket_type* __new_buckets = _M_allocate_buckets(__n);
2009 _M_before_begin._M_nxt =
nullptr;
2010 std::size_t __bbegin_bkt = 0;
2011 std::size_t __prev_bkt = 0;
2013 bool __check_bucket =
false;
2018 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2020 if (__prev_p && __prev_bkt == __bkt)
2025 __p->_M_nxt = __prev_p->_M_nxt;
2026 __prev_p->_M_nxt = __p;
2033 __check_bucket =
true;
2041 if (__prev_p->_M_nxt)
2043 std::size_t __next_bkt
2044 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2046 if (__next_bkt != __prev_bkt)
2047 __new_buckets[__next_bkt] = __prev_p;
2049 __check_bucket =
false;
2052 if (!__new_buckets[__bkt])
2054 __p->_M_nxt = _M_before_begin._M_nxt;
2055 _M_before_begin._M_nxt = __p;
2056 __new_buckets[__bkt] = &_M_before_begin;
2058 __new_buckets[__bbegin_bkt] = __p;
2059 __bbegin_bkt = __bkt;
2063 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2064 __new_buckets[__bkt]->_M_nxt = __p;
2072 if (__check_bucket && __prev_p->_M_nxt)
2074 std::size_t __next_bkt
2075 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2076 if (__next_bkt != __prev_bkt)
2077 __new_buckets[__next_bkt] = __prev_p;
2080 _M_deallocate_buckets();
2081 _M_bucket_count = __n;
2082 _M_buckets = __new_buckets;
2085 _GLIBCXX_END_NAMESPACE_VERSION
2088 #endif // _HASHTABLE_H
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.
Uniform interface to all allocator types.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
Node iterators, used to iterate through all the hashtable.
_T2 second
first is a copy of the first object
Uniform interface to C++98 and C++0x allocators.
ISO C++ entities toplevel namespace is std.
constexpr conditional< __move_if_noexcept_cond< _Tp >::value, const _Tp &, _Tp && >::type move_if_noexcept(_Tp &__x) noexcept
Conditionally convert a value to an rvalue.
Node const_iterators, used to iterate through all the hashtable.
Struct holding two objects of arbitrary type.
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
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 pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
_T1 first
second_type is the second bound type
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.