1 // unordered_set 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_set.h
26 * This is an internal header file, included by other library headers.
27 * Do not attempt to use it directly. @headername{unordered_set}
28 */
29
30 #ifndef _UNORDERED_SET_H
31 #define _UNORDERED_SET_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 _Value,
40 class _Hash = hash<_Value>,
41 class _Pred = std::equal_to<_Value>,
42 class _Alloc = std::allocator<_Value>,
43 bool __cache_hash_code =
44 __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
45 integral_constant<bool, !__is_final(_Hash)>,
46 __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
47 class __unordered_set
48 : public _Hashtable<_Value, _Value, _Alloc,
49 std::_Identity<_Value>, _Pred,
50 _Hash, __detail::_Mod_range_hashing,
51 __detail::_Default_ranged_hash,
52 __detail::_Prime_rehash_policy,
53 __cache_hash_code, true, true>,
54 __check_copy_constructible<_Alloc>
55 {
56 typedef _Hashtable<_Value, _Value, _Alloc,
57 std::_Identity<_Value>, _Pred,
58 _Hash, __detail::_Mod_range_hashing,
59 __detail::_Default_ranged_hash,
60 __detail::_Prime_rehash_policy,
61 __cache_hash_code, true, 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 typedef typename _Base::iterator iterator;
71 typedef typename _Base::const_iterator const_iterator;
72
73 explicit
74 __unordered_set(size_type __n = 10,
75 const hasher& __hf = hasher(),
76 const key_equal& __eql = key_equal(),
77 const allocator_type& __a = allocator_type())
78 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
79 __detail::_Default_ranged_hash(), __eql,
80 std::_Identity<value_type>(), __a)
81 { }
82
83 template<typename _InputIterator>
84 __unordered_set(_InputIterator __f, _InputIterator __l,
85 size_type __n = 0,
86 const hasher& __hf = hasher(),
87 const key_equal& __eql = key_equal(),
88 const allocator_type& __a = allocator_type())
89 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
90 __detail::_Default_ranged_hash(), __eql,
91 std::_Identity<value_type>(), __a)
92 { }
93
94 __unordered_set(initializer_list<value_type> __l,
95 size_type __n = 0,
96 const hasher& __hf = hasher(),
97 const key_equal& __eql = key_equal(),
98 const allocator_type& __a = allocator_type())
99 : _Base(__l.begin(), __l.end(), __n, __hf,
100 __detail::_Mod_range_hashing(),
101 __detail::_Default_ranged_hash(), __eql,
102 std::_Identity<value_type>(), __a)
103 { }
104
105 __unordered_set&
106 operator=(initializer_list<value_type> __l)
107 {
108 this->clear();
109 this->insert(__l.begin(), __l.end());
110 return *this;
111 }
112
113 using _Base::insert;
114
115 std::pair<iterator, bool>
116 insert(value_type&& __v)
117 { return this->_M_insert(std::move(__v), std::true_type()); }
118
119 iterator
120 insert(const_iterator, value_type&& __v)
121 { return insert(std::move(__v)).first; }
122 };
123
124 template<class _Value,
125 class _Hash = hash<_Value>,
126 class _Pred = std::equal_to<_Value>,
127 class _Alloc = std::allocator<_Value>,
128 bool __cache_hash_code =
129 __not_<__and_<is_integral<_Value>, is_empty<_Hash>,
130 integral_constant<bool, !__is_final(_Hash)>,
131 __detail::__is_noexcept_hash<_Value, _Hash>>>::value>
132 class __unordered_multiset
133 : public _Hashtable<_Value, _Value, _Alloc,
134 std::_Identity<_Value>, _Pred,
135 _Hash, __detail::_Mod_range_hashing,
136 __detail::_Default_ranged_hash,
137 __detail::_Prime_rehash_policy,
138 __cache_hash_code, true, false>,
139 __check_copy_constructible<_Alloc>
140 {
141 typedef _Hashtable<_Value, _Value, _Alloc,
142 std::_Identity<_Value>, _Pred,
143 _Hash, __detail::_Mod_range_hashing,
144 __detail::_Default_ranged_hash,
145 __detail::_Prime_rehash_policy,
146 __cache_hash_code, true, false>
147 _Base;
148
149 public:
150 typedef typename _Base::value_type value_type;
151 typedef typename _Base::size_type size_type;
152 typedef typename _Base::hasher hasher;
153 typedef typename _Base::key_equal key_equal;
154 typedef typename _Base::allocator_type allocator_type;
155 typedef typename _Base::iterator iterator;
156 typedef typename _Base::const_iterator const_iterator;
157
158 explicit
159 __unordered_multiset(size_type __n = 10,
160 const hasher& __hf = hasher(),
161 const key_equal& __eql = key_equal(),
162 const allocator_type& __a = allocator_type())
163 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
164 __detail::_Default_ranged_hash(), __eql,
165 std::_Identity<value_type>(), __a)
166 { }
167
168
169 template<typename _InputIterator>
170 __unordered_multiset(_InputIterator __f, _InputIterator __l,
171 size_type __n = 0,
172 const hasher& __hf = hasher(),
173 const key_equal& __eql = key_equal(),
174 const allocator_type& __a = allocator_type())
175 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
176 __detail::_Default_ranged_hash(), __eql,
177 std::_Identity<value_type>(), __a)
178 { }
179
180 __unordered_multiset(initializer_list<value_type> __l,
181 size_type __n = 0,
182 const hasher& __hf = hasher(),
183 const key_equal& __eql = key_equal(),
184 const allocator_type& __a = allocator_type())
185 : _Base(__l.begin(), __l.end(), __n, __hf,
186 __detail::_Mod_range_hashing(),
187 __detail::_Default_ranged_hash(), __eql,
188 std::_Identity<value_type>(), __a)
189 { }
190
191 __unordered_multiset&
192 operator=(initializer_list<value_type> __l)
193 {
194 this->clear();
195 this->insert(__l.begin(), __l.end());
196 return *this;
197 }
198
199 using _Base::insert;
200
201 iterator
202 insert(value_type&& __v)
203 { return this->_M_insert(std::move(__v), std::false_type()); }
204
205 iterator
206 insert(const_iterator, value_type&& __v)
207 { return insert(std::move(__v)); }
208 };
209
210 template<class _Value, class _Hash, class _Pred, class _Alloc,
211 bool __cache_hash_code>
212 inline void
213 swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
214 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
215 { __x.swap(__y); }
216
217 template<class _Value, class _Hash, class _Pred, class _Alloc,
218 bool __cache_hash_code>
219 inline void
220 swap(__unordered_multiset<_Value, _Hash, _Pred,
221 _Alloc, __cache_hash_code>& __x,
222 __unordered_multiset<_Value, _Hash, _Pred,
223 _Alloc, __cache_hash_code>& __y)
224 { __x.swap(__y); }
225
226 template<class _Value, class _Hash, class _Pred, class _Alloc,
227 bool __cache_hash_code>
228 inline bool
229 operator==(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
230 __cache_hash_code>& __x,
231 const __unordered_set<_Value, _Hash, _Pred, _Alloc,
232 __cache_hash_code>& __y)
233 { return __x._M_equal(__y); }
234
235 template<class _Value, class _Hash, class _Pred, class _Alloc,
236 bool __cache_hash_code>
237 inline bool
238 operator!=(const __unordered_set<_Value, _Hash, _Pred, _Alloc,
239 __cache_hash_code>& __x,
240 const __unordered_set<_Value, _Hash, _Pred, _Alloc,
241 __cache_hash_code>& __y)
242 { return !(__x == __y); }
243
244 template<class _Value, class _Hash, class _Pred, class _Alloc,
245 bool __cache_hash_code>
246 inline bool
247 operator==(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
248 __cache_hash_code>& __x,
249 const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
250 __cache_hash_code>& __y)
251 { return __x._M_equal(__y); }
252
253 template<class _Value, class _Hash, class _Pred, class _Alloc,
254 bool __cache_hash_code>
255 inline bool
256 operator!=(const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
257 __cache_hash_code>& __x,
258 const __unordered_multiset<_Value, _Hash, _Pred, _Alloc,
259 __cache_hash_code>& __y)
260 { return !(__x == __y); }
261
262 /**
263 * @brief A standard container composed of unique keys (containing
264 * at most one of each key value) in which the elements' keys are
265 * the elements themselves.
266 *
267 * @ingroup unordered_associative_containers
268 *
269 * Meets the requirements of a <a href="tables.html#65">container</a>, and
270 * <a href="tables.html#xx">unordered associative container</a>
271 *
272 * @param Value Type of key objects.
273 * @param Hash Hashing function object type, defaults to hash<Value>.
274 * @param Pred Predicate function object type, defaults to equal_to<Value>.
275 * @param Alloc Allocator type, defaults to allocator<Key>.
276 */
277 template<class _Value,
278 class _Hash = hash<_Value>,
279 class _Pred = std::equal_to<_Value>,
280 class _Alloc = std::allocator<_Value> >
281 class unordered_set
282 : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
283 {
284 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base;
285
286 public:
287 typedef typename _Base::value_type value_type;
288 typedef typename _Base::size_type size_type;
289 typedef typename _Base::hasher hasher;
290 typedef typename _Base::key_equal key_equal;
291 typedef typename _Base::allocator_type allocator_type;
292
293 explicit
294 unordered_set(size_type __n = 10,
295 const hasher& __hf = hasher(),
296 const key_equal& __eql = key_equal(),
297 const allocator_type& __a = allocator_type())
298 : _Base(__n, __hf, __eql, __a)
299 { }
300
301 template<typename _InputIterator>
302 unordered_set(_InputIterator __f, _InputIterator __l,
303 size_type __n = 0,
304 const hasher& __hf = hasher(),
305 const key_equal& __eql = key_equal(),
306 const allocator_type& __a = allocator_type())
307 : _Base(__f, __l, __n, __hf, __eql, __a)
308 { }
309
310 unordered_set(initializer_list<value_type> __l,
311 size_type __n = 0,
312 const hasher& __hf = hasher(),
313 const key_equal& __eql = key_equal(),
314 const allocator_type& __a = allocator_type())
315 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
316 { }
317
318 unordered_set&
319 operator=(initializer_list<value_type> __l)
320 {
321 this->clear();
322 this->insert(__l.begin(), __l.end());
323 return *this;
324 }
325 };
326
327 /**
328 * @brief A standard container composed of equivalent keys
329 * (possibly containing multiple of each key value) in which the
330 * elements' keys are the elements themselves.
331 *
332 * @ingroup unordered_associative_containers
333 *
334 * Meets the requirements of a <a href="tables.html#65">container</a>, and
335 * <a href="tables.html#xx">unordered associative container</a>
336 *
337 * @param Value Type of key objects.
338 * @param Hash Hashing function object type, defaults to hash<Value>.
339 * @param Pred Predicate function object type, defaults to equal_to<Value>.
340 * @param Alloc Allocator type, defaults to allocator<Key>.
341 */
342 template<class _Value,
343 class _Hash = hash<_Value>,
344 class _Pred = std::equal_to<_Value>,
345 class _Alloc = std::allocator<_Value> >
346 class unordered_multiset
347 : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
348 {
349 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base;
350
351 public:
352 typedef typename _Base::value_type value_type;
353 typedef typename _Base::size_type size_type;
354 typedef typename _Base::hasher hasher;
355 typedef typename _Base::key_equal key_equal;
356 typedef typename _Base::allocator_type allocator_type;
357
358 explicit
359 unordered_multiset(size_type __n = 10,
360 const hasher& __hf = hasher(),
361 const key_equal& __eql = key_equal(),
362 const allocator_type& __a = allocator_type())
363 : _Base(__n, __hf, __eql, __a)
364 { }
365
366
367 template<typename _InputIterator>
368 unordered_multiset(_InputIterator __f, _InputIterator __l,
369 size_type __n = 0,
370 const hasher& __hf = hasher(),
371 const key_equal& __eql = key_equal(),
372 const allocator_type& __a = allocator_type())
373 : _Base(__f, __l, __n, __hf, __eql, __a)
374 { }
375
376 unordered_multiset(initializer_list<value_type> __l,
377 size_type __n = 0,
378 const hasher& __hf = hasher(),
379 const key_equal& __eql = key_equal(),
380 const allocator_type& __a = allocator_type())
381 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
382 { }
383
384 unordered_multiset&
385 operator=(initializer_list<value_type> __l)
386 {
387 this->clear();
388 this->insert(__l.begin(), __l.end());
389 return *this;
390 }
391 };
392
393 template<class _Value, class _Hash, class _Pred, class _Alloc>
394 inline void
395 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
396 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
397 { __x.swap(__y); }
398
399 template<class _Value, class _Hash, class _Pred, class _Alloc>
400 inline void
401 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
402 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
403 { __x.swap(__y); }
404
405 template<class _Value, class _Hash, class _Pred, class _Alloc>
406 inline bool
407 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
408 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
409 { return __x._M_equal(__y); }
410
411 template<class _Value, class _Hash, class _Pred, class _Alloc>
412 inline bool
413 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
414 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
415 { return !(__x == __y); }
416
417 template<class _Value, class _Hash, class _Pred, class _Alloc>
418 inline bool
419 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
420 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
421 { return __x._M_equal(__y); }
422
423 template<class _Value, class _Hash, class _Pred, class _Alloc>
424 inline bool
425 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
426 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
427 { return !(__x == __y); }
428
429 _GLIBCXX_END_NAMESPACE_CONTAINER
430 } // namespace std
431
432 #endif /* _UNORDERED_SET_H */
433
434