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