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)
160 * @brief A standard container composed of unique keys (containing
161 * at most one of each key value) in which the elements' keys are
162 * the elements themselves.
164 * @ingroup unordered_associative_containers
166 * Meets the requirements of a <a href="tables.html#65">container</a>, and
167 * <a href="tables.html#xx">unordered associative container</a>
169 * @param Value Type of key 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>.
174 template<class _Value,
175 class _Hash = hash<_Value>,
176 class _Pred = std::equal_to<_Value>,
177 class _Alloc = std::allocator<_Value> >
179 : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
181 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base;
184 typedef typename _Base::value_type value_type;
185 typedef typename _Base::size_type size_type;
186 typedef typename _Base::hasher hasher;
187 typedef typename _Base::key_equal key_equal;
188 typedef typename _Base::allocator_type allocator_type;
191 unordered_set(size_type __n = 10,
192 const hasher& __hf = hasher(),
193 const key_equal& __eql = key_equal(),
194 const allocator_type& __a = allocator_type())
195 : _Base(__n, __hf, __eql, __a)
198 template<typename _InputIterator>
199 unordered_set(_InputIterator __f, _InputIterator __l,
201 const hasher& __hf = hasher(),
202 const key_equal& __eql = key_equal(),
203 const allocator_type& __a = allocator_type())
204 : _Base(__f, __l, __n, __hf, __eql, __a)
207 unordered_set(unordered_set&& __x)
208 : _Base(std::forward<_Base>(__x)) { }
210 unordered_set(initializer_list<value_type> __l,
212 const hasher& __hf = hasher(),
213 const key_equal& __eql = key_equal(),
214 const allocator_type& __a = allocator_type())
215 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
219 operator=(unordered_set&& __x)
229 operator=(initializer_list<value_type> __l)
232 this->insert(__l.begin(), __l.end());
238 * @brief A standard container composed of equivalent keys
239 * (possibly containing multiple of each key value) in which the
240 * elements' keys are the elements themselves.
242 * @ingroup unordered_associative_containers
244 * Meets the requirements of a <a href="tables.html#65">container</a>, and
245 * <a href="tables.html#xx">unordered associative container</a>
247 * @param Value Type of key objects.
248 * @param Hash Hashing function object type, defaults to hash<Value>.
249 * @param Pred Predicate function object type, defaults to equal_to<Value>.
250 * @param Alloc Allocator type, defaults to allocator<Key>.
252 template<class _Value,
253 class _Hash = hash<_Value>,
254 class _Pred = std::equal_to<_Value>,
255 class _Alloc = std::allocator<_Value> >
256 class unordered_multiset
257 : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
259 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base;
262 typedef typename _Base::value_type value_type;
263 typedef typename _Base::size_type size_type;
264 typedef typename _Base::hasher hasher;
265 typedef typename _Base::key_equal key_equal;
266 typedef typename _Base::allocator_type allocator_type;
269 unordered_multiset(size_type __n = 10,
270 const hasher& __hf = hasher(),
271 const key_equal& __eql = key_equal(),
272 const allocator_type& __a = allocator_type())
273 : _Base(__n, __hf, __eql, __a)
277 template<typename _InputIterator>
278 unordered_multiset(_InputIterator __f, _InputIterator __l,
279 typename _Base::size_type __n = 0,
280 const hasher& __hf = hasher(),
281 const key_equal& __eql = key_equal(),
282 const allocator_type& __a = allocator_type())
283 : _Base(__f, __l, __n, __hf, __eql, __a)
286 unordered_multiset(unordered_multiset&& __x)
287 : _Base(std::forward<_Base>(__x)) { }
289 unordered_multiset(initializer_list<value_type> __l,
291 const hasher& __hf = hasher(),
292 const key_equal& __eql = key_equal(),
293 const allocator_type& __a = allocator_type())
294 : _Base(__l.begin(), __l.end(), __n, __hf, __eql, __a)
298 operator=(unordered_multiset&& __x)
308 operator=(initializer_list<value_type> __l)
311 this->insert(__l.begin(), __l.end());
316 template<class _Value, class _Hash, class _Pred, class _Alloc>
318 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
319 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
322 template<class _Value, class _Hash, class _Pred, class _Alloc>
324 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
325 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
328 _GLIBCXX_END_NESTED_NAMESPACE
330 #endif /* _UNORDERED_SET_H */