NCBI C++ ToolKit
_hashtable.h
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /*
2  *
3  * Copyright (c) 1994
4  * Hewlett-Packard Company
5  *
6  * Copyright (c) 1996,1997
7  * Silicon Graphics Computer Systems, Inc.
8  *
9  * Copyright (c) 1997
10  * Moscow Center for SPARC Technology
11  *
12  * Copyright (c) 1999
13  * Boris Fomitchev
14  *
15  * This material is provided "as is", with absolutely no warranty expressed
16  * or implied. Any use is at your own risk.
17  *
18  * Permission to use or copy this software for any purpose is hereby granted
19  * without fee, provided the above notices are retained on all copies.
20  * Permission to modify the code and to distribute modified code is granted,
21  * provided the above notices are retained, and a notice that the code was
22  * modified is included with the above copyright notice.
23  *
24  */
25 
26 /* NOTE: File was modified to fix include paths
27  */
28 
29 /* NOTE: This is an internal header file, included by other STL headers.
30  * You should not attempt to use it directly.
31  */
32 
33 #ifndef _STLP_INTERNAL_HASHTABLE_H
34 #define _STLP_INTERNAL_HASHTABLE_H
35 
36 # ifndef _STLP_INTERNAL_VECTOR_H
37 # include <stl/_vector.h>
38 # endif
39 
40 # ifndef _STLP_INTERNAL_ITERATOR_H
41 # include <stl/_iterator.h>
42 # endif
43 
44 # ifndef _STLP_INTERNAL_FUNCTION_H
45 # include <stl/_function_base.h>
46 # endif
47 
48 # ifndef _STLP_INTERNAL_ALGOBASE_H
49 # include <stl/_algobase.h>
50 # endif
51 
52 # ifndef _STLP_HASH_FUN_H
53 # include <stl/_hash_fun.h>
54 # endif
55 
56 // Hashtable class, used to implement the hashed associative containers
57 // hash_set, hash_map, hash_multiset, and hash_multimap.
58 
59 #ifdef _STLP_DEBUG
60 # define hashtable __WORKAROUND_DBG_RENAME(hashtable)
61 #endif
62 
64 
65 template <class _Val>
67 {
70  _Val _M_val;
72 };
73 
74 // some compilers require the names of template parameters to be the same
75 template <class _Val, class _Key, class _HF,
76  class _ExK, class _EqK, class _All>
77 class hashtable;
78 
79 template <class _Val, class _Key, class _HF,
80  class _ExK, class _EqK, class _All>
82 {
86 
89 
91  : _M_cur(__n), _M_ht(__tab) {}
93 
95 };
96 
97 
98 template <class _Val, class _Traits, class _Key, class _HF,
99  class _ExK, class _EqK, class _All>
100 struct _Ht_iterator : public _Hashtable_iterator< _Val, _Key,_HF, _ExK,_EqK,_All>
101 {
102 
104 
105  // typedef _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> iterator;
106  // typedef _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> const_iterator;
108 
111 
112  typedef _Val value_type;
113  typedef forward_iterator_tag iterator_category;
114  typedef ptrdiff_t difference_type;
115  typedef size_t size_type;
116  typedef typename _Traits::reference reference;
117  typedef typename _Traits::pointer pointer;
118 
119  _Ht_iterator(const _Node* __n, const _Hashtable* __tab) :
120  _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>((_Node*)__n, (_Hashtable*)__tab) {}
122  _Ht_iterator(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __it) :
123  _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>(__it) {}
124 
125  reference operator*() const {
126  return this->_M_cur->_M_val;
127  }
129 
130  _Self& operator++() {
131  _Node* __n = this->_M_cur->_M_next;
132  this->_M_cur = (__n !=0 ? __n : this->_M_skip_to_next());
133  return *this;
134  }
135  inline _Self operator++(int) {
136  _Self __tmp = *this;
137  ++*this;
138  return __tmp;
139  }
140 };
141 
142 template <class _Val, class _Traits, class _Traits1, class _Key, class _HF,
143  class _ExK, class _EqK, class _All>
144 inline bool
147  return __x._M_cur == __y._M_cur;
148 }
149 
150 #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
151 template <class _Val, class _Key, class _HF,
152  class _ExK, class _EqK, class _All>
153 inline bool
156  return __x._M_cur != __y._M_cur;
157 }
158 #else
159 
160 # if (defined (__GNUC__) && (__GNUC_MINOR__ < 8))
161 template <class _Val, class _Key, class _HF,
162  class _ExK, class _EqK, class _All>
163 inline bool
164 operator!=(const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x,
165  const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) {
166  return __x._M_cur != __y._M_cur;
167 }
168 # endif
169 
170 template <class _Val, class _Key, class _HF,
171  class _ExK, class _EqK, class _All>
172 inline bool
173 operator!=(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x,
174  const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) {
175  return __x._M_cur != __y._M_cur;
176 }
177 #endif
178 
179 # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
180 template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
181 inline _Val* value_type(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (_Val*) 0; }
182 template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
183 inline forward_iterator_tag iterator_category(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return forward_iterator_tag(); }
184 template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
185 inline ptrdiff_t* distance_type(const _Ht_iterator<_Val,_Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (ptrdiff_t*) 0; }
186 #endif
187 
188 #define __stl_num_primes 28
189 template <class _Tp>
190 class _Stl_prime {
191 public:
192  static const size_t _M_list[__stl_num_primes];
193 };
194 
195 # if defined (_STLP_USE_TEMPLATE_EXPORT)
196 _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
197 # endif
198 
200 
201 
202 // Hashtables handle allocators a bit differently than other containers
203 // do. If we're using standard-conforming allocators, then a hashtable
204 // unconditionally has a member variable to hold its allocator, even if
205 // it so happens that all instances of the allocator type are identical.
206 // This is because, for hashtables, this extra storage is negligible.
207 // Additionally, a base class wouldn't serve any other purposes; it
208 // wouldn't, for example, simplify the exception-handling code.
209 template <class _Val, class _Key, class _HF,
210  class _ExK, class _EqK, class _All>
211 class hashtable {
213 public:
214  typedef _Key key_type;
215  typedef _Val value_type;
216  typedef _HF hasher;
217  typedef _EqK key_equal;
218 
219  typedef size_t size_type;
220  typedef ptrdiff_t difference_type;
221  typedef value_type* pointer;
222  typedef const value_type* const_pointer;
224  typedef const value_type& const_reference;
225  typedef forward_iterator_tag _Iterator_category;
226 
227  hasher hash_funct() const { return _M_hash; }
228  key_equal key_eq() const { return _M_equals; }
229 
230 private:
232 
233 private:
234  _STLP_FORCE_ALLOCATORS(_Val, _All)
238 public:
239  typedef typename _Alloc_traits<_Val,_All>::allocator_type allocator_type;
242  }
243 private:
249  const _Node* _M_get_bucket(size_t __n) const { return (_Node*)_M_buckets[__n]; }
250 
251 public:
256  friend struct _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>;
257  friend struct _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>;
258  friend struct _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK, _All>;
259 
260 public:
262  const _HF& __hf,
263  const _EqK& __eql,
264  const _ExK& __ext,
265  const allocator_type& __a = allocator_type())
266  :
267  _M_hash(__hf),
268  _M_equals(__eql),
269  _M_get_key(__ext),
272  {
274  }
275 
277  const _HF& __hf,
278  const _EqK& __eql,
279  const allocator_type& __a = allocator_type())
280  :
281  _M_hash(__hf),
282  _M_equals(__eql),
283  _M_get_key(_ExK()),
286  {
288  }
289 
290  hashtable(const _Self& __ht)
291  :
292  _M_hash(__ht._M_hash),
293  _M_equals(__ht._M_equals),
294  _M_get_key(__ht._M_get_key),
297  {
298  _M_copy_from(__ht);
299  }
300 
301  _Self& operator= (const _Self& __ht)
302  {
303  if (&__ht != this) {
304  clear();
305  _M_hash = __ht._M_hash;
306  _M_equals = __ht._M_equals;
307  _M_get_key = __ht._M_get_key;
308  _M_copy_from(__ht);
309  }
310  return *this;
311  }
312 
313  ~hashtable() { clear(); }
314 
315  size_type size() const { return _M_num_elements._M_data; }
316  size_type max_size() const { return size_type(-1); }
317  bool empty() const { return size() == 0; }
318 
319  void swap(_Self& __ht)
320  {
324  _M_buckets.swap(__ht._M_buckets);
326  }
327 
329  {
330  for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
331  if (_M_buckets[__n])
332  return iterator((_Node*)_M_buckets[__n], this);
333  return end();
334  }
335 
336  iterator end() { return iterator((_Node*)0, this); }
337 
339  {
340  for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
341  if (_M_buckets[__n])
342  return const_iterator((_Node*)_M_buckets[__n], this);
343  return end();
344  }
345 
346  const_iterator end() const { return const_iterator((_Node*)0, this); }
347 
350 
351 public:
352 
353  size_type bucket_count() const { return _M_buckets.size(); }
354 
357 
359  {
360  size_type __result = 0;
361  for (_Node* __cur = (_Node*)_M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
362  __result += 1;
363  return __result;
364  }
365 
366  pair<iterator, bool> insert_unique(const value_type& __obj)
367  {
368  resize(_M_num_elements._M_data + 1);
369  return insert_unique_noresize(__obj);
370  }
371 
373  {
374  resize(_M_num_elements._M_data + 1);
375  return insert_equal_noresize(__obj);
376  }
377 
378  pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
380 
381 #ifdef _STLP_MEMBER_TEMPLATES
382  template <class _InputIterator>
383  void insert_unique(_InputIterator __f, _InputIterator __l)
384  {
385  insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator));
386  }
387 
388  template <class _InputIterator>
389  void insert_equal(_InputIterator __f, _InputIterator __l)
390  {
391  insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator));
392  }
393 
394  template <class _InputIterator>
395  void insert_unique(_InputIterator __f, _InputIterator __l,
396  const input_iterator_tag &)
397  {
398  for ( ; __f != __l; ++__f)
399  insert_unique(*__f);
400  }
401 
402  template <class _InputIterator>
403  void insert_equal(_InputIterator __f, _InputIterator __l,
404  const input_iterator_tag &)
405  {
406  for ( ; __f != __l; ++__f)
407  insert_equal(*__f);
408  }
409 
410  template <class _ForwardIterator>
411  void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
412  const forward_iterator_tag &)
413  {
414  size_type __n = distance(__f, __l);
415  resize(_M_num_elements._M_data + __n);
416  for ( ; __n > 0; --__n, ++__f)
418  }
419 
420  template <class _ForwardIterator>
421  void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
422  const forward_iterator_tag &)
423  {
424  size_type __n = distance(__f, __l);
425  resize(_M_num_elements._M_data + __n);
426  for ( ; __n > 0; --__n, ++__f)
427  insert_equal_noresize(*__f);
428  }
429 
430 #else /* _STLP_MEMBER_TEMPLATES */
431  void insert_unique(const value_type* __f, const value_type* __l)
432  {
433  size_type __n = __l - __f;
434  resize(_M_num_elements._M_data + __n);
435  for ( ; __n > 0; --__n, ++__f)
437  }
438 
439  void insert_equal(const value_type* __f, const value_type* __l)
440  {
441  size_type __n = __l - __f;
442  resize(_M_num_elements._M_data + __n);
443  for ( ; __n > 0; --__n, ++__f)
444  insert_equal_noresize(*__f);
445  }
446 
448  {
449  size_type __n = distance(__f, __l);
450  resize(_M_num_elements._M_data + __n);
451  for ( ; __n > 0; --__n, ++__f)
453  }
454 
456  {
457  size_type __n = distance(__f, __l);
458  resize(_M_num_elements._M_data + __n);
459  for ( ; __n > 0; --__n, ++__f)
460  insert_equal_noresize(*__f);
461  }
462 #endif /*_STLP_MEMBER_TEMPLATES */
463 
464  reference find_or_insert(const value_type& __obj);
465 
466 private:
467 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC_)))
468  template <class _KT>
469  _Node* _M_find(const _KT& __key) const
470 # else
471  _Node* _M_find(const key_type& __key) const
472 # endif
473  {
474  size_type __n = _M_hash(__key)% _M_buckets.size();
475  _Node* __first;
476  for ( __first = (_Node*)_M_buckets[__n];
477  __first && !_M_equals(_M_get_key(__first->_M_val), __key);
478  __first = __first->_M_next)
479  {}
480  return __first;
481  }
482 
483 public:
484 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__)))
485  template <class _KT>
486  iterator find(const _KT& __key)
487 # else
488  iterator find(const key_type& __key)
489 # endif
490  {
491  return iterator(_M_find(__key), this);
492  }
493 
494 # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__)))
495  template <class _KT>
496  const_iterator find(const _KT& __key) const
497 # else
498  const_iterator find(const key_type& __key) const
499 # endif
500  {
501  return const_iterator(_M_find(__key), this);
502  }
503 
504  size_type count(const key_type& __key) const
505  {
506  const size_type __n = _M_bkt_num_key(__key);
507  size_type __result = 0;
508 
509  for (const _Node* __cur = (_Node*)_M_buckets[__n]; __cur; __cur = __cur->_M_next)
510  if (_M_equals(_M_get_key(__cur->_M_val), __key))
511  ++__result;
512  return __result;
513  }
514 
515  pair<iterator, iterator>
516  equal_range(const key_type& __key);
517 
518  pair<const_iterator, const_iterator>
519  equal_range(const key_type& __key) const;
520 
521  size_type erase(const key_type& __key);
522  // void erase(const iterator& __it); `
523  void erase(const const_iterator& __it) ;
524 
525  // void erase(const const_iterator& __first, const const_iterator __last) {
526  // erase((const iterator&)__first, (const iterator&)__last);
527  // }
528  void erase(const_iterator __first, const_iterator __last);
529  void resize(size_type __num_elements_hint);
530  void clear();
531 
532 public:
533  // this is for hash_map::operator[]
534  reference _M_insert(const value_type& __obj);
535 
536 private:
537 
538  size_type _M_next_size(size_type __n) const;
539 
541  {
542  const size_type __n_buckets = _M_next_size(__n);
543  _M_buckets.reserve(__n_buckets);
544  _M_buckets.insert(_M_buckets.end(), __n_buckets, (void*) 0);
545  _M_num_elements._M_data = 0;
546  }
547 
548  size_type _M_bkt_num_key(const key_type& __key) const
549  {
550  return _M_bkt_num_key(__key, _M_buckets.size());
551  }
552 
553  size_type _M_bkt_num(const value_type& __obj) const
554  {
555  return _M_bkt_num_key(_M_get_key(__obj));
556  }
557 
558  size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
559  {
560  return _M_hash(__key) % __n;
561  }
562 
563  size_type _M_bkt_num(const value_type& __obj, size_t __n) const
564  {
565  return _M_bkt_num_key(_M_get_key(__obj), __n);
566  }
567 
568  _Node* _M_new_node(const value_type& __obj)
569  {
570  _Node* __n = _M_num_elements.allocate(1);
571  __n->_M_next = 0;
572  _STLP_TRY {
573  _Construct(&__n->_M_val, __obj);
574  // return __n;
575  }
576  _STLP_UNWIND(_M_num_elements.deallocate(__n, 1));
577  return __n;
578  }
579 
581  {
582  _STLP_STD::_Destroy(&__n->_M_val);
583  _M_num_elements.deallocate(__n, 1);
584  }
585 
586  void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
587  void _M_erase_bucket(const size_type __n, _Node* __last);
588 
589  void _M_copy_from(const _Self& __ht);
590 };
591 
592 #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
593 #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
594 // MODIFIED - fixed path
596 #undef _STLP_TEMPLATE_CONTAINER
597 #undef _STLP_TEMPLATE_HEADER
598 
600 
601 # undef hashtable
602 
603 # if !defined (_STLP_LINK_TIME_INSTANTIATION)
604 # include <stl/_hashtable.c>
605 # endif
606 
607 # if defined (_STLP_DEBUG)
608 # include <stl/debug/_hashtable.h>
609 # endif
610 
611 #endif /* _STLP_INTERNAL_HASHTABLE_H */
612 
613 // Local Variables:
614 // mode:C++
615 // End:
616 
617 
bool operator==(const _Ht_iterator< _Val, _Traits, _Key, _HF, _ExK, _EqK, _All > &__x, const _Ht_iterator< _Val, _Traits1, _Key, _HF, _ExK, _EqK, _All > &__y)
Definition: _hashtable.h:145
#define __stl_num_primes
Definition: _hashtable.h:188
_Stl_prime< bool > _Stl_prime_type
Definition: _hashtable.h:199
bool operator!=(const _Ht_iterator< _Val, _Nonconst_traits< _Val >, _Key, _HF, _ExK, _EqK, _All > &__x, const _Ht_iterator< _Val, _Const_traits< _Val >, _Key, _HF, _ExK, _EqK, _All > &__y)
Definition: _hashtable.h:173
static const size_t _M_list[28]
Definition: _hashtable.h:192
__vector__< void *, _M_node_ptr_allocator_type > _BucketVector
Definition: _hashtable.h:237
_Val value_type
Definition: _hashtable.h:215
void insert_unique(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:447
iterator insert_equal(const value_type &__obj)
Definition: _hashtable.h:372
void resize(size_type __num_elements_hint)
Definition: _hashtable.c:335
hasher _M_hash
Definition: _hashtable.h:244
_Node * _M_new_node(const value_type &__obj)
Definition: _hashtable.h:568
_Self & operator=(const _Self &__ht)
Definition: _hashtable.h:301
const_iterator end() const
Definition: _hashtable.h:346
size_type max_size() const
Definition: _hashtable.h:316
hashtable(const _Self &__ht)
Definition: _hashtable.h:290
void _M_delete_node(_Node *__n)
Definition: _hashtable.h:580
key_equal _M_equals
Definition: _hashtable.h:245
size_type _M_bkt_num_key(const key_type &__key) const
Definition: _hashtable.h:548
const_iterator find(const key_type &__key) const
Definition: _hashtable.h:498
void insert_equal(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:439
size_type max_bucket_count() const
Definition: _hashtable.h:355
_Alloc_traits< void *, _All >::allocator_type _M_node_ptr_allocator_type
Definition: _hashtable.h:236
allocator_type get_allocator() const
Definition: _hashtable.h:240
value_type * pointer
Definition: _hashtable.h:221
hashtable(size_type __n, const _HF &__hf, const _EqK &__eql, const allocator_type &__a=allocator_type())
Definition: _hashtable.h:276
iterator insert_equal_noresize(const value_type &__obj)
Definition: _hashtable.c:144
void swap(_Self &__ht)
Definition: _hashtable.h:319
ptrdiff_t difference_type
Definition: _hashtable.h:220
size_type _M_next_size(size_type __n) const
Definition: _hashtable.c:94
_STLP_alloc_proxy< size_type, _Node, _M_node_allocator_type > _M_num_elements
Definition: _hashtable.h:248
hashtable< _Val, _Key, _HF, _ExK, _EqK, _All > _Self
Definition: _hashtable.h:212
pair< iterator, bool > insert_unique_noresize(const value_type &__obj)
Definition: _hashtable.c:125
size_type _M_bkt_num(const value_type &__obj) const
Definition: _hashtable.h:553
bool empty() const
Definition: _hashtable.h:317
_Const_traits< _Val > __const_val_traits
Definition: _hashtable.h:252
_BucketVector _M_buckets
Definition: _hashtable.h:247
void _M_initialize_buckets(size_type __n)
Definition: _hashtable.h:540
_Node * _M_find(const key_type &__key) const
Definition: _hashtable.h:471
iterator begin()
Definition: _hashtable.h:328
hashtable(size_type __n, const _HF &__hf, const _EqK &__eql, const _ExK &__ext, const allocator_type &__a=allocator_type())
Definition: _hashtable.h:261
_Nonconst_traits< _Val > __nonconst_val_traits
Definition: _hashtable.h:253
forward_iterator_tag _Iterator_category
Definition: _hashtable.h:225
size_type size() const
Definition: _hashtable.h:315
const_iterator begin() const
Definition: _hashtable.h:338
size_type count(const key_type &__key) const
Definition: _hashtable.h:504
void _M_erase_bucket(const size_type __n, _Node *__first, _Node *__last)
Definition: _hashtable.c:374
_HF hasher
Definition: _hashtable.h:216
void clear()
Definition: _hashtable.c:409
void _M_copy_from(const _Self &__ht)
Definition: _hashtable.c:426
const _Node * _M_get_bucket(size_t __n) const
Definition: _hashtable.h:249
_Ht_iterator< _Val, __const_val_traits, _Key, _HF, _ExK, _EqK, _All > const_iterator
Definition: _hashtable.h:254
iterator find(const key_type &__key)
Definition: _hashtable.h:488
reference _M_insert(const value_type &__obj)
Definition: _hashtable.c:167
value_type & reference
Definition: _hashtable.h:223
size_type _M_bkt_num_key(const key_type &__key, size_t __n) const
Definition: _hashtable.h:558
void insert_unique(const value_type *__f, const value_type *__l)
Definition: _hashtable.h:431
size_type bucket_count() const
Definition: _hashtable.h:353
_ExK _M_get_key
Definition: _hashtable.h:246
pair< iterator, iterator > equal_range(const key_type &__key)
Definition: _hashtable.c:196
_EqK key_equal
Definition: _hashtable.h:217
const value_type & const_reference
Definition: _hashtable.h:224
reference find_or_insert(const value_type &__obj)
Definition: _hashtable.c:183
_Key key_type
Definition: _hashtable.h:214
iterator end()
Definition: _hashtable.h:336
const value_type * const_pointer
Definition: _hashtable.h:222
key_equal key_eq() const
Definition: _hashtable.h:228
_Alloc_traits< _Node, _All >::allocator_type _M_node_allocator_type
Definition: _hashtable.h:235
static bool _STLP_CALL _M_equal(const hashtable< _Val, _Key, _HF, _ExK, _EqK, _All > &, const hashtable< _Val, _Key, _HF, _ExK, _EqK, _All > &)
Definition: _hashtable.c:103
hasher hash_funct() const
Definition: _hashtable.h:227
pair< iterator, bool > insert_unique(const value_type &__obj)
Definition: _hashtable.h:366
size_type erase(const key_type &__key)
Definition: _hashtable.c:246
_Hashtable_node< _Val > _Node
Definition: _hashtable.h:231
size_type elems_in_bucket(size_type __bucket) const
Definition: _hashtable.h:358
size_t size_type
Definition: _hashtable.h:219
_Ht_iterator< _Val, __nonconst_val_traits, _Key, _HF, _ExK, _EqK, _All > iterator
Definition: _hashtable.h:255
_Alloc_traits< _Val, _All >::allocator_type allocator_type
Definition: _hashtable.h:239
void insert_equal(const_iterator __f, const_iterator __l)
Definition: _hashtable.h:455
size_type _M_bkt_num(const value_type &__obj, size_t __n) const
Definition: _hashtable.h:563
void swap(NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair1, NCBI_NS_NCBI::pair_base_member< T1, T2 > &pair2)
Definition: ncbimisc.hpp:1508
unsigned int
A callback function used to compare two keys in a database.
Definition: types.hpp:1210
double value_type
The numeric datatype used by the parser.
Definition: muParserDef.h:228
const GenericPointer< typename T::ValueType > & pointer
Definition: pointer.h:1126
#define _STLP_UNWIND(action)
Definition: stlp_defs.hpp:134
#define _STLP_CONVERT_ALLOCATOR(__a, _Tp)
Definition: stlp_defs.hpp:130
#define __vector__
Definition: stlp_defs.hpp:128
#define _STLP_FORCE_ALLOCATORS(a, y)
Definition: stlp_defs.hpp:129
#define __TRIVIAL_STUFF(__type)
Definition: stlp_defs.hpp:139
#define _STLP_TRY
Definition: stlp_defs.hpp:133
#define _STLP_CALL
Definition: stlp_defs.hpp:119
#define _STLP_DEFINE_ARROW_OPERATOR
Definition: stlp_defs.hpp:143
#define _STLP_BEGIN_NAMESPACE
Definition: stlp_defs.hpp:116
#define _STLP_END_NAMESPACE
Definition: stlp_defs.hpp:117
_Node * _M_skip_to_next()
Definition: _hashtable.c:80
_Hashtable_node< _Val > _Node
Definition: _hashtable.h:85
hashtable< _Val, _Key, _HF, _ExK, _EqK, _All > _Hashtable
Definition: _hashtable.h:84
_Hashtable * _M_ht
Definition: _hashtable.h:88
_Hashtable_iterator(_Node *__n, _Hashtable *__tab)
Definition: _hashtable.h:90
_Self * _M_next
Definition: _hashtable.h:69
_Hashtable_node< _Val > _Self
Definition: _hashtable.h:68
hashtable< _Val, _Key, _HF, _ExK, _EqK, _All > _Hashtable
Definition: _hashtable.h:109
_Self operator++(int)
Definition: _hashtable.h:135
_Hashtable_iterator< _Val, _Key, _HF, _ExK, _EqK, _All > _Base
Definition: _hashtable.h:103
size_t size_type
Definition: _hashtable.h:115
_Hashtable_node< _Val > _Node
Definition: _hashtable.h:110
reference operator*() const
Definition: _hashtable.h:125
_STLP_DEFINE_ARROW_OPERATOR _Self & operator++()
Definition: _hashtable.h:130
_Traits::pointer pointer
Definition: _hashtable.h:117
_Ht_iterator(const _Node *__n, const _Hashtable *__tab)
Definition: _hashtable.h:119
_Ht_iterator(const _Ht_iterator< _Val, _Nonconst_traits< _Val >, _Key, _HF, _ExK, _EqK, _All > &__it)
Definition: _hashtable.h:122
_Val value_type
Definition: _hashtable.h:112
forward_iterator_tag iterator_category
Definition: _hashtable.h:113
_Traits::reference reference
Definition: _hashtable.h:116
ptrdiff_t difference_type
Definition: _hashtable.h:114
_Ht_iterator< _Val, _Traits, _Key, _HF, _ExK, _EqK, _All > _Self
Definition: _hashtable.h:107
#define const
Definition: zconf.h:232
Modified on Mon Apr 22 04:03:47 2024 by modify_doxy.py rev. 669887