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