1 | // -*- C++ -*- |
2 | //===-------------------------- unordered_set -----------------------------===// |
3 | // |
4 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
5 | // See https://llvm.org/LICENSE.txt for license information. |
6 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
7 | // |
8 | //===----------------------------------------------------------------------===// |
9 | |
10 | #ifndef _LIBCPP_UNORDERED_SET |
11 | #define _LIBCPP_UNORDERED_SET |
12 | |
13 | /* |
14 | |
15 | unordered_set synopsis |
16 | |
17 | #include <initializer_list> |
18 | |
19 | namespace std |
20 | { |
21 | |
22 | template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, |
23 | class Alloc = allocator<Value>> |
24 | class unordered_set |
25 | { |
26 | public: |
27 | // types |
28 | typedef Value key_type; |
29 | typedef key_type value_type; |
30 | typedef Hash hasher; |
31 | typedef Pred key_equal; |
32 | typedef Alloc allocator_type; |
33 | typedef value_type& reference; |
34 | typedef const value_type& const_reference; |
35 | typedef typename allocator_traits<allocator_type>::pointer pointer; |
36 | typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; |
37 | typedef typename allocator_traits<allocator_type>::size_type size_type; |
38 | typedef typename allocator_traits<allocator_type>::difference_type difference_type; |
39 | |
40 | typedef /unspecified/ iterator; |
41 | typedef /unspecified/ const_iterator; |
42 | typedef /unspecified/ local_iterator; |
43 | typedef /unspecified/ const_local_iterator; |
44 | |
45 | typedef unspecified node_type unspecified; // C++17 |
46 | typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 |
47 | |
48 | unordered_set() |
49 | noexcept( |
50 | is_nothrow_default_constructible<hasher>::value && |
51 | is_nothrow_default_constructible<key_equal>::value && |
52 | is_nothrow_default_constructible<allocator_type>::value); |
53 | explicit unordered_set(size_type n, const hasher& hf = hasher(), |
54 | const key_equal& eql = key_equal(), |
55 | const allocator_type& a = allocator_type()); |
56 | template <class InputIterator> |
57 | unordered_set(InputIterator f, InputIterator l, |
58 | size_type n = 0, const hasher& hf = hasher(), |
59 | const key_equal& eql = key_equal(), |
60 | const allocator_type& a = allocator_type()); |
61 | explicit unordered_set(const allocator_type&); |
62 | unordered_set(const unordered_set&); |
63 | unordered_set(const unordered_set&, const Allocator&); |
64 | unordered_set(unordered_set&&) |
65 | noexcept( |
66 | is_nothrow_move_constructible<hasher>::value && |
67 | is_nothrow_move_constructible<key_equal>::value && |
68 | is_nothrow_move_constructible<allocator_type>::value); |
69 | unordered_set(unordered_set&&, const Allocator&); |
70 | unordered_set(initializer_list<value_type>, size_type n = 0, |
71 | const hasher& hf = hasher(), const key_equal& eql = key_equal(), |
72 | const allocator_type& a = allocator_type()); |
73 | unordered_set(size_type n, const allocator_type& a); // C++14 |
74 | unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14 |
75 | template <class InputIterator> |
76 | unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 |
77 | template <class InputIterator> |
78 | unordered_set(InputIterator f, InputIterator l, size_type n, |
79 | const hasher& hf, const allocator_type& a); // C++14 |
80 | unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 |
81 | unordered_set(initializer_list<value_type> il, size_type n, |
82 | const hasher& hf, const allocator_type& a); // C++14 |
83 | ~unordered_set(); |
84 | unordered_set& operator=(const unordered_set&); |
85 | unordered_set& operator=(unordered_set&&) |
86 | noexcept( |
87 | allocator_type::propagate_on_container_move_assignment::value && |
88 | is_nothrow_move_assignable<allocator_type>::value && |
89 | is_nothrow_move_assignable<hasher>::value && |
90 | is_nothrow_move_assignable<key_equal>::value); |
91 | unordered_set& operator=(initializer_list<value_type>); |
92 | |
93 | allocator_type get_allocator() const noexcept; |
94 | |
95 | bool empty() const noexcept; |
96 | size_type size() const noexcept; |
97 | size_type max_size() const noexcept; |
98 | |
99 | iterator begin() noexcept; |
100 | iterator end() noexcept; |
101 | const_iterator begin() const noexcept; |
102 | const_iterator end() const noexcept; |
103 | const_iterator cbegin() const noexcept; |
104 | const_iterator cend() const noexcept; |
105 | |
106 | template <class... Args> |
107 | pair<iterator, bool> emplace(Args&&... args); |
108 | template <class... Args> |
109 | iterator emplace_hint(const_iterator position, Args&&... args); |
110 | pair<iterator, bool> insert(const value_type& obj); |
111 | pair<iterator, bool> insert(value_type&& obj); |
112 | iterator insert(const_iterator hint, const value_type& obj); |
113 | iterator insert(const_iterator hint, value_type&& obj); |
114 | template <class InputIterator> |
115 | void insert(InputIterator first, InputIterator last); |
116 | void insert(initializer_list<value_type>); |
117 | |
118 | node_type extract(const_iterator position); // C++17 |
119 | node_type extract(const key_type& x); // C++17 |
120 | insert_return_type insert(node_type&& nh); // C++17 |
121 | iterator insert(const_iterator hint, node_type&& nh); // C++17 |
122 | |
123 | iterator erase(const_iterator position); |
124 | iterator erase(iterator position); // C++14 |
125 | size_type erase(const key_type& k); |
126 | iterator erase(const_iterator first, const_iterator last); |
127 | void clear() noexcept; |
128 | |
129 | template<class H2, class P2> |
130 | void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 |
131 | template<class H2, class P2> |
132 | void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 |
133 | template<class H2, class P2> |
134 | void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 |
135 | template<class H2, class P2> |
136 | void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 |
137 | |
138 | void swap(unordered_set&) |
139 | noexcept(allocator_traits<Allocator>::is_always_equal::value && |
140 | noexcept(swap(declval<hasher&>(), declval<hasher&>())) && |
141 | noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 |
142 | |
143 | hasher hash_function() const; |
144 | key_equal key_eq() const; |
145 | |
146 | iterator find(const key_type& k); |
147 | const_iterator find(const key_type& k) const; |
148 | size_type count(const key_type& k) const; |
149 | bool contains(const key_type& k) const; // C++20 |
150 | pair<iterator, iterator> equal_range(const key_type& k); |
151 | pair<const_iterator, const_iterator> equal_range(const key_type& k) const; |
152 | |
153 | size_type bucket_count() const noexcept; |
154 | size_type max_bucket_count() const noexcept; |
155 | |
156 | size_type bucket_size(size_type n) const; |
157 | size_type bucket(const key_type& k) const; |
158 | |
159 | local_iterator begin(size_type n); |
160 | local_iterator end(size_type n); |
161 | const_local_iterator begin(size_type n) const; |
162 | const_local_iterator end(size_type n) const; |
163 | const_local_iterator cbegin(size_type n) const; |
164 | const_local_iterator cend(size_type n) const; |
165 | |
166 | float load_factor() const noexcept; |
167 | float max_load_factor() const noexcept; |
168 | void max_load_factor(float z); |
169 | void rehash(size_type n); |
170 | void reserve(size_type n); |
171 | }; |
172 | |
173 | template <class Value, class Hash, class Pred, class Alloc> |
174 | void swap(unordered_set<Value, Hash, Pred, Alloc>& x, |
175 | unordered_set<Value, Hash, Pred, Alloc>& y) |
176 | noexcept(noexcept(x.swap(y))); |
177 | |
178 | template <class Value, class Hash, class Pred, class Alloc> |
179 | bool |
180 | operator==(const unordered_set<Value, Hash, Pred, Alloc>& x, |
181 | const unordered_set<Value, Hash, Pred, Alloc>& y); |
182 | |
183 | template <class Value, class Hash, class Pred, class Alloc> |
184 | bool |
185 | operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x, |
186 | const unordered_set<Value, Hash, Pred, Alloc>& y); |
187 | |
188 | template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>, |
189 | class Alloc = allocator<Value>> |
190 | class unordered_multiset |
191 | { |
192 | public: |
193 | // types |
194 | typedef Value key_type; |
195 | typedef key_type value_type; |
196 | typedef Hash hasher; |
197 | typedef Pred key_equal; |
198 | typedef Alloc allocator_type; |
199 | typedef value_type& reference; |
200 | typedef const value_type& const_reference; |
201 | typedef typename allocator_traits<allocator_type>::pointer pointer; |
202 | typedef typename allocator_traits<allocator_type>::const_pointer const_pointer; |
203 | typedef typename allocator_traits<allocator_type>::size_type size_type; |
204 | typedef typename allocator_traits<allocator_type>::difference_type difference_type; |
205 | |
206 | typedef /unspecified/ iterator; |
207 | typedef /unspecified/ const_iterator; |
208 | typedef /unspecified/ local_iterator; |
209 | typedef /unspecified/ const_local_iterator; |
210 | |
211 | typedef unspecified node_type unspecified; // C++17 |
212 | |
213 | unordered_multiset() |
214 | noexcept( |
215 | is_nothrow_default_constructible<hasher>::value && |
216 | is_nothrow_default_constructible<key_equal>::value && |
217 | is_nothrow_default_constructible<allocator_type>::value); |
218 | explicit unordered_multiset(size_type n, const hasher& hf = hasher(), |
219 | const key_equal& eql = key_equal(), |
220 | const allocator_type& a = allocator_type()); |
221 | template <class InputIterator> |
222 | unordered_multiset(InputIterator f, InputIterator l, |
223 | size_type n = 0, const hasher& hf = hasher(), |
224 | const key_equal& eql = key_equal(), |
225 | const allocator_type& a = allocator_type()); |
226 | explicit unordered_multiset(const allocator_type&); |
227 | unordered_multiset(const unordered_multiset&); |
228 | unordered_multiset(const unordered_multiset&, const Allocator&); |
229 | unordered_multiset(unordered_multiset&&) |
230 | noexcept( |
231 | is_nothrow_move_constructible<hasher>::value && |
232 | is_nothrow_move_constructible<key_equal>::value && |
233 | is_nothrow_move_constructible<allocator_type>::value); |
234 | unordered_multiset(unordered_multiset&&, const Allocator&); |
235 | unordered_multiset(initializer_list<value_type>, size_type n = /see below/, |
236 | const hasher& hf = hasher(), const key_equal& eql = key_equal(), |
237 | const allocator_type& a = allocator_type()); |
238 | unordered_multiset(size_type n, const allocator_type& a); // C++14 |
239 | unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14 |
240 | template <class InputIterator> |
241 | unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14 |
242 | template <class InputIterator> |
243 | unordered_multiset(InputIterator f, InputIterator l, size_type n, |
244 | const hasher& hf, const allocator_type& a); // C++14 |
245 | unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14 |
246 | unordered_multiset(initializer_list<value_type> il, size_type n, |
247 | const hasher& hf, const allocator_type& a); // C++14 |
248 | ~unordered_multiset(); |
249 | unordered_multiset& operator=(const unordered_multiset&); |
250 | unordered_multiset& operator=(unordered_multiset&&) |
251 | noexcept( |
252 | allocator_type::propagate_on_container_move_assignment::value && |
253 | is_nothrow_move_assignable<allocator_type>::value && |
254 | is_nothrow_move_assignable<hasher>::value && |
255 | is_nothrow_move_assignable<key_equal>::value); |
256 | unordered_multiset& operator=(initializer_list<value_type>); |
257 | |
258 | allocator_type get_allocator() const noexcept; |
259 | |
260 | bool empty() const noexcept; |
261 | size_type size() const noexcept; |
262 | size_type max_size() const noexcept; |
263 | |
264 | iterator begin() noexcept; |
265 | iterator end() noexcept; |
266 | const_iterator begin() const noexcept; |
267 | const_iterator end() const noexcept; |
268 | const_iterator cbegin() const noexcept; |
269 | const_iterator cend() const noexcept; |
270 | |
271 | template <class... Args> |
272 | iterator emplace(Args&&... args); |
273 | template <class... Args> |
274 | iterator emplace_hint(const_iterator position, Args&&... args); |
275 | iterator insert(const value_type& obj); |
276 | iterator insert(value_type&& obj); |
277 | iterator insert(const_iterator hint, const value_type& obj); |
278 | iterator insert(const_iterator hint, value_type&& obj); |
279 | template <class InputIterator> |
280 | void insert(InputIterator first, InputIterator last); |
281 | void insert(initializer_list<value_type>); |
282 | |
283 | node_type extract(const_iterator position); // C++17 |
284 | node_type extract(const key_type& x); // C++17 |
285 | iterator insert(node_type&& nh); // C++17 |
286 | iterator insert(const_iterator hint, node_type&& nh); // C++17 |
287 | |
288 | iterator erase(const_iterator position); |
289 | iterator erase(iterator position); // C++14 |
290 | size_type erase(const key_type& k); |
291 | iterator erase(const_iterator first, const_iterator last); |
292 | void clear() noexcept; |
293 | |
294 | template<class H2, class P2> |
295 | void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17 |
296 | template<class H2, class P2> |
297 | void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17 |
298 | template<class H2, class P2> |
299 | void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17 |
300 | template<class H2, class P2> |
301 | void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17 |
302 | |
303 | void swap(unordered_multiset&) |
304 | noexcept(allocator_traits<Allocator>::is_always_equal::value && |
305 | noexcept(swap(declval<hasher&>(), declval<hasher&>())) && |
306 | noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17 |
307 | |
308 | hasher hash_function() const; |
309 | key_equal key_eq() const; |
310 | |
311 | iterator find(const key_type& k); |
312 | const_iterator find(const key_type& k) const; |
313 | size_type count(const key_type& k) const; |
314 | bool contains(const key_type& k) const; // C++20 |
315 | pair<iterator, iterator> equal_range(const key_type& k); |
316 | pair<const_iterator, const_iterator> equal_range(const key_type& k) const; |
317 | |
318 | size_type bucket_count() const noexcept; |
319 | size_type max_bucket_count() const noexcept; |
320 | |
321 | size_type bucket_size(size_type n) const; |
322 | size_type bucket(const key_type& k) const; |
323 | |
324 | local_iterator begin(size_type n); |
325 | local_iterator end(size_type n); |
326 | const_local_iterator begin(size_type n) const; |
327 | const_local_iterator end(size_type n) const; |
328 | const_local_iterator cbegin(size_type n) const; |
329 | const_local_iterator cend(size_type n) const; |
330 | |
331 | float load_factor() const noexcept; |
332 | float max_load_factor() const noexcept; |
333 | void max_load_factor(float z); |
334 | void rehash(size_type n); |
335 | void reserve(size_type n); |
336 | }; |
337 | |
338 | template <class Value, class Hash, class Pred, class Alloc> |
339 | void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x, |
340 | unordered_multiset<Value, Hash, Pred, Alloc>& y) |
341 | noexcept(noexcept(x.swap(y))); |
342 | |
343 | template <class K, class T, class H, class P, class A, class Predicate> |
344 | void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20 |
345 | |
346 | template <class K, class T, class H, class P, class A, class Predicate> |
347 | void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20 |
348 | |
349 | |
350 | template <class Value, class Hash, class Pred, class Alloc> |
351 | bool |
352 | operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x, |
353 | const unordered_multiset<Value, Hash, Pred, Alloc>& y); |
354 | |
355 | template <class Value, class Hash, class Pred, class Alloc> |
356 | bool |
357 | operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x, |
358 | const unordered_multiset<Value, Hash, Pred, Alloc>& y); |
359 | } // std |
360 | |
361 | */ |
362 | |
363 | #include <__config> |
364 | #include <__hash_table> |
365 | #include <__node_handle> |
366 | #include <functional> |
367 | #include <version> |
368 | |
369 | #include <__debug> |
370 | |
371 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
372 | #pragma GCC system_header |
373 | #endif |
374 | |
375 | _LIBCPP_BEGIN_NAMESPACE_STD |
376 | |
377 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
378 | class unordered_multiset; |
379 | |
380 | template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, |
381 | class _Alloc = allocator<_Value> > |
382 | class _LIBCPP_TEMPLATE_VIS unordered_set |
383 | { |
384 | public: |
385 | // types |
386 | typedef _Value key_type; |
387 | typedef key_type value_type; |
388 | typedef typename __identity<_Hash>::type hasher; |
389 | typedef typename __identity<_Pred>::type key_equal; |
390 | typedef typename __identity<_Alloc>::type allocator_type; |
391 | typedef value_type& reference; |
392 | typedef const value_type& const_reference; |
393 | static_assert((is_same<value_type, typename allocator_type::value_type>::value), |
394 | "Invalid allocator::value_type" ); |
395 | |
396 | private: |
397 | typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; |
398 | |
399 | __table __table_; |
400 | |
401 | public: |
402 | typedef typename __table::pointer pointer; |
403 | typedef typename __table::const_pointer const_pointer; |
404 | typedef typename __table::size_type size_type; |
405 | typedef typename __table::difference_type difference_type; |
406 | |
407 | typedef typename __table::const_iterator iterator; |
408 | typedef typename __table::const_iterator const_iterator; |
409 | typedef typename __table::const_local_iterator local_iterator; |
410 | typedef typename __table::const_local_iterator const_local_iterator; |
411 | |
412 | #if _LIBCPP_STD_VER > 14 |
413 | typedef __set_node_handle<typename __table::__node, allocator_type> node_type; |
414 | typedef __insert_return_type<iterator, node_type> insert_return_type; |
415 | #endif |
416 | |
417 | template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> |
418 | friend class _LIBCPP_TEMPLATE_VIS unordered_set; |
419 | template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> |
420 | friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; |
421 | |
422 | _LIBCPP_INLINE_VISIBILITY |
423 | unordered_set() |
424 | _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) |
425 | { |
426 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
427 | __get_db()->__insert_c(this); |
428 | #endif |
429 | } |
430 | explicit unordered_set(size_type __n, const hasher& __hf = hasher(), |
431 | const key_equal& __eql = key_equal()); |
432 | #if _LIBCPP_STD_VER > 11 |
433 | inline _LIBCPP_INLINE_VISIBILITY |
434 | unordered_set(size_type __n, const allocator_type& __a) |
435 | : unordered_set(__n, hasher(), key_equal(), __a) {} |
436 | inline _LIBCPP_INLINE_VISIBILITY |
437 | unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a) |
438 | : unordered_set(__n, __hf, key_equal(), __a) {} |
439 | #endif |
440 | unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql, |
441 | const allocator_type& __a); |
442 | template <class _InputIterator> |
443 | unordered_set(_InputIterator __first, _InputIterator __last); |
444 | template <class _InputIterator> |
445 | unordered_set(_InputIterator __first, _InputIterator __last, |
446 | size_type __n, const hasher& __hf = hasher(), |
447 | const key_equal& __eql = key_equal()); |
448 | template <class _InputIterator> |
449 | unordered_set(_InputIterator __first, _InputIterator __last, |
450 | size_type __n, const hasher& __hf, const key_equal& __eql, |
451 | const allocator_type& __a); |
452 | #if _LIBCPP_STD_VER > 11 |
453 | template <class _InputIterator> |
454 | inline _LIBCPP_INLINE_VISIBILITY |
455 | unordered_set(_InputIterator __first, _InputIterator __last, |
456 | size_type __n, const allocator_type& __a) |
457 | : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {} |
458 | template <class _InputIterator> |
459 | unordered_set(_InputIterator __first, _InputIterator __last, |
460 | size_type __n, const hasher& __hf, const allocator_type& __a) |
461 | : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {} |
462 | #endif |
463 | _LIBCPP_INLINE_VISIBILITY |
464 | explicit unordered_set(const allocator_type& __a); |
465 | unordered_set(const unordered_set& __u); |
466 | unordered_set(const unordered_set& __u, const allocator_type& __a); |
467 | #ifndef _LIBCPP_CXX03_LANG |
468 | _LIBCPP_INLINE_VISIBILITY |
469 | unordered_set(unordered_set&& __u) |
470 | _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); |
471 | unordered_set(unordered_set&& __u, const allocator_type& __a); |
472 | unordered_set(initializer_list<value_type> __il); |
473 | unordered_set(initializer_list<value_type> __il, size_type __n, |
474 | const hasher& __hf = hasher(), |
475 | const key_equal& __eql = key_equal()); |
476 | unordered_set(initializer_list<value_type> __il, size_type __n, |
477 | const hasher& __hf, const key_equal& __eql, |
478 | const allocator_type& __a); |
479 | #if _LIBCPP_STD_VER > 11 |
480 | inline _LIBCPP_INLINE_VISIBILITY |
481 | unordered_set(initializer_list<value_type> __il, size_type __n, |
482 | const allocator_type& __a) |
483 | : unordered_set(__il, __n, hasher(), key_equal(), __a) {} |
484 | inline _LIBCPP_INLINE_VISIBILITY |
485 | unordered_set(initializer_list<value_type> __il, size_type __n, |
486 | const hasher& __hf, const allocator_type& __a) |
487 | : unordered_set(__il, __n, __hf, key_equal(), __a) {} |
488 | #endif |
489 | #endif // _LIBCPP_CXX03_LANG |
490 | _LIBCPP_INLINE_VISIBILITY |
491 | ~unordered_set() { |
492 | static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "" ); |
493 | } |
494 | |
495 | _LIBCPP_INLINE_VISIBILITY |
496 | unordered_set& operator=(const unordered_set& __u) |
497 | { |
498 | __table_ = __u.__table_; |
499 | return *this; |
500 | } |
501 | #ifndef _LIBCPP_CXX03_LANG |
502 | _LIBCPP_INLINE_VISIBILITY |
503 | unordered_set& operator=(unordered_set&& __u) |
504 | _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); |
505 | _LIBCPP_INLINE_VISIBILITY |
506 | unordered_set& operator=(initializer_list<value_type> __il); |
507 | #endif // _LIBCPP_CXX03_LANG |
508 | |
509 | _LIBCPP_INLINE_VISIBILITY |
510 | allocator_type get_allocator() const _NOEXCEPT |
511 | {return allocator_type(__table_.__node_alloc());} |
512 | |
513 | _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY |
514 | bool empty() const _NOEXCEPT {return __table_.size() == 0;} |
515 | _LIBCPP_INLINE_VISIBILITY |
516 | size_type size() const _NOEXCEPT {return __table_.size();} |
517 | _LIBCPP_INLINE_VISIBILITY |
518 | size_type max_size() const _NOEXCEPT {return __table_.max_size();} |
519 | |
520 | _LIBCPP_INLINE_VISIBILITY |
521 | iterator begin() _NOEXCEPT {return __table_.begin();} |
522 | _LIBCPP_INLINE_VISIBILITY |
523 | iterator end() _NOEXCEPT {return __table_.end();} |
524 | _LIBCPP_INLINE_VISIBILITY |
525 | const_iterator begin() const _NOEXCEPT {return __table_.begin();} |
526 | _LIBCPP_INLINE_VISIBILITY |
527 | const_iterator end() const _NOEXCEPT {return __table_.end();} |
528 | _LIBCPP_INLINE_VISIBILITY |
529 | const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} |
530 | _LIBCPP_INLINE_VISIBILITY |
531 | const_iterator cend() const _NOEXCEPT {return __table_.end();} |
532 | |
533 | #ifndef _LIBCPP_CXX03_LANG |
534 | template <class... _Args> |
535 | _LIBCPP_INLINE_VISIBILITY |
536 | pair<iterator, bool> emplace(_Args&&... __args) |
537 | {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} |
538 | template <class... _Args> |
539 | _LIBCPP_INLINE_VISIBILITY |
540 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
541 | iterator emplace_hint(const_iterator __p, _Args&&... __args) |
542 | { |
543 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, |
544 | "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not" |
545 | " referring to this unordered_set" ); |
546 | return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first; |
547 | } |
548 | #else |
549 | iterator emplace_hint(const_iterator, _Args&&... __args) |
550 | {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;} |
551 | #endif |
552 | |
553 | _LIBCPP_INLINE_VISIBILITY |
554 | pair<iterator, bool> insert(value_type&& __x) |
555 | {return __table_.__insert_unique(_VSTD::move(__x));} |
556 | _LIBCPP_INLINE_VISIBILITY |
557 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
558 | iterator insert(const_iterator __p, value_type&& __x) |
559 | { |
560 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, |
561 | "unordered_set::insert(const_iterator, value_type&&) called with an iterator not" |
562 | " referring to this unordered_set" ); |
563 | return insert(_VSTD::move(__x)).first; |
564 | } |
565 | #else |
566 | iterator insert(const_iterator, value_type&& __x) |
567 | {return insert(_VSTD::move(__x)).first;} |
568 | #endif |
569 | _LIBCPP_INLINE_VISIBILITY |
570 | void insert(initializer_list<value_type> __il) |
571 | {insert(__il.begin(), __il.end());} |
572 | #endif // _LIBCPP_CXX03_LANG |
573 | _LIBCPP_INLINE_VISIBILITY |
574 | pair<iterator, bool> insert(const value_type& __x) |
575 | {return __table_.__insert_unique(__x);} |
576 | |
577 | _LIBCPP_INLINE_VISIBILITY |
578 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
579 | iterator insert(const_iterator __p, const value_type& __x) |
580 | { |
581 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this, |
582 | "unordered_set::insert(const_iterator, const value_type&) called with an iterator not" |
583 | " referring to this unordered_set" ); |
584 | return insert(__x).first; |
585 | } |
586 | #else |
587 | iterator insert(const_iterator, const value_type& __x) |
588 | {return insert(__x).first;} |
589 | #endif |
590 | template <class _InputIterator> |
591 | _LIBCPP_INLINE_VISIBILITY |
592 | void insert(_InputIterator __first, _InputIterator __last); |
593 | |
594 | _LIBCPP_INLINE_VISIBILITY |
595 | iterator erase(const_iterator __p) {return __table_.erase(__p);} |
596 | _LIBCPP_INLINE_VISIBILITY |
597 | size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);} |
598 | _LIBCPP_INLINE_VISIBILITY |
599 | iterator erase(const_iterator __first, const_iterator __last) |
600 | {return __table_.erase(__first, __last);} |
601 | _LIBCPP_INLINE_VISIBILITY |
602 | void clear() _NOEXCEPT {__table_.clear();} |
603 | |
604 | #if _LIBCPP_STD_VER > 14 |
605 | _LIBCPP_INLINE_VISIBILITY |
606 | insert_return_type insert(node_type&& __nh) |
607 | { |
608 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
609 | "node_type with incompatible allocator passed to unordered_set::insert()" ); |
610 | return __table_.template __node_handle_insert_unique< |
611 | node_type, insert_return_type>(_VSTD::move(__nh)); |
612 | } |
613 | _LIBCPP_INLINE_VISIBILITY |
614 | iterator insert(const_iterator __h, node_type&& __nh) |
615 | { |
616 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
617 | "node_type with incompatible allocator passed to unordered_set::insert()" ); |
618 | return __table_.template __node_handle_insert_unique<node_type>( |
619 | __h, _VSTD::move(__nh)); |
620 | } |
621 | _LIBCPP_INLINE_VISIBILITY |
622 | node_type (key_type const& __key) |
623 | { |
624 | return __table_.template __node_handle_extract<node_type>(__key); |
625 | } |
626 | _LIBCPP_INLINE_VISIBILITY |
627 | node_type (const_iterator __it) |
628 | { |
629 | return __table_.template __node_handle_extract<node_type>(__it); |
630 | } |
631 | |
632 | template<class _H2, class _P2> |
633 | _LIBCPP_INLINE_VISIBILITY |
634 | void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) |
635 | { |
636 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
637 | "merging container with incompatible allocator" ); |
638 | __table_.__node_handle_merge_unique(__source.__table_); |
639 | } |
640 | template<class _H2, class _P2> |
641 | _LIBCPP_INLINE_VISIBILITY |
642 | void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) |
643 | { |
644 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
645 | "merging container with incompatible allocator" ); |
646 | __table_.__node_handle_merge_unique(__source.__table_); |
647 | } |
648 | template<class _H2, class _P2> |
649 | _LIBCPP_INLINE_VISIBILITY |
650 | void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) |
651 | { |
652 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
653 | "merging container with incompatible allocator" ); |
654 | __table_.__node_handle_merge_unique(__source.__table_); |
655 | } |
656 | template<class _H2, class _P2> |
657 | _LIBCPP_INLINE_VISIBILITY |
658 | void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) |
659 | { |
660 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
661 | "merging container with incompatible allocator" ); |
662 | __table_.__node_handle_merge_unique(__source.__table_); |
663 | } |
664 | #endif |
665 | |
666 | _LIBCPP_INLINE_VISIBILITY |
667 | void swap(unordered_set& __u) |
668 | _NOEXCEPT_(__is_nothrow_swappable<__table>::value) |
669 | {__table_.swap(__u.__table_);} |
670 | |
671 | _LIBCPP_INLINE_VISIBILITY |
672 | hasher hash_function() const {return __table_.hash_function();} |
673 | _LIBCPP_INLINE_VISIBILITY |
674 | key_equal key_eq() const {return __table_.key_eq();} |
675 | |
676 | _LIBCPP_INLINE_VISIBILITY |
677 | iterator find(const key_type& __k) {return __table_.find(__k);} |
678 | _LIBCPP_INLINE_VISIBILITY |
679 | const_iterator find(const key_type& __k) const {return __table_.find(__k);} |
680 | _LIBCPP_INLINE_VISIBILITY |
681 | size_type count(const key_type& __k) const {return __table_.__count_unique(__k);} |
682 | #if _LIBCPP_STD_VER > 17 |
683 | _LIBCPP_INLINE_VISIBILITY |
684 | bool contains(const key_type& __k) const {return find(__k) != end();} |
685 | #endif // _LIBCPP_STD_VER > 17 |
686 | _LIBCPP_INLINE_VISIBILITY |
687 | pair<iterator, iterator> equal_range(const key_type& __k) |
688 | {return __table_.__equal_range_unique(__k);} |
689 | _LIBCPP_INLINE_VISIBILITY |
690 | pair<const_iterator, const_iterator> equal_range(const key_type& __k) const |
691 | {return __table_.__equal_range_unique(__k);} |
692 | |
693 | _LIBCPP_INLINE_VISIBILITY |
694 | size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} |
695 | _LIBCPP_INLINE_VISIBILITY |
696 | size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} |
697 | |
698 | _LIBCPP_INLINE_VISIBILITY |
699 | size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} |
700 | _LIBCPP_INLINE_VISIBILITY |
701 | size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} |
702 | |
703 | _LIBCPP_INLINE_VISIBILITY |
704 | local_iterator begin(size_type __n) {return __table_.begin(__n);} |
705 | _LIBCPP_INLINE_VISIBILITY |
706 | local_iterator end(size_type __n) {return __table_.end(__n);} |
707 | _LIBCPP_INLINE_VISIBILITY |
708 | const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} |
709 | _LIBCPP_INLINE_VISIBILITY |
710 | const_local_iterator end(size_type __n) const {return __table_.cend(__n);} |
711 | _LIBCPP_INLINE_VISIBILITY |
712 | const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} |
713 | _LIBCPP_INLINE_VISIBILITY |
714 | const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} |
715 | |
716 | _LIBCPP_INLINE_VISIBILITY |
717 | float load_factor() const _NOEXCEPT {return __table_.load_factor();} |
718 | _LIBCPP_INLINE_VISIBILITY |
719 | float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} |
720 | _LIBCPP_INLINE_VISIBILITY |
721 | void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} |
722 | _LIBCPP_INLINE_VISIBILITY |
723 | void rehash(size_type __n) {__table_.rehash(__n);} |
724 | _LIBCPP_INLINE_VISIBILITY |
725 | void reserve(size_type __n) {__table_.reserve(__n);} |
726 | |
727 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
728 | |
729 | bool __dereferenceable(const const_iterator* __i) const |
730 | {return __table_.__dereferenceable(__i);} |
731 | bool __decrementable(const const_iterator* __i) const |
732 | {return __table_.__decrementable(__i);} |
733 | bool __addable(const const_iterator* __i, ptrdiff_t __n) const |
734 | {return __table_.__addable(__i, __n);} |
735 | bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const |
736 | {return __table_.__addable(__i, __n);} |
737 | |
738 | #endif // _LIBCPP_DEBUG_LEVEL >= 2 |
739 | |
740 | }; |
741 | |
742 | #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES |
743 | template<class _InputIterator, |
744 | class _Hash = hash<__iter_value_type<_InputIterator>>, |
745 | class _Pred = equal_to<__iter_value_type<_InputIterator>>, |
746 | class _Allocator = allocator<__iter_value_type<_InputIterator>>, |
747 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
748 | class = _EnableIf<!is_integral<_Hash>::value>, |
749 | class = _EnableIf<!__is_allocator<_Pred>::value>, |
750 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
751 | unordered_set(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, |
752 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) |
753 | -> unordered_set<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; |
754 | |
755 | template<class _Tp, class _Hash = hash<_Tp>, |
756 | class _Pred = equal_to<_Tp>, |
757 | class _Allocator = allocator<_Tp>, |
758 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
759 | class = _EnableIf<!is_integral<_Hash>::value>, |
760 | class = _EnableIf<!__is_allocator<_Pred>::value>, |
761 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
762 | unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, |
763 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) |
764 | -> unordered_set<_Tp, _Hash, _Pred, _Allocator>; |
765 | |
766 | template<class _InputIterator, class _Allocator, |
767 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
768 | unordered_set(_InputIterator, _InputIterator, |
769 | typename allocator_traits<_Allocator>::size_type, _Allocator) |
770 | -> unordered_set<__iter_value_type<_InputIterator>, |
771 | hash<__iter_value_type<_InputIterator>>, |
772 | equal_to<__iter_value_type<_InputIterator>>, |
773 | _Allocator>; |
774 | |
775 | template<class _InputIterator, class _Hash, class _Allocator, |
776 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
777 | class = _EnableIf<!is_integral<_Hash>::value>, |
778 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
779 | unordered_set(_InputIterator, _InputIterator, |
780 | typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) |
781 | -> unordered_set<__iter_value_type<_InputIterator>, _Hash, |
782 | equal_to<__iter_value_type<_InputIterator>>, |
783 | _Allocator>; |
784 | |
785 | template<class _Tp, class _Allocator, |
786 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
787 | unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) |
788 | -> unordered_set<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; |
789 | |
790 | template<class _Tp, class _Hash, class _Allocator, |
791 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
792 | class = _EnableIf<!is_integral<_Hash>::value>, |
793 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
794 | unordered_set(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) |
795 | -> unordered_set<_Tp, _Hash, equal_to<_Tp>, _Allocator>; |
796 | #endif |
797 | |
798 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
799 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, |
800 | const hasher& __hf, const key_equal& __eql) |
801 | : __table_(__hf, __eql) |
802 | { |
803 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
804 | __get_db()->__insert_c(this); |
805 | #endif |
806 | __table_.rehash(__n); |
807 | } |
808 | |
809 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
810 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n, |
811 | const hasher& __hf, const key_equal& __eql, const allocator_type& __a) |
812 | : __table_(__hf, __eql, __a) |
813 | { |
814 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
815 | __get_db()->__insert_c(this); |
816 | #endif |
817 | __table_.rehash(__n); |
818 | } |
819 | |
820 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
821 | template <class _InputIterator> |
822 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
823 | _InputIterator __first, _InputIterator __last) |
824 | { |
825 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
826 | __get_db()->__insert_c(this); |
827 | #endif |
828 | insert(__first, __last); |
829 | } |
830 | |
831 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
832 | template <class _InputIterator> |
833 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
834 | _InputIterator __first, _InputIterator __last, size_type __n, |
835 | const hasher& __hf, const key_equal& __eql) |
836 | : __table_(__hf, __eql) |
837 | { |
838 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
839 | __get_db()->__insert_c(this); |
840 | #endif |
841 | __table_.rehash(__n); |
842 | insert(__first, __last); |
843 | } |
844 | |
845 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
846 | template <class _InputIterator> |
847 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
848 | _InputIterator __first, _InputIterator __last, size_type __n, |
849 | const hasher& __hf, const key_equal& __eql, const allocator_type& __a) |
850 | : __table_(__hf, __eql, __a) |
851 | { |
852 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
853 | __get_db()->__insert_c(this); |
854 | #endif |
855 | __table_.rehash(__n); |
856 | insert(__first, __last); |
857 | } |
858 | |
859 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
860 | inline |
861 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
862 | const allocator_type& __a) |
863 | : __table_(__a) |
864 | { |
865 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
866 | __get_db()->__insert_c(this); |
867 | #endif |
868 | } |
869 | |
870 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
871 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
872 | const unordered_set& __u) |
873 | : __table_(__u.__table_) |
874 | { |
875 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
876 | __get_db()->__insert_c(this); |
877 | #endif |
878 | __table_.rehash(__u.bucket_count()); |
879 | insert(__u.begin(), __u.end()); |
880 | } |
881 | |
882 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
883 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
884 | const unordered_set& __u, const allocator_type& __a) |
885 | : __table_(__u.__table_, __a) |
886 | { |
887 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
888 | __get_db()->__insert_c(this); |
889 | #endif |
890 | __table_.rehash(__u.bucket_count()); |
891 | insert(__u.begin(), __u.end()); |
892 | } |
893 | |
894 | #ifndef _LIBCPP_CXX03_LANG |
895 | |
896 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
897 | inline |
898 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
899 | unordered_set&& __u) |
900 | _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) |
901 | : __table_(_VSTD::move(__u.__table_)) |
902 | { |
903 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
904 | __get_db()->__insert_c(this); |
905 | __get_db()->swap(this, &__u); |
906 | #endif |
907 | } |
908 | |
909 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
910 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
911 | unordered_set&& __u, const allocator_type& __a) |
912 | : __table_(_VSTD::move(__u.__table_), __a) |
913 | { |
914 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
915 | __get_db()->__insert_c(this); |
916 | #endif |
917 | if (__a != __u.get_allocator()) |
918 | { |
919 | iterator __i = __u.begin(); |
920 | while (__u.size() != 0) |
921 | __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_)); |
922 | } |
923 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
924 | else |
925 | __get_db()->swap(this, &__u); |
926 | #endif |
927 | } |
928 | |
929 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
930 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
931 | initializer_list<value_type> __il) |
932 | { |
933 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
934 | __get_db()->__insert_c(this); |
935 | #endif |
936 | insert(__il.begin(), __il.end()); |
937 | } |
938 | |
939 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
940 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
941 | initializer_list<value_type> __il, size_type __n, const hasher& __hf, |
942 | const key_equal& __eql) |
943 | : __table_(__hf, __eql) |
944 | { |
945 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
946 | __get_db()->__insert_c(this); |
947 | #endif |
948 | __table_.rehash(__n); |
949 | insert(__il.begin(), __il.end()); |
950 | } |
951 | |
952 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
953 | unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set( |
954 | initializer_list<value_type> __il, size_type __n, const hasher& __hf, |
955 | const key_equal& __eql, const allocator_type& __a) |
956 | : __table_(__hf, __eql, __a) |
957 | { |
958 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
959 | __get_db()->__insert_c(this); |
960 | #endif |
961 | __table_.rehash(__n); |
962 | insert(__il.begin(), __il.end()); |
963 | } |
964 | |
965 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
966 | inline |
967 | unordered_set<_Value, _Hash, _Pred, _Alloc>& |
968 | unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u) |
969 | _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) |
970 | { |
971 | __table_ = _VSTD::move(__u.__table_); |
972 | return *this; |
973 | } |
974 | |
975 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
976 | inline |
977 | unordered_set<_Value, _Hash, _Pred, _Alloc>& |
978 | unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=( |
979 | initializer_list<value_type> __il) |
980 | { |
981 | __table_.__assign_unique(__il.begin(), __il.end()); |
982 | return *this; |
983 | } |
984 | |
985 | #endif // _LIBCPP_CXX03_LANG |
986 | |
987 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
988 | template <class _InputIterator> |
989 | inline |
990 | void |
991 | unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, |
992 | _InputIterator __last) |
993 | { |
994 | for (; __first != __last; ++__first) |
995 | __table_.__insert_unique(*__first); |
996 | } |
997 | |
998 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
999 | inline _LIBCPP_INLINE_VISIBILITY |
1000 | void |
1001 | swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, |
1002 | unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) |
1003 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
1004 | { |
1005 | __x.swap(__y); |
1006 | } |
1007 | |
1008 | #if _LIBCPP_STD_VER > 17 |
1009 | template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> |
1010 | inline _LIBCPP_INLINE_VISIBILITY |
1011 | void erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) |
1012 | { __libcpp_erase_if_container(__c, __pred); } |
1013 | #endif |
1014 | |
1015 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1016 | bool |
1017 | operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, |
1018 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) |
1019 | { |
1020 | if (__x.size() != __y.size()) |
1021 | return false; |
1022 | typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator |
1023 | const_iterator; |
1024 | for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end(); |
1025 | __i != __ex; ++__i) |
1026 | { |
1027 | const_iterator __j = __y.find(*__i); |
1028 | if (__j == __ey || !(*__i == *__j)) |
1029 | return false; |
1030 | } |
1031 | return true; |
1032 | } |
1033 | |
1034 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1035 | inline _LIBCPP_INLINE_VISIBILITY |
1036 | bool |
1037 | operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x, |
1038 | const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y) |
1039 | { |
1040 | return !(__x == __y); |
1041 | } |
1042 | |
1043 | template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>, |
1044 | class _Alloc = allocator<_Value> > |
1045 | class _LIBCPP_TEMPLATE_VIS unordered_multiset |
1046 | { |
1047 | public: |
1048 | // types |
1049 | typedef _Value key_type; |
1050 | typedef key_type value_type; |
1051 | typedef typename __identity<_Hash>::type hasher; |
1052 | typedef typename __identity<_Pred>::type key_equal; |
1053 | typedef typename __identity<_Alloc>::type allocator_type; |
1054 | typedef value_type& reference; |
1055 | typedef const value_type& const_reference; |
1056 | static_assert((is_same<value_type, typename allocator_type::value_type>::value), |
1057 | "Invalid allocator::value_type" ); |
1058 | |
1059 | private: |
1060 | typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table; |
1061 | |
1062 | __table __table_; |
1063 | |
1064 | public: |
1065 | typedef typename __table::pointer pointer; |
1066 | typedef typename __table::const_pointer const_pointer; |
1067 | typedef typename __table::size_type size_type; |
1068 | typedef typename __table::difference_type difference_type; |
1069 | |
1070 | typedef typename __table::const_iterator iterator; |
1071 | typedef typename __table::const_iterator const_iterator; |
1072 | typedef typename __table::const_local_iterator local_iterator; |
1073 | typedef typename __table::const_local_iterator const_local_iterator; |
1074 | |
1075 | #if _LIBCPP_STD_VER > 14 |
1076 | typedef __set_node_handle<typename __table::__node, allocator_type> node_type; |
1077 | #endif |
1078 | |
1079 | template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> |
1080 | friend class _LIBCPP_TEMPLATE_VIS unordered_set; |
1081 | template <class _Value2, class _Hash2, class _Pred2, class _Alloc2> |
1082 | friend class _LIBCPP_TEMPLATE_VIS unordered_multiset; |
1083 | |
1084 | _LIBCPP_INLINE_VISIBILITY |
1085 | unordered_multiset() |
1086 | _NOEXCEPT_(is_nothrow_default_constructible<__table>::value) |
1087 | { |
1088 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1089 | __get_db()->__insert_c(this); |
1090 | #endif |
1091 | } |
1092 | explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(), |
1093 | const key_equal& __eql = key_equal()); |
1094 | unordered_multiset(size_type __n, const hasher& __hf, |
1095 | const key_equal& __eql, const allocator_type& __a); |
1096 | #if _LIBCPP_STD_VER > 11 |
1097 | inline _LIBCPP_INLINE_VISIBILITY |
1098 | unordered_multiset(size_type __n, const allocator_type& __a) |
1099 | : unordered_multiset(__n, hasher(), key_equal(), __a) {} |
1100 | inline _LIBCPP_INLINE_VISIBILITY |
1101 | unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a) |
1102 | : unordered_multiset(__n, __hf, key_equal(), __a) {} |
1103 | #endif |
1104 | template <class _InputIterator> |
1105 | unordered_multiset(_InputIterator __first, _InputIterator __last); |
1106 | template <class _InputIterator> |
1107 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
1108 | size_type __n, const hasher& __hf = hasher(), |
1109 | const key_equal& __eql = key_equal()); |
1110 | template <class _InputIterator> |
1111 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
1112 | size_type __n , const hasher& __hf, |
1113 | const key_equal& __eql, const allocator_type& __a); |
1114 | #if _LIBCPP_STD_VER > 11 |
1115 | template <class _InputIterator> |
1116 | inline _LIBCPP_INLINE_VISIBILITY |
1117 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
1118 | size_type __n, const allocator_type& __a) |
1119 | : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {} |
1120 | template <class _InputIterator> |
1121 | inline _LIBCPP_INLINE_VISIBILITY |
1122 | unordered_multiset(_InputIterator __first, _InputIterator __last, |
1123 | size_type __n, const hasher& __hf, const allocator_type& __a) |
1124 | : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {} |
1125 | #endif |
1126 | _LIBCPP_INLINE_VISIBILITY |
1127 | explicit unordered_multiset(const allocator_type& __a); |
1128 | unordered_multiset(const unordered_multiset& __u); |
1129 | unordered_multiset(const unordered_multiset& __u, const allocator_type& __a); |
1130 | #ifndef _LIBCPP_CXX03_LANG |
1131 | _LIBCPP_INLINE_VISIBILITY |
1132 | unordered_multiset(unordered_multiset&& __u) |
1133 | _NOEXCEPT_(is_nothrow_move_constructible<__table>::value); |
1134 | unordered_multiset(unordered_multiset&& __u, const allocator_type& __a); |
1135 | unordered_multiset(initializer_list<value_type> __il); |
1136 | unordered_multiset(initializer_list<value_type> __il, size_type __n, |
1137 | const hasher& __hf = hasher(), |
1138 | const key_equal& __eql = key_equal()); |
1139 | unordered_multiset(initializer_list<value_type> __il, size_type __n, |
1140 | const hasher& __hf, const key_equal& __eql, |
1141 | const allocator_type& __a); |
1142 | #if _LIBCPP_STD_VER > 11 |
1143 | inline _LIBCPP_INLINE_VISIBILITY |
1144 | unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a) |
1145 | : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {} |
1146 | inline _LIBCPP_INLINE_VISIBILITY |
1147 | unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a) |
1148 | : unordered_multiset(__il, __n, __hf, key_equal(), __a) {} |
1149 | #endif |
1150 | #endif // _LIBCPP_CXX03_LANG |
1151 | _LIBCPP_INLINE_VISIBILITY |
1152 | ~unordered_multiset() { |
1153 | static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "" ); |
1154 | } |
1155 | |
1156 | _LIBCPP_INLINE_VISIBILITY |
1157 | unordered_multiset& operator=(const unordered_multiset& __u) |
1158 | { |
1159 | __table_ = __u.__table_; |
1160 | return *this; |
1161 | } |
1162 | #ifndef _LIBCPP_CXX03_LANG |
1163 | _LIBCPP_INLINE_VISIBILITY |
1164 | unordered_multiset& operator=(unordered_multiset&& __u) |
1165 | _NOEXCEPT_(is_nothrow_move_assignable<__table>::value); |
1166 | unordered_multiset& operator=(initializer_list<value_type> __il); |
1167 | #endif // _LIBCPP_CXX03_LANG |
1168 | |
1169 | _LIBCPP_INLINE_VISIBILITY |
1170 | allocator_type get_allocator() const _NOEXCEPT |
1171 | {return allocator_type(__table_.__node_alloc());} |
1172 | |
1173 | _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY |
1174 | bool empty() const _NOEXCEPT {return __table_.size() == 0;} |
1175 | _LIBCPP_INLINE_VISIBILITY |
1176 | size_type size() const _NOEXCEPT {return __table_.size();} |
1177 | _LIBCPP_INLINE_VISIBILITY |
1178 | size_type max_size() const _NOEXCEPT {return __table_.max_size();} |
1179 | |
1180 | _LIBCPP_INLINE_VISIBILITY |
1181 | iterator begin() _NOEXCEPT {return __table_.begin();} |
1182 | _LIBCPP_INLINE_VISIBILITY |
1183 | iterator end() _NOEXCEPT {return __table_.end();} |
1184 | _LIBCPP_INLINE_VISIBILITY |
1185 | const_iterator begin() const _NOEXCEPT {return __table_.begin();} |
1186 | _LIBCPP_INLINE_VISIBILITY |
1187 | const_iterator end() const _NOEXCEPT {return __table_.end();} |
1188 | _LIBCPP_INLINE_VISIBILITY |
1189 | const_iterator cbegin() const _NOEXCEPT {return __table_.begin();} |
1190 | _LIBCPP_INLINE_VISIBILITY |
1191 | const_iterator cend() const _NOEXCEPT {return __table_.end();} |
1192 | |
1193 | #ifndef _LIBCPP_CXX03_LANG |
1194 | template <class... _Args> |
1195 | _LIBCPP_INLINE_VISIBILITY |
1196 | iterator emplace(_Args&&... __args) |
1197 | {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} |
1198 | template <class... _Args> |
1199 | _LIBCPP_INLINE_VISIBILITY |
1200 | iterator emplace_hint(const_iterator __p, _Args&&... __args) |
1201 | {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} |
1202 | |
1203 | _LIBCPP_INLINE_VISIBILITY |
1204 | iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));} |
1205 | _LIBCPP_INLINE_VISIBILITY |
1206 | iterator insert(const_iterator __p, value_type&& __x) |
1207 | {return __table_.__insert_multi(__p, _VSTD::move(__x));} |
1208 | _LIBCPP_INLINE_VISIBILITY |
1209 | void insert(initializer_list<value_type> __il) |
1210 | {insert(__il.begin(), __il.end());} |
1211 | #endif // _LIBCPP_CXX03_LANG |
1212 | |
1213 | _LIBCPP_INLINE_VISIBILITY |
1214 | iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);} |
1215 | |
1216 | _LIBCPP_INLINE_VISIBILITY |
1217 | iterator insert(const_iterator __p, const value_type& __x) |
1218 | {return __table_.__insert_multi(__p, __x);} |
1219 | |
1220 | template <class _InputIterator> |
1221 | _LIBCPP_INLINE_VISIBILITY |
1222 | void insert(_InputIterator __first, _InputIterator __last); |
1223 | |
1224 | #if _LIBCPP_STD_VER > 14 |
1225 | _LIBCPP_INLINE_VISIBILITY |
1226 | iterator insert(node_type&& __nh) |
1227 | { |
1228 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
1229 | "node_type with incompatible allocator passed to unordered_multiset::insert()" ); |
1230 | return __table_.template __node_handle_insert_multi<node_type>( |
1231 | _VSTD::move(__nh)); |
1232 | } |
1233 | _LIBCPP_INLINE_VISIBILITY |
1234 | iterator insert(const_iterator __hint, node_type&& __nh) |
1235 | { |
1236 | _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), |
1237 | "node_type with incompatible allocator passed to unordered_multiset::insert()" ); |
1238 | return __table_.template __node_handle_insert_multi<node_type>( |
1239 | __hint, _VSTD::move(__nh)); |
1240 | } |
1241 | _LIBCPP_INLINE_VISIBILITY |
1242 | node_type (const_iterator __position) |
1243 | { |
1244 | return __table_.template __node_handle_extract<node_type>( |
1245 | __position); |
1246 | } |
1247 | _LIBCPP_INLINE_VISIBILITY |
1248 | node_type (key_type const& __key) |
1249 | { |
1250 | return __table_.template __node_handle_extract<node_type>(__key); |
1251 | } |
1252 | |
1253 | template <class _H2, class _P2> |
1254 | _LIBCPP_INLINE_VISIBILITY |
1255 | void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source) |
1256 | { |
1257 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1258 | "merging container with incompatible allocator" ); |
1259 | return __table_.__node_handle_merge_multi(__source.__table_); |
1260 | } |
1261 | template <class _H2, class _P2> |
1262 | _LIBCPP_INLINE_VISIBILITY |
1263 | void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source) |
1264 | { |
1265 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1266 | "merging container with incompatible allocator" ); |
1267 | return __table_.__node_handle_merge_multi(__source.__table_); |
1268 | } |
1269 | template <class _H2, class _P2> |
1270 | _LIBCPP_INLINE_VISIBILITY |
1271 | void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source) |
1272 | { |
1273 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1274 | "merging container with incompatible allocator" ); |
1275 | return __table_.__node_handle_merge_multi(__source.__table_); |
1276 | } |
1277 | template <class _H2, class _P2> |
1278 | _LIBCPP_INLINE_VISIBILITY |
1279 | void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source) |
1280 | { |
1281 | _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), |
1282 | "merging container with incompatible allocator" ); |
1283 | return __table_.__node_handle_merge_multi(__source.__table_); |
1284 | } |
1285 | #endif |
1286 | |
1287 | _LIBCPP_INLINE_VISIBILITY |
1288 | iterator erase(const_iterator __p) {return __table_.erase(__p);} |
1289 | _LIBCPP_INLINE_VISIBILITY |
1290 | size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);} |
1291 | _LIBCPP_INLINE_VISIBILITY |
1292 | iterator erase(const_iterator __first, const_iterator __last) |
1293 | {return __table_.erase(__first, __last);} |
1294 | _LIBCPP_INLINE_VISIBILITY |
1295 | void clear() _NOEXCEPT {__table_.clear();} |
1296 | |
1297 | _LIBCPP_INLINE_VISIBILITY |
1298 | void swap(unordered_multiset& __u) |
1299 | _NOEXCEPT_(__is_nothrow_swappable<__table>::value) |
1300 | {__table_.swap(__u.__table_);} |
1301 | |
1302 | _LIBCPP_INLINE_VISIBILITY |
1303 | hasher hash_function() const {return __table_.hash_function();} |
1304 | _LIBCPP_INLINE_VISIBILITY |
1305 | key_equal key_eq() const {return __table_.key_eq();} |
1306 | |
1307 | _LIBCPP_INLINE_VISIBILITY |
1308 | iterator find(const key_type& __k) {return __table_.find(__k);} |
1309 | _LIBCPP_INLINE_VISIBILITY |
1310 | const_iterator find(const key_type& __k) const {return __table_.find(__k);} |
1311 | _LIBCPP_INLINE_VISIBILITY |
1312 | size_type count(const key_type& __k) const {return __table_.__count_multi(__k);} |
1313 | #if _LIBCPP_STD_VER > 17 |
1314 | _LIBCPP_INLINE_VISIBILITY |
1315 | bool contains(const key_type& __k) const {return find(__k) != end();} |
1316 | #endif // _LIBCPP_STD_VER > 17 |
1317 | _LIBCPP_INLINE_VISIBILITY |
1318 | pair<iterator, iterator> equal_range(const key_type& __k) |
1319 | {return __table_.__equal_range_multi(__k);} |
1320 | _LIBCPP_INLINE_VISIBILITY |
1321 | pair<const_iterator, const_iterator> equal_range(const key_type& __k) const |
1322 | {return __table_.__equal_range_multi(__k);} |
1323 | |
1324 | _LIBCPP_INLINE_VISIBILITY |
1325 | size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();} |
1326 | _LIBCPP_INLINE_VISIBILITY |
1327 | size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();} |
1328 | |
1329 | _LIBCPP_INLINE_VISIBILITY |
1330 | size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);} |
1331 | _LIBCPP_INLINE_VISIBILITY |
1332 | size_type bucket(const key_type& __k) const {return __table_.bucket(__k);} |
1333 | |
1334 | _LIBCPP_INLINE_VISIBILITY |
1335 | local_iterator begin(size_type __n) {return __table_.begin(__n);} |
1336 | _LIBCPP_INLINE_VISIBILITY |
1337 | local_iterator end(size_type __n) {return __table_.end(__n);} |
1338 | _LIBCPP_INLINE_VISIBILITY |
1339 | const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);} |
1340 | _LIBCPP_INLINE_VISIBILITY |
1341 | const_local_iterator end(size_type __n) const {return __table_.cend(__n);} |
1342 | _LIBCPP_INLINE_VISIBILITY |
1343 | const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);} |
1344 | _LIBCPP_INLINE_VISIBILITY |
1345 | const_local_iterator cend(size_type __n) const {return __table_.cend(__n);} |
1346 | |
1347 | _LIBCPP_INLINE_VISIBILITY |
1348 | float load_factor() const _NOEXCEPT {return __table_.load_factor();} |
1349 | _LIBCPP_INLINE_VISIBILITY |
1350 | float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();} |
1351 | _LIBCPP_INLINE_VISIBILITY |
1352 | void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);} |
1353 | _LIBCPP_INLINE_VISIBILITY |
1354 | void rehash(size_type __n) {__table_.rehash(__n);} |
1355 | _LIBCPP_INLINE_VISIBILITY |
1356 | void reserve(size_type __n) {__table_.reserve(__n);} |
1357 | |
1358 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1359 | |
1360 | bool __dereferenceable(const const_iterator* __i) const |
1361 | {return __table_.__dereferenceable(__i);} |
1362 | bool __decrementable(const const_iterator* __i) const |
1363 | {return __table_.__decrementable(__i);} |
1364 | bool __addable(const const_iterator* __i, ptrdiff_t __n) const |
1365 | {return __table_.__addable(__i, __n);} |
1366 | bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const |
1367 | {return __table_.__addable(__i, __n);} |
1368 | |
1369 | #endif // _LIBCPP_DEBUG_LEVEL >= 2 |
1370 | |
1371 | }; |
1372 | |
1373 | #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES |
1374 | template<class _InputIterator, |
1375 | class _Hash = hash<__iter_value_type<_InputIterator>>, |
1376 | class _Pred = equal_to<__iter_value_type<_InputIterator>>, |
1377 | class _Allocator = allocator<__iter_value_type<_InputIterator>>, |
1378 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
1379 | class = _EnableIf<!is_integral<_Hash>::value>, |
1380 | class = _EnableIf<!__is_allocator<_Pred>::value>, |
1381 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
1382 | unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type = 0, |
1383 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) |
1384 | -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, _Pred, _Allocator>; |
1385 | |
1386 | template<class _Tp, class _Hash = hash<_Tp>, |
1387 | class _Pred = equal_to<_Tp>, class _Allocator = allocator<_Tp>, |
1388 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
1389 | class = _EnableIf<!is_integral<_Hash>::value>, |
1390 | class = _EnableIf<!__is_allocator<_Pred>::value>, |
1391 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
1392 | unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type = 0, |
1393 | _Hash = _Hash(), _Pred = _Pred(), _Allocator = _Allocator()) |
1394 | -> unordered_multiset<_Tp, _Hash, _Pred, _Allocator>; |
1395 | |
1396 | template<class _InputIterator, class _Allocator, |
1397 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
1398 | unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, _Allocator) |
1399 | -> unordered_multiset<__iter_value_type<_InputIterator>, |
1400 | hash<__iter_value_type<_InputIterator>>, |
1401 | equal_to<__iter_value_type<_InputIterator>>, |
1402 | _Allocator>; |
1403 | |
1404 | template<class _InputIterator, class _Hash, class _Allocator, |
1405 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
1406 | class = _EnableIf<!is_integral<_Hash>::value>, |
1407 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
1408 | unordered_multiset(_InputIterator, _InputIterator, typename allocator_traits<_Allocator>::size_type, |
1409 | _Hash, _Allocator) |
1410 | -> unordered_multiset<__iter_value_type<_InputIterator>, _Hash, |
1411 | equal_to<__iter_value_type<_InputIterator>>, |
1412 | _Allocator>; |
1413 | |
1414 | template<class _Tp, class _Allocator, |
1415 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
1416 | unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Allocator) |
1417 | -> unordered_multiset<_Tp, hash<_Tp>, equal_to<_Tp>, _Allocator>; |
1418 | |
1419 | template<class _Tp, class _Hash, class _Allocator, |
1420 | class = _EnableIf<!__is_allocator<_Hash>::value>, |
1421 | class = _EnableIf<!is_integral<_Hash>::value>, |
1422 | class = _EnableIf<__is_allocator<_Allocator>::value>> |
1423 | unordered_multiset(initializer_list<_Tp>, typename allocator_traits<_Allocator>::size_type, _Hash, _Allocator) |
1424 | -> unordered_multiset<_Tp, _Hash, equal_to<_Tp>, _Allocator>; |
1425 | #endif |
1426 | |
1427 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1428 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1429 | size_type __n, const hasher& __hf, const key_equal& __eql) |
1430 | : __table_(__hf, __eql) |
1431 | { |
1432 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1433 | __get_db()->__insert_c(this); |
1434 | #endif |
1435 | __table_.rehash(__n); |
1436 | } |
1437 | |
1438 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1439 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1440 | size_type __n, const hasher& __hf, const key_equal& __eql, |
1441 | const allocator_type& __a) |
1442 | : __table_(__hf, __eql, __a) |
1443 | { |
1444 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1445 | __get_db()->__insert_c(this); |
1446 | #endif |
1447 | __table_.rehash(__n); |
1448 | } |
1449 | |
1450 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1451 | template <class _InputIterator> |
1452 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1453 | _InputIterator __first, _InputIterator __last) |
1454 | { |
1455 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1456 | __get_db()->__insert_c(this); |
1457 | #endif |
1458 | insert(__first, __last); |
1459 | } |
1460 | |
1461 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1462 | template <class _InputIterator> |
1463 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1464 | _InputIterator __first, _InputIterator __last, size_type __n, |
1465 | const hasher& __hf, const key_equal& __eql) |
1466 | : __table_(__hf, __eql) |
1467 | { |
1468 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1469 | __get_db()->__insert_c(this); |
1470 | #endif |
1471 | __table_.rehash(__n); |
1472 | insert(__first, __last); |
1473 | } |
1474 | |
1475 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1476 | template <class _InputIterator> |
1477 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1478 | _InputIterator __first, _InputIterator __last, size_type __n, |
1479 | const hasher& __hf, const key_equal& __eql, const allocator_type& __a) |
1480 | : __table_(__hf, __eql, __a) |
1481 | { |
1482 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1483 | __get_db()->__insert_c(this); |
1484 | #endif |
1485 | __table_.rehash(__n); |
1486 | insert(__first, __last); |
1487 | } |
1488 | |
1489 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1490 | inline |
1491 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1492 | const allocator_type& __a) |
1493 | : __table_(__a) |
1494 | { |
1495 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1496 | __get_db()->__insert_c(this); |
1497 | #endif |
1498 | } |
1499 | |
1500 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1501 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1502 | const unordered_multiset& __u) |
1503 | : __table_(__u.__table_) |
1504 | { |
1505 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1506 | __get_db()->__insert_c(this); |
1507 | #endif |
1508 | __table_.rehash(__u.bucket_count()); |
1509 | insert(__u.begin(), __u.end()); |
1510 | } |
1511 | |
1512 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1513 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1514 | const unordered_multiset& __u, const allocator_type& __a) |
1515 | : __table_(__u.__table_, __a) |
1516 | { |
1517 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1518 | __get_db()->__insert_c(this); |
1519 | #endif |
1520 | __table_.rehash(__u.bucket_count()); |
1521 | insert(__u.begin(), __u.end()); |
1522 | } |
1523 | |
1524 | #ifndef _LIBCPP_CXX03_LANG |
1525 | |
1526 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1527 | inline |
1528 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1529 | unordered_multiset&& __u) |
1530 | _NOEXCEPT_(is_nothrow_move_constructible<__table>::value) |
1531 | : __table_(_VSTD::move(__u.__table_)) |
1532 | { |
1533 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1534 | __get_db()->__insert_c(this); |
1535 | __get_db()->swap(this, &__u); |
1536 | #endif |
1537 | } |
1538 | |
1539 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1540 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1541 | unordered_multiset&& __u, const allocator_type& __a) |
1542 | : __table_(_VSTD::move(__u.__table_), __a) |
1543 | { |
1544 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1545 | __get_db()->__insert_c(this); |
1546 | #endif |
1547 | if (__a != __u.get_allocator()) |
1548 | { |
1549 | iterator __i = __u.begin(); |
1550 | while (__u.size() != 0) |
1551 | __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_)); |
1552 | } |
1553 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1554 | else |
1555 | __get_db()->swap(this, &__u); |
1556 | #endif |
1557 | } |
1558 | |
1559 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1560 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1561 | initializer_list<value_type> __il) |
1562 | { |
1563 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1564 | __get_db()->__insert_c(this); |
1565 | #endif |
1566 | insert(__il.begin(), __il.end()); |
1567 | } |
1568 | |
1569 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1570 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1571 | initializer_list<value_type> __il, size_type __n, const hasher& __hf, |
1572 | const key_equal& __eql) |
1573 | : __table_(__hf, __eql) |
1574 | { |
1575 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1576 | __get_db()->__insert_c(this); |
1577 | #endif |
1578 | __table_.rehash(__n); |
1579 | insert(__il.begin(), __il.end()); |
1580 | } |
1581 | |
1582 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1583 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset( |
1584 | initializer_list<value_type> __il, size_type __n, const hasher& __hf, |
1585 | const key_equal& __eql, const allocator_type& __a) |
1586 | : __table_(__hf, __eql, __a) |
1587 | { |
1588 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
1589 | __get_db()->__insert_c(this); |
1590 | #endif |
1591 | __table_.rehash(__n); |
1592 | insert(__il.begin(), __il.end()); |
1593 | } |
1594 | |
1595 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1596 | inline |
1597 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& |
1598 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( |
1599 | unordered_multiset&& __u) |
1600 | _NOEXCEPT_(is_nothrow_move_assignable<__table>::value) |
1601 | { |
1602 | __table_ = _VSTD::move(__u.__table_); |
1603 | return *this; |
1604 | } |
1605 | |
1606 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1607 | inline |
1608 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& |
1609 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=( |
1610 | initializer_list<value_type> __il) |
1611 | { |
1612 | __table_.__assign_multi(__il.begin(), __il.end()); |
1613 | return *this; |
1614 | } |
1615 | |
1616 | #endif // _LIBCPP_CXX03_LANG |
1617 | |
1618 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1619 | template <class _InputIterator> |
1620 | inline |
1621 | void |
1622 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first, |
1623 | _InputIterator __last) |
1624 | { |
1625 | for (; __first != __last; ++__first) |
1626 | __table_.__insert_multi(*__first); |
1627 | } |
1628 | |
1629 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1630 | inline _LIBCPP_INLINE_VISIBILITY |
1631 | void |
1632 | swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, |
1633 | unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) |
1634 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
1635 | { |
1636 | __x.swap(__y); |
1637 | } |
1638 | |
1639 | #if _LIBCPP_STD_VER > 17 |
1640 | template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate> |
1641 | inline _LIBCPP_INLINE_VISIBILITY |
1642 | void erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred) |
1643 | { __libcpp_erase_if_container(__c, __pred); } |
1644 | #endif |
1645 | |
1646 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1647 | bool |
1648 | operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, |
1649 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) |
1650 | { |
1651 | if (__x.size() != __y.size()) |
1652 | return false; |
1653 | typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator |
1654 | const_iterator; |
1655 | typedef pair<const_iterator, const_iterator> _EqRng; |
1656 | for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;) |
1657 | { |
1658 | _EqRng __xeq = __x.equal_range(*__i); |
1659 | _EqRng __yeq = __y.equal_range(*__i); |
1660 | if (_VSTD::distance(__xeq.first, __xeq.second) != |
1661 | _VSTD::distance(__yeq.first, __yeq.second) || |
1662 | !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first)) |
1663 | return false; |
1664 | __i = __xeq.second; |
1665 | } |
1666 | return true; |
1667 | } |
1668 | |
1669 | template <class _Value, class _Hash, class _Pred, class _Alloc> |
1670 | inline _LIBCPP_INLINE_VISIBILITY |
1671 | bool |
1672 | operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, |
1673 | const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) |
1674 | { |
1675 | return !(__x == __y); |
1676 | } |
1677 | |
1678 | _LIBCPP_END_NAMESPACE_STD |
1679 | |
1680 | #endif // _LIBCPP_UNORDERED_SET |
1681 | |