63 #define _HASHTABLE_H 1
77 using std::forward_iterator_tag;
78 using std::input_iterator_tag;
79 using std::_Construct;
84 using std::__iterator_category;
93 template<
class _Val,
class _Key,
class _HashFcn,
class _ExtractKey,
94 class _EqualKey,
class _Alloc = std::allocator<_Val> >
97 template<
class _Val,
class _Key,
class _HashFcn,
98 class _ExtractKey,
class _EqualKey,
class _Alloc>
101 template<
class _Val,
class _Key,
class _HashFcn,
102 class _ExtractKey,
class _EqualKey,
class _Alloc>
105 template<
class _Val,
class _Key,
class _HashFcn,
106 class _ExtractKey,
class _EqualKey,
class _Alloc>
112 _ExtractKey, _EqualKey, _Alloc>
115 _ExtractKey, _EqualKey, _Alloc>
156 template<
class _Val,
class _Key,
class _HashFcn,
157 class _ExtractKey,
class _EqualKey,
class _Alloc>
158 struct _Hashtable_const_iterator
160 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
163 _ExtractKey,_EqualKey,_Alloc>
166 _ExtractKey, _EqualKey, _Alloc>
216 53ul, 97ul, 193ul, 389ul, 769ul,
217 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
218 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
219 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
220 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
221 1610612741ul, 3221225473ul, 4294967291ul
229 const unsigned long* pos = std::lower_bound(__first, __last, __n);
230 return pos == __last ? *(__last - 1) : *pos;
234 template<
class _Val,
class _Key,
class _HF,
class _Ex,
235 class _Eq,
class _All>
238 template<
class _Val,
class _Key,
class _HF,
class _Ex,
239 class _Eq,
class _All>
241 operator==(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
242 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
252 template<
class _Val,
class _Key,
class _HashFcn,
253 class _ExtractKey,
class _EqualKey,
class _Alloc>
287 typedef typename _Alloc::template rebind<_Node>::other
_Node_Alloc;
325 const _EqualKey& __eql,
const _ExtractKey& __ext,
332 const _EqualKey& __eql,
371 {
return size() == 0; }
409 template<
class _Vl,
class _Ky,
class _HF,
class _Ex,
class _Eq,
453 template<
class _InputIterator>
458 template<
class _InputIterator>
463 template<
class _InputIterator>
468 for ( ; __f != __l; ++__f)
472 template<
class _InputIterator>
477 for ( ; __f != __l; ++__f)
481 template<
class _ForwardIterator>
484 forward_iterator_tag)
488 for ( ; __n > 0; --__n, ++__f)
492 template<
class _ForwardIterator>
494 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
495 forward_iterator_tag)
499 for ( ; __n > 0; --__n, ++__f)
522 const _Node* __first;
537 __cur = __cur->_M_next)
543 pair<iterator, iterator>
546 pair<const_iterator, const_iterator>
594 {
return _M_hash(__key) % __n; }
613 __throw_exception_again;
634 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
636 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
640 const _Node* __old = _M_cur;
645 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
646 _M_cur = _M_ht->_M_buckets[__bucket];
651 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
662 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
668 const _Node* __old = _M_cur;
673 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
674 _M_cur = _M_ht->_M_buckets[__bucket];
679 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
690 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
697 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
700 for (
size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
702 _Node* __cur1 = __ht1._M_buckets[__n];
703 _Node* __cur2 = __ht2._M_buckets[__n];
705 for (; __cur1 && __cur2;
706 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
708 if (__cur1 || __cur2)
711 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
712 __cur1 = __cur1->_M_next)
714 bool _found__cur1 =
false;
715 for (__cur2 = __ht2._M_buckets[__n];
716 __cur2; __cur2 = __cur2->_M_next)
718 if (__cur1->_M_val == __cur2->_M_val)
731 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
735 {
return !(__ht1 == __ht2); }
737 template<
class _Val,
class _Key,
class _HF,
class _Extract,
class _EqKey,
742 { __ht1.swap(__ht2); }
744 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
745 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
bool>
750 _Node* __first = _M_buckets[__n];
752 for (
_Node* __cur = __first; __cur; __cur = __cur->
_M_next)
753 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
754 return pair<iterator, bool>(
iterator(__cur,
this),
false);
756 _Node* __tmp = _M_new_node(__obj);
758 _M_buckets[__n] = __tmp;
760 return pair<iterator, bool>(
iterator(__tmp,
this),
true);
763 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
769 _Node* __first = _M_buckets[__n];
771 for (
_Node* __cur = __first; __cur; __cur = __cur->
_M_next)
772 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
774 _Node* __tmp = _M_new_node(__obj);
781 _Node* __tmp = _M_new_node(__obj);
783 _M_buckets[__n] = __tmp;
788 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
793 resize(_M_num_elements + 1);
796 _Node* __first = _M_buckets[__n];
798 for (
_Node* __cur = __first; __cur; __cur = __cur->
_M_next)
799 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
802 _Node* __tmp = _M_new_node(__obj);
804 _M_buckets[__n] = __tmp;
809 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
810 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
815 typedef pair<iterator, iterator> _Pii;
816 const size_type __n = _M_bkt_num_key(__key);
818 for (
_Node* __first = _M_buckets[__n]; __first;
820 if (_M_equals(_M_get_key(__first->_M_val), __key))
824 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
826 for (
size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
828 return _Pii(
iterator(__first,
this),
830 return _Pii(
iterator(__first,
this), end());
832 return _Pii(end(), end());
835 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
836 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
841 typedef pair<const_iterator, const_iterator> _Pii;
842 const size_type __n = _M_bkt_num_key(__key);
844 for (
const _Node* __first = _M_buckets[__n]; __first;
847 if (_M_equals(_M_get_key(__first->_M_val), __key))
851 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
854 for (
size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
861 return _Pii(end(), end());
864 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
869 const size_type __n = _M_bkt_num_key(__key);
870 _Node* __first = _M_buckets[__n];
875 _Node* __cur = __first;
879 if (_M_equals(_M_get_key(__next->
_M_val), __key))
882 _M_delete_node(__next);
893 if (_M_equals(_M_get_key(__first->
_M_val), __key))
895 _M_buckets[__n] = __first->
_M_next;
896 _M_delete_node(__first);
904 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
912 _Node* __cur = _M_buckets[__n];
916 _M_buckets[__n] = __cur->
_M_next;
917 _M_delete_node(__cur);
928 _M_delete_node(__next);
942 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
955 else if (__f_bucket == __l_bucket)
956 _M_erase_bucket(__f_bucket, __first.
_M_cur, __last.
_M_cur);
959 _M_erase_bucket(__f_bucket, __first.
_M_cur, 0);
960 for (
size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
961 _M_erase_bucket(__n, 0);
962 if (__l_bucket != _M_buckets.size())
963 _M_erase_bucket(__l_bucket, __last.
_M_cur);
967 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
978 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
985 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
990 const size_type __old_n = _M_buckets.size();
991 if (__num_elements_hint > __old_n)
993 const size_type __n = _M_next_size(__num_elements_hint);
999 for (
size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1001 _Node* __first = _M_buckets[__bucket];
1006 _M_buckets[__bucket] = __first->
_M_next;
1007 __first->
_M_next = __tmp[__new_bucket];
1008 __tmp[__new_bucket] = __first;
1009 __first = _M_buckets[__bucket];
1012 _M_buckets.swap(__tmp);
1016 for (
size_type __bucket = 0; __bucket < __tmp.size();
1019 while (__tmp[__bucket])
1022 _M_delete_node(__tmp[__bucket]);
1023 __tmp[__bucket] = __next;
1026 __throw_exception_again;
1032 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1037 _Node* __cur = _M_buckets[__n];
1038 if (__cur == __first)
1039 _M_erase_bucket(__n, __last);
1045 __cur = __next, __next = __cur->
_M_next)
1047 while (__next != __last)
1050 _M_delete_node(__next);
1057 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1062 _Node* __cur = _M_buckets[__n];
1063 while (__cur != __last)
1066 _M_delete_node(__cur);
1068 _M_buckets[__n] = __cur;
1073 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1078 for (
size_type __i = 0; __i < _M_buckets.size(); ++__i)
1080 _Node* __cur = _M_buckets[__i];
1084 _M_delete_node(__cur);
1087 _M_buckets[__i] = 0;
1089 _M_num_elements = 0;
1092 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1098 _M_buckets.reserve(__ht._M_buckets.size());
1099 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (
_Node*) 0);
1102 for (
size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1103 const _Node* __cur = __ht._M_buckets[__i];
1107 _M_buckets[__i] = __local_copy;
1111 __cur = __next, __next = __cur->
_M_next)
1113 __local_copy->
_M_next = _M_new_node(__next->_M_val);
1114 __local_copy = __local_copy->
_M_next;
1118 _M_num_elements = __ht._M_num_elements;
1123 __throw_exception_again;