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