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