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