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