1// -*- C++ -*- 2//===---------------------------- set -------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_SET 11#define _LIBCPP_SET 12 13/* 14 15 set synopsis 16 17namespace std 18{ 19 20template <class Key, class Compare = less<Key>, 21 class Allocator = allocator<Key>> 22class set 23{ 24public: 25 // types: 26 typedef Key key_type; 27 typedef key_type value_type; 28 typedef Compare key_compare; 29 typedef key_compare value_compare; 30 typedef Allocator allocator_type; 31 typedef typename allocator_type::reference reference; 32 typedef typename allocator_type::const_reference const_reference; 33 typedef typename allocator_type::size_type size_type; 34 typedef typename allocator_type::difference_type difference_type; 35 typedef typename allocator_type::pointer pointer; 36 typedef typename allocator_type::const_pointer const_pointer; 37 38 typedef implementation-defined iterator; 39 typedef implementation-defined const_iterator; 40 typedef std::reverse_iterator<iterator> reverse_iterator; 41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 42 typedef unspecified node_type; // C++17 43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 44 45 // construct/copy/destroy: 46 set() 47 noexcept( 48 is_nothrow_default_constructible<allocator_type>::value && 49 is_nothrow_default_constructible<key_compare>::value && 50 is_nothrow_copy_constructible<key_compare>::value); 51 explicit set(const value_compare& comp); 52 set(const value_compare& comp, const allocator_type& a); 53 template <class InputIterator> 54 set(InputIterator first, InputIterator last, 55 const value_compare& comp = value_compare()); 56 template <class InputIterator> 57 set(InputIterator first, InputIterator last, const value_compare& comp, 58 const allocator_type& a); 59 set(const set& s); 60 set(set&& s) 61 noexcept( 62 is_nothrow_move_constructible<allocator_type>::value && 63 is_nothrow_move_constructible<key_compare>::value); 64 explicit set(const allocator_type& a); 65 set(const set& s, const allocator_type& a); 66 set(set&& s, const allocator_type& a); 67 set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 68 set(initializer_list<value_type> il, const value_compare& comp, 69 const allocator_type& a); 70 template <class InputIterator> 71 set(InputIterator first, InputIterator last, const allocator_type& a) 72 : set(first, last, Compare(), a) {} // C++14 73 set(initializer_list<value_type> il, const allocator_type& a) 74 : set(il, Compare(), a) {} // C++14 75 ~set(); 76 77 set& operator=(const set& s); 78 set& operator=(set&& s) 79 noexcept( 80 allocator_type::propagate_on_container_move_assignment::value && 81 is_nothrow_move_assignable<allocator_type>::value && 82 is_nothrow_move_assignable<key_compare>::value); 83 set& operator=(initializer_list<value_type> il); 84 85 // iterators: 86 iterator begin() noexcept; 87 const_iterator begin() const noexcept; 88 iterator end() noexcept; 89 const_iterator end() const noexcept; 90 91 reverse_iterator rbegin() noexcept; 92 const_reverse_iterator rbegin() const noexcept; 93 reverse_iterator rend() noexcept; 94 const_reverse_iterator rend() const noexcept; 95 96 const_iterator cbegin() const noexcept; 97 const_iterator cend() const noexcept; 98 const_reverse_iterator crbegin() const noexcept; 99 const_reverse_iterator crend() const noexcept; 100 101 // capacity: 102 bool empty() const noexcept; 103 size_type size() const noexcept; 104 size_type max_size() const noexcept; 105 106 // modifiers: 107 template <class... Args> 108 pair<iterator, bool> emplace(Args&&... args); 109 template <class... Args> 110 iterator emplace_hint(const_iterator position, Args&&... args); 111 pair<iterator,bool> insert(const value_type& v); 112 pair<iterator,bool> insert(value_type&& v); 113 iterator insert(const_iterator position, const value_type& v); 114 iterator insert(const_iterator position, value_type&& v); 115 template <class InputIterator> 116 void insert(InputIterator first, InputIterator last); 117 void insert(initializer_list<value_type> il); 118 119 node_type extract(const_iterator position); // C++17 120 node_type extract(const key_type& x); // C++17 121 insert_return_type insert(node_type&& nh); // C++17 122 iterator insert(const_iterator hint, node_type&& nh); // C++17 123 124 iterator erase(const_iterator position); 125 iterator erase(iterator position); // C++14 126 size_type erase(const key_type& k); 127 iterator erase(const_iterator first, const_iterator last); 128 void clear() noexcept; 129 130 template<class C2> 131 void merge(set<Key, C2, Allocator>& source); // C++17 132 template<class C2> 133 void merge(set<Key, C2, Allocator>&& source); // C++17 134 template<class C2> 135 void merge(multiset<Key, C2, Allocator>& source); // C++17 136 template<class C2> 137 void merge(multiset<Key, C2, Allocator>&& source); // C++17 138 139 void swap(set& s) 140 noexcept( 141 __is_nothrow_swappable<key_compare>::value && 142 (!allocator_type::propagate_on_container_swap::value || 143 __is_nothrow_swappable<allocator_type>::value)); 144 145 // observers: 146 allocator_type get_allocator() const noexcept; 147 key_compare key_comp() const; 148 value_compare value_comp() const; 149 150 // set operations: 151 iterator find(const key_type& k); 152 const_iterator find(const key_type& k) const; 153 template<typename K> 154 iterator find(const K& x); 155 template<typename K> 156 const_iterator find(const K& x) const; // C++14 157 template<typename K> 158 size_type count(const K& x) const; // C++14 159 size_type count(const key_type& k) const; 160 bool contains(const key_type& x) const; // C++20 161 iterator lower_bound(const key_type& k); 162 const_iterator lower_bound(const key_type& k) const; 163 template<typename K> 164 iterator lower_bound(const K& x); // C++14 165 template<typename K> 166 const_iterator lower_bound(const K& x) const; // C++14 167 168 iterator upper_bound(const key_type& k); 169 const_iterator upper_bound(const key_type& k) const; 170 template<typename K> 171 iterator upper_bound(const K& x); // C++14 172 template<typename K> 173 const_iterator upper_bound(const K& x) const; // C++14 174 pair<iterator,iterator> equal_range(const key_type& k); 175 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 176 template<typename K> 177 pair<iterator,iterator> equal_range(const K& x); // C++14 178 template<typename K> 179 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 180}; 181 182template <class Key, class Compare, class Allocator> 183bool 184operator==(const set<Key, Compare, Allocator>& x, 185 const set<Key, Compare, Allocator>& y); 186 187template <class Key, class Compare, class Allocator> 188bool 189operator< (const set<Key, Compare, Allocator>& x, 190 const set<Key, Compare, Allocator>& y); 191 192template <class Key, class Compare, class Allocator> 193bool 194operator!=(const set<Key, Compare, Allocator>& x, 195 const set<Key, Compare, Allocator>& y); 196 197template <class Key, class Compare, class Allocator> 198bool 199operator> (const set<Key, Compare, Allocator>& x, 200 const set<Key, Compare, Allocator>& y); 201 202template <class Key, class Compare, class Allocator> 203bool 204operator>=(const set<Key, Compare, Allocator>& x, 205 const set<Key, Compare, Allocator>& y); 206 207template <class Key, class Compare, class Allocator> 208bool 209operator<=(const set<Key, Compare, Allocator>& x, 210 const set<Key, Compare, Allocator>& y); 211 212// specialized algorithms: 213template <class Key, class Compare, class Allocator> 214void 215swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 216 noexcept(noexcept(x.swap(y))); 217 218template <class Key, class Compare, class Allocator, class Predicate> 219typename set<Key, Compare, Allocator>::size_type 220erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 221 222template <class Key, class Compare = less<Key>, 223 class Allocator = allocator<Key>> 224class multiset 225{ 226public: 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 template<typename K> 359 size_type count(const K& x) const; // C++14 360 size_type count(const key_type& k) const; 361 bool contains(const key_type& x) const; // C++20 362 iterator lower_bound(const key_type& k); 363 const_iterator lower_bound(const key_type& k) const; 364 template<typename K> 365 iterator lower_bound(const K& x); // C++14 366 template<typename K> 367 const_iterator lower_bound(const K& x) const; // C++14 368 369 iterator upper_bound(const key_type& k); 370 const_iterator upper_bound(const key_type& k) const; 371 template<typename K> 372 iterator upper_bound(const K& x); // C++14 373 template<typename K> 374 const_iterator upper_bound(const K& x) const; // C++14 375 376 pair<iterator,iterator> equal_range(const key_type& k); 377 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 378 template<typename K> 379 pair<iterator,iterator> equal_range(const K& x); // C++14 380 template<typename K> 381 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 382}; 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 409template <class Key, class Compare, class Allocator> 410bool 411operator<=(const multiset<Key, Compare, Allocator>& x, 412 const multiset<Key, Compare, Allocator>& y); 413 414// specialized algorithms: 415template <class Key, class Compare, class Allocator> 416void 417swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 418 noexcept(noexcept(x.swap(y))); 419 420template <class Key, class Compare, class Allocator, class Predicate> 421typename multiset<Key, Compare, Allocator>::size_type 422erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 423 424} // std 425 426*/ 427 428#include <__config> 429#include <__tree> 430#include <__node_handle> 431#include <compare> 432#include <functional> 433#include <initializer_list> 434#include <iterator> // __libcpp_erase_if_container 435#include <version> 436 437#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 438#pragma GCC system_header 439#endif 440 441_LIBCPP_BEGIN_NAMESPACE_STD 442 443template <class _Key, class _Compare, class _Allocator> 444class multiset; 445 446template <class _Key, class _Compare = less<_Key>, 447 class _Allocator = allocator<_Key> > 448class _LIBCPP_TEMPLATE_VIS set 449{ 450public: 451 // types: 452 typedef _Key key_type; 453 typedef key_type value_type; 454 typedef _Compare key_compare; 455 typedef key_compare value_compare; 456 typedef __identity_t<_Allocator> allocator_type; 457 typedef value_type& reference; 458 typedef const value_type& const_reference; 459 460 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 461 "Allocator::value_type must be same type as value_type"); 462 463private: 464 typedef __tree<value_type, value_compare, allocator_type> __base; 465 typedef allocator_traits<allocator_type> __alloc_traits; 466 typedef typename __base::__node_holder __node_holder; 467 468 __base __tree_; 469 470public: 471 typedef typename __base::pointer pointer; 472 typedef typename __base::const_pointer const_pointer; 473 typedef typename __base::size_type size_type; 474 typedef typename __base::difference_type difference_type; 475 typedef typename __base::const_iterator iterator; 476 typedef typename __base::const_iterator const_iterator; 477 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 478 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 479 480#if _LIBCPP_STD_VER > 14 481 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 482 typedef __insert_return_type<iterator, node_type> insert_return_type; 483#endif 484 485 template <class _Key2, class _Compare2, class _Alloc2> 486 friend class _LIBCPP_TEMPLATE_VIS set; 487 template <class _Key2, class _Compare2, class _Alloc2> 488 friend class _LIBCPP_TEMPLATE_VIS multiset; 489 490 _LIBCPP_INLINE_VISIBILITY 491 set() 492 _NOEXCEPT_( 493 is_nothrow_default_constructible<allocator_type>::value && 494 is_nothrow_default_constructible<key_compare>::value && 495 is_nothrow_copy_constructible<key_compare>::value) 496 : __tree_(value_compare()) {} 497 498 _LIBCPP_INLINE_VISIBILITY 499 explicit set(const value_compare& __comp) 500 _NOEXCEPT_( 501 is_nothrow_default_constructible<allocator_type>::value && 502 is_nothrow_copy_constructible<key_compare>::value) 503 : __tree_(__comp) {} 504 505 _LIBCPP_INLINE_VISIBILITY 506 explicit set(const value_compare& __comp, const allocator_type& __a) 507 : __tree_(__comp, __a) {} 508 template <class _InputIterator> 509 _LIBCPP_INLINE_VISIBILITY 510 set(_InputIterator __f, _InputIterator __l, 511 const value_compare& __comp = value_compare()) 512 : __tree_(__comp) 513 { 514 insert(__f, __l); 515 } 516 517 template <class _InputIterator> 518 _LIBCPP_INLINE_VISIBILITY 519 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 520 const allocator_type& __a) 521 : __tree_(__comp, __a) 522 { 523 insert(__f, __l); 524 } 525 526#if _LIBCPP_STD_VER > 11 527 template <class _InputIterator> 528 _LIBCPP_INLINE_VISIBILITY 529 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 530 : set(__f, __l, key_compare(), __a) {} 531#endif 532 533 _LIBCPP_INLINE_VISIBILITY 534 set(const set& __s) 535 : __tree_(__s.__tree_) 536 { 537 insert(__s.begin(), __s.end()); 538 } 539 540 _LIBCPP_INLINE_VISIBILITY 541 set& operator=(const set& __s) 542 { 543 __tree_ = __s.__tree_; 544 return *this; 545 } 546 547#ifndef _LIBCPP_CXX03_LANG 548 _LIBCPP_INLINE_VISIBILITY 549 set(set&& __s) 550 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 551 : __tree_(_VSTD::move(__s.__tree_)) {} 552#endif // _LIBCPP_CXX03_LANG 553 554 _LIBCPP_INLINE_VISIBILITY 555 explicit set(const allocator_type& __a) 556 : __tree_(__a) {} 557 558 _LIBCPP_INLINE_VISIBILITY 559 set(const set& __s, const allocator_type& __a) 560 : __tree_(__s.__tree_.value_comp(), __a) 561 { 562 insert(__s.begin(), __s.end()); 563 } 564 565#ifndef _LIBCPP_CXX03_LANG 566 set(set&& __s, const allocator_type& __a); 567 568 _LIBCPP_INLINE_VISIBILITY 569 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 570 : __tree_(__comp) 571 { 572 insert(__il.begin(), __il.end()); 573 } 574 575 _LIBCPP_INLINE_VISIBILITY 576 set(initializer_list<value_type> __il, const value_compare& __comp, 577 const allocator_type& __a) 578 : __tree_(__comp, __a) 579 { 580 insert(__il.begin(), __il.end()); 581 } 582 583#if _LIBCPP_STD_VER > 11 584 _LIBCPP_INLINE_VISIBILITY 585 set(initializer_list<value_type> __il, const allocator_type& __a) 586 : set(__il, key_compare(), __a) {} 587#endif 588 589 _LIBCPP_INLINE_VISIBILITY 590 set& operator=(initializer_list<value_type> __il) 591 { 592 __tree_.__assign_unique(__il.begin(), __il.end()); 593 return *this; 594 } 595 596 _LIBCPP_INLINE_VISIBILITY 597 set& operator=(set&& __s) 598 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 599 { 600 __tree_ = _VSTD::move(__s.__tree_); 601 return *this; 602 } 603#endif // _LIBCPP_CXX03_LANG 604 605 _LIBCPP_INLINE_VISIBILITY 606 ~set() { 607 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 608 } 609 610 _LIBCPP_INLINE_VISIBILITY 611 iterator begin() _NOEXCEPT {return __tree_.begin();} 612 _LIBCPP_INLINE_VISIBILITY 613 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 614 _LIBCPP_INLINE_VISIBILITY 615 iterator end() _NOEXCEPT {return __tree_.end();} 616 _LIBCPP_INLINE_VISIBILITY 617 const_iterator end() const _NOEXCEPT {return __tree_.end();} 618 619 _LIBCPP_INLINE_VISIBILITY 620 reverse_iterator rbegin() _NOEXCEPT 621 {return reverse_iterator(end());} 622 _LIBCPP_INLINE_VISIBILITY 623 const_reverse_iterator rbegin() const _NOEXCEPT 624 {return const_reverse_iterator(end());} 625 _LIBCPP_INLINE_VISIBILITY 626 reverse_iterator rend() _NOEXCEPT 627 {return reverse_iterator(begin());} 628 _LIBCPP_INLINE_VISIBILITY 629 const_reverse_iterator rend() const _NOEXCEPT 630 {return const_reverse_iterator(begin());} 631 632 _LIBCPP_INLINE_VISIBILITY 633 const_iterator cbegin() const _NOEXCEPT {return begin();} 634 _LIBCPP_INLINE_VISIBILITY 635 const_iterator cend() const _NOEXCEPT {return end();} 636 _LIBCPP_INLINE_VISIBILITY 637 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 638 _LIBCPP_INLINE_VISIBILITY 639 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 640 641 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 642 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 643 _LIBCPP_INLINE_VISIBILITY 644 size_type size() const _NOEXCEPT {return __tree_.size();} 645 _LIBCPP_INLINE_VISIBILITY 646 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 647 648 // modifiers: 649#ifndef _LIBCPP_CXX03_LANG 650 template <class... _Args> 651 _LIBCPP_INLINE_VISIBILITY 652 pair<iterator, bool> emplace(_Args&&... __args) 653 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 654 template <class... _Args> 655 _LIBCPP_INLINE_VISIBILITY 656 iterator emplace_hint(const_iterator __p, _Args&&... __args) 657 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 658#endif // _LIBCPP_CXX03_LANG 659 660 _LIBCPP_INLINE_VISIBILITY 661 pair<iterator,bool> insert(const value_type& __v) 662 {return __tree_.__insert_unique(__v);} 663 _LIBCPP_INLINE_VISIBILITY 664 iterator insert(const_iterator __p, const value_type& __v) 665 {return __tree_.__insert_unique(__p, __v);} 666 667 template <class _InputIterator> 668 _LIBCPP_INLINE_VISIBILITY 669 void insert(_InputIterator __f, _InputIterator __l) 670 { 671 for (const_iterator __e = cend(); __f != __l; ++__f) 672 __tree_.__insert_unique(__e, *__f); 673 } 674 675#ifndef _LIBCPP_CXX03_LANG 676 _LIBCPP_INLINE_VISIBILITY 677 pair<iterator,bool> insert(value_type&& __v) 678 {return __tree_.__insert_unique(_VSTD::move(__v));} 679 680 _LIBCPP_INLINE_VISIBILITY 681 iterator insert(const_iterator __p, value_type&& __v) 682 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 683 684 _LIBCPP_INLINE_VISIBILITY 685 void insert(initializer_list<value_type> __il) 686 {insert(__il.begin(), __il.end());} 687#endif // _LIBCPP_CXX03_LANG 688 689 _LIBCPP_INLINE_VISIBILITY 690 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 691 _LIBCPP_INLINE_VISIBILITY 692 size_type erase(const key_type& __k) 693 {return __tree_.__erase_unique(__k);} 694 _LIBCPP_INLINE_VISIBILITY 695 iterator erase(const_iterator __f, const_iterator __l) 696 {return __tree_.erase(__f, __l);} 697 _LIBCPP_INLINE_VISIBILITY 698 void clear() _NOEXCEPT {__tree_.clear();} 699 700#if _LIBCPP_STD_VER > 14 701 _LIBCPP_INLINE_VISIBILITY 702 insert_return_type insert(node_type&& __nh) 703 { 704 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 705 "node_type with incompatible allocator passed to set::insert()"); 706 return __tree_.template __node_handle_insert_unique< 707 node_type, insert_return_type>(_VSTD::move(__nh)); 708 } 709 _LIBCPP_INLINE_VISIBILITY 710 iterator insert(const_iterator __hint, node_type&& __nh) 711 { 712 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 713 "node_type with incompatible allocator passed to set::insert()"); 714 return __tree_.template __node_handle_insert_unique<node_type>( 715 __hint, _VSTD::move(__nh)); 716 } 717 _LIBCPP_INLINE_VISIBILITY 718 node_type extract(key_type const& __key) 719 { 720 return __tree_.template __node_handle_extract<node_type>(__key); 721 } 722 _LIBCPP_INLINE_VISIBILITY 723 node_type extract(const_iterator __it) 724 { 725 return __tree_.template __node_handle_extract<node_type>(__it); 726 } 727 template <class _Compare2> 728 _LIBCPP_INLINE_VISIBILITY 729 void merge(set<key_type, _Compare2, allocator_type>& __source) 730 { 731 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 732 "merging container with incompatible allocator"); 733 __tree_.__node_handle_merge_unique(__source.__tree_); 734 } 735 template <class _Compare2> 736 _LIBCPP_INLINE_VISIBILITY 737 void merge(set<key_type, _Compare2, allocator_type>&& __source) 738 { 739 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 740 "merging container with incompatible allocator"); 741 __tree_.__node_handle_merge_unique(__source.__tree_); 742 } 743 template <class _Compare2> 744 _LIBCPP_INLINE_VISIBILITY 745 void merge(multiset<key_type, _Compare2, allocator_type>& __source) 746 { 747 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 748 "merging container with incompatible allocator"); 749 __tree_.__node_handle_merge_unique(__source.__tree_); 750 } 751 template <class _Compare2> 752 _LIBCPP_INLINE_VISIBILITY 753 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 754 { 755 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 756 "merging container with incompatible allocator"); 757 __tree_.__node_handle_merge_unique(__source.__tree_); 758 } 759#endif 760 761 _LIBCPP_INLINE_VISIBILITY 762 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 763 {__tree_.swap(__s.__tree_);} 764 765 _LIBCPP_INLINE_VISIBILITY 766 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 767 _LIBCPP_INLINE_VISIBILITY 768 key_compare key_comp() const {return __tree_.value_comp();} 769 _LIBCPP_INLINE_VISIBILITY 770 value_compare value_comp() const {return __tree_.value_comp();} 771 772 // set operations: 773 _LIBCPP_INLINE_VISIBILITY 774 iterator find(const key_type& __k) {return __tree_.find(__k);} 775 _LIBCPP_INLINE_VISIBILITY 776 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 777#if _LIBCPP_STD_VER > 11 778 template <typename _K2> 779 _LIBCPP_INLINE_VISIBILITY 780 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 781 find(const _K2& __k) {return __tree_.find(__k);} 782 template <typename _K2> 783 _LIBCPP_INLINE_VISIBILITY 784 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 785 find(const _K2& __k) const {return __tree_.find(__k);} 786#endif 787 788 _LIBCPP_INLINE_VISIBILITY 789 size_type count(const key_type& __k) const 790 {return __tree_.__count_unique(__k);} 791#if _LIBCPP_STD_VER > 11 792 template <typename _K2> 793 _LIBCPP_INLINE_VISIBILITY 794 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 795 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 796#endif 797 798#if _LIBCPP_STD_VER > 17 799 _LIBCPP_INLINE_VISIBILITY 800 bool contains(const key_type& __k) const {return find(__k) != end();} 801#endif // _LIBCPP_STD_VER > 17 802 803 _LIBCPP_INLINE_VISIBILITY 804 iterator lower_bound(const key_type& __k) 805 {return __tree_.lower_bound(__k);} 806 _LIBCPP_INLINE_VISIBILITY 807 const_iterator lower_bound(const key_type& __k) const 808 {return __tree_.lower_bound(__k);} 809#if _LIBCPP_STD_VER > 11 810 template <typename _K2> 811 _LIBCPP_INLINE_VISIBILITY 812 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 813 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 814 815 template <typename _K2> 816 _LIBCPP_INLINE_VISIBILITY 817 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 818 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 819#endif 820 821 _LIBCPP_INLINE_VISIBILITY 822 iterator upper_bound(const key_type& __k) 823 {return __tree_.upper_bound(__k);} 824 _LIBCPP_INLINE_VISIBILITY 825 const_iterator upper_bound(const key_type& __k) const 826 {return __tree_.upper_bound(__k);} 827#if _LIBCPP_STD_VER > 11 828 template <typename _K2> 829 _LIBCPP_INLINE_VISIBILITY 830 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 831 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 832 template <typename _K2> 833 _LIBCPP_INLINE_VISIBILITY 834 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 835 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 836#endif 837 838 _LIBCPP_INLINE_VISIBILITY 839 pair<iterator,iterator> equal_range(const key_type& __k) 840 {return __tree_.__equal_range_unique(__k);} 841 _LIBCPP_INLINE_VISIBILITY 842 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 843 {return __tree_.__equal_range_unique(__k);} 844#if _LIBCPP_STD_VER > 11 845 template <typename _K2> 846 _LIBCPP_INLINE_VISIBILITY 847 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 848 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 849 template <typename _K2> 850 _LIBCPP_INLINE_VISIBILITY 851 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 852 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 853#endif 854}; 855 856#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 857template<class _InputIterator, 858 class _Compare = less<__iter_value_type<_InputIterator>>, 859 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 860 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 861 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 862set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 863 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 864 865template<class _Key, class _Compare = less<_Key>, 866 class _Allocator = allocator<_Key>, 867 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 868 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 869set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 870 -> set<_Key, _Compare, _Allocator>; 871 872template<class _InputIterator, class _Allocator, 873 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 874set(_InputIterator, _InputIterator, _Allocator) 875 -> set<__iter_value_type<_InputIterator>, 876 less<__iter_value_type<_InputIterator>>, _Allocator>; 877 878template<class _Key, class _Allocator, 879 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 880set(initializer_list<_Key>, _Allocator) 881 -> set<_Key, less<_Key>, _Allocator>; 882#endif 883 884#ifndef _LIBCPP_CXX03_LANG 885 886template <class _Key, class _Compare, class _Allocator> 887set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 888 : __tree_(_VSTD::move(__s.__tree_), __a) 889{ 890 if (__a != __s.get_allocator()) 891 { 892 const_iterator __e = cend(); 893 while (!__s.empty()) 894 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 895 } 896} 897 898#endif // _LIBCPP_CXX03_LANG 899 900template <class _Key, class _Compare, class _Allocator> 901inline _LIBCPP_INLINE_VISIBILITY 902bool 903operator==(const set<_Key, _Compare, _Allocator>& __x, 904 const set<_Key, _Compare, _Allocator>& __y) 905{ 906 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 907} 908 909template <class _Key, class _Compare, class _Allocator> 910inline _LIBCPP_INLINE_VISIBILITY 911bool 912operator< (const set<_Key, _Compare, _Allocator>& __x, 913 const set<_Key, _Compare, _Allocator>& __y) 914{ 915 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 916} 917 918template <class _Key, class _Compare, class _Allocator> 919inline _LIBCPP_INLINE_VISIBILITY 920bool 921operator!=(const set<_Key, _Compare, _Allocator>& __x, 922 const set<_Key, _Compare, _Allocator>& __y) 923{ 924 return !(__x == __y); 925} 926 927template <class _Key, class _Compare, class _Allocator> 928inline _LIBCPP_INLINE_VISIBILITY 929bool 930operator> (const set<_Key, _Compare, _Allocator>& __x, 931 const set<_Key, _Compare, _Allocator>& __y) 932{ 933 return __y < __x; 934} 935 936template <class _Key, class _Compare, class _Allocator> 937inline _LIBCPP_INLINE_VISIBILITY 938bool 939operator>=(const set<_Key, _Compare, _Allocator>& __x, 940 const set<_Key, _Compare, _Allocator>& __y) 941{ 942 return !(__x < __y); 943} 944 945template <class _Key, class _Compare, class _Allocator> 946inline _LIBCPP_INLINE_VISIBILITY 947bool 948operator<=(const set<_Key, _Compare, _Allocator>& __x, 949 const set<_Key, _Compare, _Allocator>& __y) 950{ 951 return !(__y < __x); 952} 953 954// specialized algorithms: 955template <class _Key, class _Compare, class _Allocator> 956inline _LIBCPP_INLINE_VISIBILITY 957void 958swap(set<_Key, _Compare, _Allocator>& __x, 959 set<_Key, _Compare, _Allocator>& __y) 960 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 961{ 962 __x.swap(__y); 963} 964 965#if _LIBCPP_STD_VER > 17 966template <class _Key, class _Compare, class _Allocator, class _Predicate> 967inline _LIBCPP_INLINE_VISIBILITY 968 typename set<_Key, _Compare, _Allocator>::size_type 969 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 970 return _VSTD::__libcpp_erase_if_container(__c, __pred); 971} 972#endif 973 974template <class _Key, class _Compare = less<_Key>, 975 class _Allocator = allocator<_Key> > 976class _LIBCPP_TEMPLATE_VIS multiset 977{ 978public: 979 // types: 980 typedef _Key key_type; 981 typedef key_type value_type; 982 typedef _Compare key_compare; 983 typedef key_compare value_compare; 984 typedef __identity_t<_Allocator> allocator_type; 985 typedef value_type& reference; 986 typedef const value_type& const_reference; 987 988 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 989 "Allocator::value_type must be same type as value_type"); 990 991private: 992 typedef __tree<value_type, value_compare, allocator_type> __base; 993 typedef allocator_traits<allocator_type> __alloc_traits; 994 typedef typename __base::__node_holder __node_holder; 995 996 __base __tree_; 997 998public: 999 typedef typename __base::pointer pointer; 1000 typedef typename __base::const_pointer const_pointer; 1001 typedef typename __base::size_type size_type; 1002 typedef typename __base::difference_type difference_type; 1003 typedef typename __base::const_iterator iterator; 1004 typedef typename __base::const_iterator const_iterator; 1005 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1006 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1007 1008#if _LIBCPP_STD_VER > 14 1009 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 1010#endif 1011 1012 template <class _Key2, class _Compare2, class _Alloc2> 1013 friend class _LIBCPP_TEMPLATE_VIS set; 1014 template <class _Key2, class _Compare2, class _Alloc2> 1015 friend class _LIBCPP_TEMPLATE_VIS multiset; 1016 1017 // construct/copy/destroy: 1018 _LIBCPP_INLINE_VISIBILITY 1019 multiset() 1020 _NOEXCEPT_( 1021 is_nothrow_default_constructible<allocator_type>::value && 1022 is_nothrow_default_constructible<key_compare>::value && 1023 is_nothrow_copy_constructible<key_compare>::value) 1024 : __tree_(value_compare()) {} 1025 1026 _LIBCPP_INLINE_VISIBILITY 1027 explicit multiset(const value_compare& __comp) 1028 _NOEXCEPT_( 1029 is_nothrow_default_constructible<allocator_type>::value && 1030 is_nothrow_copy_constructible<key_compare>::value) 1031 : __tree_(__comp) {} 1032 1033 _LIBCPP_INLINE_VISIBILITY 1034 explicit multiset(const value_compare& __comp, const allocator_type& __a) 1035 : __tree_(__comp, __a) {} 1036 template <class _InputIterator> 1037 _LIBCPP_INLINE_VISIBILITY 1038 multiset(_InputIterator __f, _InputIterator __l, 1039 const value_compare& __comp = value_compare()) 1040 : __tree_(__comp) 1041 { 1042 insert(__f, __l); 1043 } 1044 1045#if _LIBCPP_STD_VER > 11 1046 template <class _InputIterator> 1047 _LIBCPP_INLINE_VISIBILITY 1048 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1049 : multiset(__f, __l, key_compare(), __a) {} 1050#endif 1051 1052 template <class _InputIterator> 1053 _LIBCPP_INLINE_VISIBILITY 1054 multiset(_InputIterator __f, _InputIterator __l, 1055 const value_compare& __comp, const allocator_type& __a) 1056 : __tree_(__comp, __a) 1057 { 1058 insert(__f, __l); 1059 } 1060 1061 _LIBCPP_INLINE_VISIBILITY 1062 multiset(const multiset& __s) 1063 : __tree_(__s.__tree_.value_comp(), 1064 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 1065 { 1066 insert(__s.begin(), __s.end()); 1067 } 1068 1069 _LIBCPP_INLINE_VISIBILITY 1070 multiset& operator=(const multiset& __s) 1071 { 1072 __tree_ = __s.__tree_; 1073 return *this; 1074 } 1075 1076#ifndef _LIBCPP_CXX03_LANG 1077 _LIBCPP_INLINE_VISIBILITY 1078 multiset(multiset&& __s) 1079 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1080 : __tree_(_VSTD::move(__s.__tree_)) {} 1081 1082 multiset(multiset&& __s, const allocator_type& __a); 1083#endif // _LIBCPP_CXX03_LANG 1084 _LIBCPP_INLINE_VISIBILITY 1085 explicit multiset(const allocator_type& __a) 1086 : __tree_(__a) {} 1087 _LIBCPP_INLINE_VISIBILITY 1088 multiset(const multiset& __s, const allocator_type& __a) 1089 : __tree_(__s.__tree_.value_comp(), __a) 1090 { 1091 insert(__s.begin(), __s.end()); 1092 } 1093 1094#ifndef _LIBCPP_CXX03_LANG 1095 _LIBCPP_INLINE_VISIBILITY 1096 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 1097 : __tree_(__comp) 1098 { 1099 insert(__il.begin(), __il.end()); 1100 } 1101 1102 _LIBCPP_INLINE_VISIBILITY 1103 multiset(initializer_list<value_type> __il, const value_compare& __comp, 1104 const allocator_type& __a) 1105 : __tree_(__comp, __a) 1106 { 1107 insert(__il.begin(), __il.end()); 1108 } 1109 1110#if _LIBCPP_STD_VER > 11 1111 _LIBCPP_INLINE_VISIBILITY 1112 multiset(initializer_list<value_type> __il, const allocator_type& __a) 1113 : multiset(__il, key_compare(), __a) {} 1114#endif 1115 1116 _LIBCPP_INLINE_VISIBILITY 1117 multiset& operator=(initializer_list<value_type> __il) 1118 { 1119 __tree_.__assign_multi(__il.begin(), __il.end()); 1120 return *this; 1121 } 1122 1123 _LIBCPP_INLINE_VISIBILITY 1124 multiset& operator=(multiset&& __s) 1125 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1126 { 1127 __tree_ = _VSTD::move(__s.__tree_); 1128 return *this; 1129 } 1130#endif // _LIBCPP_CXX03_LANG 1131 1132 _LIBCPP_INLINE_VISIBILITY 1133 ~multiset() { 1134 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1135 } 1136 1137 _LIBCPP_INLINE_VISIBILITY 1138 iterator begin() _NOEXCEPT {return __tree_.begin();} 1139 _LIBCPP_INLINE_VISIBILITY 1140 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1141 _LIBCPP_INLINE_VISIBILITY 1142 iterator end() _NOEXCEPT {return __tree_.end();} 1143 _LIBCPP_INLINE_VISIBILITY 1144 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1145 1146 _LIBCPP_INLINE_VISIBILITY 1147 reverse_iterator rbegin() _NOEXCEPT 1148 {return reverse_iterator(end());} 1149 _LIBCPP_INLINE_VISIBILITY 1150 const_reverse_iterator rbegin() const _NOEXCEPT 1151 {return const_reverse_iterator(end());} 1152 _LIBCPP_INLINE_VISIBILITY 1153 reverse_iterator rend() _NOEXCEPT 1154 {return reverse_iterator(begin());} 1155 _LIBCPP_INLINE_VISIBILITY 1156 const_reverse_iterator rend() const _NOEXCEPT 1157 {return const_reverse_iterator(begin());} 1158 1159 _LIBCPP_INLINE_VISIBILITY 1160 const_iterator cbegin() const _NOEXCEPT {return begin();} 1161 _LIBCPP_INLINE_VISIBILITY 1162 const_iterator cend() const _NOEXCEPT {return end();} 1163 _LIBCPP_INLINE_VISIBILITY 1164 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1165 _LIBCPP_INLINE_VISIBILITY 1166 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1167 1168 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1169 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1170 _LIBCPP_INLINE_VISIBILITY 1171 size_type size() const _NOEXCEPT {return __tree_.size();} 1172 _LIBCPP_INLINE_VISIBILITY 1173 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1174 1175 // modifiers: 1176#ifndef _LIBCPP_CXX03_LANG 1177 template <class... _Args> 1178 _LIBCPP_INLINE_VISIBILITY 1179 iterator emplace(_Args&&... __args) 1180 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1181 template <class... _Args> 1182 _LIBCPP_INLINE_VISIBILITY 1183 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1184 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1185#endif // _LIBCPP_CXX03_LANG 1186 1187 _LIBCPP_INLINE_VISIBILITY 1188 iterator insert(const value_type& __v) 1189 {return __tree_.__insert_multi(__v);} 1190 _LIBCPP_INLINE_VISIBILITY 1191 iterator insert(const_iterator __p, const value_type& __v) 1192 {return __tree_.__insert_multi(__p, __v);} 1193 1194 template <class _InputIterator> 1195 _LIBCPP_INLINE_VISIBILITY 1196 void insert(_InputIterator __f, _InputIterator __l) 1197 { 1198 for (const_iterator __e = cend(); __f != __l; ++__f) 1199 __tree_.__insert_multi(__e, *__f); 1200 } 1201 1202#ifndef _LIBCPP_CXX03_LANG 1203 _LIBCPP_INLINE_VISIBILITY 1204 iterator insert(value_type&& __v) 1205 {return __tree_.__insert_multi(_VSTD::move(__v));} 1206 1207 _LIBCPP_INLINE_VISIBILITY 1208 iterator insert(const_iterator __p, value_type&& __v) 1209 {return __tree_.__insert_multi(__p, _VSTD::move(__v));} 1210 1211 _LIBCPP_INLINE_VISIBILITY 1212 void insert(initializer_list<value_type> __il) 1213 {insert(__il.begin(), __il.end());} 1214#endif // _LIBCPP_CXX03_LANG 1215 1216 _LIBCPP_INLINE_VISIBILITY 1217 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1218 _LIBCPP_INLINE_VISIBILITY 1219 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1220 _LIBCPP_INLINE_VISIBILITY 1221 iterator erase(const_iterator __f, const_iterator __l) 1222 {return __tree_.erase(__f, __l);} 1223 _LIBCPP_INLINE_VISIBILITY 1224 void clear() _NOEXCEPT {__tree_.clear();} 1225 1226#if _LIBCPP_STD_VER > 14 1227 _LIBCPP_INLINE_VISIBILITY 1228 iterator insert(node_type&& __nh) 1229 { 1230 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1231 "node_type with incompatible allocator passed to multiset::insert()"); 1232 return __tree_.template __node_handle_insert_multi<node_type>( 1233 _VSTD::move(__nh)); 1234 } 1235 _LIBCPP_INLINE_VISIBILITY 1236 iterator insert(const_iterator __hint, node_type&& __nh) 1237 { 1238 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1239 "node_type with incompatible allocator passed to multiset::insert()"); 1240 return __tree_.template __node_handle_insert_multi<node_type>( 1241 __hint, _VSTD::move(__nh)); 1242 } 1243 _LIBCPP_INLINE_VISIBILITY 1244 node_type extract(key_type const& __key) 1245 { 1246 return __tree_.template __node_handle_extract<node_type>(__key); 1247 } 1248 _LIBCPP_INLINE_VISIBILITY 1249 node_type extract(const_iterator __it) 1250 { 1251 return __tree_.template __node_handle_extract<node_type>(__it); 1252 } 1253 template <class _Compare2> 1254 _LIBCPP_INLINE_VISIBILITY 1255 void merge(multiset<key_type, _Compare2, allocator_type>& __source) 1256 { 1257 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1258 "merging container with incompatible allocator"); 1259 __tree_.__node_handle_merge_multi(__source.__tree_); 1260 } 1261 template <class _Compare2> 1262 _LIBCPP_INLINE_VISIBILITY 1263 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 1264 { 1265 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1266 "merging container with incompatible allocator"); 1267 __tree_.__node_handle_merge_multi(__source.__tree_); 1268 } 1269 template <class _Compare2> 1270 _LIBCPP_INLINE_VISIBILITY 1271 void merge(set<key_type, _Compare2, allocator_type>& __source) 1272 { 1273 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1274 "merging container with incompatible allocator"); 1275 __tree_.__node_handle_merge_multi(__source.__tree_); 1276 } 1277 template <class _Compare2> 1278 _LIBCPP_INLINE_VISIBILITY 1279 void merge(set<key_type, _Compare2, allocator_type>&& __source) 1280 { 1281 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1282 "merging container with incompatible allocator"); 1283 __tree_.__node_handle_merge_multi(__source.__tree_); 1284 } 1285#endif 1286 1287 _LIBCPP_INLINE_VISIBILITY 1288 void swap(multiset& __s) 1289 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1290 {__tree_.swap(__s.__tree_);} 1291 1292 _LIBCPP_INLINE_VISIBILITY 1293 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1294 _LIBCPP_INLINE_VISIBILITY 1295 key_compare key_comp() const {return __tree_.value_comp();} 1296 _LIBCPP_INLINE_VISIBILITY 1297 value_compare value_comp() const {return __tree_.value_comp();} 1298 1299 // set operations: 1300 _LIBCPP_INLINE_VISIBILITY 1301 iterator find(const key_type& __k) {return __tree_.find(__k);} 1302 _LIBCPP_INLINE_VISIBILITY 1303 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1304#if _LIBCPP_STD_VER > 11 1305 template <typename _K2> 1306 _LIBCPP_INLINE_VISIBILITY 1307 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1308 find(const _K2& __k) {return __tree_.find(__k);} 1309 template <typename _K2> 1310 _LIBCPP_INLINE_VISIBILITY 1311 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1312 find(const _K2& __k) const {return __tree_.find(__k);} 1313#endif 1314 1315 _LIBCPP_INLINE_VISIBILITY 1316 size_type count(const key_type& __k) const 1317 {return __tree_.__count_multi(__k);} 1318#if _LIBCPP_STD_VER > 11 1319 template <typename _K2> 1320 _LIBCPP_INLINE_VISIBILITY 1321 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1322 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1323#endif 1324 1325#if _LIBCPP_STD_VER > 17 1326 _LIBCPP_INLINE_VISIBILITY 1327 bool contains(const key_type& __k) const {return find(__k) != end();} 1328#endif // _LIBCPP_STD_VER > 17 1329 1330 _LIBCPP_INLINE_VISIBILITY 1331 iterator lower_bound(const key_type& __k) 1332 {return __tree_.lower_bound(__k);} 1333 _LIBCPP_INLINE_VISIBILITY 1334 const_iterator lower_bound(const key_type& __k) const 1335 {return __tree_.lower_bound(__k);} 1336#if _LIBCPP_STD_VER > 11 1337 template <typename _K2> 1338 _LIBCPP_INLINE_VISIBILITY 1339 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1340 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1341 1342 template <typename _K2> 1343 _LIBCPP_INLINE_VISIBILITY 1344 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1345 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1346#endif 1347 1348 _LIBCPP_INLINE_VISIBILITY 1349 iterator upper_bound(const key_type& __k) 1350 {return __tree_.upper_bound(__k);} 1351 _LIBCPP_INLINE_VISIBILITY 1352 const_iterator upper_bound(const key_type& __k) const 1353 {return __tree_.upper_bound(__k);} 1354#if _LIBCPP_STD_VER > 11 1355 template <typename _K2> 1356 _LIBCPP_INLINE_VISIBILITY 1357 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1358 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1359 template <typename _K2> 1360 _LIBCPP_INLINE_VISIBILITY 1361 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1362 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1363#endif 1364 1365 _LIBCPP_INLINE_VISIBILITY 1366 pair<iterator,iterator> equal_range(const key_type& __k) 1367 {return __tree_.__equal_range_multi(__k);} 1368 _LIBCPP_INLINE_VISIBILITY 1369 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1370 {return __tree_.__equal_range_multi(__k);} 1371#if _LIBCPP_STD_VER > 11 1372 template <typename _K2> 1373 _LIBCPP_INLINE_VISIBILITY 1374 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1375 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1376 template <typename _K2> 1377 _LIBCPP_INLINE_VISIBILITY 1378 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1379 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1380#endif 1381}; 1382 1383#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 1384template<class _InputIterator, 1385 class _Compare = less<__iter_value_type<_InputIterator>>, 1386 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1387 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 1388 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 1389multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1390 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 1391 1392template<class _Key, class _Compare = less<_Key>, 1393 class _Allocator = allocator<_Key>, 1394 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 1395 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 1396multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 1397 -> multiset<_Key, _Compare, _Allocator>; 1398 1399template<class _InputIterator, class _Allocator, 1400 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1401multiset(_InputIterator, _InputIterator, _Allocator) 1402 -> multiset<__iter_value_type<_InputIterator>, 1403 less<__iter_value_type<_InputIterator>>, _Allocator>; 1404 1405template<class _Key, class _Allocator, 1406 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1407multiset(initializer_list<_Key>, _Allocator) 1408 -> multiset<_Key, less<_Key>, _Allocator>; 1409#endif 1410 1411#ifndef _LIBCPP_CXX03_LANG 1412 1413template <class _Key, class _Compare, class _Allocator> 1414multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1415 : __tree_(_VSTD::move(__s.__tree_), __a) 1416{ 1417 if (__a != __s.get_allocator()) 1418 { 1419 const_iterator __e = cend(); 1420 while (!__s.empty()) 1421 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1422 } 1423} 1424 1425#endif // _LIBCPP_CXX03_LANG 1426 1427template <class _Key, class _Compare, class _Allocator> 1428inline _LIBCPP_INLINE_VISIBILITY 1429bool 1430operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1431 const multiset<_Key, _Compare, _Allocator>& __y) 1432{ 1433 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1434} 1435 1436template <class _Key, class _Compare, class _Allocator> 1437inline _LIBCPP_INLINE_VISIBILITY 1438bool 1439operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1440 const multiset<_Key, _Compare, _Allocator>& __y) 1441{ 1442 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1443} 1444 1445template <class _Key, class _Compare, class _Allocator> 1446inline _LIBCPP_INLINE_VISIBILITY 1447bool 1448operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1449 const multiset<_Key, _Compare, _Allocator>& __y) 1450{ 1451 return !(__x == __y); 1452} 1453 1454template <class _Key, class _Compare, class _Allocator> 1455inline _LIBCPP_INLINE_VISIBILITY 1456bool 1457operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1458 const multiset<_Key, _Compare, _Allocator>& __y) 1459{ 1460 return __y < __x; 1461} 1462 1463template <class _Key, class _Compare, class _Allocator> 1464inline _LIBCPP_INLINE_VISIBILITY 1465bool 1466operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1467 const multiset<_Key, _Compare, _Allocator>& __y) 1468{ 1469 return !(__x < __y); 1470} 1471 1472template <class _Key, class _Compare, class _Allocator> 1473inline _LIBCPP_INLINE_VISIBILITY 1474bool 1475operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1476 const multiset<_Key, _Compare, _Allocator>& __y) 1477{ 1478 return !(__y < __x); 1479} 1480 1481template <class _Key, class _Compare, class _Allocator> 1482inline _LIBCPP_INLINE_VISIBILITY 1483void 1484swap(multiset<_Key, _Compare, _Allocator>& __x, 1485 multiset<_Key, _Compare, _Allocator>& __y) 1486 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1487{ 1488 __x.swap(__y); 1489} 1490 1491#if _LIBCPP_STD_VER > 17 1492template <class _Key, class _Compare, class _Allocator, class _Predicate> 1493inline _LIBCPP_INLINE_VISIBILITY 1494 typename multiset<_Key, _Compare, _Allocator>::size_type 1495 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 1496 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1497} 1498#endif 1499 1500_LIBCPP_END_NAMESPACE_STD 1501 1502#endif // _LIBCPP_SET 1503