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_TEMPLATE_VIS 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 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 413 "Allocator::value_type must be same type as value_type"); 414 415 private: 416 typedef __tree<value_type, value_compare, allocator_type> __base; 417 typedef allocator_traits<allocator_type> __alloc_traits; 418 typedef typename __base::__node_holder __node_holder; 419 420 __base __tree_; 421 422 public: 423 typedef typename __base::pointer pointer; 424 typedef typename __base::const_pointer const_pointer; 425 typedef typename __base::size_type size_type; 426 typedef typename __base::difference_type difference_type; 427 typedef typename __base::const_iterator iterator; 428 typedef typename __base::const_iterator const_iterator; 429 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 430 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 431 432 _LIBCPP_INLINE_VISIBILITY 433 set() 434 _NOEXCEPT_( 435 is_nothrow_default_constructible<allocator_type>::value && 436 is_nothrow_default_constructible<key_compare>::value && 437 is_nothrow_copy_constructible<key_compare>::value) 438 : __tree_(value_compare()) {} 439 440 _LIBCPP_INLINE_VISIBILITY 441 explicit set(const value_compare& __comp) 442 _NOEXCEPT_( 443 is_nothrow_default_constructible<allocator_type>::value && 444 is_nothrow_copy_constructible<key_compare>::value) 445 : __tree_(__comp) {} 446 447 _LIBCPP_INLINE_VISIBILITY 448 explicit set(const value_compare& __comp, const allocator_type& __a) 449 : __tree_(__comp, __a) {} 450 template <class _InputIterator> 451 _LIBCPP_INLINE_VISIBILITY 452 set(_InputIterator __f, _InputIterator __l, 453 const value_compare& __comp = value_compare()) 454 : __tree_(__comp) 455 { 456 insert(__f, __l); 457 } 458 459 template <class _InputIterator> 460 _LIBCPP_INLINE_VISIBILITY 461 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 462 const allocator_type& __a) 463 : __tree_(__comp, __a) 464 { 465 insert(__f, __l); 466 } 467 468 #if _LIBCPP_STD_VER > 11 469 template <class _InputIterator> 470 _LIBCPP_INLINE_VISIBILITY 471 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 472 : set(__f, __l, key_compare(), __a) {} 473 #endif 474 475 _LIBCPP_INLINE_VISIBILITY 476 set(const set& __s) 477 : __tree_(__s.__tree_) 478 { 479 insert(__s.begin(), __s.end()); 480 } 481 482 _LIBCPP_INLINE_VISIBILITY 483 set& operator=(const set& __s) 484 { 485 __tree_ = __s.__tree_; 486 return *this; 487 } 488 489 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 490 _LIBCPP_INLINE_VISIBILITY 491 set(set&& __s) 492 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 493 : __tree_(_VSTD::move(__s.__tree_)) {} 494 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 495 496 _LIBCPP_INLINE_VISIBILITY 497 explicit set(const allocator_type& __a) 498 : __tree_(__a) {} 499 500 _LIBCPP_INLINE_VISIBILITY 501 set(const set& __s, const allocator_type& __a) 502 : __tree_(__s.__tree_.value_comp(), __a) 503 { 504 insert(__s.begin(), __s.end()); 505 } 506 507 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 508 set(set&& __s, const allocator_type& __a); 509 #endif 510 511 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 512 _LIBCPP_INLINE_VISIBILITY 513 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 514 : __tree_(__comp) 515 { 516 insert(__il.begin(), __il.end()); 517 } 518 519 _LIBCPP_INLINE_VISIBILITY 520 set(initializer_list<value_type> __il, const value_compare& __comp, 521 const allocator_type& __a) 522 : __tree_(__comp, __a) 523 { 524 insert(__il.begin(), __il.end()); 525 } 526 527 #if _LIBCPP_STD_VER > 11 528 _LIBCPP_INLINE_VISIBILITY 529 set(initializer_list<value_type> __il, const allocator_type& __a) 530 : set(__il, key_compare(), __a) {} 531 #endif 532 533 _LIBCPP_INLINE_VISIBILITY 534 set& operator=(initializer_list<value_type> __il) 535 { 536 __tree_.__assign_unique(__il.begin(), __il.end()); 537 return *this; 538 } 539 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 540 541 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 542 _LIBCPP_INLINE_VISIBILITY 543 set& operator=(set&& __s) 544 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 545 { 546 __tree_ = _VSTD::move(__s.__tree_); 547 return *this; 548 } 549 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 550 551 _LIBCPP_INLINE_VISIBILITY 552 iterator begin() _NOEXCEPT {return __tree_.begin();} 553 _LIBCPP_INLINE_VISIBILITY 554 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 555 _LIBCPP_INLINE_VISIBILITY 556 iterator end() _NOEXCEPT {return __tree_.end();} 557 _LIBCPP_INLINE_VISIBILITY 558 const_iterator end() const _NOEXCEPT {return __tree_.end();} 559 560 _LIBCPP_INLINE_VISIBILITY 561 reverse_iterator rbegin() _NOEXCEPT 562 {return reverse_iterator(end());} 563 _LIBCPP_INLINE_VISIBILITY 564 const_reverse_iterator rbegin() const _NOEXCEPT 565 {return const_reverse_iterator(end());} 566 _LIBCPP_INLINE_VISIBILITY 567 reverse_iterator rend() _NOEXCEPT 568 {return reverse_iterator(begin());} 569 _LIBCPP_INLINE_VISIBILITY 570 const_reverse_iterator rend() const _NOEXCEPT 571 {return const_reverse_iterator(begin());} 572 573 _LIBCPP_INLINE_VISIBILITY 574 const_iterator cbegin() const _NOEXCEPT {return begin();} 575 _LIBCPP_INLINE_VISIBILITY 576 const_iterator cend() const _NOEXCEPT {return end();} 577 _LIBCPP_INLINE_VISIBILITY 578 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 579 _LIBCPP_INLINE_VISIBILITY 580 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 581 582 _LIBCPP_INLINE_VISIBILITY 583 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 584 _LIBCPP_INLINE_VISIBILITY 585 size_type size() const _NOEXCEPT {return __tree_.size();} 586 _LIBCPP_INLINE_VISIBILITY 587 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 588 589 // modifiers: 590 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 591 template <class... _Args> 592 _LIBCPP_INLINE_VISIBILITY 593 pair<iterator, bool> emplace(_Args&&... __args) 594 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 595 template <class... _Args> 596 _LIBCPP_INLINE_VISIBILITY 597 iterator emplace_hint(const_iterator __p, _Args&&... __args) 598 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 599 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 600 _LIBCPP_INLINE_VISIBILITY 601 pair<iterator,bool> insert(const value_type& __v) 602 {return __tree_.__insert_unique(__v);} 603 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 604 _LIBCPP_INLINE_VISIBILITY 605 pair<iterator,bool> insert(value_type&& __v) 606 {return __tree_.__insert_unique(_VSTD::move(__v));} 607 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 608 _LIBCPP_INLINE_VISIBILITY 609 iterator insert(const_iterator __p, const value_type& __v) 610 {return __tree_.__insert_unique(__p, __v);} 611 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 612 _LIBCPP_INLINE_VISIBILITY 613 iterator insert(const_iterator __p, value_type&& __v) 614 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 615 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 616 template <class _InputIterator> 617 _LIBCPP_INLINE_VISIBILITY 618 void insert(_InputIterator __f, _InputIterator __l) 619 { 620 for (const_iterator __e = cend(); __f != __l; ++__f) 621 __tree_.__insert_unique(__e, *__f); 622 } 623 624 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 625 _LIBCPP_INLINE_VISIBILITY 626 void insert(initializer_list<value_type> __il) 627 {insert(__il.begin(), __il.end());} 628 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 629 630 _LIBCPP_INLINE_VISIBILITY 631 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 632 _LIBCPP_INLINE_VISIBILITY 633 size_type erase(const key_type& __k) 634 {return __tree_.__erase_unique(__k);} 635 _LIBCPP_INLINE_VISIBILITY 636 iterator erase(const_iterator __f, const_iterator __l) 637 {return __tree_.erase(__f, __l);} 638 _LIBCPP_INLINE_VISIBILITY 639 void clear() _NOEXCEPT {__tree_.clear();} 640 641 _LIBCPP_INLINE_VISIBILITY 642 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 643 {__tree_.swap(__s.__tree_);} 644 645 _LIBCPP_INLINE_VISIBILITY 646 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 647 _LIBCPP_INLINE_VISIBILITY 648 key_compare key_comp() const {return __tree_.value_comp();} 649 _LIBCPP_INLINE_VISIBILITY 650 value_compare value_comp() const {return __tree_.value_comp();} 651 652 // set operations: 653 _LIBCPP_INLINE_VISIBILITY 654 iterator find(const key_type& __k) {return __tree_.find(__k);} 655 _LIBCPP_INLINE_VISIBILITY 656 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 657 #if _LIBCPP_STD_VER > 11 658 template <typename _K2> 659 _LIBCPP_INLINE_VISIBILITY 660 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 661 find(const _K2& __k) {return __tree_.find(__k);} 662 template <typename _K2> 663 _LIBCPP_INLINE_VISIBILITY 664 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 665 find(const _K2& __k) const {return __tree_.find(__k);} 666 #endif 667 668 _LIBCPP_INLINE_VISIBILITY 669 size_type count(const key_type& __k) const 670 {return __tree_.__count_unique(__k);} 671 #if _LIBCPP_STD_VER > 11 672 template <typename _K2> 673 _LIBCPP_INLINE_VISIBILITY 674 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 675 count(const _K2& __k) const {return __tree_.__count_unique(__k);} 676 #endif 677 _LIBCPP_INLINE_VISIBILITY 678 iterator lower_bound(const key_type& __k) 679 {return __tree_.lower_bound(__k);} 680 _LIBCPP_INLINE_VISIBILITY 681 const_iterator lower_bound(const key_type& __k) const 682 {return __tree_.lower_bound(__k);} 683 #if _LIBCPP_STD_VER > 11 684 template <typename _K2> 685 _LIBCPP_INLINE_VISIBILITY 686 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 687 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 688 689 template <typename _K2> 690 _LIBCPP_INLINE_VISIBILITY 691 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 692 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 693 #endif 694 695 _LIBCPP_INLINE_VISIBILITY 696 iterator upper_bound(const key_type& __k) 697 {return __tree_.upper_bound(__k);} 698 _LIBCPP_INLINE_VISIBILITY 699 const_iterator upper_bound(const key_type& __k) const 700 {return __tree_.upper_bound(__k);} 701 #if _LIBCPP_STD_VER > 11 702 template <typename _K2> 703 _LIBCPP_INLINE_VISIBILITY 704 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 705 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 706 template <typename _K2> 707 _LIBCPP_INLINE_VISIBILITY 708 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 709 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 710 #endif 711 712 _LIBCPP_INLINE_VISIBILITY 713 pair<iterator,iterator> equal_range(const key_type& __k) 714 {return __tree_.__equal_range_unique(__k);} 715 _LIBCPP_INLINE_VISIBILITY 716 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 717 {return __tree_.__equal_range_unique(__k);} 718 #if _LIBCPP_STD_VER > 11 719 template <typename _K2> 720 _LIBCPP_INLINE_VISIBILITY 721 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 722 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} 723 template <typename _K2> 724 _LIBCPP_INLINE_VISIBILITY 725 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 726 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);} 727 #endif 728 }; 729 730 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 731 732 template <class _Key, class _Compare, class _Allocator> 733 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 734 : __tree_(_VSTD::move(__s.__tree_), __a) 735 { 736 if (__a != __s.get_allocator()) 737 { 738 const_iterator __e = cend(); 739 while (!__s.empty()) 740 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 741 } 742 } 743 744 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 745 746 template <class _Key, class _Compare, class _Allocator> 747 inline _LIBCPP_INLINE_VISIBILITY 748 bool 749 operator==(const set<_Key, _Compare, _Allocator>& __x, 750 const set<_Key, _Compare, _Allocator>& __y) 751 { 752 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 753 } 754 755 template <class _Key, class _Compare, class _Allocator> 756 inline _LIBCPP_INLINE_VISIBILITY 757 bool 758 operator< (const set<_Key, _Compare, _Allocator>& __x, 759 const set<_Key, _Compare, _Allocator>& __y) 760 { 761 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 762 } 763 764 template <class _Key, class _Compare, class _Allocator> 765 inline _LIBCPP_INLINE_VISIBILITY 766 bool 767 operator!=(const set<_Key, _Compare, _Allocator>& __x, 768 const set<_Key, _Compare, _Allocator>& __y) 769 { 770 return !(__x == __y); 771 } 772 773 template <class _Key, class _Compare, class _Allocator> 774 inline _LIBCPP_INLINE_VISIBILITY 775 bool 776 operator> (const set<_Key, _Compare, _Allocator>& __x, 777 const set<_Key, _Compare, _Allocator>& __y) 778 { 779 return __y < __x; 780 } 781 782 template <class _Key, class _Compare, class _Allocator> 783 inline _LIBCPP_INLINE_VISIBILITY 784 bool 785 operator>=(const set<_Key, _Compare, _Allocator>& __x, 786 const set<_Key, _Compare, _Allocator>& __y) 787 { 788 return !(__x < __y); 789 } 790 791 template <class _Key, class _Compare, class _Allocator> 792 inline _LIBCPP_INLINE_VISIBILITY 793 bool 794 operator<=(const set<_Key, _Compare, _Allocator>& __x, 795 const set<_Key, _Compare, _Allocator>& __y) 796 { 797 return !(__y < __x); 798 } 799 800 // specialized algorithms: 801 template <class _Key, class _Compare, class _Allocator> 802 inline _LIBCPP_INLINE_VISIBILITY 803 void 804 swap(set<_Key, _Compare, _Allocator>& __x, 805 set<_Key, _Compare, _Allocator>& __y) 806 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 807 { 808 __x.swap(__y); 809 } 810 811 template <class _Key, class _Compare = less<_Key>, 812 class _Allocator = allocator<_Key> > 813 class _LIBCPP_TEMPLATE_VIS multiset 814 { 815 public: 816 // types: 817 typedef _Key key_type; 818 typedef key_type value_type; 819 typedef _Compare key_compare; 820 typedef key_compare value_compare; 821 typedef _Allocator allocator_type; 822 typedef value_type& reference; 823 typedef const value_type& const_reference; 824 825 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 826 "Allocator::value_type must be same type as value_type"); 827 828 private: 829 typedef __tree<value_type, value_compare, allocator_type> __base; 830 typedef allocator_traits<allocator_type> __alloc_traits; 831 typedef typename __base::__node_holder __node_holder; 832 833 __base __tree_; 834 835 public: 836 typedef typename __base::pointer pointer; 837 typedef typename __base::const_pointer const_pointer; 838 typedef typename __base::size_type size_type; 839 typedef typename __base::difference_type difference_type; 840 typedef typename __base::const_iterator iterator; 841 typedef typename __base::const_iterator const_iterator; 842 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 843 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 844 845 // construct/copy/destroy: 846 _LIBCPP_INLINE_VISIBILITY 847 multiset() 848 _NOEXCEPT_( 849 is_nothrow_default_constructible<allocator_type>::value && 850 is_nothrow_default_constructible<key_compare>::value && 851 is_nothrow_copy_constructible<key_compare>::value) 852 : __tree_(value_compare()) {} 853 854 _LIBCPP_INLINE_VISIBILITY 855 explicit multiset(const value_compare& __comp) 856 _NOEXCEPT_( 857 is_nothrow_default_constructible<allocator_type>::value && 858 is_nothrow_copy_constructible<key_compare>::value) 859 : __tree_(__comp) {} 860 861 _LIBCPP_INLINE_VISIBILITY 862 explicit multiset(const value_compare& __comp, const allocator_type& __a) 863 : __tree_(__comp, __a) {} 864 template <class _InputIterator> 865 _LIBCPP_INLINE_VISIBILITY 866 multiset(_InputIterator __f, _InputIterator __l, 867 const value_compare& __comp = value_compare()) 868 : __tree_(__comp) 869 { 870 insert(__f, __l); 871 } 872 873 #if _LIBCPP_STD_VER > 11 874 template <class _InputIterator> 875 _LIBCPP_INLINE_VISIBILITY 876 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 877 : multiset(__f, __l, key_compare(), __a) {} 878 #endif 879 880 template <class _InputIterator> 881 _LIBCPP_INLINE_VISIBILITY 882 multiset(_InputIterator __f, _InputIterator __l, 883 const value_compare& __comp, const allocator_type& __a) 884 : __tree_(__comp, __a) 885 { 886 insert(__f, __l); 887 } 888 889 _LIBCPP_INLINE_VISIBILITY 890 multiset(const multiset& __s) 891 : __tree_(__s.__tree_.value_comp(), 892 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 893 { 894 insert(__s.begin(), __s.end()); 895 } 896 897 _LIBCPP_INLINE_VISIBILITY 898 multiset& operator=(const multiset& __s) 899 { 900 __tree_ = __s.__tree_; 901 return *this; 902 } 903 904 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 905 _LIBCPP_INLINE_VISIBILITY 906 multiset(multiset&& __s) 907 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 908 : __tree_(_VSTD::move(__s.__tree_)) {} 909 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 910 _LIBCPP_INLINE_VISIBILITY 911 explicit multiset(const allocator_type& __a) 912 : __tree_(__a) {} 913 _LIBCPP_INLINE_VISIBILITY 914 multiset(const multiset& __s, const allocator_type& __a) 915 : __tree_(__s.__tree_.value_comp(), __a) 916 { 917 insert(__s.begin(), __s.end()); 918 } 919 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 920 multiset(multiset&& __s, const allocator_type& __a); 921 #endif 922 923 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 924 _LIBCPP_INLINE_VISIBILITY 925 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 926 : __tree_(__comp) 927 { 928 insert(__il.begin(), __il.end()); 929 } 930 931 _LIBCPP_INLINE_VISIBILITY 932 multiset(initializer_list<value_type> __il, const value_compare& __comp, 933 const allocator_type& __a) 934 : __tree_(__comp, __a) 935 { 936 insert(__il.begin(), __il.end()); 937 } 938 939 #if _LIBCPP_STD_VER > 11 940 _LIBCPP_INLINE_VISIBILITY 941 multiset(initializer_list<value_type> __il, const allocator_type& __a) 942 : multiset(__il, key_compare(), __a) {} 943 #endif 944 945 _LIBCPP_INLINE_VISIBILITY 946 multiset& operator=(initializer_list<value_type> __il) 947 { 948 __tree_.__assign_multi(__il.begin(), __il.end()); 949 return *this; 950 } 951 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 952 953 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 954 _LIBCPP_INLINE_VISIBILITY 955 multiset& operator=(multiset&& __s) 956 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 957 { 958 __tree_ = _VSTD::move(__s.__tree_); 959 return *this; 960 } 961 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 962 963 _LIBCPP_INLINE_VISIBILITY 964 iterator begin() _NOEXCEPT {return __tree_.begin();} 965 _LIBCPP_INLINE_VISIBILITY 966 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 967 _LIBCPP_INLINE_VISIBILITY 968 iterator end() _NOEXCEPT {return __tree_.end();} 969 _LIBCPP_INLINE_VISIBILITY 970 const_iterator end() const _NOEXCEPT {return __tree_.end();} 971 972 _LIBCPP_INLINE_VISIBILITY 973 reverse_iterator rbegin() _NOEXCEPT 974 {return reverse_iterator(end());} 975 _LIBCPP_INLINE_VISIBILITY 976 const_reverse_iterator rbegin() const _NOEXCEPT 977 {return const_reverse_iterator(end());} 978 _LIBCPP_INLINE_VISIBILITY 979 reverse_iterator rend() _NOEXCEPT 980 {return reverse_iterator(begin());} 981 _LIBCPP_INLINE_VISIBILITY 982 const_reverse_iterator rend() const _NOEXCEPT 983 {return const_reverse_iterator(begin());} 984 985 _LIBCPP_INLINE_VISIBILITY 986 const_iterator cbegin() const _NOEXCEPT {return begin();} 987 _LIBCPP_INLINE_VISIBILITY 988 const_iterator cend() const _NOEXCEPT {return end();} 989 _LIBCPP_INLINE_VISIBILITY 990 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 991 _LIBCPP_INLINE_VISIBILITY 992 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 993 994 _LIBCPP_INLINE_VISIBILITY 995 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 996 _LIBCPP_INLINE_VISIBILITY 997 size_type size() const _NOEXCEPT {return __tree_.size();} 998 _LIBCPP_INLINE_VISIBILITY 999 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1000 1001 // modifiers: 1002 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1003 template <class... _Args> 1004 _LIBCPP_INLINE_VISIBILITY 1005 iterator emplace(_Args&&... __args) 1006 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1007 template <class... _Args> 1008 _LIBCPP_INLINE_VISIBILITY 1009 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1010 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1011 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) 1012 _LIBCPP_INLINE_VISIBILITY 1013 iterator insert(const value_type& __v) 1014 {return __tree_.__insert_multi(__v);} 1015 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1016 _LIBCPP_INLINE_VISIBILITY 1017 iterator insert(value_type&& __v) 1018 {return __tree_.__insert_multi(_VSTD::move(__v));} 1019 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1020 _LIBCPP_INLINE_VISIBILITY 1021 iterator insert(const_iterator __p, const value_type& __v) 1022 {return __tree_.__insert_multi(__p, __v);} 1023 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1024 _LIBCPP_INLINE_VISIBILITY 1025 iterator insert(const_iterator __p, value_type&& __v) 1026 {return __tree_.__insert_multi(__p, _VSTD::move(__v));} 1027 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1028 template <class _InputIterator> 1029 _LIBCPP_INLINE_VISIBILITY 1030 void insert(_InputIterator __f, _InputIterator __l) 1031 { 1032 for (const_iterator __e = cend(); __f != __l; ++__f) 1033 __tree_.__insert_multi(__e, *__f); 1034 } 1035 1036 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1037 _LIBCPP_INLINE_VISIBILITY 1038 void insert(initializer_list<value_type> __il) 1039 {insert(__il.begin(), __il.end());} 1040 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1041 1042 _LIBCPP_INLINE_VISIBILITY 1043 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1044 _LIBCPP_INLINE_VISIBILITY 1045 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1046 _LIBCPP_INLINE_VISIBILITY 1047 iterator erase(const_iterator __f, const_iterator __l) 1048 {return __tree_.erase(__f, __l);} 1049 _LIBCPP_INLINE_VISIBILITY 1050 void clear() _NOEXCEPT {__tree_.clear();} 1051 1052 _LIBCPP_INLINE_VISIBILITY 1053 void swap(multiset& __s) 1054 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1055 {__tree_.swap(__s.__tree_);} 1056 1057 _LIBCPP_INLINE_VISIBILITY 1058 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1059 _LIBCPP_INLINE_VISIBILITY 1060 key_compare key_comp() const {return __tree_.value_comp();} 1061 _LIBCPP_INLINE_VISIBILITY 1062 value_compare value_comp() const {return __tree_.value_comp();} 1063 1064 // set operations: 1065 _LIBCPP_INLINE_VISIBILITY 1066 iterator find(const key_type& __k) {return __tree_.find(__k);} 1067 _LIBCPP_INLINE_VISIBILITY 1068 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1069 #if _LIBCPP_STD_VER > 11 1070 template <typename _K2> 1071 _LIBCPP_INLINE_VISIBILITY 1072 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1073 find(const _K2& __k) {return __tree_.find(__k);} 1074 template <typename _K2> 1075 _LIBCPP_INLINE_VISIBILITY 1076 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1077 find(const _K2& __k) const {return __tree_.find(__k);} 1078 #endif 1079 1080 _LIBCPP_INLINE_VISIBILITY 1081 size_type count(const key_type& __k) const 1082 {return __tree_.__count_multi(__k);} 1083 #if _LIBCPP_STD_VER > 11 1084 template <typename _K2> 1085 _LIBCPP_INLINE_VISIBILITY 1086 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1087 count(const _K2& __k) {return __tree_.__count_multi(__k);} 1088 #endif 1089 1090 _LIBCPP_INLINE_VISIBILITY 1091 iterator lower_bound(const key_type& __k) 1092 {return __tree_.lower_bound(__k);} 1093 _LIBCPP_INLINE_VISIBILITY 1094 const_iterator lower_bound(const key_type& __k) const 1095 {return __tree_.lower_bound(__k);} 1096 #if _LIBCPP_STD_VER > 11 1097 template <typename _K2> 1098 _LIBCPP_INLINE_VISIBILITY 1099 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1100 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1101 1102 template <typename _K2> 1103 _LIBCPP_INLINE_VISIBILITY 1104 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1105 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1106 #endif 1107 1108 _LIBCPP_INLINE_VISIBILITY 1109 iterator upper_bound(const key_type& __k) 1110 {return __tree_.upper_bound(__k);} 1111 _LIBCPP_INLINE_VISIBILITY 1112 const_iterator upper_bound(const key_type& __k) const 1113 {return __tree_.upper_bound(__k);} 1114 #if _LIBCPP_STD_VER > 11 1115 template <typename _K2> 1116 _LIBCPP_INLINE_VISIBILITY 1117 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1118 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1119 template <typename _K2> 1120 _LIBCPP_INLINE_VISIBILITY 1121 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1122 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1123 #endif 1124 1125 _LIBCPP_INLINE_VISIBILITY 1126 pair<iterator,iterator> equal_range(const key_type& __k) 1127 {return __tree_.__equal_range_multi(__k);} 1128 _LIBCPP_INLINE_VISIBILITY 1129 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1130 {return __tree_.__equal_range_multi(__k);} 1131 #if _LIBCPP_STD_VER > 11 1132 template <typename _K2> 1133 _LIBCPP_INLINE_VISIBILITY 1134 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1135 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1136 template <typename _K2> 1137 _LIBCPP_INLINE_VISIBILITY 1138 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1139 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1140 #endif 1141 }; 1142 1143 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1144 1145 template <class _Key, class _Compare, class _Allocator> 1146 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1147 : __tree_(_VSTD::move(__s.__tree_), __a) 1148 { 1149 if (__a != __s.get_allocator()) 1150 { 1151 const_iterator __e = cend(); 1152 while (!__s.empty()) 1153 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1154 } 1155 } 1156 1157 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1158 1159 template <class _Key, class _Compare, class _Allocator> 1160 inline _LIBCPP_INLINE_VISIBILITY 1161 bool 1162 operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1163 const multiset<_Key, _Compare, _Allocator>& __y) 1164 { 1165 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1166 } 1167 1168 template <class _Key, class _Compare, class _Allocator> 1169 inline _LIBCPP_INLINE_VISIBILITY 1170 bool 1171 operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1172 const multiset<_Key, _Compare, _Allocator>& __y) 1173 { 1174 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1175 } 1176 1177 template <class _Key, class _Compare, class _Allocator> 1178 inline _LIBCPP_INLINE_VISIBILITY 1179 bool 1180 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1181 const multiset<_Key, _Compare, _Allocator>& __y) 1182 { 1183 return !(__x == __y); 1184 } 1185 1186 template <class _Key, class _Compare, class _Allocator> 1187 inline _LIBCPP_INLINE_VISIBILITY 1188 bool 1189 operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1190 const multiset<_Key, _Compare, _Allocator>& __y) 1191 { 1192 return __y < __x; 1193 } 1194 1195 template <class _Key, class _Compare, class _Allocator> 1196 inline _LIBCPP_INLINE_VISIBILITY 1197 bool 1198 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1199 const multiset<_Key, _Compare, _Allocator>& __y) 1200 { 1201 return !(__x < __y); 1202 } 1203 1204 template <class _Key, class _Compare, class _Allocator> 1205 inline _LIBCPP_INLINE_VISIBILITY 1206 bool 1207 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1208 const multiset<_Key, _Compare, _Allocator>& __y) 1209 { 1210 return !(__y < __x); 1211 } 1212 1213 template <class _Key, class _Compare, class _Allocator> 1214 inline _LIBCPP_INLINE_VISIBILITY 1215 void 1216 swap(multiset<_Key, _Compare, _Allocator>& __x, 1217 multiset<_Key, _Compare, _Allocator>& __y) 1218 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1219 { 1220 __x.swap(__y); 1221 } 1222 1223 _LIBCPP_END_NAMESPACE_STD 1224 1225 #endif // _LIBCPP_SET 1226
