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