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 ~set(); 70 71 set& operator=(const set& s); 72 set& operator=(set&& s) 73 noexcept( 74 allocator_type::propagate_on_container_move_assignment::value && 75 is_nothrow_move_assignable<allocator_type>::value && 76 is_nothrow_move_assignable<key_compare>::value); 77 set& operator=(initializer_list<value_type> il); 78 79 // iterators: 80 iterator begin() noexcept; 81 const_iterator begin() const noexcept; 82 iterator end() noexcept; 83 const_iterator end() const noexcept; 84 85 reverse_iterator rbegin() noexcept; 86 const_reverse_iterator rbegin() const noexcept; 87 reverse_iterator rend() noexcept; 88 const_reverse_iterator rend() const noexcept; 89 90 const_iterator cbegin() const noexcept; 91 const_iterator cend() const noexcept; 92 const_reverse_iterator crbegin() const noexcept; 93 const_reverse_iterator crend() const noexcept; 94 95 // capacity: 96 bool empty() const noexcept; 97 size_type size() const noexcept; 98 size_type max_size() const noexcept; 99 100 // modifiers: 101 template <class... Args> 102 pair<iterator, bool> emplace(Args&&... args); 103 template <class... Args> 104 iterator emplace_hint(const_iterator position, Args&&... args); 105 pair<iterator,bool> insert(const value_type& v); 106 pair<iterator,bool> insert(value_type&& v); 107 iterator insert(const_iterator position, const value_type& v); 108 iterator insert(const_iterator position, value_type&& v); 109 template <class InputIterator> 110 void insert(InputIterator first, InputIterator last); 111 void insert(initializer_list<value_type> il); 112 113 iterator erase(const_iterator position); 114 size_type erase(const key_type& k); 115 iterator erase(const_iterator first, const_iterator last); 116 void clear() noexcept; 117 118 void swap(set& s) 119 noexcept( 120 __is_nothrow_swappable<key_compare>::value && 121 (!allocator_type::propagate_on_container_swap::value || 122 __is_nothrow_swappable<allocator_type>::value)); 123 124 // observers: 125 allocator_type get_allocator() const noexcept; 126 key_compare key_comp() const; 127 value_compare value_comp() const; 128 129 // set operations: 130 iterator find(const key_type& k); 131 const_iterator find(const key_type& k) const; 132 size_type count(const key_type& k) const; 133 iterator lower_bound(const key_type& k); 134 const_iterator lower_bound(const key_type& k) const; 135 iterator upper_bound(const key_type& k); 136 const_iterator upper_bound(const key_type& k) const; 137 pair<iterator,iterator> equal_range(const key_type& k); 138 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 139}; 140 141template <class Key, class Compare, class Allocator> 142bool 143operator==(const set<Key, Compare, Allocator>& x, 144 const set<Key, Compare, Allocator>& y); 145 146template <class Key, class Compare, class Allocator> 147bool 148operator< (const set<Key, Compare, Allocator>& x, 149 const set<Key, Compare, Allocator>& y); 150 151template <class Key, class Compare, class Allocator> 152bool 153operator!=(const set<Key, Compare, Allocator>& x, 154 const set<Key, Compare, Allocator>& y); 155 156template <class Key, class Compare, class Allocator> 157bool 158operator> (const set<Key, Compare, Allocator>& x, 159 const set<Key, Compare, Allocator>& y); 160 161template <class Key, class Compare, class Allocator> 162bool 163operator>=(const set<Key, Compare, Allocator>& x, 164 const set<Key, Compare, Allocator>& y); 165 166template <class Key, class Compare, class Allocator> 167bool 168operator<=(const set<Key, Compare, Allocator>& x, 169 const set<Key, Compare, Allocator>& y); 170 171// specialized algorithms: 172template <class Key, class Compare, class Allocator> 173void 174swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 175 noexcept(noexcept(x.swap(y))); 176 177template <class Key, class Compare = less<Key>, 178 class Allocator = allocator<Key>> 179class multiset 180{ 181public: 182 // types: 183 typedef Key key_type; 184 typedef key_type value_type; 185 typedef Compare key_compare; 186 typedef key_compare value_compare; 187 typedef Allocator allocator_type; 188 typedef typename allocator_type::reference reference; 189 typedef typename allocator_type::const_reference const_reference; 190 typedef typename allocator_type::size_type size_type; 191 typedef typename allocator_type::difference_type difference_type; 192 typedef typename allocator_type::pointer pointer; 193 typedef typename allocator_type::const_pointer const_pointer; 194 195 typedef implementation-defined iterator; 196 typedef implementation-defined const_iterator; 197 typedef std::reverse_iterator<iterator> reverse_iterator; 198 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 199 200 // construct/copy/destroy: 201 multiset() 202 noexcept( 203 is_nothrow_default_constructible<allocator_type>::value && 204 is_nothrow_default_constructible<key_compare>::value && 205 is_nothrow_copy_constructible<key_compare>::value); 206 explicit multiset(const value_compare& comp); 207 multiset(const value_compare& comp, const allocator_type& a); 208 template <class InputIterator> 209 multiset(InputIterator first, InputIterator last, 210 const value_compare& comp = value_compare()); 211 template <class InputIterator> 212 multiset(InputIterator first, InputIterator last, 213 const value_compare& comp, const allocator_type& a); 214 multiset(const multiset& s); 215 multiset(multiset&& s) 216 noexcept( 217 is_nothrow_move_constructible<allocator_type>::value && 218 is_nothrow_move_constructible<key_compare>::value); 219 explicit multiset(const allocator_type& a); 220 multiset(const multiset& s, const allocator_type& a); 221 multiset(multiset&& s, const allocator_type& a); 222 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 223 multiset(initializer_list<value_type> il, const value_compare& comp, 224 const allocator_type& a); 225 ~multiset(); 226 227 multiset& operator=(const multiset& s); 228 multiset& operator=(multiset&& s) 229 noexcept( 230 allocator_type::propagate_on_container_move_assignment::value && 231 is_nothrow_move_assignable<allocator_type>::value && 232 is_nothrow_move_assignable<key_compare>::value); 233 multiset& operator=(initializer_list<value_type> il); 234 235 // iterators: 236 iterator begin() noexcept; 237 const_iterator begin() const noexcept; 238 iterator end() noexcept; 239 const_iterator end() const noexcept; 240 241 reverse_iterator rbegin() noexcept; 242 const_reverse_iterator rbegin() const noexcept; 243 reverse_iterator rend() noexcept; 244 const_reverse_iterator rend() const noexcept; 245 246 const_iterator cbegin() const noexcept; 247 const_iterator cend() const noexcept; 248 const_reverse_iterator crbegin() const noexcept; 249 const_reverse_iterator crend() const noexcept; 250 251 // capacity: 252 bool empty() const noexcept; 253 size_type size() const noexcept; 254 size_type max_size() const noexcept; 255 256 // modifiers: 257 template <class... Args> 258 iterator emplace(Args&&... args); 259 template <class... Args> 260 iterator emplace_hint(const_iterator position, Args&&... args); 261 iterator insert(const value_type& v); 262 iterator insert(value_type&& v); 263 iterator insert(const_iterator position, const value_type& v); 264 iterator insert(const_iterator position, value_type&& v); 265 template <class InputIterator> 266 void insert(InputIterator first, InputIterator last); 267 void insert(initializer_list<value_type> il); 268 269 iterator erase(const_iterator position); 270 size_type erase(const key_type& k); 271 iterator erase(const_iterator first, const_iterator last); 272 void clear() noexcept; 273 274 void swap(multiset& s) 275 noexcept( 276 __is_nothrow_swappable<key_compare>::value && 277 (!allocator_type::propagate_on_container_swap::value || 278 __is_nothrow_swappable<allocator_type>::value)); 279 280 // observers: 281 allocator_type get_allocator() const noexcept; 282 key_compare key_comp() const; 283 value_compare value_comp() const; 284 285 // set operations: 286 iterator find(const key_type& k); 287 const_iterator find(const key_type& k) const; 288 size_type count(const key_type& k) const; 289 iterator lower_bound(const key_type& k); 290 const_iterator lower_bound(const key_type& k) const; 291 iterator upper_bound(const key_type& k); 292 const_iterator upper_bound(const key_type& k) const; 293 pair<iterator,iterator> equal_range(const key_type& k); 294 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 295}; 296 297template <class Key, class Compare, class Allocator> 298bool 299operator==(const multiset<Key, Compare, Allocator>& x, 300 const multiset<Key, Compare, Allocator>& y); 301 302template <class Key, class Compare, class Allocator> 303bool 304operator< (const multiset<Key, Compare, Allocator>& x, 305 const multiset<Key, Compare, Allocator>& y); 306 307template <class Key, class Compare, class Allocator> 308bool 309operator!=(const multiset<Key, Compare, Allocator>& x, 310 const multiset<Key, Compare, Allocator>& y); 311 312template <class Key, class Compare, class Allocator> 313bool 314operator> (const multiset<Key, Compare, Allocator>& x, 315 const multiset<Key, Compare, Allocator>& y); 316 317template <class Key, class Compare, class Allocator> 318bool 319operator>=(const multiset<Key, Compare, Allocator>& x, 320 const multiset<Key, Compare, Allocator>& y); 321 322template <class Key, class Compare, class Allocator> 323bool 324operator<=(const multiset<Key, Compare, Allocator>& x, 325 const multiset<Key, Compare, Allocator>& y); 326 327// specialized algorithms: 328template <class Key, class Compare, class Allocator> 329void 330swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 331 noexcept(noexcept(x.swap(y))); 332 333} // std 334 335*/ 336 337#include <__config> 338#include <__tree> 339#include <functional> 340 341#pragma GCC system_header 342 343_LIBCPP_BEGIN_NAMESPACE_STD 344 345template <class _Key, class _Compare = less<_Key>, 346 class _Allocator = allocator<_Key> > 347class _LIBCPP_VISIBLE set 348{ 349public: 350 // types: 351 typedef _Key key_type; 352 typedef key_type value_type; 353 typedef _Compare key_compare; 354 typedef key_compare value_compare; 355 typedef _Allocator allocator_type; 356 typedef value_type& reference; 357 typedef const value_type& const_reference; 358 359private: 360 typedef __tree<value_type, value_compare, allocator_type> __base; 361 typedef allocator_traits<allocator_type> __alloc_traits; 362 typedef typename __base::__node_holder __node_holder; 363 364 __base __tree_; 365 366public: 367 typedef typename __base::pointer pointer; 368 typedef typename __base::const_pointer const_pointer; 369 typedef typename __base::size_type size_type; 370 typedef typename __base::difference_type difference_type; 371 typedef typename __base::const_iterator iterator; 372 typedef typename __base::const_iterator const_iterator; 373 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 374 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 375 376 _LIBCPP_INLINE_VISIBILITY 377 explicit set(const value_compare& __comp = value_compare()) 378 _NOEXCEPT_( 379 is_nothrow_default_constructible<allocator_type>::value && 380 is_nothrow_default_constructible<key_compare>::value && 381 is_nothrow_copy_constructible<key_compare>::value) 382 : __tree_(__comp) {} 383 _LIBCPP_INLINE_VISIBILITY 384 set(const value_compare& __comp, const allocator_type& __a) 385 : __tree_(__comp, __a) {} 386 template <class _InputIterator> 387 _LIBCPP_INLINE_VISIBILITY 388 set(_InputIterator __f, _InputIterator __l, 389 const value_compare& __comp = value_compare()) 390 : __tree_(__comp) 391 { 392 insert(__f, __l); 393 } 394 395 template <class _InputIterator> 396 _LIBCPP_INLINE_VISIBILITY 397 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 398 const allocator_type& __a) 399 : __tree_(__comp, __a) 400 { 401 insert(__f, __l); 402 } 403 404 _LIBCPP_INLINE_VISIBILITY 405 set(const set& __s) 406 : __tree_(__s.__tree_) 407 { 408 insert(__s.begin(), __s.end()); 409 } 410 411 _LIBCPP_INLINE_VISIBILITY 412 set& operator=(const set& __s) 413 { 414 __tree_ = __s.__tree_; 415 return *this; 416 } 417 418#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 419 _LIBCPP_INLINE_VISIBILITY 420 set(set&& __s) 421 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 422 : __tree_(_VSTD::move(__s.__tree_)) {} 423#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 424 425 _LIBCPP_INLINE_VISIBILITY 426 explicit set(const allocator_type& __a) 427 : __tree_(__a) {} 428 429 _LIBCPP_INLINE_VISIBILITY 430 set(const set& __s, const allocator_type& __a) 431 : __tree_(__s.__tree_.value_comp(), __a) 432 { 433 insert(__s.begin(), __s.end()); 434 } 435 436#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 437 set(set&& __s, const allocator_type& __a); 438#endif 439 440#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 441 _LIBCPP_INLINE_VISIBILITY 442 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 443 : __tree_(__comp) 444 { 445 insert(__il.begin(), __il.end()); 446 } 447 448 _LIBCPP_INLINE_VISIBILITY 449 set(initializer_list<value_type> __il, const value_compare& __comp, 450 const allocator_type& __a) 451 : __tree_(__comp, __a) 452 { 453 insert(__il.begin(), __il.end()); 454 } 455 456 _LIBCPP_INLINE_VISIBILITY 457 set& operator=(initializer_list<value_type> __il) 458 { 459 __tree_.__assign_unique(__il.begin(), __il.end()); 460 return *this; 461 } 462#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 463 464#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 465 _LIBCPP_INLINE_VISIBILITY 466 set& operator=(set&& __s) 467 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 468 { 469 __tree_ = _VSTD::move(__s.__tree_); 470 return *this; 471 } 472#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 473 474 _LIBCPP_INLINE_VISIBILITY 475 iterator begin() _NOEXCEPT {return __tree_.begin();} 476 _LIBCPP_INLINE_VISIBILITY 477 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 478 _LIBCPP_INLINE_VISIBILITY 479 iterator end() _NOEXCEPT {return __tree_.end();} 480 _LIBCPP_INLINE_VISIBILITY 481 const_iterator end() const _NOEXCEPT {return __tree_.end();} 482 483 _LIBCPP_INLINE_VISIBILITY 484 reverse_iterator rbegin() _NOEXCEPT 485 {return reverse_iterator(end());} 486 _LIBCPP_INLINE_VISIBILITY 487 const_reverse_iterator rbegin() const _NOEXCEPT 488 {return const_reverse_iterator(end());} 489 _LIBCPP_INLINE_VISIBILITY 490 reverse_iterator rend() _NOEXCEPT 491 {return reverse_iterator(begin());} 492 _LIBCPP_INLINE_VISIBILITY 493 const_reverse_iterator rend() const _NOEXCEPT 494 {return const_reverse_iterator(begin());} 495 496 _LIBCPP_INLINE_VISIBILITY 497 const_iterator cbegin() const _NOEXCEPT {return begin();} 498 _LIBCPP_INLINE_VISIBILITY 499 const_iterator cend() const _NOEXCEPT {return end();} 500 _LIBCPP_INLINE_VISIBILITY 501 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 502 _LIBCPP_INLINE_VISIBILITY 503 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 504 505 _LIBCPP_INLINE_VISIBILITY 506 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 507 _LIBCPP_INLINE_VISIBILITY 508 size_type size() const _NOEXCEPT {return __tree_.size();} 509 _LIBCPP_INLINE_VISIBILITY 510 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 511 512 // modifiers: 513#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 514 template <class... _Args> 515 _LIBCPP_INLINE_VISIBILITY 516 pair<iterator, bool> emplace(_Args&&... __args) 517 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 518 template <class... _Args> 519 _LIBCPP_INLINE_VISIBILITY 520 iterator emplace_hint(const_iterator __p, _Args&&... __args) 521 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 522#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 523 _LIBCPP_INLINE_VISIBILITY 524 pair<iterator,bool> insert(const value_type& __v) 525 {return __tree_.__insert_unique(__v);} 526#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 527 _LIBCPP_INLINE_VISIBILITY 528 pair<iterator,bool> insert(value_type&& __v) 529 {return __tree_.__insert_unique(_VSTD::move(__v));} 530#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 531 _LIBCPP_INLINE_VISIBILITY 532 iterator insert(const_iterator __p, const value_type& __v) 533 {return __tree_.__insert_unique(__p, __v);} 534#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 535 _LIBCPP_INLINE_VISIBILITY 536 iterator insert(const_iterator __p, value_type&& __v) 537 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 538#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 539 template <class _InputIterator> 540 _LIBCPP_INLINE_VISIBILITY 541 void insert(_InputIterator __f, _InputIterator __l) 542 { 543 for (const_iterator __e = cend(); __f != __l; ++__f) 544 __tree_.__insert_unique(__e, *__f); 545 } 546 547#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 548 _LIBCPP_INLINE_VISIBILITY 549 void insert(initializer_list<value_type> __il) 550 {insert(__il.begin(), __il.end());} 551#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 552 553 _LIBCPP_INLINE_VISIBILITY 554 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 555 _LIBCPP_INLINE_VISIBILITY 556 size_type erase(const key_type& __k) 557 {return __tree_.__erase_unique(__k);} 558 _LIBCPP_INLINE_VISIBILITY 559 iterator erase(const_iterator __f, const_iterator __l) 560 {return __tree_.erase(__f, __l);} 561 _LIBCPP_INLINE_VISIBILITY 562 void clear() _NOEXCEPT {__tree_.clear();} 563 564 _LIBCPP_INLINE_VISIBILITY 565 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 566 {__tree_.swap(__s.__tree_);} 567 568 _LIBCPP_INLINE_VISIBILITY 569 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 570 _LIBCPP_INLINE_VISIBILITY 571 key_compare key_comp() const {return __tree_.value_comp();} 572 _LIBCPP_INLINE_VISIBILITY 573 value_compare value_comp() const {return __tree_.value_comp();} 574 575 // set operations: 576 _LIBCPP_INLINE_VISIBILITY 577 iterator find(const key_type& __k) {return __tree_.find(__k);} 578 _LIBCPP_INLINE_VISIBILITY 579 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 580 _LIBCPP_INLINE_VISIBILITY 581 size_type count(const key_type& __k) const 582 {return __tree_.__count_unique(__k);} 583 _LIBCPP_INLINE_VISIBILITY 584 iterator lower_bound(const key_type& __k) 585 {return __tree_.lower_bound(__k);} 586 _LIBCPP_INLINE_VISIBILITY 587 const_iterator lower_bound(const key_type& __k) const 588 {return __tree_.lower_bound(__k);} 589 _LIBCPP_INLINE_VISIBILITY 590 iterator upper_bound(const key_type& __k) 591 {return __tree_.upper_bound(__k);} 592 _LIBCPP_INLINE_VISIBILITY 593 const_iterator upper_bound(const key_type& __k) const 594 {return __tree_.upper_bound(__k);} 595 _LIBCPP_INLINE_VISIBILITY 596 pair<iterator,iterator> equal_range(const key_type& __k) 597 {return __tree_.__equal_range_unique(__k);} 598 _LIBCPP_INLINE_VISIBILITY 599 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 600 {return __tree_.__equal_range_unique(__k);} 601}; 602 603#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 604 605template <class _Key, class _Compare, class _Allocator> 606set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 607 : __tree_(_VSTD::move(__s.__tree_), __a) 608{ 609 if (__a != __s.get_allocator()) 610 { 611 const_iterator __e = cend(); 612 while (!__s.empty()) 613 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 614 } 615} 616 617#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 618 619template <class _Key, class _Compare, class _Allocator> 620inline _LIBCPP_INLINE_VISIBILITY 621bool 622operator==(const set<_Key, _Compare, _Allocator>& __x, 623 const set<_Key, _Compare, _Allocator>& __y) 624{ 625 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 626} 627 628template <class _Key, class _Compare, class _Allocator> 629inline _LIBCPP_INLINE_VISIBILITY 630bool 631operator< (const set<_Key, _Compare, _Allocator>& __x, 632 const set<_Key, _Compare, _Allocator>& __y) 633{ 634 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 635} 636 637template <class _Key, class _Compare, class _Allocator> 638inline _LIBCPP_INLINE_VISIBILITY 639bool 640operator!=(const set<_Key, _Compare, _Allocator>& __x, 641 const set<_Key, _Compare, _Allocator>& __y) 642{ 643 return !(__x == __y); 644} 645 646template <class _Key, class _Compare, class _Allocator> 647inline _LIBCPP_INLINE_VISIBILITY 648bool 649operator> (const set<_Key, _Compare, _Allocator>& __x, 650 const set<_Key, _Compare, _Allocator>& __y) 651{ 652 return __y < __x; 653} 654 655template <class _Key, class _Compare, class _Allocator> 656inline _LIBCPP_INLINE_VISIBILITY 657bool 658operator>=(const set<_Key, _Compare, _Allocator>& __x, 659 const set<_Key, _Compare, _Allocator>& __y) 660{ 661 return !(__x < __y); 662} 663 664template <class _Key, class _Compare, class _Allocator> 665inline _LIBCPP_INLINE_VISIBILITY 666bool 667operator<=(const set<_Key, _Compare, _Allocator>& __x, 668 const set<_Key, _Compare, _Allocator>& __y) 669{ 670 return !(__y < __x); 671} 672 673// specialized algorithms: 674template <class _Key, class _Compare, class _Allocator> 675inline _LIBCPP_INLINE_VISIBILITY 676void 677swap(set<_Key, _Compare, _Allocator>& __x, 678 set<_Key, _Compare, _Allocator>& __y) 679 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 680{ 681 __x.swap(__y); 682} 683 684template <class _Key, class _Compare = less<_Key>, 685 class _Allocator = allocator<_Key> > 686class _LIBCPP_VISIBLE multiset 687{ 688public: 689 // types: 690 typedef _Key key_type; 691 typedef key_type value_type; 692 typedef _Compare key_compare; 693 typedef key_compare value_compare; 694 typedef _Allocator allocator_type; 695 typedef value_type& reference; 696 typedef const value_type& const_reference; 697 698private: 699 typedef __tree<value_type, value_compare, allocator_type> __base; 700 typedef allocator_traits<allocator_type> __alloc_traits; 701 typedef typename __base::__node_holder __node_holder; 702 703 __base __tree_; 704 705public: 706 typedef typename __base::pointer pointer; 707 typedef typename __base::const_pointer const_pointer; 708 typedef typename __base::size_type size_type; 709 typedef typename __base::difference_type difference_type; 710 typedef typename __base::const_iterator iterator; 711 typedef typename __base::const_iterator const_iterator; 712 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 713 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 714 715 // construct/copy/destroy: 716 _LIBCPP_INLINE_VISIBILITY 717 explicit multiset(const value_compare& __comp = value_compare()) 718 _NOEXCEPT_( 719 is_nothrow_default_constructible<allocator_type>::value && 720 is_nothrow_default_constructible<key_compare>::value && 721 is_nothrow_copy_constructible<key_compare>::value) 722 : __tree_(__comp) {} 723 _LIBCPP_INLINE_VISIBILITY 724 multiset(const value_compare& __comp, const allocator_type& __a) 725 : __tree_(__comp, __a) {} 726 template <class _InputIterator> 727 _LIBCPP_INLINE_VISIBILITY 728 multiset(_InputIterator __f, _InputIterator __l, 729 const value_compare& __comp = value_compare()) 730 : __tree_(__comp) 731 { 732 insert(__f, __l); 733 } 734 735 template <class _InputIterator> 736 _LIBCPP_INLINE_VISIBILITY 737 multiset(_InputIterator __f, _InputIterator __l, 738 const value_compare& __comp, const allocator_type& __a) 739 : __tree_(__comp, __a) 740 { 741 insert(__f, __l); 742 } 743 744 _LIBCPP_INLINE_VISIBILITY 745 multiset(const multiset& __s) 746 : __tree_(__s.__tree_.value_comp(), 747 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 748 { 749 insert(__s.begin(), __s.end()); 750 } 751 752 _LIBCPP_INLINE_VISIBILITY 753 multiset& operator=(const multiset& __s) 754 { 755 __tree_ = __s.__tree_; 756 return *this; 757 } 758 759#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 760 _LIBCPP_INLINE_VISIBILITY 761 multiset(multiset&& __s) 762 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 763 : __tree_(_VSTD::move(__s.__tree_)) {} 764#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 765 _LIBCPP_INLINE_VISIBILITY 766 explicit multiset(const allocator_type& __a) 767 : __tree_(__a) {} 768 _LIBCPP_INLINE_VISIBILITY 769 multiset(const multiset& __s, const allocator_type& __a) 770 : __tree_(__s.__tree_.value_comp(), __a) 771 { 772 insert(__s.begin(), __s.end()); 773 } 774#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 775 multiset(multiset&& __s, const allocator_type& __a); 776#endif 777 778#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 779 _LIBCPP_INLINE_VISIBILITY 780 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 781 : __tree_(__comp) 782 { 783 insert(__il.begin(), __il.end()); 784 } 785 786 _LIBCPP_INLINE_VISIBILITY 787 multiset(initializer_list<value_type> __il, const value_compare& __comp, 788 const allocator_type& __a) 789 : __tree_(__comp, __a) 790 { 791 insert(__il.begin(), __il.end()); 792 } 793 794 _LIBCPP_INLINE_VISIBILITY 795 multiset& operator=(initializer_list<value_type> __il) 796 { 797 __tree_.__assign_multi(__il.begin(), __il.end()); 798 return *this; 799 } 800#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 801 802#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 803 _LIBCPP_INLINE_VISIBILITY 804 multiset& operator=(multiset&& __s) 805 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 806 { 807 __tree_ = _VSTD::move(__s.__tree_); 808 return *this; 809 } 810#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 811 812 _LIBCPP_INLINE_VISIBILITY 813 iterator begin() _NOEXCEPT {return __tree_.begin();} 814 _LIBCPP_INLINE_VISIBILITY 815 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 816 _LIBCPP_INLINE_VISIBILITY 817 iterator end() _NOEXCEPT {return __tree_.end();} 818 _LIBCPP_INLINE_VISIBILITY 819 const_iterator end() const _NOEXCEPT {return __tree_.end();} 820 821 _LIBCPP_INLINE_VISIBILITY 822 reverse_iterator rbegin() _NOEXCEPT 823 {return reverse_iterator(end());} 824 _LIBCPP_INLINE_VISIBILITY 825 const_reverse_iterator rbegin() const _NOEXCEPT 826 {return const_reverse_iterator(end());} 827 _LIBCPP_INLINE_VISIBILITY 828 reverse_iterator rend() _NOEXCEPT 829 {return reverse_iterator(begin());} 830 _LIBCPP_INLINE_VISIBILITY 831 const_reverse_iterator rend() const _NOEXCEPT 832 {return const_reverse_iterator(begin());} 833 834 _LIBCPP_INLINE_VISIBILITY 835 const_iterator cbegin() const _NOEXCEPT {return begin();} 836 _LIBCPP_INLINE_VISIBILITY 837 const_iterator cend() const _NOEXCEPT {return end();} 838 _LIBCPP_INLINE_VISIBILITY 839 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 840 _LIBCPP_INLINE_VISIBILITY 841 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 842 843 _LIBCPP_INLINE_VISIBILITY 844 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 845 _LIBCPP_INLINE_VISIBILITY 846 size_type size() const _NOEXCEPT {return __tree_.size();} 847 _LIBCPP_INLINE_VISIBILITY 848 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 849 850 // modifiers: 851#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 852 template <class... _Args> 853 _LIBCPP_INLINE_VISIBILITY 854 iterator emplace(_Args&&... __args) 855 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 856 template <class... _Args> 857 _LIBCPP_INLINE_VISIBILITY 858 iterator emplace_hint(const_iterator __p, _Args&&... __args) 859 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 860#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 861 _LIBCPP_INLINE_VISIBILITY 862 iterator insert(const value_type& __v) 863 {return __tree_.__insert_multi(__v);} 864#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 865 _LIBCPP_INLINE_VISIBILITY 866 iterator insert(value_type&& __v) 867 {return __tree_.__insert_multi(_VSTD::move(__v));} 868#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 869 _LIBCPP_INLINE_VISIBILITY 870 iterator insert(const_iterator __p, const value_type& __v) 871 {return __tree_.__insert_multi(__p, __v);} 872#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 873 _LIBCPP_INLINE_VISIBILITY 874 iterator insert(const_iterator __p, value_type&& __v) 875 {return __tree_.__insert_multi(_VSTD::move(__v));} 876#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 877 template <class _InputIterator> 878 _LIBCPP_INLINE_VISIBILITY 879 void insert(_InputIterator __f, _InputIterator __l) 880 { 881 for (const_iterator __e = cend(); __f != __l; ++__f) 882 __tree_.__insert_multi(__e, *__f); 883 } 884 885#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 886 _LIBCPP_INLINE_VISIBILITY 887 void insert(initializer_list<value_type> __il) 888 {insert(__il.begin(), __il.end());} 889#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 890 891 _LIBCPP_INLINE_VISIBILITY 892 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 893 _LIBCPP_INLINE_VISIBILITY 894 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 895 _LIBCPP_INLINE_VISIBILITY 896 iterator erase(const_iterator __f, const_iterator __l) 897 {return __tree_.erase(__f, __l);} 898 _LIBCPP_INLINE_VISIBILITY 899 void clear() _NOEXCEPT {__tree_.clear();} 900 901 _LIBCPP_INLINE_VISIBILITY 902 void swap(multiset& __s) 903 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 904 {__tree_.swap(__s.__tree_);} 905 906 _LIBCPP_INLINE_VISIBILITY 907 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 908 _LIBCPP_INLINE_VISIBILITY 909 key_compare key_comp() const {return __tree_.value_comp();} 910 _LIBCPP_INLINE_VISIBILITY 911 value_compare value_comp() const {return __tree_.value_comp();} 912 913 // set operations: 914 _LIBCPP_INLINE_VISIBILITY 915 iterator find(const key_type& __k) {return __tree_.find(__k);} 916 _LIBCPP_INLINE_VISIBILITY 917 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 918 _LIBCPP_INLINE_VISIBILITY 919 size_type count(const key_type& __k) const 920 {return __tree_.__count_multi(__k);} 921 _LIBCPP_INLINE_VISIBILITY 922 iterator lower_bound(const key_type& __k) 923 {return __tree_.lower_bound(__k);} 924 _LIBCPP_INLINE_VISIBILITY 925 const_iterator lower_bound(const key_type& __k) const 926 {return __tree_.lower_bound(__k);} 927 _LIBCPP_INLINE_VISIBILITY 928 iterator upper_bound(const key_type& __k) 929 {return __tree_.upper_bound(__k);} 930 _LIBCPP_INLINE_VISIBILITY 931 const_iterator upper_bound(const key_type& __k) const 932 {return __tree_.upper_bound(__k);} 933 _LIBCPP_INLINE_VISIBILITY 934 pair<iterator,iterator> equal_range(const key_type& __k) 935 {return __tree_.__equal_range_multi(__k);} 936 _LIBCPP_INLINE_VISIBILITY 937 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 938 {return __tree_.__equal_range_multi(__k);} 939}; 940 941#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 942 943template <class _Key, class _Compare, class _Allocator> 944multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 945 : __tree_(_VSTD::move(__s.__tree_), __a) 946{ 947 if (__a != __s.get_allocator()) 948 { 949 const_iterator __e = cend(); 950 while (!__s.empty()) 951 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 952 } 953} 954 955#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 956 957template <class _Key, class _Compare, class _Allocator> 958inline _LIBCPP_INLINE_VISIBILITY 959bool 960operator==(const multiset<_Key, _Compare, _Allocator>& __x, 961 const multiset<_Key, _Compare, _Allocator>& __y) 962{ 963 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 964} 965 966template <class _Key, class _Compare, class _Allocator> 967inline _LIBCPP_INLINE_VISIBILITY 968bool 969operator< (const multiset<_Key, _Compare, _Allocator>& __x, 970 const multiset<_Key, _Compare, _Allocator>& __y) 971{ 972 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 973} 974 975template <class _Key, class _Compare, class _Allocator> 976inline _LIBCPP_INLINE_VISIBILITY 977bool 978operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 979 const multiset<_Key, _Compare, _Allocator>& __y) 980{ 981 return !(__x == __y); 982} 983 984template <class _Key, class _Compare, class _Allocator> 985inline _LIBCPP_INLINE_VISIBILITY 986bool 987operator> (const multiset<_Key, _Compare, _Allocator>& __x, 988 const multiset<_Key, _Compare, _Allocator>& __y) 989{ 990 return __y < __x; 991} 992 993template <class _Key, class _Compare, class _Allocator> 994inline _LIBCPP_INLINE_VISIBILITY 995bool 996operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 997 const multiset<_Key, _Compare, _Allocator>& __y) 998{ 999 return !(__x < __y); 1000} 1001 1002template <class _Key, class _Compare, class _Allocator> 1003inline _LIBCPP_INLINE_VISIBILITY 1004bool 1005operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1006 const multiset<_Key, _Compare, _Allocator>& __y) 1007{ 1008 return !(__y < __x); 1009} 1010 1011template <class _Key, class _Compare, class _Allocator> 1012inline _LIBCPP_INLINE_VISIBILITY 1013void 1014swap(multiset<_Key, _Compare, _Allocator>& __x, 1015 multiset<_Key, _Compare, _Allocator>& __y) 1016 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1017{ 1018 __x.swap(__y); 1019} 1020 1021_LIBCPP_END_NAMESPACE_STD 1022 1023#endif // _LIBCPP_SET 1024