1 // unordered_set 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_set.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_SET_H
31 #define _UNORDERED_SET_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 _Value
,
38 class _Hash
= hash
<_Value
>,
39 class _Pred
= std::equal_to
<_Value
>,
40 class _Alloc
= std::allocator
<_Value
>,
41 bool __cache_hash_code
= false>
43 : public _Hashtable
<_Value
, _Value
, _Alloc
,
44 std::_Identity
<_Value
>, _Pred
,
45 _Hash
, __detail::_Mod_range_hashing
,
46 __detail::_Default_ranged_hash
,
47 __detail::_Prime_rehash_policy
,
48 __cache_hash_code
, true, true>
50 typedef _Hashtable
<_Value
, _Value
, _Alloc
,
51 std::_Identity
<_Value
>, _Pred
,
52 _Hash
, __detail::_Mod_range_hashing
,
53 __detail::_Default_ranged_hash
,
54 __detail::_Prime_rehash_policy
,
55 __cache_hash_code
, true, 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_set(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(), __eql
,
71 std::_Identity
<_Value
>(), __a
)
74 template<typename _InputIterator
>
75 __unordered_set(_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(), __eql
,
82 std::_Identity
<_Value
>(), __a
)
85 __unordered_set(__unordered_set
&& __x
)
86 : _Base(std::forward
<_Base
>(__x
)) { }
89 template<class _Value
,
90 class _Hash
= hash
<_Value
>,
91 class _Pred
= std::equal_to
<_Value
>,
92 class _Alloc
= std::allocator
<_Value
>,
93 bool __cache_hash_code
= false>
94 class __unordered_multiset
95 : public _Hashtable
<_Value
, _Value
, _Alloc
,
96 std::_Identity
<_Value
>, _Pred
,
97 _Hash
, __detail::_Mod_range_hashing
,
98 __detail::_Default_ranged_hash
,
99 __detail::_Prime_rehash_policy
,
100 __cache_hash_code
, true, false>
102 typedef _Hashtable
<_Value
, _Value
, _Alloc
,
103 std::_Identity
<_Value
>, _Pred
,
104 _Hash
, __detail::_Mod_range_hashing
,
105 __detail::_Default_ranged_hash
,
106 __detail::_Prime_rehash_policy
,
107 __cache_hash_code
, true, false>
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
;
117 __unordered_multiset(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(), __eql
,
123 std::_Identity
<_Value
>(), __a
)
127 template<typename _InputIterator
>
128 __unordered_multiset(_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(), __eql
,
135 std::_Identity
<_Value
>(), __a
)
138 __unordered_multiset(__unordered_multiset
&& __x
)
139 : _Base(std::forward
<_Base
>(__x
)) { }
142 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
143 bool __cache_hash_code
>
145 swap(__unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
, __cache_hash_code
>& __x
,
146 __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
, __cache_hash_code
>& __y
)
149 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
150 bool __cache_hash_code
>
152 swap(__unordered_multiset
<_Value
, _Hash
, _Pred
,
153 _Alloc
, __cache_hash_code
>& __x
,
154 __unordered_multiset
<_Value
, _Hash
, _Pred
,
155 _Alloc
, __cache_hash_code
>& __y
)
158 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
159 bool __cache_hash_code
>
161 operator==(const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
162 __cache_hash_code
>& __x
,
163 const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
164 __cache_hash_code
>& __y
)
165 { return __x
._M_equal(__y
); }
167 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
168 bool __cache_hash_code
>
170 operator!=(const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
171 __cache_hash_code
>& __x
,
172 const __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
,
173 __cache_hash_code
>& __y
)
174 { return !(__x
== __y
); }
176 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
177 bool __cache_hash_code
>
179 operator==(const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
180 __cache_hash_code
>& __x
,
181 const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
182 __cache_hash_code
>& __y
)
183 { return __x
._M_equal(__y
); }
185 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
,
186 bool __cache_hash_code
>
188 operator!=(const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
189 __cache_hash_code
>& __x
,
190 const __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
,
191 __cache_hash_code
>& __y
)
192 { return !(__x
== __y
); }
195 * @brief A standard container composed of unique keys (containing
196 * at most one of each key value) in which the elements' keys are
197 * the elements themselves.
199 * @ingroup unordered_associative_containers
201 * Meets the requirements of a <a href="tables.html#65">container</a>, and
202 * <a href="tables.html#xx">unordered associative container</a>
204 * @param Value Type of key objects.
205 * @param Hash Hashing function object type, defaults to hash<Value>.
206 * @param Pred Predicate function object type, defaults to equal_to<Value>.
207 * @param Alloc Allocator type, defaults to allocator<Key>.
209 template<class _Value
,
210 class _Hash
= hash
<_Value
>,
211 class _Pred
= std::equal_to
<_Value
>,
212 class _Alloc
= std::allocator
<_Value
> >
214 : public __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>
216 typedef __unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
> _Base
;
219 typedef typename
_Base::value_type value_type
;
220 typedef typename
_Base::size_type size_type
;
221 typedef typename
_Base::hasher hasher
;
222 typedef typename
_Base::key_equal key_equal
;
223 typedef typename
_Base::allocator_type allocator_type
;
226 unordered_set(size_type __n
= 10,
227 const hasher
& __hf
= hasher(),
228 const key_equal
& __eql
= key_equal(),
229 const allocator_type
& __a
= allocator_type())
230 : _Base(__n
, __hf
, __eql
, __a
)
233 template<typename _InputIterator
>
234 unordered_set(_InputIterator __f
, _InputIterator __l
,
236 const hasher
& __hf
= hasher(),
237 const key_equal
& __eql
= key_equal(),
238 const allocator_type
& __a
= allocator_type())
239 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
242 unordered_set(unordered_set
&& __x
)
243 : _Base(std::forward
<_Base
>(__x
)) { }
245 unordered_set(initializer_list
<value_type
> __l
,
247 const hasher
& __hf
= hasher(),
248 const key_equal
& __eql
= key_equal(),
249 const allocator_type
& __a
= allocator_type())
250 : _Base(__l
.begin(), __l
.end(), __n
, __hf
, __eql
, __a
)
254 operator=(unordered_set
&& __x
)
264 operator=(initializer_list
<value_type
> __l
)
267 this->insert(__l
.begin(), __l
.end());
273 * @brief A standard container composed of equivalent keys
274 * (possibly containing multiple of each key value) in which the
275 * elements' keys are the elements themselves.
277 * @ingroup unordered_associative_containers
279 * Meets the requirements of a <a href="tables.html#65">container</a>, and
280 * <a href="tables.html#xx">unordered associative container</a>
282 * @param Value Type of key objects.
283 * @param Hash Hashing function object type, defaults to hash<Value>.
284 * @param Pred Predicate function object type, defaults to equal_to<Value>.
285 * @param Alloc Allocator type, defaults to allocator<Key>.
287 template<class _Value
,
288 class _Hash
= hash
<_Value
>,
289 class _Pred
= std::equal_to
<_Value
>,
290 class _Alloc
= std::allocator
<_Value
> >
291 class unordered_multiset
292 : public __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>
294 typedef __unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
> _Base
;
297 typedef typename
_Base::value_type value_type
;
298 typedef typename
_Base::size_type size_type
;
299 typedef typename
_Base::hasher hasher
;
300 typedef typename
_Base::key_equal key_equal
;
301 typedef typename
_Base::allocator_type allocator_type
;
304 unordered_multiset(size_type __n
= 10,
305 const hasher
& __hf
= hasher(),
306 const key_equal
& __eql
= key_equal(),
307 const allocator_type
& __a
= allocator_type())
308 : _Base(__n
, __hf
, __eql
, __a
)
312 template<typename _InputIterator
>
313 unordered_multiset(_InputIterator __f
, _InputIterator __l
,
314 typename
_Base::size_type __n
= 0,
315 const hasher
& __hf
= hasher(),
316 const key_equal
& __eql
= key_equal(),
317 const allocator_type
& __a
= allocator_type())
318 : _Base(__f
, __l
, __n
, __hf
, __eql
, __a
)
321 unordered_multiset(unordered_multiset
&& __x
)
322 : _Base(std::forward
<_Base
>(__x
)) { }
324 unordered_multiset(initializer_list
<value_type
> __l
,
326 const hasher
& __hf
= hasher(),
327 const key_equal
& __eql
= key_equal(),
328 const allocator_type
& __a
= allocator_type())
329 : _Base(__l
.begin(), __l
.end(), __n
, __hf
, __eql
, __a
)
333 operator=(unordered_multiset
&& __x
)
343 operator=(initializer_list
<value_type
> __l
)
346 this->insert(__l
.begin(), __l
.end());
351 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
353 swap(unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
354 unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
357 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
359 swap(unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
360 unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
363 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
365 operator==(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
366 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
367 { return __x
._M_equal(__y
); }
369 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
371 operator!=(const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
372 const unordered_set
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
373 { return !(__x
== __y
); }
375 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
377 operator==(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
378 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
379 { return __x
._M_equal(__y
); }
381 template<class _Value
, class _Hash
, class _Pred
, class _Alloc
>
383 operator!=(const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __x
,
384 const unordered_multiset
<_Value
, _Hash
, _Pred
, _Alloc
>& __y
)
385 { return !(__x
== __y
); }
387 _GLIBCXX_END_NESTED_NAMESPACE
389 #endif /* _UNORDERED_SET_H */