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