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
_GLIBCXX_VISIBILITY(default)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 */
418