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