1 // unordered_set implementation -*- C++ -*-
3 // Copyright (C) 2010, 2011 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>
55 typedef _Hashtable
<_Value
, _Value
, _Alloc
,
56 std::_Identity
<_Value
>, _Pred
,
57 _Hash
, __detail::_Mod_range_hashing
,
58 __detail::_Default_ranged_hash
,
59 __detail::_Prime_rehash_policy
,
60 __cache_hash_code
, true, true>
64 typedef typename
_Base::value_type value_type
;
65 typedef typename
_Base::size_type size_type
;
66 typedef typename
_Base::hasher hasher
;
67 typedef typename
_Base::key_equal key_equal
;
68 typedef typename
_Base::allocator_type allocator_type
;
69 typedef typename
_Base::iterator iterator
;
70 typedef typename
_Base::const_iterator const_iterator
;
73 __unordered_set(size_type __n
= 10,
74 const hasher
& __hf
= hasher(),
75 const key_equal
& __eql
= key_equal(),
76 const allocator_type
& __a
= allocator_type())
77 : _Base(__n
, __hf
, __detail::_Mod_range_hashing(),
78 __detail::_Default_ranged_hash(), __eql
,
79 std::_Identity
<value_type
>(), __a
)
82 template<typename _InputIterator
>
83 __unordered_set(_InputIterator __f
, _InputIterator __l
,
85 const hasher
& __hf
= hasher(),
86 const key_equal
& __eql
= key_equal(),
87 const allocator_type
& __a
= allocator_type())
88 : _Base(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
89 __detail::_Default_ranged_hash(), __eql
,
90 std::_Identity
<value_type
>(), __a
)
93 __unordered_set(initializer_list
<value_type
> __l
,
95 const hasher
& __hf
= hasher(),
96 const key_equal
& __eql
= key_equal(),
97 const allocator_type
& __a
= allocator_type())
98 : _Base(__l
.begin(), __l
.end(), __n
, __hf
,
99 __detail::_Mod_range_hashing(),
100 __detail::_Default_ranged_hash(), __eql
,
101 std::_Identity
<value_type
>(), __a
)
105 operator=(initializer_list
<value_type
> __l
)
108 this->insert(__l
.begin(), __l
.end());
114 std::pair
<iterator
, bool>
115 insert(value_type
&& __v
)
116 { return this->_M_insert(std::move(__v
), std::true_type()); }
119 insert(const_iterator
, value_type
&& __v
)
120 { return insert(std::move(__v
)).first
; }
123 template<class _Value
,
124 class _Hash
= hash
<_Value
>,
125 class _Pred
= std::equal_to
<_Value
>,
126 class _Alloc
= std::allocator
<_Value
>,
127 bool __cache_hash_code
=
128 __not_
<__and_
<is_integral
<_Value
>, is_empty
<_Hash
>,
129 integral_constant
<bool, !__is_final(_Hash
)>,
130 __detail::__is_noexcept_hash
<_Value
, _Hash
>>>::value
>
131 class __unordered_multiset
132 : public _Hashtable
<_Value
, _Value
, _Alloc
,
133 std::_Identity
<_Value
>, _Pred
,
134 _Hash
, __detail::_Mod_range_hashing
,
135 __detail::_Default_ranged_hash
,
136 __detail::_Prime_rehash_policy
,
137 __cache_hash_code
, true, false>
139 typedef _Hashtable
<_Value
, _Value
, _Alloc
,
140 std::_Identity
<_Value
>, _Pred
,
141 _Hash
, __detail::_Mod_range_hashing
,
142 __detail::_Default_ranged_hash
,
143 __detail::_Prime_rehash_policy
,
144 __cache_hash_code
, true, false>
148 typedef typename
_Base::value_type value_type
;
149 typedef typename
_Base::size_type size_type
;
150 typedef typename
_Base::hasher hasher
;
151 typedef typename
_Base::key_equal key_equal
;
152 typedef typename
_Base::allocator_type allocator_type
;
153 typedef typename
_Base::iterator iterator
;
154 typedef typename
_Base::const_iterator const_iterator
;
157 __unordered_multiset(size_type __n
= 10,
158 const hasher
& __hf
= hasher(),
159 const key_equal
& __eql
= key_equal(),
160 const allocator_type
& __a
= allocator_type())
161 : _Base(__n
, __hf
, __detail::_Mod_range_hashing(),
162 __detail::_Default_ranged_hash(), __eql
,
163 std::_Identity
<value_type
>(), __a
)
167 template<typename _InputIterator
>
168 __unordered_multiset(_InputIterator __f
, _InputIterator __l
,
170 const hasher
& __hf
= hasher(),
171 const key_equal
& __eql
= key_equal(),
172 const allocator_type
& __a
= allocator_type())
173 : _Base(__f
, __l
, __n
, __hf
, __detail::_Mod_range_hashing(),
174 __detail::_Default_ranged_hash(), __eql
,
175 std::_Identity
<value_type
>(), __a
)
178 __unordered_multiset(initializer_list
<value_type
> __l
,
180 const hasher
& __hf
= hasher(),
181 const key_equal
& __eql
= key_equal(),
182 const allocator_type
& __a
= allocator_type())
183 : _Base(__l
.begin(), __l
.end(), __n
, __hf
,
184 __detail::_Mod_range_hashing(),
185 __detail::_Default_ranged_hash(), __eql
,
186 std::_Identity
<value_type
>(), __a
)
189 __unordered_multiset
&
190 operator=(initializer_list
<value_type
> __l
)
193 this->insert(__l
.begin(), __l
.end());
200 insert(value_type
&& __v
)
201 { return this->_M_insert(std::move(__v
), std::false_type()); }
204 insert(const_iterator
, value_type
&& __v
)
205 { return insert(std::move(__v
)); }
208 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
209 bool __cache_hash_code
>
211 swap(__unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
, __cache_hash_code
>& __x
,
212 __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
, __cache_hash_code
>& __y
)
215 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
216 bool __cache_hash_code
>
218 swap(__unordered_multiset
<_Value
, _Hash
, _Pred
,
219 _Alloc
, __cache_hash_code
>& __x
,
220 __unordered_multiset
<_Value
, _Hash
, _Pred
,
221 _Alloc
, __cache_hash_code
>& __y
)
224 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
225 bool __cache_hash_code
>
227 operator==(const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
228 __cache_hash_code
>& __x
,
229 const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
230 __cache_hash_code
>& __y
)
231 { return __x
._M_equal(__y
); }
233 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
234 bool __cache_hash_code
>
236 operator!=(const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
237 __cache_hash_code
>& __x
,
238 const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
239 __cache_hash_code
>& __y
)
240 { return !(__x
== __y
); }
242 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
243 bool __cache_hash_code
>
245 operator==(const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
246 __cache_hash_code
>& __x
,
247 const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
248 __cache_hash_code
>& __y
)
249 { return __x
._M_equal(__y
); }
251 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
252 bool __cache_hash_code
>
254 operator!=(const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
255 __cache_hash_code
>& __x
,
256 const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
257 __cache_hash_code
>& __y
)
258 { return !(__x
== __y
); }
261 * @brief A standard container composed of unique keys (containing
262 * at most one of each key value) in which the elements' keys are
263 * the elements themselves.
265 * @ingroup unordered_associative_containers
267 * Meets the requirements of a <a href="tables.html#65">container</a>, and
268 * <a href="tables.html#xx">unordered associative container</a>
270 * @param Value Type of key objects.
271 * @param Hash Hashing function object type, defaults to hash<Value>.
272 * @param Pred Predicate function object type, defaults to equal_to<Value>.
273 * @param Alloc Allocator type, defaults to allocator<Key>.
275 template<class _Value
,
276 class _Hash
= hash
<_Value
>,
277 class _Pred
= std::equal_to
<_Value
>,
278 class _Alloc
= std::allocator
<_Value
> >
280 : public __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>
282 typedef __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
> _Base
;
285 typedef typename
_Base::value_type value_type
;
286 typedef typename
_Base::size_type size_type
;
287 typedef typename
_Base::hasher hasher
;
288 typedef typename
_Base::key_equal key_equal
;
289 typedef typename
_Base::allocator_type allocator_type
;
292 unordered_set(size_type __n
= 10,
293 const hasher
& __hf
= hasher(),
294 const key_equal
& __eql
= key_equal(),
295 const allocator_type
& __a
= allocator_type())
296 : _Base(__n
, __hf
, __eql
, __a
)
299 template<typename _InputIterator
>
300 unordered_set(_InputIterator __f
, _InputIterator __l
,
302 const hasher
& __hf
= hasher(),
303 const key_equal
& __eql
= key_equal(),
304 const allocator_type
& __a
= allocator_type())
305 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
308 unordered_set(initializer_list
<value_type
> __l
,
310 const hasher
& __hf
= hasher(),
311 const key_equal
& __eql
= key_equal(),
312 const allocator_type
& __a
= allocator_type())
313 : _Base(__l
.begin(), __l
.end(), __n
, __hf
, __eql
, __a
)
317 operator=(initializer_list
<value_type
> __l
)
320 this->insert(__l
.begin(), __l
.end());
326 * @brief A standard container composed of equivalent keys
327 * (possibly containing multiple of each key value) in which the
328 * elements' keys are the elements themselves.
330 * @ingroup unordered_associative_containers
332 * Meets the requirements of a <a href="tables.html#65">container</a>, and
333 * <a href="tables.html#xx">unordered associative container</a>
335 * @param Value Type of key objects.
336 * @param Hash Hashing function object type, defaults to hash<Value>.
337 * @param Pred Predicate function object type, defaults to equal_to<Value>.
338 * @param Alloc Allocator type, defaults to allocator<Key>.
340 template<class _Value
,
341 class _Hash
= hash
<_Value
>,
342 class _Pred
= std::equal_to
<_Value
>,
343 class _Alloc
= std::allocator
<_Value
> >
344 class unordered_multiset
345 : public __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>
347 typedef __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
> _Base
;
350 typedef typename
_Base::value_type value_type
;
351 typedef typename
_Base::size_type size_type
;
352 typedef typename
_Base::hasher hasher
;
353 typedef typename
_Base::key_equal key_equal
;
354 typedef typename
_Base::allocator_type allocator_type
;
357 unordered_multiset(size_type __n
= 10,
358 const hasher
& __hf
= hasher(),
359 const key_equal
& __eql
= key_equal(),
360 const allocator_type
& __a
= allocator_type())
361 : _Base(__n
, __hf
, __eql
, __a
)
365 template<typename _InputIterator
>
366 unordered_multiset(_InputIterator __f
, _InputIterator __l
,
368 const hasher
& __hf
= hasher(),
369 const key_equal
& __eql
= key_equal(),
370 const allocator_type
& __a
= allocator_type())
371 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
374 unordered_multiset(initializer_list
<value_type
> __l
,
376 const hasher
& __hf
= hasher(),
377 const key_equal
& __eql
= key_equal(),
378 const allocator_type
& __a
= allocator_type())
379 : _Base(__l
.begin(), __l
.end(), __n
, __hf
, __eql
, __a
)
383 operator=(initializer_list
<value_type
> __l
)
386 this->insert(__l
.begin(), __l
.end());
391 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
393 swap(unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
394 unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
397 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
399 swap(unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
400 unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
403 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
405 operator==(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
406 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
407 { return __x
._M_equal(__y
); }
409 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
411 operator!=(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
412 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
413 { return !(__x
== __y
); }
415 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
417 operator==(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
418 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
419 { return __x
._M_equal(__y
); }
421 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
423 operator!=(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
424 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
425 { return !(__x
== __y
); }
427 _GLIBCXX_END_NAMESPACE_CONTAINER
430 #endif /* _UNORDERED_SET_H */