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>
129 : _M_cur(__n), _M_ht(__tab) { }
135 {
return _M_cur->
_M_val; }
149 {
return _M_cur == __it.
_M_cur; }
153 {
return _M_cur != __it.
_M_cur; }
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>
181 : _M_cur(__n), _M_ht(__tab) { }
186 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
190 {
return _M_cur->
_M_val; }
204 {
return _M_cur == __it.
_M_cur; }
208 {
return _M_cur != __it.
_M_cur; }
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
228 const unsigned long* __last = __stl_prime_list + (int)
_S_num_primes;
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;
295 {
return _M_node_allocator.allocate(1); }
299 { _M_node_allocator.deallocate(__p, 1); }
324 hashtable(size_type __n,
const _HashFcn& __hf,
325 const _EqualKey& __eql,
const _ExtractKey& __ext,
327 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
328 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
331 hashtable(size_type __n,
const _HashFcn& __hf,
332 const _EqualKey& __eql,
334 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
335 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
339 : _M_node_allocator(__ht.
get_allocator()), _M_hash(__ht._M_hash),
340 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
350 _M_hash = __ht._M_hash;
351 _M_equals = __ht._M_equals;
352 _M_get_key = __ht._M_get_key;
371 {
return size() == 0; }
379 _M_buckets.swap(__ht._M_buckets);
380 std::swap(_M_num_elements, __ht._M_num_elements);
386 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
388 return iterator(_M_buckets[__n],
this);
399 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
409 template<
class _Vl,
class _Ky,
class _HF,
class _Ex,
class _Eq,
418 {
return _M_buckets.size(); }
427 size_type __result = 0;
428 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
436 resize(_M_num_elements + 1);
443 resize(_M_num_elements + 1);
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)
486 size_type __n = distance(__f, __l);
487 resize(_M_num_elements + __n);
488 for ( ; __n > 0; --__n, ++__f)
492 template<
class _ForwardIterator>
494 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
495 forward_iterator_tag)
497 size_type __n = distance(__f, __l);
498 resize(_M_num_elements + __n);
499 for ( ; __n > 0; --__n, ++__f)
507 find(
const key_type& __key)
511 for (__first = _M_buckets[__n];
519 find(
const key_type& __key)
const
522 const _Node* __first;
523 for (__first = _M_buckets[__n];
531 count(
const key_type& __key)
const
534 size_type __result = 0;
536 for (
const _Node* __cur = _M_buckets[__n]; __cur;
537 __cur = __cur->_M_next)
543 pair<iterator, iterator>
546 pair<const_iterator, const_iterator>
550 erase(
const key_type& __key);
565 resize(size_type __num_elements_hint);
579 _M_buckets.reserve(__n_buckets);
580 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
594 {
return _M_hash(__key) % __n; }
597 _M_bkt_num(
const value_type& __obj,
size_t __n)
const
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;
641 _M_cur = _M_cur->_M_next;
644 size_type __bucket = _M_ht->_M_bkt_num(__old->
_M_val);
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;
669 _M_cur = _M_cur->_M_next;
672 size_type __bucket = _M_ht->_M_bkt_num(__old->
_M_val);
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>
749 const size_type __n = _M_bkt_num(__obj);
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);
757 __tmp->_M_next = __first;
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>
768 const size_type __n = _M_bkt_num(__obj);
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);
795 size_type __n = _M_bkt_num(__obj);
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)))
800 return __cur->_M_val;
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;
819 __first = __first->_M_next)
820 if (_M_equals(_M_get_key(__first->_M_val), __key))
822 for (_Node* __cur = __first->_M_next; __cur;
823 __cur = __cur->_M_next)
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;
845 __first = __first->_M_next)
847 if (_M_equals(_M_get_key(__first->_M_val), __key))
849 for (
const _Node* __cur = __first->_M_next; __cur;
850 __cur = __cur->_M_next)
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];
871 size_type __erased = 0;
875 _Node* __cur = __first;
876 _Node* __next = __cur->
_M_next;
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>
911 const size_type __n = _M_bkt_num(__p->
_M_val);
912 _Node* __cur = _M_buckets[__n];
916 _M_buckets[__n] = __cur->
_M_next;
917 _M_delete_node(__cur);
922 _Node* __next = __cur->
_M_next;
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>
973 const_cast<hashtable*>(__first.
_M_ht)),
975 const_cast<hashtable*>(__last.
_M_ht)));
978 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
983 const_cast<hashtable*>(__it.
_M_ht))); }
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);
996 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
999 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1001 _Node* __first = _M_buckets[__bucket];
1004 size_type __new_bucket = _M_bkt_num(__first->
_M_val,
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])
1021 _Node* __next = __tmp[__bucket]->
_M_next;
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)
1065 _Node* __next = __cur->
_M_next;
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];
1083 _Node* __next = __cur->
_M_next;
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];
1106 _Node* __local_copy = _M_new_node(__cur->
_M_val);
1107 _M_buckets[__i] = __local_copy;
1109 for (_Node* __next = __cur->
_M_next;
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;
hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > _Hashtable
hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > _Hashtable
_Hashtable_node * _M_next
hasher hash_funct() const
pointer operator->() const
bool operator==(const hashtable< _Val, _Key, _HF, _Ex, _Eq, _All > &__ht1, const hashtable< _Val, _Key, _HF, _Ex, _Eq, _All > &__ht2)
ptrdiff_t difference_type
hashtable & operator=(const hashtable &__ht)
_Hashtable_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > const_iterator
pair< iterator, iterator > equal_range(const key_type &__key)
void swap(hashtable &__ht)
reference operator*() const
bool operator==(const iterator &__it) const
_Alloc::template rebind< value_type >::other allocator_type
ptrdiff_t difference_type
unsigned long __stl_next_prime(unsigned long __n)
size_type max_size() const
_Hashtable_node< _Val > _Node
allocator_type get_allocator() const
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
pair< iterator, bool > insert_unique(const value_type &__obj)
bool operator!=(const hashtable< _Val, _Key, _HF, _Ex, _Eq, _All > &__ht1, const hashtable< _Val, _Key, _HF, _Ex, _Eq, _All > &__ht2)
forward_iterator_tag iterator_category
iterator find(const key_type &__key)
const value_type & const_reference
_Hashtable_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > const_iterator
size_type bucket_count() const
_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > iterator
_Hashtable_const_iterator()
size_type max_bucket_count() const
ptrdiff_t difference_type
_Node_Alloc _M_node_allocator
size_type _M_num_elements
_Alloc::template rebind< _Node >::other _Node_Alloc
bool operator==(const const_iterator &__it) const
forward_iterator_tag iterator_category
bool operator!=(const iterator &__it) const
This file is a GNU extension to the Standard C++ Library (possibly containing extensions from the HP/...
vector< _Node *, _Nodeptr_Alloc > _Vector_type
_Hashtable_iterator(_Node *__n, _Hashtable *__tab)
_Hashtable_node< _Val > _Node
bool operator!=(const const_iterator &__it) const
_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > iterator
iterator insert_equal(const value_type &__obj)
size_type count(const key_type &__key) const
const value_type * const_pointer
const_iterator & operator++()
hashtable(size_type __n, const _HashFcn &__hf, const _EqualKey &__eql, const _ExtractKey &__ext, const allocator_type &__a=allocator_type())
_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > iterator
friend bool operator==(const hashtable< _Vl, _Ky, _HF, _Ex, _Eq, _Al > &, const hashtable< _Vl, _Ky, _HF, _Ex, _Eq, _Al > &)
size_type elems_in_bucket(size_type __bucket) const
_Hashtable_const_iterator(const iterator &__it)
static const unsigned long __stl_prime_list[_S_num_primes]
void _M_copy_from(const hashtable &__ht)
_Node * _M_new_node(const value_type &__obj)
void _M_initialize_buckets(size_type __n)
pointer operator->() const
void resize(size_type __num_elements_hint)
_Hashtable_const_iterator(const _Node *__n, const _Hashtable *__tab)
size_type erase(const key_type &__key)
size_type _M_bkt_num_key(const key_type &__key) const
void _M_erase_bucket(const size_type __n, _Node *__first, _Node *__last)
iterator insert_equal_noresize(const value_type &__obj)
size_type _M_bkt_num(const value_type &__obj) const
reference operator*() const
void _M_put_node(_Node *__p)
_Hashtable_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > const_iterator
reference find_or_insert(const value_type &__obj)
void _M_delete_node(_Node *__n)
size_type _M_next_size(size_type __n) const
_Alloc::template rebind< _Node * >::other _Nodeptr_Alloc
void swap(hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht1, hashtable< _Val, _Key, _HF, _Extract, _EqKey, _All > &__ht2)
_Hashtable_node< _Val > _Node