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 set() 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_(value_compare()) {} 434 435 _LIBCPP_INLINE_VISIBILITY 436 explicit set(const value_compare& __comp) 437 _NOEXCEPT_( 438 is_nothrow_default_constructible<allocator_type>::value && 439 is_nothrow_copy_constructible<key_compare>::value) 440 : __tree_(__comp) {} 441 442 _LIBCPP_INLINE_VISIBILITY 443 explicit set(const value_compare& __comp, const allocator_type& __a) 444 : __tree_(__comp, __a) {} 445 template <class _InputIterator> 446 _LIBCPP_INLINE_VISIBILITY 447 set(_InputIterator __f, _InputIterator __l, 448 const value_compare& __comp = value_compare()) 449 : __tree_(__comp) 450 { 451 insert(__f, __l); 452 } 453 454 template <class _InputIterator> 455 _LIBCPP_INLINE_VISIBILITY 456 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 457 const allocator_type& __a) 458 : __tree_(__comp, __a) 459 { 460 insert(__f, __l); 461 } 462 463#if _LIBCPP_STD_VER > 11 464 template <class _InputIterator> 465 _LIBCPP_INLINE_VISIBILITY 466 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 467 : set(__f, __l, key_compare(), __a) {} 468#endif 469 470 _LIBCPP_INLINE_VISIBILITY 471 set(const set& __s) 472 : __tree_(__s.__tree_) 473 { 474 insert(__s.begin(), __s.end()); 475 } 476 477 _LIBCPP_INLINE_VISIBILITY 478 set& operator=(const set& __s) 479 { 480 __tree_ = __s.__tree_; 481 return *this; 482 } 483 484#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 485 _LIBCPP_INLINE_VISIBILITY 486 set(set&& __s) 487 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 488 : __tree_(_VSTD::move(__s.__tree_)) {} 489#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 490 491 _LIBCPP_INLINE_VISIBILITY 492 explicit set(const allocator_type& __a) 493 : __tree_(__a) {} 494 495 _LIBCPP_INLINE_VISIBILITY 496 set(const set& __s, const allocator_type& __a) 497 : __tree_(__s.__tree_.value_comp(), __a) 498 { 499 insert(__s.begin(), __s.end()); 500 } 501 502#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 503 set(set&& __s, const allocator_type& __a); 504#endif 505 506#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 507 _LIBCPP_INLINE_VISIBILITY 508 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 509 : __tree_(__comp) 510 { 511 insert(__il.begin(), __il.end()); 512 } 513 514 _LIBCPP_INLINE_VISIBILITY 515 set(initializer_list<value_type> __il, const value_compare& __comp, 516 const allocator_type& __a) 517 : __tree_(__comp, __a) 518 { 519 insert(__il.begin(), __il.end()); 520 } 521 522#if _LIBCPP_STD_VER > 11 523 _LIBCPP_INLINE_VISIBILITY 524 set(initializer_list<value_type> __il, const allocator_type& __a) 525 : set(__il, key_compare(), __a) {} 526#endif 527 528 _LIBCPP_INLINE_VISIBILITY 529 set& operator=(initializer_list<value_type> __il) 530 { 531 __tree_.__assign_unique(__il.begin(), __il.end()); 532 return *this; 533 } 534#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 535 536#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 537 _LIBCPP_INLINE_VISIBILITY 538 set& operator=(set&& __s) 539 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 540 { 541 __tree_ = _VSTD::move(__s.__tree_); 542 return *this; 543 } 544#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 545 546 _LIBCPP_INLINE_VISIBILITY 547 iterator begin() _NOEXCEPT {return __tree_.begin();} 548 _LIBCPP_INLINE_VISIBILITY 549 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 550 _LIBCPP_INLINE_VISIBILITY 551 iterator end() _NOEXCEPT {return __tree_.end();} 552 _LIBCPP_INLINE_VISIBILITY 553 const_iterator end() const _NOEXCEPT {return __tree_.end();} 554 555 _LIBCPP_INLINE_VISIBILITY 556 reverse_iterator rbegin() _NOEXCEPT 557 {return reverse_iterator(end());} 558 _LIBCPP_INLINE_VISIBILITY 559 const_reverse_iterator rbegin() const _NOEXCEPT 560 {return const_reverse_iterator(end());} 561 _LIBCPP_INLINE_VISIBILITY 562 reverse_iterator rend() _NOEXCEPT 563 {return reverse_iterator(begin());} 564 _LIBCPP_INLINE_VISIBILITY 565 const_reverse_iterator rend() const _NOEXCEPT 566 {return const_reverse_iterator(begin());} 567 568 _LIBCPP_INLINE_VISIBILITY 569 const_iterator cbegin() const _NOEXCEPT {return begin();} 570 _LIBCPP_INLINE_VISIBILITY 571 const_iterator cend() const _NOEXCEPT {return end();} 572 _LIBCPP_INLINE_VISIBILITY 573 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 574 _LIBCPP_INLINE_VISIBILITY 575 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 576 577 _LIBCPP_INLINE_VISIBILITY 578 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 579 _LIBCPP_INLINE_VISIBILITY 580 size_type size() const _NOEXCEPT {return __tree_.size();} 581 _LIBCPP_INLINE_VISIBILITY 582 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 583 584 // modifiers: 585#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 586 template <class... _Args> 587 _LIBCPP_INLINE_VISIBILITY 588 pair<iterator, bool> emplace(_Args&&... __args) 589 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 590 template <class... _Args> 591 _LIBCPP_INLINE_VISIBILITY 592 iterator emplace_hint(const_iterator __p, _Args&&... __args) 593 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 594#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 595 _LIBCPP_INLINE_VISIBILITY 596 pair<iterator,bool> insert(const value_type& __v) 597 {return __tree_.__insert_unique(__v);} 598#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 599 _LIBCPP_INLINE_VISIBILITY 600 pair<iterator,bool> insert(value_type&& __v) 601 {return __tree_.__insert_unique(_VSTD::move(__v));} 602#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 603 _LIBCPP_INLINE_VISIBILITY 604 iterator insert(const_iterator __p, const value_type& __v) 605 {return __tree_.__insert_unique(__p, __v);} 606#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 607 _LIBCPP_INLINE_VISIBILITY 608 iterator insert(const_iterator __p, value_type&& __v) 609 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 610#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 611 template <class _InputIterator> 612 _LIBCPP_INLINE_VISIBILITY 613 void insert(_InputIterator __f, _InputIterator __l) 614 { 615 for (const_iterator __e = cend(); __f != __l; ++__f) 616 __tree_.__insert_unique(__e, *__f); 617 } 618 619#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 620 _LIBCPP_INLINE_VISIBILITY 621 void insert(initializer_list<value_type> __il) 622 {insert(__il.begin(), __il.end());} 623#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 624 625 _LIBCPP_INLINE_VISIBILITY 626 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 627 _LIBCPP_INLINE_VISIBILITY 628 size_type erase(const key_type& __k) 629 {return __tree_.__erase_unique(__k);} 630 _LIBCPP_INLINE_VISIBILITY 631 iterator erase(const_iterator __f, const_iterator __l) 632 {return __tree_.erase(__f, __l);} 633 _LIBCPP_INLINE_VISIBILITY 634 void clear() _NOEXCEPT {__tree_.clear();} 635 636 _LIBCPP_INLINE_VISIBILITY 637 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 638 {__tree_.swap(__s.__tree_);} 639 640 _LIBCPP_INLINE_VISIBILITY 641 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 642 _LIBCPP_INLINE_VISIBILITY 643 key_compare key_comp() const {return __tree_.value_comp();} 644 _LIBCPP_INLINE_VISIBILITY 645 value_compare value_comp() const {return __tree_.value_comp();} 646 647 // set operations: 648 _LIBCPP_INLINE_VISIBILITY 649 iterator find(const key_type& __k) {return __tree_.find(__k);} 650 _LIBCPP_INLINE_VISIBILITY 651 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 652#if _LIBCPP_STD_VER > 11 653 template <typename _K2> 654 _LIBCPP_INLINE_VISIBILITY 655 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 656 find(const _K2& __k) {return __tree_.find(__k);} 657 template <typename _K2> 658 _LIBCPP_INLINE_VISIBILITY 659 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 660 find(const _K2& __k) const {return __tree_.find(__k);} 661#endif 662 663 _LIBCPP_INLINE_VISIBILITY 664 size_type count(const key_type& __k) const 665 {return __tree_.__count_unique(__k);} 666 _LIBCPP_INLINE_VISIBILITY 667 iterator lower_bound(const key_type& __k) 668 {return __tree_.lower_bound(__k);} 669 _LIBCPP_INLINE_VISIBILITY 670 const_iterator lower_bound(const key_type& __k) const 671 {return __tree_.lower_bound(__k);} 672#if _LIBCPP_STD_VER > 11 673 template <typename _K2> 674 _LIBCPP_INLINE_VISIBILITY 675 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 676 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 677 678 template <typename _K2> 679 _LIBCPP_INLINE_VISIBILITY 680 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 681 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 682#endif 683 684 _LIBCPP_INLINE_VISIBILITY 685 iterator upper_bound(const key_type& __k) 686 {return __tree_.upper_bound(__k);} 687 _LIBCPP_INLINE_VISIBILITY 688 const_iterator upper_bound(const key_type& __k) const 689 {return __tree_.upper_bound(__k);} 690#if _LIBCPP_STD_VER > 11 691 template <typename _K2> 692 _LIBCPP_INLINE_VISIBILITY 693 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 694 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 695 template <typename _K2> 696 _LIBCPP_INLINE_VISIBILITY 697 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 698 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 699#endif 700 701 _LIBCPP_INLINE_VISIBILITY 702 pair<iterator,iterator> equal_range(const key_type& __k) 703 {return __tree_.__equal_range_unique(__k);} 704 _LIBCPP_INLINE_VISIBILITY 705 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 706 {return __tree_.__equal_range_unique(__k);} 707#if _LIBCPP_STD_VER > 11 708 template <typename _K2> 709 _LIBCPP_INLINE_VISIBILITY 710 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 711 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 712 template <typename _K2> 713 _LIBCPP_INLINE_VISIBILITY 714 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 715 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 716#endif 717}; 718 719#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 720 721template <class _Key, class _Compare, class _Allocator> 722set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 723 : __tree_(_VSTD::move(__s.__tree_), __a) 724{ 725 if (__a != __s.get_allocator()) 726 { 727 const_iterator __e = cend(); 728 while (!__s.empty()) 729 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 730 } 731} 732 733#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 734 735template <class _Key, class _Compare, class _Allocator> 736inline _LIBCPP_INLINE_VISIBILITY 737bool 738operator==(const set<_Key, _Compare, _Allocator>& __x, 739 const set<_Key, _Compare, _Allocator>& __y) 740{ 741 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 742} 743 744template <class _Key, class _Compare, class _Allocator> 745inline _LIBCPP_INLINE_VISIBILITY 746bool 747operator< (const set<_Key, _Compare, _Allocator>& __x, 748 const set<_Key, _Compare, _Allocator>& __y) 749{ 750 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 751} 752 753template <class _Key, class _Compare, class _Allocator> 754inline _LIBCPP_INLINE_VISIBILITY 755bool 756operator!=(const set<_Key, _Compare, _Allocator>& __x, 757 const set<_Key, _Compare, _Allocator>& __y) 758{ 759 return !(__x == __y); 760} 761 762template <class _Key, class _Compare, class _Allocator> 763inline _LIBCPP_INLINE_VISIBILITY 764bool 765operator> (const set<_Key, _Compare, _Allocator>& __x, 766 const set<_Key, _Compare, _Allocator>& __y) 767{ 768 return __y < __x; 769} 770 771template <class _Key, class _Compare, class _Allocator> 772inline _LIBCPP_INLINE_VISIBILITY 773bool 774operator>=(const set<_Key, _Compare, _Allocator>& __x, 775 const set<_Key, _Compare, _Allocator>& __y) 776{ 777 return !(__x < __y); 778} 779 780template <class _Key, class _Compare, class _Allocator> 781inline _LIBCPP_INLINE_VISIBILITY 782bool 783operator<=(const set<_Key, _Compare, _Allocator>& __x, 784 const set<_Key, _Compare, _Allocator>& __y) 785{ 786 return !(__y < __x); 787} 788 789// specialized algorithms: 790template <class _Key, class _Compare, class _Allocator> 791inline _LIBCPP_INLINE_VISIBILITY 792void 793swap(set<_Key, _Compare, _Allocator>& __x, 794 set<_Key, _Compare, _Allocator>& __y) 795 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 796{ 797 __x.swap(__y); 798} 799 800template <class _Key, class _Compare = less<_Key>, 801 class _Allocator = allocator<_Key> > 802class _LIBCPP_TYPE_VIS_ONLY multiset 803{ 804public: 805 // types: 806 typedef _Key key_type; 807 typedef key_type value_type; 808 typedef _Compare key_compare; 809 typedef key_compare value_compare; 810 typedef _Allocator allocator_type; 811 typedef value_type& reference; 812 typedef const value_type& const_reference; 813 814private: 815 typedef __tree<value_type, value_compare, allocator_type> __base; 816 typedef allocator_traits<allocator_type> __alloc_traits; 817 typedef typename __base::__node_holder __node_holder; 818 819 __base __tree_; 820 821public: 822 typedef typename __base::pointer pointer; 823 typedef typename __base::const_pointer const_pointer; 824 typedef typename __base::size_type size_type; 825 typedef typename __base::difference_type difference_type; 826 typedef typename __base::const_iterator iterator; 827 typedef typename __base::const_iterator const_iterator; 828 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 829 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 830 831 // construct/copy/destroy: 832 _LIBCPP_INLINE_VISIBILITY 833 multiset() 834 _NOEXCEPT_( 835 is_nothrow_default_constructible<allocator_type>::value && 836 is_nothrow_default_constructible<key_compare>::value && 837 is_nothrow_copy_constructible<key_compare>::value) 838 : __tree_(value_compare()) {} 839 840 _LIBCPP_INLINE_VISIBILITY 841 explicit multiset(const value_compare& __comp) 842 _NOEXCEPT_( 843 is_nothrow_default_constructible<allocator_type>::value && 844 is_nothrow_copy_constructible<key_compare>::value) 845 : __tree_(__comp) {} 846 847 _LIBCPP_INLINE_VISIBILITY 848 explicit multiset(const value_compare& __comp, const allocator_type& __a) 849 : __tree_(__comp, __a) {} 850 template <class _InputIterator> 851 _LIBCPP_INLINE_VISIBILITY 852 multiset(_InputIterator __f, _InputIterator __l, 853 const value_compare& __comp = value_compare()) 854 : __tree_(__comp) 855 { 856 insert(__f, __l); 857 } 858 859#if _LIBCPP_STD_VER > 11 860 template <class _InputIterator> 861 _LIBCPP_INLINE_VISIBILITY 862 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 863 : multiset(__f, __l, key_compare(), __a) {} 864#endif 865 866 template <class _InputIterator> 867 _LIBCPP_INLINE_VISIBILITY 868 multiset(_InputIterator __f, _InputIterator __l, 869 const value_compare& __comp, const allocator_type& __a) 870 : __tree_(__comp, __a) 871 { 872 insert(__f, __l); 873 } 874 875 _LIBCPP_INLINE_VISIBILITY 876 multiset(const multiset& __s) 877 : __tree_(__s.__tree_.value_comp(), 878 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 879 { 880 insert(__s.begin(), __s.end()); 881 } 882 883 _LIBCPP_INLINE_VISIBILITY 884 multiset& operator=(const multiset& __s) 885 { 886 __tree_ = __s.__tree_; 887 return *this; 888 } 889 890#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 891 _LIBCPP_INLINE_VISIBILITY 892 multiset(multiset&& __s) 893 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 894 : __tree_(_VSTD::move(__s.__tree_)) {} 895#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 896 _LIBCPP_INLINE_VISIBILITY 897 explicit multiset(const allocator_type& __a) 898 : __tree_(__a) {} 899 _LIBCPP_INLINE_VISIBILITY 900 multiset(const multiset& __s, const allocator_type& __a) 901 : __tree_(__s.__tree_.value_comp(), __a) 902 { 903 insert(__s.begin(), __s.end()); 904 } 905#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 906 multiset(multiset&& __s, const allocator_type& __a); 907#endif 908 909#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 910 _LIBCPP_INLINE_VISIBILITY 911 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 912 : __tree_(__comp) 913 { 914 insert(__il.begin(), __il.end()); 915 } 916 917 _LIBCPP_INLINE_VISIBILITY 918 multiset(initializer_list<value_type> __il, const value_compare& __comp, 919 const allocator_type& __a) 920 : __tree_(__comp, __a) 921 { 922 insert(__il.begin(), __il.end()); 923 } 924 925#if _LIBCPP_STD_VER > 11 926 _LIBCPP_INLINE_VISIBILITY 927 multiset(initializer_list<value_type> __il, const allocator_type& __a) 928 : multiset(__il, key_compare(), __a) {} 929#endif 930 931 _LIBCPP_INLINE_VISIBILITY 932 multiset& operator=(initializer_list<value_type> __il) 933 { 934 __tree_.__assign_multi(__il.begin(), __il.end()); 935 return *this; 936 } 937#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 938 939#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 940 _LIBCPP_INLINE_VISIBILITY 941 multiset& operator=(multiset&& __s) 942 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 943 { 944 __tree_ = _VSTD::move(__s.__tree_); 945 return *this; 946 } 947#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 948 949 _LIBCPP_INLINE_VISIBILITY 950 iterator begin() _NOEXCEPT {return __tree_.begin();} 951 _LIBCPP_INLINE_VISIBILITY 952 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 953 _LIBCPP_INLINE_VISIBILITY 954 iterator end() _NOEXCEPT {return __tree_.end();} 955 _LIBCPP_INLINE_VISIBILITY 956 const_iterator end() const _NOEXCEPT {return __tree_.end();} 957 958 _LIBCPP_INLINE_VISIBILITY 959 reverse_iterator rbegin() _NOEXCEPT 960 {return reverse_iterator(end());} 961 _LIBCPP_INLINE_VISIBILITY 962 const_reverse_iterator rbegin() const _NOEXCEPT 963 {return const_reverse_iterator(end());} 964 _LIBCPP_INLINE_VISIBILITY 965 reverse_iterator rend() _NOEXCEPT 966 {return reverse_iterator(begin());} 967 _LIBCPP_INLINE_VISIBILITY 968 const_reverse_iterator rend() const _NOEXCEPT 969 {return const_reverse_iterator(begin());} 970 971 _LIBCPP_INLINE_VISIBILITY 972 const_iterator cbegin() const _NOEXCEPT {return begin();} 973 _LIBCPP_INLINE_VISIBILITY 974 const_iterator cend() const _NOEXCEPT {return end();} 975 _LIBCPP_INLINE_VISIBILITY 976 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 977 _LIBCPP_INLINE_VISIBILITY 978 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 979 980 _LIBCPP_INLINE_VISIBILITY 981 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 982 _LIBCPP_INLINE_VISIBILITY 983 size_type size() const _NOEXCEPT {return __tree_.size();} 984 _LIBCPP_INLINE_VISIBILITY 985 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 986 987 // modifiers: 988#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 989 template <class... _Args> 990 _LIBCPP_INLINE_VISIBILITY 991 iterator emplace(_Args&&... __args) 992 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 993 template <class... _Args> 994 _LIBCPP_INLINE_VISIBILITY 995 iterator emplace_hint(const_iterator __p, _Args&&... __args) 996 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 997#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 998 _LIBCPP_INLINE_VISIBILITY 999 iterator insert(const value_type& __v) 1000 {return __tree_.__insert_multi(__v);} 1001#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1002 _LIBCPP_INLINE_VISIBILITY 1003 iterator insert(value_type&& __v) 1004 {return __tree_.__insert_multi(_VSTD::move(__v));} 1005#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1006 _LIBCPP_INLINE_VISIBILITY 1007 iterator insert(const_iterator __p, const value_type& __v) 1008 {return __tree_.__insert_multi(__p, __v);} 1009#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1010 _LIBCPP_INLINE_VISIBILITY 1011 iterator insert(const_iterator __p, value_type&& __v) 1012 {return __tree_.__insert_multi(_VSTD::move(__v));} 1013#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1014 template <class _InputIterator> 1015 _LIBCPP_INLINE_VISIBILITY 1016 void insert(_InputIterator __f, _InputIterator __l) 1017 { 1018 for (const_iterator __e = cend(); __f != __l; ++__f) 1019 __tree_.__insert_multi(__e, *__f); 1020 } 1021 1022#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1023 _LIBCPP_INLINE_VISIBILITY 1024 void insert(initializer_list<value_type> __il) 1025 {insert(__il.begin(), __il.end());} 1026#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1027 1028 _LIBCPP_INLINE_VISIBILITY 1029 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1030 _LIBCPP_INLINE_VISIBILITY 1031 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1032 _LIBCPP_INLINE_VISIBILITY 1033 iterator erase(const_iterator __f, const_iterator __l) 1034 {return __tree_.erase(__f, __l);} 1035 _LIBCPP_INLINE_VISIBILITY 1036 void clear() _NOEXCEPT {__tree_.clear();} 1037 1038 _LIBCPP_INLINE_VISIBILITY 1039 void swap(multiset& __s) 1040 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1041 {__tree_.swap(__s.__tree_);} 1042 1043 _LIBCPP_INLINE_VISIBILITY 1044 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1045 _LIBCPP_INLINE_VISIBILITY 1046 key_compare key_comp() const {return __tree_.value_comp();} 1047 _LIBCPP_INLINE_VISIBILITY 1048 value_compare value_comp() const {return __tree_.value_comp();} 1049 1050 // set operations: 1051 _LIBCPP_INLINE_VISIBILITY 1052 iterator find(const key_type& __k) {return __tree_.find(__k);} 1053 _LIBCPP_INLINE_VISIBILITY 1054 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1055#if _LIBCPP_STD_VER > 11 1056 template <typename _K2> 1057 _LIBCPP_INLINE_VISIBILITY 1058 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1059 find(const _K2& __k) {return __tree_.find(__k);} 1060 template <typename _K2> 1061 _LIBCPP_INLINE_VISIBILITY 1062 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1063 find(const _K2& __k) const {return __tree_.find(__k);} 1064#endif 1065 1066 _LIBCPP_INLINE_VISIBILITY 1067 size_type count(const key_type& __k) const 1068 {return __tree_.__count_multi(__k);} 1069 1070 _LIBCPP_INLINE_VISIBILITY 1071 iterator lower_bound(const key_type& __k) 1072 {return __tree_.lower_bound(__k);} 1073 _LIBCPP_INLINE_VISIBILITY 1074 const_iterator lower_bound(const key_type& __k) const 1075 {return __tree_.lower_bound(__k);} 1076#if _LIBCPP_STD_VER > 11 1077 template <typename _K2> 1078 _LIBCPP_INLINE_VISIBILITY 1079 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1080 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1081 1082 template <typename _K2> 1083 _LIBCPP_INLINE_VISIBILITY 1084 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1085 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1086#endif 1087 1088 _LIBCPP_INLINE_VISIBILITY 1089 iterator upper_bound(const key_type& __k) 1090 {return __tree_.upper_bound(__k);} 1091 _LIBCPP_INLINE_VISIBILITY 1092 const_iterator upper_bound(const key_type& __k) const 1093 {return __tree_.upper_bound(__k);} 1094#if _LIBCPP_STD_VER > 11 1095 template <typename _K2> 1096 _LIBCPP_INLINE_VISIBILITY 1097 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1098 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1099 template <typename _K2> 1100 _LIBCPP_INLINE_VISIBILITY 1101 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1102 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1103#endif 1104 1105 _LIBCPP_INLINE_VISIBILITY 1106 pair<iterator,iterator> equal_range(const key_type& __k) 1107 {return __tree_.__equal_range_multi(__k);} 1108 _LIBCPP_INLINE_VISIBILITY 1109 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1110 {return __tree_.__equal_range_multi(__k);} 1111#if _LIBCPP_STD_VER > 11 1112 template <typename _K2> 1113 _LIBCPP_INLINE_VISIBILITY 1114 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1115 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1116 template <typename _K2> 1117 _LIBCPP_INLINE_VISIBILITY 1118 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1119 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1120#endif 1121}; 1122 1123#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1124 1125template <class _Key, class _Compare, class _Allocator> 1126multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1127 : __tree_(_VSTD::move(__s.__tree_), __a) 1128{ 1129 if (__a != __s.get_allocator()) 1130 { 1131 const_iterator __e = cend(); 1132 while (!__s.empty()) 1133 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1134 } 1135} 1136 1137#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1138 1139template <class _Key, class _Compare, class _Allocator> 1140inline _LIBCPP_INLINE_VISIBILITY 1141bool 1142operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1143 const multiset<_Key, _Compare, _Allocator>& __y) 1144{ 1145 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1146} 1147 1148template <class _Key, class _Compare, class _Allocator> 1149inline _LIBCPP_INLINE_VISIBILITY 1150bool 1151operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1152 const multiset<_Key, _Compare, _Allocator>& __y) 1153{ 1154 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1155} 1156 1157template <class _Key, class _Compare, class _Allocator> 1158inline _LIBCPP_INLINE_VISIBILITY 1159bool 1160operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1161 const multiset<_Key, _Compare, _Allocator>& __y) 1162{ 1163 return !(__x == __y); 1164} 1165 1166template <class _Key, class _Compare, class _Allocator> 1167inline _LIBCPP_INLINE_VISIBILITY 1168bool 1169operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1170 const multiset<_Key, _Compare, _Allocator>& __y) 1171{ 1172 return __y < __x; 1173} 1174 1175template <class _Key, class _Compare, class _Allocator> 1176inline _LIBCPP_INLINE_VISIBILITY 1177bool 1178operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1179 const multiset<_Key, _Compare, _Allocator>& __y) 1180{ 1181 return !(__x < __y); 1182} 1183 1184template <class _Key, class _Compare, class _Allocator> 1185inline _LIBCPP_INLINE_VISIBILITY 1186bool 1187operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1188 const multiset<_Key, _Compare, _Allocator>& __y) 1189{ 1190 return !(__y < __x); 1191} 1192 1193template <class _Key, class _Compare, class _Allocator> 1194inline _LIBCPP_INLINE_VISIBILITY 1195void 1196swap(multiset<_Key, _Compare, _Allocator>& __x, 1197 multiset<_Key, _Compare, _Allocator>& __y) 1198 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1199{ 1200 __x.swap(__y); 1201} 1202 1203_LIBCPP_END_NAMESPACE_STD 1204 1205#endif // _LIBCPP_SET 1206