31 #ifndef _HASHTABLE_POLICY_H
32 #define _HASHTABLE_POLICY_H 1
34 namespace std _GLIBCXX_VISIBILITY(default)
36 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 template<
typename _Key,
typename _Value,
typename _Alloc,
39 typename _ExtractKey,
typename _Equal,
40 typename _H1,
typename _H2,
typename _Hash,
41 typename _RehashPolicy,
typename _Traits>
44 _GLIBCXX_END_NAMESPACE_VERSION
48 _GLIBCXX_BEGIN_NAMESPACE_VERSION
55 template<
typename _Key,
typename _Value,
56 typename _ExtractKey,
typename _Equal,
57 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
62 template<
class _Iterator>
63 inline typename std::iterator_traits<_Iterator>::difference_type
64 __distance_fw(_Iterator __first, _Iterator __last,
68 template<
class _Iterator>
69 inline typename std::iterator_traits<_Iterator>::difference_type
70 __distance_fw(_Iterator __first, _Iterator __last,
74 template<
class _Iterator>
75 inline typename std::iterator_traits<_Iterator>::difference_type
76 __distance_fw(_Iterator __first, _Iterator __last)
78 typedef typename std::iterator_traits<_Iterator>::iterator_category _Tag;
79 return __distance_fw(__first, __last, _Tag());
83 template <
typename _Key,
typename _Hash>
85 noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
90 template<
typename _Tp>
92 operator()(_Tp&& __x)
const
93 {
return std::forward<_Tp>(__x); }
98 template<
typename _Tp>
100 operator()(_Tp&& __x) const
101 -> decltype(std::get<0>(std::
forward<_Tp>(__x)))
102 {
return std::get<0>(std::forward<_Tp>(__x)); }
130 template<
bool _Cache_hash_code,
bool _Constant_iterators,
bool _Unique_keys>
161 template<
typename _Value,
bool _Cache_hash_code>
169 template<
typename _Value>
173 std::size_t _M_hash_code;
175 template<
typename... _Args>
177 : _M_v(std::forward<_Args>(__args)...), _M_hash_code() { }
180 _M_next()
const {
return static_cast<_Hash_node*
>(_M_nxt); }
188 template<
typename _Value>
193 template<
typename... _Args>
195 : _M_v(std::forward<_Args>(__args)...) { }
198 _M_next()
const {
return static_cast<_Hash_node*
>(_M_nxt); }
202 template<
typename _Value,
bool _Cache_hash_code>
214 { _M_cur = _M_cur->_M_next(); }
217 template<
typename _Value,
bool _Cache_hash_code>
221 {
return __x._M_cur == __y._M_cur; }
223 template<
typename _Value,
bool _Cache_hash_code>
225 operator!=(
const _Node_iterator_base<_Value, _Cache_hash_code>& __x,
226 const _Node_iterator_base<_Value, _Cache_hash_code>& __y)
227 {
return __x._M_cur != __y._M_cur; }
230 template<
typename _Value,
bool __constant_iterators,
bool __cache>
239 typedef _Value value_type;
240 typedef std::ptrdiff_t difference_type;
244 const _Value*, _Value*>::type;
247 const _Value&, _Value&>::type;
258 {
return this->_M_cur->_M_v; }
281 template<
typename _Value,
bool __constant_iterators,
bool __cache>
290 typedef _Value value_type;
291 typedef std::ptrdiff_t difference_type;
294 typedef const _Value* pointer;
295 typedef const _Value& reference;
310 {
return this->_M_cur->_M_v; }
339 typedef std::size_t first_argument_type;
340 typedef std::size_t second_argument_type;
341 typedef std::size_t result_type;
344 operator()(first_argument_type __num, second_argument_type __den)
const
345 {
return __num % __den; }
360 : _M_max_load_factor(__z), _M_next_resize(0) { }
363 max_load_factor()
const noexcept
364 {
return _M_max_load_factor; }
368 _M_next_bkt(std::size_t __n)
const;
372 _M_bkt_for_elements(std::size_t __n)
const
373 {
return __builtin_ceil(__n / (
long double)_M_max_load_factor); }
380 _M_need_rehash(std::size_t __n_bkt, std::size_t __n_elt,
381 std::size_t __n_ins)
const;
383 typedef std::size_t _State;
387 {
return _M_next_resize; }
390 _M_reset(_State __state)
391 { _M_next_resize = __state; }
393 enum { _S_n_primes =
sizeof(
unsigned long) != 8 ? 256 : 256 + 48 };
395 static const std::size_t _S_growth_factor = 2;
397 float _M_max_load_factor;
398 mutable std::size_t _M_next_resize;
419 template<
typename _Key,
typename _Value,
typename _Alloc,
420 typename _ExtractKey,
typename _Equal,
421 typename _H1,
typename _H2,
typename _Hash,
422 typename _RehashPolicy,
typename _Traits,
423 bool _Unique_keys = _Traits::__unique_keys::value>
427 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
428 typename _H1,
typename _H2,
typename _Hash,
429 typename _RehashPolicy,
typename _Traits>
430 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
431 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
437 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
438 typename _H1,
typename _H2,
typename _Hash,
439 typename _RehashPolicy,
typename _Traits>
440 struct _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
441 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
446 _Equal, _H1, _H2, _Hash,
451 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
453 using __hash_code =
typename __hashtable_base::__hash_code;
454 using __node_type =
typename __hashtable_base::__node_type;
457 using key_type =
typename __hashtable_base::key_type;
470 at(
const key_type& __k);
473 at(
const key_type& __k)
const;
476 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
477 typename _H1,
typename _H2,
typename _Hash,
478 typename _RehashPolicy,
typename _Traits>
479 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
480 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>
482 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
483 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
484 operator[](
const key_type& __k)
486 __hashtable* __h =
static_cast<__hashtable*
>(
this);
487 __hash_code __code = __h->_M_hash_code(__k);
488 std::size_t __n = __h->_M_bucket_index(__k, __code);
489 __node_type* __p = __h->_M_find_node(__n, __k, __code);
496 return __h->_M_insert_unique_node(__n, __code, __p)->second;
499 return (__p->_M_v).second;
502 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
503 typename _H1,
typename _H2,
typename _Hash,
504 typename _RehashPolicy,
typename _Traits>
505 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
506 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>
508 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
509 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
510 operator[](key_type&& __k)
512 __hashtable* __h =
static_cast<__hashtable*
>(
this);
513 __hash_code __code = __h->_M_hash_code(__k);
514 std::size_t __n = __h->_M_bucket_index(__k, __code);
515 __node_type* __p = __h->_M_find_node(__n, __k, __code);
520 std::forward_as_tuple(std::move(__k)),
522 return __h->_M_insert_unique_node(__n, __code, __p)->second;
525 return (__p->_M_v).second;
528 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
529 typename _H1,
typename _H2,
typename _Hash,
530 typename _RehashPolicy,
typename _Traits>
531 typename _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
532 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>
534 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
535 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
536 at(
const key_type& __k)
538 __hashtable* __h =
static_cast<__hashtable*
>(
this);
539 __hash_code __code = __h->_M_hash_code(__k);
540 std::size_t __n = __h->_M_bucket_index(__k, __code);
541 __node_type* __p = __h->_M_find_node(__n, __k, __code);
544 __throw_out_of_range(__N(
"_Map_base::at"));
545 return (__p->_M_v).second;
548 template<
typename _Key,
typename _Pair,
typename _Alloc,
typename _Equal,
549 typename _H1,
typename _H2,
typename _Hash,
550 typename _RehashPolicy,
typename _Traits>
551 const typename _Map_base<_Key, _Pair, _Alloc, _Select1st,
552 _Equal, _H1, _H2, _Hash, _RehashPolicy,
553 _Traits,
true>::mapped_type&
554 _Map_base<_Key, _Pair, _Alloc, _Select1st, _Equal,
555 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
556 at(
const key_type& __k)
const
558 const __hashtable* __h =
static_cast<const __hashtable*
>(
this);
559 __hash_code __code = __h->_M_hash_code(__k);
560 std::size_t __n = __h->_M_bucket_index(__k, __code);
561 __node_type* __p = __h->_M_find_node(__n, __k, __code);
564 __throw_out_of_range(__N(
"_Map_base::at"));
565 return (__p->_M_v).second;
573 template<
typename _Key,
typename _Value,
typename _Alloc,
574 typename _ExtractKey,
typename _Equal,
575 typename _H1,
typename _H2,
typename _Hash,
576 typename _RehashPolicy,
typename _Traits>
580 _Equal, _H1, _H2, _Hash,
581 _RehashPolicy, _Traits>;
584 _Equal, _H1, _H2, _Hash,
587 using value_type =
typename __hashtable_base::value_type;
590 using size_type =
typename __hashtable_base::size_type;
592 using __unique_keys =
typename __hashtable_base::__unique_keys;
593 using __ireturn_type =
typename __hashtable_base::__ireturn_type;
594 using __iconv_type =
typename __hashtable_base::__iconv_type;
597 _M_conjure_hashtable()
601 insert(
const value_type& __v)
604 return __h._M_insert(__v, __unique_keys());
608 insert(const_iterator,
const value_type& __v)
609 {
return __iconv_type()(insert(__v)); }
613 { this->insert(__l.begin(), __l.end()); }
615 template<
typename _InputIterator>
617 insert(_InputIterator __first, _InputIterator __last);
620 template<
typename _Key,
typename _Value,
typename _Alloc,
621 typename _ExtractKey,
typename _Equal,
622 typename _H1,
typename _H2,
typename _Hash,
623 typename _RehashPolicy,
typename _Traits>
624 template<
typename _InputIterator>
626 _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
627 _RehashPolicy, _Traits>::
628 insert(_InputIterator __first, _InputIterator __last)
630 using __rehash_type =
typename __hashtable::__rehash_type;
631 using __rehash_state =
typename __hashtable::__rehash_state;
634 size_type __n_elt = __detail::__distance_fw(__first, __last);
636 __hashtable& __h = _M_conjure_hashtable();
637 __rehash_type& __rehash = __h._M_rehash_policy;
638 const __rehash_state& __saved_state = __rehash._M_state();
639 pair_type __do_rehash = __rehash._M_need_rehash(__h._M_bucket_count,
640 __h._M_element_count,
643 if (__do_rehash.first)
644 __h._M_rehash(__do_rehash.second, __saved_state);
646 for (; __first != __last; ++__first)
647 __h._M_insert(*__first, __unique_keys());
655 template<
typename _Key,
typename _Value,
typename _Alloc,
656 typename _ExtractKey,
typename _Equal,
657 typename _H1,
typename _H2,
typename _Hash,
658 typename _RehashPolicy,
typename _Traits,
659 bool _Constant_iterators = _Traits::__constant_iterators::value,
660 bool _Unique_keys = _Traits::__unique_keys::value>
664 template<
typename _Key,
typename _Value,
typename _Alloc,
665 typename _ExtractKey,
typename _Equal,
666 typename _H1,
typename _H2,
typename _Hash,
667 typename _RehashPolicy,
typename _Traits>
668 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
669 _RehashPolicy, _Traits, true, true>
670 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
671 _H1, _H2, _Hash, _RehashPolicy, _Traits>
674 _Equal, _H1, _H2, _Hash,
675 _RehashPolicy, _Traits>;
676 using value_type =
typename __base_type::value_type;
677 using iterator =
typename __base_type::iterator;
678 using const_iterator =
typename __base_type::const_iterator;
680 using __unique_keys =
typename __base_type::__unique_keys;
683 using __base_type::insert;
686 insert(value_type&& __v)
689 return __h._M_insert(std::move(__v), __unique_keys());
693 insert(const_iterator, value_type&& __v)
694 {
return insert(std::move(__v)).first; }
698 template<
typename _Key,
typename _Value,
typename _Alloc,
699 typename _ExtractKey,
typename _Equal,
700 typename _H1,
typename _H2,
typename _Hash,
701 typename _RehashPolicy,
typename _Traits>
702 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
703 _RehashPolicy, _Traits, true, false>
704 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
705 _H1, _H2, _Hash, _RehashPolicy, _Traits>
708 _Equal, _H1, _H2, _Hash,
709 _RehashPolicy, _Traits>;
710 using value_type =
typename __base_type::value_type;
711 using iterator =
typename __base_type::iterator;
712 using const_iterator =
typename __base_type::const_iterator;
714 using __unique_keys =
typename __base_type::__unique_keys;
717 using __base_type::insert;
720 insert(value_type&& __v)
723 return __h._M_insert(std::move(__v), __unique_keys());
727 insert(const_iterator, value_type&& __v)
728 {
return insert(std::move(__v)); }
732 template<
typename _Key,
typename _Value,
typename _Alloc,
733 typename _ExtractKey,
typename _Equal,
734 typename _H1,
typename _H2,
typename _Hash,
735 typename _RehashPolicy,
typename _Traits,
bool _Unique_keys>
736 struct _Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash,
737 _RehashPolicy, _Traits, false, _Unique_keys>
738 :
public _Insert_base<_Key, _Value, _Alloc, _ExtractKey, _Equal,
739 _H1, _H2, _Hash, _RehashPolicy, _Traits>
742 _Equal, _H1, _H2, _Hash,
743 _RehashPolicy, _Traits>;
744 using value_type =
typename __base_type::value_type;
745 using iterator =
typename __base_type::iterator;
746 using const_iterator =
typename __base_type::const_iterator;
748 using __unique_keys =
typename __base_type::__unique_keys;
750 using __ireturn_type =
typename __base_type::__ireturn_type;
751 using __iconv_type =
typename __base_type::__iconv_type;
753 using __base_type::insert;
755 template<
typename _Pair>
758 template<
typename _Pair>
761 template<
typename _Pair>
764 template<
typename _Pair,
typename = _IFconsp<_Pair>>
769 return __h._M_emplace(__unique_keys(), std::forward<_Pair>(__v));
772 template<
typename _Pair,
typename = _IFconsp<_Pair>>
774 insert(const_iterator, _Pair&& __v)
775 {
return __iconv_type()(insert(std::forward<_Pair>(__v))); }
784 template<
typename _Key,
typename _Value,
typename _Alloc,
785 typename _ExtractKey,
typename _Equal,
786 typename _H1,
typename _H2,
typename _Hash,
787 typename _RehashPolicy,
typename _Traits>
791 template<
typename _Key,
typename _Value,
typename _Alloc,
792 typename _ExtractKey,
typename _Equal,
793 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
798 _Equal, _H1, _H2, _Hash,
802 max_load_factor()
const noexcept
805 return __this->__rehash_policy().max_load_factor();
809 max_load_factor(
float __z)
816 reserve(std::size_t __n)
819 __this->rehash(__builtin_ceil(__n / max_load_factor()));
829 template<
int _Nm,
typename _Tp,
830 bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)>
834 template<
int _Nm,
typename _Tp>
845 {
return static_cast<const _Tp&
>(__eboh); }
849 {
return static_cast<_Tp&
>(__eboh); }
853 template<
int _Nm,
typename _Tp>
863 {
return __eboh._M_tp; }
867 {
return __eboh._M_tp; }
879 template<
typename _Key,
typename _Value,
typename _ExtractKey,
880 typename _H1,
typename _H2,
typename _Hash,
881 bool __cache_hash_code>
904 template<
typename _Key,
typename _Value,
typename _ExtractKey,
905 typename _H1,
typename _H2,
typename _Hash,
906 bool __cache_hash_code>
911 template<
typename _Key,
typename _Value,
typename _ExtractKey,
912 typename _H1,
typename _H2,
typename _Hash>
922 typedef void* __hash_code;
933 _M_hash_code(
const _Key& __key)
const
937 _M_bucket_index(
const _Key& __k, __hash_code, std::size_t __n)
const
938 {
return _M_ranged_hash()(__k, __n); }
941 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
942 {
return _M_ranged_hash()(_M_extract()(__p->_M_v), __n); }
955 std::swap(_M_extract(), __x._M_extract());
956 std::swap(_M_ranged_hash(), __x._M_ranged_hash());
960 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
963 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
966 _M_ranged_hash()
const {
return __ebo_hash::_S_cget(*
this); }
969 _M_ranged_hash() {
return __ebo_hash::_S_get(*
this); }
978 template<
typename _Key,
typename _Value,
typename _ExtractKey,
979 typename _H1,
typename _H2,
typename _Hash>
980 struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>;
985 template<
typename _Key,
typename _Value,
typename _ExtractKey,
986 typename _H1,
typename _H2>
1002 hash_function()
const
1006 typedef std::size_t __hash_code;
1013 const _H1& __h1,
const _H2& __h2,
1018 _M_hash_code(
const _Key& __k)
const
1019 {
return _M_h1()(__k); }
1022 _M_bucket_index(
const _Key&, __hash_code __c, std::size_t __n)
const
1023 {
return _M_h2()(__c, __n); }
1027 std::size_t __n)
const
1028 {
return _M_h2()(_M_h1()(_M_extract()(__p->_M_v)), __n); }
1041 std::swap(_M_extract(), __x._M_extract());
1042 std::swap(_M_h1(), __x._M_h1());
1043 std::swap(_M_h2(), __x._M_h2());
1047 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1050 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1053 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1056 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1059 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1062 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1068 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1069 typename _H1,
typename _H2>
1079 _Default_ranged_hash, true>;
1089 hash_function()
const
1093 typedef std::size_t __hash_code;
1097 const _H1& __h1,
const _H2& __h2,
1098 const _Default_ranged_hash&)
1102 _M_hash_code(
const _Key& __k)
const
1103 {
return _M_h1()(__k); }
1106 _M_bucket_index(
const _Key&, __hash_code __c,
1107 std::size_t __n)
const
1108 {
return _M_h2()(__c, __n); }
1111 _M_bucket_index(
const __node_type* __p, std::size_t __n)
const
1112 {
return _M_h2()(__p->_M_hash_code, __n); }
1115 _M_store_code(
__node_type* __n, __hash_code __c)
const
1116 { __n->_M_hash_code = __c; }
1120 { __to->_M_hash_code = __from->_M_hash_code; }
1125 std::swap(_M_extract(), __x._M_extract());
1126 std::swap(_M_h1(), __x._M_h1());
1127 std::swap(_M_h2(), __x._M_h2());
1131 _M_extract()
const {
return __ebo_extract_key::_S_cget(*
this); }
1134 _M_extract() {
return __ebo_extract_key::_S_get(*
this); }
1137 _M_h1()
const {
return __ebo_h1::_S_cget(*
this); }
1140 _M_h1() {
return __ebo_h1::_S_get(*
this); }
1143 _M_h2()
const {
return __ebo_h2::_S_cget(*
this); }
1146 _M_h2() {
return __ebo_h2::_S_get(*
this); }
1153 template <
typename _Key,
typename _Value,
typename _ExtractKey,
1154 typename _Equal,
typename _HashCodeType,
1155 bool __cache_hash_code>
1159 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1160 typename _Equal,
typename _HashCodeType>
1164 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1166 {
return __c == __n->_M_hash_code && __eq(__k, __extract(__n->_M_v)); }
1170 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1171 typename _Equal,
typename _HashCodeType>
1175 _S_equals(
const _Equal& __eq,
const _ExtractKey& __extract,
1177 {
return __eq(__k, __extract(__n->_M_v)); }
1182 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1183 typename _H1,
typename _H2,
typename _Hash>
1185 _H1, _H2, _Hash, true>
1191 _H1, _H2, _Hash,
true>;
1197 std::size_t __bkt, std::size_t __bkt_count)
1199 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1204 _M_cur = _M_cur->_M_next();
1208 = __base_type::_S_get(*
this)(_M_cur->_M_hash_code,
1210 if (__bkt != _M_bucket)
1216 std::size_t _M_bucket;
1217 std::size_t _M_bucket_count;
1221 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1222 typename _H1,
typename _H2,
typename _Hash>
1224 _H1, _H2, _Hash, false>
1226 _H1, _H2, _Hash, false>
1230 _H1, _H2, _Hash,
false>;
1236 std::size_t __bkt, std::size_t __bkt_count)
1238 _M_cur(__p), _M_bucket(__bkt), _M_bucket_count(__bkt_count) { }
1243 _M_cur = _M_cur->_M_next();
1246 std::size_t __bkt = this->_M_bucket_index(_M_cur, _M_bucket_count);
1247 if (__bkt != _M_bucket)
1253 std::size_t _M_bucket;
1254 std::size_t _M_bucket_count;
1257 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1258 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1261 _H1, _H2, _Hash, __cache>& __x,
1263 _H1, _H2, _Hash, __cache>& __y)
1264 {
return __x._M_cur == __y._M_cur; }
1266 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1267 typename _H1,
typename _H2,
typename _Hash,
bool __cache>
1269 operator!=(
const _Local_iterator_base<_Key, _Value, _ExtractKey,
1270 _H1, _H2, _Hash, __cache>& __x,
1271 const _Local_iterator_base<_Key, _Value, _ExtractKey,
1272 _H1, _H2, _Hash, __cache>& __y)
1273 {
return __x._M_cur != __y._M_cur; }
1276 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1277 typename _H1,
typename _H2,
typename _Hash,
1278 bool __constant_iterators,
bool __cache>
1281 _H1, _H2, _Hash, __cache>
1285 _H1, _H2, _Hash, __cache>;
1286 using __hash_code_base =
typename __base_type::__hash_code_base;
1288 typedef _Value value_type;
1290 const _Value*, _Value*>::type
1293 const _Value&, _Value&>::type
1295 typedef std::ptrdiff_t difference_type;
1302 std::size_t __bkt, std::size_t __bkt_count)
1308 {
return this->_M_cur->_M_v; }
1331 template<
typename _Key,
typename _Value,
typename _ExtractKey,
1332 typename _H1,
typename _H2,
typename _Hash,
1333 bool __constant_iterators,
bool __cache>
1336 _H1, _H2, _Hash, __cache>
1340 _H1, _H2, _Hash, __cache>;
1341 using __hash_code_base =
typename __base_type::__hash_code_base;
1344 typedef _Value value_type;
1345 typedef const _Value* pointer;
1346 typedef const _Value& reference;
1347 typedef std::ptrdiff_t difference_type;
1354 std::size_t __bkt, std::size_t __bkt_count)
1360 __constant_iterators,
1367 {
return this->_M_cur->_M_v; }
1399 template<
typename _Key,
typename _Value,
1400 typename _ExtractKey,
typename _Equal,
1401 typename _H1,
typename _H2,
typename _Hash,
typename _Traits>
1404 _Traits::__hash_cached::value>,
1408 typedef _Key key_type;
1409 typedef _Value value_type;
1410 typedef _Equal key_equal;
1411 typedef std::size_t size_type;
1412 typedef std::ptrdiff_t difference_type;
1414 using __traits_type = _Traits;
1415 using __hash_cached =
typename __traits_type::__hash_cached;
1416 using __constant_iterators =
typename __traits_type::__constant_iterators;
1417 using __unique_keys =
typename __traits_type::__unique_keys;
1421 __hash_cached::value>;
1423 using __hash_code =
typename __hash_code_base::__hash_code;
1424 using __node_type =
typename __hash_code_base::__node_type;
1427 __constant_iterators::value,
1428 __hash_cached::value>;
1431 __constant_iterators::value,
1432 __hash_cached::value>;
1435 _ExtractKey, _H1, _H2, _Hash,
1436 __constant_iterators::value,
1437 __hash_cached::value>;
1441 _ExtractKey, _H1, _H2, _Hash,
1442 __constant_iterators::value,
1443 __hash_cached::value>;
1450 _Select1st, _Identity
1454 using _EqualHelper =
_Equal_helper<_Key, _Value, _ExtractKey, _Equal,
1455 __hash_code, __hash_cached::value>;
1459 using __bucket_type = __node_base*;
1461 _Hashtable_base(
const _ExtractKey& __ex,
const _H1& __h1,
const _H2& __h2,
1462 const _Hash& __hash,
const _Equal& __eq)
1463 : __hash_code_base(__ex, __h1, __h2, __hash), _EqualEBO(__eq)
1467 _M_equals(
const _Key& __k, __hash_code __c, __node_type* __n)
const
1469 return _EqualHelper::_S_equals(_M_eq(), this->_M_extract(),
1474 _M_swap(_Hashtable_base& __x)
1476 __hash_code_base::_M_swap(__x);
1477 std::swap(_M_eq(), __x._M_eq());
1481 _M_eq()
const {
return _EqualEBO::_S_cget(*
this); }
1484 _M_eq() {
return _EqualEBO::_S_get(*
this); }
1495 template<
typename _Uiterator>
1497 _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
1501 template<
typename _Uiterator>
1504 _S_is_permutation(_Uiterator __first1, _Uiterator __last1,
1505 _Uiterator __first2)
1507 for (; __first1 != __last1; ++__first1, ++__first2)
1508 if (!(*__first1 == *__first2))
1511 if (__first1 == __last1)
1514 _Uiterator __last2 = __first2;
1517 for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
1519 _Uiterator __tmp = __first1;
1520 while (__tmp != __it1 && !
bool(*__tmp == *__it1))
1527 std::ptrdiff_t __n2 = 0;
1528 for (__tmp = __first2; __tmp != __last2; ++__tmp)
1529 if (*__tmp == *__it1)
1535 std::ptrdiff_t __n1 = 0;
1536 for (__tmp = __it1; __tmp != __last1; ++__tmp)
1537 if (*__tmp == *__it1)
1554 template<
typename _Key,
typename _Value,
typename _Alloc,
1555 typename _ExtractKey,
typename _Equal,
1556 typename _H1,
typename _H2,
typename _Hash,
1557 typename _RehashPolicy,
typename _Traits,
1558 bool _Unique_keys = _Traits::__unique_keys::value>
1562 template<
typename _Key,
typename _Value,
typename _Alloc,
1563 typename _ExtractKey,
typename _Equal,
1564 typename _H1,
typename _H2,
typename _Hash,
1565 typename _RehashPolicy,
typename _Traits>
1567 _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
1570 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1576 template<
typename _Key,
typename _Value,
typename _Alloc,
1577 typename _ExtractKey,
typename _Equal,
1578 typename _H1,
typename _H2,
typename _Hash,
1579 typename _RehashPolicy,
typename _Traits>
1581 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1582 _H1, _H2, _Hash, _RehashPolicy, _Traits,
true>::
1583 _M_equal(
const __hashtable& __other)
const
1585 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1587 if (__this->size() != __other.size())
1590 for (
auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
1592 const auto __ity = __other.find(_ExtractKey()(*__itx));
1593 if (__ity == __other.end() || !bool(*__ity == *__itx))
1600 template<
typename _Key,
typename _Value,
typename _Alloc,
1601 typename _ExtractKey,
typename _Equal,
1602 typename _H1,
typename _H2,
typename _Hash,
1603 typename _RehashPolicy,
typename _Traits>
1605 _H1, _H2, _Hash, _RehashPolicy, _Traits, false>
1609 _H1, _H2, _Hash, _RehashPolicy, _Traits>;
1615 template<
typename _Key,
typename _Value,
typename _Alloc,
1616 typename _ExtractKey,
typename _Equal,
1617 typename _H1,
typename _H2,
typename _Hash,
1618 typename _RehashPolicy,
typename _Traits>
1620 _Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal,
1621 _H1, _H2, _Hash, _RehashPolicy, _Traits,
false>::
1622 _M_equal(
const __hashtable& __other)
const
1624 const __hashtable* __this =
static_cast<const __hashtable*
>(
this);
1626 if (__this->size() != __other.size())
1629 for (
auto __itx = __this->begin(); __itx != __this->end();)
1631 const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
1632 const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
1638 if (!_S_is_permutation(__xrange.first, __xrange.second,
1642 __itx = __xrange.second;
1651 template<
typename _NodeAlloc>
1659 template<
typename _Alloc>
1661 : _NodeAlloc(std::forward<_Alloc>(__a))
1666 _GLIBCXX_END_NAMESPACE_VERSION
1670 #endif // _HASHTABLE_POLICY_H