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_CXX03_LANG
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 unordered_set(initializer_list<value_type> __il);
417 unordered_set(initializer_list<value_type> __il, size_type __n,
418 const hasher& __hf = hasher(),
419 const key_equal& __eql = key_equal());
420 unordered_set(initializer_list<value_type> __il, size_type __n,
421 const hasher& __hf, const key_equal& __eql,
422 const allocator_type& __a);
423 #if _LIBCPP_STD_VER > 11
424 inline _LIBCPP_INLINE_VISIBILITY
425 unordered_set(initializer_list<value_type> __il, size_type __n,
426 const allocator_type& __a)
427 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
428 inline _LIBCPP_INLINE_VISIBILITY
429 unordered_set(initializer_list<value_type> __il, size_type __n,
430 const hasher& __hf, const allocator_type& __a)
431 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
433 #endif // _LIBCPP_CXX03_LANG
434 // ~unordered_set() = default;
435 _LIBCPP_INLINE_VISIBILITY
436 unordered_set& operator=(const unordered_set& __u)
438 __table_ = __u.__table_;
441 #ifndef _LIBCPP_CXX03_LANG
442 _LIBCPP_INLINE_VISIBILITY
443 unordered_set& operator=(unordered_set&& __u)
444 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
445 _LIBCPP_INLINE_VISIBILITY
446 unordered_set& operator=(initializer_list<value_type> __il);
447 #endif // _LIBCPP_CXX03_LANG
449 _LIBCPP_INLINE_VISIBILITY
450 allocator_type get_allocator() const _NOEXCEPT
451 {return allocator_type(__table_.__node_alloc());}
453 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
454 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
455 _LIBCPP_INLINE_VISIBILITY
456 size_type size() const _NOEXCEPT {return __table_.size();}
457 _LIBCPP_INLINE_VISIBILITY
458 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
460 _LIBCPP_INLINE_VISIBILITY
461 iterator begin() _NOEXCEPT {return __table_.begin();}
462 _LIBCPP_INLINE_VISIBILITY
463 iterator end() _NOEXCEPT {return __table_.end();}
464 _LIBCPP_INLINE_VISIBILITY
465 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
466 _LIBCPP_INLINE_VISIBILITY
467 const_iterator end() const _NOEXCEPT {return __table_.end();}
468 _LIBCPP_INLINE_VISIBILITY
469 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
470 _LIBCPP_INLINE_VISIBILITY
471 const_iterator cend() const _NOEXCEPT {return __table_.end();}
473 #ifndef _LIBCPP_CXX03_LANG
474 template <class... _Args>
475 _LIBCPP_INLINE_VISIBILITY
476 pair<iterator, bool> emplace(_Args&&... __args)
477 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
478 template <class... _Args>
479 _LIBCPP_INLINE_VISIBILITY
480 #if _LIBCPP_DEBUG_LEVEL >= 2
481 iterator emplace_hint(const_iterator __p, _Args&&... __args)
483 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
484 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
485 " referring to this unordered_set");
486 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
489 iterator emplace_hint(const_iterator, _Args&&... __args)
490 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
493 _LIBCPP_INLINE_VISIBILITY
494 pair<iterator, bool> insert(value_type&& __x)
495 {return __table_.__insert_unique(_VSTD::move(__x));}
496 _LIBCPP_INLINE_VISIBILITY
497 #if _LIBCPP_DEBUG_LEVEL >= 2
498 iterator insert(const_iterator __p, value_type&& __x)
500 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
501 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
502 " referring to this unordered_set");
503 return insert(_VSTD::move(__x)).first;
506 iterator insert(const_iterator, value_type&& __x)
507 {return insert(_VSTD::move(__x)).first;}
509 _LIBCPP_INLINE_VISIBILITY
510 void insert(initializer_list<value_type> __il)
511 {insert(__il.begin(), __il.end());}
512 #endif // _LIBCPP_CXX03_LANG
513 _LIBCPP_INLINE_VISIBILITY
514 pair<iterator, bool> insert(const value_type& __x)
515 {return __table_.__insert_unique(__x);}
517 _LIBCPP_INLINE_VISIBILITY
518 #if _LIBCPP_DEBUG_LEVEL >= 2
519 iterator insert(const_iterator __p, const value_type& __x)
521 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
522 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
523 " referring to this unordered_set");
524 return insert(__x).first;
527 iterator insert(const_iterator, const value_type& __x)
528 {return insert(__x).first;}
530 template <class _InputIterator>
531 _LIBCPP_INLINE_VISIBILITY
532 void insert(_InputIterator __first, _InputIterator __last);
534 _LIBCPP_INLINE_VISIBILITY
535 iterator erase(const_iterator __p) {return __table_.erase(__p);}
536 _LIBCPP_INLINE_VISIBILITY
537 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
538 _LIBCPP_INLINE_VISIBILITY
539 iterator erase(const_iterator __first, const_iterator __last)
540 {return __table_.erase(__first, __last);}
541 _LIBCPP_INLINE_VISIBILITY
542 void clear() _NOEXCEPT {__table_.clear();}
544 _LIBCPP_INLINE_VISIBILITY
545 void swap(unordered_set& __u)
546 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
547 {__table_.swap(__u.__table_);}
549 _LIBCPP_INLINE_VISIBILITY
550 hasher hash_function() const {return __table_.hash_function();}
551 _LIBCPP_INLINE_VISIBILITY
552 key_equal key_eq() const {return __table_.key_eq();}
554 _LIBCPP_INLINE_VISIBILITY
555 iterator find(const key_type& __k) {return __table_.find(__k);}
556 _LIBCPP_INLINE_VISIBILITY
557 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
558 _LIBCPP_INLINE_VISIBILITY
559 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
560 _LIBCPP_INLINE_VISIBILITY
561 pair<iterator, iterator> equal_range(const key_type& __k)
562 {return __table_.__equal_range_unique(__k);}
563 _LIBCPP_INLINE_VISIBILITY
564 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
565 {return __table_.__equal_range_unique(__k);}
567 _LIBCPP_INLINE_VISIBILITY
568 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
569 _LIBCPP_INLINE_VISIBILITY
570 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
572 _LIBCPP_INLINE_VISIBILITY
573 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
574 _LIBCPP_INLINE_VISIBILITY
575 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
577 _LIBCPP_INLINE_VISIBILITY
578 local_iterator begin(size_type __n) {return __table_.begin(__n);}
579 _LIBCPP_INLINE_VISIBILITY
580 local_iterator end(size_type __n) {return __table_.end(__n);}
581 _LIBCPP_INLINE_VISIBILITY
582 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
583 _LIBCPP_INLINE_VISIBILITY
584 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
585 _LIBCPP_INLINE_VISIBILITY
586 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
587 _LIBCPP_INLINE_VISIBILITY
588 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
590 _LIBCPP_INLINE_VISIBILITY
591 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
592 _LIBCPP_INLINE_VISIBILITY
593 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
594 _LIBCPP_INLINE_VISIBILITY
595 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
596 _LIBCPP_INLINE_VISIBILITY
597 void rehash(size_type __n) {__table_.rehash(__n);}
598 _LIBCPP_INLINE_VISIBILITY
599 void reserve(size_type __n) {__table_.reserve(__n);}
601 #if _LIBCPP_DEBUG_LEVEL >= 2
603 bool __dereferenceable(const const_iterator* __i) const
604 {return __table_.__dereferenceable(__i);}
605 bool __decrementable(const const_iterator* __i) const
606 {return __table_.__decrementable(__i);}
607 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
608 {return __table_.__addable(__i, __n);}
609 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
610 {return __table_.__addable(__i, __n);}
612 #endif // _LIBCPP_DEBUG_LEVEL >= 2
616 template <class _Value, class _Hash, class _Pred, class _Alloc>
617 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
618 const hasher& __hf, const key_equal& __eql)
619 : __table_(__hf, __eql)
621 #if _LIBCPP_DEBUG_LEVEL >= 2
622 __get_db()->__insert_c(this);
624 __table_.rehash(__n);
627 template <class _Value, class _Hash, class _Pred, class _Alloc>
628 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
629 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
630 : __table_(__hf, __eql, __a)
632 #if _LIBCPP_DEBUG_LEVEL >= 2
633 __get_db()->__insert_c(this);
635 __table_.rehash(__n);
638 template <class _Value, class _Hash, class _Pred, class _Alloc>
639 template <class _InputIterator>
640 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
641 _InputIterator __first, _InputIterator __last)
643 #if _LIBCPP_DEBUG_LEVEL >= 2
644 __get_db()->__insert_c(this);
646 insert(__first, __last);
649 template <class _Value, class _Hash, class _Pred, class _Alloc>
650 template <class _InputIterator>
651 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
652 _InputIterator __first, _InputIterator __last, size_type __n,
653 const hasher& __hf, const key_equal& __eql)
654 : __table_(__hf, __eql)
656 #if _LIBCPP_DEBUG_LEVEL >= 2
657 __get_db()->__insert_c(this);
659 __table_.rehash(__n);
660 insert(__first, __last);
663 template <class _Value, class _Hash, class _Pred, class _Alloc>
664 template <class _InputIterator>
665 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
666 _InputIterator __first, _InputIterator __last, size_type __n,
667 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
668 : __table_(__hf, __eql, __a)
670 #if _LIBCPP_DEBUG_LEVEL >= 2
671 __get_db()->__insert_c(this);
673 __table_.rehash(__n);
674 insert(__first, __last);
677 template <class _Value, class _Hash, class _Pred, class _Alloc>
679 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
680 const allocator_type& __a)
683 #if _LIBCPP_DEBUG_LEVEL >= 2
684 __get_db()->__insert_c(this);
688 template <class _Value, class _Hash, class _Pred, class _Alloc>
689 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
690 const unordered_set& __u)
691 : __table_(__u.__table_)
693 #if _LIBCPP_DEBUG_LEVEL >= 2
694 __get_db()->__insert_c(this);
696 __table_.rehash(__u.bucket_count());
697 insert(__u.begin(), __u.end());
700 template <class _Value, class _Hash, class _Pred, class _Alloc>
701 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
702 const unordered_set& __u, const allocator_type& __a)
703 : __table_(__u.__table_, __a)
705 #if _LIBCPP_DEBUG_LEVEL >= 2
706 __get_db()->__insert_c(this);
708 __table_.rehash(__u.bucket_count());
709 insert(__u.begin(), __u.end());
712 #ifndef _LIBCPP_CXX03_LANG
714 template <class _Value, class _Hash, class _Pred, class _Alloc>
716 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
718 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
719 : __table_(_VSTD::move(__u.__table_))
721 #if _LIBCPP_DEBUG_LEVEL >= 2
722 __get_db()->__insert_c(this);
723 __get_db()->swap(this, &__u);
727 template <class _Value, class _Hash, class _Pred, class _Alloc>
728 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
729 unordered_set&& __u, const allocator_type& __a)
730 : __table_(_VSTD::move(__u.__table_), __a)
732 #if _LIBCPP_DEBUG_LEVEL >= 2
733 __get_db()->__insert_c(this);
735 if (__a != __u.get_allocator())
737 iterator __i = __u.begin();
738 while (__u.size() != 0)
739 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
741 #if _LIBCPP_DEBUG_LEVEL >= 2
743 __get_db()->swap(this, &__u);
747 template <class _Value, class _Hash, class _Pred, class _Alloc>
748 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
749 initializer_list<value_type> __il)
751 #if _LIBCPP_DEBUG_LEVEL >= 2
752 __get_db()->__insert_c(this);
754 insert(__il.begin(), __il.end());
757 template <class _Value, class _Hash, class _Pred, class _Alloc>
758 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
759 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
760 const key_equal& __eql)
761 : __table_(__hf, __eql)
763 #if _LIBCPP_DEBUG_LEVEL >= 2
764 __get_db()->__insert_c(this);
766 __table_.rehash(__n);
767 insert(__il.begin(), __il.end());
770 template <class _Value, class _Hash, class _Pred, class _Alloc>
771 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
772 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
773 const key_equal& __eql, const allocator_type& __a)
774 : __table_(__hf, __eql, __a)
776 #if _LIBCPP_DEBUG_LEVEL >= 2
777 __get_db()->__insert_c(this);
779 __table_.rehash(__n);
780 insert(__il.begin(), __il.end());
783 template <class _Value, class _Hash, class _Pred, class _Alloc>
785 unordered_set<_Value, _Hash, _Pred, _Alloc>&
786 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
787 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
789 __table_ = _VSTD::move(__u.__table_);
793 template <class _Value, class _Hash, class _Pred, class _Alloc>
795 unordered_set<_Value, _Hash, _Pred, _Alloc>&
796 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
797 initializer_list<value_type> __il)
799 __table_.__assign_unique(__il.begin(), __il.end());
803 #endif // _LIBCPP_CXX03_LANG
805 template <class _Value, class _Hash, class _Pred, class _Alloc>
806 template <class _InputIterator>
809 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
810 _InputIterator __last)
812 for (; __first != __last; ++__first)
813 __table_.__insert_unique(*__first);
816 template <class _Value, class _Hash, class _Pred, class _Alloc>
817 inline _LIBCPP_INLINE_VISIBILITY
819 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
820 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
821 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
826 template <class _Value, class _Hash, class _Pred, class _Alloc>
828 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
829 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
831 if (__x.size() != __y.size())
833 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
835 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
838 const_iterator __j = __y.find(*__i);
839 if (__j == __ey || !(*__i == *__j))
845 template <class _Value, class _Hash, class _Pred, class _Alloc>
846 inline _LIBCPP_INLINE_VISIBILITY
848 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
849 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
851 return !(__x == __y);
854 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
855 class _Alloc = allocator<_Value> >
856 class _LIBCPP_TEMPLATE_VIS unordered_multiset
860 typedef _Value key_type;
861 typedef key_type value_type;
862 typedef _Hash hasher;
863 typedef _Pred key_equal;
864 typedef _Alloc allocator_type;
865 typedef value_type& reference;
866 typedef const value_type& const_reference;
867 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
868 "Invalid allocator::value_type");
871 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
876 typedef typename __table::pointer pointer;
877 typedef typename __table::const_pointer const_pointer;
878 typedef typename __table::size_type size_type;
879 typedef typename __table::difference_type difference_type;
881 typedef typename __table::const_iterator iterator;
882 typedef typename __table::const_iterator const_iterator;
883 typedef typename __table::const_local_iterator local_iterator;
884 typedef typename __table::const_local_iterator const_local_iterator;
886 _LIBCPP_INLINE_VISIBILITY
888 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
890 #if _LIBCPP_DEBUG_LEVEL >= 2
891 __get_db()->__insert_c(this);
894 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
895 const key_equal& __eql = key_equal());
896 unordered_multiset(size_type __n, const hasher& __hf,
897 const key_equal& __eql, const allocator_type& __a);
898 #if _LIBCPP_STD_VER > 11
899 inline _LIBCPP_INLINE_VISIBILITY
900 unordered_multiset(size_type __n, const allocator_type& __a)
901 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
902 inline _LIBCPP_INLINE_VISIBILITY
903 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
904 : unordered_multiset(__n, __hf, key_equal(), __a) {}
906 template <class _InputIterator>
907 unordered_multiset(_InputIterator __first, _InputIterator __last);
908 template <class _InputIterator>
909 unordered_multiset(_InputIterator __first, _InputIterator __last,
910 size_type __n, const hasher& __hf = hasher(),
911 const key_equal& __eql = key_equal());
912 template <class _InputIterator>
913 unordered_multiset(_InputIterator __first, _InputIterator __last,
914 size_type __n , const hasher& __hf,
915 const key_equal& __eql, const allocator_type& __a);
916 #if _LIBCPP_STD_VER > 11
917 template <class _InputIterator>
918 inline _LIBCPP_INLINE_VISIBILITY
919 unordered_multiset(_InputIterator __first, _InputIterator __last,
920 size_type __n, const allocator_type& __a)
921 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
922 template <class _InputIterator>
923 inline _LIBCPP_INLINE_VISIBILITY
924 unordered_multiset(_InputIterator __first, _InputIterator __last,
925 size_type __n, const hasher& __hf, const allocator_type& __a)
926 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
928 _LIBCPP_INLINE_VISIBILITY
929 explicit unordered_multiset(const allocator_type& __a);
930 unordered_multiset(const unordered_multiset& __u);
931 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
932 #ifndef _LIBCPP_CXX03_LANG
933 _LIBCPP_INLINE_VISIBILITY
934 unordered_multiset(unordered_multiset&& __u)
935 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
936 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
937 unordered_multiset(initializer_list<value_type> __il);
938 unordered_multiset(initializer_list<value_type> __il, size_type __n,
939 const hasher& __hf = hasher(),
940 const key_equal& __eql = key_equal());
941 unordered_multiset(initializer_list<value_type> __il, size_type __n,
942 const hasher& __hf, const key_equal& __eql,
943 const allocator_type& __a);
944 #if _LIBCPP_STD_VER > 11
945 inline _LIBCPP_INLINE_VISIBILITY
946 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
947 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
948 inline _LIBCPP_INLINE_VISIBILITY
949 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
950 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
952 #endif // _LIBCPP_CXX03_LANG
953 // ~unordered_multiset() = default;
954 _LIBCPP_INLINE_VISIBILITY
955 unordered_multiset& operator=(const unordered_multiset& __u)
957 __table_ = __u.__table_;
960 #ifndef _LIBCPP_CXX03_LANG
961 _LIBCPP_INLINE_VISIBILITY
962 unordered_multiset& operator=(unordered_multiset&& __u)
963 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
964 unordered_multiset& operator=(initializer_list<value_type> __il);
965 #endif // _LIBCPP_CXX03_LANG
967 _LIBCPP_INLINE_VISIBILITY
968 allocator_type get_allocator() const _NOEXCEPT
969 {return allocator_type(__table_.__node_alloc());}
971 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
972 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
973 _LIBCPP_INLINE_VISIBILITY
974 size_type size() const _NOEXCEPT {return __table_.size();}
975 _LIBCPP_INLINE_VISIBILITY
976 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
978 _LIBCPP_INLINE_VISIBILITY
979 iterator begin() _NOEXCEPT {return __table_.begin();}
980 _LIBCPP_INLINE_VISIBILITY
981 iterator end() _NOEXCEPT {return __table_.end();}
982 _LIBCPP_INLINE_VISIBILITY
983 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
984 _LIBCPP_INLINE_VISIBILITY
985 const_iterator end() const _NOEXCEPT {return __table_.end();}
986 _LIBCPP_INLINE_VISIBILITY
987 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
988 _LIBCPP_INLINE_VISIBILITY
989 const_iterator cend() const _NOEXCEPT {return __table_.end();}
991 #ifndef _LIBCPP_CXX03_LANG
992 template <class... _Args>
993 _LIBCPP_INLINE_VISIBILITY
994 iterator emplace(_Args&&... __args)
995 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
996 template <class... _Args>
997 _LIBCPP_INLINE_VISIBILITY
998 iterator emplace_hint(const_iterator __p, _Args&&... __args)
999 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1001 _LIBCPP_INLINE_VISIBILITY
1002 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1003 _LIBCPP_INLINE_VISIBILITY
1004 iterator insert(const_iterator __p, value_type&& __x)
1005 {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1006 _LIBCPP_INLINE_VISIBILITY
1007 void insert(initializer_list<value_type> __il)
1008 {insert(__il.begin(), __il.end());}
1009 #endif // _LIBCPP_CXX03_LANG
1011 _LIBCPP_INLINE_VISIBILITY
1012 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1014 _LIBCPP_INLINE_VISIBILITY
1015 iterator insert(const_iterator __p, const value_type& __x)
1016 {return __table_.__insert_multi(__p, __x);}
1018 template <class _InputIterator>
1019 _LIBCPP_INLINE_VISIBILITY
1020 void insert(_InputIterator __first, _InputIterator __last);
1022 _LIBCPP_INLINE_VISIBILITY
1023 iterator erase(const_iterator __p) {return __table_.erase(__p);}
1024 _LIBCPP_INLINE_VISIBILITY
1025 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1026 _LIBCPP_INLINE_VISIBILITY
1027 iterator erase(const_iterator __first, const_iterator __last)
1028 {return __table_.erase(__first, __last);}
1029 _LIBCPP_INLINE_VISIBILITY
1030 void clear() _NOEXCEPT {__table_.clear();}
1032 _LIBCPP_INLINE_VISIBILITY
1033 void swap(unordered_multiset& __u)
1034 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1035 {__table_.swap(__u.__table_);}
1037 _LIBCPP_INLINE_VISIBILITY
1038 hasher hash_function() const {return __table_.hash_function();}
1039 _LIBCPP_INLINE_VISIBILITY
1040 key_equal key_eq() const {return __table_.key_eq();}
1042 _LIBCPP_INLINE_VISIBILITY
1043 iterator find(const key_type& __k) {return __table_.find(__k);}
1044 _LIBCPP_INLINE_VISIBILITY
1045 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1046 _LIBCPP_INLINE_VISIBILITY
1047 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1048 _LIBCPP_INLINE_VISIBILITY
1049 pair<iterator, iterator> equal_range(const key_type& __k)
1050 {return __table_.__equal_range_multi(__k);}
1051 _LIBCPP_INLINE_VISIBILITY
1052 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1053 {return __table_.__equal_range_multi(__k);}
1055 _LIBCPP_INLINE_VISIBILITY
1056 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1057 _LIBCPP_INLINE_VISIBILITY
1058 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1060 _LIBCPP_INLINE_VISIBILITY
1061 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1062 _LIBCPP_INLINE_VISIBILITY
1063 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1065 _LIBCPP_INLINE_VISIBILITY
1066 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1067 _LIBCPP_INLINE_VISIBILITY
1068 local_iterator end(size_type __n) {return __table_.end(__n);}
1069 _LIBCPP_INLINE_VISIBILITY
1070 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1071 _LIBCPP_INLINE_VISIBILITY
1072 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1073 _LIBCPP_INLINE_VISIBILITY
1074 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1075 _LIBCPP_INLINE_VISIBILITY
1076 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1078 _LIBCPP_INLINE_VISIBILITY
1079 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1080 _LIBCPP_INLINE_VISIBILITY
1081 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1082 _LIBCPP_INLINE_VISIBILITY
1083 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1084 _LIBCPP_INLINE_VISIBILITY
1085 void rehash(size_type __n) {__table_.rehash(__n);}
1086 _LIBCPP_INLINE_VISIBILITY
1087 void reserve(size_type __n) {__table_.reserve(__n);}
1089 #if _LIBCPP_DEBUG_LEVEL >= 2
1091 bool __dereferenceable(const const_iterator* __i) const
1092 {return __table_.__dereferenceable(__i);}
1093 bool __decrementable(const const_iterator* __i) const
1094 {return __table_.__decrementable(__i);}
1095 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1096 {return __table_.__addable(__i, __n);}
1097 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1098 {return __table_.__addable(__i, __n);}
1100 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1104 template <class _Value, class _Hash, class _Pred, class _Alloc>
1105 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1106 size_type __n, const hasher& __hf, const key_equal& __eql)
1107 : __table_(__hf, __eql)
1109 #if _LIBCPP_DEBUG_LEVEL >= 2
1110 __get_db()->__insert_c(this);
1112 __table_.rehash(__n);
1115 template <class _Value, class _Hash, class _Pred, class _Alloc>
1116 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1117 size_type __n, const hasher& __hf, const key_equal& __eql,
1118 const allocator_type& __a)
1119 : __table_(__hf, __eql, __a)
1121 #if _LIBCPP_DEBUG_LEVEL >= 2
1122 __get_db()->__insert_c(this);
1124 __table_.rehash(__n);
1127 template <class _Value, class _Hash, class _Pred, class _Alloc>
1128 template <class _InputIterator>
1129 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1130 _InputIterator __first, _InputIterator __last)
1132 #if _LIBCPP_DEBUG_LEVEL >= 2
1133 __get_db()->__insert_c(this);
1135 insert(__first, __last);
1138 template <class _Value, class _Hash, class _Pred, class _Alloc>
1139 template <class _InputIterator>
1140 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1141 _InputIterator __first, _InputIterator __last, size_type __n,
1142 const hasher& __hf, const key_equal& __eql)
1143 : __table_(__hf, __eql)
1145 #if _LIBCPP_DEBUG_LEVEL >= 2
1146 __get_db()->__insert_c(this);
1148 __table_.rehash(__n);
1149 insert(__first, __last);
1152 template <class _Value, class _Hash, class _Pred, class _Alloc>
1153 template <class _InputIterator>
1154 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1155 _InputIterator __first, _InputIterator __last, size_type __n,
1156 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1157 : __table_(__hf, __eql, __a)
1159 #if _LIBCPP_DEBUG_LEVEL >= 2
1160 __get_db()->__insert_c(this);
1162 __table_.rehash(__n);
1163 insert(__first, __last);
1166 template <class _Value, class _Hash, class _Pred, class _Alloc>
1168 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1169 const allocator_type& __a)
1172 #if _LIBCPP_DEBUG_LEVEL >= 2
1173 __get_db()->__insert_c(this);
1177 template <class _Value, class _Hash, class _Pred, class _Alloc>
1178 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1179 const unordered_multiset& __u)
1180 : __table_(__u.__table_)
1182 #if _LIBCPP_DEBUG_LEVEL >= 2
1183 __get_db()->__insert_c(this);
1185 __table_.rehash(__u.bucket_count());
1186 insert(__u.begin(), __u.end());
1189 template <class _Value, class _Hash, class _Pred, class _Alloc>
1190 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1191 const unordered_multiset& __u, const allocator_type& __a)
1192 : __table_(__u.__table_, __a)
1194 #if _LIBCPP_DEBUG_LEVEL >= 2
1195 __get_db()->__insert_c(this);
1197 __table_.rehash(__u.bucket_count());
1198 insert(__u.begin(), __u.end());
1201 #ifndef _LIBCPP_CXX03_LANG
1203 template <class _Value, class _Hash, class _Pred, class _Alloc>
1205 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1206 unordered_multiset&& __u)
1207 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1208 : __table_(_VSTD::move(__u.__table_))
1210 #if _LIBCPP_DEBUG_LEVEL >= 2
1211 __get_db()->__insert_c(this);
1212 __get_db()->swap(this, &__u);
1216 template <class _Value, class _Hash, class _Pred, class _Alloc>
1217 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1218 unordered_multiset&& __u, const allocator_type& __a)
1219 : __table_(_VSTD::move(__u.__table_), __a)
1221 #if _LIBCPP_DEBUG_LEVEL >= 2
1222 __get_db()->__insert_c(this);
1224 if (__a != __u.get_allocator())
1226 iterator __i = __u.begin();
1227 while (__u.size() != 0)
1228 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1230 #if _LIBCPP_DEBUG_LEVEL >= 2
1232 __get_db()->swap(this, &__u);
1236 template <class _Value, class _Hash, class _Pred, class _Alloc>
1237 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1238 initializer_list<value_type> __il)
1240 #if _LIBCPP_DEBUG_LEVEL >= 2
1241 __get_db()->__insert_c(this);
1243 insert(__il.begin(), __il.end());
1246 template <class _Value, class _Hash, class _Pred, class _Alloc>
1247 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1248 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1249 const key_equal& __eql)
1250 : __table_(__hf, __eql)
1252 #if _LIBCPP_DEBUG_LEVEL >= 2
1253 __get_db()->__insert_c(this);
1255 __table_.rehash(__n);
1256 insert(__il.begin(), __il.end());
1259 template <class _Value, class _Hash, class _Pred, class _Alloc>
1260 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1261 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1262 const key_equal& __eql, const allocator_type& __a)
1263 : __table_(__hf, __eql, __a)
1265 #if _LIBCPP_DEBUG_LEVEL >= 2
1266 __get_db()->__insert_c(this);
1268 __table_.rehash(__n);
1269 insert(__il.begin(), __il.end());
1272 template <class _Value, class _Hash, class _Pred, class _Alloc>
1274 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1275 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1276 unordered_multiset&& __u)
1277 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1279 __table_ = _VSTD::move(__u.__table_);
1283 template <class _Value, class _Hash, class _Pred, class _Alloc>
1285 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1286 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1287 initializer_list<value_type> __il)
1289 __table_.__assign_multi(__il.begin(), __il.end());
1293 #endif // _LIBCPP_CXX03_LANG
1295 template <class _Value, class _Hash, class _Pred, class _Alloc>
1296 template <class _InputIterator>
1299 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1300 _InputIterator __last)
1302 for (; __first != __last; ++__first)
1303 __table_.__insert_multi(*__first);
1306 template <class _Value, class _Hash, class _Pred, class _Alloc>
1307 inline _LIBCPP_INLINE_VISIBILITY
1309 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1310 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1311 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1316 template <class _Value, class _Hash, class _Pred, class _Alloc>
1318 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1319 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1321 if (__x.size() != __y.size())
1323 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1325 typedef pair<const_iterator, const_iterator> _EqRng;
1326 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1328 _EqRng __xeq = __x.equal_range(*__i);
1329 _EqRng __yeq = __y.equal_range(*__i);
1330 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1331 _VSTD::distance(__yeq.first, __yeq.second) ||
1332 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1339 template <class _Value, class _Hash, class _Pred, class _Alloc>
1340 inline _LIBCPP_INLINE_VISIBILITY
1342 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1343 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1345 return !(__x == __y);
1348 _LIBCPP_END_NAMESPACE_STD
1350 #endif // _LIBCPP_UNORDERED_SET