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