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