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; }
139 {
return &(operator*()); }
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>
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; }
194 {
return &(operator*()); }
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>
252 template<
class _Val,
class _Key,
class _HashFcn,
253 class _ExtractKey,
class _EqualKey,
class _Alloc>
275 {
return _M_equals; }
284 {
return _M_node_allocator; }
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,
326 const allocator_type& __a = allocator_type())
327 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
328 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
329 { _M_initialize_buckets(__n); }
331 hashtable(size_type __n,
const _HashFcn& __hf,
332 const _EqualKey& __eql,
333 const allocator_type& __a = allocator_type())
334 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
335 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
336 { _M_initialize_buckets(__n); }
342 { _M_copy_from(__ht); }
363 {
return _M_num_elements; }
367 {
return size_type(-1); }
371 {
return size() == 0; }
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(); }
421 max_bucket_count()
const 425 elems_in_bucket(size_type __bucket)
const 427 size_type __result = 0;
428 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
434 insert_unique(
const value_type& __obj)
436 resize(_M_num_elements + 1);
437 return insert_unique_noresize(__obj);
441 insert_equal(
const value_type& __obj)
443 resize(_M_num_elements + 1);
444 return insert_equal_noresize(__obj);
448 insert_unique_noresize(
const value_type& __obj);
451 insert_equal_noresize(
const value_type& __obj);
453 template<
class _InputIterator>
455 insert_unique(_InputIterator __f, _InputIterator __l)
456 { insert_unique(__f, __l, __iterator_category(__f)); }
458 template<
class _InputIterator>
460 insert_equal(_InputIterator __f, _InputIterator __l)
461 { insert_equal(__f, __l, __iterator_category(__f)); }
463 template<
class _InputIterator>
465 insert_unique(_InputIterator __f, _InputIterator __l,
468 for ( ; __f != __l; ++__f)
472 template<
class _InputIterator>
474 insert_equal(_InputIterator __f, _InputIterator __l,
477 for ( ; __f != __l; ++__f)
481 template<
class _ForwardIterator>
483 insert_unique(_ForwardIterator __f, _ForwardIterator __l,
484 forward_iterator_tag)
486 size_type __n = distance(__f, __l);
487 resize(_M_num_elements + __n);
488 for ( ; __n > 0; --__n, ++__f)
489 insert_unique_noresize(*__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)
500 insert_equal_noresize(*__f);
504 find_or_insert(
const value_type& __obj);
507 find(
const key_type& __key)
509 size_type __n = _M_bkt_num_key(__key);
511 for (__first = _M_buckets[__n];
512 __first && !_M_equals(_M_get_key(__first->
_M_val), __key);
519 find(
const key_type& __key)
const 521 size_type __n = _M_bkt_num_key(__key);
522 const _Node* __first;
523 for (__first = _M_buckets[__n];
524 __first && !_M_equals(_M_get_key(__first->
_M_val), __key);
531 count(
const key_type& __key)
const 533 const size_type __n = _M_bkt_num_key(__key);
534 size_type __result = 0;
536 for (
const _Node* __cur = _M_buckets[__n]; __cur;
537 __cur = __cur->_M_next)
538 if (_M_equals(_M_get_key(__cur->_M_val), __key))
543 pair<iterator, iterator>
544 equal_range(
const key_type& __key);
546 pair<const_iterator, const_iterator>
547 equal_range(
const key_type& __key)
const;
550 erase(
const key_type& __key);
565 resize(size_type __num_elements_hint);
572 _M_next_size(size_type __n)
const 576 _M_initialize_buckets(size_type __n)
578 const size_type __n_buckets = _M_next_size(__n);
579 _M_buckets.reserve(__n_buckets);
580 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
585 _M_bkt_num_key(
const key_type& __key)
const 586 {
return _M_bkt_num_key(__key, _M_buckets.size()); }
589 _M_bkt_num(
const value_type& __obj)
const 590 {
return _M_bkt_num_key(_M_get_key(__obj)); }
593 _M_bkt_num_key(
const key_type& __key,
size_t __n)
const 594 {
return _M_hash(__key) % __n; }
597 _M_bkt_num(
const value_type& __obj,
size_t __n)
const 598 {
return _M_bkt_num_key(_M_get_key(__obj), __n); }
601 _M_new_node(
const value_type& __obj)
603 _Node* __n = _M_get_node();
607 this->get_allocator().construct(&__n->
_M_val, __obj);
613 __throw_exception_again;
618 _M_delete_node(_Node* __n)
620 this->get_allocator().destroy(&__n->
_M_val);
625 _M_erase_bucket(
const size_type __n, _Node* __first, _Node* __last);
628 _M_erase_bucket(
const size_type __n, _Node* __last);
634 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
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>
700 for (
size_t __n = 0; __n < __ht1.
_M_buckets.size(); ++__n)
705 for (; __cur1 && __cur2;
706 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
708 if (__cur1 || __cur2)
712 __cur1 = __cur1->_M_next)
714 bool _found__cur1 =
false;
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>
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) {
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;
1123 __throw_exception_again;
hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > _Hashtable
hashtable< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > _Hashtable
bool operator!=(const iterator &__it) const
_Hashtable_node * _M_next
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_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > const_iterator
pair< iterator, iterator > equal_range(const key_type &__key)
void swap(hashtable &__ht)
hasher hash_funct() const
_Alloc::template rebind< value_type >::other allocator_type
ptrdiff_t difference_type
unsigned long __stl_next_prime(unsigned long __n)
_Hashtable_node< _Val > _Node
bool operator==(const const_iterator &__it) const
pair< iterator, bool > insert_unique_noresize(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
const value_type & const_reference
reference operator*() const
_Hashtable_const_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > const_iterator
_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > iterator
pointer operator->() const
_Hashtable_const_iterator()
ptrdiff_t difference_type
_Node_Alloc _M_node_allocator
size_type _M_num_elements
_Alloc::template rebind< _Node >::other _Node_Alloc
forward_iterator_tag iterator_category
pointer operator->() 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
_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > iterator
const value_type * const_pointer
const_iterator & operator++()
allocator_type get_allocator() const
bool operator!=(const const_iterator &__it) const
_Hashtable_iterator< _Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc > iterator
reference operator*() const
bool operator==(const iterator &__it) const
_Hashtable_const_iterator(const iterator &__it)
static const unsigned long __stl_prime_list[_S_num_primes]
void _M_copy_from(const hashtable &__ht)
void resize(size_type __num_elements_hint)
_Hashtable_const_iterator(const _Node *__n, const _Hashtable *__tab)
size_type erase(const key_type &__key)
void _M_erase_bucket(const size_type __n, _Node *__first, _Node *__last)
iterator insert_equal_noresize(const value_type &__obj)
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)
_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