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