1 // unordered_set 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_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}
30 #ifndef _UNORDERED_SET_H
31 #define _UNORDERED_SET_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 _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>
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>
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>
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;
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)
83 template<typename _InputIterator>
84 __unordered_set(_InputIterator __f, _InputIterator __l,
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)
94 __unordered_set(initializer_list<value_type> __l,
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)
106 operator=(initializer_list<value_type> __l)
109 this->insert(__l.begin(), __l.end());
115 std::pair<iterator, bool>
116 insert(value_type&& __v)
117 { return this->_M_insert(std::move(__v), std::true_type()); }
120 insert(const_iterator, value_type&& __v)
121 { return insert(std::move(__v)).first; }
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>
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>
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;
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)
169 template<typename _InputIterator>
170 __unordered_multiset(_InputIterator __f, _InputIterator __l,
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)
180 __unordered_multiset(initializer_list<value_type> __l,
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)
191 __unordered_multiset&
192 operator=(initializer_list<value_type> __l)
195 this->insert(__l.begin(), __l.end());
202 insert(value_type&& __v)
203 { return this->_M_insert(std::move(__v), std::false_type()); }
206 insert(const_iterator, value_type&& __v)
207 { return insert(std::move(__v)); }
210 template<class _Value, class _Hash, class _Pred, class _Alloc,
211 bool __cache_hash_code>
213 swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
214 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
217 template<class _Value, class _Hash, class _Pred, class _Alloc,
218 bool __cache_hash_code>
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)
226 template<class _Value, class _Hash, class _Pred, class _Alloc,
227 bool __cache_hash_code>
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); }
235 template<class _Value, class _Hash, class _Pred, class _Alloc,
236 bool __cache_hash_code>
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); }
244 template<class _Value, class _Hash, class _Pred, class _Alloc,
245 bool __cache_hash_code>
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); }
253 template<class _Value, class _Hash, class _Pred, class _Alloc,
254 bool __cache_hash_code>
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); }
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.
267 * @ingroup unordered_associative_containers
269 * Meets the requirements of a <a href="tables.html#65">container</a>, and
270 * <a href="tables.html#xx">unordered associative container</a>
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>.
277 template<class _Value,
278 class _Hash = hash<_Value>,
279 class _Pred = std::equal_to<_Value>,
280 class _Alloc = std::allocator<_Value> >
282 : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
284 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base;
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;
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)
301 template<typename _InputIterator>
302 unordered_set(_InputIterator __f, _InputIterator __l,
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)
310 unordered_set(initializer_list<value_type> __l,
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)
319 operator=(initializer_list<value_type> __l)
322 this->insert(__l.begin(), __l.end());
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.
332 * @ingroup unordered_associative_containers
334 * Meets the requirements of a <a href="tables.html#65">container</a>, and
335 * <a href="tables.html#xx">unordered associative container</a>
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>.
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>
349 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base;
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;
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)
367 template<typename _InputIterator>
368 unordered_multiset(_InputIterator __f, _InputIterator __l,
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)
376 unordered_multiset(initializer_list<value_type> __l,
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)
385 operator=(initializer_list<value_type> __l)
388 this->insert(__l.begin(), __l.end());
393 template<class _Value, class _Hash, class _Pred, class _Alloc>
395 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
396 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
399 template<class _Value, class _Hash, class _Pred, class _Alloc>
401 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
402 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
405 template<class _Value, class _Hash, class _Pred, class _Alloc>
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); }
411 template<class _Value, class _Hash, class _Pred, class _Alloc>
413 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
414 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
415 { return !(__x == __y); }
417 template<class _Value, class _Hash, class _Pred, class _Alloc>
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); }
423 template<class _Value, class _Hash, class _Pred, class _Alloc>
425 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
426 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
427 { return !(__x == __y); }
429 _GLIBCXX_END_NAMESPACE_CONTAINER
432 #endif /* _UNORDERED_SET_H */