libstdc++
unordered_map.h
Go to the documentation of this file.
1 // unordered_map implementation -*- C++ -*-
2 
3 // Copyright (C) 2010, 2011 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 /** @file bits/unordered_map.h
26  * This is an internal header file, included by other library headers.
27  * Do not attempt to use it directly. @headername{unordered_map}
28  */
29 
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
36 
37  // NB: When we get typedef templates these class definitions
38  // will be unnecessary.
39  template<class _Key, class _Tp,
40  class _Hash = hash<_Key>,
41  class _Pred = std::equal_to<_Key>,
43  bool __cache_hash_code =
44  __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
45  integral_constant<bool, !__is_final(_Hash)>,
46  __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
47  class __unordered_map
48  : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
49  std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
50  _Hash, __detail::_Mod_range_hashing,
51  __detail::_Default_ranged_hash,
52  __detail::_Prime_rehash_policy,
53  __cache_hash_code, false, true>
54  {
55  typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
56  std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
57  _Hash, __detail::_Mod_range_hashing,
58  __detail::_Default_ranged_hash,
59  __detail::_Prime_rehash_policy,
60  __cache_hash_code, false, true>
61  _Base;
62 
63  public:
64  typedef typename _Base::value_type value_type;
65  typedef typename _Base::size_type size_type;
66  typedef typename _Base::hasher hasher;
67  typedef typename _Base::key_equal key_equal;
68  typedef typename _Base::allocator_type allocator_type;
69 
70  explicit
71  __unordered_map(size_type __n = 10,
72  const hasher& __hf = hasher(),
73  const key_equal& __eql = key_equal(),
74  const allocator_type& __a = allocator_type())
75  : _Base(__n, __hf, __detail::_Mod_range_hashing(),
76  __detail::_Default_ranged_hash(),
77  __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
78  { }
79 
80  template<typename _InputIterator>
81  __unordered_map(_InputIterator __f, _InputIterator __l,
82  size_type __n = 0,
83  const hasher& __hf = hasher(),
84  const key_equal& __eql = key_equal(),
85  const allocator_type& __a = allocator_type())
86  : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
87  __detail::_Default_ranged_hash(),
88  __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
89  { }
90 
91  __unordered_map(initializer_list<value_type> __l,
92  size_type __n = 0,
93  const hasher& __hf = hasher(),
94  const key_equal& __eql = key_equal(),
95  const allocator_type& __a = allocator_type())
96  : _Base(__l.begin(), __l.end(), __n, __hf,
97  __detail::_Mod_range_hashing(),
98  __detail::_Default_ranged_hash(),
99  __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
100  { }
101 
102  __unordered_map&
103  operator=(initializer_list<value_type> __l)
104  {
105  this->clear();
106  this->insert(__l.begin(), __l.end());
107  return *this;
108  }
109  };
110 
111  template<class _Key, class _Tp,
112  class _Hash = hash<_Key>,
113  class _Pred = std::equal_to<_Key>,
115  bool __cache_hash_code =
116  __not_<__and_<is_integral<_Key>, is_empty<_Hash>,
117  integral_constant<bool, !__is_final(_Hash)>,
118  __detail::__is_noexcept_hash<_Key, _Hash>>>::value>
119  class __unordered_multimap
120  : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
121  _Alloc,
122  std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
123  _Hash, __detail::_Mod_range_hashing,
124  __detail::_Default_ranged_hash,
125  __detail::_Prime_rehash_policy,
126  __cache_hash_code, false, false>
127  {
128  typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
129  _Alloc,
130  std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
131  _Hash, __detail::_Mod_range_hashing,
132  __detail::_Default_ranged_hash,
133  __detail::_Prime_rehash_policy,
134  __cache_hash_code, false, false>
135  _Base;
136 
137  public:
138  typedef typename _Base::value_type value_type;
139  typedef typename _Base::size_type size_type;
140  typedef typename _Base::hasher hasher;
141  typedef typename _Base::key_equal key_equal;
142  typedef typename _Base::allocator_type allocator_type;
143 
144  explicit
145  __unordered_multimap(size_type __n = 10,
146  const hasher& __hf = hasher(),
147  const key_equal& __eql = key_equal(),
148  const allocator_type& __a = allocator_type())
149  : _Base(__n, __hf, __detail::_Mod_range_hashing(),
150  __detail::_Default_ranged_hash(),
151  __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
152  { }
153 
154 
155  template<typename _InputIterator>
156  __unordered_multimap(_InputIterator __f, _InputIterator __l,
157  size_type __n = 0,
158  const hasher& __hf = hasher(),
159  const key_equal& __eql = key_equal(),
160  const allocator_type& __a = allocator_type())
161  : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
162  __detail::_Default_ranged_hash(),
163  __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
164  { }
165 
166  __unordered_multimap(initializer_list<value_type> __l,
167  size_type __n = 0,
168  const hasher& __hf = hasher(),
169  const key_equal& __eql = key_equal(),
170  const allocator_type& __a = allocator_type())
171  : _Base(__l.begin(), __l.end(), __n, __hf,
172  __detail::_Mod_range_hashing(),
173  __detail::_Default_ranged_hash(),
174  __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
175  { }
176 
177  __unordered_multimap&
178  operator=(initializer_list<value_type> __l)
179  {
180  this->clear();
181  this->insert(__l.begin(), __l.end());
182  return *this;
183  }
184  };
185 
186  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
187  bool __cache_hash_code>
188  inline void
189  swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
190  _Alloc, __cache_hash_code>& __x,
191  __unordered_map<_Key, _Tp, _Hash, _Pred,
192  _Alloc, __cache_hash_code>& __y)
193  { __x.swap(__y); }
194 
195  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
196  bool __cache_hash_code>
197  inline void
198  swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
199  _Alloc, __cache_hash_code>& __x,
200  __unordered_multimap<_Key, _Tp, _Hash, _Pred,
201  _Alloc, __cache_hash_code>& __y)
202  { __x.swap(__y); }
203 
204  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
205  bool __cache_hash_code>
206  inline bool
207  operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
208  __cache_hash_code>& __x,
209  const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
210  __cache_hash_code>& __y)
211  { return __x._M_equal(__y); }
212 
213  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
214  bool __cache_hash_code>
215  inline bool
216  operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
217  __cache_hash_code>& __x,
218  const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
219  __cache_hash_code>& __y)
220  { return !(__x == __y); }
221 
222  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
223  bool __cache_hash_code>
224  inline bool
225  operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
226  __cache_hash_code>& __x,
227  const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
228  __cache_hash_code>& __y)
229  { return __x._M_equal(__y); }
230 
231  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
232  bool __cache_hash_code>
233  inline bool
234  operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
235  __cache_hash_code>& __x,
236  const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
237  __cache_hash_code>& __y)
238  { return !(__x == __y); }
239 
240  /**
241  * @brief A standard container composed of unique keys (containing
242  * at most one of each key value) that associates values of another type
243  * with the keys.
244  *
245  * @ingroup unordered_associative_containers
246  *
247  * Meets the requirements of a <a href="tables.html#65">container</a>, and
248  * <a href="tables.html#xx">unordered associative container</a>
249  *
250  * @param Key Type of key objects.
251  * @param Tp Type of mapped objects.
252  * @param Hash Hashing function object type, defaults to hash<Value>.
253  * @param Pred Predicate function object type, defaults to equal_to<Value>.
254  * @param Alloc Allocator type, defaults to allocator<Key>.
255  *
256  * The resulting value type of the container is std::pair<const Key, Tp>.
257  */
258  template<class _Key, class _Tp,
259  class _Hash = hash<_Key>,
260  class _Pred = std::equal_to<_Key>,
263  : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
264  {
265  typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
266 
267  public:
268  typedef typename _Base::value_type value_type;
269  typedef typename _Base::size_type size_type;
270  typedef typename _Base::hasher hasher;
271  typedef typename _Base::key_equal key_equal;
272  typedef typename _Base::allocator_type allocator_type;
273 
274  explicit
275  unordered_map(size_type __n = 10,
276  const hasher& __hf = hasher(),
277  const key_equal& __eql = key_equal(),
278  const allocator_type& __a = allocator_type())
279  : _Base(__n, __hf, __eql, __a)
280  { }
281 
282  template<typename _InputIterator>
283  unordered_map(_InputIterator __f, _InputIterator __l,
284  size_type __n = 0,
285  const hasher& __hf = hasher(),
286  const key_equal& __eql = key_equal(),
287  const allocator_type& __a = allocator_type())
288  : _Base(__f, __l, __n, __hf, __eql, __a)
289  { }
290 
292  size_type __n = 0,
293  const hasher& __hf = hasher(),
294  const key_equal& __eql = key_equal(),
295  const allocator_type& __a = allocator_type())
296  : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
297  { }
298 
300  operator=(initializer_list<value_type> __l)
301  {
302  this->clear();
303  this->insert(__l.begin(), __l.end());
304  return *this;
305  }
306  };
307 
308  /**
309  * @brief A standard container composed of equivalent keys
310  * (possibly containing multiple of each key value) that associates
311  * values of another type with the keys.
312  *
313  * @ingroup unordered_associative_containers
314  *
315  * Meets the requirements of a <a href="tables.html#65">container</a>, and
316  * <a href="tables.html#xx">unordered associative container</a>
317  *
318  * @param Key Type of key objects.
319  * @param Tp Type of mapped objects.
320  * @param Hash Hashing function object type, defaults to hash<Value>.
321  * @param Pred Predicate function object type, defaults to equal_to<Value>.
322  * @param Alloc Allocator type, defaults to allocator<Key>.
323  *
324  * The resulting value type of the container is std::pair<const Key, Tp>.
325  */
326  template<class _Key, class _Tp,
327  class _Hash = hash<_Key>,
328  class _Pred = std::equal_to<_Key>,
331  : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
332  {
333  typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
334 
335  public:
336  typedef typename _Base::value_type value_type;
337  typedef typename _Base::size_type size_type;
338  typedef typename _Base::hasher hasher;
339  typedef typename _Base::key_equal key_equal;
340  typedef typename _Base::allocator_type allocator_type;
341 
342  explicit
343  unordered_multimap(size_type __n = 10,
344  const hasher& __hf = hasher(),
345  const key_equal& __eql = key_equal(),
346  const allocator_type& __a = allocator_type())
347  : _Base(__n, __hf, __eql, __a)
348  { }
349 
350  template<typename _InputIterator>
351  unordered_multimap(_InputIterator __f, _InputIterator __l,
352  size_type __n = 0,
353  const hasher& __hf = hasher(),
354  const key_equal& __eql = key_equal(),
355  const allocator_type& __a = allocator_type())
356  : _Base(__f, __l, __n, __hf, __eql, __a)
357  { }
358 
360  size_type __n = 0,
361  const hasher& __hf = hasher(),
362  const key_equal& __eql = key_equal(),
363  const allocator_type& __a = allocator_type())
364  : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
365  { }
366 
368  operator=(initializer_list<value_type> __l)
369  {
370  this->clear();
371  this->insert(__l.begin(), __l.end());
372  return *this;
373  }
374  };
375 
376  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
377  inline void
380  { __x.swap(__y); }
381 
382  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
383  inline void
384  swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
385  unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
386  { __x.swap(__y); }
387 
388  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
389  inline bool
390  operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
391  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
392  { return __x._M_equal(__y); }
393 
394  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
395  inline bool
396  operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
397  const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
398  { return !(__x == __y); }
399 
400  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
401  inline bool
402  operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
403  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
404  { return __x._M_equal(__y); }
405 
406  template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
407  inline bool
408  operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
409  const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
410  { return !(__x == __y); }
411 
412 _GLIBCXX_END_NAMESPACE_CONTAINER
413 } // namespace std
414 
415 #endif /* _UNORDERED_MAP_H */