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