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