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