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 std::_Select1st<std::pair<const _Key, _Tp> >, _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 std::_Select1st<std::pair<const _Key, _Tp> >, _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::size_type size_type;
60 typedef typename _Base::hasher hasher;
61 typedef typename _Base::key_equal key_equal;
62 typedef typename _Base::allocator_type allocator_type;
65 __unordered_map(size_type __n = 10,
66 const hasher& __hf = hasher(),
67 const key_equal& __eql = key_equal(),
68 const allocator_type& __a = allocator_type())
69 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
70 __detail::_Default_ranged_hash(),
71 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
74 template<typename _InputIterator>
75 __unordered_map(_InputIterator __f, _InputIterator __l,
77 const hasher& __hf = hasher(),
78 const key_equal& __eql = key_equal(),
79 const allocator_type& __a = allocator_type())
80 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
81 __detail::_Default_ranged_hash(),
82 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
85 __unordered_map(__unordered_map&& __x)
86 : _Base(std::forward<_Base>(__x)) { }
89 template<class _Key, class _Tp,
90 class _Hash = hash<_Key>,
91 class _Pred = std::equal_to<_Key>,
92 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
93 bool __cache_hash_code = false>
94 class __unordered_multimap
95 : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
97 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
98 _Hash, __detail::_Mod_range_hashing,
99 __detail::_Default_ranged_hash,
100 __detail::_Prime_rehash_policy,
101 __cache_hash_code, false, false>
103 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
105 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
106 _Hash, __detail::_Mod_range_hashing,
107 __detail::_Default_ranged_hash,
108 __detail::_Prime_rehash_policy,
109 __cache_hash_code, false, false>
113 typedef typename _Base::size_type size_type;
114 typedef typename _Base::hasher hasher;
115 typedef typename _Base::key_equal key_equal;
116 typedef typename _Base::allocator_type allocator_type;
119 __unordered_multimap(size_type __n = 10,
120 const hasher& __hf = hasher(),
121 const key_equal& __eql = key_equal(),
122 const allocator_type& __a = allocator_type())
123 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
124 __detail::_Default_ranged_hash(),
125 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
129 template<typename _InputIterator>
130 __unordered_multimap(_InputIterator __f, _InputIterator __l,
131 typename _Base::size_type __n = 0,
132 const hasher& __hf = hasher(),
133 const key_equal& __eql = key_equal(),
134 const allocator_type& __a = allocator_type())
135 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
136 __detail::_Default_ranged_hash(),
137 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
140 __unordered_multimap(__unordered_multimap&& __x)
141 : _Base(std::forward<_Base>(__x)) { }
144 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
145 bool __cache_hash_code>
147 swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
148 _Alloc, __cache_hash_code>& __x,
149 __unordered_map<_Key, _Tp, _Hash, _Pred,
150 _Alloc, __cache_hash_code>& __y)
153 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
154 bool __cache_hash_code>
156 swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
157 _Alloc, __cache_hash_code>& __x,
158 __unordered_multimap<_Key, _Tp, _Hash, _Pred,
159 _Alloc, __cache_hash_code>& __y)
164 * @brief A standard container composed of unique keys (containing
165 * at most one of each key value) that associates values of another type
168 * @ingroup unordered_associative_containers
170 * Meets the requirements of a <a href="tables.html#65">container</a>, and
171 * <a href="tables.html#xx">unordered associative container</a>
173 * @param Key Type of key objects.
174 * @param Tp Type of mapped objects.
175 * @param Hash Hashing function object type, defaults to hash<Value>.
176 * @param Pred Predicate function object type, defaults to equal_to<Value>.
177 * @param Alloc Allocator type, defaults to allocator<Key>.
179 * The resulting value type of the container is std::pair<const Key, Tp>.
181 template<class _Key, class _Tp,
182 class _Hash = hash<_Key>,
183 class _Pred = std::equal_to<_Key>,
184 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
186 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
188 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
191 typedef typename _Base::value_type value_type;
192 typedef typename _Base::size_type size_type;
193 typedef typename _Base::hasher hasher;
194 typedef typename _Base::key_equal key_equal;
195 typedef typename _Base::allocator_type allocator_type;
198 unordered_map(size_type __n = 10,
199 const hasher& __hf = hasher(),
200 const key_equal& __eql = key_equal(),
201 const allocator_type& __a = allocator_type())
202 : _Base(__n, __hf, __eql, __a)
205 template<typename _InputIterator>
206 unordered_map(_InputIterator __f, _InputIterator __l,
208 const hasher& __hf = hasher(),
209 const key_equal& __eql = key_equal(),
210 const allocator_type& __a = allocator_type())
211 : _Base(__f, __l, __n, __hf, __eql, __a)
214 unordered_map(unordered_map&& __x)
215 : _Base(std::forward<_Base>(__x)) { }
217 unordered_map(initializer_list<value_type> __l,
219 const hasher& __hf = hasher(),
220 const key_equal& __eql = key_equal(),
221 const allocator_type& __a = allocator_type())
222 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
226 operator=(unordered_map&& __x)
236 operator=(initializer_list<value_type> __l)
239 this->insert(__l.begin(), __l.end());
245 * @brief A standard container composed of equivalent keys
246 * (possibly containing multiple of each key value) that associates
247 * values of another type with the keys.
249 * @ingroup unordered_associative_containers
251 * Meets the requirements of a <a href="tables.html#65">container</a>, and
252 * <a href="tables.html#xx">unordered associative container</a>
254 * @param Key Type of key objects.
255 * @param Tp Type of mapped objects.
256 * @param Hash Hashing function object type, defaults to hash<Value>.
257 * @param Pred Predicate function object type, defaults to equal_to<Value>.
258 * @param Alloc Allocator type, defaults to allocator<Key>.
260 * The resulting value type of the container is std::pair<const Key, Tp>.
262 template<class _Key, class _Tp,
263 class _Hash = hash<_Key>,
264 class _Pred = std::equal_to<_Key>,
265 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
266 class unordered_multimap
267 : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
269 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
272 typedef typename _Base::value_type value_type;
273 typedef typename _Base::size_type size_type;
274 typedef typename _Base::hasher hasher;
275 typedef typename _Base::key_equal key_equal;
276 typedef typename _Base::allocator_type allocator_type;
279 unordered_multimap(size_type __n = 10,
280 const hasher& __hf = hasher(),
281 const key_equal& __eql = key_equal(),
282 const allocator_type& __a = allocator_type())
283 : _Base(__n, __hf, __eql, __a)
287 template<typename _InputIterator>
288 unordered_multimap(_InputIterator __f, _InputIterator __l,
289 typename _Base::size_type __n = 0,
290 const hasher& __hf = hasher(),
291 const key_equal& __eql = key_equal(),
292 const allocator_type& __a = allocator_type())
293 : _Base(__f, __l, __n, __hf, __eql, __a)
296 unordered_multimap(unordered_multimap&& __x)
297 : _Base(std::forward<_Base>(__x)) { }
299 unordered_multimap(initializer_list<value_type> __l,
301 const hasher& __hf = hasher(),
302 const key_equal& __eql = key_equal(),
303 const allocator_type& __a = allocator_type())
304 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
308 operator=(unordered_multimap&& __x)
318 operator=(initializer_list<value_type> __l)
321 this->insert(__l.begin(), __l.end());
326 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
328 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
329 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
332 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
334 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
335 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
338 _GLIBCXX_END_NESTED_NAMESPACE
340 #endif /* _UNORDERED_MAP_H */