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