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_NODISCARD_AFTER_CXX17 _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_NODISCARD_AFTER_CXX17 _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) const {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 1219