overby.me
this repo has no description
1// -*- C++ -*-
2//===---------------------------- set -------------------------------------===//
3//
4// The LLVM Compiler Infrastructure
5//
6// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_SET
12#define _LIBCPP_SET
13
14/*
15
16 set synopsis
17
18namespace std
19{
20
21template <class Key, class Compare = less<Key>,
22 class Allocator = allocator<Key>>
23class set
24{
25public:
26 // types:
27 typedef Key key_type;
28 typedef key_type value_type;
29 typedef Compare key_compare;
30 typedef key_compare value_compare;
31 typedef Allocator allocator_type;
32 typedef typename allocator_type::reference reference;
33 typedef typename allocator_type::const_reference const_reference;
34 typedef typename allocator_type::size_type size_type;
35 typedef typename allocator_type::difference_type difference_type;
36 typedef typename allocator_type::pointer pointer;
37 typedef typename allocator_type::const_pointer const_pointer;
38
39 typedef implementation-defined iterator;
40 typedef implementation-defined const_iterator;
41 typedef std::reverse_iterator<iterator> reverse_iterator;
42 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
43
44 // construct/copy/destroy:
45 set()
46 noexcept(
47 is_nothrow_default_constructible<allocator_type>::value &&
48 is_nothrow_default_constructible<key_compare>::value &&
49 is_nothrow_copy_constructible<key_compare>::value);
50 explicit set(const value_compare& comp);
51 set(const value_compare& comp, const allocator_type& a);
52 template <class InputIterator>
53 set(InputIterator first, InputIterator last,
54 const value_compare& comp = value_compare());
55 template <class InputIterator>
56 set(InputIterator first, InputIterator last, const value_compare& comp,
57 const allocator_type& a);
58 set(const set& s);
59 set(set&& s)
60 noexcept(
61 is_nothrow_move_constructible<allocator_type>::value &&
62 is_nothrow_move_constructible<key_compare>::value);
63 explicit set(const allocator_type& a);
64 set(const set& s, const allocator_type& a);
65 set(set&& s, const allocator_type& a);
66 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
67 set(initializer_list<value_type> il, const value_compare& comp,
68 const allocator_type& a);
69 template <class InputIterator>
70 set(InputIterator first, InputIterator last, const allocator_type& a)
71 : set(first, last, Compare(), a) {} // C++14
72 set(initializer_list<value_type> il, const allocator_type& a)
73 : set(il, Compare(), a) {} // C++14
74 ~set();
75
76 set& operator=(const set& s);
77 set& operator=(set&& s)
78 noexcept(
79 allocator_type::propagate_on_container_move_assignment::value &&
80 is_nothrow_move_assignable<allocator_type>::value &&
81 is_nothrow_move_assignable<key_compare>::value);
82 set& operator=(initializer_list<value_type> il);
83
84 // iterators:
85 iterator begin() noexcept;
86 const_iterator begin() const noexcept;
87 iterator end() noexcept;
88 const_iterator end() const noexcept;
89
90 reverse_iterator rbegin() noexcept;
91 const_reverse_iterator rbegin() const noexcept;
92 reverse_iterator rend() noexcept;
93 const_reverse_iterator rend() const noexcept;
94
95 const_iterator cbegin() const noexcept;
96 const_iterator cend() const noexcept;
97 const_reverse_iterator crbegin() const noexcept;
98 const_reverse_iterator crend() const noexcept;
99
100 // capacity:
101 bool empty() const noexcept;
102 size_type size() const noexcept;
103 size_type max_size() const noexcept;
104
105 // modifiers:
106 template <class... Args>
107 pair<iterator, bool> emplace(Args&&... args);
108 template <class... Args>
109 iterator emplace_hint(const_iterator position, Args&&... args);
110 pair<iterator,bool> insert(const value_type& v);
111 pair<iterator,bool> insert(value_type&& v);
112 iterator insert(const_iterator position, const value_type& v);
113 iterator insert(const_iterator position, value_type&& v);
114 template <class InputIterator>
115 void insert(InputIterator first, InputIterator last);
116 void insert(initializer_list<value_type> il);
117
118 iterator erase(const_iterator position);
119 iterator erase(iterator position); // C++14
120 size_type erase(const key_type& k);
121 iterator erase(const_iterator first, const_iterator last);
122 void clear() noexcept;
123
124 void swap(set& s)
125 noexcept(
126 __is_nothrow_swappable<key_compare>::value &&
127 (!allocator_type::propagate_on_container_swap::value ||
128 __is_nothrow_swappable<allocator_type>::value));
129
130 // observers:
131 allocator_type get_allocator() const noexcept;
132 key_compare key_comp() const;
133 value_compare value_comp() const;
134
135 // set operations:
136 iterator find(const key_type& k);
137 const_iterator find(const key_type& k) const;
138 template<typename K>
139 iterator find(const K& x);
140 template<typename K>
141 const_iterator find(const K& x) const; // C++14
142 template<typename K>
143 size_type count(const K& x) const; // C++14
144
145 size_type count(const key_type& k) const;
146 iterator lower_bound(const key_type& k);
147 const_iterator lower_bound(const key_type& k) const;
148 template<typename K>
149 iterator lower_bound(const K& x); // C++14
150 template<typename K>
151 const_iterator lower_bound(const K& x) const; // C++14
152
153 iterator upper_bound(const key_type& k);
154 const_iterator upper_bound(const key_type& k) const;
155 template<typename K>
156 iterator upper_bound(const K& x); // C++14
157 template<typename K>
158 const_iterator upper_bound(const K& x) const; // C++14
159 pair<iterator,iterator> equal_range(const key_type& k);
160 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
161 template<typename K>
162 pair<iterator,iterator> equal_range(const K& x); // C++14
163 template<typename K>
164 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
165};
166
167template <class Key, class Compare, class Allocator>
168bool
169operator==(const set<Key, Compare, Allocator>& x,
170 const set<Key, Compare, Allocator>& y);
171
172template <class Key, class Compare, class Allocator>
173bool
174operator< (const set<Key, Compare, Allocator>& x,
175 const set<Key, Compare, Allocator>& y);
176
177template <class Key, class Compare, class Allocator>
178bool
179operator!=(const set<Key, Compare, Allocator>& x,
180 const set<Key, Compare, Allocator>& y);
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
197// specialized algorithms:
198template <class Key, class Compare, class Allocator>
199void
200swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
201 noexcept(noexcept(x.swap(y)));
202
203template <class Key, class Compare = less<Key>,
204 class Allocator = allocator<Key>>
205class multiset
206{
207public:
208 // types:
209 typedef Key key_type;
210 typedef key_type value_type;
211 typedef Compare key_compare;
212 typedef key_compare value_compare;
213 typedef Allocator allocator_type;
214 typedef typename allocator_type::reference reference;
215 typedef typename allocator_type::const_reference const_reference;
216 typedef typename allocator_type::size_type size_type;
217 typedef typename allocator_type::difference_type difference_type;
218 typedef typename allocator_type::pointer pointer;
219 typedef typename allocator_type::const_pointer const_pointer;
220
221 typedef implementation-defined iterator;
222 typedef implementation-defined const_iterator;
223 typedef std::reverse_iterator<iterator> reverse_iterator;
224 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
225
226 // construct/copy/destroy:
227 multiset()
228 noexcept(
229 is_nothrow_default_constructible<allocator_type>::value &&
230 is_nothrow_default_constructible<key_compare>::value &&
231 is_nothrow_copy_constructible<key_compare>::value);
232 explicit multiset(const value_compare& comp);
233 multiset(const value_compare& comp, const allocator_type& a);
234 template <class InputIterator>
235 multiset(InputIterator first, InputIterator last,
236 const value_compare& comp = value_compare());
237 template <class InputIterator>
238 multiset(InputIterator first, InputIterator last,
239 const value_compare& comp, const allocator_type& a);
240 multiset(const multiset& s);
241 multiset(multiset&& s)
242 noexcept(
243 is_nothrow_move_constructible<allocator_type>::value &&
244 is_nothrow_move_constructible<key_compare>::value);
245 explicit multiset(const allocator_type& a);
246 multiset(const multiset& s, const allocator_type& a);
247 multiset(multiset&& s, const allocator_type& a);
248 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
249 multiset(initializer_list<value_type> il, const value_compare& comp,
250 const allocator_type& a);
251 template <class InputIterator>
252 multiset(InputIterator first, InputIterator last, const allocator_type& a)
253 : set(first, last, Compare(), a) {} // C++14
254 multiset(initializer_list<value_type> il, const allocator_type& a)
255 : set(il, Compare(), a) {} // C++14
256 ~multiset();
257
258 multiset& operator=(const multiset& s);
259 multiset& operator=(multiset&& s)
260 noexcept(
261 allocator_type::propagate_on_container_move_assignment::value &&
262 is_nothrow_move_assignable<allocator_type>::value &&
263 is_nothrow_move_assignable<key_compare>::value);
264 multiset& operator=(initializer_list<value_type> il);
265
266 // iterators:
267 iterator begin() noexcept;
268 const_iterator begin() const noexcept;
269 iterator end() noexcept;
270 const_iterator end() const noexcept;
271
272 reverse_iterator rbegin() noexcept;
273 const_reverse_iterator rbegin() const noexcept;
274 reverse_iterator rend() noexcept;
275 const_reverse_iterator rend() const noexcept;
276
277 const_iterator cbegin() const noexcept;
278 const_iterator cend() const noexcept;
279 const_reverse_iterator crbegin() const noexcept;
280 const_reverse_iterator crend() const noexcept;
281
282 // capacity:
283 bool empty() const noexcept;
284 size_type size() const noexcept;
285 size_type max_size() const noexcept;
286
287 // modifiers:
288 template <class... Args>
289 iterator emplace(Args&&... args);
290 template <class... Args>
291 iterator emplace_hint(const_iterator position, Args&&... args);
292 iterator insert(const value_type& v);
293 iterator insert(value_type&& v);
294 iterator insert(const_iterator position, const value_type& v);
295 iterator insert(const_iterator position, value_type&& v);
296 template <class InputIterator>
297 void insert(InputIterator first, InputIterator last);
298 void insert(initializer_list<value_type> il);
299
300 iterator erase(const_iterator position);
301 iterator erase(iterator position); // C++14
302 size_type erase(const key_type& k);
303 iterator erase(const_iterator first, const_iterator last);
304 void clear() noexcept;
305
306 void swap(multiset& s)
307 noexcept(
308 __is_nothrow_swappable<key_compare>::value &&
309 (!allocator_type::propagate_on_container_swap::value ||
310 __is_nothrow_swappable<allocator_type>::value));
311
312 // observers:
313 allocator_type get_allocator() const noexcept;
314 key_compare key_comp() const;
315 value_compare value_comp() const;
316
317 // set operations:
318 iterator find(const key_type& k);
319 const_iterator find(const key_type& k) const;
320 template<typename K>
321 iterator find(const K& x);
322 template<typename K>
323 const_iterator find(const K& x) const; // C++14
324
325 size_type count(const key_type& k) const;
326 iterator lower_bound(const key_type& k);
327 const_iterator lower_bound(const key_type& k) const;
328 template<typename K>
329 iterator lower_bound(const K& x); // C++14
330 template<typename K>
331 const_iterator lower_bound(const K& x) const; // C++14
332
333 iterator upper_bound(const key_type& k);
334 const_iterator upper_bound(const key_type& k) const;
335 template<typename K>
336 iterator upper_bound(const K& x); // C++14
337 template<typename K>
338 const_iterator upper_bound(const K& x) const; // C++14
339
340 pair<iterator,iterator> equal_range(const key_type& k);
341 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
342 template<typename K>
343 pair<iterator,iterator> equal_range(const K& x); // C++14
344 template<typename K>
345 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
346};
347
348template <class Key, class Compare, class Allocator>
349bool
350operator==(const multiset<Key, Compare, Allocator>& x,
351 const multiset<Key, Compare, Allocator>& y);
352
353template <class Key, class Compare, class Allocator>
354bool
355operator< (const multiset<Key, Compare, Allocator>& x,
356 const multiset<Key, Compare, Allocator>& y);
357
358template <class Key, class Compare, class Allocator>
359bool
360operator!=(const multiset<Key, Compare, Allocator>& x,
361 const multiset<Key, Compare, Allocator>& y);
362
363template <class Key, class Compare, class Allocator>
364bool
365operator> (const multiset<Key, Compare, Allocator>& x,
366 const multiset<Key, Compare, Allocator>& y);
367
368template <class Key, class Compare, class Allocator>
369bool
370operator>=(const multiset<Key, Compare, Allocator>& x,
371 const multiset<Key, Compare, Allocator>& y);
372
373template <class Key, class Compare, class Allocator>
374bool
375operator<=(const multiset<Key, Compare, Allocator>& x,
376 const multiset<Key, Compare, Allocator>& y);
377
378// specialized algorithms:
379template <class Key, class Compare, class Allocator>
380void
381swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
382 noexcept(noexcept(x.swap(y)));
383
384} // std
385
386*/
387
388#include <__config>
389#include <__tree>
390#include <functional>
391
392#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
393#pragma GCC system_header
394#endif
395
396_LIBCPP_BEGIN_NAMESPACE_STD
397
398template <class _Key, class _Compare = less<_Key>,
399 class _Allocator = allocator<_Key> >
400class _LIBCPP_TEMPLATE_VIS set
401{
402public:
403 // types:
404 typedef _Key key_type;
405 typedef key_type value_type;
406 typedef _Compare key_compare;
407 typedef key_compare value_compare;
408 typedef _Allocator allocator_type;
409 typedef value_type& reference;
410 typedef const value_type& const_reference;
411
412 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
413 "Allocator::value_type must be same type as value_type");
414
415private:
416 typedef __tree<value_type, value_compare, allocator_type> __base;
417 typedef allocator_traits<allocator_type> __alloc_traits;
418 typedef typename __base::__node_holder __node_holder;
419
420 __base __tree_;
421
422public:
423 typedef typename __base::pointer pointer;
424 typedef typename __base::const_pointer const_pointer;
425 typedef typename __base::size_type size_type;
426 typedef typename __base::difference_type difference_type;
427 typedef typename __base::const_iterator iterator;
428 typedef typename __base::const_iterator const_iterator;
429 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
430 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
431
432 _LIBCPP_INLINE_VISIBILITY
433 set()
434 _NOEXCEPT_(
435 is_nothrow_default_constructible<allocator_type>::value &&
436 is_nothrow_default_constructible<key_compare>::value &&
437 is_nothrow_copy_constructible<key_compare>::value)
438 : __tree_(value_compare()) {}
439
440 _LIBCPP_INLINE_VISIBILITY
441 explicit set(const value_compare& __comp)
442 _NOEXCEPT_(
443 is_nothrow_default_constructible<allocator_type>::value &&
444 is_nothrow_copy_constructible<key_compare>::value)
445 : __tree_(__comp) {}
446
447 _LIBCPP_INLINE_VISIBILITY
448 explicit set(const value_compare& __comp, const allocator_type& __a)
449 : __tree_(__comp, __a) {}
450 template <class _InputIterator>
451 _LIBCPP_INLINE_VISIBILITY
452 set(_InputIterator __f, _InputIterator __l,
453 const value_compare& __comp = value_compare())
454 : __tree_(__comp)
455 {
456 insert(__f, __l);
457 }
458
459 template <class _InputIterator>
460 _LIBCPP_INLINE_VISIBILITY
461 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
462 const allocator_type& __a)
463 : __tree_(__comp, __a)
464 {
465 insert(__f, __l);
466 }
467
468#if _LIBCPP_STD_VER > 11
469 template <class _InputIterator>
470 _LIBCPP_INLINE_VISIBILITY
471 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
472 : set(__f, __l, key_compare(), __a) {}
473#endif
474
475 _LIBCPP_INLINE_VISIBILITY
476 set(const set& __s)
477 : __tree_(__s.__tree_)
478 {
479 insert(__s.begin(), __s.end());
480 }
481
482 _LIBCPP_INLINE_VISIBILITY
483 set& operator=(const set& __s)
484 {
485 __tree_ = __s.__tree_;
486 return *this;
487 }
488
489#ifndef _LIBCPP_CXX03_LANG
490 _LIBCPP_INLINE_VISIBILITY
491 set(set&& __s)
492 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
493 : __tree_(_VSTD::move(__s.__tree_)) {}
494#endif // _LIBCPP_CXX03_LANG
495
496 _LIBCPP_INLINE_VISIBILITY
497 explicit set(const allocator_type& __a)
498 : __tree_(__a) {}
499
500 _LIBCPP_INLINE_VISIBILITY
501 set(const set& __s, const allocator_type& __a)
502 : __tree_(__s.__tree_.value_comp(), __a)
503 {
504 insert(__s.begin(), __s.end());
505 }
506
507#ifndef _LIBCPP_CXX03_LANG
508 set(set&& __s, const allocator_type& __a);
509
510 _LIBCPP_INLINE_VISIBILITY
511 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
512 : __tree_(__comp)
513 {
514 insert(__il.begin(), __il.end());
515 }
516
517 _LIBCPP_INLINE_VISIBILITY
518 set(initializer_list<value_type> __il, const value_compare& __comp,
519 const allocator_type& __a)
520 : __tree_(__comp, __a)
521 {
522 insert(__il.begin(), __il.end());
523 }
524
525#if _LIBCPP_STD_VER > 11
526 _LIBCPP_INLINE_VISIBILITY
527 set(initializer_list<value_type> __il, const allocator_type& __a)
528 : set(__il, key_compare(), __a) {}
529#endif
530
531 _LIBCPP_INLINE_VISIBILITY
532 set& operator=(initializer_list<value_type> __il)
533 {
534 __tree_.__assign_unique(__il.begin(), __il.end());
535 return *this;
536 }
537
538 _LIBCPP_INLINE_VISIBILITY
539 set& operator=(set&& __s)
540 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
541 {
542 __tree_ = _VSTD::move(__s.__tree_);
543 return *this;
544 }
545#endif // _LIBCPP_CXX03_LANG
546
547 _LIBCPP_INLINE_VISIBILITY
548 iterator begin() _NOEXCEPT {return __tree_.begin();}
549 _LIBCPP_INLINE_VISIBILITY
550 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
551 _LIBCPP_INLINE_VISIBILITY
552 iterator end() _NOEXCEPT {return __tree_.end();}
553 _LIBCPP_INLINE_VISIBILITY
554 const_iterator end() const _NOEXCEPT {return __tree_.end();}
555
556 _LIBCPP_INLINE_VISIBILITY
557 reverse_iterator rbegin() _NOEXCEPT
558 {return reverse_iterator(end());}
559 _LIBCPP_INLINE_VISIBILITY
560 const_reverse_iterator rbegin() const _NOEXCEPT
561 {return const_reverse_iterator(end());}
562 _LIBCPP_INLINE_VISIBILITY
563 reverse_iterator rend() _NOEXCEPT
564 {return reverse_iterator(begin());}
565 _LIBCPP_INLINE_VISIBILITY
566 const_reverse_iterator rend() const _NOEXCEPT
567 {return const_reverse_iterator(begin());}
568
569 _LIBCPP_INLINE_VISIBILITY
570 const_iterator cbegin() const _NOEXCEPT {return begin();}
571 _LIBCPP_INLINE_VISIBILITY
572 const_iterator cend() const _NOEXCEPT {return end();}
573 _LIBCPP_INLINE_VISIBILITY
574 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
575 _LIBCPP_INLINE_VISIBILITY
576 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
577
578 _LIBCPP_INLINE_VISIBILITY
579 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
580 _LIBCPP_INLINE_VISIBILITY
581 size_type size() const _NOEXCEPT {return __tree_.size();}
582 _LIBCPP_INLINE_VISIBILITY
583 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
584
585 // modifiers:
586#ifndef _LIBCPP_CXX03_LANG
587 template <class... _Args>
588 _LIBCPP_INLINE_VISIBILITY
589 pair<iterator, bool> emplace(_Args&&... __args)
590 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
591 template <class... _Args>
592 _LIBCPP_INLINE_VISIBILITY
593 iterator emplace_hint(const_iterator __p, _Args&&... __args)
594 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}
595#endif // _LIBCPP_CXX03_LANG
596
597 _LIBCPP_INLINE_VISIBILITY
598 pair<iterator,bool> insert(const value_type& __v)
599 {return __tree_.__insert_unique(__v);}
600 _LIBCPP_INLINE_VISIBILITY
601 iterator insert(const_iterator __p, const value_type& __v)
602 {return __tree_.__insert_unique(__p, __v);}
603
604 template <class _InputIterator>
605 _LIBCPP_INLINE_VISIBILITY
606 void insert(_InputIterator __f, _InputIterator __l)
607 {
608 for (const_iterator __e = cend(); __f != __l; ++__f)
609 __tree_.__insert_unique(__e, *__f);
610 }
611
612#ifndef _LIBCPP_CXX03_LANG
613 _LIBCPP_INLINE_VISIBILITY
614 pair<iterator,bool> insert(value_type&& __v)
615 {return __tree_.__insert_unique(_VSTD::move(__v));}
616
617 _LIBCPP_INLINE_VISIBILITY
618 iterator insert(const_iterator __p, value_type&& __v)
619 {return __tree_.__insert_unique(__p, _VSTD::move(__v));}
620
621 _LIBCPP_INLINE_VISIBILITY
622 void insert(initializer_list<value_type> __il)
623 {insert(__il.begin(), __il.end());}
624#endif // _LIBCPP_CXX03_LANG
625
626 _LIBCPP_INLINE_VISIBILITY
627 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
628 _LIBCPP_INLINE_VISIBILITY
629 size_type erase(const key_type& __k)
630 {return __tree_.__erase_unique(__k);}
631 _LIBCPP_INLINE_VISIBILITY
632 iterator erase(const_iterator __f, const_iterator __l)
633 {return __tree_.erase(__f, __l);}
634 _LIBCPP_INLINE_VISIBILITY
635 void clear() _NOEXCEPT {__tree_.clear();}
636
637 _LIBCPP_INLINE_VISIBILITY
638 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
639 {__tree_.swap(__s.__tree_);}
640
641 _LIBCPP_INLINE_VISIBILITY
642 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
643 _LIBCPP_INLINE_VISIBILITY
644 key_compare key_comp() const {return __tree_.value_comp();}
645 _LIBCPP_INLINE_VISIBILITY
646 value_compare value_comp() const {return __tree_.value_comp();}
647
648 // set operations:
649 _LIBCPP_INLINE_VISIBILITY
650 iterator find(const key_type& __k) {return __tree_.find(__k);}
651 _LIBCPP_INLINE_VISIBILITY
652 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
653#if _LIBCPP_STD_VER > 11
654 template <typename _K2>
655 _LIBCPP_INLINE_VISIBILITY
656 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
657 find(const _K2& __k) {return __tree_.find(__k);}
658 template <typename _K2>
659 _LIBCPP_INLINE_VISIBILITY
660 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
661 find(const _K2& __k) const {return __tree_.find(__k);}
662#endif
663
664 _LIBCPP_INLINE_VISIBILITY
665 size_type count(const key_type& __k) const
666 {return __tree_.__count_unique(__k);}
667#if _LIBCPP_STD_VER > 11
668 template <typename _K2>
669 _LIBCPP_INLINE_VISIBILITY
670 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
671 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
672#endif
673 _LIBCPP_INLINE_VISIBILITY
674 iterator lower_bound(const key_type& __k)
675 {return __tree_.lower_bound(__k);}
676 _LIBCPP_INLINE_VISIBILITY
677 const_iterator lower_bound(const key_type& __k) const
678 {return __tree_.lower_bound(__k);}
679#if _LIBCPP_STD_VER > 11
680 template <typename _K2>
681 _LIBCPP_INLINE_VISIBILITY
682 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
683 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
684
685 template <typename _K2>
686 _LIBCPP_INLINE_VISIBILITY
687 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
688 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
689#endif
690
691 _LIBCPP_INLINE_VISIBILITY
692 iterator upper_bound(const key_type& __k)
693 {return __tree_.upper_bound(__k);}
694 _LIBCPP_INLINE_VISIBILITY
695 const_iterator upper_bound(const key_type& __k) const
696 {return __tree_.upper_bound(__k);}
697#if _LIBCPP_STD_VER > 11
698 template <typename _K2>
699 _LIBCPP_INLINE_VISIBILITY
700 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
701 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
702 template <typename _K2>
703 _LIBCPP_INLINE_VISIBILITY
704 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
705 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
706#endif
707
708 _LIBCPP_INLINE_VISIBILITY
709 pair<iterator,iterator> equal_range(const key_type& __k)
710 {return __tree_.__equal_range_unique(__k);}
711 _LIBCPP_INLINE_VISIBILITY
712 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
713 {return __tree_.__equal_range_unique(__k);}
714#if _LIBCPP_STD_VER > 11
715 template <typename _K2>
716 _LIBCPP_INLINE_VISIBILITY
717 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
718 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
719 template <typename _K2>
720 _LIBCPP_INLINE_VISIBILITY
721 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
722 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
723#endif
724};
725
726#ifndef _LIBCPP_CXX03_LANG
727
728template <class _Key, class _Compare, class _Allocator>
729set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
730 : __tree_(_VSTD::move(__s.__tree_), __a)
731{
732 if (__a != __s.get_allocator())
733 {
734 const_iterator __e = cend();
735 while (!__s.empty())
736 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
737 }
738}
739
740#endif // _LIBCPP_CXX03_LANG
741
742template <class _Key, class _Compare, class _Allocator>
743inline _LIBCPP_INLINE_VISIBILITY
744bool
745operator==(const set<_Key, _Compare, _Allocator>& __x,
746 const set<_Key, _Compare, _Allocator>& __y)
747{
748 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
749}
750
751template <class _Key, class _Compare, class _Allocator>
752inline _LIBCPP_INLINE_VISIBILITY
753bool
754operator< (const set<_Key, _Compare, _Allocator>& __x,
755 const set<_Key, _Compare, _Allocator>& __y)
756{
757 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
758}
759
760template <class _Key, class _Compare, class _Allocator>
761inline _LIBCPP_INLINE_VISIBILITY
762bool
763operator!=(const set<_Key, _Compare, _Allocator>& __x,
764 const set<_Key, _Compare, _Allocator>& __y)
765{
766 return !(__x == __y);
767}
768
769template <class _Key, class _Compare, class _Allocator>
770inline _LIBCPP_INLINE_VISIBILITY
771bool
772operator> (const set<_Key, _Compare, _Allocator>& __x,
773 const set<_Key, _Compare, _Allocator>& __y)
774{
775 return __y < __x;
776}
777
778template <class _Key, class _Compare, class _Allocator>
779inline _LIBCPP_INLINE_VISIBILITY
780bool
781operator>=(const set<_Key, _Compare, _Allocator>& __x,
782 const set<_Key, _Compare, _Allocator>& __y)
783{
784 return !(__x < __y);
785}
786
787template <class _Key, class _Compare, class _Allocator>
788inline _LIBCPP_INLINE_VISIBILITY
789bool
790operator<=(const set<_Key, _Compare, _Allocator>& __x,
791 const set<_Key, _Compare, _Allocator>& __y)
792{
793 return !(__y < __x);
794}
795
796// specialized algorithms:
797template <class _Key, class _Compare, class _Allocator>
798inline _LIBCPP_INLINE_VISIBILITY
799void
800swap(set<_Key, _Compare, _Allocator>& __x,
801 set<_Key, _Compare, _Allocator>& __y)
802 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
803{
804 __x.swap(__y);
805}
806
807template <class _Key, class _Compare = less<_Key>,
808 class _Allocator = allocator<_Key> >
809class _LIBCPP_TEMPLATE_VIS multiset
810{
811public:
812 // types:
813 typedef _Key key_type;
814 typedef key_type value_type;
815 typedef _Compare key_compare;
816 typedef key_compare value_compare;
817 typedef _Allocator allocator_type;
818 typedef value_type& reference;
819 typedef const value_type& const_reference;
820
821 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
822 "Allocator::value_type must be same type as value_type");
823
824private:
825 typedef __tree<value_type, value_compare, allocator_type> __base;
826 typedef allocator_traits<allocator_type> __alloc_traits;
827 typedef typename __base::__node_holder __node_holder;
828
829 __base __tree_;
830
831public:
832 typedef typename __base::pointer pointer;
833 typedef typename __base::const_pointer const_pointer;
834 typedef typename __base::size_type size_type;
835 typedef typename __base::difference_type difference_type;
836 typedef typename __base::const_iterator iterator;
837 typedef typename __base::const_iterator const_iterator;
838 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
839 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
840
841 // construct/copy/destroy:
842 _LIBCPP_INLINE_VISIBILITY
843 multiset()
844 _NOEXCEPT_(
845 is_nothrow_default_constructible<allocator_type>::value &&
846 is_nothrow_default_constructible<key_compare>::value &&
847 is_nothrow_copy_constructible<key_compare>::value)
848 : __tree_(value_compare()) {}
849
850 _LIBCPP_INLINE_VISIBILITY
851 explicit multiset(const value_compare& __comp)
852 _NOEXCEPT_(
853 is_nothrow_default_constructible<allocator_type>::value &&
854 is_nothrow_copy_constructible<key_compare>::value)
855 : __tree_(__comp) {}
856
857 _LIBCPP_INLINE_VISIBILITY
858 explicit multiset(const value_compare& __comp, const allocator_type& __a)
859 : __tree_(__comp, __a) {}
860 template <class _InputIterator>
861 _LIBCPP_INLINE_VISIBILITY
862 multiset(_InputIterator __f, _InputIterator __l,
863 const value_compare& __comp = value_compare())
864 : __tree_(__comp)
865 {
866 insert(__f, __l);
867 }
868
869#if _LIBCPP_STD_VER > 11
870 template <class _InputIterator>
871 _LIBCPP_INLINE_VISIBILITY
872 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
873 : multiset(__f, __l, key_compare(), __a) {}
874#endif
875
876 template <class _InputIterator>
877 _LIBCPP_INLINE_VISIBILITY
878 multiset(_InputIterator __f, _InputIterator __l,
879 const value_compare& __comp, const allocator_type& __a)
880 : __tree_(__comp, __a)
881 {
882 insert(__f, __l);
883 }
884
885 _LIBCPP_INLINE_VISIBILITY
886 multiset(const multiset& __s)
887 : __tree_(__s.__tree_.value_comp(),
888 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
889 {
890 insert(__s.begin(), __s.end());
891 }
892
893 _LIBCPP_INLINE_VISIBILITY
894 multiset& operator=(const multiset& __s)
895 {
896 __tree_ = __s.__tree_;
897 return *this;
898 }
899
900#ifndef _LIBCPP_CXX03_LANG
901 _LIBCPP_INLINE_VISIBILITY
902 multiset(multiset&& __s)
903 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
904 : __tree_(_VSTD::move(__s.__tree_)) {}
905
906 multiset(multiset&& __s, const allocator_type& __a);
907#endif // _LIBCPP_CXX03_LANG
908 _LIBCPP_INLINE_VISIBILITY
909 explicit multiset(const allocator_type& __a)
910 : __tree_(__a) {}
911 _LIBCPP_INLINE_VISIBILITY
912 multiset(const multiset& __s, const allocator_type& __a)
913 : __tree_(__s.__tree_.value_comp(), __a)
914 {
915 insert(__s.begin(), __s.end());
916 }
917
918#ifndef _LIBCPP_CXX03_LANG
919 _LIBCPP_INLINE_VISIBILITY
920 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
921 : __tree_(__comp)
922 {
923 insert(__il.begin(), __il.end());
924 }
925
926 _LIBCPP_INLINE_VISIBILITY
927 multiset(initializer_list<value_type> __il, const value_compare& __comp,
928 const allocator_type& __a)
929 : __tree_(__comp, __a)
930 {
931 insert(__il.begin(), __il.end());
932 }
933
934#if _LIBCPP_STD_VER > 11
935 _LIBCPP_INLINE_VISIBILITY
936 multiset(initializer_list<value_type> __il, const allocator_type& __a)
937 : multiset(__il, key_compare(), __a) {}
938#endif
939
940 _LIBCPP_INLINE_VISIBILITY
941 multiset& operator=(initializer_list<value_type> __il)
942 {
943 __tree_.__assign_multi(__il.begin(), __il.end());
944 return *this;
945 }
946
947 _LIBCPP_INLINE_VISIBILITY
948 multiset& operator=(multiset&& __s)
949 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
950 {
951 __tree_ = _VSTD::move(__s.__tree_);
952 return *this;
953 }
954#endif // _LIBCPP_CXX03_LANG
955
956 _LIBCPP_INLINE_VISIBILITY
957 iterator begin() _NOEXCEPT {return __tree_.begin();}
958 _LIBCPP_INLINE_VISIBILITY
959 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
960 _LIBCPP_INLINE_VISIBILITY
961 iterator end() _NOEXCEPT {return __tree_.end();}
962 _LIBCPP_INLINE_VISIBILITY
963 const_iterator end() const _NOEXCEPT {return __tree_.end();}
964
965 _LIBCPP_INLINE_VISIBILITY
966 reverse_iterator rbegin() _NOEXCEPT
967 {return reverse_iterator(end());}
968 _LIBCPP_INLINE_VISIBILITY
969 const_reverse_iterator rbegin() const _NOEXCEPT
970 {return const_reverse_iterator(end());}
971 _LIBCPP_INLINE_VISIBILITY
972 reverse_iterator rend() _NOEXCEPT
973 {return reverse_iterator(begin());}
974 _LIBCPP_INLINE_VISIBILITY
975 const_reverse_iterator rend() const _NOEXCEPT
976 {return const_reverse_iterator(begin());}
977
978 _LIBCPP_INLINE_VISIBILITY
979 const_iterator cbegin() const _NOEXCEPT {return begin();}
980 _LIBCPP_INLINE_VISIBILITY
981 const_iterator cend() const _NOEXCEPT {return end();}
982 _LIBCPP_INLINE_VISIBILITY
983 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
984 _LIBCPP_INLINE_VISIBILITY
985 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
986
987 _LIBCPP_INLINE_VISIBILITY
988 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
989 _LIBCPP_INLINE_VISIBILITY
990 size_type size() const _NOEXCEPT {return __tree_.size();}
991 _LIBCPP_INLINE_VISIBILITY
992 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
993
994 // modifiers:
995#ifndef _LIBCPP_CXX03_LANG
996 template <class... _Args>
997 _LIBCPP_INLINE_VISIBILITY
998 iterator emplace(_Args&&... __args)
999 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
1000 template <class... _Args>
1001 _LIBCPP_INLINE_VISIBILITY
1002 iterator emplace_hint(const_iterator __p, _Args&&... __args)
1003 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
1004#endif // _LIBCPP_CXX03_LANG
1005
1006 _LIBCPP_INLINE_VISIBILITY
1007 iterator insert(const value_type& __v)
1008 {return __tree_.__insert_multi(__v);}
1009 _LIBCPP_INLINE_VISIBILITY
1010 iterator insert(const_iterator __p, const value_type& __v)
1011 {return __tree_.__insert_multi(__p, __v);}
1012
1013 template <class _InputIterator>
1014 _LIBCPP_INLINE_VISIBILITY
1015 void insert(_InputIterator __f, _InputIterator __l)
1016 {
1017 for (const_iterator __e = cend(); __f != __l; ++__f)
1018 __tree_.__insert_multi(__e, *__f);
1019 }
1020
1021#ifndef _LIBCPP_CXX03_LANG
1022 _LIBCPP_INLINE_VISIBILITY
1023 iterator insert(value_type&& __v)
1024 {return __tree_.__insert_multi(_VSTD::move(__v));}
1025
1026 _LIBCPP_INLINE_VISIBILITY
1027 iterator insert(const_iterator __p, value_type&& __v)
1028 {return __tree_.__insert_multi(__p, _VSTD::move(__v));}
1029
1030 _LIBCPP_INLINE_VISIBILITY
1031 void insert(initializer_list<value_type> __il)
1032 {insert(__il.begin(), __il.end());}
1033#endif // _LIBCPP_CXX03_LANG
1034
1035 _LIBCPP_INLINE_VISIBILITY
1036 iterator erase(const_iterator __p) {return __tree_.erase(__p);}
1037 _LIBCPP_INLINE_VISIBILITY
1038 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1039 _LIBCPP_INLINE_VISIBILITY
1040 iterator erase(const_iterator __f, const_iterator __l)
1041 {return __tree_.erase(__f, __l);}
1042 _LIBCPP_INLINE_VISIBILITY
1043 void clear() _NOEXCEPT {__tree_.clear();}
1044
1045 _LIBCPP_INLINE_VISIBILITY
1046 void swap(multiset& __s)
1047 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1048 {__tree_.swap(__s.__tree_);}
1049
1050 _LIBCPP_INLINE_VISIBILITY
1051 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1052 _LIBCPP_INLINE_VISIBILITY
1053 key_compare key_comp() const {return __tree_.value_comp();}
1054 _LIBCPP_INLINE_VISIBILITY
1055 value_compare value_comp() const {return __tree_.value_comp();}
1056
1057 // set operations:
1058 _LIBCPP_INLINE_VISIBILITY
1059 iterator find(const key_type& __k) {return __tree_.find(__k);}
1060 _LIBCPP_INLINE_VISIBILITY
1061 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1062#if _LIBCPP_STD_VER > 11
1063 template <typename _K2>
1064 _LIBCPP_INLINE_VISIBILITY
1065 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1066 find(const _K2& __k) {return __tree_.find(__k);}
1067 template <typename _K2>
1068 _LIBCPP_INLINE_VISIBILITY
1069 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1070 find(const _K2& __k) const {return __tree_.find(__k);}
1071#endif
1072
1073 _LIBCPP_INLINE_VISIBILITY
1074 size_type count(const key_type& __k) const
1075 {return __tree_.__count_multi(__k);}
1076#if _LIBCPP_STD_VER > 11
1077 template <typename _K2>
1078 _LIBCPP_INLINE_VISIBILITY
1079 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1080 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1081#endif
1082
1083 _LIBCPP_INLINE_VISIBILITY
1084 iterator lower_bound(const key_type& __k)
1085 {return __tree_.lower_bound(__k);}
1086 _LIBCPP_INLINE_VISIBILITY
1087 const_iterator lower_bound(const key_type& __k) const
1088 {return __tree_.lower_bound(__k);}
1089#if _LIBCPP_STD_VER > 11
1090 template <typename _K2>
1091 _LIBCPP_INLINE_VISIBILITY
1092 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1093 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1094
1095 template <typename _K2>
1096 _LIBCPP_INLINE_VISIBILITY
1097 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1098 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1099#endif
1100
1101 _LIBCPP_INLINE_VISIBILITY
1102 iterator upper_bound(const key_type& __k)
1103 {return __tree_.upper_bound(__k);}
1104 _LIBCPP_INLINE_VISIBILITY
1105 const_iterator upper_bound(const key_type& __k) const
1106 {return __tree_.upper_bound(__k);}
1107#if _LIBCPP_STD_VER > 11
1108 template <typename _K2>
1109 _LIBCPP_INLINE_VISIBILITY
1110 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type
1111 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1112 template <typename _K2>
1113 _LIBCPP_INLINE_VISIBILITY
1114 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type
1115 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1116#endif
1117
1118 _LIBCPP_INLINE_VISIBILITY
1119 pair<iterator,iterator> equal_range(const key_type& __k)
1120 {return __tree_.__equal_range_multi(__k);}
1121 _LIBCPP_INLINE_VISIBILITY
1122 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1123 {return __tree_.__equal_range_multi(__k);}
1124#if _LIBCPP_STD_VER > 11
1125 template <typename _K2>
1126 _LIBCPP_INLINE_VISIBILITY
1127 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1128 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1129 template <typename _K2>
1130 _LIBCPP_INLINE_VISIBILITY
1131 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1132 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1133#endif
1134};
1135
1136#ifndef _LIBCPP_CXX03_LANG
1137
1138template <class _Key, class _Compare, class _Allocator>
1139multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1140 : __tree_(_VSTD::move(__s.__tree_), __a)
1141{
1142 if (__a != __s.get_allocator())
1143 {
1144 const_iterator __e = cend();
1145 while (!__s.empty())
1146 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_));
1147 }
1148}
1149
1150#endif // _LIBCPP_CXX03_LANG
1151
1152template <class _Key, class _Compare, class _Allocator>
1153inline _LIBCPP_INLINE_VISIBILITY
1154bool
1155operator==(const multiset<_Key, _Compare, _Allocator>& __x,
1156 const multiset<_Key, _Compare, _Allocator>& __y)
1157{
1158 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1159}
1160
1161template <class _Key, class _Compare, class _Allocator>
1162inline _LIBCPP_INLINE_VISIBILITY
1163bool
1164operator< (const multiset<_Key, _Compare, _Allocator>& __x,
1165 const multiset<_Key, _Compare, _Allocator>& __y)
1166{
1167 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1168}
1169
1170template <class _Key, class _Compare, class _Allocator>
1171inline _LIBCPP_INLINE_VISIBILITY
1172bool
1173operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
1174 const multiset<_Key, _Compare, _Allocator>& __y)
1175{
1176 return !(__x == __y);
1177}
1178
1179template <class _Key, class _Compare, class _Allocator>
1180inline _LIBCPP_INLINE_VISIBILITY
1181bool
1182operator> (const multiset<_Key, _Compare, _Allocator>& __x,
1183 const multiset<_Key, _Compare, _Allocator>& __y)
1184{
1185 return __y < __x;
1186}
1187
1188template <class _Key, class _Compare, class _Allocator>
1189inline _LIBCPP_INLINE_VISIBILITY
1190bool
1191operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
1192 const multiset<_Key, _Compare, _Allocator>& __y)
1193{
1194 return !(__x < __y);
1195}
1196
1197template <class _Key, class _Compare, class _Allocator>
1198inline _LIBCPP_INLINE_VISIBILITY
1199bool
1200operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
1201 const multiset<_Key, _Compare, _Allocator>& __y)
1202{
1203 return !(__y < __x);
1204}
1205
1206template <class _Key, class _Compare, class _Allocator>
1207inline _LIBCPP_INLINE_VISIBILITY
1208void
1209swap(multiset<_Key, _Compare, _Allocator>& __x,
1210 multiset<_Key, _Compare, _Allocator>& __y)
1211 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1212{
1213 __x.swap(__y);
1214}
1215
1216_LIBCPP_END_NAMESPACE_STD
1217
1218#endif // _LIBCPP_SET