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