56 #ifndef _BACKWARD_HASHTABLE_H
57 #define _BACKWARD_HASHTABLE_H 1
69 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
71 _GLIBCXX_BEGIN_NAMESPACE_VERSION
74 struct _Hashtable_node
76 _Hashtable_node* _M_next;
80 template<
class _Val,
class _Key,
class _HashFcn,
class _ExtractKey,
84 template<
class _Val,
class _Key,
class _HashFcn,
85 class _ExtractKey,
class _EqualKey,
class _Alloc>
86 struct _Hashtable_iterator;
88 template<
class _Val,
class _Key,
class _HashFcn,
89 class _ExtractKey,
class _EqualKey,
class _Alloc>
90 struct _Hashtable_const_iterator;
92 template<
class _Val,
class _Key,
class _HashFcn,
93 class _ExtractKey,
class _EqualKey,
class _Alloc>
94 struct _Hashtable_iterator
96 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
98 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
99 _ExtractKey, _EqualKey, _Alloc>
101 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
102 _ExtractKey, _EqualKey, _Alloc>
104 typedef _Hashtable_node<_Val> _Node;
106 typedef _Val value_type;
107 typedef std::ptrdiff_t difference_type;
108 typedef std::size_t size_type;
109 typedef _Val& reference;
110 typedef _Val* pointer;
115 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
116 : _M_cur(__n), _M_ht(__tab) { }
118 _Hashtable_iterator() { }
122 {
return _M_cur->_M_val; }
135 operator==(
const iterator& __it)
const
136 {
return _M_cur == __it._M_cur; }
139 operator!=(
const iterator& __it)
const
140 {
return _M_cur != __it._M_cur; }
143 template<
class _Val,
class _Key,
class _HashFcn,
144 class _ExtractKey,
class _EqualKey,
class _Alloc>
145 struct _Hashtable_const_iterator
147 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
149 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
150 _ExtractKey,_EqualKey,_Alloc>
152 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
153 _ExtractKey, _EqualKey, _Alloc>
155 typedef _Hashtable_node<_Val> _Node;
158 typedef _Val value_type;
159 typedef std::ptrdiff_t difference_type;
160 typedef std::size_t size_type;
161 typedef const _Val& reference;
162 typedef const _Val* pointer;
165 const _Hashtable* _M_ht;
167 _Hashtable_const_iterator(
const _Node* __n,
const _Hashtable* __tab)
168 : _M_cur(__n), _M_ht(__tab) { }
170 _Hashtable_const_iterator() { }
172 _Hashtable_const_iterator(
const iterator& __it)
173 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
177 {
return _M_cur->_M_val; }
190 operator==(
const const_iterator& __it)
const
191 {
return _M_cur == __it._M_cur; }
194 operator!=(
const const_iterator& __it)
const
195 {
return _M_cur != __it._M_cur; }
199 enum { _S_num_primes = 29 };
201 template<
typename _PrimeType>
202 struct _Hashtable_prime_list
204 static const _PrimeType __stl_prime_list[_S_num_primes];
206 static const _PrimeType*
210 template<
typename _PrimeType>
const _PrimeType
211 _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] =
213 5ul, 53ul, 97ul, 193ul, 389ul,
214 769ul, 1543ul, 3079ul, 6151ul, 12289ul,
215 24593ul, 49157ul, 98317ul, 196613ul, 393241ul,
216 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul,
217 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul,
218 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul
221 template<
class _PrimeType>
inline const _PrimeType*
222 _Hashtable_prime_list<_PrimeType>::_S_get_prime_list()
224 return __stl_prime_list;
228 __stl_next_prime(
unsigned long __n)
230 const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list();
231 const unsigned long* __last = __first + (int)_S_num_primes;
232 const unsigned long* pos = std::lower_bound(__first, __last, __n);
233 return pos == __last ? *(__last - 1) : *pos;
237 template<
class _Val,
class _Key,
class _HF,
class _Ex,
238 class _Eq,
class _All>
241 template<
class _Val,
class _Key,
class _HF,
class _Ex,
242 class _Eq,
class _All>
244 operator==(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
245 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
255 template<
class _Val,
class _Key,
class _HashFcn,
256 class _ExtractKey,
class _EqualKey,
class _Alloc>
260 typedef _Key key_type;
261 typedef _Val value_type;
262 typedef _HashFcn hasher;
263 typedef _EqualKey key_equal;
265 typedef std::size_t size_type;
266 typedef std::ptrdiff_t difference_type;
267 typedef value_type* pointer;
268 typedef const value_type* const_pointer;
269 typedef value_type& reference;
270 typedef const value_type& const_reference;
278 {
return _M_equals; }
281 typedef _Hashtable_node<_Val> _Node;
285 rebind<value_type>::other allocator_type;
288 get_allocator()
const
289 {
return _M_node_allocator; }
293 typedef typename _Alloc_traits::template rebind<_Node>::other
295 typedef typename _Alloc_traits::template rebind<_Node*>::other
299 _Node_Alloc _M_node_allocator;
303 {
return _M_node_allocator.allocate(1); }
306 _M_put_node(_Node* __p)
307 { _M_node_allocator.deallocate(__p, 1); }
312 _ExtractKey _M_get_key;
313 _Vector_type _M_buckets;
314 size_type _M_num_elements;
317 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
320 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
325 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
328 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
332 hashtable(size_type __n,
const _HashFcn& __hf,
333 const _EqualKey& __eql,
const _ExtractKey& __ext,
334 const allocator_type& __a = allocator_type())
335 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
336 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
337 { _M_initialize_buckets(__n); }
339 hashtable(size_type __n,
const _HashFcn& __hf,
340 const _EqualKey& __eql,
341 const allocator_type& __a = allocator_type())
342 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
343 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
344 { _M_initialize_buckets(__n); }
346 hashtable(
const hashtable& __ht)
347 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
348 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
349 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
350 { _M_copy_from(__ht); }
353 operator= (
const hashtable& __ht)
358 _M_hash = __ht._M_hash;
359 _M_equals = __ht._M_equals;
360 _M_get_key = __ht._M_get_key;
371 {
return _M_num_elements; }
375 {
return size_type(-1); }
377 _GLIBCXX_NODISCARD
bool
379 {
return size() == 0; }
382 swap(hashtable& __ht)
387 _M_buckets.swap(__ht._M_buckets);
388 std::swap(_M_num_elements, __ht._M_num_elements);
394 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
396 return iterator(_M_buckets[__n],
this);
402 {
return iterator(0,
this); }
407 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
409 return const_iterator(_M_buckets[__n],
this);
415 {
return const_iterator(0,
this); }
417 template<
class _Vl,
class _Ky,
class _HF,
class _Ex,
class _Eq,
420 operator==(
const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
421 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
426 {
return _M_buckets.size(); }
429 max_bucket_count()
const
430 {
return _Hashtable_prime_list<unsigned long>::
431 _S_get_prime_list()[(int)_S_num_primes - 1];
435 elems_in_bucket(size_type __bucket)
const
437 size_type __result = 0;
438 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
444 insert_unique(
const value_type& __obj)
446 resize(_M_num_elements + 1);
447 return insert_unique_noresize(__obj);
451 insert_equal(
const value_type& __obj)
453 resize(_M_num_elements + 1);
454 return insert_equal_noresize(__obj);
458 insert_unique_noresize(
const value_type& __obj);
461 insert_equal_noresize(
const value_type& __obj);
463 template<
class _InputIterator>
465 insert_unique(_InputIterator __f, _InputIterator __l)
468 template<
class _InputIterator>
470 insert_equal(_InputIterator __f, _InputIterator __l)
473 template<
class _InputIterator>
475 insert_unique(_InputIterator __f, _InputIterator __l,
478 for ( ; __f != __l; ++__f)
482 template<
class _InputIterator>
484 insert_equal(_InputIterator __f, _InputIterator __l,
487 for ( ; __f != __l; ++__f)
491 template<
class _ForwardIterator>
493 insert_unique(_ForwardIterator __f, _ForwardIterator __l,
497 resize(_M_num_elements + __n);
498 for ( ; __n > 0; --__n, ++__f)
499 insert_unique_noresize(*__f);
502 template<
class _ForwardIterator>
504 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
508 resize(_M_num_elements + __n);
509 for ( ; __n > 0; --__n, ++__f)
510 insert_equal_noresize(*__f);
514 find_or_insert(
const value_type& __obj);
517 find(
const key_type& __key)
519 size_type __n = _M_bkt_num_key(__key);
521 for (__first = _M_buckets[__n];
522 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
523 __first = __first->_M_next)
525 return iterator(__first,
this);
529 find(
const key_type& __key)
const
531 size_type __n = _M_bkt_num_key(__key);
532 const _Node* __first;
533 for (__first = _M_buckets[__n];
534 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
535 __first = __first->_M_next)
537 return const_iterator(__first,
this);
541 count(
const key_type& __key)
const
543 const size_type __n = _M_bkt_num_key(__key);
544 size_type __result = 0;
546 for (
const _Node* __cur = _M_buckets[__n]; __cur;
547 __cur = __cur->_M_next)
548 if (_M_equals(_M_get_key(__cur->_M_val), __key))
554 equal_range(
const key_type& __key);
557 equal_range(
const key_type& __key)
const;
560 erase(
const key_type& __key);
563 erase(
const iterator& __it);
566 erase(iterator __first, iterator __last);
569 erase(
const const_iterator& __it);
572 erase(const_iterator __first, const_iterator __last);
575 resize(size_type __num_elements_hint);
582 _M_next_size(size_type __n)
const
583 {
return __stl_next_prime(__n); }
586 _M_initialize_buckets(size_type __n)
588 const size_type __n_buckets = _M_next_size(__n);
589 _M_buckets.reserve(__n_buckets);
590 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
595 _M_bkt_num_key(
const key_type& __key)
const
596 {
return _M_bkt_num_key(__key, _M_buckets.size()); }
599 _M_bkt_num(
const value_type& __obj)
const
600 {
return _M_bkt_num_key(_M_get_key(__obj)); }
603 _M_bkt_num_key(
const key_type& __key, std::size_t __n)
const
604 {
return _M_hash(__key) % __n; }
607 _M_bkt_num(
const value_type& __obj, std::size_t __n)
const
608 {
return _M_bkt_num_key(_M_get_key(__obj), __n); }
611 _M_new_node(
const value_type& __obj)
613 _Node* __n = _M_get_node();
617 allocator_type __a = this->get_allocator();
618 _Alloc_traits::construct(__a, &__n->_M_val, __obj);
624 __throw_exception_again;
629 _M_delete_node(_Node* __n)
631 allocator_type __a = this->get_allocator();
632 _Alloc_traits::destroy(__a, &__n->_M_val);
637 _M_erase_bucket(
const size_type __n, _Node* __first, _Node* __last);
640 _M_erase_bucket(
const size_type __n, _Node* __last);
643 _M_copy_from(
const hashtable& __ht);
646 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
648 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
649 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
652 const _Node* __old = _M_cur;
653 _M_cur = _M_cur->_M_next;
656 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
657 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
658 _M_cur = _M_ht->_M_buckets[__bucket];
663 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
665 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
666 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
669 iterator __tmp = *
this;
674 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
676 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
677 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
680 const _Node* __old = _M_cur;
681 _M_cur = _M_cur->_M_next;
684 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
685 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
686 _M_cur = _M_ht->_M_buckets[__bucket];
691 template<
class _Val,
class _Key,
class _HF,
class _ExK,
class _EqK,
693 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
694 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
697 const_iterator __tmp = *
this;
702 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
704 operator==(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
705 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
707 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
709 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
712 for (std::size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
714 _Node* __cur1 = __ht1._M_buckets[__n];
715 _Node* __cur2 = __ht2._M_buckets[__n];
717 for (; __cur1 && __cur2;
718 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
720 if (__cur1 || __cur2)
723 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
724 __cur1 = __cur1->_M_next)
726 bool _found__cur1 =
false;
727 for (__cur2 = __ht2._M_buckets[__n];
728 __cur2; __cur2 = __cur2->_M_next)
730 if (__cur1->_M_val == __cur2->_M_val)
743 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
745 operator!=(
const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
746 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
747 {
return !(__ht1 == __ht2); }
749 template<
class _Val,
class _Key,
class _HF,
class _Extract,
class _EqKey,
752 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
753 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
754 { __ht1.swap(__ht2); }
756 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
759 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
760 insert_unique_noresize(
const value_type& __obj)
762 const size_type __n = _M_bkt_num(__obj);
763 _Node* __first = _M_buckets[__n];
765 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
766 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
769 _Node* __tmp = _M_new_node(__obj);
770 __tmp->_M_next = __first;
771 _M_buckets[__n] = __tmp;
776 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
777 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
778 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
779 insert_equal_noresize(
const value_type& __obj)
781 const size_type __n = _M_bkt_num(__obj);
782 _Node* __first = _M_buckets[__n];
784 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
785 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
787 _Node* __tmp = _M_new_node(__obj);
788 __tmp->_M_next = __cur->_M_next;
789 __cur->_M_next = __tmp;
791 return iterator(__tmp,
this);
794 _Node* __tmp = _M_new_node(__obj);
795 __tmp->_M_next = __first;
796 _M_buckets[__n] = __tmp;
798 return iterator(__tmp,
this);
801 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
802 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
803 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
804 find_or_insert(
const value_type& __obj)
806 resize(_M_num_elements + 1);
808 size_type __n = _M_bkt_num(__obj);
809 _Node* __first = _M_buckets[__n];
811 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
812 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
813 return __cur->_M_val;
815 _Node* __tmp = _M_new_node(__obj);
816 __tmp->_M_next = __first;
817 _M_buckets[__n] = __tmp;
819 return __tmp->_M_val;
822 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
824 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
825 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
826 equal_range(
const key_type& __key)
829 const size_type __n = _M_bkt_num_key(__key);
831 for (_Node* __first = _M_buckets[__n]; __first;
832 __first = __first->_M_next)
833 if (_M_equals(_M_get_key(__first->_M_val), __key))
835 for (_Node* __cur = __first->_M_next; __cur;
836 __cur = __cur->_M_next)
837 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
838 return _Pii(iterator(__first,
this), iterator(__cur,
this));
839 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
841 return _Pii(iterator(__first,
this),
842 iterator(_M_buckets[__m],
this));
843 return _Pii(iterator(__first,
this), end());
845 return _Pii(end(), end());
848 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
850 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
851 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
852 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
853 equal_range(
const key_type& __key)
const
856 const size_type __n = _M_bkt_num_key(__key);
858 for (
const _Node* __first = _M_buckets[__n]; __first;
859 __first = __first->_M_next)
861 if (_M_equals(_M_get_key(__first->_M_val), __key))
863 for (
const _Node* __cur = __first->_M_next; __cur;
864 __cur = __cur->_M_next)
865 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
866 return _Pii(const_iterator(__first,
this),
867 const_iterator(__cur,
this));
868 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
870 return _Pii(const_iterator(__first,
this),
871 const_iterator(_M_buckets[__m],
this));
872 return _Pii(const_iterator(__first,
this), end());
875 return _Pii(end(), end());
878 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
879 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
880 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
881 erase(
const key_type& __key)
883 const size_type __n = _M_bkt_num_key(__key);
884 _Node* __first = _M_buckets[__n];
885 _Node* __saved_slot = 0;
886 size_type __erased = 0;
890 _Node* __cur = __first;
891 _Node* __next = __cur->_M_next;
894 if (_M_equals(_M_get_key(__next->_M_val), __key))
896 if (&_M_get_key(__next->_M_val) != &__key)
898 __cur->_M_next = __next->_M_next;
899 _M_delete_node(__next);
900 __next = __cur->_M_next;
906 __saved_slot = __cur;
908 __next = __cur->_M_next;
914 __next = __cur->_M_next;
917 bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key);
920 __next = __saved_slot->_M_next;
921 __saved_slot->_M_next = __next->_M_next;
922 _M_delete_node(__next);
928 _M_buckets[__n] = __first->_M_next;
929 _M_delete_node(__first);
937 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
938 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
939 erase(
const iterator& __it)
941 _Node* __p = __it._M_cur;
944 const size_type __n = _M_bkt_num(__p->_M_val);
945 _Node* __cur = _M_buckets[__n];
949 _M_buckets[__n] = __cur->_M_next;
950 _M_delete_node(__cur);
955 _Node* __next = __cur->_M_next;
960 __cur->_M_next = __next->_M_next;
961 _M_delete_node(__next);
968 __next = __cur->_M_next;
975 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
977 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
978 erase(iterator __first, iterator __last)
980 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
983 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
986 if (__first._M_cur == __last._M_cur)
988 else if (__f_bucket == __l_bucket)
989 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
992 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
993 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
994 _M_erase_bucket(__n, 0);
995 if (__l_bucket != _M_buckets.size())
996 _M_erase_bucket(__l_bucket, __last._M_cur);
1000 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1002 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1003 erase(const_iterator __first, const_iterator __last)
1005 erase(iterator(
const_cast<_Node*
>(__first._M_cur),
1006 const_cast<hashtable*
>(__first._M_ht)),
1007 iterator(
const_cast<_Node*
>(__last._M_cur),
1008 const_cast<hashtable*
>(__last._M_ht)));
1011 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1013 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1014 erase(
const const_iterator& __it)
1015 { erase(iterator(
const_cast<_Node*
>(__it._M_cur),
1016 const_cast<hashtable*
>(__it._M_ht))); }
1018 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1020 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1021 resize(size_type __num_elements_hint)
1023 const size_type __old_n = _M_buckets.size();
1024 if (__num_elements_hint > __old_n)
1026 const size_type __n = _M_next_size(__num_elements_hint);
1029 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
1032 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
1034 _Node* __first = _M_buckets[__bucket];
1037 size_type __new_bucket = _M_bkt_num(__first->_M_val,
1039 _M_buckets[__bucket] = __first->_M_next;
1040 __first->_M_next = __tmp[__new_bucket];
1041 __tmp[__new_bucket] = __first;
1042 __first = _M_buckets[__bucket];
1045 _M_buckets.swap(__tmp);
1049 for (size_type __bucket = 0; __bucket < __tmp.size();
1052 while (__tmp[__bucket])
1054 _Node* __next = __tmp[__bucket]->_M_next;
1055 _M_delete_node(__tmp[__bucket]);
1056 __tmp[__bucket] = __next;
1059 __throw_exception_again;
1065 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1067 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1068 _M_erase_bucket(
const size_type __n, _Node* __first, _Node* __last)
1070 _Node* __cur = _M_buckets[__n];
1071 if (__cur == __first)
1072 _M_erase_bucket(__n, __last);
1076 for (__next = __cur->_M_next;
1078 __cur = __next, __next = __cur->_M_next)
1080 while (__next != __last)
1082 __cur->_M_next = __next->_M_next;
1083 _M_delete_node(__next);
1084 __next = __cur->_M_next;
1090 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1092 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1093 _M_erase_bucket(
const size_type __n, _Node* __last)
1095 _Node* __cur = _M_buckets[__n];
1096 while (__cur != __last)
1098 _Node* __next = __cur->_M_next;
1099 _M_delete_node(__cur);
1101 _M_buckets[__n] = __cur;
1106 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1108 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1111 if (_M_num_elements == 0)
1114 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
1116 _Node* __cur = _M_buckets[__i];
1119 _Node* __next = __cur->_M_next;
1120 _M_delete_node(__cur);
1123 _M_buckets[__i] = 0;
1125 _M_num_elements = 0;
1128 template<
class _Val,
class _Key,
class _HF,
class _Ex,
class _Eq,
class _All>
1130 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
1131 _M_copy_from(
const hashtable& __ht)
1134 _M_buckets.reserve(__ht._M_buckets.size());
1135 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1138 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1139 const _Node* __cur = __ht._M_buckets[__i];
1142 _Node* __local_copy = _M_new_node(__cur->_M_val);
1143 _M_buckets[__i] = __local_copy;
1145 for (_Node* __next = __cur->_M_next;
1147 __cur = __next, __next = __cur->_M_next)
1149 __local_copy->_M_next = _M_new_node(__next->_M_val);
1150 __local_copy = __local_copy->_M_next;
1154 _M_num_elements = __ht._M_num_elements;
1159 __throw_exception_again;
1163 _GLIBCXX_END_NAMESPACE_VERSION
constexpr complex< _Tp > operator*(const complex< _Tp > &__x, const complex< _Tp > &__y)
Return new complex value x times y.
void swap(any &__x, any &__y) noexcept
Exchange the states of two any objects.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
constexpr iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
GNU extensions for public use.
The standard allocator, as per C++03 [20.4.1].
Struct holding two objects of arbitrary type.
Forward iterators support a superset of input iterator operations.
Uniform interface to C++98 and C++11 allocators.