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 18 namespace std 19 { 20 21 template <class Key, class Compare = less<Key>, 22 class Allocator = allocator<Key>> 23 class set 24 { 25 public: 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 167 template <class Key, class Compare, class Allocator> 168 bool 169 operator==(const set<Key, Compare, Allocator>& x, 170 const set<Key, Compare, Allocator>& y); 171 172 template <class Key, class Compare, class Allocator> 173 bool 174 operator< (const set<Key, Compare, Allocator>& x, 175 const set<Key, Compare, Allocator>& y); 176 177 template <class Key, class Compare, class Allocator> 178 bool 179 operator!=(const set<Key, Compare, Allocator>& x, 180 const set<Key, Compare, Allocator>& y); 181 182 template <class Key, class Compare, class Allocator> 183 bool 184 operator> (const set<Key, Compare, Allocator>& x, 185 const set<Key, Compare, Allocator>& y); 186 187 template <class Key, class Compare, class Allocator> 188 bool 189 operator>=(const set<Key, Compare, Allocator>& x, 190 const set<Key, Compare, Allocator>& y); 191 192 template <class Key, class Compare, class Allocator> 193 bool 194 operator<=(const set<Key, Compare, Allocator>& x, 195 const set<Key, Compare, Allocator>& y); 196 197 // specialized algorithms: 198 template <class Key, class Compare, class Allocator> 199 void 200 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 201 noexcept(noexcept(x.swap(y))); 202 203 template <class Key, class Compare = less<Key>, 204 class Allocator = allocator<Key>> 205 class multiset 206 { 207 public: 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 348 template <class Key, class Compare, class Allocator> 349 bool 350 operator==(const multiset<Key, Compare, Allocator>& x, 351 const multiset<Key, Compare, Allocator>& y); 352 353 template <class Key, class Compare, class Allocator> 354 bool 355 operator< (const multiset<Key, Compare, Allocator>& x, 356 const multiset<Key, Compare, Allocator>& y); 357 358 template <class Key, class Compare, class Allocator> 359 bool 360 operator!=(const multiset<Key, Compare, Allocator>& x, 361 const multiset<Key, Compare, Allocator>& y); 362 363 template <class Key, class Compare, class Allocator> 364 bool 365 operator> (const multiset<Key, Compare, Allocator>& x, 366 const multiset<Key, Compare, Allocator>& y); 367 368 template <class Key, class Compare, class Allocator> 369 bool 370 operator>=(const multiset<Key, Compare, Allocator>& x, 371 const multiset<Key, Compare, Allocator>& y); 372 373 template <class Key, class Compare, class Allocator> 374 bool 375 operator<=(const multiset<Key, Compare, Allocator>& x, 376 const multiset<Key, Compare, Allocator>& y); 377 378 // specialized algorithms: 379 template <class Key, class Compare, class Allocator> 380 void 381 swap(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 398 template <class _Key, class _Compare = less<_Key>, 399 class _Allocator = allocator<_Key> > 400 class _LIBCPP_TYPE_VIS_ONLY set 401 { 402 public: 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 412 private: 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 419 public: 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 729 template <class _Key, class _Compare, class _Allocator> 730 set<_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 743 template <class _Key, class _Compare, class _Allocator> 744 inline _LIBCPP_INLINE_VISIBILITY 745 bool 746 operator==(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 752 template <class _Key, class _Compare, class _Allocator> 753 inline _LIBCPP_INLINE_VISIBILITY 754 bool 755 operator< (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 761 template <class _Key, class _Compare, class _Allocator> 762 inline _LIBCPP_INLINE_VISIBILITY 763 bool 764 operator!=(const set<_Key, _Compare, _Allocator>& __x, 765 const set<_Key, _Compare, _Allocator>& __y) 766 { 767 return !(__x == __y); 768 } 769 770 template <class _Key, class _Compare, class _Allocator> 771 inline _LIBCPP_INLINE_VISIBILITY 772 bool 773 operator> (const set<_Key, _Compare, _Allocator>& __x, 774 const set<_Key, _Compare, _Allocator>& __y) 775 { 776 return __y < __x; 777 } 778 779 template <class _Key, class _Compare, class _Allocator> 780 inline _LIBCPP_INLINE_VISIBILITY 781 bool 782 operator>=(const set<_Key, _Compare, _Allocator>& __x, 783 const set<_Key, _Compare, _Allocator>& __y) 784 { 785 return !(__x < __y); 786 } 787 788 template <class _Key, class _Compare, class _Allocator> 789 inline _LIBCPP_INLINE_VISIBILITY 790 bool 791 operator<=(const set<_Key, _Compare, _Allocator>& __x, 792 const set<_Key, _Compare, _Allocator>& __y) 793 { 794 return !(__y < __x); 795 } 796 797 // specialized algorithms: 798 template <class _Key, class _Compare, class _Allocator> 799 inline _LIBCPP_INLINE_VISIBILITY 800 void 801 swap(set<_Key, _Compare, _Allocator>& __x, 802 set<_Key, _Compare, _Allocator>& __y) 803 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 804 { 805 __x.swap(__y); 806 } 807 808 template <class _Key, class _Compare = less<_Key>, 809 class _Allocator = allocator<_Key> > 810 class _LIBCPP_TYPE_VIS_ONLY multiset 811 { 812 public: 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 822 private: 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 829 public: 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 1139 template <class _Key, class _Compare, class _Allocator> 1140 multiset<_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 1153 template <class _Key, class _Compare, class _Allocator> 1154 inline _LIBCPP_INLINE_VISIBILITY 1155 bool 1156 operator==(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 1162 template <class _Key, class _Compare, class _Allocator> 1163 inline _LIBCPP_INLINE_VISIBILITY 1164 bool 1165 operator< (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 1171 template <class _Key, class _Compare, class _Allocator> 1172 inline _LIBCPP_INLINE_VISIBILITY 1173 bool 1174 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1175 const multiset<_Key, _Compare, _Allocator>& __y) 1176 { 1177 return !(__x == __y); 1178 } 1179 1180 template <class _Key, class _Compare, class _Allocator> 1181 inline _LIBCPP_INLINE_VISIBILITY 1182 bool 1183 operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1184 const multiset<_Key, _Compare, _Allocator>& __y) 1185 { 1186 return __y < __x; 1187 } 1188 1189 template <class _Key, class _Compare, class _Allocator> 1190 inline _LIBCPP_INLINE_VISIBILITY 1191 bool 1192 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1193 const multiset<_Key, _Compare, _Allocator>& __y) 1194 { 1195 return !(__x < __y); 1196 } 1197 1198 template <class _Key, class _Compare, class _Allocator> 1199 inline _LIBCPP_INLINE_VISIBILITY 1200 bool 1201 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1202 const multiset<_Key, _Compare, _Allocator>& __y) 1203 { 1204 return !(__y < __x); 1205 } 1206 1207 template <class _Key, class _Compare, class _Allocator> 1208 inline _LIBCPP_INLINE_VISIBILITY 1209 void 1210 swap(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
