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