set revision 278724
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#if _LIBCPP_STD_VER > 11 667 template <typename _K2> 668 _LIBCPP_INLINE_VISIBILITY 669 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 670 count(const _K2& __k) {return __tree_.__count_unique(__k);} 671#endif 672 _LIBCPP_INLINE_VISIBILITY 673 iterator lower_bound(const key_type& __k) 674 {return __tree_.lower_bound(__k);} 675 _LIBCPP_INLINE_VISIBILITY 676 const_iterator lower_bound(const key_type& __k) const 677 {return __tree_.lower_bound(__k);} 678#if _LIBCPP_STD_VER > 11 679 template <typename _K2> 680 _LIBCPP_INLINE_VISIBILITY 681 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 682 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 683 684 template <typename _K2> 685 _LIBCPP_INLINE_VISIBILITY 686 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 687 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 688#endif 689 690 _LIBCPP_INLINE_VISIBILITY 691 iterator upper_bound(const key_type& __k) 692 {return __tree_.upper_bound(__k);} 693 _LIBCPP_INLINE_VISIBILITY 694 const_iterator upper_bound(const key_type& __k) const 695 {return __tree_.upper_bound(__k);} 696#if _LIBCPP_STD_VER > 11 697 template <typename _K2> 698 _LIBCPP_INLINE_VISIBILITY 699 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 700 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 701 template <typename _K2> 702 _LIBCPP_INLINE_VISIBILITY 703 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 704 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 705#endif 706 707 _LIBCPP_INLINE_VISIBILITY 708 pair<iterator,iterator> equal_range(const key_type& __k) 709 {return __tree_.__equal_range_unique(__k);} 710 _LIBCPP_INLINE_VISIBILITY 711 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 712 {return __tree_.__equal_range_unique(__k);} 713#if _LIBCPP_STD_VER > 11 714 template <typename _K2> 715 _LIBCPP_INLINE_VISIBILITY 716 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 717 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 718 template <typename _K2> 719 _LIBCPP_INLINE_VISIBILITY 720 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 721 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 722#endif 723}; 724 725#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 726 727template <class _Key, class _Compare, class _Allocator> 728set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 729 : __tree_(_VSTD::move(__s.__tree_), __a) 730{ 731 if (__a != __s.get_allocator()) 732 { 733 const_iterator __e = cend(); 734 while (!__s.empty()) 735 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 736 } 737} 738 739#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 740 741template <class _Key, class _Compare, class _Allocator> 742inline _LIBCPP_INLINE_VISIBILITY 743bool 744operator==(const set<_Key, _Compare, _Allocator>& __x, 745 const set<_Key, _Compare, _Allocator>& __y) 746{ 747 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 748} 749 750template <class _Key, class _Compare, class _Allocator> 751inline _LIBCPP_INLINE_VISIBILITY 752bool 753operator< (const set<_Key, _Compare, _Allocator>& __x, 754 const set<_Key, _Compare, _Allocator>& __y) 755{ 756 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 757} 758 759template <class _Key, class _Compare, class _Allocator> 760inline _LIBCPP_INLINE_VISIBILITY 761bool 762operator!=(const set<_Key, _Compare, _Allocator>& __x, 763 const set<_Key, _Compare, _Allocator>& __y) 764{ 765 return !(__x == __y); 766} 767 768template <class _Key, class _Compare, class _Allocator> 769inline _LIBCPP_INLINE_VISIBILITY 770bool 771operator> (const set<_Key, _Compare, _Allocator>& __x, 772 const set<_Key, _Compare, _Allocator>& __y) 773{ 774 return __y < __x; 775} 776 777template <class _Key, class _Compare, class _Allocator> 778inline _LIBCPP_INLINE_VISIBILITY 779bool 780operator>=(const set<_Key, _Compare, _Allocator>& __x, 781 const set<_Key, _Compare, _Allocator>& __y) 782{ 783 return !(__x < __y); 784} 785 786template <class _Key, class _Compare, class _Allocator> 787inline _LIBCPP_INLINE_VISIBILITY 788bool 789operator<=(const set<_Key, _Compare, _Allocator>& __x, 790 const set<_Key, _Compare, _Allocator>& __y) 791{ 792 return !(__y < __x); 793} 794 795// specialized algorithms: 796template <class _Key, class _Compare, class _Allocator> 797inline _LIBCPP_INLINE_VISIBILITY 798void 799swap(set<_Key, _Compare, _Allocator>& __x, 800 set<_Key, _Compare, _Allocator>& __y) 801 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 802{ 803 __x.swap(__y); 804} 805 806template <class _Key, class _Compare = less<_Key>, 807 class _Allocator = allocator<_Key> > 808class _LIBCPP_TYPE_VIS_ONLY multiset 809{ 810public: 811 // types: 812 typedef _Key key_type; 813 typedef key_type value_type; 814 typedef _Compare key_compare; 815 typedef key_compare value_compare; 816 typedef _Allocator allocator_type; 817 typedef value_type& reference; 818 typedef const value_type& const_reference; 819 820private: 821 typedef __tree<value_type, value_compare, allocator_type> __base; 822 typedef allocator_traits<allocator_type> __alloc_traits; 823 typedef typename __base::__node_holder __node_holder; 824 825 __base __tree_; 826 827public: 828 typedef typename __base::pointer pointer; 829 typedef typename __base::const_pointer const_pointer; 830 typedef typename __base::size_type size_type; 831 typedef typename __base::difference_type difference_type; 832 typedef typename __base::const_iterator iterator; 833 typedef typename __base::const_iterator const_iterator; 834 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 835 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 836 837 // construct/copy/destroy: 838 _LIBCPP_INLINE_VISIBILITY 839 multiset() 840 _NOEXCEPT_( 841 is_nothrow_default_constructible<allocator_type>::value && 842 is_nothrow_default_constructible<key_compare>::value && 843 is_nothrow_copy_constructible<key_compare>::value) 844 : __tree_(value_compare()) {} 845 846 _LIBCPP_INLINE_VISIBILITY 847 explicit multiset(const value_compare& __comp) 848 _NOEXCEPT_( 849 is_nothrow_default_constructible<allocator_type>::value && 850 is_nothrow_copy_constructible<key_compare>::value) 851 : __tree_(__comp) {} 852 853 _LIBCPP_INLINE_VISIBILITY 854 explicit multiset(const value_compare& __comp, const allocator_type& __a) 855 : __tree_(__comp, __a) {} 856 template <class _InputIterator> 857 _LIBCPP_INLINE_VISIBILITY 858 multiset(_InputIterator __f, _InputIterator __l, 859 const value_compare& __comp = value_compare()) 860 : __tree_(__comp) 861 { 862 insert(__f, __l); 863 } 864 865#if _LIBCPP_STD_VER > 11 866 template <class _InputIterator> 867 _LIBCPP_INLINE_VISIBILITY 868 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 869 : multiset(__f, __l, key_compare(), __a) {} 870#endif 871 872 template <class _InputIterator> 873 _LIBCPP_INLINE_VISIBILITY 874 multiset(_InputIterator __f, _InputIterator __l, 875 const value_compare& __comp, const allocator_type& __a) 876 : __tree_(__comp, __a) 877 { 878 insert(__f, __l); 879 } 880 881 _LIBCPP_INLINE_VISIBILITY 882 multiset(const multiset& __s) 883 : __tree_(__s.__tree_.value_comp(), 884 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 885 { 886 insert(__s.begin(), __s.end()); 887 } 888 889 _LIBCPP_INLINE_VISIBILITY 890 multiset& operator=(const multiset& __s) 891 { 892 __tree_ = __s.__tree_; 893 return *this; 894 } 895 896#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 897 _LIBCPP_INLINE_VISIBILITY 898 multiset(multiset&& __s) 899 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 900 : __tree_(_VSTD::move(__s.__tree_)) {} 901#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 902 _LIBCPP_INLINE_VISIBILITY 903 explicit multiset(const allocator_type& __a) 904 : __tree_(__a) {} 905 _LIBCPP_INLINE_VISIBILITY 906 multiset(const multiset& __s, const allocator_type& __a) 907 : __tree_(__s.__tree_.value_comp(), __a) 908 { 909 insert(__s.begin(), __s.end()); 910 } 911#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 912 multiset(multiset&& __s, const allocator_type& __a); 913#endif 914 915#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 916 _LIBCPP_INLINE_VISIBILITY 917 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 918 : __tree_(__comp) 919 { 920 insert(__il.begin(), __il.end()); 921 } 922 923 _LIBCPP_INLINE_VISIBILITY 924 multiset(initializer_list<value_type> __il, const value_compare& __comp, 925 const allocator_type& __a) 926 : __tree_(__comp, __a) 927 { 928 insert(__il.begin(), __il.end()); 929 } 930 931#if _LIBCPP_STD_VER > 11 932 _LIBCPP_INLINE_VISIBILITY 933 multiset(initializer_list<value_type> __il, const allocator_type& __a) 934 : multiset(__il, key_compare(), __a) {} 935#endif 936 937 _LIBCPP_INLINE_VISIBILITY 938 multiset& operator=(initializer_list<value_type> __il) 939 { 940 __tree_.__assign_multi(__il.begin(), __il.end()); 941 return *this; 942 } 943#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 944 945#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 946 _LIBCPP_INLINE_VISIBILITY 947 multiset& operator=(multiset&& __s) 948 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 949 { 950 __tree_ = _VSTD::move(__s.__tree_); 951 return *this; 952 } 953#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 954 955 _LIBCPP_INLINE_VISIBILITY 956 iterator begin() _NOEXCEPT {return __tree_.begin();} 957 _LIBCPP_INLINE_VISIBILITY 958 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 959 _LIBCPP_INLINE_VISIBILITY 960 iterator end() _NOEXCEPT {return __tree_.end();} 961 _LIBCPP_INLINE_VISIBILITY 962 const_iterator end() const _NOEXCEPT {return __tree_.end();} 963 964 _LIBCPP_INLINE_VISIBILITY 965 reverse_iterator rbegin() _NOEXCEPT 966 {return reverse_iterator(end());} 967 _LIBCPP_INLINE_VISIBILITY 968 const_reverse_iterator rbegin() const _NOEXCEPT 969 {return const_reverse_iterator(end());} 970 _LIBCPP_INLINE_VISIBILITY 971 reverse_iterator rend() _NOEXCEPT 972 {return reverse_iterator(begin());} 973 _LIBCPP_INLINE_VISIBILITY 974 const_reverse_iterator rend() const _NOEXCEPT 975 {return const_reverse_iterator(begin());} 976 977 _LIBCPP_INLINE_VISIBILITY 978 const_iterator cbegin() const _NOEXCEPT {return begin();} 979 _LIBCPP_INLINE_VISIBILITY 980 const_iterator cend() const _NOEXCEPT {return end();} 981 _LIBCPP_INLINE_VISIBILITY 982 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 983 _LIBCPP_INLINE_VISIBILITY 984 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 985 986 _LIBCPP_INLINE_VISIBILITY 987 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 988 _LIBCPP_INLINE_VISIBILITY 989 size_type size() const _NOEXCEPT {return __tree_.size();} 990 _LIBCPP_INLINE_VISIBILITY 991 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 992 993 // modifiers: 994#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 995 template <class... _Args> 996 _LIBCPP_INLINE_VISIBILITY 997 iterator emplace(_Args&&... __args) 998 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 999 template <class... _Args> 1000 _LIBCPP_INLINE_VISIBILITY 1001 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1002 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1003#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1004 _LIBCPP_INLINE_VISIBILITY 1005 iterator insert(const value_type& __v) 1006 {return __tree_.__insert_multi(__v);} 1007#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1008 _LIBCPP_INLINE_VISIBILITY 1009 iterator insert(value_type&& __v) 1010 {return __tree_.__insert_multi(_VSTD::move(__v));} 1011#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1012 _LIBCPP_INLINE_VISIBILITY 1013 iterator insert(const_iterator __p, const value_type& __v) 1014 {return __tree_.__insert_multi(__p, __v);} 1015#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1016 _LIBCPP_INLINE_VISIBILITY 1017 iterator insert(const_iterator __p, value_type&& __v) 1018 {return __tree_.__insert_multi(_VSTD::move(__v));} 1019#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020 template <class _InputIterator> 1021 _LIBCPP_INLINE_VISIBILITY 1022 void insert(_InputIterator __f, _InputIterator __l) 1023 { 1024 for (const_iterator __e = cend(); __f != __l; ++__f) 1025 __tree_.__insert_multi(__e, *__f); 1026 } 1027 1028#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1029 _LIBCPP_INLINE_VISIBILITY 1030 void insert(initializer_list<value_type> __il) 1031 {insert(__il.begin(), __il.end());} 1032#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1033 1034 _LIBCPP_INLINE_VISIBILITY 1035 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1036 _LIBCPP_INLINE_VISIBILITY 1037 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1038 _LIBCPP_INLINE_VISIBILITY 1039 iterator erase(const_iterator __f, const_iterator __l) 1040 {return __tree_.erase(__f, __l);} 1041 _LIBCPP_INLINE_VISIBILITY 1042 void clear() _NOEXCEPT {__tree_.clear();} 1043 1044 _LIBCPP_INLINE_VISIBILITY 1045 void swap(multiset& __s) 1046 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1047 {__tree_.swap(__s.__tree_);} 1048 1049 _LIBCPP_INLINE_VISIBILITY 1050 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1051 _LIBCPP_INLINE_VISIBILITY 1052 key_compare key_comp() const {return __tree_.value_comp();} 1053 _LIBCPP_INLINE_VISIBILITY 1054 value_compare value_comp() const {return __tree_.value_comp();} 1055 1056 // set operations: 1057 _LIBCPP_INLINE_VISIBILITY 1058 iterator find(const key_type& __k) {return __tree_.find(__k);} 1059 _LIBCPP_INLINE_VISIBILITY 1060 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1061#if _LIBCPP_STD_VER > 11 1062 template <typename _K2> 1063 _LIBCPP_INLINE_VISIBILITY 1064 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1065 find(const _K2& __k) {return __tree_.find(__k);} 1066 template <typename _K2> 1067 _LIBCPP_INLINE_VISIBILITY 1068 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1069 find(const _K2& __k) const {return __tree_.find(__k);} 1070#endif 1071 1072 _LIBCPP_INLINE_VISIBILITY 1073 size_type count(const key_type& __k) const 1074 {return __tree_.__count_multi(__k);} 1075#if _LIBCPP_STD_VER > 11 1076 template <typename _K2> 1077 _LIBCPP_INLINE_VISIBILITY 1078 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1079 count(const _K2& __k) {return __tree_.__count_multi(__k);} 1080#endif 1081 1082 _LIBCPP_INLINE_VISIBILITY 1083 iterator lower_bound(const key_type& __k) 1084 {return __tree_.lower_bound(__k);} 1085 _LIBCPP_INLINE_VISIBILITY 1086 const_iterator lower_bound(const key_type& __k) const 1087 {return __tree_.lower_bound(__k);} 1088#if _LIBCPP_STD_VER > 11 1089 template <typename _K2> 1090 _LIBCPP_INLINE_VISIBILITY 1091 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1092 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1093 1094 template <typename _K2> 1095 _LIBCPP_INLINE_VISIBILITY 1096 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1097 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1098#endif 1099 1100 _LIBCPP_INLINE_VISIBILITY 1101 iterator upper_bound(const key_type& __k) 1102 {return __tree_.upper_bound(__k);} 1103 _LIBCPP_INLINE_VISIBILITY 1104 const_iterator upper_bound(const key_type& __k) const 1105 {return __tree_.upper_bound(__k);} 1106#if _LIBCPP_STD_VER > 11 1107 template <typename _K2> 1108 _LIBCPP_INLINE_VISIBILITY 1109 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1110 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1111 template <typename _K2> 1112 _LIBCPP_INLINE_VISIBILITY 1113 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1114 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1115#endif 1116 1117 _LIBCPP_INLINE_VISIBILITY 1118 pair<iterator,iterator> equal_range(const key_type& __k) 1119 {return __tree_.__equal_range_multi(__k);} 1120 _LIBCPP_INLINE_VISIBILITY 1121 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1122 {return __tree_.__equal_range_multi(__k);} 1123#if _LIBCPP_STD_VER > 11 1124 template <typename _K2> 1125 _LIBCPP_INLINE_VISIBILITY 1126 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1127 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1128 template <typename _K2> 1129 _LIBCPP_INLINE_VISIBILITY 1130 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1131 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1132#endif 1133}; 1134 1135#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1136 1137template <class _Key, class _Compare, class _Allocator> 1138multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1139 : __tree_(_VSTD::move(__s.__tree_), __a) 1140{ 1141 if (__a != __s.get_allocator()) 1142 { 1143 const_iterator __e = cend(); 1144 while (!__s.empty()) 1145 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1146 } 1147} 1148 1149#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1150 1151template <class _Key, class _Compare, class _Allocator> 1152inline _LIBCPP_INLINE_VISIBILITY 1153bool 1154operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1155 const multiset<_Key, _Compare, _Allocator>& __y) 1156{ 1157 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1158} 1159 1160template <class _Key, class _Compare, class _Allocator> 1161inline _LIBCPP_INLINE_VISIBILITY 1162bool 1163operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1164 const multiset<_Key, _Compare, _Allocator>& __y) 1165{ 1166 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1167} 1168 1169template <class _Key, class _Compare, class _Allocator> 1170inline _LIBCPP_INLINE_VISIBILITY 1171bool 1172operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1173 const multiset<_Key, _Compare, _Allocator>& __y) 1174{ 1175 return !(__x == __y); 1176} 1177 1178template <class _Key, class _Compare, class _Allocator> 1179inline _LIBCPP_INLINE_VISIBILITY 1180bool 1181operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1182 const multiset<_Key, _Compare, _Allocator>& __y) 1183{ 1184 return __y < __x; 1185} 1186 1187template <class _Key, class _Compare, class _Allocator> 1188inline _LIBCPP_INLINE_VISIBILITY 1189bool 1190operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1191 const multiset<_Key, _Compare, _Allocator>& __y) 1192{ 1193 return !(__x < __y); 1194} 1195 1196template <class _Key, class _Compare, class _Allocator> 1197inline _LIBCPP_INLINE_VISIBILITY 1198bool 1199operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1200 const multiset<_Key, _Compare, _Allocator>& __y) 1201{ 1202 return !(__y < __x); 1203} 1204 1205template <class _Key, class _Compare, class _Allocator> 1206inline _LIBCPP_INLINE_VISIBILITY 1207void 1208swap(multiset<_Key, _Compare, _Allocator>& __x, 1209 multiset<_Key, _Compare, _Allocator>& __y) 1210 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1211{ 1212 __x.swap(__y); 1213} 1214 1215_LIBCPP_END_NAMESPACE_STD 1216 1217#endif // _LIBCPP_SET 1218