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