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