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