1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010, 2011, 2013 Free Software Foundation, Inc.
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)
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.
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.
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/>.
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}
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
33 namespace std _GLIBCXX_VISIBILITY(default)
35 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
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>
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>
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>
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;
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)
81 template<typename _InputIterator>
82 __unordered_map(_InputIterator __f, _InputIterator __l,
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)
92 __unordered_map(initializer_list<value_type> __l,
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)
104 operator=(initializer_list<value_type> __l)
107 this->insert(__l.begin(), __l.end());
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>,
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>
130 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
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>
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;
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)
157 template<typename _InputIterator>
158 __unordered_multimap(_InputIterator __f, _InputIterator __l,
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)
168 __unordered_multimap(initializer_list<value_type> __l,
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)
179 __unordered_multimap&
180 operator=(initializer_list<value_type> __l)
183 this->insert(__l.begin(), __l.end());
188 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
189 bool __cache_hash_code>
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)
197 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
198 bool __cache_hash_code>
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)
206 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
207 bool __cache_hash_code>
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); }
215 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
216 bool __cache_hash_code>
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); }
224 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
225 bool __cache_hash_code>
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); }
233 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
234 bool __cache_hash_code>
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); }
243 * @brief A standard container composed of unique keys (containing
244 * at most one of each key value) that associates values of another type
247 * @ingroup unordered_associative_containers
249 * Meets the requirements of a <a href="tables.html#65">container</a>, and
250 * <a href="tables.html#xx">unordered associative container</a>
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>.
258 * The resulting value type of the container is std::pair<const Key, Tp>.
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> > >
265 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
267 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
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;
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)
284 template<typename _InputIterator>
285 unordered_map(_InputIterator __f, _InputIterator __l,
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)
293 unordered_map(initializer_list<value_type> __l,
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)
302 operator=(initializer_list<value_type> __l)
305 this->insert(__l.begin(), __l.end());
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.
315 * @ingroup unordered_associative_containers
317 * Meets the requirements of a <a href="tables.html#65">container</a>, and
318 * <a href="tables.html#xx">unordered associative container</a>
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>.
326 * The resulting value type of the container is std::pair<const Key, Tp>.
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>
335 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
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;
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)
352 template<typename _InputIterator>
353 unordered_multimap(_InputIterator __f, _InputIterator __l,
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)
361 unordered_multimap(initializer_list<value_type> __l,
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)
370 operator=(initializer_list<value_type> __l)
373 this->insert(__l.begin(), __l.end());
378 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
380 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
381 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
384 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
386 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
387 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
390 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
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); }
396 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
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); }
402 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
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); }
408 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
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); }
414 _GLIBCXX_END_NAMESPACE_CONTAINER
417 #endif /* _UNORDERED_MAP_H */