|
111
|
1 // TR1 unordered_set implementation -*- C++ -*-
|
|
|
2
|
|
145
|
3 // Copyright (C) 2010-2020 Free Software Foundation, Inc.
|
|
111
|
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 tr1/unordered_set.h
|
|
|
26 * This is an internal header file, included by other library headers.
|
|
|
27 * Do not attempt to use it directly. @headername{tr1/unordered_set}
|
|
|
28 */
|
|
|
29
|
|
|
30 namespace std _GLIBCXX_VISIBILITY(default)
|
|
|
31 {
|
|
|
32 _GLIBCXX_BEGIN_NAMESPACE_VERSION
|
|
|
33
|
|
|
34 namespace tr1
|
|
|
35 {
|
|
|
36 // NB: When we get typedef templates these class definitions
|
|
|
37 // will be unnecessary.
|
|
|
38 template<class _Value,
|
|
|
39 class _Hash = hash<_Value>,
|
|
|
40 class _Pred = std::equal_to<_Value>,
|
|
|
41 class _Alloc = std::allocator<_Value>,
|
|
|
42 bool __cache_hash_code = false>
|
|
|
43 class __unordered_set
|
|
|
44 : public _Hashtable<_Value, _Value, _Alloc,
|
|
|
45 std::_Identity<_Value>, _Pred,
|
|
|
46 _Hash, __detail::_Mod_range_hashing,
|
|
|
47 __detail::_Default_ranged_hash,
|
|
|
48 __detail::_Prime_rehash_policy,
|
|
|
49 __cache_hash_code, true, true>
|
|
|
50 {
|
|
|
51 typedef _Hashtable<_Value, _Value, _Alloc,
|
|
|
52 std::_Identity<_Value>, _Pred,
|
|
|
53 _Hash, __detail::_Mod_range_hashing,
|
|
|
54 __detail::_Default_ranged_hash,
|
|
|
55 __detail::_Prime_rehash_policy,
|
|
|
56 __cache_hash_code, true, true>
|
|
|
57 _Base;
|
|
|
58
|
|
|
59 public:
|
|
|
60 typedef typename _Base::size_type size_type;
|
|
|
61 typedef typename _Base::hasher hasher;
|
|
|
62 typedef typename _Base::key_equal key_equal;
|
|
|
63 typedef typename _Base::allocator_type allocator_type;
|
|
|
64
|
|
|
65 explicit
|
|
|
66 __unordered_set(size_type __n = 10,
|
|
|
67 const hasher& __hf = hasher(),
|
|
|
68 const key_equal& __eql = key_equal(),
|
|
|
69 const allocator_type& __a = allocator_type())
|
|
|
70 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
|
|
|
71 __detail::_Default_ranged_hash(), __eql,
|
|
|
72 std::_Identity<_Value>(), __a)
|
|
|
73 { }
|
|
|
74
|
|
|
75 template<typename _InputIterator>
|
|
|
76 __unordered_set(_InputIterator __f, _InputIterator __l,
|
|
|
77 size_type __n = 10,
|
|
|
78 const hasher& __hf = hasher(),
|
|
|
79 const key_equal& __eql = key_equal(),
|
|
|
80 const allocator_type& __a = allocator_type())
|
|
|
81 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
|
|
|
82 __detail::_Default_ranged_hash(), __eql,
|
|
|
83 std::_Identity<_Value>(), __a)
|
|
|
84 { }
|
|
|
85 };
|
|
|
86
|
|
|
87 template<class _Value,
|
|
|
88 class _Hash = hash<_Value>,
|
|
|
89 class _Pred = std::equal_to<_Value>,
|
|
|
90 class _Alloc = std::allocator<_Value>,
|
|
|
91 bool __cache_hash_code = false>
|
|
|
92 class __unordered_multiset
|
|
|
93 : public _Hashtable<_Value, _Value, _Alloc,
|
|
|
94 std::_Identity<_Value>, _Pred,
|
|
|
95 _Hash, __detail::_Mod_range_hashing,
|
|
|
96 __detail::_Default_ranged_hash,
|
|
|
97 __detail::_Prime_rehash_policy,
|
|
|
98 __cache_hash_code, true, false>
|
|
|
99 {
|
|
|
100 typedef _Hashtable<_Value, _Value, _Alloc,
|
|
|
101 std::_Identity<_Value>, _Pred,
|
|
|
102 _Hash, __detail::_Mod_range_hashing,
|
|
|
103 __detail::_Default_ranged_hash,
|
|
|
104 __detail::_Prime_rehash_policy,
|
|
|
105 __cache_hash_code, true, false>
|
|
|
106 _Base;
|
|
|
107
|
|
|
108 public:
|
|
|
109 typedef typename _Base::size_type size_type;
|
|
|
110 typedef typename _Base::hasher hasher;
|
|
|
111 typedef typename _Base::key_equal key_equal;
|
|
|
112 typedef typename _Base::allocator_type allocator_type;
|
|
|
113
|
|
|
114 explicit
|
|
|
115 __unordered_multiset(size_type __n = 10,
|
|
|
116 const hasher& __hf = hasher(),
|
|
|
117 const key_equal& __eql = key_equal(),
|
|
|
118 const allocator_type& __a = allocator_type())
|
|
|
119 : _Base(__n, __hf, __detail::_Mod_range_hashing(),
|
|
|
120 __detail::_Default_ranged_hash(), __eql,
|
|
|
121 std::_Identity<_Value>(), __a)
|
|
|
122 { }
|
|
|
123
|
|
|
124
|
|
|
125 template<typename _InputIterator>
|
|
|
126 __unordered_multiset(_InputIterator __f, _InputIterator __l,
|
|
|
127 typename _Base::size_type __n = 0,
|
|
|
128 const hasher& __hf = hasher(),
|
|
|
129 const key_equal& __eql = key_equal(),
|
|
|
130 const allocator_type& __a = allocator_type())
|
|
|
131 : _Base(__f, __l, __n, __hf, __detail::_Mod_range_hashing(),
|
|
|
132 __detail::_Default_ranged_hash(), __eql,
|
|
|
133 std::_Identity<_Value>(), __a)
|
|
|
134 { }
|
|
|
135 };
|
|
|
136
|
|
|
137 template<class _Value, class _Hash, class _Pred, class _Alloc,
|
|
|
138 bool __cache_hash_code>
|
|
|
139 inline void
|
|
|
140 swap(__unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __x,
|
|
|
141 __unordered_set<_Value, _Hash, _Pred, _Alloc, __cache_hash_code>& __y)
|
|
|
142 { __x.swap(__y); }
|
|
|
143
|
|
|
144 template<class _Value, class _Hash, class _Pred, class _Alloc,
|
|
|
145 bool __cache_hash_code>
|
|
|
146 inline void
|
|
|
147 swap(__unordered_multiset<_Value, _Hash, _Pred,
|
|
|
148 _Alloc, __cache_hash_code>& __x,
|
|
|
149 __unordered_multiset<_Value, _Hash, _Pred,
|
|
|
150 _Alloc, __cache_hash_code>& __y)
|
|
|
151 { __x.swap(__y); }
|
|
|
152
|
|
|
153
|
|
|
154 /**
|
|
|
155 * @brief A standard container composed of unique keys (containing
|
|
|
156 * at most one of each key value) in which the elements' keys are
|
|
|
157 * the elements themselves.
|
|
|
158 *
|
|
|
159 * @ingroup unordered_associative_containers
|
|
|
160 *
|
|
|
161 * Meets the requirements of a <a href="tables.html#65">container</a>, and
|
|
|
162 * <a href="tables.html#xx">unordered associative container</a>
|
|
|
163 *
|
|
|
164 * @param Value Type of key objects.
|
|
|
165 * @param Hash Hashing function object type, defaults to hash<Value>.
|
|
|
166 * @param Pred Predicate function object type, defaults to equal_to<Value>.
|
|
|
167 * @param Alloc Allocator type, defaults to allocator<Key>.
|
|
|
168 */
|
|
|
169 template<class _Value,
|
|
|
170 class _Hash = hash<_Value>,
|
|
|
171 class _Pred = std::equal_to<_Value>,
|
|
|
172 class _Alloc = std::allocator<_Value> >
|
|
|
173 class unordered_set
|
|
|
174 : public __unordered_set<_Value, _Hash, _Pred, _Alloc>
|
|
|
175 {
|
|
|
176 typedef __unordered_set<_Value, _Hash, _Pred, _Alloc> _Base;
|
|
|
177
|
|
|
178 public:
|
|
|
179 typedef typename _Base::value_type value_type;
|
|
|
180 typedef typename _Base::size_type size_type;
|
|
|
181 typedef typename _Base::hasher hasher;
|
|
|
182 typedef typename _Base::key_equal key_equal;
|
|
|
183 typedef typename _Base::allocator_type allocator_type;
|
|
|
184
|
|
|
185 explicit
|
|
|
186 unordered_set(size_type __n = 10,
|
|
|
187 const hasher& __hf = hasher(),
|
|
|
188 const key_equal& __eql = key_equal(),
|
|
|
189 const allocator_type& __a = allocator_type())
|
|
|
190 : _Base(__n, __hf, __eql, __a)
|
|
|
191 { }
|
|
|
192
|
|
|
193 template<typename _InputIterator>
|
|
|
194 unordered_set(_InputIterator __f, _InputIterator __l,
|
|
|
195 size_type __n = 10,
|
|
|
196 const hasher& __hf = hasher(),
|
|
|
197 const key_equal& __eql = key_equal(),
|
|
|
198 const allocator_type& __a = allocator_type())
|
|
|
199 : _Base(__f, __l, __n, __hf, __eql, __a)
|
|
|
200 { }
|
|
|
201 };
|
|
|
202
|
|
|
203 /**
|
|
|
204 * @brief A standard container composed of equivalent keys
|
|
|
205 * (possibly containing multiple of each key value) in which the
|
|
|
206 * elements' keys are the elements themselves.
|
|
|
207 *
|
|
|
208 * @ingroup unordered_associative_containers
|
|
|
209 *
|
|
|
210 * Meets the requirements of a <a href="tables.html#65">container</a>, and
|
|
|
211 * <a href="tables.html#xx">unordered associative container</a>
|
|
|
212 *
|
|
|
213 * @param Value Type of key objects.
|
|
|
214 * @param Hash Hashing function object type, defaults to hash<Value>.
|
|
|
215 * @param Pred Predicate function object type, defaults to equal_to<Value>.
|
|
|
216 * @param Alloc Allocator type, defaults to allocator<Key>.
|
|
|
217 */
|
|
|
218 template<class _Value,
|
|
|
219 class _Hash = hash<_Value>,
|
|
|
220 class _Pred = std::equal_to<_Value>,
|
|
|
221 class _Alloc = std::allocator<_Value> >
|
|
|
222 class unordered_multiset
|
|
|
223 : public __unordered_multiset<_Value, _Hash, _Pred, _Alloc>
|
|
|
224 {
|
|
|
225 typedef __unordered_multiset<_Value, _Hash, _Pred, _Alloc> _Base;
|
|
|
226
|
|
|
227 public:
|
|
|
228 typedef typename _Base::value_type value_type;
|
|
|
229 typedef typename _Base::size_type size_type;
|
|
|
230 typedef typename _Base::hasher hasher;
|
|
|
231 typedef typename _Base::key_equal key_equal;
|
|
|
232 typedef typename _Base::allocator_type allocator_type;
|
|
|
233
|
|
|
234 explicit
|
|
|
235 unordered_multiset(size_type __n = 10,
|
|
|
236 const hasher& __hf = hasher(),
|
|
|
237 const key_equal& __eql = key_equal(),
|
|
|
238 const allocator_type& __a = allocator_type())
|
|
|
239 : _Base(__n, __hf, __eql, __a)
|
|
|
240 { }
|
|
|
241
|
|
|
242
|
|
|
243 template<typename _InputIterator>
|
|
|
244 unordered_multiset(_InputIterator __f, _InputIterator __l,
|
|
|
245 typename _Base::size_type __n = 0,
|
|
|
246 const hasher& __hf = hasher(),
|
|
|
247 const key_equal& __eql = key_equal(),
|
|
|
248 const allocator_type& __a = allocator_type())
|
|
|
249 : _Base(__f, __l, __n, __hf, __eql, __a)
|
|
|
250 { }
|
|
|
251 };
|
|
|
252
|
|
|
253 template<class _Value, class _Hash, class _Pred, class _Alloc>
|
|
|
254 inline void
|
|
|
255 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
|
|
|
256 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
|
|
|
257 { __x.swap(__y); }
|
|
|
258
|
|
|
259 template<class _Value, class _Hash, class _Pred, class _Alloc>
|
|
|
260 inline void
|
|
|
261 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
|
|
|
262 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
|
|
|
263 { __x.swap(__y); }
|
|
|
264 }
|
|
|
265
|
|
|
266 _GLIBCXX_END_NAMESPACE_VERSION
|
|
|
267 }
|
