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;
48 is_nothrow_default_constructible<hasher>::value &&
49 is_nothrow_default_constructible<key_equal>::value &&
50 is_nothrow_default_constructible<allocator_type>::value);
51 explicit unordered_set(size_type n, const hasher& hf = hasher(),
52 const key_equal& eql = key_equal(),
53 const allocator_type& a = allocator_type());
54 template <class InputIterator>
55 unordered_set(InputIterator f, InputIterator l,
56 size_type n = 0, const hasher& hf = hasher(),
57 const key_equal& eql = key_equal(),
58 const allocator_type& a = allocator_type());
59 explicit unordered_set(const allocator_type&);
60 unordered_set(const unordered_set&);
61 unordered_set(const unordered_set&, const Allocator&);
62 unordered_set(unordered_set&&)
64 is_nothrow_move_constructible<hasher>::value &&
65 is_nothrow_move_constructible<key_equal>::value &&
66 is_nothrow_move_constructible<allocator_type>::value);
67 unordered_set(unordered_set&&, const Allocator&);
68 unordered_set(initializer_list<value_type>, size_type n = 0,
69 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
70 const allocator_type& a = allocator_type());
71 unordered_set(size_type n, const allocator_type& a); // C++14
72 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
73 template <class InputIterator>
74 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
75 template <class InputIterator>
76 unordered_set(InputIterator f, InputIterator l, size_type n,
77 const hasher& hf, const allocator_type& a); // C++14
78 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
79 unordered_set(initializer_list<value_type> il, size_type n,
80 const hasher& hf, const allocator_type& a); // C++14
82 unordered_set& operator=(const unordered_set&);
83 unordered_set& operator=(unordered_set&&)
85 allocator_type::propagate_on_container_move_assignment::value &&
86 is_nothrow_move_assignable<allocator_type>::value &&
87 is_nothrow_move_assignable<hasher>::value &&
88 is_nothrow_move_assignable<key_equal>::value);
89 unordered_set& operator=(initializer_list<value_type>);
91 allocator_type get_allocator() const noexcept;
93 bool empty() const noexcept;
94 size_type size() const noexcept;
95 size_type max_size() const noexcept;
97 iterator begin() noexcept;
98 iterator end() noexcept;
99 const_iterator begin() const noexcept;
100 const_iterator end() const noexcept;
101 const_iterator cbegin() const noexcept;
102 const_iterator cend() const noexcept;
104 template <class... Args>
105 pair<iterator, bool> emplace(Args&&... args);
106 template <class... Args>
107 iterator emplace_hint(const_iterator position, Args&&... args);
108 pair<iterator, bool> insert(const value_type& obj);
109 pair<iterator, bool> insert(value_type&& obj);
110 iterator insert(const_iterator hint, const value_type& obj);
111 iterator insert(const_iterator hint, value_type&& obj);
112 template <class InputIterator>
113 void insert(InputIterator first, InputIterator last);
114 void insert(initializer_list<value_type>);
116 iterator erase(const_iterator position);
117 iterator erase(iterator position); // C++14
118 size_type erase(const key_type& k);
119 iterator erase(const_iterator first, const_iterator last);
120 void clear() noexcept;
122 void swap(unordered_set&)
123 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
124 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
125 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
127 hasher hash_function() const;
128 key_equal key_eq() const;
130 iterator find(const key_type& k);
131 const_iterator find(const key_type& k) const;
132 size_type count(const key_type& k) const;
133 pair<iterator, iterator> equal_range(const key_type& k);
134 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
136 size_type bucket_count() const noexcept;
137 size_type max_bucket_count() const noexcept;
139 size_type bucket_size(size_type n) const;
140 size_type bucket(const key_type& k) const;
142 local_iterator begin(size_type n);
143 local_iterator end(size_type n);
144 const_local_iterator begin(size_type n) const;
145 const_local_iterator end(size_type n) const;
146 const_local_iterator cbegin(size_type n) const;
147 const_local_iterator cend(size_type n) const;
149 float load_factor() const noexcept;
150 float max_load_factor() const noexcept;
151 void max_load_factor(float z);
152 void rehash(size_type n);
153 void reserve(size_type n);
156 template <class Value, class Hash, class Pred, class Alloc>
157 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
158 unordered_set<Value, Hash, Pred, Alloc>& y)
159 noexcept(noexcept(x.swap(y)));
161 template <class Value, class Hash, class Pred, class Alloc>
163 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
164 const unordered_set<Value, Hash, Pred, Alloc>& y);
166 template <class Value, class Hash, class Pred, class Alloc>
168 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
169 const unordered_set<Value, Hash, Pred, Alloc>& y);
171 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
172 class Alloc = allocator<Value>>
173 class unordered_multiset
177 typedef Value key_type;
178 typedef key_type value_type;
180 typedef Pred key_equal;
181 typedef Alloc allocator_type;
182 typedef value_type& reference;
183 typedef const value_type& const_reference;
184 typedef typename allocator_traits<allocator_type>::pointer pointer;
185 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
186 typedef typename allocator_traits<allocator_type>::size_type size_type;
187 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
189 typedef /unspecified/ iterator;
190 typedef /unspecified/ const_iterator;
191 typedef /unspecified/ local_iterator;
192 typedef /unspecified/ const_local_iterator;
196 is_nothrow_default_constructible<hasher>::value &&
197 is_nothrow_default_constructible<key_equal>::value &&
198 is_nothrow_default_constructible<allocator_type>::value);
199 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
200 const key_equal& eql = key_equal(),
201 const allocator_type& a = allocator_type());
202 template <class InputIterator>
203 unordered_multiset(InputIterator f, InputIterator l,
204 size_type n = 0, const hasher& hf = hasher(),
205 const key_equal& eql = key_equal(),
206 const allocator_type& a = allocator_type());
207 explicit unordered_multiset(const allocator_type&);
208 unordered_multiset(const unordered_multiset&);
209 unordered_multiset(const unordered_multiset&, const Allocator&);
210 unordered_multiset(unordered_multiset&&)
212 is_nothrow_move_constructible<hasher>::value &&
213 is_nothrow_move_constructible<key_equal>::value &&
214 is_nothrow_move_constructible<allocator_type>::value);
215 unordered_multiset(unordered_multiset&&, const Allocator&);
216 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
217 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
218 const allocator_type& a = allocator_type());
219 unordered_multiset(size_type n, const allocator_type& a); // C++14
220 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
221 template <class InputIterator>
222 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
223 template <class InputIterator>
224 unordered_multiset(InputIterator f, InputIterator l, size_type n,
225 const hasher& hf, const allocator_type& a); // C++14
226 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
227 unordered_multiset(initializer_list<value_type> il, size_type n,
228 const hasher& hf, const allocator_type& a); // C++14
229 ~unordered_multiset();
230 unordered_multiset& operator=(const unordered_multiset&);
231 unordered_multiset& operator=(unordered_multiset&&)
233 allocator_type::propagate_on_container_move_assignment::value &&
234 is_nothrow_move_assignable<allocator_type>::value &&
235 is_nothrow_move_assignable<hasher>::value &&
236 is_nothrow_move_assignable<key_equal>::value);
237 unordered_multiset& operator=(initializer_list<value_type>);
239 allocator_type get_allocator() const noexcept;
241 bool empty() const noexcept;
242 size_type size() const noexcept;
243 size_type max_size() const noexcept;
245 iterator begin() noexcept;
246 iterator end() noexcept;
247 const_iterator begin() const noexcept;
248 const_iterator end() const noexcept;
249 const_iterator cbegin() const noexcept;
250 const_iterator cend() const noexcept;
252 template <class... Args>
253 iterator emplace(Args&&... args);
254 template <class... Args>
255 iterator emplace_hint(const_iterator position, Args&&... args);
256 iterator insert(const value_type& obj);
257 iterator insert(value_type&& obj);
258 iterator insert(const_iterator hint, const value_type& obj);
259 iterator insert(const_iterator hint, value_type&& obj);
260 template <class InputIterator>
261 void insert(InputIterator first, InputIterator last);
262 void insert(initializer_list<value_type>);
264 iterator erase(const_iterator position);
265 iterator erase(iterator position); // C++14
266 size_type erase(const key_type& k);
267 iterator erase(const_iterator first, const_iterator last);
268 void clear() noexcept;
270 void swap(unordered_multiset&)
271 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
272 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
273 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
275 hasher hash_function() const;
276 key_equal key_eq() const;
278 iterator find(const key_type& k);
279 const_iterator find(const key_type& k) const;
280 size_type count(const key_type& k) const;
281 pair<iterator, iterator> equal_range(const key_type& k);
282 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
284 size_type bucket_count() const noexcept;
285 size_type max_bucket_count() const noexcept;
287 size_type bucket_size(size_type n) const;
288 size_type bucket(const key_type& k) const;
290 local_iterator begin(size_type n);
291 local_iterator end(size_type n);
292 const_local_iterator begin(size_type n) const;
293 const_local_iterator end(size_type n) const;
294 const_local_iterator cbegin(size_type n) const;
295 const_local_iterator cend(size_type n) const;
297 float load_factor() const noexcept;
298 float max_load_factor() const noexcept;
299 void max_load_factor(float z);
300 void rehash(size_type n);
301 void reserve(size_type n);
304 template <class Value, class Hash, class Pred, class Alloc>
305 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
306 unordered_multiset<Value, Hash, Pred, Alloc>& y)
307 noexcept(noexcept(x.swap(y)));
309 template <class Value, class Hash, class Pred, class Alloc>
311 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
312 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
314 template <class Value, class Hash, class Pred, class Alloc>
316 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
317 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
323 #include <__hash_table>
324 #include <functional>
328 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
329 #pragma GCC system_header
332 _LIBCPP_BEGIN_NAMESPACE_STD
334 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
335 class _Alloc = allocator<_Value> >
336 class _LIBCPP_TEMPLATE_VIS unordered_set
340 typedef _Value key_type;
341 typedef key_type value_type;
342 typedef _Hash hasher;
343 typedef _Pred key_equal;
344 typedef _Alloc allocator_type;
345 typedef value_type& reference;
346 typedef const value_type& const_reference;
347 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
348 "Invalid allocator::value_type");
351 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
356 typedef typename __table::pointer pointer;
357 typedef typename __table::const_pointer const_pointer;
358 typedef typename __table::size_type size_type;
359 typedef typename __table::difference_type difference_type;
361 typedef typename __table::const_iterator iterator;
362 typedef typename __table::const_iterator const_iterator;
363 typedef typename __table::const_local_iterator local_iterator;
364 typedef typename __table::const_local_iterator const_local_iterator;
366 _LIBCPP_INLINE_VISIBILITY
368 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
370 #if _LIBCPP_DEBUG_LEVEL >= 2
371 __get_db()->__insert_c(this);
374 explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
375 const key_equal& __eql = key_equal());
376 #if _LIBCPP_STD_VER > 11
377 inline _LIBCPP_INLINE_VISIBILITY
378 unordered_set(size_type __n, const allocator_type& __a)
379 : unordered_set(__n, hasher(), key_equal(), __a) {}
380 inline _LIBCPP_INLINE_VISIBILITY
381 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
382 : unordered_set(__n, __hf, key_equal(), __a) {}
384 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
385 const allocator_type& __a);
386 template <class _InputIterator>
387 unordered_set(_InputIterator __first, _InputIterator __last);
388 template <class _InputIterator>
389 unordered_set(_InputIterator __first, _InputIterator __last,
390 size_type __n, const hasher& __hf = hasher(),
391 const key_equal& __eql = key_equal());
392 template <class _InputIterator>
393 unordered_set(_InputIterator __first, _InputIterator __last,
394 size_type __n, const hasher& __hf, const key_equal& __eql,
395 const allocator_type& __a);
396 #if _LIBCPP_STD_VER > 11
397 template <class _InputIterator>
398 inline _LIBCPP_INLINE_VISIBILITY
399 unordered_set(_InputIterator __first, _InputIterator __last,
400 size_type __n, const allocator_type& __a)
401 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
402 template <class _InputIterator>
403 unordered_set(_InputIterator __first, _InputIterator __last,
404 size_type __n, const hasher& __hf, const allocator_type& __a)
405 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
407 _LIBCPP_INLINE_VISIBILITY
408 explicit unordered_set(const allocator_type& __a);
409 unordered_set(const unordered_set& __u);
410 unordered_set(const unordered_set& __u, const allocator_type& __a);
411 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
412 _LIBCPP_INLINE_VISIBILITY
413 unordered_set(unordered_set&& __u)
414 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
415 unordered_set(unordered_set&& __u, const allocator_type& __a);
416 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
417 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
418 unordered_set(initializer_list<value_type> __il);
419 unordered_set(initializer_list<value_type> __il, size_type __n,
420 const hasher& __hf = hasher(),
421 const key_equal& __eql = key_equal());
422 unordered_set(initializer_list<value_type> __il, size_type __n,
423 const hasher& __hf, const key_equal& __eql,
424 const allocator_type& __a);
425 #if _LIBCPP_STD_VER > 11
426 inline _LIBCPP_INLINE_VISIBILITY
427 unordered_set(initializer_list<value_type> __il, size_type __n,
428 const allocator_type& __a)
429 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
430 inline _LIBCPP_INLINE_VISIBILITY
431 unordered_set(initializer_list<value_type> __il, size_type __n,
432 const hasher& __hf, const allocator_type& __a)
433 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
435 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
436 // ~unordered_set() = default;
437 _LIBCPP_INLINE_VISIBILITY
438 unordered_set& operator=(const unordered_set& __u)
440 __table_ = __u.__table_;
443 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
444 _LIBCPP_INLINE_VISIBILITY
445 unordered_set& operator=(unordered_set&& __u)
446 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
448 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
449 _LIBCPP_INLINE_VISIBILITY
450 unordered_set& operator=(initializer_list<value_type> __il);
451 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
453 _LIBCPP_INLINE_VISIBILITY
454 allocator_type get_allocator() const _NOEXCEPT
455 {return allocator_type(__table_.__node_alloc());}
457 _LIBCPP_INLINE_VISIBILITY
458 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
459 _LIBCPP_INLINE_VISIBILITY
460 size_type size() const _NOEXCEPT {return __table_.size();}
461 _LIBCPP_INLINE_VISIBILITY
462 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
464 _LIBCPP_INLINE_VISIBILITY
465 iterator begin() _NOEXCEPT {return __table_.begin();}
466 _LIBCPP_INLINE_VISIBILITY
467 iterator end() _NOEXCEPT {return __table_.end();}
468 _LIBCPP_INLINE_VISIBILITY
469 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
470 _LIBCPP_INLINE_VISIBILITY
471 const_iterator end() const _NOEXCEPT {return __table_.end();}
472 _LIBCPP_INLINE_VISIBILITY
473 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
474 _LIBCPP_INLINE_VISIBILITY
475 const_iterator cend() const _NOEXCEPT {return __table_.end();}
477 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
478 template <class... _Args>
479 _LIBCPP_INLINE_VISIBILITY
480 pair<iterator, bool> emplace(_Args&&... __args)
481 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
482 template <class... _Args>
483 _LIBCPP_INLINE_VISIBILITY
484 #if _LIBCPP_DEBUG_LEVEL >= 2
485 iterator emplace_hint(const_iterator __p, _Args&&... __args)
487 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
488 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
489 " referring to this unordered_set");
490 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
493 iterator emplace_hint(const_iterator, _Args&&... __args)
494 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
496 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
497 _LIBCPP_INLINE_VISIBILITY
498 pair<iterator, bool> insert(const value_type& __x)
499 {return __table_.__insert_unique(__x);}
500 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
501 _LIBCPP_INLINE_VISIBILITY
502 pair<iterator, bool> insert(value_type&& __x)
503 {return __table_.__insert_unique(_VSTD::move(__x));}
504 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
505 _LIBCPP_INLINE_VISIBILITY
506 #if _LIBCPP_DEBUG_LEVEL >= 2
507 iterator insert(const_iterator __p, const value_type& __x)
509 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
510 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
511 " referring to this unordered_set");
512 return insert(__x).first;
515 iterator insert(const_iterator, const value_type& __x)
516 {return insert(__x).first;}
518 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
519 _LIBCPP_INLINE_VISIBILITY
520 #if _LIBCPP_DEBUG_LEVEL >= 2
521 iterator insert(const_iterator __p, value_type&& __x)
523 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
524 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
525 " referring to this unordered_set");
526 return insert(_VSTD::move(__x)).first;
529 iterator insert(const_iterator, value_type&& __x)
530 {return insert(_VSTD::move(__x)).first;}
532 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
533 template <class _InputIterator>
534 _LIBCPP_INLINE_VISIBILITY
535 void insert(_InputIterator __first, _InputIterator __last);
536 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
537 _LIBCPP_INLINE_VISIBILITY
538 void insert(initializer_list<value_type> __il)
539 {insert(__il.begin(), __il.end());}
540 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
542 _LIBCPP_INLINE_VISIBILITY
543 iterator erase(const_iterator __p) {return __table_.erase(__p);}
544 _LIBCPP_INLINE_VISIBILITY
545 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
546 _LIBCPP_INLINE_VISIBILITY
547 iterator erase(const_iterator __first, const_iterator __last)
548 {return __table_.erase(__first, __last);}
549 _LIBCPP_INLINE_VISIBILITY
550 void clear() _NOEXCEPT {__table_.clear();}
552 _LIBCPP_INLINE_VISIBILITY
553 void swap(unordered_set& __u)
554 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
555 {__table_.swap(__u.__table_);}
557 _LIBCPP_INLINE_VISIBILITY
558 hasher hash_function() const {return __table_.hash_function();}
559 _LIBCPP_INLINE_VISIBILITY
560 key_equal key_eq() const {return __table_.key_eq();}
562 _LIBCPP_INLINE_VISIBILITY
563 iterator find(const key_type& __k) {return __table_.find(__k);}
564 _LIBCPP_INLINE_VISIBILITY
565 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
566 _LIBCPP_INLINE_VISIBILITY
567 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
568 _LIBCPP_INLINE_VISIBILITY
569 pair<iterator, iterator> equal_range(const key_type& __k)
570 {return __table_.__equal_range_unique(__k);}
571 _LIBCPP_INLINE_VISIBILITY
572 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
573 {return __table_.__equal_range_unique(__k);}
575 _LIBCPP_INLINE_VISIBILITY
576 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
577 _LIBCPP_INLINE_VISIBILITY
578 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
580 _LIBCPP_INLINE_VISIBILITY
581 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
582 _LIBCPP_INLINE_VISIBILITY
583 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
585 _LIBCPP_INLINE_VISIBILITY
586 local_iterator begin(size_type __n) {return __table_.begin(__n);}
587 _LIBCPP_INLINE_VISIBILITY
588 local_iterator end(size_type __n) {return __table_.end(__n);}
589 _LIBCPP_INLINE_VISIBILITY
590 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
591 _LIBCPP_INLINE_VISIBILITY
592 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
593 _LIBCPP_INLINE_VISIBILITY
594 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
595 _LIBCPP_INLINE_VISIBILITY
596 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
598 _LIBCPP_INLINE_VISIBILITY
599 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
600 _LIBCPP_INLINE_VISIBILITY
601 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
602 _LIBCPP_INLINE_VISIBILITY
603 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
604 _LIBCPP_INLINE_VISIBILITY
605 void rehash(size_type __n) {__table_.rehash(__n);}
606 _LIBCPP_INLINE_VISIBILITY
607 void reserve(size_type __n) {__table_.reserve(__n);}
609 #if _LIBCPP_DEBUG_LEVEL >= 2
611 bool __dereferenceable(const const_iterator* __i) const
612 {return __table_.__dereferenceable(__i);}
613 bool __decrementable(const const_iterator* __i) const
614 {return __table_.__decrementable(__i);}
615 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
616 {return __table_.__addable(__i, __n);}
617 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
618 {return __table_.__addable(__i, __n);}
620 #endif // _LIBCPP_DEBUG_LEVEL >= 2
624 template <class _Value, class _Hash, class _Pred, class _Alloc>
625 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
626 const hasher& __hf, const key_equal& __eql)
627 : __table_(__hf, __eql)
629 #if _LIBCPP_DEBUG_LEVEL >= 2
630 __get_db()->__insert_c(this);
632 __table_.rehash(__n);
635 template <class _Value, class _Hash, class _Pred, class _Alloc>
636 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
637 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
638 : __table_(__hf, __eql, __a)
640 #if _LIBCPP_DEBUG_LEVEL >= 2
641 __get_db()->__insert_c(this);
643 __table_.rehash(__n);
646 template <class _Value, class _Hash, class _Pred, class _Alloc>
647 template <class _InputIterator>
648 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
649 _InputIterator __first, _InputIterator __last)
651 #if _LIBCPP_DEBUG_LEVEL >= 2
652 __get_db()->__insert_c(this);
654 insert(__first, __last);
657 template <class _Value, class _Hash, class _Pred, class _Alloc>
658 template <class _InputIterator>
659 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
660 _InputIterator __first, _InputIterator __last, size_type __n,
661 const hasher& __hf, const key_equal& __eql)
662 : __table_(__hf, __eql)
664 #if _LIBCPP_DEBUG_LEVEL >= 2
665 __get_db()->__insert_c(this);
667 __table_.rehash(__n);
668 insert(__first, __last);
671 template <class _Value, class _Hash, class _Pred, class _Alloc>
672 template <class _InputIterator>
673 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
674 _InputIterator __first, _InputIterator __last, size_type __n,
675 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
676 : __table_(__hf, __eql, __a)
678 #if _LIBCPP_DEBUG_LEVEL >= 2
679 __get_db()->__insert_c(this);
681 __table_.rehash(__n);
682 insert(__first, __last);
685 template <class _Value, class _Hash, class _Pred, class _Alloc>
687 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
688 const allocator_type& __a)
691 #if _LIBCPP_DEBUG_LEVEL >= 2
692 __get_db()->__insert_c(this);
696 template <class _Value, class _Hash, class _Pred, class _Alloc>
697 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
698 const unordered_set& __u)
699 : __table_(__u.__table_)
701 #if _LIBCPP_DEBUG_LEVEL >= 2
702 __get_db()->__insert_c(this);
704 __table_.rehash(__u.bucket_count());
705 insert(__u.begin(), __u.end());
708 template <class _Value, class _Hash, class _Pred, class _Alloc>
709 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
710 const unordered_set& __u, const allocator_type& __a)
711 : __table_(__u.__table_, __a)
713 #if _LIBCPP_DEBUG_LEVEL >= 2
714 __get_db()->__insert_c(this);
716 __table_.rehash(__u.bucket_count());
717 insert(__u.begin(), __u.end());
720 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
722 template <class _Value, class _Hash, class _Pred, class _Alloc>
724 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
726 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
727 : __table_(_VSTD::move(__u.__table_))
729 #if _LIBCPP_DEBUG_LEVEL >= 2
730 __get_db()->__insert_c(this);
731 __get_db()->swap(this, &__u);
735 template <class _Value, class _Hash, class _Pred, class _Alloc>
736 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
737 unordered_set&& __u, const allocator_type& __a)
738 : __table_(_VSTD::move(__u.__table_), __a)
740 #if _LIBCPP_DEBUG_LEVEL >= 2
741 __get_db()->__insert_c(this);
743 if (__a != __u.get_allocator())
745 iterator __i = __u.begin();
746 while (__u.size() != 0)
747 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
749 #if _LIBCPP_DEBUG_LEVEL >= 2
751 __get_db()->swap(this, &__u);
755 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
757 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
759 template <class _Value, class _Hash, class _Pred, class _Alloc>
760 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
761 initializer_list<value_type> __il)
763 #if _LIBCPP_DEBUG_LEVEL >= 2
764 __get_db()->__insert_c(this);
766 insert(__il.begin(), __il.end());
769 template <class _Value, class _Hash, class _Pred, class _Alloc>
770 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
771 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
772 const key_equal& __eql)
773 : __table_(__hf, __eql)
775 #if _LIBCPP_DEBUG_LEVEL >= 2
776 __get_db()->__insert_c(this);
778 __table_.rehash(__n);
779 insert(__il.begin(), __il.end());
782 template <class _Value, class _Hash, class _Pred, class _Alloc>
783 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
784 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
785 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(__il.begin(), __il.end());
795 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
797 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
799 template <class _Value, class _Hash, class _Pred, class _Alloc>
801 unordered_set<_Value, _Hash, _Pred, _Alloc>&
802 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
803 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
805 __table_ = _VSTD::move(__u.__table_);
809 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
811 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
813 template <class _Value, class _Hash, class _Pred, class _Alloc>
815 unordered_set<_Value, _Hash, _Pred, _Alloc>&
816 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
817 initializer_list<value_type> __il)
819 __table_.__assign_unique(__il.begin(), __il.end());
823 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
825 template <class _Value, class _Hash, class _Pred, class _Alloc>
826 template <class _InputIterator>
829 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
830 _InputIterator __last)
832 for (; __first != __last; ++__first)
833 __table_.__insert_unique(*__first);
836 template <class _Value, class _Hash, class _Pred, class _Alloc>
837 inline _LIBCPP_INLINE_VISIBILITY
839 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
840 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
841 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
846 template <class _Value, class _Hash, class _Pred, class _Alloc>
848 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
849 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
851 if (__x.size() != __y.size())
853 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
855 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
858 const_iterator __j = __y.find(*__i);
859 if (__j == __ey || !(*__i == *__j))
865 template <class _Value, class _Hash, class _Pred, class _Alloc>
866 inline _LIBCPP_INLINE_VISIBILITY
868 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
869 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
871 return !(__x == __y);
874 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
875 class _Alloc = allocator<_Value> >
876 class _LIBCPP_TEMPLATE_VIS unordered_multiset
880 typedef _Value key_type;
881 typedef key_type value_type;
882 typedef _Hash hasher;
883 typedef _Pred key_equal;
884 typedef _Alloc allocator_type;
885 typedef value_type& reference;
886 typedef const value_type& const_reference;
887 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
888 "Invalid allocator::value_type");
891 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
896 typedef typename __table::pointer pointer;
897 typedef typename __table::const_pointer const_pointer;
898 typedef typename __table::size_type size_type;
899 typedef typename __table::difference_type difference_type;
901 typedef typename __table::const_iterator iterator;
902 typedef typename __table::const_iterator const_iterator;
903 typedef typename __table::const_local_iterator local_iterator;
904 typedef typename __table::const_local_iterator const_local_iterator;
906 _LIBCPP_INLINE_VISIBILITY
908 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
910 #if _LIBCPP_DEBUG_LEVEL >= 2
911 __get_db()->__insert_c(this);
914 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
915 const key_equal& __eql = key_equal());
916 unordered_multiset(size_type __n, const hasher& __hf,
917 const key_equal& __eql, const allocator_type& __a);
918 #if _LIBCPP_STD_VER > 11
919 inline _LIBCPP_INLINE_VISIBILITY
920 unordered_multiset(size_type __n, const allocator_type& __a)
921 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
922 inline _LIBCPP_INLINE_VISIBILITY
923 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
924 : unordered_multiset(__n, __hf, key_equal(), __a) {}
926 template <class _InputIterator>
927 unordered_multiset(_InputIterator __first, _InputIterator __last);
928 template <class _InputIterator>
929 unordered_multiset(_InputIterator __first, _InputIterator __last,
930 size_type __n, const hasher& __hf = hasher(),
931 const key_equal& __eql = key_equal());
932 template <class _InputIterator>
933 unordered_multiset(_InputIterator __first, _InputIterator __last,
934 size_type __n , const hasher& __hf,
935 const key_equal& __eql, const allocator_type& __a);
936 #if _LIBCPP_STD_VER > 11
937 template <class _InputIterator>
938 inline _LIBCPP_INLINE_VISIBILITY
939 unordered_multiset(_InputIterator __first, _InputIterator __last,
940 size_type __n, const allocator_type& __a)
941 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
942 template <class _InputIterator>
943 inline _LIBCPP_INLINE_VISIBILITY
944 unordered_multiset(_InputIterator __first, _InputIterator __last,
945 size_type __n, const hasher& __hf, const allocator_type& __a)
946 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
948 _LIBCPP_INLINE_VISIBILITY
949 explicit unordered_multiset(const allocator_type& __a);
950 unordered_multiset(const unordered_multiset& __u);
951 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
952 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
953 _LIBCPP_INLINE_VISIBILITY
954 unordered_multiset(unordered_multiset&& __u)
955 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
956 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
957 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
958 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
959 unordered_multiset(initializer_list<value_type> __il);
960 unordered_multiset(initializer_list<value_type> __il, size_type __n,
961 const hasher& __hf = hasher(),
962 const key_equal& __eql = key_equal());
963 unordered_multiset(initializer_list<value_type> __il, size_type __n,
964 const hasher& __hf, const key_equal& __eql,
965 const allocator_type& __a);
966 #if _LIBCPP_STD_VER > 11
967 inline _LIBCPP_INLINE_VISIBILITY
968 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
969 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
970 inline _LIBCPP_INLINE_VISIBILITY
971 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
972 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
974 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
975 // ~unordered_multiset() = default;
976 _LIBCPP_INLINE_VISIBILITY
977 unordered_multiset& operator=(const unordered_multiset& __u)
979 __table_ = __u.__table_;
982 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
983 _LIBCPP_INLINE_VISIBILITY
984 unordered_multiset& operator=(unordered_multiset&& __u)
985 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
987 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
988 unordered_multiset& operator=(initializer_list<value_type> __il);
989 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
991 _LIBCPP_INLINE_VISIBILITY
992 allocator_type get_allocator() const _NOEXCEPT
993 {return allocator_type(__table_.__node_alloc());}
995 _LIBCPP_INLINE_VISIBILITY
996 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
997 _LIBCPP_INLINE_VISIBILITY
998 size_type size() const _NOEXCEPT {return __table_.size();}
999 _LIBCPP_INLINE_VISIBILITY
1000 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1002 _LIBCPP_INLINE_VISIBILITY
1003 iterator begin() _NOEXCEPT {return __table_.begin();}
1004 _LIBCPP_INLINE_VISIBILITY
1005 iterator end() _NOEXCEPT {return __table_.end();}
1006 _LIBCPP_INLINE_VISIBILITY
1007 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1008 _LIBCPP_INLINE_VISIBILITY
1009 const_iterator end() const _NOEXCEPT {return __table_.end();}
1010 _LIBCPP_INLINE_VISIBILITY
1011 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1012 _LIBCPP_INLINE_VISIBILITY
1013 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1015 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1016 template <class... _Args>
1017 _LIBCPP_INLINE_VISIBILITY
1018 iterator emplace(_Args&&... __args)
1019 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1020 template <class... _Args>
1021 _LIBCPP_INLINE_VISIBILITY
1022 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1023 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1024 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1025 _LIBCPP_INLINE_VISIBILITY
1026 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1027 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1028 _LIBCPP_INLINE_VISIBILITY
1029 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1031 _LIBCPP_INLINE_VISIBILITY
1032 iterator insert(const_iterator __p, const value_type& __x)
1033 {return __table_.__insert_multi(__p, __x);}
1034 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1035 _LIBCPP_INLINE_VISIBILITY
1036 iterator insert(const_iterator __p, value_type&& __x)
1037 {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1038 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1039 template <class _InputIterator>
1040 _LIBCPP_INLINE_VISIBILITY
1041 void insert(_InputIterator __first, _InputIterator __last);
1042 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1043 _LIBCPP_INLINE_VISIBILITY
1044 void insert(initializer_list<value_type> __il)
1045 {insert(__il.begin(), __il.end());}
1046 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1048 _LIBCPP_INLINE_VISIBILITY
1049 iterator erase(const_iterator __p) {return __table_.erase(__p);}
1050 _LIBCPP_INLINE_VISIBILITY
1051 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1052 _LIBCPP_INLINE_VISIBILITY
1053 iterator erase(const_iterator __first, const_iterator __last)
1054 {return __table_.erase(__first, __last);}
1055 _LIBCPP_INLINE_VISIBILITY
1056 void clear() _NOEXCEPT {__table_.clear();}
1058 _LIBCPP_INLINE_VISIBILITY
1059 void swap(unordered_multiset& __u)
1060 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1061 {__table_.swap(__u.__table_);}
1063 _LIBCPP_INLINE_VISIBILITY
1064 hasher hash_function() const {return __table_.hash_function();}
1065 _LIBCPP_INLINE_VISIBILITY
1066 key_equal key_eq() const {return __table_.key_eq();}
1068 _LIBCPP_INLINE_VISIBILITY
1069 iterator find(const key_type& __k) {return __table_.find(__k);}
1070 _LIBCPP_INLINE_VISIBILITY
1071 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1072 _LIBCPP_INLINE_VISIBILITY
1073 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1074 _LIBCPP_INLINE_VISIBILITY
1075 pair<iterator, iterator> equal_range(const key_type& __k)
1076 {return __table_.__equal_range_multi(__k);}
1077 _LIBCPP_INLINE_VISIBILITY
1078 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1079 {return __table_.__equal_range_multi(__k);}
1081 _LIBCPP_INLINE_VISIBILITY
1082 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1083 _LIBCPP_INLINE_VISIBILITY
1084 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1086 _LIBCPP_INLINE_VISIBILITY
1087 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1088 _LIBCPP_INLINE_VISIBILITY
1089 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1091 _LIBCPP_INLINE_VISIBILITY
1092 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1093 _LIBCPP_INLINE_VISIBILITY
1094 local_iterator end(size_type __n) {return __table_.end(__n);}
1095 _LIBCPP_INLINE_VISIBILITY
1096 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1097 _LIBCPP_INLINE_VISIBILITY
1098 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1099 _LIBCPP_INLINE_VISIBILITY
1100 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1101 _LIBCPP_INLINE_VISIBILITY
1102 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1104 _LIBCPP_INLINE_VISIBILITY
1105 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1106 _LIBCPP_INLINE_VISIBILITY
1107 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1108 _LIBCPP_INLINE_VISIBILITY
1109 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1110 _LIBCPP_INLINE_VISIBILITY
1111 void rehash(size_type __n) {__table_.rehash(__n);}
1112 _LIBCPP_INLINE_VISIBILITY
1113 void reserve(size_type __n) {__table_.reserve(__n);}
1115 #if _LIBCPP_DEBUG_LEVEL >= 2
1117 bool __dereferenceable(const const_iterator* __i) const
1118 {return __table_.__dereferenceable(__i);}
1119 bool __decrementable(const const_iterator* __i) const
1120 {return __table_.__decrementable(__i);}
1121 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1122 {return __table_.__addable(__i, __n);}
1123 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1124 {return __table_.__addable(__i, __n);}
1126 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1130 template <class _Value, class _Hash, class _Pred, class _Alloc>
1131 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1132 size_type __n, const hasher& __hf, const key_equal& __eql)
1133 : __table_(__hf, __eql)
1135 #if _LIBCPP_DEBUG_LEVEL >= 2
1136 __get_db()->__insert_c(this);
1138 __table_.rehash(__n);
1141 template <class _Value, class _Hash, class _Pred, class _Alloc>
1142 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1143 size_type __n, const hasher& __hf, const key_equal& __eql,
1144 const allocator_type& __a)
1145 : __table_(__hf, __eql, __a)
1147 #if _LIBCPP_DEBUG_LEVEL >= 2
1148 __get_db()->__insert_c(this);
1150 __table_.rehash(__n);
1153 template <class _Value, class _Hash, class _Pred, class _Alloc>
1154 template <class _InputIterator>
1155 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1156 _InputIterator __first, _InputIterator __last)
1158 #if _LIBCPP_DEBUG_LEVEL >= 2
1159 __get_db()->__insert_c(this);
1161 insert(__first, __last);
1164 template <class _Value, class _Hash, class _Pred, class _Alloc>
1165 template <class _InputIterator>
1166 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1167 _InputIterator __first, _InputIterator __last, size_type __n,
1168 const hasher& __hf, const key_equal& __eql)
1169 : __table_(__hf, __eql)
1171 #if _LIBCPP_DEBUG_LEVEL >= 2
1172 __get_db()->__insert_c(this);
1174 __table_.rehash(__n);
1175 insert(__first, __last);
1178 template <class _Value, class _Hash, class _Pred, class _Alloc>
1179 template <class _InputIterator>
1180 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1181 _InputIterator __first, _InputIterator __last, size_type __n,
1182 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1183 : __table_(__hf, __eql, __a)
1185 #if _LIBCPP_DEBUG_LEVEL >= 2
1186 __get_db()->__insert_c(this);
1188 __table_.rehash(__n);
1189 insert(__first, __last);
1192 template <class _Value, class _Hash, class _Pred, class _Alloc>
1194 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1195 const allocator_type& __a)
1198 #if _LIBCPP_DEBUG_LEVEL >= 2
1199 __get_db()->__insert_c(this);
1203 template <class _Value, class _Hash, class _Pred, class _Alloc>
1204 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1205 const unordered_multiset& __u)
1206 : __table_(__u.__table_)
1208 #if _LIBCPP_DEBUG_LEVEL >= 2
1209 __get_db()->__insert_c(this);
1211 __table_.rehash(__u.bucket_count());
1212 insert(__u.begin(), __u.end());
1215 template <class _Value, class _Hash, class _Pred, class _Alloc>
1216 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1217 const unordered_multiset& __u, const allocator_type& __a)
1218 : __table_(__u.__table_, __a)
1220 #if _LIBCPP_DEBUG_LEVEL >= 2
1221 __get_db()->__insert_c(this);
1223 __table_.rehash(__u.bucket_count());
1224 insert(__u.begin(), __u.end());
1227 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1229 template <class _Value, class _Hash, class _Pred, class _Alloc>
1231 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1232 unordered_multiset&& __u)
1233 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1234 : __table_(_VSTD::move(__u.__table_))
1236 #if _LIBCPP_DEBUG_LEVEL >= 2
1237 __get_db()->__insert_c(this);
1238 __get_db()->swap(this, &__u);
1242 template <class _Value, class _Hash, class _Pred, class _Alloc>
1243 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1244 unordered_multiset&& __u, const allocator_type& __a)
1245 : __table_(_VSTD::move(__u.__table_), __a)
1247 #if _LIBCPP_DEBUG_LEVEL >= 2
1248 __get_db()->__insert_c(this);
1250 if (__a != __u.get_allocator())
1252 iterator __i = __u.begin();
1253 while (__u.size() != 0)
1254 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1256 #if _LIBCPP_DEBUG_LEVEL >= 2
1258 __get_db()->swap(this, &__u);
1262 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1264 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1266 template <class _Value, class _Hash, class _Pred, class _Alloc>
1267 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1268 initializer_list<value_type> __il)
1270 #if _LIBCPP_DEBUG_LEVEL >= 2
1271 __get_db()->__insert_c(this);
1273 insert(__il.begin(), __il.end());
1276 template <class _Value, class _Hash, class _Pred, class _Alloc>
1277 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1278 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1279 const key_equal& __eql)
1280 : __table_(__hf, __eql)
1282 #if _LIBCPP_DEBUG_LEVEL >= 2
1283 __get_db()->__insert_c(this);
1285 __table_.rehash(__n);
1286 insert(__il.begin(), __il.end());
1289 template <class _Value, class _Hash, class _Pred, class _Alloc>
1290 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1291 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1292 const key_equal& __eql, const allocator_type& __a)
1293 : __table_(__hf, __eql, __a)
1295 #if _LIBCPP_DEBUG_LEVEL >= 2
1296 __get_db()->__insert_c(this);
1298 __table_.rehash(__n);
1299 insert(__il.begin(), __il.end());
1302 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1304 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1306 template <class _Value, class _Hash, class _Pred, class _Alloc>
1308 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1309 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1310 unordered_multiset&& __u)
1311 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1313 __table_ = _VSTD::move(__u.__table_);
1317 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1319 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1321 template <class _Value, class _Hash, class _Pred, class _Alloc>
1323 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1324 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1325 initializer_list<value_type> __il)
1327 __table_.__assign_multi(__il.begin(), __il.end());
1331 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1333 template <class _Value, class _Hash, class _Pred, class _Alloc>
1334 template <class _InputIterator>
1337 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1338 _InputIterator __last)
1340 for (; __first != __last; ++__first)
1341 __table_.__insert_multi(*__first);
1344 template <class _Value, class _Hash, class _Pred, class _Alloc>
1345 inline _LIBCPP_INLINE_VISIBILITY
1347 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1348 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1349 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1354 template <class _Value, class _Hash, class _Pred, class _Alloc>
1356 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1357 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1359 if (__x.size() != __y.size())
1361 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1363 typedef pair<const_iterator, const_iterator> _EqRng;
1364 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1366 _EqRng __xeq = __x.equal_range(*__i);
1367 _EqRng __yeq = __y.equal_range(*__i);
1368 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1369 _VSTD::distance(__yeq.first, __yeq.second) ||
1370 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1377 template <class _Value, class _Hash, class _Pred, class _Alloc>
1378 inline _LIBCPP_INLINE_VISIBILITY
1380 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1381 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1383 return !(__x == __y);
1386 _LIBCPP_END_NAMESPACE_STD
1388 #endif // _LIBCPP_UNORDERED_SET