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