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