2 //===-------------------------- unordered_set -----------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_UNORDERED_SET
12 #define _LIBCPP_UNORDERED_SET
16 unordered_set synopsis
18 #include <initializer_list>
23 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
24 class Alloc = allocator<Value>>
29 typedef Value key_type;
30 typedef key_type value_type;
32 typedef Pred key_equal;
33 typedef Alloc allocator_type;
34 typedef value_type& reference;
35 typedef const value_type& const_reference;
36 typedef typename allocator_traits<allocator_type>::pointer pointer;
37 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
38 typedef typename allocator_traits<allocator_type>::size_type size_type;
39 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
41 typedef /unspecified/ iterator;
42 typedef /unspecified/ const_iterator;
43 typedef /unspecified/ local_iterator;
44 typedef /unspecified/ const_local_iterator;
46 typedef unspecified node_type unspecified; // C++17
47 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
51 is_nothrow_default_constructible<hasher>::value &&
52 is_nothrow_default_constructible<key_equal>::value &&
53 is_nothrow_default_constructible<allocator_type>::value);
54 explicit unordered_set(size_type n, const hasher& hf = hasher(),
55 const key_equal& eql = key_equal(),
56 const allocator_type& a = allocator_type());
57 template <class InputIterator>
58 unordered_set(InputIterator f, InputIterator l,
59 size_type n = 0, const hasher& hf = hasher(),
60 const key_equal& eql = key_equal(),
61 const allocator_type& a = allocator_type());
62 explicit unordered_set(const allocator_type&);
63 unordered_set(const unordered_set&);
64 unordered_set(const unordered_set&, const Allocator&);
65 unordered_set(unordered_set&&)
67 is_nothrow_move_constructible<hasher>::value &&
68 is_nothrow_move_constructible<key_equal>::value &&
69 is_nothrow_move_constructible<allocator_type>::value);
70 unordered_set(unordered_set&&, const Allocator&);
71 unordered_set(initializer_list<value_type>, size_type n = 0,
72 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
73 const allocator_type& a = allocator_type());
74 unordered_set(size_type n, const allocator_type& a); // C++14
75 unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
76 template <class InputIterator>
77 unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
78 template <class InputIterator>
79 unordered_set(InputIterator f, InputIterator l, size_type n,
80 const hasher& hf, const allocator_type& a); // C++14
81 unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
82 unordered_set(initializer_list<value_type> il, size_type n,
83 const hasher& hf, const allocator_type& a); // C++14
85 unordered_set& operator=(const unordered_set&);
86 unordered_set& operator=(unordered_set&&)
88 allocator_type::propagate_on_container_move_assignment::value &&
89 is_nothrow_move_assignable<allocator_type>::value &&
90 is_nothrow_move_assignable<hasher>::value &&
91 is_nothrow_move_assignable<key_equal>::value);
92 unordered_set& operator=(initializer_list<value_type>);
94 allocator_type get_allocator() const noexcept;
96 bool empty() const noexcept;
97 size_type size() const noexcept;
98 size_type max_size() const noexcept;
100 iterator begin() noexcept;
101 iterator end() noexcept;
102 const_iterator begin() const noexcept;
103 const_iterator end() const noexcept;
104 const_iterator cbegin() const noexcept;
105 const_iterator cend() const noexcept;
107 template <class... Args>
108 pair<iterator, bool> emplace(Args&&... args);
109 template <class... Args>
110 iterator emplace_hint(const_iterator position, Args&&... args);
111 pair<iterator, bool> insert(const value_type& obj);
112 pair<iterator, bool> insert(value_type&& obj);
113 iterator insert(const_iterator hint, const value_type& obj);
114 iterator insert(const_iterator hint, value_type&& obj);
115 template <class InputIterator>
116 void insert(InputIterator first, InputIterator last);
117 void insert(initializer_list<value_type>);
119 node_type extract(const_iterator position); // C++17
120 node_type extract(const key_type& x); // C++17
121 insert_return_type insert(node_type&& nh); // C++17
122 iterator insert(const_iterator hint, node_type&& nh); // C++17
124 iterator erase(const_iterator position);
125 iterator erase(iterator position); // C++14
126 size_type erase(const key_type& k);
127 iterator erase(const_iterator first, const_iterator last);
128 void clear() noexcept;
130 void swap(unordered_set&)
131 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
132 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
133 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
135 hasher hash_function() const;
136 key_equal key_eq() const;
138 iterator find(const key_type& k);
139 const_iterator find(const key_type& k) const;
140 size_type count(const key_type& k) const;
141 pair<iterator, iterator> equal_range(const key_type& k);
142 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
144 size_type bucket_count() const noexcept;
145 size_type max_bucket_count() const noexcept;
147 size_type bucket_size(size_type n) const;
148 size_type bucket(const key_type& k) const;
150 local_iterator begin(size_type n);
151 local_iterator end(size_type n);
152 const_local_iterator begin(size_type n) const;
153 const_local_iterator end(size_type n) const;
154 const_local_iterator cbegin(size_type n) const;
155 const_local_iterator cend(size_type n) const;
157 float load_factor() const noexcept;
158 float max_load_factor() const noexcept;
159 void max_load_factor(float z);
160 void rehash(size_type n);
161 void reserve(size_type n);
164 template <class Value, class Hash, class Pred, class Alloc>
165 void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
166 unordered_set<Value, Hash, Pred, Alloc>& y)
167 noexcept(noexcept(x.swap(y)));
169 template <class Value, class Hash, class Pred, class Alloc>
171 operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
172 const unordered_set<Value, Hash, Pred, Alloc>& y);
174 template <class Value, class Hash, class Pred, class Alloc>
176 operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
177 const unordered_set<Value, Hash, Pred, Alloc>& y);
179 template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
180 class Alloc = allocator<Value>>
181 class unordered_multiset
185 typedef Value key_type;
186 typedef key_type value_type;
188 typedef Pred key_equal;
189 typedef Alloc allocator_type;
190 typedef value_type& reference;
191 typedef const value_type& const_reference;
192 typedef typename allocator_traits<allocator_type>::pointer pointer;
193 typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
194 typedef typename allocator_traits<allocator_type>::size_type size_type;
195 typedef typename allocator_traits<allocator_type>::difference_type difference_type;
197 typedef /unspecified/ iterator;
198 typedef /unspecified/ const_iterator;
199 typedef /unspecified/ local_iterator;
200 typedef /unspecified/ const_local_iterator;
202 typedef unspecified node_type unspecified; // C++17
206 is_nothrow_default_constructible<hasher>::value &&
207 is_nothrow_default_constructible<key_equal>::value &&
208 is_nothrow_default_constructible<allocator_type>::value);
209 explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
210 const key_equal& eql = key_equal(),
211 const allocator_type& a = allocator_type());
212 template <class InputIterator>
213 unordered_multiset(InputIterator f, InputIterator l,
214 size_type n = 0, const hasher& hf = hasher(),
215 const key_equal& eql = key_equal(),
216 const allocator_type& a = allocator_type());
217 explicit unordered_multiset(const allocator_type&);
218 unordered_multiset(const unordered_multiset&);
219 unordered_multiset(const unordered_multiset&, const Allocator&);
220 unordered_multiset(unordered_multiset&&)
222 is_nothrow_move_constructible<hasher>::value &&
223 is_nothrow_move_constructible<key_equal>::value &&
224 is_nothrow_move_constructible<allocator_type>::value);
225 unordered_multiset(unordered_multiset&&, const Allocator&);
226 unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
227 const hasher& hf = hasher(), const key_equal& eql = key_equal(),
228 const allocator_type& a = allocator_type());
229 unordered_multiset(size_type n, const allocator_type& a); // C++14
230 unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
231 template <class InputIterator>
232 unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
233 template <class InputIterator>
234 unordered_multiset(InputIterator f, InputIterator l, size_type n,
235 const hasher& hf, const allocator_type& a); // C++14
236 unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
237 unordered_multiset(initializer_list<value_type> il, size_type n,
238 const hasher& hf, const allocator_type& a); // C++14
239 ~unordered_multiset();
240 unordered_multiset& operator=(const unordered_multiset&);
241 unordered_multiset& operator=(unordered_multiset&&)
243 allocator_type::propagate_on_container_move_assignment::value &&
244 is_nothrow_move_assignable<allocator_type>::value &&
245 is_nothrow_move_assignable<hasher>::value &&
246 is_nothrow_move_assignable<key_equal>::value);
247 unordered_multiset& operator=(initializer_list<value_type>);
249 allocator_type get_allocator() const noexcept;
251 bool empty() const noexcept;
252 size_type size() const noexcept;
253 size_type max_size() const noexcept;
255 iterator begin() noexcept;
256 iterator end() noexcept;
257 const_iterator begin() const noexcept;
258 const_iterator end() const noexcept;
259 const_iterator cbegin() const noexcept;
260 const_iterator cend() const noexcept;
262 template <class... Args>
263 iterator emplace(Args&&... args);
264 template <class... Args>
265 iterator emplace_hint(const_iterator position, Args&&... args);
266 iterator insert(const value_type& obj);
267 iterator insert(value_type&& obj);
268 iterator insert(const_iterator hint, const value_type& obj);
269 iterator insert(const_iterator hint, value_type&& obj);
270 template <class InputIterator>
271 void insert(InputIterator first, InputIterator last);
272 void insert(initializer_list<value_type>);
274 node_type extract(const_iterator position); // C++17
275 node_type extract(const key_type& x); // C++17
276 iterator insert(node_type&& nh); // C++17
277 iterator insert(const_iterator hint, node_type&& nh); // C++17
279 iterator erase(const_iterator position);
280 iterator erase(iterator position); // C++14
281 size_type erase(const key_type& k);
282 iterator erase(const_iterator first, const_iterator last);
283 void clear() noexcept;
285 void swap(unordered_multiset&)
286 noexcept(allocator_traits<Allocator>::is_always_equal::value &&
287 noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
288 noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
290 hasher hash_function() const;
291 key_equal key_eq() const;
293 iterator find(const key_type& k);
294 const_iterator find(const key_type& k) const;
295 size_type count(const key_type& k) const;
296 pair<iterator, iterator> equal_range(const key_type& k);
297 pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
299 size_type bucket_count() const noexcept;
300 size_type max_bucket_count() const noexcept;
302 size_type bucket_size(size_type n) const;
303 size_type bucket(const key_type& k) const;
305 local_iterator begin(size_type n);
306 local_iterator end(size_type n);
307 const_local_iterator begin(size_type n) const;
308 const_local_iterator end(size_type n) const;
309 const_local_iterator cbegin(size_type n) const;
310 const_local_iterator cend(size_type n) const;
312 float load_factor() const noexcept;
313 float max_load_factor() const noexcept;
314 void max_load_factor(float z);
315 void rehash(size_type n);
316 void reserve(size_type n);
319 template <class Value, class Hash, class Pred, class Alloc>
320 void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
321 unordered_multiset<Value, Hash, Pred, Alloc>& y)
322 noexcept(noexcept(x.swap(y)));
324 template <class Value, class Hash, class Pred, class Alloc>
326 operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
327 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
329 template <class Value, class Hash, class Pred, class Alloc>
331 operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
332 const unordered_multiset<Value, Hash, Pred, Alloc>& y);
338 #include <__hash_table>
339 #include <__node_handle>
340 #include <functional>
344 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
345 #pragma GCC system_header
348 _LIBCPP_BEGIN_NAMESPACE_STD
350 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
351 class _Alloc = allocator<_Value> >
352 class _LIBCPP_TEMPLATE_VIS unordered_set
356 typedef _Value key_type;
357 typedef key_type value_type;
358 typedef _Hash hasher;
359 typedef _Pred key_equal;
360 typedef _Alloc allocator_type;
361 typedef value_type& reference;
362 typedef const value_type& const_reference;
363 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
364 "Invalid allocator::value_type");
367 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
372 typedef typename __table::pointer pointer;
373 typedef typename __table::const_pointer const_pointer;
374 typedef typename __table::size_type size_type;
375 typedef typename __table::difference_type difference_type;
377 typedef typename __table::const_iterator iterator;
378 typedef typename __table::const_iterator const_iterator;
379 typedef typename __table::const_local_iterator local_iterator;
380 typedef typename __table::const_local_iterator const_local_iterator;
382 #if _LIBCPP_STD_VER > 14
383 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
384 typedef __insert_return_type<iterator, node_type> insert_return_type;
387 _LIBCPP_INLINE_VISIBILITY
389 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
391 #if _LIBCPP_DEBUG_LEVEL >= 2
392 __get_db()->__insert_c(this);
395 explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
396 const key_equal& __eql = key_equal());
397 #if _LIBCPP_STD_VER > 11
398 inline _LIBCPP_INLINE_VISIBILITY
399 unordered_set(size_type __n, const allocator_type& __a)
400 : unordered_set(__n, hasher(), key_equal(), __a) {}
401 inline _LIBCPP_INLINE_VISIBILITY
402 unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
403 : unordered_set(__n, __hf, key_equal(), __a) {}
405 unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
406 const allocator_type& __a);
407 template <class _InputIterator>
408 unordered_set(_InputIterator __first, _InputIterator __last);
409 template <class _InputIterator>
410 unordered_set(_InputIterator __first, _InputIterator __last,
411 size_type __n, const hasher& __hf = hasher(),
412 const key_equal& __eql = key_equal());
413 template <class _InputIterator>
414 unordered_set(_InputIterator __first, _InputIterator __last,
415 size_type __n, const hasher& __hf, const key_equal& __eql,
416 const allocator_type& __a);
417 #if _LIBCPP_STD_VER > 11
418 template <class _InputIterator>
419 inline _LIBCPP_INLINE_VISIBILITY
420 unordered_set(_InputIterator __first, _InputIterator __last,
421 size_type __n, const allocator_type& __a)
422 : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
423 template <class _InputIterator>
424 unordered_set(_InputIterator __first, _InputIterator __last,
425 size_type __n, const hasher& __hf, const allocator_type& __a)
426 : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
428 _LIBCPP_INLINE_VISIBILITY
429 explicit unordered_set(const allocator_type& __a);
430 unordered_set(const unordered_set& __u);
431 unordered_set(const unordered_set& __u, const allocator_type& __a);
432 #ifndef _LIBCPP_CXX03_LANG
433 _LIBCPP_INLINE_VISIBILITY
434 unordered_set(unordered_set&& __u)
435 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
436 unordered_set(unordered_set&& __u, const allocator_type& __a);
437 unordered_set(initializer_list<value_type> __il);
438 unordered_set(initializer_list<value_type> __il, size_type __n,
439 const hasher& __hf = hasher(),
440 const key_equal& __eql = key_equal());
441 unordered_set(initializer_list<value_type> __il, size_type __n,
442 const hasher& __hf, const key_equal& __eql,
443 const allocator_type& __a);
444 #if _LIBCPP_STD_VER > 11
445 inline _LIBCPP_INLINE_VISIBILITY
446 unordered_set(initializer_list<value_type> __il, size_type __n,
447 const allocator_type& __a)
448 : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
449 inline _LIBCPP_INLINE_VISIBILITY
450 unordered_set(initializer_list<value_type> __il, size_type __n,
451 const hasher& __hf, const allocator_type& __a)
452 : unordered_set(__il, __n, __hf, key_equal(), __a) {}
454 #endif // _LIBCPP_CXX03_LANG
455 // ~unordered_set() = default;
456 _LIBCPP_INLINE_VISIBILITY
457 unordered_set& operator=(const unordered_set& __u)
459 __table_ = __u.__table_;
462 #ifndef _LIBCPP_CXX03_LANG
463 _LIBCPP_INLINE_VISIBILITY
464 unordered_set& operator=(unordered_set&& __u)
465 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
466 _LIBCPP_INLINE_VISIBILITY
467 unordered_set& operator=(initializer_list<value_type> __il);
468 #endif // _LIBCPP_CXX03_LANG
470 _LIBCPP_INLINE_VISIBILITY
471 allocator_type get_allocator() const _NOEXCEPT
472 {return allocator_type(__table_.__node_alloc());}
474 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
475 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
476 _LIBCPP_INLINE_VISIBILITY
477 size_type size() const _NOEXCEPT {return __table_.size();}
478 _LIBCPP_INLINE_VISIBILITY
479 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
481 _LIBCPP_INLINE_VISIBILITY
482 iterator begin() _NOEXCEPT {return __table_.begin();}
483 _LIBCPP_INLINE_VISIBILITY
484 iterator end() _NOEXCEPT {return __table_.end();}
485 _LIBCPP_INLINE_VISIBILITY
486 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
487 _LIBCPP_INLINE_VISIBILITY
488 const_iterator end() const _NOEXCEPT {return __table_.end();}
489 _LIBCPP_INLINE_VISIBILITY
490 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
491 _LIBCPP_INLINE_VISIBILITY
492 const_iterator cend() const _NOEXCEPT {return __table_.end();}
494 #ifndef _LIBCPP_CXX03_LANG
495 template <class... _Args>
496 _LIBCPP_INLINE_VISIBILITY
497 pair<iterator, bool> emplace(_Args&&... __args)
498 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
499 template <class... _Args>
500 _LIBCPP_INLINE_VISIBILITY
501 #if _LIBCPP_DEBUG_LEVEL >= 2
502 iterator emplace_hint(const_iterator __p, _Args&&... __args)
504 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
505 "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
506 " referring to this unordered_set");
507 return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
510 iterator emplace_hint(const_iterator, _Args&&... __args)
511 {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
514 _LIBCPP_INLINE_VISIBILITY
515 pair<iterator, bool> insert(value_type&& __x)
516 {return __table_.__insert_unique(_VSTD::move(__x));}
517 _LIBCPP_INLINE_VISIBILITY
518 #if _LIBCPP_DEBUG_LEVEL >= 2
519 iterator insert(const_iterator __p, value_type&& __x)
521 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
522 "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
523 " referring to this unordered_set");
524 return insert(_VSTD::move(__x)).first;
527 iterator insert(const_iterator, value_type&& __x)
528 {return insert(_VSTD::move(__x)).first;}
530 _LIBCPP_INLINE_VISIBILITY
531 void insert(initializer_list<value_type> __il)
532 {insert(__il.begin(), __il.end());}
533 #endif // _LIBCPP_CXX03_LANG
534 _LIBCPP_INLINE_VISIBILITY
535 pair<iterator, bool> insert(const value_type& __x)
536 {return __table_.__insert_unique(__x);}
538 _LIBCPP_INLINE_VISIBILITY
539 #if _LIBCPP_DEBUG_LEVEL >= 2
540 iterator insert(const_iterator __p, const value_type& __x)
542 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
543 "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
544 " referring to this unordered_set");
545 return insert(__x).first;
548 iterator insert(const_iterator, const value_type& __x)
549 {return insert(__x).first;}
551 template <class _InputIterator>
552 _LIBCPP_INLINE_VISIBILITY
553 void insert(_InputIterator __first, _InputIterator __last);
555 _LIBCPP_INLINE_VISIBILITY
556 iterator erase(const_iterator __p) {return __table_.erase(__p);}
557 _LIBCPP_INLINE_VISIBILITY
558 size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
559 _LIBCPP_INLINE_VISIBILITY
560 iterator erase(const_iterator __first, const_iterator __last)
561 {return __table_.erase(__first, __last);}
562 _LIBCPP_INLINE_VISIBILITY
563 void clear() _NOEXCEPT {__table_.clear();}
565 #if _LIBCPP_STD_VER > 14
566 _LIBCPP_INLINE_VISIBILITY
567 insert_return_type insert(node_type&& __nh)
569 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
570 "node_type with incompatible allocator passed to unordered_set::insert()");
571 return __table_.template __node_handle_insert_unique<
572 node_type, insert_return_type>(_VSTD::move(__nh));
574 _LIBCPP_INLINE_VISIBILITY
575 iterator insert(const_iterator __h, node_type&& __nh)
577 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
578 "node_type with incompatible allocator passed to unordered_set::insert()");
579 return __table_.template __node_handle_insert_unique<node_type>(
580 __h, _VSTD::move(__nh));
582 _LIBCPP_INLINE_VISIBILITY
583 node_type extract(key_type const& __key)
585 return __table_.template __node_handle_extract<node_type>(__key);
587 _LIBCPP_INLINE_VISIBILITY
588 node_type extract(const_iterator __it)
590 return __table_.template __node_handle_extract<node_type>(__it);
594 _LIBCPP_INLINE_VISIBILITY
595 void swap(unordered_set& __u)
596 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
597 {__table_.swap(__u.__table_);}
599 _LIBCPP_INLINE_VISIBILITY
600 hasher hash_function() const {return __table_.hash_function();}
601 _LIBCPP_INLINE_VISIBILITY
602 key_equal key_eq() const {return __table_.key_eq();}
604 _LIBCPP_INLINE_VISIBILITY
605 iterator find(const key_type& __k) {return __table_.find(__k);}
606 _LIBCPP_INLINE_VISIBILITY
607 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
608 _LIBCPP_INLINE_VISIBILITY
609 size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
610 _LIBCPP_INLINE_VISIBILITY
611 pair<iterator, iterator> equal_range(const key_type& __k)
612 {return __table_.__equal_range_unique(__k);}
613 _LIBCPP_INLINE_VISIBILITY
614 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
615 {return __table_.__equal_range_unique(__k);}
617 _LIBCPP_INLINE_VISIBILITY
618 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
619 _LIBCPP_INLINE_VISIBILITY
620 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
622 _LIBCPP_INLINE_VISIBILITY
623 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
624 _LIBCPP_INLINE_VISIBILITY
625 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
627 _LIBCPP_INLINE_VISIBILITY
628 local_iterator begin(size_type __n) {return __table_.begin(__n);}
629 _LIBCPP_INLINE_VISIBILITY
630 local_iterator end(size_type __n) {return __table_.end(__n);}
631 _LIBCPP_INLINE_VISIBILITY
632 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
633 _LIBCPP_INLINE_VISIBILITY
634 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
635 _LIBCPP_INLINE_VISIBILITY
636 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
637 _LIBCPP_INLINE_VISIBILITY
638 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
640 _LIBCPP_INLINE_VISIBILITY
641 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
642 _LIBCPP_INLINE_VISIBILITY
643 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
644 _LIBCPP_INLINE_VISIBILITY
645 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
646 _LIBCPP_INLINE_VISIBILITY
647 void rehash(size_type __n) {__table_.rehash(__n);}
648 _LIBCPP_INLINE_VISIBILITY
649 void reserve(size_type __n) {__table_.reserve(__n);}
651 #if _LIBCPP_DEBUG_LEVEL >= 2
653 bool __dereferenceable(const const_iterator* __i) const
654 {return __table_.__dereferenceable(__i);}
655 bool __decrementable(const const_iterator* __i) const
656 {return __table_.__decrementable(__i);}
657 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
658 {return __table_.__addable(__i, __n);}
659 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
660 {return __table_.__addable(__i, __n);}
662 #endif // _LIBCPP_DEBUG_LEVEL >= 2
666 template <class _Value, class _Hash, class _Pred, class _Alloc>
667 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
668 const hasher& __hf, const key_equal& __eql)
669 : __table_(__hf, __eql)
671 #if _LIBCPP_DEBUG_LEVEL >= 2
672 __get_db()->__insert_c(this);
674 __table_.rehash(__n);
677 template <class _Value, class _Hash, class _Pred, class _Alloc>
678 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
679 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
680 : __table_(__hf, __eql, __a)
682 #if _LIBCPP_DEBUG_LEVEL >= 2
683 __get_db()->__insert_c(this);
685 __table_.rehash(__n);
688 template <class _Value, class _Hash, class _Pred, class _Alloc>
689 template <class _InputIterator>
690 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
691 _InputIterator __first, _InputIterator __last)
693 #if _LIBCPP_DEBUG_LEVEL >= 2
694 __get_db()->__insert_c(this);
696 insert(__first, __last);
699 template <class _Value, class _Hash, class _Pred, class _Alloc>
700 template <class _InputIterator>
701 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
702 _InputIterator __first, _InputIterator __last, size_type __n,
703 const hasher& __hf, const key_equal& __eql)
704 : __table_(__hf, __eql)
706 #if _LIBCPP_DEBUG_LEVEL >= 2
707 __get_db()->__insert_c(this);
709 __table_.rehash(__n);
710 insert(__first, __last);
713 template <class _Value, class _Hash, class _Pred, class _Alloc>
714 template <class _InputIterator>
715 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
716 _InputIterator __first, _InputIterator __last, size_type __n,
717 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
718 : __table_(__hf, __eql, __a)
720 #if _LIBCPP_DEBUG_LEVEL >= 2
721 __get_db()->__insert_c(this);
723 __table_.rehash(__n);
724 insert(__first, __last);
727 template <class _Value, class _Hash, class _Pred, class _Alloc>
729 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
730 const allocator_type& __a)
733 #if _LIBCPP_DEBUG_LEVEL >= 2
734 __get_db()->__insert_c(this);
738 template <class _Value, class _Hash, class _Pred, class _Alloc>
739 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
740 const unordered_set& __u)
741 : __table_(__u.__table_)
743 #if _LIBCPP_DEBUG_LEVEL >= 2
744 __get_db()->__insert_c(this);
746 __table_.rehash(__u.bucket_count());
747 insert(__u.begin(), __u.end());
750 template <class _Value, class _Hash, class _Pred, class _Alloc>
751 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
752 const unordered_set& __u, const allocator_type& __a)
753 : __table_(__u.__table_, __a)
755 #if _LIBCPP_DEBUG_LEVEL >= 2
756 __get_db()->__insert_c(this);
758 __table_.rehash(__u.bucket_count());
759 insert(__u.begin(), __u.end());
762 #ifndef _LIBCPP_CXX03_LANG
764 template <class _Value, class _Hash, class _Pred, class _Alloc>
766 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
768 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
769 : __table_(_VSTD::move(__u.__table_))
771 #if _LIBCPP_DEBUG_LEVEL >= 2
772 __get_db()->__insert_c(this);
773 __get_db()->swap(this, &__u);
777 template <class _Value, class _Hash, class _Pred, class _Alloc>
778 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
779 unordered_set&& __u, const allocator_type& __a)
780 : __table_(_VSTD::move(__u.__table_), __a)
782 #if _LIBCPP_DEBUG_LEVEL >= 2
783 __get_db()->__insert_c(this);
785 if (__a != __u.get_allocator())
787 iterator __i = __u.begin();
788 while (__u.size() != 0)
789 __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
791 #if _LIBCPP_DEBUG_LEVEL >= 2
793 __get_db()->swap(this, &__u);
797 template <class _Value, class _Hash, class _Pred, class _Alloc>
798 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
799 initializer_list<value_type> __il)
801 #if _LIBCPP_DEBUG_LEVEL >= 2
802 __get_db()->__insert_c(this);
804 insert(__il.begin(), __il.end());
807 template <class _Value, class _Hash, class _Pred, class _Alloc>
808 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
809 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
810 const key_equal& __eql)
811 : __table_(__hf, __eql)
813 #if _LIBCPP_DEBUG_LEVEL >= 2
814 __get_db()->__insert_c(this);
816 __table_.rehash(__n);
817 insert(__il.begin(), __il.end());
820 template <class _Value, class _Hash, class _Pred, class _Alloc>
821 unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
822 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
823 const key_equal& __eql, const allocator_type& __a)
824 : __table_(__hf, __eql, __a)
826 #if _LIBCPP_DEBUG_LEVEL >= 2
827 __get_db()->__insert_c(this);
829 __table_.rehash(__n);
830 insert(__il.begin(), __il.end());
833 template <class _Value, class _Hash, class _Pred, class _Alloc>
835 unordered_set<_Value, _Hash, _Pred, _Alloc>&
836 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
837 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
839 __table_ = _VSTD::move(__u.__table_);
843 template <class _Value, class _Hash, class _Pred, class _Alloc>
845 unordered_set<_Value, _Hash, _Pred, _Alloc>&
846 unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
847 initializer_list<value_type> __il)
849 __table_.__assign_unique(__il.begin(), __il.end());
853 #endif // _LIBCPP_CXX03_LANG
855 template <class _Value, class _Hash, class _Pred, class _Alloc>
856 template <class _InputIterator>
859 unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
860 _InputIterator __last)
862 for (; __first != __last; ++__first)
863 __table_.__insert_unique(*__first);
866 template <class _Value, class _Hash, class _Pred, class _Alloc>
867 inline _LIBCPP_INLINE_VISIBILITY
869 swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
870 unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
871 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
876 template <class _Value, class _Hash, class _Pred, class _Alloc>
878 operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
879 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
881 if (__x.size() != __y.size())
883 typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
885 for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
888 const_iterator __j = __y.find(*__i);
889 if (__j == __ey || !(*__i == *__j))
895 template <class _Value, class _Hash, class _Pred, class _Alloc>
896 inline _LIBCPP_INLINE_VISIBILITY
898 operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
899 const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
901 return !(__x == __y);
904 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
905 class _Alloc = allocator<_Value> >
906 class _LIBCPP_TEMPLATE_VIS unordered_multiset
910 typedef _Value key_type;
911 typedef key_type value_type;
912 typedef _Hash hasher;
913 typedef _Pred key_equal;
914 typedef _Alloc allocator_type;
915 typedef value_type& reference;
916 typedef const value_type& const_reference;
917 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
918 "Invalid allocator::value_type");
921 typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
926 typedef typename __table::pointer pointer;
927 typedef typename __table::const_pointer const_pointer;
928 typedef typename __table::size_type size_type;
929 typedef typename __table::difference_type difference_type;
931 typedef typename __table::const_iterator iterator;
932 typedef typename __table::const_iterator const_iterator;
933 typedef typename __table::const_local_iterator local_iterator;
934 typedef typename __table::const_local_iterator const_local_iterator;
936 #if _LIBCPP_STD_VER > 14
937 typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
940 _LIBCPP_INLINE_VISIBILITY
942 _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
944 #if _LIBCPP_DEBUG_LEVEL >= 2
945 __get_db()->__insert_c(this);
948 explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
949 const key_equal& __eql = key_equal());
950 unordered_multiset(size_type __n, const hasher& __hf,
951 const key_equal& __eql, const allocator_type& __a);
952 #if _LIBCPP_STD_VER > 11
953 inline _LIBCPP_INLINE_VISIBILITY
954 unordered_multiset(size_type __n, const allocator_type& __a)
955 : unordered_multiset(__n, hasher(), key_equal(), __a) {}
956 inline _LIBCPP_INLINE_VISIBILITY
957 unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
958 : unordered_multiset(__n, __hf, key_equal(), __a) {}
960 template <class _InputIterator>
961 unordered_multiset(_InputIterator __first, _InputIterator __last);
962 template <class _InputIterator>
963 unordered_multiset(_InputIterator __first, _InputIterator __last,
964 size_type __n, const hasher& __hf = hasher(),
965 const key_equal& __eql = key_equal());
966 template <class _InputIterator>
967 unordered_multiset(_InputIterator __first, _InputIterator __last,
968 size_type __n , const hasher& __hf,
969 const key_equal& __eql, const allocator_type& __a);
970 #if _LIBCPP_STD_VER > 11
971 template <class _InputIterator>
972 inline _LIBCPP_INLINE_VISIBILITY
973 unordered_multiset(_InputIterator __first, _InputIterator __last,
974 size_type __n, const allocator_type& __a)
975 : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
976 template <class _InputIterator>
977 inline _LIBCPP_INLINE_VISIBILITY
978 unordered_multiset(_InputIterator __first, _InputIterator __last,
979 size_type __n, const hasher& __hf, const allocator_type& __a)
980 : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
982 _LIBCPP_INLINE_VISIBILITY
983 explicit unordered_multiset(const allocator_type& __a);
984 unordered_multiset(const unordered_multiset& __u);
985 unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
986 #ifndef _LIBCPP_CXX03_LANG
987 _LIBCPP_INLINE_VISIBILITY
988 unordered_multiset(unordered_multiset&& __u)
989 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
990 unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
991 unordered_multiset(initializer_list<value_type> __il);
992 unordered_multiset(initializer_list<value_type> __il, size_type __n,
993 const hasher& __hf = hasher(),
994 const key_equal& __eql = key_equal());
995 unordered_multiset(initializer_list<value_type> __il, size_type __n,
996 const hasher& __hf, const key_equal& __eql,
997 const allocator_type& __a);
998 #if _LIBCPP_STD_VER > 11
999 inline _LIBCPP_INLINE_VISIBILITY
1000 unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
1001 : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
1002 inline _LIBCPP_INLINE_VISIBILITY
1003 unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
1004 : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
1006 #endif // _LIBCPP_CXX03_LANG
1007 // ~unordered_multiset() = default;
1008 _LIBCPP_INLINE_VISIBILITY
1009 unordered_multiset& operator=(const unordered_multiset& __u)
1011 __table_ = __u.__table_;
1014 #ifndef _LIBCPP_CXX03_LANG
1015 _LIBCPP_INLINE_VISIBILITY
1016 unordered_multiset& operator=(unordered_multiset&& __u)
1017 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
1018 unordered_multiset& operator=(initializer_list<value_type> __il);
1019 #endif // _LIBCPP_CXX03_LANG
1021 _LIBCPP_INLINE_VISIBILITY
1022 allocator_type get_allocator() const _NOEXCEPT
1023 {return allocator_type(__table_.__node_alloc());}
1025 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
1026 bool empty() const _NOEXCEPT {return __table_.size() == 0;}
1027 _LIBCPP_INLINE_VISIBILITY
1028 size_type size() const _NOEXCEPT {return __table_.size();}
1029 _LIBCPP_INLINE_VISIBILITY
1030 size_type max_size() const _NOEXCEPT {return __table_.max_size();}
1032 _LIBCPP_INLINE_VISIBILITY
1033 iterator begin() _NOEXCEPT {return __table_.begin();}
1034 _LIBCPP_INLINE_VISIBILITY
1035 iterator end() _NOEXCEPT {return __table_.end();}
1036 _LIBCPP_INLINE_VISIBILITY
1037 const_iterator begin() const _NOEXCEPT {return __table_.begin();}
1038 _LIBCPP_INLINE_VISIBILITY
1039 const_iterator end() const _NOEXCEPT {return __table_.end();}
1040 _LIBCPP_INLINE_VISIBILITY
1041 const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
1042 _LIBCPP_INLINE_VISIBILITY
1043 const_iterator cend() const _NOEXCEPT {return __table_.end();}
1045 #ifndef _LIBCPP_CXX03_LANG
1046 template <class... _Args>
1047 _LIBCPP_INLINE_VISIBILITY
1048 iterator emplace(_Args&&... __args)
1049 {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1050 template <class... _Args>
1051 _LIBCPP_INLINE_VISIBILITY
1052 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1053 {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1055 _LIBCPP_INLINE_VISIBILITY
1056 iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
1057 _LIBCPP_INLINE_VISIBILITY
1058 iterator insert(const_iterator __p, value_type&& __x)
1059 {return __table_.__insert_multi(__p, _VSTD::move(__x));}
1060 _LIBCPP_INLINE_VISIBILITY
1061 void insert(initializer_list<value_type> __il)
1062 {insert(__il.begin(), __il.end());}
1063 #endif // _LIBCPP_CXX03_LANG
1065 _LIBCPP_INLINE_VISIBILITY
1066 iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
1068 _LIBCPP_INLINE_VISIBILITY
1069 iterator insert(const_iterator __p, const value_type& __x)
1070 {return __table_.__insert_multi(__p, __x);}
1072 template <class _InputIterator>
1073 _LIBCPP_INLINE_VISIBILITY
1074 void insert(_InputIterator __first, _InputIterator __last);
1076 #if _LIBCPP_STD_VER > 14
1077 _LIBCPP_INLINE_VISIBILITY
1078 iterator insert(node_type&& __nh)
1080 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1081 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1082 return __table_.template __node_handle_insert_multi<node_type>(
1085 _LIBCPP_INLINE_VISIBILITY
1086 iterator insert(const_iterator __hint, node_type&& __nh)
1088 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
1089 "node_type with incompatible allocator passed to unordered_multiset::insert()");
1090 return __table_.template __node_handle_insert_multi<node_type>(
1091 __hint, _VSTD::move(__nh));
1093 _LIBCPP_INLINE_VISIBILITY
1094 node_type extract(const_iterator __position)
1096 return __table_.template __node_handle_extract<node_type>(
1099 _LIBCPP_INLINE_VISIBILITY
1100 node_type extract(key_type const& __key)
1102 return __table_.template __node_handle_extract<node_type>(__key);
1106 _LIBCPP_INLINE_VISIBILITY
1107 iterator erase(const_iterator __p) {return __table_.erase(__p);}
1108 _LIBCPP_INLINE_VISIBILITY
1109 size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
1110 _LIBCPP_INLINE_VISIBILITY
1111 iterator erase(const_iterator __first, const_iterator __last)
1112 {return __table_.erase(__first, __last);}
1113 _LIBCPP_INLINE_VISIBILITY
1114 void clear() _NOEXCEPT {__table_.clear();}
1116 _LIBCPP_INLINE_VISIBILITY
1117 void swap(unordered_multiset& __u)
1118 _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
1119 {__table_.swap(__u.__table_);}
1121 _LIBCPP_INLINE_VISIBILITY
1122 hasher hash_function() const {return __table_.hash_function();}
1123 _LIBCPP_INLINE_VISIBILITY
1124 key_equal key_eq() const {return __table_.key_eq();}
1126 _LIBCPP_INLINE_VISIBILITY
1127 iterator find(const key_type& __k) {return __table_.find(__k);}
1128 _LIBCPP_INLINE_VISIBILITY
1129 const_iterator find(const key_type& __k) const {return __table_.find(__k);}
1130 _LIBCPP_INLINE_VISIBILITY
1131 size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
1132 _LIBCPP_INLINE_VISIBILITY
1133 pair<iterator, iterator> equal_range(const key_type& __k)
1134 {return __table_.__equal_range_multi(__k);}
1135 _LIBCPP_INLINE_VISIBILITY
1136 pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
1137 {return __table_.__equal_range_multi(__k);}
1139 _LIBCPP_INLINE_VISIBILITY
1140 size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
1141 _LIBCPP_INLINE_VISIBILITY
1142 size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
1144 _LIBCPP_INLINE_VISIBILITY
1145 size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
1146 _LIBCPP_INLINE_VISIBILITY
1147 size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
1149 _LIBCPP_INLINE_VISIBILITY
1150 local_iterator begin(size_type __n) {return __table_.begin(__n);}
1151 _LIBCPP_INLINE_VISIBILITY
1152 local_iterator end(size_type __n) {return __table_.end(__n);}
1153 _LIBCPP_INLINE_VISIBILITY
1154 const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
1155 _LIBCPP_INLINE_VISIBILITY
1156 const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
1157 _LIBCPP_INLINE_VISIBILITY
1158 const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
1159 _LIBCPP_INLINE_VISIBILITY
1160 const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
1162 _LIBCPP_INLINE_VISIBILITY
1163 float load_factor() const _NOEXCEPT {return __table_.load_factor();}
1164 _LIBCPP_INLINE_VISIBILITY
1165 float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
1166 _LIBCPP_INLINE_VISIBILITY
1167 void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
1168 _LIBCPP_INLINE_VISIBILITY
1169 void rehash(size_type __n) {__table_.rehash(__n);}
1170 _LIBCPP_INLINE_VISIBILITY
1171 void reserve(size_type __n) {__table_.reserve(__n);}
1173 #if _LIBCPP_DEBUG_LEVEL >= 2
1175 bool __dereferenceable(const const_iterator* __i) const
1176 {return __table_.__dereferenceable(__i);}
1177 bool __decrementable(const const_iterator* __i) const
1178 {return __table_.__decrementable(__i);}
1179 bool __addable(const const_iterator* __i, ptrdiff_t __n) const
1180 {return __table_.__addable(__i, __n);}
1181 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1182 {return __table_.__addable(__i, __n);}
1184 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1188 template <class _Value, class _Hash, class _Pred, class _Alloc>
1189 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1190 size_type __n, const hasher& __hf, const key_equal& __eql)
1191 : __table_(__hf, __eql)
1193 #if _LIBCPP_DEBUG_LEVEL >= 2
1194 __get_db()->__insert_c(this);
1196 __table_.rehash(__n);
1199 template <class _Value, class _Hash, class _Pred, class _Alloc>
1200 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1201 size_type __n, const hasher& __hf, const key_equal& __eql,
1202 const allocator_type& __a)
1203 : __table_(__hf, __eql, __a)
1205 #if _LIBCPP_DEBUG_LEVEL >= 2
1206 __get_db()->__insert_c(this);
1208 __table_.rehash(__n);
1211 template <class _Value, class _Hash, class _Pred, class _Alloc>
1212 template <class _InputIterator>
1213 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1214 _InputIterator __first, _InputIterator __last)
1216 #if _LIBCPP_DEBUG_LEVEL >= 2
1217 __get_db()->__insert_c(this);
1219 insert(__first, __last);
1222 template <class _Value, class _Hash, class _Pred, class _Alloc>
1223 template <class _InputIterator>
1224 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1225 _InputIterator __first, _InputIterator __last, size_type __n,
1226 const hasher& __hf, const key_equal& __eql)
1227 : __table_(__hf, __eql)
1229 #if _LIBCPP_DEBUG_LEVEL >= 2
1230 __get_db()->__insert_c(this);
1232 __table_.rehash(__n);
1233 insert(__first, __last);
1236 template <class _Value, class _Hash, class _Pred, class _Alloc>
1237 template <class _InputIterator>
1238 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1239 _InputIterator __first, _InputIterator __last, size_type __n,
1240 const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
1241 : __table_(__hf, __eql, __a)
1243 #if _LIBCPP_DEBUG_LEVEL >= 2
1244 __get_db()->__insert_c(this);
1246 __table_.rehash(__n);
1247 insert(__first, __last);
1250 template <class _Value, class _Hash, class _Pred, class _Alloc>
1252 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1253 const allocator_type& __a)
1256 #if _LIBCPP_DEBUG_LEVEL >= 2
1257 __get_db()->__insert_c(this);
1261 template <class _Value, class _Hash, class _Pred, class _Alloc>
1262 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1263 const unordered_multiset& __u)
1264 : __table_(__u.__table_)
1266 #if _LIBCPP_DEBUG_LEVEL >= 2
1267 __get_db()->__insert_c(this);
1269 __table_.rehash(__u.bucket_count());
1270 insert(__u.begin(), __u.end());
1273 template <class _Value, class _Hash, class _Pred, class _Alloc>
1274 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1275 const unordered_multiset& __u, const allocator_type& __a)
1276 : __table_(__u.__table_, __a)
1278 #if _LIBCPP_DEBUG_LEVEL >= 2
1279 __get_db()->__insert_c(this);
1281 __table_.rehash(__u.bucket_count());
1282 insert(__u.begin(), __u.end());
1285 #ifndef _LIBCPP_CXX03_LANG
1287 template <class _Value, class _Hash, class _Pred, class _Alloc>
1289 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1290 unordered_multiset&& __u)
1291 _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
1292 : __table_(_VSTD::move(__u.__table_))
1294 #if _LIBCPP_DEBUG_LEVEL >= 2
1295 __get_db()->__insert_c(this);
1296 __get_db()->swap(this, &__u);
1300 template <class _Value, class _Hash, class _Pred, class _Alloc>
1301 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1302 unordered_multiset&& __u, const allocator_type& __a)
1303 : __table_(_VSTD::move(__u.__table_), __a)
1305 #if _LIBCPP_DEBUG_LEVEL >= 2
1306 __get_db()->__insert_c(this);
1308 if (__a != __u.get_allocator())
1310 iterator __i = __u.begin();
1311 while (__u.size() != 0)
1312 __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
1314 #if _LIBCPP_DEBUG_LEVEL >= 2
1316 __get_db()->swap(this, &__u);
1320 template <class _Value, class _Hash, class _Pred, class _Alloc>
1321 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1322 initializer_list<value_type> __il)
1324 #if _LIBCPP_DEBUG_LEVEL >= 2
1325 __get_db()->__insert_c(this);
1327 insert(__il.begin(), __il.end());
1330 template <class _Value, class _Hash, class _Pred, class _Alloc>
1331 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1332 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1333 const key_equal& __eql)
1334 : __table_(__hf, __eql)
1336 #if _LIBCPP_DEBUG_LEVEL >= 2
1337 __get_db()->__insert_c(this);
1339 __table_.rehash(__n);
1340 insert(__il.begin(), __il.end());
1343 template <class _Value, class _Hash, class _Pred, class _Alloc>
1344 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
1345 initializer_list<value_type> __il, size_type __n, const hasher& __hf,
1346 const key_equal& __eql, const allocator_type& __a)
1347 : __table_(__hf, __eql, __a)
1349 #if _LIBCPP_DEBUG_LEVEL >= 2
1350 __get_db()->__insert_c(this);
1352 __table_.rehash(__n);
1353 insert(__il.begin(), __il.end());
1356 template <class _Value, class _Hash, class _Pred, class _Alloc>
1358 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1359 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1360 unordered_multiset&& __u)
1361 _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
1363 __table_ = _VSTD::move(__u.__table_);
1367 template <class _Value, class _Hash, class _Pred, class _Alloc>
1369 unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
1370 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
1371 initializer_list<value_type> __il)
1373 __table_.__assign_multi(__il.begin(), __il.end());
1377 #endif // _LIBCPP_CXX03_LANG
1379 template <class _Value, class _Hash, class _Pred, class _Alloc>
1380 template <class _InputIterator>
1383 unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
1384 _InputIterator __last)
1386 for (; __first != __last; ++__first)
1387 __table_.__insert_multi(*__first);
1390 template <class _Value, class _Hash, class _Pred, class _Alloc>
1391 inline _LIBCPP_INLINE_VISIBILITY
1393 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1394 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1395 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1400 template <class _Value, class _Hash, class _Pred, class _Alloc>
1402 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1403 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1405 if (__x.size() != __y.size())
1407 typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
1409 typedef pair<const_iterator, const_iterator> _EqRng;
1410 for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
1412 _EqRng __xeq = __x.equal_range(*__i);
1413 _EqRng __yeq = __y.equal_range(*__i);
1414 if (_VSTD::distance(__xeq.first, __xeq.second) !=
1415 _VSTD::distance(__yeq.first, __yeq.second) ||
1416 !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
1423 template <class _Value, class _Hash, class _Pred, class _Alloc>
1424 inline _LIBCPP_INLINE_VISIBILITY
1426 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
1427 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
1429 return !(__x == __y);
1432 _LIBCPP_END_NAMESPACE_STD
1434 #endif // _LIBCPP_UNORDERED_SET