2 //===-------------------------- unordered_set -----------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_UNORDERED_SET
12 #define _LIBCPP_UNORDERED_SET
16 unordered_set synopsis
18 #include <initializer_list>
23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
24 class Alloc = allocator<Value>>
29 typedef Value key_type;
30 typedef key_type value_type;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef value_type& reference;
35 typedef const value_type& const_reference;
36 typedef typename allocator_traits<allocator_type>::pointer pointer;
37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
38 typedef typename allocator_traits<allocator_type>::size_type size_type;
39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
46 typedef unspecified node_type unspecified; // C++17
47 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
51 is_nothrow_default_constructible<hasher>::value &&
52 is_nothrow_default_constructible<key_equal>::value &&
53 is_nothrow_default_constructible<allocator_type>::value);
54 explicit unordered_set(size_type n, const hasher& hf = hasher(),
55 const key_equal& eql = key_equal(),
56 const allocator_type& a = allocator_type());
57 template <class InputIterator>
58 unordered_set(InputIterator f, InputIterator l,
59 size_type n = 0, const hasher& hf = hasher(),
60 const key_equal& eql = key_equal(),
61 const allocator_type& a = allocator_type());
62 explicit unordered_set(const allocator_type&);
63 unordered_set(const unordered_set&);
64 unordered_set(const unordered_set&, const Allocator&);
65 unordered_set(unordered_set&&)
67 is_nothrow_move_constructible<hasher>::value &&
68 is_nothrow_move_constructible<key_equal>::value &&
69 is_nothrow_move_constructible<allocator_type>::value);
70 unordered_set(unordered_set&&, const Allocator&);
71 unordered_set(initializer_list<value_type>, size_type n = 0,
72 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
73 const allocator_type& a = allocator_type());
74 unordered_set(size_type n, const allocator_type& a); // C++14
75 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
76 template <class InputIterator>
77 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
78 template <class InputIterator>
79 unordered_set(InputIterator f, InputIterator l, size_type n,
80 const hasher& hf, const allocator_type& a); // C++14
81 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
82 unordered_set(initializer_list<value_type> il, size_type n,
83 const hasher& hf, const allocator_type& a); // C++14
85 unordered_set& operator=(const unordered_set&);
86 unordered_set& operator=(unordered_set&&)
88 allocator_type::propagate_on_container_move_assignment::value &&
89 is_nothrow_move_assignable<allocator_type>::value &&
90 is_nothrow_move_assignable<hasher>::value &&
91 is_nothrow_move_assignable<key_equal>::value);
92 unordered_set& operator=(initializer_list<value_type>);
94 allocator_type get_allocator() const noexcept;
96 bool empty() const noexcept;
97 size_type size() const noexcept;
98 size_type max_size() const noexcept;
100 iterator begin() noexcept;
101 iterator end() noexcept;
102 const_iterator begin() const noexcept;
103 const_iterator end() const noexcept;
104 const_iterator cbegin() const noexcept;
105 const_iterator cend() const noexcept;
107 template <class... Args>
108 pair<iterator, bool> emplace(Args&&... args);
109 template <class... Args>
110 iterator emplace_hint(const_iterator position, Args&&... args);
111 pair<iterator, bool> insert(const value_type& obj);
112 pair<iterator, bool> insert(value_type&& obj);
113 iterator insert(const_iterator hint, const value_type& obj);
114 iterator insert(const_iterator hint, value_type&& obj);
115 template <class InputIterator>
116 void insert(InputIterator first, InputIterator last);
117 void insert(initializer_list<value_type>);
119 node_type extract(const_iterator position); // C++17
120 node_type extract(const key_type& x); // C++17
121 insert_return_type insert(node_type&& nh); // C++17
122 iterator insert(const_iterator hint, node_type&& nh); // C++17
124 iterator erase(const_iterator position);
125 iterator erase(iterator position); // C++14
126 size_type erase(const key_type& k);
127 iterator erase(const_iterator first, const_iterator last);
128 void clear() noexcept;
130 template<class H2, class P2>
131 void merge(unordered_set<Key, H2, P2, Allocator>& source); // C++17
132 template<class H2, class P2>
133 void merge(unordered_set<Key, H2, P2, Allocator>&& source); // C++17
134 template<class H2, class P2>
135 void merge(unordered_multiset<Key, H2, P2, Allocator>& source); // C++17
136 template<class H2, class P2>
137 void merge(unordered_multiset<Key, H2, P2, Allocator>&& source); // C++17
139 void swap(unordered_set&)
140 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
141 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
142 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
144 hasher hash_function() const;
145 key_equal key_eq() const;
147 iterator find(const key_type& k);
148 const_iterator find(const key_type& k) const;
149 size_type count(const key_type& k) const;
150 pair<iterator, iterator> equal_range(const key_type& k);
151 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
153 size_type bucket_count() const noexcept;
154 size_type max_bucket_count() const noexcept;
156 size_type bucket_size(size_type n) const;
157 size_type bucket(const key_type& k) const;
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;
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);
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)));
178 template <class Value, class Hash, class Pred, class Alloc>
180 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
181 const unordered_set<Value, Hash, Pred, Alloc>& y);
183 template <class Value, class Hash, class Pred, class Alloc>
185 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
186 const unordered_set<Value, Hash, Pred, Alloc>& y);
188 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
189 class Alloc = allocator<Value>>
190 class unordered_multiset
194 typedef Value key_type;
195 typedef key_type value_type;
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;
206 typedef /unspecified/ iterator;
207 typedef /unspecified/ const_iterator;
208 typedef /unspecified/ local_iterator;
209 typedef /unspecified/ const_local_iterator;
211 typedef unspecified node_type unspecified; // C++17
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&&)
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&&)
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>);
258 allocator_type get_allocator() const noexcept;
260 bool empty() const noexcept;
261 size_type size() const noexcept;
262 size_type max_size() const noexcept;
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;
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>);
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
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;
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
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
308 hasher hash_function() const;
309 key_equal key_eq() const;
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 pair<iterator, iterator> equal_range(const key_type& k);
315 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
317 size_type bucket_count() const noexcept;
318 size_type max_bucket_count() const noexcept;
320 size_type bucket_size(size_type n) const;
321 size_type bucket(const key_type& k) const;
323 local_iterator begin(size_type n);
324 local_iterator end(size_type n);
325 const_local_iterator begin(size_type n) const;
326 const_local_iterator end(size_type n) const;
327 const_local_iterator cbegin(size_type n) const;
328 const_local_iterator cend(size_type n) const;
330 float load_factor() const noexcept;
331 float max_load_factor() const noexcept;
332 void max_load_factor(float z);
333 void rehash(size_type n);
334 void reserve(size_type n);
337 template <class Value, class Hash, class Pred, class Alloc>
338 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
339 unordered_multiset<Value, Hash, Pred, Alloc>& y)
340 noexcept(noexcept(x.swap(y)));
342 template <class K, class T, class H, class P, class A, class Predicate>
343 void erase_if(unordered_set<K, T, H, P, A>& c, Predicate pred); // C++20
345 template <class K, class T, class H, class P, class A, class Predicate>
346 void erase_if(unordered_multiset<K, T, H, P, A>& c, Predicate pred); // C++20
349 template <class Value, class Hash, class Pred, class Alloc>
351 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
352 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
354 template <class Value, class Hash, class Pred, class Alloc>
356 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
357 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
363 #include <__hash_table>
364 #include <__node_handle>
365 #include <functional>
370 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
371 #pragma GCC system_header
374 _LIBCPP_BEGIN_NAMESPACE_STD
376 template <class _Value, class _Hash, class _Pred, class _Alloc>
377 class unordered_multiset;
379 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
380 class _Alloc = allocator<_Value> >
381 class _LIBCPP_TEMPLATE_VIS unordered_set
385 typedef _Value key_type;
386 typedef key_type value_type;
387 typedef _Hash hasher;
388 typedef _Pred key_equal;
389 typedef _Alloc allocator_type;
390 typedef value_type& reference;
391 typedef const value_type& const_reference;
392 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
393 "Invalid allocator::value_type");
394 static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
397 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
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;
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;
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;
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;
422 _LIBCPP_INLINE_VISIBILITY
424 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
426 #if _LIBCPP_DEBUG_LEVEL >= 2
427 __get_db()->__insert_c(this);
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) {}
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) {}
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) {}
489 #endif // _LIBCPP_CXX03_LANG
490 // ~unordered_set() = default;
491 _LIBCPP_INLINE_VISIBILITY
492 unordered_set& operator=(const unordered_set& __u)
494 __table_ = __u.__table_;
497 #ifndef _LIBCPP_CXX03_LANG
498 _LIBCPP_INLINE_VISIBILITY
499 unordered_set& operator=(unordered_set&& __u)
500 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
501 _LIBCPP_INLINE_VISIBILITY
502 unordered_set& operator=(initializer_list<value_type> __il);
503 #endif // _LIBCPP_CXX03_LANG
505 _LIBCPP_INLINE_VISIBILITY
506 allocator_type get_allocator() const _NOEXCEPT
507 {return allocator_type(__table_.__node_alloc());}
509 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
510 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
511 _LIBCPP_INLINE_VISIBILITY
512 size_type size() const _NOEXCEPT {return __table_.size();}
513 _LIBCPP_INLINE_VISIBILITY
514 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
516 _LIBCPP_INLINE_VISIBILITY
517 iterator begin() _NOEXCEPT {return __table_.begin();}
518 _LIBCPP_INLINE_VISIBILITY
519 iterator end() _NOEXCEPT {return __table_.end();}
520 _LIBCPP_INLINE_VISIBILITY
521 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
522 _LIBCPP_INLINE_VISIBILITY
523 const_iterator end() const _NOEXCEPT {return __table_.end();}
524 _LIBCPP_INLINE_VISIBILITY
525 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
526 _LIBCPP_INLINE_VISIBILITY
527 const_iterator cend() const _NOEXCEPT {return __table_.end();}
529 #ifndef _LIBCPP_CXX03_LANG
530 template <class... _Args>
531 _LIBCPP_INLINE_VISIBILITY
532 pair<iterator, bool> emplace(_Args&&... __args)
533 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
534 template <class... _Args>
535 _LIBCPP_INLINE_VISIBILITY
536 #if _LIBCPP_DEBUG_LEVEL >= 2
537 iterator emplace_hint(const_iterator __p, _Args&&... __args)
539 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
540 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
541 " referring to this unordered_set");
542 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
545 iterator emplace_hint(const_iterator, _Args&&... __args)
546 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
549 _LIBCPP_INLINE_VISIBILITY
550 pair<iterator, bool> insert(value_type&& __x)
551 {return __table_.__insert_unique(_VSTD::move(__x));}
552 _LIBCPP_INLINE_VISIBILITY
553 #if _LIBCPP_DEBUG_LEVEL >= 2
554 iterator insert(const_iterator __p, value_type&& __x)
556 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
557 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
558 " referring to this unordered_set");
559 return insert(_VSTD::move(__x)).first;
562 iterator insert(const_iterator, value_type&& __x)
563 {return insert(_VSTD::move(__x)).first;}
565 _LIBCPP_INLINE_VISIBILITY
566 void insert(initializer_list<value_type> __il)
567 {insert(__il.begin(), __il.end());}
568 #endif // _LIBCPP_CXX03_LANG
569 _LIBCPP_INLINE_VISIBILITY
570 pair<iterator, bool> insert(const value_type& __x)
571 {return __table_.__insert_unique(__x);}
573 _LIBCPP_INLINE_VISIBILITY
574 #if _LIBCPP_DEBUG_LEVEL >= 2
575 iterator insert(const_iterator __p, const value_type& __x)
577 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
578 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
579 " referring to this unordered_set");
580 return insert(__x).first;
583 iterator insert(const_iterator, const value_type& __x)
584 {return insert(__x).first;}
586 template <class _InputIterator>
587 _LIBCPP_INLINE_VISIBILITY
588 void insert(_InputIterator __first, _InputIterator __last);
590 _LIBCPP_INLINE_VISIBILITY
591 iterator erase(const_iterator __p) {return __table_.erase(__p);}
592 _LIBCPP_INLINE_VISIBILITY
593 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
594 _LIBCPP_INLINE_VISIBILITY
595 iterator erase(const_iterator __first, const_iterator __last)
596 {return __table_.erase(__first, __last);}
597 _LIBCPP_INLINE_VISIBILITY
598 void clear() _NOEXCEPT {__table_.clear();}
600 #if _LIBCPP_STD_VER > 14
601 _LIBCPP_INLINE_VISIBILITY
602 insert_return_type insert(node_type&& __nh)
604 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
605 "node_type with incompatible allocator passed to unordered_set::insert()");
606 return __table_.template __node_handle_insert_unique<
607 node_type, insert_return_type>(_VSTD::move(__nh));
609 _LIBCPP_INLINE_VISIBILITY
610 iterator insert(const_iterator __h, node_type&& __nh)
612 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
613 "node_type with incompatible allocator passed to unordered_set::insert()");
614 return __table_.template __node_handle_insert_unique<node_type>(
615 __h, _VSTD::move(__nh));
617 _LIBCPP_INLINE_VISIBILITY
618 node_type extract(key_type const& __key)
620 return __table_.template __node_handle_extract<node_type>(__key);
622 _LIBCPP_INLINE_VISIBILITY
623 node_type extract(const_iterator __it)
625 return __table_.template __node_handle_extract<node_type>(__it);
628 template<class _H2, class _P2>
629 _LIBCPP_INLINE_VISIBILITY
630 void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
632 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
633 "merging container with incompatible allocator");
634 __table_.__node_handle_merge_unique(__source.__table_);
636 template<class _H2, class _P2>
637 _LIBCPP_INLINE_VISIBILITY
638 void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
640 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
641 "merging container with incompatible allocator");
642 __table_.__node_handle_merge_unique(__source.__table_);
644 template<class _H2, class _P2>
645 _LIBCPP_INLINE_VISIBILITY
646 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
648 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
649 "merging container with incompatible allocator");
650 __table_.__node_handle_merge_unique(__source.__table_);
652 template<class _H2, class _P2>
653 _LIBCPP_INLINE_VISIBILITY
654 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
656 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
657 "merging container with incompatible allocator");
658 __table_.__node_handle_merge_unique(__source.__table_);
662 _LIBCPP_INLINE_VISIBILITY
663 void swap(unordered_set& __u)
664 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
665 {__table_.swap(__u.__table_);}
667 _LIBCPP_INLINE_VISIBILITY
668 hasher hash_function() const {return __table_.hash_function();}
669 _LIBCPP_INLINE_VISIBILITY
670 key_equal key_eq() const {return __table_.key_eq();}
672 _LIBCPP_INLINE_VISIBILITY
673 iterator find(const key_type& __k) {return __table_.find(__k);}
674 _LIBCPP_INLINE_VISIBILITY
675 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
676 _LIBCPP_INLINE_VISIBILITY
677 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
678 _LIBCPP_INLINE_VISIBILITY
679 pair<iterator, iterator> equal_range(const key_type& __k)
680 {return __table_.__equal_range_unique(__k);}
681 _LIBCPP_INLINE_VISIBILITY
682 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
683 {return __table_.__equal_range_unique(__k);}
685 _LIBCPP_INLINE_VISIBILITY
686 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
687 _LIBCPP_INLINE_VISIBILITY
688 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
690 _LIBCPP_INLINE_VISIBILITY
691 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
692 _LIBCPP_INLINE_VISIBILITY
693 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
695 _LIBCPP_INLINE_VISIBILITY
696 local_iterator begin(size_type __n) {return __table_.begin(__n);}
697 _LIBCPP_INLINE_VISIBILITY
698 local_iterator end(size_type __n) {return __table_.end(__n);}
699 _LIBCPP_INLINE_VISIBILITY
700 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
701 _LIBCPP_INLINE_VISIBILITY
702 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
703 _LIBCPP_INLINE_VISIBILITY
704 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
705 _LIBCPP_INLINE_VISIBILITY
706 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
708 _LIBCPP_INLINE_VISIBILITY
709 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
710 _LIBCPP_INLINE_VISIBILITY
711 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
712 _LIBCPP_INLINE_VISIBILITY
713 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
714 _LIBCPP_INLINE_VISIBILITY
715 void rehash(size_type __n) {__table_.rehash(__n);}
716 _LIBCPP_INLINE_VISIBILITY
717 void reserve(size_type __n) {__table_.reserve(__n);}
719 #if _LIBCPP_DEBUG_LEVEL >= 2
721 bool __dereferenceable(const const_iterator* __i) const
722 {return __table_.__dereferenceable(__i);}
723 bool __decrementable(const const_iterator* __i) const
724 {return __table_.__decrementable(__i);}
725 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
726 {return __table_.__addable(__i, __n);}
727 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
728 {return __table_.__addable(__i, __n);}
730 #endif // _LIBCPP_DEBUG_LEVEL >= 2
734 template <class _Value, class _Hash, class _Pred, class _Alloc>
735 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
736 const hasher& __hf, const key_equal& __eql)
737 : __table_(__hf, __eql)
739 #if _LIBCPP_DEBUG_LEVEL >= 2
740 __get_db()->__insert_c(this);
742 __table_.rehash(__n);
745 template <class _Value, class _Hash, class _Pred, class _Alloc>
746 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
747 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
748 : __table_(__hf, __eql, __a)
750 #if _LIBCPP_DEBUG_LEVEL >= 2
751 __get_db()->__insert_c(this);
753 __table_.rehash(__n);
756 template <class _Value, class _Hash, class _Pred, class _Alloc>
757 template <class _InputIterator>
758 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
759 _InputIterator __first, _InputIterator __last)
761 #if _LIBCPP_DEBUG_LEVEL >= 2
762 __get_db()->__insert_c(this);
764 insert(__first, __last);
767 template <class _Value, class _Hash, class _Pred, class _Alloc>
768 template <class _InputIterator>
769 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
770 _InputIterator __first, _InputIterator __last, size_type __n,
771 const hasher& __hf, const key_equal& __eql)
772 : __table_(__hf, __eql)
774 #if _LIBCPP_DEBUG_LEVEL >= 2
775 __get_db()->__insert_c(this);
777 __table_.rehash(__n);
778 insert(__first, __last);
781 template <class _Value, class _Hash, class _Pred, class _Alloc>
782 template <class _InputIterator>
783 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
784 _InputIterator __first, _InputIterator __last, size_type __n,
785 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
786 : __table_(__hf, __eql, __a)
788 #if _LIBCPP_DEBUG_LEVEL >= 2
789 __get_db()->__insert_c(this);
791 __table_.rehash(__n);
792 insert(__first, __last);
795 template <class _Value, class _Hash, class _Pred, class _Alloc>
797 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
798 const allocator_type& __a)
801 #if _LIBCPP_DEBUG_LEVEL >= 2
802 __get_db()->__insert_c(this);
806 template <class _Value, class _Hash, class _Pred, class _Alloc>
807 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
808 const unordered_set& __u)
809 : __table_(__u.__table_)
811 #if _LIBCPP_DEBUG_LEVEL >= 2
812 __get_db()->__insert_c(this);
814 __table_.rehash(__u.bucket_count());
815 insert(__u.begin(), __u.end());
818 template <class _Value, class _Hash, class _Pred, class _Alloc>
819 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
820 const unordered_set& __u, const allocator_type& __a)
821 : __table_(__u.__table_, __a)
823 #if _LIBCPP_DEBUG_LEVEL >= 2
824 __get_db()->__insert_c(this);
826 __table_.rehash(__u.bucket_count());
827 insert(__u.begin(), __u.end());
830 #ifndef _LIBCPP_CXX03_LANG
832 template <class _Value, class _Hash, class _Pred, class _Alloc>
834 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
836 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
837 : __table_(_VSTD::move(__u.__table_))
839 #if _LIBCPP_DEBUG_LEVEL >= 2
840 __get_db()->__insert_c(this);
841 __get_db()->swap(this, &__u);
845 template <class _Value, class _Hash, class _Pred, class _Alloc>
846 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
847 unordered_set&& __u, const allocator_type& __a)
848 : __table_(_VSTD::move(__u.__table_), __a)
850 #if _LIBCPP_DEBUG_LEVEL >= 2
851 __get_db()->__insert_c(this);
853 if (__a != __u.get_allocator())
855 iterator __i = __u.begin();
856 while (__u.size() != 0)
857 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
859 #if _LIBCPP_DEBUG_LEVEL >= 2
861 __get_db()->swap(this, &__u);
865 template <class _Value, class _Hash, class _Pred, class _Alloc>
866 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
867 initializer_list<value_type> __il)
869 #if _LIBCPP_DEBUG_LEVEL >= 2
870 __get_db()->__insert_c(this);
872 insert(__il.begin(), __il.end());
875 template <class _Value, class _Hash, class _Pred, class _Alloc>
876 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
877 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
878 const key_equal& __eql)
879 : __table_(__hf, __eql)
881 #if _LIBCPP_DEBUG_LEVEL >= 2
882 __get_db()->__insert_c(this);
884 __table_.rehash(__n);
885 insert(__il.begin(), __il.end());
888 template <class _Value, class _Hash, class _Pred, class _Alloc>
889 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
890 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
891 const key_equal& __eql, const allocator_type& __a)
892 : __table_(__hf, __eql, __a)
894 #if _LIBCPP_DEBUG_LEVEL >= 2
895 __get_db()->__insert_c(this);
897 __table_.rehash(__n);
898 insert(__il.begin(), __il.end());
901 template <class _Value, class _Hash, class _Pred, class _Alloc>
903 unordered_set<_Value, _Hash, _Pred, _Alloc>&
904 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
905 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
907 __table_ = _VSTD::move(__u.__table_);
911 template <class _Value, class _Hash, class _Pred, class _Alloc>
913 unordered_set<_Value, _Hash, _Pred, _Alloc>&
914 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
915 initializer_list<value_type> __il)
917 __table_.__assign_unique(__il.begin(), __il.end());
921 #endif // _LIBCPP_CXX03_LANG
923 template <class _Value, class _Hash, class _Pred, class _Alloc>
924 template <class _InputIterator>
927 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
928 _InputIterator __last)
930 for (; __first != __last; ++__first)
931 __table_.__insert_unique(*__first);
934 template <class _Value, class _Hash, class _Pred, class _Alloc>
935 inline _LIBCPP_INLINE_VISIBILITY
937 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
938 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
939 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
944 #if _LIBCPP_STD_VER > 17
945 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
946 inline _LIBCPP_INLINE_VISIBILITY
947 void erase_if(unordered_set<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
948 { __libcpp_erase_if_container(__c, __pred); }
951 template <class _Value, class _Hash, class _Pred, class _Alloc>
953 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
954 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
956 if (__x.size() != __y.size())
958 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
960 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
963 const_iterator __j = __y.find(*__i);
964 if (__j == __ey || !(*__i == *__j))
970 template <class _Value, class _Hash, class _Pred, class _Alloc>
971 inline _LIBCPP_INLINE_VISIBILITY
973 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
974 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
976 return !(__x == __y);
979 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
980 class _Alloc = allocator<_Value> >
981 class _LIBCPP_TEMPLATE_VIS unordered_multiset
985 typedef _Value key_type;
986 typedef key_type value_type;
987 typedef _Hash hasher;
988 typedef _Pred key_equal;
989 typedef _Alloc allocator_type;
990 typedef value_type& reference;
991 typedef const value_type& const_reference;
992 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
993 "Invalid allocator::value_type");
994 static_assert(sizeof(__diagnose_unordered_container_requirements<_Value, _Hash, _Pred>(0)), "");
997 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
1002 typedef typename __table::pointer pointer;
1003 typedef typename __table::const_pointer const_pointer;
1004 typedef typename __table::size_type size_type;
1005 typedef typename __table::difference_type difference_type;
1007 typedef typename __table::const_iterator iterator;
1008 typedef typename __table::const_iterator const_iterator;
1009 typedef typename __table::const_local_iterator local_iterator;
1010 typedef typename __table::const_local_iterator const_local_iterator;
1012 #if _LIBCPP_STD_VER > 14
1013 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
1016 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1017 friend class _LIBCPP_TEMPLATE_VIS unordered_set;
1018 template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
1019 friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
1021 _LIBCPP_INLINE_VISIBILITY
1022 unordered_multiset()
1023 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
1025 #if _LIBCPP_DEBUG_LEVEL >= 2
1026 __get_db()->__insert_c(this);
1029 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
1030 const key_equal& __eql = key_equal());
1031 unordered_multiset(size_type __n, const hasher& __hf,
1032 const key_equal& __eql, const allocator_type& __a);
1033 #if _LIBCPP_STD_VER > 11
1034 inline _LIBCPP_INLINE_VISIBILITY
1035 unordered_multiset(size_type __n, const allocator_type& __a)
1036 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
1037 inline _LIBCPP_INLINE_VISIBILITY
1038 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
1039 : unordered_multiset(__n, __hf, key_equal(), __a) {}
1041 template <class _InputIterator>
1042 unordered_multiset(_InputIterator __first, _InputIterator __last);
1043 template <class _InputIterator>
1044 unordered_multiset(_InputIterator __first, _InputIterator __last,
1045 size_type __n, const hasher& __hf = hasher(),
1046 const key_equal& __eql = key_equal());
1047 template <class _InputIterator>
1048 unordered_multiset(_InputIterator __first, _InputIterator __last,
1049 size_type __n , const hasher& __hf,
1050 const key_equal& __eql, const allocator_type& __a);
1051 #if _LIBCPP_STD_VER > 11
1052 template <class _InputIterator>
1053 inline _LIBCPP_INLINE_VISIBILITY
1054 unordered_multiset(_InputIterator __first, _InputIterator __last,
1055 size_type __n, const allocator_type& __a)
1056 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
1057 template <class _InputIterator>
1058 inline _LIBCPP_INLINE_VISIBILITY
1059 unordered_multiset(_InputIterator __first, _InputIterator __last,
1060 size_type __n, const hasher& __hf, const allocator_type& __a)
1061 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
1063 _LIBCPP_INLINE_VISIBILITY
1064 explicit unordered_multiset(const allocator_type& __a);
1065 unordered_multiset(const unordered_multiset& __u);
1066 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
1067 #ifndef _LIBCPP_CXX03_LANG
1068 _LIBCPP_INLINE_VISIBILITY
1069 unordered_multiset(unordered_multiset&& __u)
1070 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
1071 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
1072 unordered_multiset(initializer_list<value_type> __il);
1073 unordered_multiset(initializer_list<value_type> __il, size_type __n,
1074 const hasher& __hf = hasher(),
1075 const key_equal& __eql = key_equal());
1076 unordered_multiset(initializer_list<value_type> __il, size_type __n,
1077 const hasher& __hf, const key_equal& __eql,
1078 const allocator_type& __a);
1079 #if _LIBCPP_STD_VER > 11
1080 inline _LIBCPP_INLINE_VISIBILITY
1081 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1082 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1083 inline _LIBCPP_INLINE_VISIBILITY
1084 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1085 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1087 #endif // _LIBCPP_CXX03_LANG
1088 // ~unordered_multiset() = default;
1089 _LIBCPP_INLINE_VISIBILITY
1090 unordered_multiset& operator=(const unordered_multiset& __u)
1092 __table_ = __u.__table_;
1095 #ifndef _LIBCPP_CXX03_LANG
1096 _LIBCPP_INLINE_VISIBILITY
1097 unordered_multiset& operator=(unordered_multiset&& __u)
1098 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1099 unordered_multiset& operator=(initializer_list<value_type> __il);
1100 #endif // _LIBCPP_CXX03_LANG
1102 _LIBCPP_INLINE_VISIBILITY
1103 allocator_type get_allocator() const _NOEXCEPT
1104 {return allocator_type(__table_.__node_alloc());}
1106 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1107 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1108 _LIBCPP_INLINE_VISIBILITY
1109 size_type size() const _NOEXCEPT {return __table_.size();}
1110 _LIBCPP_INLINE_VISIBILITY
1111 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1113 _LIBCPP_INLINE_VISIBILITY
1114 iterator begin() _NOEXCEPT {return __table_.begin();}
1115 _LIBCPP_INLINE_VISIBILITY
1116 iterator end() _NOEXCEPT {return __table_.end();}
1117 _LIBCPP_INLINE_VISIBILITY
1118 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1119 _LIBCPP_INLINE_VISIBILITY
1120 const_iterator end() const _NOEXCEPT {return __table_.end();}
1121 _LIBCPP_INLINE_VISIBILITY
1122 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1123 _LIBCPP_INLINE_VISIBILITY
1124 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1126 #ifndef _LIBCPP_CXX03_LANG
1127 template <class... _Args>
1128 _LIBCPP_INLINE_VISIBILITY
1129 iterator emplace(_Args&&... __args)
1130 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1131 template <class... _Args>
1132 _LIBCPP_INLINE_VISIBILITY
1133 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1134 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1136 _LIBCPP_INLINE_VISIBILITY
1137 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1138 _LIBCPP_INLINE_VISIBILITY
1139 iterator insert(const_iterator __p, value_type&& __x)
1140 {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1141 _LIBCPP_INLINE_VISIBILITY
1142 void insert(initializer_list<value_type> __il)
1143 {insert(__il.begin(), __il.end());}
1144 #endif // _LIBCPP_CXX03_LANG
1146 _LIBCPP_INLINE_VISIBILITY
1147 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1149 _LIBCPP_INLINE_VISIBILITY
1150 iterator insert(const_iterator __p, const value_type& __x)
1151 {return __table_.__insert_multi(__p, __x);}
1153 template <class _InputIterator>
1154 _LIBCPP_INLINE_VISIBILITY
1155 void insert(_InputIterator __first, _InputIterator __last);
1157 #if _LIBCPP_STD_VER > 14
1158 _LIBCPP_INLINE_VISIBILITY
1159 iterator insert(node_type&& __nh)
1161 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1162 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1163 return __table_.template __node_handle_insert_multi<node_type>(
1166 _LIBCPP_INLINE_VISIBILITY
1167 iterator insert(const_iterator __hint, node_type&& __nh)
1169 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1170 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1171 return __table_.template __node_handle_insert_multi<node_type>(
1172 __hint, _VSTD::move(__nh));
1174 _LIBCPP_INLINE_VISIBILITY
1175 node_type extract(const_iterator __position)
1177 return __table_.template __node_handle_extract<node_type>(
1180 _LIBCPP_INLINE_VISIBILITY
1181 node_type extract(key_type const& __key)
1183 return __table_.template __node_handle_extract<node_type>(__key);
1186 template <class _H2, class _P2>
1187 _LIBCPP_INLINE_VISIBILITY
1188 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
1190 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1191 "merging container with incompatible allocator");
1192 return __table_.__node_handle_merge_multi(__source.__table_);
1194 template <class _H2, class _P2>
1195 _LIBCPP_INLINE_VISIBILITY
1196 void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
1198 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1199 "merging container with incompatible allocator");
1200 return __table_.__node_handle_merge_multi(__source.__table_);
1202 template <class _H2, class _P2>
1203 _LIBCPP_INLINE_VISIBILITY
1204 void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
1206 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1207 "merging container with incompatible allocator");
1208 return __table_.__node_handle_merge_multi(__source.__table_);
1210 template <class _H2, class _P2>
1211 _LIBCPP_INLINE_VISIBILITY
1212 void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
1214 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
1215 "merging container with incompatible allocator");
1216 return __table_.__node_handle_merge_multi(__source.__table_);
1220 _LIBCPP_INLINE_VISIBILITY
1221 iterator erase(const_iterator __p) {return __table_.erase(__p);}
1222 _LIBCPP_INLINE_VISIBILITY
1223 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1224 _LIBCPP_INLINE_VISIBILITY
1225 iterator erase(const_iterator __first, const_iterator __last)
1226 {return __table_.erase(__first, __last);}
1227 _LIBCPP_INLINE_VISIBILITY
1228 void clear() _NOEXCEPT {__table_.clear();}
1230 _LIBCPP_INLINE_VISIBILITY
1231 void swap(unordered_multiset& __u)
1232 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1233 {__table_.swap(__u.__table_);}
1235 _LIBCPP_INLINE_VISIBILITY
1236 hasher hash_function() const {return __table_.hash_function();}
1237 _LIBCPP_INLINE_VISIBILITY
1238 key_equal key_eq() const {return __table_.key_eq();}
1240 _LIBCPP_INLINE_VISIBILITY
1241 iterator find(const key_type& __k) {return __table_.find(__k);}
1242 _LIBCPP_INLINE_VISIBILITY
1243 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1244 _LIBCPP_INLINE_VISIBILITY
1245 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1246 _LIBCPP_INLINE_VISIBILITY
1247 pair<iterator, iterator> equal_range(const key_type& __k)
1248 {return __table_.__equal_range_multi(__k);}
1249 _LIBCPP_INLINE_VISIBILITY
1250 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1251 {return __table_.__equal_range_multi(__k);}
1253 _LIBCPP_INLINE_VISIBILITY
1254 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1255 _LIBCPP_INLINE_VISIBILITY
1256 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1258 _LIBCPP_INLINE_VISIBILITY
1259 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1260 _LIBCPP_INLINE_VISIBILITY
1261 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1263 _LIBCPP_INLINE_VISIBILITY
1264 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1265 _LIBCPP_INLINE_VISIBILITY
1266 local_iterator end(size_type __n) {return __table_.end(__n);}
1267 _LIBCPP_INLINE_VISIBILITY
1268 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1269 _LIBCPP_INLINE_VISIBILITY
1270 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1271 _LIBCPP_INLINE_VISIBILITY
1272 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1273 _LIBCPP_INLINE_VISIBILITY
1274 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1276 _LIBCPP_INLINE_VISIBILITY
1277 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1278 _LIBCPP_INLINE_VISIBILITY
1279 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1280 _LIBCPP_INLINE_VISIBILITY
1281 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1282 _LIBCPP_INLINE_VISIBILITY
1283 void rehash(size_type __n) {__table_.rehash(__n);}
1284 _LIBCPP_INLINE_VISIBILITY
1285 void reserve(size_type __n) {__table_.reserve(__n);}
1287 #if _LIBCPP_DEBUG_LEVEL >= 2
1289 bool __dereferenceable(const const_iterator* __i) const
1290 {return __table_.__dereferenceable(__i);}
1291 bool __decrementable(const const_iterator* __i) const
1292 {return __table_.__decrementable(__i);}
1293 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1294 {return __table_.__addable(__i, __n);}
1295 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1296 {return __table_.__addable(__i, __n);}
1298 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1302 template <class _Value, class _Hash, class _Pred, class _Alloc>
1303 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1304 size_type __n, const hasher& __hf, const key_equal& __eql)
1305 : __table_(__hf, __eql)
1307 #if _LIBCPP_DEBUG_LEVEL >= 2
1308 __get_db()->__insert_c(this);
1310 __table_.rehash(__n);
1313 template <class _Value, class _Hash, class _Pred, class _Alloc>
1314 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1315 size_type __n, const hasher& __hf, const key_equal& __eql,
1316 const allocator_type& __a)
1317 : __table_(__hf, __eql, __a)
1319 #if _LIBCPP_DEBUG_LEVEL >= 2
1320 __get_db()->__insert_c(this);
1322 __table_.rehash(__n);
1325 template <class _Value, class _Hash, class _Pred, class _Alloc>
1326 template <class _InputIterator>
1327 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1328 _InputIterator __first, _InputIterator __last)
1330 #if _LIBCPP_DEBUG_LEVEL >= 2
1331 __get_db()->__insert_c(this);
1333 insert(__first, __last);
1336 template <class _Value, class _Hash, class _Pred, class _Alloc>
1337 template <class _InputIterator>
1338 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1339 _InputIterator __first, _InputIterator __last, size_type __n,
1340 const hasher& __hf, const key_equal& __eql)
1341 : __table_(__hf, __eql)
1343 #if _LIBCPP_DEBUG_LEVEL >= 2
1344 __get_db()->__insert_c(this);
1346 __table_.rehash(__n);
1347 insert(__first, __last);
1350 template <class _Value, class _Hash, class _Pred, class _Alloc>
1351 template <class _InputIterator>
1352 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1353 _InputIterator __first, _InputIterator __last, size_type __n,
1354 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1355 : __table_(__hf, __eql, __a)
1357 #if _LIBCPP_DEBUG_LEVEL >= 2
1358 __get_db()->__insert_c(this);
1360 __table_.rehash(__n);
1361 insert(__first, __last);
1364 template <class _Value, class _Hash, class _Pred, class _Alloc>
1366 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1367 const allocator_type& __a)
1370 #if _LIBCPP_DEBUG_LEVEL >= 2
1371 __get_db()->__insert_c(this);
1375 template <class _Value, class _Hash, class _Pred, class _Alloc>
1376 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1377 const unordered_multiset& __u)
1378 : __table_(__u.__table_)
1380 #if _LIBCPP_DEBUG_LEVEL >= 2
1381 __get_db()->__insert_c(this);
1383 __table_.rehash(__u.bucket_count());
1384 insert(__u.begin(), __u.end());
1387 template <class _Value, class _Hash, class _Pred, class _Alloc>
1388 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1389 const unordered_multiset& __u, const allocator_type& __a)
1390 : __table_(__u.__table_, __a)
1392 #if _LIBCPP_DEBUG_LEVEL >= 2
1393 __get_db()->__insert_c(this);
1395 __table_.rehash(__u.bucket_count());
1396 insert(__u.begin(), __u.end());
1399 #ifndef _LIBCPP_CXX03_LANG
1401 template <class _Value, class _Hash, class _Pred, class _Alloc>
1403 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1404 unordered_multiset&& __u)
1405 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1406 : __table_(_VSTD::move(__u.__table_))
1408 #if _LIBCPP_DEBUG_LEVEL >= 2
1409 __get_db()->__insert_c(this);
1410 __get_db()->swap(this, &__u);
1414 template <class _Value, class _Hash, class _Pred, class _Alloc>
1415 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1416 unordered_multiset&& __u, const allocator_type& __a)
1417 : __table_(_VSTD::move(__u.__table_), __a)
1419 #if _LIBCPP_DEBUG_LEVEL >= 2
1420 __get_db()->__insert_c(this);
1422 if (__a != __u.get_allocator())
1424 iterator __i = __u.begin();
1425 while (__u.size() != 0)
1426 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1428 #if _LIBCPP_DEBUG_LEVEL >= 2
1430 __get_db()->swap(this, &__u);
1434 template <class _Value, class _Hash, class _Pred, class _Alloc>
1435 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1436 initializer_list<value_type> __il)
1438 #if _LIBCPP_DEBUG_LEVEL >= 2
1439 __get_db()->__insert_c(this);
1441 insert(__il.begin(), __il.end());
1444 template <class _Value, class _Hash, class _Pred, class _Alloc>
1445 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1446 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1447 const key_equal& __eql)
1448 : __table_(__hf, __eql)
1450 #if _LIBCPP_DEBUG_LEVEL >= 2
1451 __get_db()->__insert_c(this);
1453 __table_.rehash(__n);
1454 insert(__il.begin(), __il.end());
1457 template <class _Value, class _Hash, class _Pred, class _Alloc>
1458 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1459 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1460 const key_equal& __eql, const allocator_type& __a)
1461 : __table_(__hf, __eql, __a)
1463 #if _LIBCPP_DEBUG_LEVEL >= 2
1464 __get_db()->__insert_c(this);
1466 __table_.rehash(__n);
1467 insert(__il.begin(), __il.end());
1470 template <class _Value, class _Hash, class _Pred, class _Alloc>
1472 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1473 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1474 unordered_multiset&& __u)
1475 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1477 __table_ = _VSTD::move(__u.__table_);
1481 template <class _Value, class _Hash, class _Pred, class _Alloc>
1483 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1484 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1485 initializer_list<value_type> __il)
1487 __table_.__assign_multi(__il.begin(), __il.end());
1491 #endif // _LIBCPP_CXX03_LANG
1493 template <class _Value, class _Hash, class _Pred, class _Alloc>
1494 template <class _InputIterator>
1497 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1498 _InputIterator __last)
1500 for (; __first != __last; ++__first)
1501 __table_.__insert_multi(*__first);
1504 template <class _Value, class _Hash, class _Pred, class _Alloc>
1505 inline _LIBCPP_INLINE_VISIBILITY
1507 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1508 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1509 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1514 #if _LIBCPP_STD_VER > 17
1515 template <class _Value, class _Hash, class _Pred, class _Alloc, class _Predicate>
1516 inline _LIBCPP_INLINE_VISIBILITY
1517 void erase_if(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __c, _Predicate __pred)
1518 { __libcpp_erase_if_container(__c, __pred); }
1521 template <class _Value, class _Hash, class _Pred, class _Alloc>
1523 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1524 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1526 if (__x.size() != __y.size())
1528 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1530 typedef pair<const_iterator, const_iterator> _EqRng;
1531 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1533 _EqRng __xeq = __x.equal_range(*__i);
1534 _EqRng __yeq = __y.equal_range(*__i);
1535 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1536 _VSTD::distance(__yeq.first, __yeq.second) ||
1537 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1544 template <class _Value, class _Hash, class _Pred, class _Alloc>
1545 inline _LIBCPP_INLINE_VISIBILITY
1547 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1548 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1550 return !(__x == __y);
1553 _LIBCPP_END_NAMESPACE_STD
1555 #endif // _LIBCPP_UNORDERED_SET