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