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 #include "backward_warning.h"
61 #include <bits/c++config.h>
62 #include <backward/hashtable.h>
63 #include <bits/concept_check.h>
64 
65 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
66 
67  using std::equal_to;
68  using std::allocator;
69  using std::pair;
70  using std::_Select1st;
71 
72  /**
73  * This is an SGI extension.
74  * @ingroup SGIextensions
75  * @doctodo
76  */
77  template<class _Key, class _Tp, class _HashFn = hash<_Key>,
78  class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
79  class hash_map
80  {
81  private:
82  typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
83  _Select1st<pair<const _Key, _Tp> >,
84  _EqualKey, _Alloc> _Ht;
85 
86  _Ht _M_ht;
87 
88  public:
89  typedef typename _Ht::key_type key_type;
90  typedef _Tp data_type;
91  typedef _Tp mapped_type;
92  typedef typename _Ht::value_type value_type;
93  typedef typename _Ht::hasher hasher;
94  typedef typename _Ht::key_equal key_equal;
95 
96  typedef typename _Ht::size_type size_type;
97  typedef typename _Ht::difference_type difference_type;
98  typedef typename _Ht::pointer pointer;
99  typedef typename _Ht::const_pointer const_pointer;
100  typedef typename _Ht::reference reference;
101  typedef typename _Ht::const_reference const_reference;
102 
103  typedef typename _Ht::iterator iterator;
104  typedef typename _Ht::const_iterator const_iterator;
105 
106  typedef typename _Ht::allocator_type allocator_type;
107 
108  hasher
109  hash_funct() const
110  { return _M_ht.hash_funct(); }
111 
112  key_equal
113  key_eq() const
114  { return _M_ht.key_eq(); }
115 
116  allocator_type
117  get_allocator() const
118  { return _M_ht.get_allocator(); }
119 
120  hash_map()
121  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
122 
123  explicit
124  hash_map(size_type __n)
125  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
126 
127  hash_map(size_type __n, const hasher& __hf)
128  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
129 
130  hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
131  const allocator_type& __a = allocator_type())
132  : _M_ht(__n, __hf, __eql, __a) {}
133 
134  template<class _InputIterator>
135  hash_map(_InputIterator __f, _InputIterator __l)
136  : _M_ht(100, hasher(), key_equal(), allocator_type())
137  { _M_ht.insert_unique(__f, __l); }
138 
139  template<class _InputIterator>
140  hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
141  : _M_ht(__n, 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  const hasher& __hf)
147  : _M_ht(__n, __hf, key_equal(), allocator_type())
148  { _M_ht.insert_unique(__f, __l); }
149 
150  template<class _InputIterator>
151  hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
152  const hasher& __hf, const key_equal& __eql,
153  const allocator_type& __a = allocator_type())
154  : _M_ht(__n, __hf, __eql, __a)
155  { _M_ht.insert_unique(__f, __l); }
156 
157  size_type
158  size() const
159  { return _M_ht.size(); }
160 
161  size_type
162  max_size() const
163  { return _M_ht.max_size(); }
164 
165  bool
166  empty() const
167  { return _M_ht.empty(); }
168 
169  void
170  swap(hash_map& __hs)
171  { _M_ht.swap(__hs._M_ht); }
172 
173  template<class _K1, class _T1, class _HF, class _EqK, class _Al>
174  friend bool
175  operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
177 
178  iterator
179  begin()
180  { return _M_ht.begin(); }
181 
182  iterator
183  end()
184  { return _M_ht.end(); }
185 
186  const_iterator
187  begin() const
188  { return _M_ht.begin(); }
189 
190  const_iterator
191  end() const
192  { return _M_ht.end(); }
193 
195  insert(const value_type& __obj)
196  { return _M_ht.insert_unique(__obj); }
197 
198  template<class _InputIterator>
199  void
200  insert(_InputIterator __f, _InputIterator __l)
201  { _M_ht.insert_unique(__f, __l); }
202 
204  insert_noresize(const value_type& __obj)
205  { return _M_ht.insert_unique_noresize(__obj); }
206 
207  iterator
208  find(const key_type& __key)
209  { return _M_ht.find(__key); }
210 
211  const_iterator
212  find(const key_type& __key) const
213  { return _M_ht.find(__key); }
214 
215  _Tp&
216  operator[](const key_type& __key)
217  { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
218 
219  size_type
220  count(const key_type& __key) const
221  { return _M_ht.count(__key); }
222 
224  equal_range(const key_type& __key)
225  { return _M_ht.equal_range(__key); }
226 
228  equal_range(const key_type& __key) const
229  { return _M_ht.equal_range(__key); }
230 
231  size_type
232  erase(const key_type& __key)
233  {return _M_ht.erase(__key); }
234 
235  void
236  erase(iterator __it)
237  { _M_ht.erase(__it); }
238 
239  void
240  erase(iterator __f, iterator __l)
241  { _M_ht.erase(__f, __l); }
242 
243  void
244  clear()
245  { _M_ht.clear(); }
246 
247  void
248  resize(size_type __hint)
249  { _M_ht.resize(__hint); }
250 
251  size_type
252  bucket_count() const
253  { return _M_ht.bucket_count(); }
254 
255  size_type
256  max_bucket_count() const
257  { return _M_ht.max_bucket_count(); }
258 
259  size_type
260  elems_in_bucket(size_type __n) const
261  { return _M_ht.elems_in_bucket(__n); }
262  };
263 
264  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
265  inline bool
266  operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
268  { return __hm1._M_ht == __hm2._M_ht; }
269 
270  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
271  inline bool
272  operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
273  const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
274  { return !(__hm1 == __hm2); }
275 
276  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
277  inline void
278  swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
279  hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
280  { __hm1.swap(__hm2); }
281 
282 
283  /**
284  * This is an SGI extension.
285  * @ingroup SGIextensions
286  * @doctodo
287  */
288  template<class _Key, class _Tp,
289  class _HashFn = hash<_Key>,
290  class _EqualKey = equal_to<_Key>,
291  class _Alloc = allocator<_Tp> >
293  {
294  // concept requirements
295  __glibcxx_class_requires(_Key, _SGIAssignableConcept)
296  __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
297  __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
298  __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
299 
300  private:
301  typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
302  _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
303  _Ht;
304 
305  _Ht _M_ht;
306 
307  public:
308  typedef typename _Ht::key_type key_type;
309  typedef _Tp data_type;
310  typedef _Tp mapped_type;
311  typedef typename _Ht::value_type value_type;
312  typedef typename _Ht::hasher hasher;
313  typedef typename _Ht::key_equal key_equal;
314 
315  typedef typename _Ht::size_type size_type;
316  typedef typename _Ht::difference_type difference_type;
317  typedef typename _Ht::pointer pointer;
318  typedef typename _Ht::const_pointer const_pointer;
319  typedef typename _Ht::reference reference;
320  typedef typename _Ht::const_reference const_reference;
321 
322  typedef typename _Ht::iterator iterator;
323  typedef typename _Ht::const_iterator const_iterator;
324 
325  typedef typename _Ht::allocator_type allocator_type;
326 
327  hasher
328  hash_funct() const
329  { return _M_ht.hash_funct(); }
330 
331  key_equal
332  key_eq() const
333  { return _M_ht.key_eq(); }
334 
335  allocator_type
336  get_allocator() const
337  { return _M_ht.get_allocator(); }
338 
339  hash_multimap()
340  : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
341 
342  explicit
343  hash_multimap(size_type __n)
344  : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
345 
346  hash_multimap(size_type __n, const hasher& __hf)
347  : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
348 
349  hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
350  const allocator_type& __a = allocator_type())
351  : _M_ht(__n, __hf, __eql, __a) {}
352 
353  template<class _InputIterator>
354  hash_multimap(_InputIterator __f, _InputIterator __l)
355  : _M_ht(100, hasher(), key_equal(), allocator_type())
356  { _M_ht.insert_equal(__f, __l); }
357 
358  template<class _InputIterator>
359  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
360  : _M_ht(__n, 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  const hasher& __hf)
366  : _M_ht(__n, __hf, key_equal(), allocator_type())
367  { _M_ht.insert_equal(__f, __l); }
368 
369  template<class _InputIterator>
370  hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
371  const hasher& __hf, const key_equal& __eql,
372  const allocator_type& __a = allocator_type())
373  : _M_ht(__n, __hf, __eql, __a)
374  { _M_ht.insert_equal(__f, __l); }
375 
376  size_type
377  size() const
378  { return _M_ht.size(); }
379 
380  size_type
381  max_size() const
382  { return _M_ht.max_size(); }
383 
384  bool
385  empty() const
386  { return _M_ht.empty(); }
387 
388  void
389  swap(hash_multimap& __hs)
390  { _M_ht.swap(__hs._M_ht); }
391 
392  template<class _K1, class _T1, class _HF, class _EqK, class _Al>
393  friend bool
394  operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
396 
397  iterator
398  begin()
399  { return _M_ht.begin(); }
400 
401  iterator
402  end()
403  { return _M_ht.end(); }
404 
405  const_iterator
406  begin() const
407  { return _M_ht.begin(); }
408 
409  const_iterator
410  end() const
411  { return _M_ht.end(); }
412 
413  iterator
414  insert(const value_type& __obj)
415  { return _M_ht.insert_equal(__obj); }
416 
417  template<class _InputIterator>
418  void
419  insert(_InputIterator __f, _InputIterator __l)
420  { _M_ht.insert_equal(__f,__l); }
421 
422  iterator
423  insert_noresize(const value_type& __obj)
424  { return _M_ht.insert_equal_noresize(__obj); }
425 
426  iterator
427  find(const key_type& __key)
428  { return _M_ht.find(__key); }
429 
430  const_iterator
431  find(const key_type& __key) const
432  { return _M_ht.find(__key); }
433 
434  size_type
435  count(const key_type& __key) const
436  { return _M_ht.count(__key); }
437 
439  equal_range(const key_type& __key)
440  { return _M_ht.equal_range(__key); }
441 
443  equal_range(const key_type& __key) const
444  { return _M_ht.equal_range(__key); }
445 
446  size_type
447  erase(const key_type& __key)
448  { return _M_ht.erase(__key); }
449 
450  void
451  erase(iterator __it)
452  { _M_ht.erase(__it); }
453 
454  void
455  erase(iterator __f, iterator __l)
456  { _M_ht.erase(__f, __l); }
457 
458  void
459  clear()
460  { _M_ht.clear(); }
461 
462  void
463  resize(size_type __hint)
464  { _M_ht.resize(__hint); }
465 
466  size_type
467  bucket_count() const
468  { return _M_ht.bucket_count(); }
469 
470  size_type
471  max_bucket_count() const
472  { return _M_ht.max_bucket_count(); }
473 
474  size_type
475  elems_in_bucket(size_type __n) const
476  { return _M_ht.elems_in_bucket(__n); }
477  };
478 
479  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
480  inline bool
481  operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
483  { return __hm1._M_ht == __hm2._M_ht; }
484 
485  template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
486  inline bool
487  operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
488  const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
489  { return !(__hm1 == __hm2); }
490 
491  template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
492  inline void
493  swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
494  hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
495  { __hm1.swap(__hm2); }
496 
497 _GLIBCXX_END_NAMESPACE
498 
499 _GLIBCXX_BEGIN_NAMESPACE(std)
500 
501  // Specialization of insert_iterator so that it will work for hash_map
502  // and hash_multimap.
503  template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
504  class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
505  _EqKey, _Alloc> >
506  {
507  protected:
509  _Container;
510  _Container* container;
511 
512  public:
513  typedef _Container container_type;
514  typedef output_iterator_tag iterator_category;
515  typedef void value_type;
516  typedef void difference_type;
517  typedef void pointer;
518  typedef void reference;
519 
520  insert_iterator(_Container& __x)
521  : container(&__x) {}
522 
523  insert_iterator(_Container& __x, typename _Container::iterator)
524  : container(&__x) {}
525 
526  insert_iterator<_Container>&
527  operator=(const typename _Container::value_type& __value)
528  {
529  container->insert(__value);
530  return *this;
531  }
532 
533  insert_iterator<_Container>&
534  operator*()
535  { return *this; }
536 
537  insert_iterator<_Container>&
538  operator++() { return *this; }
539 
540  insert_iterator<_Container>&
541  operator++(int)
542  { return *this; }
543  };
544 
545  template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
546  class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
547  _EqKey, _Alloc> >
548  {
549  protected:
551  _Container;
552  _Container* container;
553  typename _Container::iterator iter;
554 
555  public:
556  typedef _Container container_type;
557  typedef output_iterator_tag iterator_category;
558  typedef void value_type;
559  typedef void difference_type;
560  typedef void pointer;
561  typedef void reference;
562 
563  insert_iterator(_Container& __x)
564  : container(&__x) {}
565 
566  insert_iterator(_Container& __x, typename _Container::iterator)
567  : container(&__x) {}
568 
569  insert_iterator<_Container>&
570  operator=(const typename _Container::value_type& __value)
571  {
572  container->insert(__value);
573  return *this;
574  }
575 
576  insert_iterator<_Container>&
577  operator*()
578  { return *this; }
579 
580  insert_iterator<_Container>&
581  operator++()
582  { return *this; }
583 
584  insert_iterator<_Container>&
585  operator++(int)
586  { return *this; }
587  };
588 
589 _GLIBCXX_END_NAMESPACE
590 
591 #endif
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67