1 // unordered_map implementation -*- C++ -*-
3 // Copyright (C) 2010 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 * You should not attempt to use it directly.
30 #ifndef _UNORDERED_MAP_H
31 #define _UNORDERED_MAP_H
33 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
35 // XXX When we get typedef templates these class definitions
36 // will be unnecessary.
37 template<class _Key, class _Tp,
38 class _Hash = hash<_Key>,
39 class _Pred = std::equal_to<_Key>,
40 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
41 bool __cache_hash_code = false>
43 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
44 __detail::_Select1st, _Pred,
45 _Hash, __detail::_Mod_range_hashing,
46 __detail::_Default_ranged_hash,
47 __detail::_Prime_rehash_policy,
48 __cache_hash_code, false, true>
50 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
51 __detail::_Select1st, _Pred,
52 _Hash, __detail::_Mod_range_hashing,
53 __detail::_Default_ranged_hash,
54 __detail::_Prime_rehash_policy,
55 __cache_hash_code, false, true>
59 typedef typename _Base::value_type value_type;
60 typedef typename _Base::size_type size_type;
61 typedef typename _Base::hasher hasher;
62 typedef typename _Base::key_equal key_equal;
63 typedef typename _Base::allocator_type allocator_type;
66 __unordered_map(size_type __n = 10,
67 const hasher& __hf = hasher(),
68 const key_equal& __eql = key_equal(),
69 const allocator_type& __a = allocator_type())
70 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
71 __detail::_Default_ranged_hash(),
72 __eql, __detail::_Select1st(), __a)
75 template<typename _InputIterator>
76 __unordered_map(_InputIterator __f, _InputIterator __l,
78 const hasher& __hf = hasher(),
79 const key_equal& __eql = key_equal(),
80 const allocator_type& __a = allocator_type())
81 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
82 __detail::_Default_ranged_hash(),
83 __eql, __detail::_Select1st(), __a)
86 __unordered_map(initializer_list<value_type> __l,
88 const hasher& __hf = hasher(),
89 const key_equal& __eql = key_equal(),
90 const allocator_type& __a = allocator_type())
91 : _Base(__l.begin(), __l.end(), __n, __hf,
92 __detail::_Mod_range_hashing(),
93 __detail::_Default_ranged_hash(),
94 __eql, __detail::_Select1st(), __a)
98 operator=(initializer_list<value_type> __l)
101 this->insert(__l.begin(), __l.end());
106 template<class _Key, class _Tp,
107 class _Hash = hash<_Key>,
108 class _Pred = std::equal_to<_Key>,
109 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
110 bool __cache_hash_code = false>
111 class __unordered_multimap
112 : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
114 __detail::_Select1st, _Pred,
115 _Hash, __detail::_Mod_range_hashing,
116 __detail::_Default_ranged_hash,
117 __detail::_Prime_rehash_policy,
118 __cache_hash_code, false, false>
120 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
122 __detail::_Select1st, _Pred,
123 _Hash, __detail::_Mod_range_hashing,
124 __detail::_Default_ranged_hash,
125 __detail::_Prime_rehash_policy,
126 __cache_hash_code, false, false>
130 typedef typename _Base::value_type value_type;
131 typedef typename _Base::size_type size_type;
132 typedef typename _Base::hasher hasher;
133 typedef typename _Base::key_equal key_equal;
134 typedef typename _Base::allocator_type allocator_type;
137 __unordered_multimap(size_type __n = 10,
138 const hasher& __hf = hasher(),
139 const key_equal& __eql = key_equal(),
140 const allocator_type& __a = allocator_type())
141 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
142 __detail::_Default_ranged_hash(),
143 __eql, __detail::_Select1st(), __a)
147 template<typename _InputIterator>
148 __unordered_multimap(_InputIterator __f, _InputIterator __l,
150 const hasher& __hf = hasher(),
151 const key_equal& __eql = key_equal(),
152 const allocator_type& __a = allocator_type())
153 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
154 __detail::_Default_ranged_hash(),
155 __eql, __detail::_Select1st(), __a)
158 __unordered_multimap(initializer_list<value_type> __l,
160 const hasher& __hf = hasher(),
161 const key_equal& __eql = key_equal(),
162 const allocator_type& __a = allocator_type())
163 : _Base(__l.begin(), __l.end(), __n, __hf,
164 __detail::_Mod_range_hashing(),
165 __detail::_Default_ranged_hash(),
166 __eql, __detail::_Select1st(), __a)
169 __unordered_multimap&
170 operator=(initializer_list<value_type> __l)
173 this->insert(__l.begin(), __l.end());
178 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
179 bool __cache_hash_code>
181 swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
182 _Alloc, __cache_hash_code>& __x,
183 __unordered_map<_Key, _Tp, _Hash, _Pred,
184 _Alloc, __cache_hash_code>& __y)
187 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
188 bool __cache_hash_code>
190 swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
191 _Alloc, __cache_hash_code>& __x,
192 __unordered_multimap<_Key, _Tp, _Hash, _Pred,
193 _Alloc, __cache_hash_code>& __y)
196 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
197 bool __cache_hash_code>
199 operator==(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
200 __cache_hash_code>& __x,
201 const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
202 __cache_hash_code>& __y)
203 { return __x._M_equal(__y); }
205 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
206 bool __cache_hash_code>
208 operator!=(const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
209 __cache_hash_code>& __x,
210 const __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc,
211 __cache_hash_code>& __y)
212 { return !(__x == __y); }
214 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
215 bool __cache_hash_code>
217 operator==(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
218 __cache_hash_code>& __x,
219 const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
220 __cache_hash_code>& __y)
221 { return __x._M_equal(__y); }
223 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
224 bool __cache_hash_code>
226 operator!=(const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
227 __cache_hash_code>& __x,
228 const __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc,
229 __cache_hash_code>& __y)
230 { return !(__x == __y); }
233 * @brief A standard container composed of unique keys (containing
234 * at most one of each key value) that associates values of another type
237 * @ingroup unordered_associative_containers
239 * Meets the requirements of a <a href="tables.html#65">container</a>, and
240 * <a href="tables.html#xx">unordered associative container</a>
242 * @param Key Type of key objects.
243 * @param Tp Type of mapped objects.
244 * @param Hash Hashing function object type, defaults to hash<Value>.
245 * @param Pred Predicate function object type, defaults to equal_to<Value>.
246 * @param Alloc Allocator type, defaults to allocator<Key>.
248 * The resulting value type of the container is std::pair<const Key, Tp>.
250 template<class _Key, class _Tp,
251 class _Hash = hash<_Key>,
252 class _Pred = std::equal_to<_Key>,
253 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
255 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
257 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
260 typedef typename _Base::value_type value_type;
261 typedef typename _Base::size_type size_type;
262 typedef typename _Base::hasher hasher;
263 typedef typename _Base::key_equal key_equal;
264 typedef typename _Base::allocator_type allocator_type;
267 unordered_map(size_type __n = 10,
268 const hasher& __hf = hasher(),
269 const key_equal& __eql = key_equal(),
270 const allocator_type& __a = allocator_type())
271 : _Base(__n, __hf, __eql, __a)
274 template<typename _InputIterator>
275 unordered_map(_InputIterator __f, _InputIterator __l,
277 const hasher& __hf = hasher(),
278 const key_equal& __eql = key_equal(),
279 const allocator_type& __a = allocator_type())
280 : _Base(__f, __l, __n, __hf, __eql, __a)
283 unordered_map(initializer_list<value_type> __l,
285 const hasher& __hf = hasher(),
286 const key_equal& __eql = key_equal(),
287 const allocator_type& __a = allocator_type())
288 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
292 operator=(initializer_list<value_type> __l)
295 this->insert(__l.begin(), __l.end());
301 * @brief A standard container composed of equivalent keys
302 * (possibly containing multiple of each key value) that associates
303 * values of another type with the keys.
305 * @ingroup unordered_associative_containers
307 * Meets the requirements of a <a href="tables.html#65">container</a>, and
308 * <a href="tables.html#xx">unordered associative container</a>
310 * @param Key Type of key objects.
311 * @param Tp Type of mapped objects.
312 * @param Hash Hashing function object type, defaults to hash<Value>.
313 * @param Pred Predicate function object type, defaults to equal_to<Value>.
314 * @param Alloc Allocator type, defaults to allocator<Key>.
316 * The resulting value type of the container is std::pair<const Key, Tp>.
318 template<class _Key, class _Tp,
319 class _Hash = hash<_Key>,
320 class _Pred = std::equal_to<_Key>,
321 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
322 class unordered_multimap
323 : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
325 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
328 typedef typename _Base::value_type value_type;
329 typedef typename _Base::size_type size_type;
330 typedef typename _Base::hasher hasher;
331 typedef typename _Base::key_equal key_equal;
332 typedef typename _Base::allocator_type allocator_type;
335 unordered_multimap(size_type __n = 10,
336 const hasher& __hf = hasher(),
337 const key_equal& __eql = key_equal(),
338 const allocator_type& __a = allocator_type())
339 : _Base(__n, __hf, __eql, __a)
342 template<typename _InputIterator>
343 unordered_multimap(_InputIterator __f, _InputIterator __l,
345 const hasher& __hf = hasher(),
346 const key_equal& __eql = key_equal(),
347 const allocator_type& __a = allocator_type())
348 : _Base(__f, __l, __n, __hf, __eql, __a)
351 unordered_multimap(initializer_list<value_type> __l,
353 const hasher& __hf = hasher(),
354 const key_equal& __eql = key_equal(),
355 const allocator_type& __a = allocator_type())
356 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
360 operator=(initializer_list<value_type> __l)
363 this->insert(__l.begin(), __l.end());
368 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
370 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
371 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
374 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
376 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
377 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
380 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
382 operator==(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
383 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
384 { return __x._M_equal(__y); }
386 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
388 operator!=(const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
389 const unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
390 { return !(__x == __y); }
392 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
394 operator==(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
395 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
396 { return __x._M_equal(__y); }
398 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
400 operator!=(const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
401 const unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
402 { return !(__x == __y); }
404 _GLIBCXX_END_NESTED_NAMESPACE
406 #endif /* _UNORDERED_MAP_H */