1 // TR1 unordered_map implementation -*- C++ -*-
2
3 // Copyright (C) 2010-2023 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 tr1/unordered_map.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{tr1/unordered_map}
28 */
29
30 namespace std _GLIBCXX_VISIBILITY(default)
31 {
32 _GLIBCXX_BEGIN_NAMESPACE_VERSION
33
34 namespace tr1
35 {
36 // NB: When we get typedef templates these class definitions
37 // will be unnecessary.
38 template<class _Key, class _Tp,
39 class _Hash = hash<_Key>,
40 class _Pred = std::equal_to<_Key>,
41 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
42 bool __cache_hash_code = false>
43 class __unordered_map
44 : public _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
45 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
46 _Hash, __detail::_Mod_range_hashing,
47 __detail::_Default_ranged_hash,
48 __detail::_Prime_rehash_policy,
49 __cache_hash_code, false, true>
50 {
51 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>, _Alloc,
52 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
53 _Hash, __detail::_Mod_range_hashing,
54 __detail::_Default_ranged_hash,
55 __detail::_Prime_rehash_policy,
56 __cache_hash_code, false, true>
57 _Base;
58
59 public:
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;
64
65 explicit
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, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
73 { }
74
75 template<typename _InputIterator>
76 __unordered_map(_InputIterator __f, _InputIterator __l,
77 size_type __n = 10,
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, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
84 { }
85 };
86
87 template<class _Key, class _Tp,
88 class _Hash = hash<_Key>,
89 class _Pred = std::equal_to<_Key>,
90 class _Alloc = std::allocator<std::pair<const _Key, _Tp> >,
91 bool __cache_hash_code = false>
92 class __unordered_multimap
93 : public _Hashtable<_Key, std::pair<const _Key, _Tp>,
94 _Alloc,
95 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
96 _Hash, __detail::_Mod_range_hashing,
97 __detail::_Default_ranged_hash,
98 __detail::_Prime_rehash_policy,
99 __cache_hash_code, false, false>
100 {
101 typedef _Hashtable<_Key, std::pair<const _Key, _Tp>,
102 _Alloc,
103 std::_Select1st<std::pair<const _Key, _Tp> >, _Pred,
104 _Hash, __detail::_Mod_range_hashing,
105 __detail::_Default_ranged_hash,
106 __detail::_Prime_rehash_policy,
107 __cache_hash_code, false, false>
108 _Base;
109
110 public:
111 typedef typename _Base::size_type size_type;
112 typedef typename _Base::hasher hasher;
113 typedef typename _Base::key_equal key_equal;
114 typedef typename _Base::allocator_type allocator_type;
115
116 explicit
117 __unordered_multimap(size_type __n = 10,
118 const hasher& __hf = hasher(),
119 const key_equal& __eql = key_equal(),
120 const allocator_type& __a = allocator_type())
121 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
122 __detail::_Default_ranged_hash(),
123 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
124 { }
125
126
127 template<typename _InputIterator>
128 __unordered_multimap(_InputIterator __f, _InputIterator __l,
129 typename _Base::size_type __n = 0,
130 const hasher& __hf = hasher(),
131 const key_equal& __eql = key_equal(),
132 const allocator_type& __a = allocator_type())
133 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
134 __detail::_Default_ranged_hash(),
135 __eql, std::_Select1st<std::pair<const _Key, _Tp> >(), __a)
136 { }
137 };
138
139 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
140 bool __cache_hash_code>
141 inline void
142 swap(__unordered_map<_Key, _Tp, _Hash, _Pred,
143 _Alloc, __cache_hash_code>& __x,
144 __unordered_map<_Key, _Tp, _Hash, _Pred,
145 _Alloc, __cache_hash_code>& __y)
146 { __x.swap(__y); }
147
148 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc,
149 bool __cache_hash_code>
150 inline void
151 swap(__unordered_multimap<_Key, _Tp, _Hash, _Pred,
152 _Alloc, __cache_hash_code>& __x,
153 __unordered_multimap<_Key, _Tp, _Hash, _Pred,
154 _Alloc, __cache_hash_code>& __y)
155 { __x.swap(__y); }
156
157
158 /**
159 * @brief A standard container composed of unique keys (containing
160 * at most one of each key value) that associates values of another type
161 * with the keys.
162 *
163 * @ingroup unordered_associative_containers
164 *
165 * Meets the requirements of a <a href="tables.html#65">container</a>, and
166 * <a href="tables.html#xx">unordered associative container</a>
167 *
168 * @param Key Type of key objects.
169 * @param Tp Type of mapped objects.
170 * @param Hash Hashing function object type, defaults to hash<Value>.
171 * @param Pred Predicate function object type, defaults to equal_to<Value>.
172 * @param Alloc Allocator type, defaults to allocator<Key>.
173 *
174 * The resulting value type of the container is std::pair<const Key, Tp>.
175 */
176 template<class _Key, class _Tp,
177 class _Hash = hash<_Key>,
178 class _Pred = std::equal_to<_Key>,
179 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
180 class unordered_map
181 : public __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
182 {
183 typedef __unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
184
185 public:
186 typedef typename _Base::value_type value_type;
187 typedef typename _Base::size_type size_type;
188 typedef typename _Base::hasher hasher;
189 typedef typename _Base::key_equal key_equal;
190 typedef typename _Base::allocator_type allocator_type;
191
192 explicit
193 unordered_map(size_type __n = 10,
194 const hasher& __hf = hasher(),
195 const key_equal& __eql = key_equal(),
196 const allocator_type& __a = allocator_type())
197 : _Base(__n, __hf, __eql, __a)
198 { }
199
200 template<typename _InputIterator>
201 unordered_map(_InputIterator __f, _InputIterator __l,
202 size_type __n = 10,
203 const hasher& __hf = hasher(),
204 const key_equal& __eql = key_equal(),
205 const allocator_type& __a = allocator_type())
206 : _Base(__f, __l, __n, __hf, __eql, __a)
207 { }
208 };
209
210 /**
211 * @brief A standard container composed of equivalent keys
212 * (possibly containing multiple of each key value) that associates
213 * values of another type with the keys.
214 *
215 * @ingroup unordered_associative_containers
216 *
217 * Meets the requirements of a <a href="tables.html#65">container</a>, and
218 * <a href="tables.html#xx">unordered associative container</a>
219 *
220 * @param Key Type of key objects.
221 * @param Tp Type of mapped objects.
222 * @param Hash Hashing function object type, defaults to hash<Value>.
223 * @param Pred Predicate function object type, defaults to equal_to<Value>.
224 * @param Alloc Allocator type, defaults to allocator<Key>.
225 *
226 * The resulting value type of the container is std::pair<const Key, Tp>.
227 */
228 template<class _Key, class _Tp,
229 class _Hash = hash<_Key>,
230 class _Pred = std::equal_to<_Key>,
231 class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
232 class unordered_multimap
233 : public __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
234 {
235 typedef __unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc> _Base;
236
237 public:
238 typedef typename _Base::value_type value_type;
239 typedef typename _Base::size_type size_type;
240 typedef typename _Base::hasher hasher;
241 typedef typename _Base::key_equal key_equal;
242 typedef typename _Base::allocator_type allocator_type;
243
244 explicit
245 unordered_multimap(size_type __n = 10,
246 const hasher& __hf = hasher(),
247 const key_equal& __eql = key_equal(),
248 const allocator_type& __a = allocator_type())
249 : _Base(__n, __hf, __eql, __a)
250 { }
251
252
253 template<typename _InputIterator>
254 unordered_multimap(_InputIterator __f, _InputIterator __l,
255 typename _Base::size_type __n = 0,
256 const hasher& __hf = hasher(),
257 const key_equal& __eql = key_equal(),
258 const allocator_type& __a = allocator_type())
259 : _Base(__f, __l, __n, __hf, __eql, __a)
260 { }
261
262 };
263
264 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
265 inline void
266 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
267 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
268 { __x.swap(__y); }
269
270 template<class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
271 inline void
272 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
273 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
274 { __x.swap(__y); }
275 }
276
277 _GLIBCXX_END_NAMESPACE_VERSION
278 }