libstdc++
hash_map
Go to the documentation of this file.
1 // Hashing map implementation -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2004, 2005, 2006, 2009, 2010
4 // Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  * Copyright (c) 1996
28  * Silicon Graphics Computer Systems, Inc.
29  *
30  * Permission to use, copy, modify, distribute and sell this software
31  * and its documentation for any purpose is hereby granted without fee,
32  * provided that the above copyright notice appear in all copies and
33  * that both that copyright notice and this permission notice appear
34  * in supporting documentation. Silicon Graphics makes no
35  * representations about the suitability of this software for any
36  * purpose. It is provided "as is" without express or implied warranty.
37  *
38  *
39  * Copyright (c) 1994
40  * Hewlett-Packard Company
41  *
42  * Permission to use, copy, modify, distribute and sell this software
43  * and its documentation for any purpose is hereby granted without fee,
44  * provided that the above copyright notice appear in all copies and
45  * that both that copyright notice and this permission notice appear
46  * in supporting documentation. Hewlett-Packard Company makes no
47  * representations about the suitability of this software for any
48  * purpose. It is provided "as is" without express or implied warranty.
49  *
50  */
51 
52 /** @file backward/hash_map
53  * This file is a GNU extension to the Standard C++ Library (possibly
54  * containing extensions from the HP/SGI STL subset).
55  */
56 
57 #ifndef _BACKWARD_HASH_MAP
58 #define _BACKWARD_HASH_MAP 1
59 
60 #ifndef _GLIBCXX_PERMIT_BACKWARD_HASH
61 #include "backward_warning.h"
62 #endif
63 
64 #include <bits/c++config.h>
65 #include <backward/hashtable.h>
66 #include <bits/concept_check.h>
67 
68 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
69 {
70 _GLIBCXX_BEGIN_NAMESPACE_VERSION
71 
72  using std::equal_to;
73  using std::allocator;
74  using std::pair;
75  using std::_Select1st;
76 
77  /**
78  * This is an SGI extension.
79  * @ingroup SGIextensions
80  * @doctodo
81  */
82  template<class _Key, class _Tp, class _HashFn = hash<_Key>,
83  class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
84  class hash_map
85  {
86  private:
87  typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
88  _Select1st<pair<const _Key, _Tp> >,
89  _EqualKey, _Alloc> _Ht;
90 
91  _Ht _M_ht;
92 
93  public:
94  typedef typename _Ht::key_type key_type;
95  typedef _Tp data_type;
96  typedef _Tp mapped_type;
97  typedef typename _Ht::value_type value_type;
98  typedef typename _Ht::hasher hasher;
99  typedef typename _Ht::key_equal key_equal;
100 
101  typedef typename _Ht::size_type size_type;
102  typedef typename _Ht::difference_type difference_type;
103  typedef typename _Ht::pointer pointer;
104  typedef typename _Ht::const_pointer const_pointer;
105  typedef typename _Ht::reference reference;
106  typedef typename _Ht::const_reference const_reference;
107 
108  typedef typename _Ht::iterator iterator;
109  typedef typename _Ht::const_iterator const_iterator;
110 
111  typedef typename _Ht::allocator_type allocator_type;
112 
113  hasher
114  hash_funct() const
115  { return _M_ht.hash_funct(); }
116 
117  key_equal
118  key_eq() const
119  { return _M_ht.key_eq(); }
120 
121  allocator_type
122  get_allocator() const
123  { return _M_ht.get_allocator(); }
124 
125  hash_map()
126  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
127 
128  explicit
129  hash_map(size_type __n)
130  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
131 
132  hash_map(size_type __n, const hasher& __hf)
133  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
134 
135  hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
136  const allocator_type& __a = allocator_type())
137  : _M_ht(__n, __hf, __eql, __a) {}
138 
139  template<class _InputIterator>
140  hash_map(_InputIterator __f, _InputIterator __l)
141  : _M_ht(100, hasher(), key_equal(), allocator_type())
142  { _M_ht.insert_unique(__f, __l); }
143 
144  template<class _InputIterator>
145  hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
146  : _M_ht(__n, hasher(), key_equal(), allocator_type())
147  { _M_ht.insert_unique(__f, __l); }
148 
149  template<class _InputIterator>
150  hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
151  const hasher& __hf)
152  : _M_ht(__n, __hf, key_equal(), allocator_type())
153  { _M_ht.insert_unique(__f, __l); }
154 
155  template<class _InputIterator>
156  hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
157  const hasher& __hf, const key_equal& __eql,
158  const allocator_type& __a = allocator_type())
159  : _M_ht(__n, __hf, __eql, __a)
160  { _M_ht.insert_unique(__f, __l); }
161 
162  size_type
163  size() const
164  { return _M_ht.size(); }
165 
166  size_type
167  max_size() const
168  { return _M_ht.max_size(); }
169 
170  bool
171  empty() const
172  { return _M_ht.empty(); }
173 
174  void
175  swap(hash_map& __hs)
176  { _M_ht.swap(__hs._M_ht); }
177 
178  template<class _K1, class _T1, class _HF, class _EqK, class _Al>
179  friend bool
180  operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
181  const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
182 
183  iterator
184  begin()
185  { return _M_ht.begin(); }
186 
187  iterator
188  end()
189  { return _M_ht.end(); }
190 
191  const_iterator
192  begin() const
193  { return _M_ht.begin(); }
194 
195  const_iterator
196  end() const
197  { return _M_ht.end(); }
198 
199  pair<iterator, bool>
200  insert(const value_type& __obj)
201  { return _M_ht.insert_unique(__obj); }
202 
203  template<class _InputIterator>
204  void
205  insert(_InputIterator __f, _InputIterator __l)
206  { _M_ht.insert_unique(__f, __l); }
207 
208  pair<iterator, bool>
209  insert_noresize(const value_type& __obj)
210  { return _M_ht.insert_unique_noresize(__obj); }
211 
212  iterator
213  find(const key_type& __key)
214  { return _M_ht.find(__key); }
215 
216  const_iterator
217  find(const key_type& __key) const
218  { return _M_ht.find(__key); }
219 
220  _Tp&
221  operator[](const key_type& __key)
222  { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
223 
224  size_type
225  count(const key_type& __key) const
226  { return _M_ht.count(__key); }
227 
228  pair<iterator, iterator>
229  equal_range(const key_type& __key)
230  { return _M_ht.equal_range(__key); }
231 
232  pair<const_iterator, const_iterator>
233  equal_range(const key_type& __key) const
234  { return _M_ht.equal_range(__key); }
235 
236  size_type
237  erase(const key_type& __key)
238  {return _M_ht.erase(__key); }
239 
240  void
241  erase(iterator __it)
242  { _M_ht.erase(__it); }
243 
244  void
245  erase(iterator __f, iterator __l)
246  { _M_ht.erase(__f, __l); }
247 
248  void
249  clear()
250  { _M_ht.clear(); }
251 
252  void
253  resize(size_type __hint)
254  { _M_ht.resize(__hint); }
255 
256  size_type
257  bucket_count() const
258  { return _M_ht.bucket_count(); }
259 
260  size_type
261  max_bucket_count() const
262  { return _M_ht.max_bucket_count(); }
263 
264  size_type
265  elems_in_bucket(size_type __n) const
266  { return _M_ht.elems_in_bucket(__n); }
267  };
268 
269  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
270  inline bool
271  operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
272  const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
273  { return __hm1._M_ht == __hm2._M_ht; }
274 
275  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
276  inline bool
277  operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
278  const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
279  { return !(__hm1 == __hm2); }
280 
281  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
282  inline void
283  swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
284  hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
285  { __hm1.swap(__hm2); }
286 
287 
288  /**
289  * This is an SGI extension.
290  * @ingroup SGIextensions
291  * @doctodo
292  */
293  template<class _Key, class _Tp,
294  class _HashFn = hash<_Key>,
295  class _EqualKey = equal_to<_Key>,
296  class _Alloc = allocator<_Tp> >
297  class hash_multimap
298  {
299  // concept requirements
300  __glibcxx_class_requires(_Key, _SGIAssignableConcept)
301  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
302  __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
303  __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
304 
305  private:
306  typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
307  _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
308  _Ht;
309 
310  _Ht _M_ht;
311 
312  public:
313  typedef typename _Ht::key_type key_type;
314  typedef _Tp data_type;
315  typedef _Tp mapped_type;
316  typedef typename _Ht::value_type value_type;
317  typedef typename _Ht::hasher hasher;
318  typedef typename _Ht::key_equal key_equal;
319 
320  typedef typename _Ht::size_type size_type;
321  typedef typename _Ht::difference_type difference_type;
322  typedef typename _Ht::pointer pointer;
323  typedef typename _Ht::const_pointer const_pointer;
324  typedef typename _Ht::reference reference;
325  typedef typename _Ht::const_reference const_reference;
326 
327  typedef typename _Ht::iterator iterator;
328  typedef typename _Ht::const_iterator const_iterator;
329 
330  typedef typename _Ht::allocator_type allocator_type;
331 
332  hasher
333  hash_funct() const
334  { return _M_ht.hash_funct(); }
335 
336  key_equal
337  key_eq() const
338  { return _M_ht.key_eq(); }
339 
340  allocator_type
341  get_allocator() const
342  { return _M_ht.get_allocator(); }
343 
344  hash_multimap()
345  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
346 
347  explicit
348  hash_multimap(size_type __n)
349  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
350 
351  hash_multimap(size_type __n, const hasher& __hf)
352  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
353 
354  hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
355  const allocator_type& __a = allocator_type())
356  : _M_ht(__n, __hf, __eql, __a) {}
357 
358  template<class _InputIterator>
359  hash_multimap(_InputIterator __f, _InputIterator __l)
360  : _M_ht(100, hasher(), key_equal(), allocator_type())
361  { _M_ht.insert_equal(__f, __l); }
362 
363  template<class _InputIterator>
364  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
365  : _M_ht(__n, hasher(), key_equal(), allocator_type())
366  { _M_ht.insert_equal(__f, __l); }
367 
368  template<class _InputIterator>
369  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
370  const hasher& __hf)
371  : _M_ht(__n, __hf, key_equal(), allocator_type())
372  { _M_ht.insert_equal(__f, __l); }
373 
374  template<class _InputIterator>
375  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
376  const hasher& __hf, const key_equal& __eql,
377  const allocator_type& __a = allocator_type())
378  : _M_ht(__n, __hf, __eql, __a)
379  { _M_ht.insert_equal(__f, __l); }
380 
381  size_type
382  size() const
383  { return _M_ht.size(); }
384 
385  size_type
386  max_size() const
387  { return _M_ht.max_size(); }
388 
389  bool
390  empty() const
391  { return _M_ht.empty(); }
392 
393  void
394  swap(hash_multimap& __hs)
395  { _M_ht.swap(__hs._M_ht); }
396 
397  template<class _K1, class _T1, class _HF, class _EqK, class _Al>
398  friend bool
399  operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
400  const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
401 
402  iterator
403  begin()
404  { return _M_ht.begin(); }
405 
406  iterator
407  end()
408  { return _M_ht.end(); }
409 
410  const_iterator
411  begin() const
412  { return _M_ht.begin(); }
413 
414  const_iterator
415  end() const
416  { return _M_ht.end(); }
417 
418  iterator
419  insert(const value_type& __obj)
420  { return _M_ht.insert_equal(__obj); }
421 
422  template<class _InputIterator>
423  void
424  insert(_InputIterator __f, _InputIterator __l)
425  { _M_ht.insert_equal(__f,__l); }
426 
427  iterator
428  insert_noresize(const value_type& __obj)
429  { return _M_ht.insert_equal_noresize(__obj); }
430 
431  iterator
432  find(const key_type& __key)
433  { return _M_ht.find(__key); }
434 
435  const_iterator
436  find(const key_type& __key) const
437  { return _M_ht.find(__key); }
438 
439  size_type
440  count(const key_type& __key) const
441  { return _M_ht.count(__key); }
442 
443  pair<iterator, iterator>
444  equal_range(const key_type& __key)
445  { return _M_ht.equal_range(__key); }
446 
447  pair<const_iterator, const_iterator>
448  equal_range(const key_type& __key) const
449  { return _M_ht.equal_range(__key); }
450 
451  size_type
452  erase(const key_type& __key)
453  { return _M_ht.erase(__key); }
454 
455  void
456  erase(iterator __it)
457  { _M_ht.erase(__it); }
458 
459  void
460  erase(iterator __f, iterator __l)
461  { _M_ht.erase(__f, __l); }
462 
463  void
464  clear()
465  { _M_ht.clear(); }
466 
467  void
468  resize(size_type __hint)
469  { _M_ht.resize(__hint); }
470 
471  size_type
472  bucket_count() const
473  { return _M_ht.bucket_count(); }
474 
475  size_type
476  max_bucket_count() const
477  { return _M_ht.max_bucket_count(); }
478 
479  size_type
480  elems_in_bucket(size_type __n) const
481  { return _M_ht.elems_in_bucket(__n); }
482  };
483 
484  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
485  inline bool
486  operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
487  const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
488  { return __hm1._M_ht == __hm2._M_ht; }
489 
490  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
491  inline bool
492  operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
493  const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
494  { return !(__hm1 == __hm2); }
495 
496  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
497  inline void
498  swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
499  hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
500  { __hm1.swap(__hm2); }
501 
502 _GLIBCXX_END_NAMESPACE_VERSION
503 } // namespace
504 
505 namespace std _GLIBCXX_VISIBILITY(default)
506 {
507 _GLIBCXX_BEGIN_NAMESPACE_VERSION
508 
509  // Specialization of insert_iterator so that it will work for hash_map
510  // and hash_multimap.
511  template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
512  class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
513  _EqKey, _Alloc> >
514  {
515  protected:
516  typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
517  _Container;
518  _Container* container;
519 
520  public:
521  typedef _Container container_type;
522  typedef output_iterator_tag iterator_category;
523  typedef void value_type;
524  typedef void difference_type;
525  typedef void pointer;
526  typedef void reference;
527 
528  insert_iterator(_Container& __x)
529  : container(&__x) {}
530 
531  insert_iterator(_Container& __x, typename _Container::iterator)
532  : container(&__x) {}
533 
534  insert_iterator<_Container>&
535  operator=(const typename _Container::value_type& __value)
536  {
537  container->insert(__value);
538  return *this;
539  }
540 
541  insert_iterator<_Container>&
542  operator*()
543  { return *this; }
544 
545  insert_iterator<_Container>&
546  operator++() { return *this; }
547 
548  insert_iterator<_Container>&
549  operator++(int)
550  { return *this; }
551  };
552 
553  template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
554  class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
555  _EqKey, _Alloc> >
556  {
557  protected:
558  typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
559  _Container;
560  _Container* container;
561  typename _Container::iterator iter;
562 
563  public:
564  typedef _Container container_type;
565  typedef output_iterator_tag iterator_category;
566  typedef void value_type;
567  typedef void difference_type;
568  typedef void pointer;
569  typedef void reference;
570 
571  insert_iterator(_Container& __x)
572  : container(&__x) {}
573 
574  insert_iterator(_Container& __x, typename _Container::iterator)
575  : container(&__x) {}
576 
577  insert_iterator<_Container>&
578  operator=(const typename _Container::value_type& __value)
579  {
580  container->insert(__value);
581  return *this;
582  }
583 
584  insert_iterator<_Container>&
585  operator*()
586  { return *this; }
587 
588  insert_iterator<_Container>&
589  operator++()
590  { return *this; }
591 
592  insert_iterator<_Container>&
593  operator++(int)
594  { return *this; }
595  };
596 
597 _GLIBCXX_END_NAMESPACE_VERSION
598 } // namespace
599 
600 #endif
std::pair
Struct holding two objects of arbitrary type.
Definition: stl_pair.h:87
std::insert_iterator::operator*
insert_iterator & operator*()
Simply returns *this.
Definition: stl_iterator.h:650
std::insert_iterator::insert_iterator
insert_iterator(_Container &__x, typename _Container::iterator __i)
Definition: stl_iterator.h:596
std::insert_iterator::operator=
insert_iterator & operator=(const typename _Container::value_type &__value)
Definition: stl_iterator.h:632
std::equal_to
One of the comparison functors.
Definition: stl_function.h:205
std::iterator< output_iterator_tag, void, void, void, void >::difference_type
void difference_type
Distance between iterators is represented as this type.
Definition: stl_iterator_base_types.h:126
std::iterator< output_iterator_tag, void, void, void, void >::pointer
void pointer
This type represents a pointer-to-value_type.
Definition: stl_iterator_base_types.h:128
std::insert_iterator::container_type
_Container container_type
A nested typedef for the type of whatever container you used.
Definition: stl_iterator.h:590
std::insert_iterator::operator++
insert_iterator & operator++()
Simply returns *this. (This iterator does not move.)
Definition: stl_iterator.h:655
std::iterator< output_iterator_tag, void, void, void, void >::reference
void reference
This type represents a reference-to-value_type.
Definition: stl_iterator_base_types.h:130
std::allocator
The standard allocator, as per [20.4].Further details: http://gcc.gnu.org/onlinedocs/libstdc++/manual...
Definition: allocator.h:66