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;
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;
313 __bucket_type* _M_buckets;
314 size_type _M_bucket_count;
315 __node_base _M_before_begin;
316 size_type _M_element_count;
317 _RehashPolicy _M_rehash_policy;
320 _M_base_alloc() {
return *
this; }
322 using __hashtable_alloc::_M_deallocate_buckets;
325 _M_deallocate_buckets()
326 { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
331 _M_bucket_begin(size_type __bkt)
const;
335 {
return static_cast<__node_type*
>(_M_before_begin._M_nxt); }
337 template<
typename _NodeGenerator>
339 _M_assign(
const _Hashtable&,
const _NodeGenerator&);
353 const _H1&,
const _H2&,
const _Hash&,
354 const _Equal&,
const _ExtractKey&,
355 const allocator_type&);
357 template<
typename _InputIterator>
358 _Hashtable(_InputIterator __first, _InputIterator __last,
359 size_type __bucket_hint,
360 const _H1&,
const _H2&,
const _Hash&,
361 const _Equal&,
const _ExtractKey&,
362 const allocator_type&);
375 :
_Hashtable(10, _H1(), _H2(), _Hash(), key_equal(),
376 __key_extract(), __a)
381 const _H1& __hf = _H1(),
382 const key_equal& __eql = key_equal(),
383 const allocator_type& __a = allocator_type())
384 :
_Hashtable(__n, __hf, _H2(), _Hash(), __eql,
385 __key_extract(), __a)
388 template<
typename _InputIterator>
389 _Hashtable(_InputIterator __f, _InputIterator __l,
391 const _H1& __hf = _H1(),
392 const key_equal& __eql = key_equal(),
393 const allocator_type& __a = allocator_type())
394 :
_Hashtable(__f, __l, __n, __hf, _H2(), _Hash(), __eql,
395 __key_extract(), __a)
400 const _H1& __hf = _H1(),
401 const key_equal& __eql = key_equal(),
402 const allocator_type& __a = allocator_type())
403 :
_Hashtable(__l.begin(), __l.end(), __n, __hf, _H2(), _Hash(), __eql,
404 __key_extract(), __a)
412 noexcept(__node_alloc_traits::_S_nothrow_move())
414 constexpr
bool __move_storage =
415 __node_alloc_traits::_S_propagate_on_move_assign()
416 || __node_alloc_traits::_S_always_equal();
417 _M_move_assign(std::move(__ht),
425 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
426 _M_before_begin._M_nxt =
nullptr;
428 this->_M_insert_range(__l.begin(), __l.end(), __roan);
436 noexcept(__node_alloc_traits::_S_nothrow_swap());
441 {
return iterator(_M_begin()); }
444 begin()
const noexcept
445 {
return const_iterator(_M_begin()); }
449 {
return iterator(
nullptr); }
453 {
return const_iterator(
nullptr); }
456 cbegin()
const noexcept
457 {
return const_iterator(_M_begin()); }
460 cend()
const noexcept
461 {
return const_iterator(
nullptr); }
464 size()
const noexcept
465 {
return _M_element_count; }
468 empty()
const noexcept
469 {
return size() == 0; }
472 get_allocator()
const noexcept
473 {
return allocator_type(this->_M_node_allocator()); }
476 max_size()
const noexcept
477 {
return __node_alloc_traits::max_size(this->_M_node_allocator()); }
482 {
return this->_M_eq(); }
488 bucket_count()
const noexcept
489 {
return _M_bucket_count; }
492 max_bucket_count()
const noexcept
493 {
return max_size(); }
496 bucket_size(size_type __n)
const
500 bucket(
const key_type& __k)
const
501 {
return _M_bucket_index(__k, this->_M_hash_code(__k)); }
506 return local_iterator(*
this, _M_bucket_begin(__n),
507 __n, _M_bucket_count);
512 {
return local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
515 begin(size_type __n)
const
517 return const_local_iterator(*
this, _M_bucket_begin(__n),
518 __n, _M_bucket_count);
522 end(size_type __n)
const
523 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
527 cbegin(size_type __n)
const
529 return const_local_iterator(*
this, _M_bucket_begin(__n),
530 __n, _M_bucket_count);
534 cend(size_type __n)
const
535 {
return const_local_iterator(*
this,
nullptr, __n, _M_bucket_count); }
538 load_factor()
const noexcept
540 return static_cast<float>(
size()) / static_cast<float>(bucket_count());
549 __rehash_policy()
const
550 {
return _M_rehash_policy; }
553 __rehash_policy(
const _RehashPolicy&);
557 find(
const key_type& __k);
560 find(
const key_type& __k)
const;
563 count(
const key_type& __k)
const;
566 equal_range(
const key_type& __k);
569 equal_range(
const key_type& __k)
const;
575 {
return __hash_code_base::_M_bucket_index(__n, _M_bucket_count); }
578 _M_bucket_index(
const key_type& __k, __hash_code __c)
const
579 {
return __hash_code_base::_M_bucket_index(__k, __c, _M_bucket_count); }
584 _M_find_before_node(size_type,
const key_type&, __hash_code)
const;
587 _M_find_node(size_type __bkt,
const key_type& __key,
588 __hash_code __c)
const
590 __node_base* __before_n = _M_find_before_node(__bkt, __key, __c);
592 return static_cast<__node_type*
>(__before_n->_M_nxt);
602 _M_remove_bucket_begin(size_type __bkt,
__node_type* __next_n,
603 size_type __next_bkt);
607 _M_get_previous_node(size_type __bkt, __node_base* __n);
613 _M_insert_unique_node(size_type __bkt, __hash_code __code,
622 template<
typename... _Args>
626 template<
typename... _Args>
629 {
return _M_emplace(cend(), __uk, std::forward<_Args>(__args)...); }
632 template<
typename... _Args>
634 _M_emplace(const_iterator,
std::true_type __uk, _Args&&... __args)
635 {
return _M_emplace(__uk, std::forward<_Args>(__args)...).first; }
637 template<
typename... _Args>
641 template<
typename _Arg,
typename _NodeGenerator>
645 template<
typename _Arg,
typename _NodeGenerator>
647 _M_insert(_Arg&& __arg,
const _NodeGenerator& __node_gen,
650 return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
655 template<
typename _Arg,
typename _NodeGenerator>
657 _M_insert(const_iterator, _Arg&& __arg,
const _NodeGenerator& __node_gen,
661 _M_insert(std::forward<_Arg>(__arg), __node_gen, __uk).
first;
665 template<
typename _Arg,
typename _NodeGenerator>
667 _M_insert(const_iterator, _Arg&&,
const _NodeGenerator&,
std::false_type);
676 _M_erase(size_type __bkt, __node_base* __prev_n,
__node_type* __n);
680 template<
typename... _Args>
682 emplace(_Args&&... __args)
683 {
return _M_emplace(__unique_keys(), std::forward<_Args>(__args)...); }
685 template<
typename... _Args>
687 emplace_hint(const_iterator __hint, _Args&&... __args)
689 return _M_emplace(__hint, __unique_keys(),
690 std::forward<_Args>(__args)...);
697 erase(const_iterator);
702 {
return erase(const_iterator(__it)); }
705 erase(
const key_type& __k)
707 if (__builtin_expect(_M_bucket_count == 0,
false))
709 return _M_erase(__unique_keys(), __k);
713 erase(const_iterator, const_iterator);
719 void rehash(size_type __n);
733 void _M_rehash(size_type __n,
const __rehash_state& __state);
738 template<
typename _Key,
typename _Value,
739 typename _Alloc,
typename _ExtractKey,
typename _Equal,
740 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
742 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
743 _Equal, _H1, _H2, _Hash, _RehashPolicy,
744 _Traits>::__node_type*
745 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
746 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
747 _M_bucket_begin(size_type __bkt)
const
749 __node_base* __n = _M_buckets[__bkt];
750 return __n ?
static_cast<__node_type*
>(__n->_M_nxt) :
nullptr;
753 template<
typename _Key,
typename _Value,
754 typename _Alloc,
typename _ExtractKey,
typename _Equal,
755 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
757 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
758 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
759 _Hashtable(size_type __bucket_hint,
760 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
761 const _Equal& __eq,
const _ExtractKey& __exk,
762 const allocator_type& __a)
763 : __hashtable_base(__exk, __h1, __h2, __h, __eq),
766 __hashtable_alloc(__node_alloc_type(__a)),
770 _M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
771 _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
774 template<
typename _Key,
typename _Value,
775 typename _Alloc,
typename _ExtractKey,
typename _Equal,
776 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
778 template<
typename _InputIterator>
779 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
780 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
781 _Hashtable(_InputIterator __f, _InputIterator __l,
782 size_type __bucket_hint,
783 const _H1& __h1,
const _H2& __h2,
const _Hash& __h,
784 const _Equal& __eq,
const _ExtractKey& __exk,
785 const allocator_type& __a)
786 : __hashtable_base(__exk, __h1, __h2, __h, __eq),
789 __hashtable_alloc(__node_alloc_type(__a)),
793 auto __nb_elems = __detail::__distance_fw(__f, __l);
795 _M_rehash_policy._M_next_bkt(
796 std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
799 _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
802 for (; __f != __l; ++__f)
808 _M_deallocate_buckets();
809 __throw_exception_again;
813 template<
typename _Key,
typename _Value,
814 typename _Alloc,
typename _ExtractKey,
typename _Equal,
815 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
817 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
818 _H1, _H2, _Hash, _RehashPolicy, _Traits>&
819 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
820 _H1, _H2, _Hash, _RehashPolicy, _Traits>::operator=(
821 const _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
822 _H1, _H2, _Hash, _RehashPolicy, _Traits>& __ht)
827 if (__node_alloc_traits::_S_propagate_on_copy_assign())
829 auto& __this_alloc = this->_M_node_allocator();
830 auto& __that_alloc = __ht._M_node_allocator();
831 if (!__node_alloc_traits::_S_always_equal()
832 && __this_alloc != __that_alloc)
835 this->_M_deallocate_nodes(_M_begin());
836 if (__builtin_expect(_M_bucket_count != 0,
true))
837 _M_deallocate_buckets();
839 std::__alloc_on_copy(__this_alloc, __that_alloc);
840 __hashtable_base::operator=(__ht);
841 _M_bucket_count = __ht._M_bucket_count;
842 _M_element_count = __ht._M_element_count;
843 _M_rehash_policy = __ht._M_rehash_policy;
847 [
this](
const __node_type* __n)
848 {
return this->_M_allocate_node(__n->_M_v()); });
855 __throw_exception_again;
859 std::__alloc_on_copy(__this_alloc, __that_alloc);
863 __bucket_type* __former_buckets =
nullptr;
864 std::size_t __former_bucket_count = _M_bucket_count;
865 const __rehash_state& __former_state = _M_rehash_policy._M_state();
867 if (_M_bucket_count != __ht._M_bucket_count)
869 __former_buckets = _M_buckets;
870 _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
871 _M_bucket_count = __ht._M_bucket_count;
874 __builtin_memset(_M_buckets, 0,
875 _M_bucket_count *
sizeof(__bucket_type));
879 __hashtable_base::operator=(__ht);
880 _M_element_count = __ht._M_element_count;
881 _M_rehash_policy = __ht._M_rehash_policy;
882 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
883 _M_before_begin._M_nxt =
nullptr;
885 [&__roan](
const __node_type* __n)
886 {
return __roan(__n->_M_v()); });
887 if (__former_buckets)
888 this->_M_deallocate_buckets(__former_buckets,
889 __former_bucket_count);
893 if (__former_buckets)
896 _M_deallocate_buckets();
897 _M_rehash_policy._M_reset(__former_state);
898 _M_buckets = __former_buckets;
899 _M_bucket_count = __former_bucket_count;
901 __builtin_memset(_M_buckets, 0,
902 _M_bucket_count *
sizeof(__bucket_type));
903 __throw_exception_again;
908 template<
typename _Key,
typename _Value,
909 typename _Alloc,
typename _ExtractKey,
typename _Equal,
910 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
912 template<
typename _NodeGenerator>
914 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
915 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
916 _M_assign(
const _Hashtable& __ht,
const _NodeGenerator& __node_gen)
918 __bucket_type* __buckets =
nullptr;
920 _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
924 if (!__ht._M_before_begin._M_nxt)
929 __node_type* __ht_n = __ht._M_begin();
930 __node_type* __this_n = __node_gen(__ht_n);
931 this->_M_copy_code(__this_n, __ht_n);
932 _M_before_begin._M_nxt = __this_n;
933 _M_buckets[_M_bucket_index(__this_n)] = &_M_before_begin;
936 __node_base* __prev_n = __this_n;
937 for (__ht_n = __ht_n->_M_next(); __ht_n; __ht_n = __ht_n->_M_next())
939 __this_n = __node_gen(__ht_n);
940 __prev_n->_M_nxt = __this_n;
941 this->_M_copy_code(__this_n, __ht_n);
942 size_type __bkt = _M_bucket_index(__this_n);
943 if (!_M_buckets[__bkt])
944 _M_buckets[__bkt] = __prev_n;
952 _M_deallocate_buckets();
953 __throw_exception_again;
957 template<
typename _Key,
typename _Value,
958 typename _Alloc,
typename _ExtractKey,
typename _Equal,
959 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
962 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
963 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
966 _M_rehash_policy._M_reset();
968 _M_buckets =
nullptr;
969 _M_before_begin._M_nxt =
nullptr;
970 _M_element_count = 0;
973 template<
typename _Key,
typename _Value,
974 typename _Alloc,
typename _ExtractKey,
typename _Equal,
975 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
978 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
979 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
982 this->_M_deallocate_nodes(_M_begin());
983 if (__builtin_expect(_M_bucket_count != 0,
true))
984 _M_deallocate_buckets();
986 __hashtable_base::operator=(std::move(__ht));
987 _M_rehash_policy = __ht._M_rehash_policy;
988 _M_buckets = __ht._M_buckets;
989 _M_bucket_count = __ht._M_bucket_count;
990 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
991 _M_element_count = __ht._M_element_count;
992 std::__alloc_on_move(this->_M_node_allocator(), __ht._M_node_allocator());
997 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1001 template<
typename _Key,
typename _Value,
1002 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1003 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1006 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1007 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1010 if (__ht._M_node_allocator() == this->_M_node_allocator())
1015 __bucket_type* __former_buckets =
nullptr;
1016 size_type __former_bucket_count = _M_bucket_count;
1017 const __rehash_state& __former_state = _M_rehash_policy._M_state();
1019 if (_M_bucket_count != __ht._M_bucket_count)
1021 __former_buckets = _M_buckets;
1022 _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
1023 _M_bucket_count = __ht._M_bucket_count;
1026 __builtin_memset(_M_buckets, 0,
1027 _M_bucket_count *
sizeof(__bucket_type));
1031 __hashtable_base::operator=(std::move(__ht));
1032 _M_element_count = __ht._M_element_count;
1033 _M_rehash_policy = __ht._M_rehash_policy;
1034 __reuse_or_alloc_node_type __roan(_M_begin(), *
this);
1035 _M_before_begin._M_nxt =
nullptr;
1037 [&__roan](__node_type* __n)
1043 if (__former_buckets)
1045 _M_deallocate_buckets();
1046 _M_rehash_policy._M_reset(__former_state);
1047 _M_buckets = __former_buckets;
1048 _M_bucket_count = __former_bucket_count;
1050 __builtin_memset(_M_buckets, 0,
1051 _M_bucket_count *
sizeof(__bucket_type));
1052 __throw_exception_again;
1057 template<
typename _Key,
typename _Value,
1058 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1059 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1061 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1062 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1063 _Hashtable(
const _Hashtable& __ht)
1064 : __hashtable_base(__ht),
1066 __rehash_base(__ht),
1068 __node_alloc_traits::_S_select_on_copy(__ht._M_node_allocator())),
1070 _M_bucket_count(__ht._M_bucket_count),
1071 _M_element_count(__ht._M_element_count),
1072 _M_rehash_policy(__ht._M_rehash_policy)
1075 [
this](
const __node_type* __n)
1076 {
return this->_M_allocate_node(__n->_M_v()); });
1079 template<
typename _Key,
typename _Value,
1080 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1081 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1083 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1084 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1085 _Hashtable(_Hashtable&& __ht) noexcept
1086 : __hashtable_base(__ht),
1088 __rehash_base(__ht),
1089 __hashtable_alloc(std::move(__ht._M_base_alloc())),
1090 _M_buckets(__ht._M_buckets),
1091 _M_bucket_count(__ht._M_bucket_count),
1092 _M_before_begin(__ht._M_before_begin._M_nxt),
1093 _M_element_count(__ht._M_element_count),
1094 _M_rehash_policy(__ht._M_rehash_policy)
1099 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1103 template<
typename _Key,
typename _Value,
1104 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1105 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1107 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1108 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1109 _Hashtable(
const _Hashtable& __ht,
const allocator_type& __a)
1110 : __hashtable_base(__ht),
1112 __rehash_base(__ht),
1113 __hashtable_alloc(__node_alloc_type(__a)),
1115 _M_bucket_count(__ht._M_bucket_count),
1116 _M_element_count(__ht._M_element_count),
1117 _M_rehash_policy(__ht._M_rehash_policy)
1120 [
this](
const __node_type* __n)
1121 {
return this->_M_allocate_node(__n->_M_v()); });
1124 template<
typename _Key,
typename _Value,
1125 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1126 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1128 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1129 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1130 _Hashtable(_Hashtable&& __ht,
const allocator_type& __a)
1131 : __hashtable_base(__ht),
1133 __rehash_base(__ht),
1134 __hashtable_alloc(__node_alloc_type(__a)),
1136 _M_bucket_count(__ht._M_bucket_count),
1137 _M_element_count(__ht._M_element_count),
1138 _M_rehash_policy(__ht._M_rehash_policy)
1140 if (__ht._M_node_allocator() == this->_M_node_allocator())
1142 _M_buckets = __ht._M_buckets;
1143 _M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
1147 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1153 [
this](__node_type* __n)
1155 return this->_M_allocate_node(
1162 template<
typename _Key,
typename _Value,
1163 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1164 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1166 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1167 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1168 ~_Hashtable() noexcept
1172 _M_deallocate_buckets();
1175 template<
typename _Key,
typename _Value,
1176 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1177 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1180 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1181 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1182 swap(_Hashtable& __x)
1183 noexcept(__node_alloc_traits::_S_nothrow_swap())
1190 std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
1191 std::swap(_M_rehash_policy, __x._M_rehash_policy);
1192 std::swap(_M_buckets, __x._M_buckets);
1193 std::swap(_M_bucket_count, __x._M_bucket_count);
1194 std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
1195 std::swap(_M_element_count, __x._M_element_count);
1200 _M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
1202 __x._M_buckets[__x._M_bucket_index(__x._M_begin())]
1203 = &__x._M_before_begin;
1206 template<
typename _Key,
typename _Value,
1207 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1208 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1211 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1212 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1213 __rehash_policy(
const _RehashPolicy& __pol)
1215 size_type __n_bkt = __pol._M_bkt_for_elements(_M_element_count);
1216 __n_bkt = __pol._M_next_bkt(__n_bkt);
1217 if (__n_bkt != _M_bucket_count)
1218 _M_rehash(__n_bkt, _M_rehash_policy._M_state());
1219 _M_rehash_policy = __pol;
1222 template<
typename _Key,
typename _Value,
1223 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1224 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1226 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1227 _H1, _H2, _Hash, _RehashPolicy,
1229 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1230 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1231 find(
const key_type& __k)
1233 if (__builtin_expect(_M_bucket_count == 0,
false))
1236 __hash_code __code = this->_M_hash_code(__k);
1237 std::size_t __n = _M_bucket_index(__k, __code);
1238 __node_type* __p = _M_find_node(__n, __k, __code);
1239 return __p ? iterator(__p) :
end();
1242 template<
typename _Key,
typename _Value,
1243 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1244 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1246 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1247 _H1, _H2, _Hash, _RehashPolicy,
1248 _Traits>::const_iterator
1249 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1250 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1251 find(
const key_type& __k)
const
1253 if (__builtin_expect(_M_bucket_count == 0,
false))
1256 __hash_code __code = this->_M_hash_code(__k);
1257 std::size_t __n = _M_bucket_index(__k, __code);
1258 __node_type* __p = _M_find_node(__n, __k, __code);
1259 return __p ? const_iterator(__p) :
end();
1262 template<
typename _Key,
typename _Value,
1263 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1264 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1266 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1267 _H1, _H2, _Hash, _RehashPolicy,
1269 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1270 _H1, _H2, _Hash, _RehashPolicy, _Traits>
::
1271 count(
const key_type& __k)
const
1273 if (__builtin_expect(_M_bucket_count == 0,
false))
1276 __hash_code __code = this->_M_hash_code(__k);
1277 std::size_t __n = _M_bucket_index(__k, __code);
1278 __node_type* __p = _M_bucket_begin(__n);
1282 std::size_t __result = 0;
1283 for (;; __p = __p->_M_next())
1285 if (this->_M_equals(__k, __code, __p))
1292 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1298 template<
typename _Key,
typename _Value,
1299 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1300 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1302 std::pair<
typename _Hashtable<_Key, _Value, _Alloc,
1303 _ExtractKey, _Equal, _H1,
1304 _H2, _Hash, _RehashPolicy,
1306 typename _Hashtable<_Key, _Value, _Alloc,
1307 _ExtractKey, _Equal, _H1,
1308 _H2, _Hash, _RehashPolicy,
1310 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1311 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1312 equal_range(
const key_type& __k)
1314 if (__builtin_expect(_M_bucket_count == 0,
false))
1317 __hash_code __code = this->_M_hash_code(__k);
1318 std::size_t __n = _M_bucket_index(__k, __code);
1319 __node_type* __p = _M_find_node(__n, __k, __code);
1323 __node_type* __p1 = __p->_M_next();
1324 while (__p1 && _M_bucket_index(__p1) == __n
1325 && this->_M_equals(__k, __code, __p1))
1326 __p1 = __p1->_M_next();
1334 template<
typename _Key,
typename _Value,
1335 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1336 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1338 std::pair<
typename _Hashtable<_Key, _Value, _Alloc,
1339 _ExtractKey, _Equal, _H1,
1340 _H2, _Hash, _RehashPolicy,
1341 _Traits>::const_iterator,
1342 typename _Hashtable<_Key, _Value, _Alloc,
1343 _ExtractKey, _Equal, _H1,
1344 _H2, _Hash, _RehashPolicy,
1345 _Traits>::const_iterator>
1346 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1347 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1348 equal_range(
const key_type& __k)
const
1350 if (__builtin_expect(_M_bucket_count == 0,
false))
1353 __hash_code __code = this->_M_hash_code(__k);
1354 std::size_t __n = _M_bucket_index(__k, __code);
1355 __node_type* __p = _M_find_node(__n, __k, __code);
1359 __node_type* __p1 = __p->_M_next();
1360 while (__p1 && _M_bucket_index(__p1) == __n
1361 && this->_M_equals(__k, __code, __p1))
1362 __p1 = __p1->_M_next();
1364 return std::make_pair(const_iterator(__p), const_iterator(__p1));
1372 template<
typename _Key,
typename _Value,
1373 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1374 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1376 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1377 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1378 _Traits>::__node_base*
1379 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1380 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1381 _M_find_before_node(size_type __n,
const key_type& __k,
1382 __hash_code __code)
const
1384 __node_base* __prev_p = _M_buckets[__n];
1388 for (__node_type* __p = static_cast<__node_type*>(__prev_p->_M_nxt);;
1389 __p = __p->_M_next())
1391 if (this->_M_equals(__k, __code, __p))
1394 if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
1401 template<
typename _Key,
typename _Value,
1402 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1403 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1406 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1407 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1408 _M_insert_bucket_begin(size_type __bkt, __node_type* __node)
1410 if (_M_buckets[__bkt])
1414 __node->_M_nxt = _M_buckets[__bkt]->_M_nxt;
1415 _M_buckets[__bkt]->_M_nxt = __node;
1422 __node->_M_nxt = _M_before_begin._M_nxt;
1423 _M_before_begin._M_nxt = __node;
1427 _M_buckets[_M_bucket_index(__node->_M_next())] = __node;
1428 _M_buckets[__bkt] = &_M_before_begin;
1432 template<
typename _Key,
typename _Value,
1433 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1434 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1437 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1438 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1439 _M_remove_bucket_begin(size_type __bkt, __node_type* __next,
1440 size_type __next_bkt)
1442 if (!__next || __next_bkt != __bkt)
1447 _M_buckets[__next_bkt] = _M_buckets[__bkt];
1450 if (&_M_before_begin == _M_buckets[__bkt])
1451 _M_before_begin._M_nxt = __next;
1452 _M_buckets[__bkt] =
nullptr;
1456 template<
typename _Key,
typename _Value,
1457 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1458 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1460 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey,
1461 _Equal, _H1, _H2, _Hash, _RehashPolicy,
1462 _Traits>::__node_base*
1463 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1464 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1465 _M_get_previous_node(size_type __bkt, __node_base* __n)
1467 __node_base* __prev_n = _M_buckets[__bkt];
1468 while (__prev_n->_M_nxt != __n)
1469 __prev_n = __prev_n->_M_nxt;
1473 template<
typename _Key,
typename _Value,
1474 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1475 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1477 template<
typename... _Args>
1478 std::pair<
typename _Hashtable<_Key, _Value, _Alloc,
1479 _ExtractKey, _Equal, _H1,
1480 _H2, _Hash, _RehashPolicy,
1481 _Traits>::iterator,
bool>
1482 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1483 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1487 __node_type* __node = this->_M_allocate_node(std::forward<_Args>(__args)...);
1488 const key_type& __k = this->_M_extract()(__node->_M_v());
1492 __code = this->_M_hash_code(__k);
1496 this->_M_deallocate_node(__node);
1497 __throw_exception_again;
1500 size_type __bkt = _M_bucket_index(__k, __code);
1501 if (__node_type* __p = _M_find_node(__bkt, __k, __code))
1504 this->_M_deallocate_node(__node);
1509 return std::make_pair(_M_insert_unique_node(__bkt, __code, __node),
1513 template<
typename _Key,
typename _Value,
1514 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1515 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1517 template<
typename... _Args>
1518 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1519 _H1, _H2, _Hash, _RehashPolicy,
1521 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1522 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1526 __node_type* __node =
1527 this->_M_allocate_node(std::forward<_Args>(__args)...);
1532 __code = this->_M_hash_code(this->_M_extract()(__node->_M_v()));
1536 this->_M_deallocate_node(__node);
1537 __throw_exception_again;
1540 return _M_insert_multi_node(__hint._M_cur, __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 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1548 _H1, _H2, _Hash, _RehashPolicy,
1550 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1551 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1552 _M_insert_unique_node(size_type __bkt, __hash_code __code,
1553 __node_type* __node)
1555 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1557 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1561 if (__do_rehash.
first)
1563 _M_rehash(__do_rehash.
second, __saved_state);
1564 __bkt = _M_bucket_index(this->_M_extract()(__node->_M_v()), __code);
1567 this->_M_store_code(__node, __code);
1570 _M_insert_bucket_begin(__bkt, __node);
1572 return iterator(__node);
1576 this->_M_deallocate_node(__node);
1577 __throw_exception_again;
1583 template<
typename _Key,
typename _Value,
1584 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1585 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1587 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1588 _H1, _H2, _Hash, _RehashPolicy,
1590 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1591 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1592 _M_insert_multi_node(__node_type* __hint, __hash_code __code,
1593 __node_type* __node)
1595 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1597 = _M_rehash_policy._M_need_rehash(_M_bucket_count, _M_element_count, 1);
1601 if (__do_rehash.
first)
1602 _M_rehash(__do_rehash.
second, __saved_state);
1604 this->_M_store_code(__node, __code);
1605 const key_type& __k = this->_M_extract()(__node->_M_v());
1606 size_type __bkt = _M_bucket_index(__k, __code);
1611 = __builtin_expect(__hint !=
nullptr,
false)
1612 && this->_M_equals(__k, __code, __hint)
1614 : _M_find_before_node(__bkt, __k, __code);
1618 __node->_M_nxt = __prev->_M_nxt;
1619 __prev->_M_nxt = __node;
1620 if (__builtin_expect(__prev == __hint,
false))
1624 && !this->_M_equals(__k, __code, __node->_M_next()))
1626 size_type __next_bkt = _M_bucket_index(__node->_M_next());
1627 if (__next_bkt != __bkt)
1628 _M_buckets[__next_bkt] = __node;
1636 _M_insert_bucket_begin(__bkt, __node);
1638 return iterator(__node);
1642 this->_M_deallocate_node(__node);
1643 __throw_exception_again;
1648 template<
typename _Key,
typename _Value,
1649 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1650 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1652 template<
typename _Arg,
typename _NodeGenerator>
1653 std::pair<
typename _Hashtable<_Key, _Value, _Alloc,
1654 _ExtractKey, _Equal, _H1,
1655 _H2, _Hash, _RehashPolicy,
1656 _Traits>::iterator,
bool>
1657 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1658 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1659 _M_insert(_Arg&& __v,
const _NodeGenerator& __node_gen,
std::true_type)
1661 const key_type& __k = this->_M_extract()(__v);
1662 __hash_code __code = this->_M_hash_code(__k);
1663 size_type __bkt = _M_bucket_index(__k, __code);
1665 __node_type* __n = _M_find_node(__bkt, __k, __code);
1669 __n = __node_gen(std::forward<_Arg>(__v));
1670 return std::make_pair(_M_insert_unique_node(__bkt, __code, __n),
true);
1674 template<
typename _Key,
typename _Value,
1675 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1676 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1678 template<
typename _Arg,
typename _NodeGenerator>
1679 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1680 _H1, _H2, _Hash, _RehashPolicy,
1682 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1683 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1684 _M_insert(const_iterator __hint, _Arg&& __v,
1685 const _NodeGenerator& __node_gen,
1690 __hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
1693 __node_type* __node = __node_gen(std::forward<_Arg>(__v));
1695 return _M_insert_multi_node(__hint._M_cur, __code, __node);
1698 template<
typename _Key,
typename _Value,
1699 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1700 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1702 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1703 _H1, _H2, _Hash, _RehashPolicy,
1705 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1706 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1707 erase(const_iterator __it)
1709 __node_type* __n = __it._M_cur;
1710 std::size_t __bkt = _M_bucket_index(__n);
1715 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1716 return _M_erase(__bkt, __prev_n, __n);
1719 template<
typename _Key,
typename _Value,
1720 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1721 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1723 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1724 _H1, _H2, _Hash, _RehashPolicy,
1726 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1727 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1728 _M_erase(size_type __bkt, __node_base* __prev_n, __node_type* __n)
1730 if (__prev_n == _M_buckets[__bkt])
1731 _M_remove_bucket_begin(__bkt, __n->_M_next(),
1732 __n->_M_nxt ? _M_bucket_index(__n->_M_next()) : 0);
1733 else if (__n->_M_nxt)
1735 size_type __next_bkt = _M_bucket_index(__n->_M_next());
1736 if (__next_bkt != __bkt)
1737 _M_buckets[__next_bkt] = __prev_n;
1740 __prev_n->_M_nxt = __n->_M_nxt;
1741 iterator __result(__n->_M_next());
1742 this->_M_deallocate_node(__n);
1748 template<
typename _Key,
typename _Value,
1749 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1750 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1752 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1753 _H1, _H2, _Hash, _RehashPolicy,
1755 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1756 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1759 __hash_code __code = this->_M_hash_code(__k);
1760 std::size_t __bkt = _M_bucket_index(__k, __code);
1763 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1768 __node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);
1769 _M_erase(__bkt, __prev_n, __n);
1773 template<
typename _Key,
typename _Value,
1774 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1775 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1777 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1778 _H1, _H2, _Hash, _RehashPolicy,
1780 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1781 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1784 __hash_code __code = this->_M_hash_code(__k);
1785 std::size_t __bkt = _M_bucket_index(__k, __code);
1788 __node_base* __prev_n = _M_find_before_node(__bkt, __k, __code);
1798 __node_type* __n =
static_cast<__node_type*
>(__prev_n->_M_nxt);
1799 __node_type* __n_last = __n;
1800 std::size_t __n_last_bkt = __bkt;
1803 __n_last = __n_last->_M_next();
1806 __n_last_bkt = _M_bucket_index(__n_last);
1808 while (__n_last_bkt == __bkt && this->_M_equals(__k, __code, __n_last));
1811 size_type __result = 0;
1814 __node_type* __p = __n->_M_next();
1815 this->_M_deallocate_node(__n);
1820 while (__n != __n_last);
1822 if (__prev_n == _M_buckets[__bkt])
1823 _M_remove_bucket_begin(__bkt, __n_last, __n_last_bkt);
1824 else if (__n_last && __n_last_bkt != __bkt)
1825 _M_buckets[__n_last_bkt] = __prev_n;
1826 __prev_n->_M_nxt = __n_last;
1830 template<
typename _Key,
typename _Value,
1831 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1832 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1834 typename _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1835 _H1, _H2, _Hash, _RehashPolicy,
1837 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1838 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1839 erase(const_iterator __first, const_iterator __last)
1841 __node_type* __n = __first._M_cur;
1842 __node_type* __last_n = __last._M_cur;
1843 if (__n == __last_n)
1844 return iterator(__n);
1846 std::size_t __bkt = _M_bucket_index(__n);
1848 __node_base* __prev_n = _M_get_previous_node(__bkt, __n);
1849 bool __is_bucket_begin = __n == _M_bucket_begin(__bkt);
1850 std::size_t __n_bkt = __bkt;
1855 __node_type* __tmp = __n;
1856 __n = __n->_M_next();
1857 this->_M_deallocate_node(__tmp);
1861 __n_bkt = _M_bucket_index(__n);
1863 while (__n != __last_n && __n_bkt == __bkt);
1864 if (__is_bucket_begin)
1865 _M_remove_bucket_begin(__bkt, __n, __n_bkt);
1866 if (__n == __last_n)
1868 __is_bucket_begin =
true;
1872 if (__n && (__n_bkt != __bkt || __is_bucket_begin))
1873 _M_buckets[__n_bkt] = __prev_n;
1874 __prev_n->_M_nxt = __n;
1875 return iterator(__n);
1878 template<
typename _Key,
typename _Value,
1879 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1880 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1883 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1884 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1887 this->_M_deallocate_nodes(_M_begin());
1888 __builtin_memset(_M_buckets, 0, _M_bucket_count *
sizeof(__bucket_type));
1889 _M_element_count = 0;
1890 _M_before_begin._M_nxt =
nullptr;
1893 template<
typename _Key,
typename _Value,
1894 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1895 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1898 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1899 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1900 rehash(size_type __n)
1902 const __rehash_state& __saved_state = _M_rehash_policy._M_state();
1903 std::size_t __buckets
1904 =
std::max(_M_rehash_policy._M_bkt_for_elements(_M_element_count + 1),
1906 __buckets = _M_rehash_policy._M_next_bkt(__buckets);
1908 if (__buckets != _M_bucket_count)
1909 _M_rehash(__buckets, __saved_state);
1912 _M_rehash_policy._M_reset(__saved_state);
1915 template<
typename _Key,
typename _Value,
1916 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1917 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1920 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1921 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1922 _M_rehash(size_type __n,
const __rehash_state& __state)
1926 _M_rehash_aux(__n, __unique_keys());
1932 _M_rehash_policy._M_reset(__state);
1933 __throw_exception_again;
1938 template<
typename _Key,
typename _Value,
1939 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1940 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1943 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1944 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1947 __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
1948 __node_type* __p = _M_begin();
1949 _M_before_begin._M_nxt =
nullptr;
1950 std::size_t __bbegin_bkt = 0;
1953 __node_type* __next = __p->_M_next();
1954 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
1955 if (!__new_buckets[__bkt])
1957 __p->_M_nxt = _M_before_begin._M_nxt;
1958 _M_before_begin._M_nxt = __p;
1959 __new_buckets[__bkt] = &_M_before_begin;
1961 __new_buckets[__bbegin_bkt] = __p;
1962 __bbegin_bkt = __bkt;
1966 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
1967 __new_buckets[__bkt]->_M_nxt = __p;
1972 if (__builtin_expect(_M_bucket_count != 0,
true))
1973 _M_deallocate_buckets();
1974 _M_bucket_count = __n;
1975 _M_buckets = __new_buckets;
1980 template<
typename _Key,
typename _Value,
1981 typename _Alloc,
typename _ExtractKey,
typename _Equal,
1982 typename _H1,
typename _H2,
typename _Hash,
typename _RehashPolicy,
1985 _Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1986 _H1, _H2, _Hash, _RehashPolicy, _Traits>::
1989 __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
1991 __node_type* __p = _M_begin();
1992 _M_before_begin._M_nxt =
nullptr;
1993 std::size_t __bbegin_bkt = 0;
1994 std::size_t __prev_bkt = 0;
1995 __node_type* __prev_p =
nullptr;
1996 bool __check_bucket =
false;
2000 __node_type* __next = __p->_M_next();
2001 std::size_t __bkt = __hash_code_base::_M_bucket_index(__p, __n);
2003 if (__prev_p && __prev_bkt == __bkt)
2008 __p->_M_nxt = __prev_p->_M_nxt;
2009 __prev_p->_M_nxt = __p;
2016 __check_bucket =
true;
2024 if (__prev_p->_M_nxt)
2026 std::size_t __next_bkt
2027 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(),
2029 if (__next_bkt != __prev_bkt)
2030 __new_buckets[__next_bkt] = __prev_p;
2032 __check_bucket =
false;
2035 if (!__new_buckets[__bkt])
2037 __p->_M_nxt = _M_before_begin._M_nxt;
2038 _M_before_begin._M_nxt = __p;
2039 __new_buckets[__bkt] = &_M_before_begin;
2041 __new_buckets[__bbegin_bkt] = __p;
2042 __bbegin_bkt = __bkt;
2046 __p->_M_nxt = __new_buckets[__bkt]->_M_nxt;
2047 __new_buckets[__bkt]->_M_nxt = __p;
2055 if (__check_bucket && __prev_p->_M_nxt)
2057 std::size_t __next_bkt
2058 = __hash_code_base::_M_bucket_index(__prev_p->_M_next(), __n);
2059 if (__next_bkt != __prev_bkt)
2060 __new_buckets[__next_bkt] = __prev_p;
2063 if (__builtin_expect(_M_bucket_count != 0,
true))
2064 _M_deallocate_buckets();
2065 _M_bucket_count = __n;
2066 _M_buckets = __new_buckets;
2069 _GLIBCXX_END_NAMESPACE_VERSION
2072 #endif // _HASHTABLE_H
Uniform interface to C++98 and C++0x allocators.
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.
_T2 second
first is a copy of the first object
constexpr const _Tp * begin(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to the first element of the initializer_list.
constexpr size_t size() const noexcept
Returns the total number of bits.
Node iterators, used to iterate through all the hashtable.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_T1 first
second_type is the second bound type
size_t count() const noexcept
Returns the number of bits which are set.
Uniform interface to all allocator types.
Node const_iterators, used to iterate through all the hashtable.
Struct holding two objects of arbitrary type.
integral_constant< bool, true > true_type
The type used as a compile-time boolean with true value.
constexpr const _Tp * end(initializer_list< _Tp > __ils) noexcept
Return an iterator pointing to one past the last element of the initializer_list. ...
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.