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 <functional> 432#include <iterator> // __libcpp_erase_if_container 433#include <version> 434 435#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 436#pragma GCC system_header 437#endif 438 439_LIBCPP_BEGIN_NAMESPACE_STD 440 441template <class _Key, class _Compare, class _Allocator> 442class multiset; 443 444template <class _Key, class _Compare = less<_Key>, 445 class _Allocator = allocator<_Key> > 446class _LIBCPP_TEMPLATE_VIS set 447{ 448public: 449 // types: 450 typedef _Key key_type; 451 typedef key_type value_type; 452 typedef _Compare key_compare; 453 typedef key_compare value_compare; 454 typedef __identity_t<_Allocator> allocator_type; 455 typedef value_type& reference; 456 typedef const value_type& const_reference; 457 458 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 459 "Allocator::value_type must be same type as value_type"); 460 461private: 462 typedef __tree<value_type, value_compare, allocator_type> __base; 463 typedef allocator_traits<allocator_type> __alloc_traits; 464 typedef typename __base::__node_holder __node_holder; 465 466 __base __tree_; 467 468public: 469 typedef typename __base::pointer pointer; 470 typedef typename __base::const_pointer const_pointer; 471 typedef typename __base::size_type size_type; 472 typedef typename __base::difference_type difference_type; 473 typedef typename __base::const_iterator iterator; 474 typedef typename __base::const_iterator const_iterator; 475 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 476 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 477 478#if _LIBCPP_STD_VER > 14 479 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 480 typedef __insert_return_type<iterator, node_type> insert_return_type; 481#endif 482 483 template <class _Key2, class _Compare2, class _Alloc2> 484 friend class _LIBCPP_TEMPLATE_VIS set; 485 template <class _Key2, class _Compare2, class _Alloc2> 486 friend class _LIBCPP_TEMPLATE_VIS multiset; 487 488 _LIBCPP_INLINE_VISIBILITY 489 set() 490 _NOEXCEPT_( 491 is_nothrow_default_constructible<allocator_type>::value && 492 is_nothrow_default_constructible<key_compare>::value && 493 is_nothrow_copy_constructible<key_compare>::value) 494 : __tree_(value_compare()) {} 495 496 _LIBCPP_INLINE_VISIBILITY 497 explicit set(const value_compare& __comp) 498 _NOEXCEPT_( 499 is_nothrow_default_constructible<allocator_type>::value && 500 is_nothrow_copy_constructible<key_compare>::value) 501 : __tree_(__comp) {} 502 503 _LIBCPP_INLINE_VISIBILITY 504 explicit set(const value_compare& __comp, const allocator_type& __a) 505 : __tree_(__comp, __a) {} 506 template <class _InputIterator> 507 _LIBCPP_INLINE_VISIBILITY 508 set(_InputIterator __f, _InputIterator __l, 509 const value_compare& __comp = value_compare()) 510 : __tree_(__comp) 511 { 512 insert(__f, __l); 513 } 514 515 template <class _InputIterator> 516 _LIBCPP_INLINE_VISIBILITY 517 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 518 const allocator_type& __a) 519 : __tree_(__comp, __a) 520 { 521 insert(__f, __l); 522 } 523 524#if _LIBCPP_STD_VER > 11 525 template <class _InputIterator> 526 _LIBCPP_INLINE_VISIBILITY 527 set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 528 : set(__f, __l, key_compare(), __a) {} 529#endif 530 531 _LIBCPP_INLINE_VISIBILITY 532 set(const set& __s) 533 : __tree_(__s.__tree_) 534 { 535 insert(__s.begin(), __s.end()); 536 } 537 538 _LIBCPP_INLINE_VISIBILITY 539 set& operator=(const set& __s) 540 { 541 __tree_ = __s.__tree_; 542 return *this; 543 } 544 545#ifndef _LIBCPP_CXX03_LANG 546 _LIBCPP_INLINE_VISIBILITY 547 set(set&& __s) 548 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 549 : __tree_(_VSTD::move(__s.__tree_)) {} 550#endif // _LIBCPP_CXX03_LANG 551 552 _LIBCPP_INLINE_VISIBILITY 553 explicit set(const allocator_type& __a) 554 : __tree_(__a) {} 555 556 _LIBCPP_INLINE_VISIBILITY 557 set(const set& __s, const allocator_type& __a) 558 : __tree_(__s.__tree_.value_comp(), __a) 559 { 560 insert(__s.begin(), __s.end()); 561 } 562 563#ifndef _LIBCPP_CXX03_LANG 564 set(set&& __s, const allocator_type& __a); 565 566 _LIBCPP_INLINE_VISIBILITY 567 set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 568 : __tree_(__comp) 569 { 570 insert(__il.begin(), __il.end()); 571 } 572 573 _LIBCPP_INLINE_VISIBILITY 574 set(initializer_list<value_type> __il, const value_compare& __comp, 575 const allocator_type& __a) 576 : __tree_(__comp, __a) 577 { 578 insert(__il.begin(), __il.end()); 579 } 580 581#if _LIBCPP_STD_VER > 11 582 _LIBCPP_INLINE_VISIBILITY 583 set(initializer_list<value_type> __il, const allocator_type& __a) 584 : set(__il, key_compare(), __a) {} 585#endif 586 587 _LIBCPP_INLINE_VISIBILITY 588 set& operator=(initializer_list<value_type> __il) 589 { 590 __tree_.__assign_unique(__il.begin(), __il.end()); 591 return *this; 592 } 593 594 _LIBCPP_INLINE_VISIBILITY 595 set& operator=(set&& __s) 596 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 597 { 598 __tree_ = _VSTD::move(__s.__tree_); 599 return *this; 600 } 601#endif // _LIBCPP_CXX03_LANG 602 603 _LIBCPP_INLINE_VISIBILITY 604 ~set() { 605 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 606 } 607 608 _LIBCPP_INLINE_VISIBILITY 609 iterator begin() _NOEXCEPT {return __tree_.begin();} 610 _LIBCPP_INLINE_VISIBILITY 611 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 612 _LIBCPP_INLINE_VISIBILITY 613 iterator end() _NOEXCEPT {return __tree_.end();} 614 _LIBCPP_INLINE_VISIBILITY 615 const_iterator end() const _NOEXCEPT {return __tree_.end();} 616 617 _LIBCPP_INLINE_VISIBILITY 618 reverse_iterator rbegin() _NOEXCEPT 619 {return reverse_iterator(end());} 620 _LIBCPP_INLINE_VISIBILITY 621 const_reverse_iterator rbegin() const _NOEXCEPT 622 {return const_reverse_iterator(end());} 623 _LIBCPP_INLINE_VISIBILITY 624 reverse_iterator rend() _NOEXCEPT 625 {return reverse_iterator(begin());} 626 _LIBCPP_INLINE_VISIBILITY 627 const_reverse_iterator rend() const _NOEXCEPT 628 {return const_reverse_iterator(begin());} 629 630 _LIBCPP_INLINE_VISIBILITY 631 const_iterator cbegin() const _NOEXCEPT {return begin();} 632 _LIBCPP_INLINE_VISIBILITY 633 const_iterator cend() const _NOEXCEPT {return end();} 634 _LIBCPP_INLINE_VISIBILITY 635 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 636 _LIBCPP_INLINE_VISIBILITY 637 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 638 639 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 640 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 641 _LIBCPP_INLINE_VISIBILITY 642 size_type size() const _NOEXCEPT {return __tree_.size();} 643 _LIBCPP_INLINE_VISIBILITY 644 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 645 646 // modifiers: 647#ifndef _LIBCPP_CXX03_LANG 648 template <class... _Args> 649 _LIBCPP_INLINE_VISIBILITY 650 pair<iterator, bool> emplace(_Args&&... __args) 651 {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 652 template <class... _Args> 653 _LIBCPP_INLINE_VISIBILITY 654 iterator emplace_hint(const_iterator __p, _Args&&... __args) 655 {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 656#endif // _LIBCPP_CXX03_LANG 657 658 _LIBCPP_INLINE_VISIBILITY 659 pair<iterator,bool> insert(const value_type& __v) 660 {return __tree_.__insert_unique(__v);} 661 _LIBCPP_INLINE_VISIBILITY 662 iterator insert(const_iterator __p, const value_type& __v) 663 {return __tree_.__insert_unique(__p, __v);} 664 665 template <class _InputIterator> 666 _LIBCPP_INLINE_VISIBILITY 667 void insert(_InputIterator __f, _InputIterator __l) 668 { 669 for (const_iterator __e = cend(); __f != __l; ++__f) 670 __tree_.__insert_unique(__e, *__f); 671 } 672 673#ifndef _LIBCPP_CXX03_LANG 674 _LIBCPP_INLINE_VISIBILITY 675 pair<iterator,bool> insert(value_type&& __v) 676 {return __tree_.__insert_unique(_VSTD::move(__v));} 677 678 _LIBCPP_INLINE_VISIBILITY 679 iterator insert(const_iterator __p, value_type&& __v) 680 {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 681 682 _LIBCPP_INLINE_VISIBILITY 683 void insert(initializer_list<value_type> __il) 684 {insert(__il.begin(), __il.end());} 685#endif // _LIBCPP_CXX03_LANG 686 687 _LIBCPP_INLINE_VISIBILITY 688 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 689 _LIBCPP_INLINE_VISIBILITY 690 size_type erase(const key_type& __k) 691 {return __tree_.__erase_unique(__k);} 692 _LIBCPP_INLINE_VISIBILITY 693 iterator erase(const_iterator __f, const_iterator __l) 694 {return __tree_.erase(__f, __l);} 695 _LIBCPP_INLINE_VISIBILITY 696 void clear() _NOEXCEPT {__tree_.clear();} 697 698#if _LIBCPP_STD_VER > 14 699 _LIBCPP_INLINE_VISIBILITY 700 insert_return_type insert(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< 705 node_type, insert_return_type>(_VSTD::move(__nh)); 706 } 707 _LIBCPP_INLINE_VISIBILITY 708 iterator insert(const_iterator __hint, node_type&& __nh) 709 { 710 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 711 "node_type with incompatible allocator passed to set::insert()"); 712 return __tree_.template __node_handle_insert_unique<node_type>( 713 __hint, _VSTD::move(__nh)); 714 } 715 _LIBCPP_INLINE_VISIBILITY 716 node_type extract(key_type const& __key) 717 { 718 return __tree_.template __node_handle_extract<node_type>(__key); 719 } 720 _LIBCPP_INLINE_VISIBILITY 721 node_type extract(const_iterator __it) 722 { 723 return __tree_.template __node_handle_extract<node_type>(__it); 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(set<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 template <class _Compare2> 750 _LIBCPP_INLINE_VISIBILITY 751 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 752 { 753 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 754 "merging container with incompatible allocator"); 755 __tree_.__node_handle_merge_unique(__source.__tree_); 756 } 757#endif 758 759 _LIBCPP_INLINE_VISIBILITY 760 void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 761 {__tree_.swap(__s.__tree_);} 762 763 _LIBCPP_INLINE_VISIBILITY 764 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 765 _LIBCPP_INLINE_VISIBILITY 766 key_compare key_comp() const {return __tree_.value_comp();} 767 _LIBCPP_INLINE_VISIBILITY 768 value_compare value_comp() const {return __tree_.value_comp();} 769 770 // set operations: 771 _LIBCPP_INLINE_VISIBILITY 772 iterator find(const key_type& __k) {return __tree_.find(__k);} 773 _LIBCPP_INLINE_VISIBILITY 774 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 775#if _LIBCPP_STD_VER > 11 776 template <typename _K2> 777 _LIBCPP_INLINE_VISIBILITY 778 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 779 find(const _K2& __k) {return __tree_.find(__k);} 780 template <typename _K2> 781 _LIBCPP_INLINE_VISIBILITY 782 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 783 find(const _K2& __k) const {return __tree_.find(__k);} 784#endif 785 786 _LIBCPP_INLINE_VISIBILITY 787 size_type count(const key_type& __k) const 788 {return __tree_.__count_unique(__k);} 789#if _LIBCPP_STD_VER > 11 790 template <typename _K2> 791 _LIBCPP_INLINE_VISIBILITY 792 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 793 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 794#endif 795 796#if _LIBCPP_STD_VER > 17 797 _LIBCPP_INLINE_VISIBILITY 798 bool contains(const key_type& __k) const {return find(__k) != end();} 799#endif // _LIBCPP_STD_VER > 17 800 801 _LIBCPP_INLINE_VISIBILITY 802 iterator lower_bound(const key_type& __k) 803 {return __tree_.lower_bound(__k);} 804 _LIBCPP_INLINE_VISIBILITY 805 const_iterator lower_bound(const key_type& __k) const 806 {return __tree_.lower_bound(__k);} 807#if _LIBCPP_STD_VER > 11 808 template <typename _K2> 809 _LIBCPP_INLINE_VISIBILITY 810 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 811 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 812 813 template <typename _K2> 814 _LIBCPP_INLINE_VISIBILITY 815 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 816 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 817#endif 818 819 _LIBCPP_INLINE_VISIBILITY 820 iterator upper_bound(const key_type& __k) 821 {return __tree_.upper_bound(__k);} 822 _LIBCPP_INLINE_VISIBILITY 823 const_iterator upper_bound(const key_type& __k) const 824 {return __tree_.upper_bound(__k);} 825#if _LIBCPP_STD_VER > 11 826 template <typename _K2> 827 _LIBCPP_INLINE_VISIBILITY 828 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 829 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 830 template <typename _K2> 831 _LIBCPP_INLINE_VISIBILITY 832 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 833 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 834#endif 835 836 _LIBCPP_INLINE_VISIBILITY 837 pair<iterator,iterator> equal_range(const key_type& __k) 838 {return __tree_.__equal_range_unique(__k);} 839 _LIBCPP_INLINE_VISIBILITY 840 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 841 {return __tree_.__equal_range_unique(__k);} 842#if _LIBCPP_STD_VER > 11 843 template <typename _K2> 844 _LIBCPP_INLINE_VISIBILITY 845 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 846 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 847 template <typename _K2> 848 _LIBCPP_INLINE_VISIBILITY 849 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 850 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 851#endif 852}; 853 854#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 855template<class _InputIterator, 856 class _Compare = less<__iter_value_type<_InputIterator>>, 857 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 858 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 859 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 860set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 861 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 862 863template<class _Key, class _Compare = less<_Key>, 864 class _Allocator = allocator<_Key>, 865 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 866 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 867set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 868 -> set<_Key, _Compare, _Allocator>; 869 870template<class _InputIterator, class _Allocator, 871 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 872set(_InputIterator, _InputIterator, _Allocator) 873 -> set<__iter_value_type<_InputIterator>, 874 less<__iter_value_type<_InputIterator>>, _Allocator>; 875 876template<class _Key, class _Allocator, 877 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 878set(initializer_list<_Key>, _Allocator) 879 -> set<_Key, less<_Key>, _Allocator>; 880#endif 881 882#ifndef _LIBCPP_CXX03_LANG 883 884template <class _Key, class _Compare, class _Allocator> 885set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 886 : __tree_(_VSTD::move(__s.__tree_), __a) 887{ 888 if (__a != __s.get_allocator()) 889 { 890 const_iterator __e = cend(); 891 while (!__s.empty()) 892 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 893 } 894} 895 896#endif // _LIBCPP_CXX03_LANG 897 898template <class _Key, class _Compare, class _Allocator> 899inline _LIBCPP_INLINE_VISIBILITY 900bool 901operator==(const set<_Key, _Compare, _Allocator>& __x, 902 const set<_Key, _Compare, _Allocator>& __y) 903{ 904 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 905} 906 907template <class _Key, class _Compare, class _Allocator> 908inline _LIBCPP_INLINE_VISIBILITY 909bool 910operator< (const set<_Key, _Compare, _Allocator>& __x, 911 const set<_Key, _Compare, _Allocator>& __y) 912{ 913 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 914} 915 916template <class _Key, class _Compare, class _Allocator> 917inline _LIBCPP_INLINE_VISIBILITY 918bool 919operator!=(const set<_Key, _Compare, _Allocator>& __x, 920 const set<_Key, _Compare, _Allocator>& __y) 921{ 922 return !(__x == __y); 923} 924 925template <class _Key, class _Compare, class _Allocator> 926inline _LIBCPP_INLINE_VISIBILITY 927bool 928operator> (const set<_Key, _Compare, _Allocator>& __x, 929 const set<_Key, _Compare, _Allocator>& __y) 930{ 931 return __y < __x; 932} 933 934template <class _Key, class _Compare, class _Allocator> 935inline _LIBCPP_INLINE_VISIBILITY 936bool 937operator>=(const set<_Key, _Compare, _Allocator>& __x, 938 const set<_Key, _Compare, _Allocator>& __y) 939{ 940 return !(__x < __y); 941} 942 943template <class _Key, class _Compare, class _Allocator> 944inline _LIBCPP_INLINE_VISIBILITY 945bool 946operator<=(const set<_Key, _Compare, _Allocator>& __x, 947 const set<_Key, _Compare, _Allocator>& __y) 948{ 949 return !(__y < __x); 950} 951 952// specialized algorithms: 953template <class _Key, class _Compare, class _Allocator> 954inline _LIBCPP_INLINE_VISIBILITY 955void 956swap(set<_Key, _Compare, _Allocator>& __x, 957 set<_Key, _Compare, _Allocator>& __y) 958 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 959{ 960 __x.swap(__y); 961} 962 963#if _LIBCPP_STD_VER > 17 964template <class _Key, class _Compare, class _Allocator, class _Predicate> 965inline _LIBCPP_INLINE_VISIBILITY 966 typename set<_Key, _Compare, _Allocator>::size_type 967 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 968 return _VSTD::__libcpp_erase_if_container(__c, __pred); 969} 970#endif 971 972template <class _Key, class _Compare = less<_Key>, 973 class _Allocator = allocator<_Key> > 974class _LIBCPP_TEMPLATE_VIS multiset 975{ 976public: 977 // types: 978 typedef _Key key_type; 979 typedef key_type value_type; 980 typedef _Compare key_compare; 981 typedef key_compare value_compare; 982 typedef __identity_t<_Allocator> allocator_type; 983 typedef value_type& reference; 984 typedef const value_type& const_reference; 985 986 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 987 "Allocator::value_type must be same type as value_type"); 988 989private: 990 typedef __tree<value_type, value_compare, allocator_type> __base; 991 typedef allocator_traits<allocator_type> __alloc_traits; 992 typedef typename __base::__node_holder __node_holder; 993 994 __base __tree_; 995 996public: 997 typedef typename __base::pointer pointer; 998 typedef typename __base::const_pointer const_pointer; 999 typedef typename __base::size_type size_type; 1000 typedef typename __base::difference_type difference_type; 1001 typedef typename __base::const_iterator iterator; 1002 typedef typename __base::const_iterator const_iterator; 1003 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1004 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1005 1006#if _LIBCPP_STD_VER > 14 1007 typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 1008#endif 1009 1010 template <class _Key2, class _Compare2, class _Alloc2> 1011 friend class _LIBCPP_TEMPLATE_VIS set; 1012 template <class _Key2, class _Compare2, class _Alloc2> 1013 friend class _LIBCPP_TEMPLATE_VIS multiset; 1014 1015 // construct/copy/destroy: 1016 _LIBCPP_INLINE_VISIBILITY 1017 multiset() 1018 _NOEXCEPT_( 1019 is_nothrow_default_constructible<allocator_type>::value && 1020 is_nothrow_default_constructible<key_compare>::value && 1021 is_nothrow_copy_constructible<key_compare>::value) 1022 : __tree_(value_compare()) {} 1023 1024 _LIBCPP_INLINE_VISIBILITY 1025 explicit multiset(const value_compare& __comp) 1026 _NOEXCEPT_( 1027 is_nothrow_default_constructible<allocator_type>::value && 1028 is_nothrow_copy_constructible<key_compare>::value) 1029 : __tree_(__comp) {} 1030 1031 _LIBCPP_INLINE_VISIBILITY 1032 explicit multiset(const value_compare& __comp, const allocator_type& __a) 1033 : __tree_(__comp, __a) {} 1034 template <class _InputIterator> 1035 _LIBCPP_INLINE_VISIBILITY 1036 multiset(_InputIterator __f, _InputIterator __l, 1037 const value_compare& __comp = value_compare()) 1038 : __tree_(__comp) 1039 { 1040 insert(__f, __l); 1041 } 1042 1043#if _LIBCPP_STD_VER > 11 1044 template <class _InputIterator> 1045 _LIBCPP_INLINE_VISIBILITY 1046 multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 1047 : multiset(__f, __l, key_compare(), __a) {} 1048#endif 1049 1050 template <class _InputIterator> 1051 _LIBCPP_INLINE_VISIBILITY 1052 multiset(_InputIterator __f, _InputIterator __l, 1053 const value_compare& __comp, const allocator_type& __a) 1054 : __tree_(__comp, __a) 1055 { 1056 insert(__f, __l); 1057 } 1058 1059 _LIBCPP_INLINE_VISIBILITY 1060 multiset(const multiset& __s) 1061 : __tree_(__s.__tree_.value_comp(), 1062 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 1063 { 1064 insert(__s.begin(), __s.end()); 1065 } 1066 1067 _LIBCPP_INLINE_VISIBILITY 1068 multiset& operator=(const multiset& __s) 1069 { 1070 __tree_ = __s.__tree_; 1071 return *this; 1072 } 1073 1074#ifndef _LIBCPP_CXX03_LANG 1075 _LIBCPP_INLINE_VISIBILITY 1076 multiset(multiset&& __s) 1077 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1078 : __tree_(_VSTD::move(__s.__tree_)) {} 1079 1080 multiset(multiset&& __s, const allocator_type& __a); 1081#endif // _LIBCPP_CXX03_LANG 1082 _LIBCPP_INLINE_VISIBILITY 1083 explicit multiset(const allocator_type& __a) 1084 : __tree_(__a) {} 1085 _LIBCPP_INLINE_VISIBILITY 1086 multiset(const multiset& __s, const allocator_type& __a) 1087 : __tree_(__s.__tree_.value_comp(), __a) 1088 { 1089 insert(__s.begin(), __s.end()); 1090 } 1091 1092#ifndef _LIBCPP_CXX03_LANG 1093 _LIBCPP_INLINE_VISIBILITY 1094 multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 1095 : __tree_(__comp) 1096 { 1097 insert(__il.begin(), __il.end()); 1098 } 1099 1100 _LIBCPP_INLINE_VISIBILITY 1101 multiset(initializer_list<value_type> __il, const value_compare& __comp, 1102 const allocator_type& __a) 1103 : __tree_(__comp, __a) 1104 { 1105 insert(__il.begin(), __il.end()); 1106 } 1107 1108#if _LIBCPP_STD_VER > 11 1109 _LIBCPP_INLINE_VISIBILITY 1110 multiset(initializer_list<value_type> __il, const allocator_type& __a) 1111 : multiset(__il, key_compare(), __a) {} 1112#endif 1113 1114 _LIBCPP_INLINE_VISIBILITY 1115 multiset& operator=(initializer_list<value_type> __il) 1116 { 1117 __tree_.__assign_multi(__il.begin(), __il.end()); 1118 return *this; 1119 } 1120 1121 _LIBCPP_INLINE_VISIBILITY 1122 multiset& operator=(multiset&& __s) 1123 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 1124 { 1125 __tree_ = _VSTD::move(__s.__tree_); 1126 return *this; 1127 } 1128#endif // _LIBCPP_CXX03_LANG 1129 1130 _LIBCPP_INLINE_VISIBILITY 1131 ~multiset() { 1132 static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 1133 } 1134 1135 _LIBCPP_INLINE_VISIBILITY 1136 iterator begin() _NOEXCEPT {return __tree_.begin();} 1137 _LIBCPP_INLINE_VISIBILITY 1138 const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 1139 _LIBCPP_INLINE_VISIBILITY 1140 iterator end() _NOEXCEPT {return __tree_.end();} 1141 _LIBCPP_INLINE_VISIBILITY 1142 const_iterator end() const _NOEXCEPT {return __tree_.end();} 1143 1144 _LIBCPP_INLINE_VISIBILITY 1145 reverse_iterator rbegin() _NOEXCEPT 1146 {return reverse_iterator(end());} 1147 _LIBCPP_INLINE_VISIBILITY 1148 const_reverse_iterator rbegin() const _NOEXCEPT 1149 {return const_reverse_iterator(end());} 1150 _LIBCPP_INLINE_VISIBILITY 1151 reverse_iterator rend() _NOEXCEPT 1152 {return reverse_iterator(begin());} 1153 _LIBCPP_INLINE_VISIBILITY 1154 const_reverse_iterator rend() const _NOEXCEPT 1155 {return const_reverse_iterator(begin());} 1156 1157 _LIBCPP_INLINE_VISIBILITY 1158 const_iterator cbegin() const _NOEXCEPT {return begin();} 1159 _LIBCPP_INLINE_VISIBILITY 1160 const_iterator cend() const _NOEXCEPT {return end();} 1161 _LIBCPP_INLINE_VISIBILITY 1162 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 1163 _LIBCPP_INLINE_VISIBILITY 1164 const_reverse_iterator crend() const _NOEXCEPT {return rend();} 1165 1166 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1167 bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 1168 _LIBCPP_INLINE_VISIBILITY 1169 size_type size() const _NOEXCEPT {return __tree_.size();} 1170 _LIBCPP_INLINE_VISIBILITY 1171 size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 1172 1173 // modifiers: 1174#ifndef _LIBCPP_CXX03_LANG 1175 template <class... _Args> 1176 _LIBCPP_INLINE_VISIBILITY 1177 iterator emplace(_Args&&... __args) 1178 {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 1179 template <class... _Args> 1180 _LIBCPP_INLINE_VISIBILITY 1181 iterator emplace_hint(const_iterator __p, _Args&&... __args) 1182 {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 1183#endif // _LIBCPP_CXX03_LANG 1184 1185 _LIBCPP_INLINE_VISIBILITY 1186 iterator insert(const value_type& __v) 1187 {return __tree_.__insert_multi(__v);} 1188 _LIBCPP_INLINE_VISIBILITY 1189 iterator insert(const_iterator __p, const value_type& __v) 1190 {return __tree_.__insert_multi(__p, __v);} 1191 1192 template <class _InputIterator> 1193 _LIBCPP_INLINE_VISIBILITY 1194 void insert(_InputIterator __f, _InputIterator __l) 1195 { 1196 for (const_iterator __e = cend(); __f != __l; ++__f) 1197 __tree_.__insert_multi(__e, *__f); 1198 } 1199 1200#ifndef _LIBCPP_CXX03_LANG 1201 _LIBCPP_INLINE_VISIBILITY 1202 iterator insert(value_type&& __v) 1203 {return __tree_.__insert_multi(_VSTD::move(__v));} 1204 1205 _LIBCPP_INLINE_VISIBILITY 1206 iterator insert(const_iterator __p, value_type&& __v) 1207 {return __tree_.__insert_multi(__p, _VSTD::move(__v));} 1208 1209 _LIBCPP_INLINE_VISIBILITY 1210 void insert(initializer_list<value_type> __il) 1211 {insert(__il.begin(), __il.end());} 1212#endif // _LIBCPP_CXX03_LANG 1213 1214 _LIBCPP_INLINE_VISIBILITY 1215 iterator erase(const_iterator __p) {return __tree_.erase(__p);} 1216 _LIBCPP_INLINE_VISIBILITY 1217 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 1218 _LIBCPP_INLINE_VISIBILITY 1219 iterator erase(const_iterator __f, const_iterator __l) 1220 {return __tree_.erase(__f, __l);} 1221 _LIBCPP_INLINE_VISIBILITY 1222 void clear() _NOEXCEPT {__tree_.clear();} 1223 1224#if _LIBCPP_STD_VER > 14 1225 _LIBCPP_INLINE_VISIBILITY 1226 iterator insert(node_type&& __nh) 1227 { 1228 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1229 "node_type with incompatible allocator passed to multiset::insert()"); 1230 return __tree_.template __node_handle_insert_multi<node_type>( 1231 _VSTD::move(__nh)); 1232 } 1233 _LIBCPP_INLINE_VISIBILITY 1234 iterator insert(const_iterator __hint, node_type&& __nh) 1235 { 1236 _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 1237 "node_type with incompatible allocator passed to multiset::insert()"); 1238 return __tree_.template __node_handle_insert_multi<node_type>( 1239 __hint, _VSTD::move(__nh)); 1240 } 1241 _LIBCPP_INLINE_VISIBILITY 1242 node_type extract(key_type const& __key) 1243 { 1244 return __tree_.template __node_handle_extract<node_type>(__key); 1245 } 1246 _LIBCPP_INLINE_VISIBILITY 1247 node_type extract(const_iterator __it) 1248 { 1249 return __tree_.template __node_handle_extract<node_type>(__it); 1250 } 1251 template <class _Compare2> 1252 _LIBCPP_INLINE_VISIBILITY 1253 void merge(multiset<key_type, _Compare2, allocator_type>& __source) 1254 { 1255 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1256 "merging container with incompatible allocator"); 1257 __tree_.__node_handle_merge_multi(__source.__tree_); 1258 } 1259 template <class _Compare2> 1260 _LIBCPP_INLINE_VISIBILITY 1261 void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 1262 { 1263 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1264 "merging container with incompatible allocator"); 1265 __tree_.__node_handle_merge_multi(__source.__tree_); 1266 } 1267 template <class _Compare2> 1268 _LIBCPP_INLINE_VISIBILITY 1269 void merge(set<key_type, _Compare2, allocator_type>& __source) 1270 { 1271 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1272 "merging container with incompatible allocator"); 1273 __tree_.__node_handle_merge_multi(__source.__tree_); 1274 } 1275 template <class _Compare2> 1276 _LIBCPP_INLINE_VISIBILITY 1277 void merge(set<key_type, _Compare2, allocator_type>&& __source) 1278 { 1279 _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 1280 "merging container with incompatible allocator"); 1281 __tree_.__node_handle_merge_multi(__source.__tree_); 1282 } 1283#endif 1284 1285 _LIBCPP_INLINE_VISIBILITY 1286 void swap(multiset& __s) 1287 _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 1288 {__tree_.swap(__s.__tree_);} 1289 1290 _LIBCPP_INLINE_VISIBILITY 1291 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 1292 _LIBCPP_INLINE_VISIBILITY 1293 key_compare key_comp() const {return __tree_.value_comp();} 1294 _LIBCPP_INLINE_VISIBILITY 1295 value_compare value_comp() const {return __tree_.value_comp();} 1296 1297 // set operations: 1298 _LIBCPP_INLINE_VISIBILITY 1299 iterator find(const key_type& __k) {return __tree_.find(__k);} 1300 _LIBCPP_INLINE_VISIBILITY 1301 const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 1302#if _LIBCPP_STD_VER > 11 1303 template <typename _K2> 1304 _LIBCPP_INLINE_VISIBILITY 1305 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1306 find(const _K2& __k) {return __tree_.find(__k);} 1307 template <typename _K2> 1308 _LIBCPP_INLINE_VISIBILITY 1309 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1310 find(const _K2& __k) const {return __tree_.find(__k);} 1311#endif 1312 1313 _LIBCPP_INLINE_VISIBILITY 1314 size_type count(const key_type& __k) const 1315 {return __tree_.__count_multi(__k);} 1316#if _LIBCPP_STD_VER > 11 1317 template <typename _K2> 1318 _LIBCPP_INLINE_VISIBILITY 1319 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 1320 count(const _K2& __k) const {return __tree_.__count_multi(__k);} 1321#endif 1322 1323#if _LIBCPP_STD_VER > 17 1324 _LIBCPP_INLINE_VISIBILITY 1325 bool contains(const key_type& __k) const {return find(__k) != end();} 1326#endif // _LIBCPP_STD_VER > 17 1327 1328 _LIBCPP_INLINE_VISIBILITY 1329 iterator lower_bound(const key_type& __k) 1330 {return __tree_.lower_bound(__k);} 1331 _LIBCPP_INLINE_VISIBILITY 1332 const_iterator lower_bound(const key_type& __k) const 1333 {return __tree_.lower_bound(__k);} 1334#if _LIBCPP_STD_VER > 11 1335 template <typename _K2> 1336 _LIBCPP_INLINE_VISIBILITY 1337 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1338 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 1339 1340 template <typename _K2> 1341 _LIBCPP_INLINE_VISIBILITY 1342 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1343 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 1344#endif 1345 1346 _LIBCPP_INLINE_VISIBILITY 1347 iterator upper_bound(const key_type& __k) 1348 {return __tree_.upper_bound(__k);} 1349 _LIBCPP_INLINE_VISIBILITY 1350 const_iterator upper_bound(const key_type& __k) const 1351 {return __tree_.upper_bound(__k);} 1352#if _LIBCPP_STD_VER > 11 1353 template <typename _K2> 1354 _LIBCPP_INLINE_VISIBILITY 1355 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type 1356 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 1357 template <typename _K2> 1358 _LIBCPP_INLINE_VISIBILITY 1359 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type 1360 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 1361#endif 1362 1363 _LIBCPP_INLINE_VISIBILITY 1364 pair<iterator,iterator> equal_range(const key_type& __k) 1365 {return __tree_.__equal_range_multi(__k);} 1366 _LIBCPP_INLINE_VISIBILITY 1367 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 1368 {return __tree_.__equal_range_multi(__k);} 1369#if _LIBCPP_STD_VER > 11 1370 template <typename _K2> 1371 _LIBCPP_INLINE_VISIBILITY 1372 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 1373 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 1374 template <typename _K2> 1375 _LIBCPP_INLINE_VISIBILITY 1376 typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 1377 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 1378#endif 1379}; 1380 1381#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES 1382template<class _InputIterator, 1383 class _Compare = less<__iter_value_type<_InputIterator>>, 1384 class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1385 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 1386 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 1387multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1388 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 1389 1390template<class _Key, class _Compare = less<_Key>, 1391 class _Allocator = allocator<_Key>, 1392 class = _EnableIf<__is_allocator<_Allocator>::value, void>, 1393 class = _EnableIf<!__is_allocator<_Compare>::value, void>> 1394multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 1395 -> multiset<_Key, _Compare, _Allocator>; 1396 1397template<class _InputIterator, class _Allocator, 1398 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1399multiset(_InputIterator, _InputIterator, _Allocator) 1400 -> multiset<__iter_value_type<_InputIterator>, 1401 less<__iter_value_type<_InputIterator>>, _Allocator>; 1402 1403template<class _Key, class _Allocator, 1404 class = _EnableIf<__is_allocator<_Allocator>::value, void>> 1405multiset(initializer_list<_Key>, _Allocator) 1406 -> multiset<_Key, less<_Key>, _Allocator>; 1407#endif 1408 1409#ifndef _LIBCPP_CXX03_LANG 1410 1411template <class _Key, class _Compare, class _Allocator> 1412multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1413 : __tree_(_VSTD::move(__s.__tree_), __a) 1414{ 1415 if (__a != __s.get_allocator()) 1416 { 1417 const_iterator __e = cend(); 1418 while (!__s.empty()) 1419 insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 1420 } 1421} 1422 1423#endif // _LIBCPP_CXX03_LANG 1424 1425template <class _Key, class _Compare, class _Allocator> 1426inline _LIBCPP_INLINE_VISIBILITY 1427bool 1428operator==(const multiset<_Key, _Compare, _Allocator>& __x, 1429 const multiset<_Key, _Compare, _Allocator>& __y) 1430{ 1431 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 1432} 1433 1434template <class _Key, class _Compare, class _Allocator> 1435inline _LIBCPP_INLINE_VISIBILITY 1436bool 1437operator< (const multiset<_Key, _Compare, _Allocator>& __x, 1438 const multiset<_Key, _Compare, _Allocator>& __y) 1439{ 1440 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 1441} 1442 1443template <class _Key, class _Compare, class _Allocator> 1444inline _LIBCPP_INLINE_VISIBILITY 1445bool 1446operator!=(const multiset<_Key, _Compare, _Allocator>& __x, 1447 const multiset<_Key, _Compare, _Allocator>& __y) 1448{ 1449 return !(__x == __y); 1450} 1451 1452template <class _Key, class _Compare, class _Allocator> 1453inline _LIBCPP_INLINE_VISIBILITY 1454bool 1455operator> (const multiset<_Key, _Compare, _Allocator>& __x, 1456 const multiset<_Key, _Compare, _Allocator>& __y) 1457{ 1458 return __y < __x; 1459} 1460 1461template <class _Key, class _Compare, class _Allocator> 1462inline _LIBCPP_INLINE_VISIBILITY 1463bool 1464operator>=(const multiset<_Key, _Compare, _Allocator>& __x, 1465 const multiset<_Key, _Compare, _Allocator>& __y) 1466{ 1467 return !(__x < __y); 1468} 1469 1470template <class _Key, class _Compare, class _Allocator> 1471inline _LIBCPP_INLINE_VISIBILITY 1472bool 1473operator<=(const multiset<_Key, _Compare, _Allocator>& __x, 1474 const multiset<_Key, _Compare, _Allocator>& __y) 1475{ 1476 return !(__y < __x); 1477} 1478 1479template <class _Key, class _Compare, class _Allocator> 1480inline _LIBCPP_INLINE_VISIBILITY 1481void 1482swap(multiset<_Key, _Compare, _Allocator>& __x, 1483 multiset<_Key, _Compare, _Allocator>& __y) 1484 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 1485{ 1486 __x.swap(__y); 1487} 1488 1489#if _LIBCPP_STD_VER > 17 1490template <class _Key, class _Compare, class _Allocator, class _Predicate> 1491inline _LIBCPP_INLINE_VISIBILITY 1492 typename multiset<_Key, _Compare, _Allocator>::size_type 1493 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 1494 return _VSTD::__libcpp_erase_if_container(__c, __pred); 1495} 1496#endif 1497 1498_LIBCPP_END_NAMESPACE_STD 1499 1500#endif // _LIBCPP_SET 1501