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