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