1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___CXX03_SET 11#define _LIBCPP___CXX03_SET 12 13/* 14 15 set synopsis 16 17namespace std 18{ 19 20template <class Key, class Compare = less<Key>, 21 class Allocator = allocator<Key>> 22class set 23{ 24public: 25 // types: 26 typedef Key key_type; 27 typedef key_type value_type; 28 typedef Compare key_compare; 29 typedef key_compare value_compare; 30 typedef Allocator allocator_type; 31 typedef typename allocator_type::reference reference; 32 typedef typename allocator_type::const_reference const_reference; 33 typedef typename allocator_type::size_type size_type; 34 typedef typename allocator_type::difference_type difference_type; 35 typedef typename allocator_type::pointer pointer; 36 typedef typename allocator_type::const_pointer const_pointer; 37 38 typedef implementation-defined iterator; 39 typedef implementation-defined const_iterator; 40 typedef std::reverse_iterator<iterator> reverse_iterator; 41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 42 typedef unspecified node_type; // C++17 43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 44 45 // construct/copy/destroy: 46 set() 47 noexcept( 48 is_nothrow_default_constructible<allocator_type>::value && 49 is_nothrow_default_constructible<key_compare>::value && 50 is_nothrow_copy_constructible<key_compare>::value); 51 explicit set(const value_compare& comp); 52 set(const value_compare& comp, const allocator_type& a); 53 template <class InputIterator> 54 set(InputIterator first, InputIterator last, 55 const value_compare& comp = value_compare()); 56 template <class InputIterator> 57 set(InputIterator first, InputIterator last, const value_compare& comp, 58 const allocator_type& a); 59 template<container-compatible-range<value_type> R> 60 set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 61 set(const set& s); 62 set(set&& s) 63 noexcept( 64 is_nothrow_move_constructible<allocator_type>::value && 65 is_nothrow_move_constructible<key_compare>::value); 66 explicit set(const allocator_type& a); 67 set(const set& s, const allocator_type& a); 68 set(set&& s, const allocator_type& a); 69 set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 70 set(initializer_list<value_type> il, const value_compare& comp, 71 const allocator_type& a); 72 template <class InputIterator> 73 set(InputIterator first, InputIterator last, const allocator_type& a) 74 : set(first, last, Compare(), a) {} // C++14 75 template<container-compatible-range<value_type> R> 76 set(from_range_t, R&& rg, const Allocator& a)) 77 : set(from_range, std::forward<R>(rg), Compare(), a) { } // C++23 78 set(initializer_list<value_type> il, const allocator_type& a) 79 : set(il, Compare(), a) {} // C++14 80 ~set(); 81 82 set& operator=(const set& s); 83 set& operator=(set&& s) 84 noexcept( 85 allocator_type::propagate_on_container_move_assignment::value && 86 is_nothrow_move_assignable<allocator_type>::value && 87 is_nothrow_move_assignable<key_compare>::value); 88 set& operator=(initializer_list<value_type> il); 89 90 // iterators: 91 iterator begin() noexcept; 92 const_iterator begin() const noexcept; 93 iterator end() noexcept; 94 const_iterator end() const noexcept; 95 96 reverse_iterator rbegin() noexcept; 97 const_reverse_iterator rbegin() const noexcept; 98 reverse_iterator rend() noexcept; 99 const_reverse_iterator rend() const noexcept; 100 101 const_iterator cbegin() const noexcept; 102 const_iterator cend() const noexcept; 103 const_reverse_iterator crbegin() const noexcept; 104 const_reverse_iterator crend() const noexcept; 105 106 // capacity: 107 bool empty() const noexcept; 108 size_type size() const noexcept; 109 size_type max_size() const noexcept; 110 111 // modifiers: 112 template <class... Args> 113 pair<iterator, bool> emplace(Args&&... args); 114 template <class... Args> 115 iterator emplace_hint(const_iterator position, Args&&... args); 116 pair<iterator,bool> insert(const value_type& v); 117 pair<iterator,bool> insert(value_type&& v); 118 iterator insert(const_iterator position, const value_type& v); 119 iterator insert(const_iterator position, value_type&& v); 120 template <class InputIterator> 121 void insert(InputIterator first, InputIterator last); 122 template<container-compatible-range<value_type> R> 123 void insert_range(R&& rg); // C++23 124 void insert(initializer_list<value_type> il); 125 126 node_type extract(const_iterator position); // C++17 127 node_type extract(const key_type& x); // C++17 128 insert_return_type insert(node_type&& nh); // C++17 129 iterator insert(const_iterator hint, node_type&& nh); // C++17 130 131 iterator erase(const_iterator position); 132 iterator erase(iterator position); // C++14 133 size_type erase(const key_type& k); 134 iterator erase(const_iterator first, const_iterator last); 135 void clear() noexcept; 136 137 template<class C2> 138 void merge(set<Key, C2, Allocator>& source); // C++17 139 template<class C2> 140 void merge(set<Key, C2, Allocator>&& source); // C++17 141 template<class C2> 142 void merge(multiset<Key, C2, Allocator>& source); // C++17 143 template<class C2> 144 void merge(multiset<Key, C2, Allocator>&& source); // C++17 145 146 void swap(set& s) 147 noexcept( 148 __is_nothrow_swappable<key_compare>::value && 149 (!allocator_type::propagate_on_container_swap::value || 150 __is_nothrow_swappable<allocator_type>::value)); 151 152 // observers: 153 allocator_type get_allocator() const noexcept; 154 key_compare key_comp() const; 155 value_compare value_comp() const; 156 157 // set operations: 158 iterator find(const key_type& k); 159 const_iterator find(const key_type& k) const; 160 template<typename K> 161 iterator find(const K& x); 162 template<typename K> 163 const_iterator find(const K& x) const; // C++14 164 165 template<typename K> 166 size_type count(const K& x) const; // C++14 167 size_type count(const key_type& k) const; 168 169 bool contains(const key_type& x) const; // C++20 170 template<class K> bool contains(const K& x) const; // C++20 171 172 iterator lower_bound(const key_type& k); 173 const_iterator lower_bound(const key_type& k) const; 174 template<typename K> 175 iterator lower_bound(const K& x); // C++14 176 template<typename K> 177 const_iterator lower_bound(const K& x) const; // C++14 178 179 iterator upper_bound(const key_type& k); 180 const_iterator upper_bound(const key_type& k) const; 181 template<typename K> 182 iterator upper_bound(const K& x); // C++14 183 template<typename K> 184 const_iterator upper_bound(const K& x) const; // C++14 185 pair<iterator,iterator> equal_range(const key_type& k); 186 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 187 template<typename K> 188 pair<iterator,iterator> equal_range(const K& x); // C++14 189 template<typename K> 190 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 191}; 192 193template <class InputIterator, 194 class Compare = less<typename iterator_traits<InputIterator>::value_type>, 195 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 196set(InputIterator, InputIterator, 197 Compare = Compare(), Allocator = Allocator()) 198 -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 199 200template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>, 201 class Allocator = allocator<ranges::range_value_t<R>>> 202 set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) 203 -> set<ranges::range_value_t<R>, Compare, Allocator>; // C++23 204 205template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 206set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 207 -> set<Key, Compare, Allocator>; // C++17 208 209template<class InputIterator, class Allocator> 210set(InputIterator, InputIterator, Allocator) 211 -> set<typename iterator_traits<InputIterator>::value_type, 212 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 213 214template<ranges::input_range R, class Allocator> 215 set(from_range_t, R&&, Allocator) 216 -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; // C++23 217 218template<class Key, class Allocator> 219set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17 220 221template <class Key, class Compare, class Allocator> 222bool 223operator==(const set<Key, Compare, Allocator>& x, 224 const set<Key, Compare, Allocator>& y); 225 226template <class Key, class Compare, class Allocator> 227bool 228operator< (const set<Key, Compare, Allocator>& x, 229 const set<Key, Compare, Allocator>& y); // removed in C++20 230 231template <class Key, class Compare, class Allocator> 232bool 233operator!=(const set<Key, Compare, Allocator>& x, 234 const set<Key, Compare, Allocator>& y); // removed in C++20 235 236template <class Key, class Compare, class Allocator> 237bool 238operator> (const set<Key, Compare, Allocator>& x, 239 const set<Key, Compare, Allocator>& y); // removed in C++20 240 241template <class Key, class Compare, class Allocator> 242bool 243operator>=(const set<Key, Compare, Allocator>& x, 244 const set<Key, Compare, Allocator>& y); // removed in C++20 245 246template <class Key, class Compare, class Allocator> 247bool 248operator<=(const set<Key, Compare, Allocator>& x, 249 const set<Key, Compare, Allocator>& y); // removed in C++20 250 251template<class Key, class Compare, class Allocator> 252 synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x, 253 const set<Key, Compare, Allocator>& y); // since C++20 254 255// specialized algorithms: 256template <class Key, class Compare, class Allocator> 257void 258swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 259 noexcept(noexcept(x.swap(y))); 260 261template <class Key, class Compare, class Allocator, class Predicate> 262typename set<Key, Compare, Allocator>::size_type 263erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 264 265template <class Key, class Compare = less<Key>, 266 class Allocator = allocator<Key>> 267class multiset 268{ 269public: 270 // types: 271 typedef Key key_type; 272 typedef key_type value_type; 273 typedef Compare key_compare; 274 typedef key_compare value_compare; 275 typedef Allocator allocator_type; 276 typedef typename allocator_type::reference reference; 277 typedef typename allocator_type::const_reference const_reference; 278 typedef typename allocator_type::size_type size_type; 279 typedef typename allocator_type::difference_type difference_type; 280 typedef typename allocator_type::pointer pointer; 281 typedef typename allocator_type::const_pointer const_pointer; 282 283 typedef implementation-defined iterator; 284 typedef implementation-defined const_iterator; 285 typedef std::reverse_iterator<iterator> reverse_iterator; 286 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 287 typedef unspecified node_type; // C++17 288 289 // construct/copy/destroy: 290 multiset() 291 noexcept( 292 is_nothrow_default_constructible<allocator_type>::value && 293 is_nothrow_default_constructible<key_compare>::value && 294 is_nothrow_copy_constructible<key_compare>::value); 295 explicit multiset(const value_compare& comp); 296 multiset(const value_compare& comp, const allocator_type& a); 297 template <class InputIterator> 298 multiset(InputIterator first, InputIterator last, 299 const value_compare& comp = value_compare()); 300 template <class InputIterator> 301 multiset(InputIterator first, InputIterator last, 302 const value_compare& comp, const allocator_type& a); 303 template<container-compatible-range<value_type> R> 304 multiset(from_range_t, R&& rg, 305 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 306 multiset(const multiset& s); 307 multiset(multiset&& s) 308 noexcept( 309 is_nothrow_move_constructible<allocator_type>::value && 310 is_nothrow_move_constructible<key_compare>::value); 311 explicit multiset(const allocator_type& a); 312 multiset(const multiset& s, const allocator_type& a); 313 multiset(multiset&& s, const allocator_type& a); 314 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 315 multiset(initializer_list<value_type> il, const value_compare& comp, 316 const allocator_type& a); 317 template <class InputIterator> 318 multiset(InputIterator first, InputIterator last, const allocator_type& a) 319 : set(first, last, Compare(), a) {} // C++14 320 template<container-compatible-range<value_type> R> 321 multiset(from_range_t, R&& rg, const Allocator& a)) 322 : multiset(from_range, std::forward<R>(rg), Compare(), a) { } // C++23 323 multiset(initializer_list<value_type> il, const allocator_type& a) 324 : set(il, Compare(), a) {} // C++14 325 ~multiset(); 326 327 multiset& operator=(const multiset& s); 328 multiset& operator=(multiset&& s) 329 noexcept( 330 allocator_type::propagate_on_container_move_assignment::value && 331 is_nothrow_move_assignable<allocator_type>::value && 332 is_nothrow_move_assignable<key_compare>::value); 333 multiset& operator=(initializer_list<value_type> il); 334 335 // iterators: 336 iterator begin() noexcept; 337 const_iterator begin() const noexcept; 338 iterator end() noexcept; 339 const_iterator end() const noexcept; 340 341 reverse_iterator rbegin() noexcept; 342 const_reverse_iterator rbegin() const noexcept; 343 reverse_iterator rend() noexcept; 344 const_reverse_iterator rend() const noexcept; 345 346 const_iterator cbegin() const noexcept; 347 const_iterator cend() const noexcept; 348 const_reverse_iterator crbegin() const noexcept; 349 const_reverse_iterator crend() const noexcept; 350 351 // capacity: 352 bool empty() const noexcept; 353 size_type size() const noexcept; 354 size_type max_size() const noexcept; 355 356 // modifiers: 357 template <class... Args> 358 iterator emplace(Args&&... args); 359 template <class... Args> 360 iterator emplace_hint(const_iterator position, Args&&... args); 361 iterator insert(const value_type& v); 362 iterator insert(value_type&& v); 363 iterator insert(const_iterator position, const value_type& v); 364 iterator insert(const_iterator position, value_type&& v); 365 template <class InputIterator> 366 void insert(InputIterator first, InputIterator last); 367 template<container-compatible-range<value_type> R> 368 void insert_range(R&& rg); // C++23 369 void insert(initializer_list<value_type> il); 370 371 node_type extract(const_iterator position); // C++17 372 node_type extract(const key_type& x); // C++17 373 iterator insert(node_type&& nh); // C++17 374 iterator insert(const_iterator hint, node_type&& nh); // C++17 375 376 iterator erase(const_iterator position); 377 iterator erase(iterator position); // C++14 378 size_type erase(const key_type& k); 379 iterator erase(const_iterator first, const_iterator last); 380 void clear() noexcept; 381 382 template<class C2> 383 void merge(multiset<Key, C2, Allocator>& source); // C++17 384 template<class C2> 385 void merge(multiset<Key, C2, Allocator>&& source); // C++17 386 template<class C2> 387 void merge(set<Key, C2, Allocator>& source); // C++17 388 template<class C2> 389 void merge(set<Key, C2, Allocator>&& source); // C++17 390 391 void swap(multiset& s) 392 noexcept( 393 __is_nothrow_swappable<key_compare>::value && 394 (!allocator_type::propagate_on_container_swap::value || 395 __is_nothrow_swappable<allocator_type>::value)); 396 397 // observers: 398 allocator_type get_allocator() const noexcept; 399 key_compare key_comp() const; 400 value_compare value_comp() const; 401 402 // set operations: 403 iterator find(const key_type& k); 404 const_iterator find(const key_type& k) const; 405 template<typename K> 406 iterator find(const K& x); 407 template<typename K> 408 const_iterator find(const K& x) const; // C++14 409 410 template<typename K> 411 size_type count(const K& x) const; // C++14 412 size_type count(const key_type& k) const; 413 414 bool contains(const key_type& x) const; // C++20 415 template<class K> bool contains(const K& x) const; // C++20 416 417 iterator lower_bound(const key_type& k); 418 const_iterator lower_bound(const key_type& k) const; 419 template<typename K> 420 iterator lower_bound(const K& x); // C++14 421 template<typename K> 422 const_iterator lower_bound(const K& x) const; // C++14 423 424 iterator upper_bound(const key_type& k); 425 const_iterator upper_bound(const key_type& k) const; 426 template<typename K> 427 iterator upper_bound(const K& x); // C++14 428 template<typename K> 429 const_iterator upper_bound(const K& x) const; // C++14 430 431 pair<iterator,iterator> equal_range(const key_type& k); 432 pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 433 template<typename K> 434 pair<iterator,iterator> equal_range(const K& x); // C++14 435 template<typename K> 436 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 437}; 438 439template <class InputIterator, 440 class Compare = less<typename iterator_traits<InputIterator>::value_type>, 441 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 442multiset(InputIterator, InputIterator, 443 Compare = Compare(), Allocator = Allocator()) 444 -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 445 446template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>, 447 class Allocator = allocator<ranges::range_value_t<R>>> 448 multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) 449 -> multiset<ranges::range_value_t<R>, Compare, Allocator>; 450 451template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 452multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 453 -> multiset<Key, Compare, Allocator>; // C++17 454 455template<class InputIterator, class Allocator> 456multiset(InputIterator, InputIterator, Allocator) 457 -> multiset<typename iterator_traits<InputIterator>::value_type, 458 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 459 460template<ranges::input_range R, class Allocator> 461 multiset(from_range_t, R&&, Allocator) 462 -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; 463 464template<class Key, class Allocator> 465multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17 466 467template <class Key, class Compare, class Allocator> 468bool 469operator==(const multiset<Key, Compare, Allocator>& x, 470 const multiset<Key, Compare, Allocator>& y); 471 472template <class Key, class Compare, class Allocator> 473bool 474operator< (const multiset<Key, Compare, Allocator>& x, 475 const multiset<Key, Compare, Allocator>& y); // removed in C++20 476 477template <class Key, class Compare, class Allocator> 478bool 479operator!=(const multiset<Key, Compare, Allocator>& x, 480 const multiset<Key, Compare, Allocator>& y); // removed in C++20 481 482template <class Key, class Compare, class Allocator> 483bool 484operator> (const multiset<Key, Compare, Allocator>& x, 485 const multiset<Key, Compare, Allocator>& y); // removed in C++20 486 487template <class Key, class Compare, class Allocator> 488bool 489operator>=(const multiset<Key, Compare, Allocator>& x, 490 const multiset<Key, Compare, Allocator>& y); // removed in C++20 491 492template <class Key, class Compare, class Allocator> 493bool 494operator<=(const multiset<Key, Compare, Allocator>& x, 495 const multiset<Key, Compare, Allocator>& y); // removed in C++20 496 497template<class Key, class Compare, class Allocator> 498 synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x, 499 const multiset<Key, Compare, Allocator>& y); // since C++20 500 501// specialized algorithms: 502template <class Key, class Compare, class Allocator> 503void 504swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 505 noexcept(noexcept(x.swap(y))); 506 507template <class Key, class Compare, class Allocator, class Predicate> 508typename multiset<Key, Compare, Allocator>::size_type 509erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 510 511} // std 512 513*/ 514 515#include <__cxx03/__algorithm/equal.h> 516#include <__cxx03/__algorithm/lexicographical_compare.h> 517#include <__cxx03/__assert> 518#include <__cxx03/__config> 519#include <__cxx03/__functional/operations.h> 520#include <__cxx03/__iterator/erase_if_container.h> 521#include <__cxx03/__iterator/iterator_traits.h> 522#include <__cxx03/__iterator/reverse_iterator.h> 523#include <__cxx03/__memory/allocator.h> 524#include <__cxx03/__tree> 525#include <__cxx03/__type_traits/is_allocator.h> 526#include <__cxx03/__utility/forward.h> 527#include <__cxx03/version> 528 529// standard-mandated includes 530 531// [iterator.range] 532#include <__cxx03/__iterator/access.h> 533 534#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 535# pragma GCC system_header 536#endif 537 538_LIBCPP_PUSH_MACROS 539#include <__cxx03/__undef_macros> 540 541_LIBCPP_BEGIN_NAMESPACE_STD 542 543template <class _Key, class _Compare, class _Allocator> 544class multiset; 545 546template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> > 547class _LIBCPP_TEMPLATE_VIS set { 548public: 549 // types: 550 typedef _Key key_type; 551 typedef key_type value_type; 552 typedef __type_identity_t<_Compare> key_compare; 553 typedef key_compare value_compare; 554 typedef __type_identity_t<_Allocator> allocator_type; 555 typedef value_type& reference; 556 typedef const value_type& const_reference; 557 558 static_assert(is_same<typename allocator_type::value_type, value_type>::value, 559 "Allocator::value_type must be same type as value_type"); 560 561private: 562 typedef __tree<value_type, value_compare, allocator_type> __base; 563 typedef allocator_traits<allocator_type> __alloc_traits; 564 565 static_assert(__check_valid_allocator<allocator_type>::value, ""); 566 567 __base __tree_; 568 569public: 570 typedef typename __base::pointer pointer; 571 typedef typename __base::const_pointer const_pointer; 572 typedef typename __base::size_type size_type; 573 typedef typename __base::difference_type difference_type; 574 typedef typename __base::const_iterator iterator; 575 typedef typename __base::const_iterator const_iterator; 576 typedef std::reverse_iterator<iterator> reverse_iterator; 577 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 578 579 template <class _Key2, class _Compare2, class _Alloc2> 580 friend class _LIBCPP_TEMPLATE_VIS set; 581 template <class _Key2, class _Compare2, class _Alloc2> 582 friend class _LIBCPP_TEMPLATE_VIS multiset; 583 584 _LIBCPP_HIDE_FROM_ABI set() : __tree_(value_compare()) {} 585 586 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) : __tree_(__comp) {} 587 588 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {} 589 template <class _InputIterator> 590 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare()) 591 : __tree_(__comp) { 592 insert(__f, __l); 593 } 594 595 template <class _InputIterator> 596 _LIBCPP_HIDE_FROM_ABI 597 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a) 598 : __tree_(__comp, __a) { 599 insert(__f, __l); 600 } 601 602 _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); } 603 604 _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) { 605 __tree_ = __s.__tree_; 606 return *this; 607 } 608 609 _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {} 610 611 _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) { 612 insert(__s.begin(), __s.end()); 613 } 614 615 _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 616 617 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 618 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 619 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 620 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 621 622 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 623 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 624 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 625 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 626 627 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 628 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 629 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 630 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 631 632 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 633 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 634 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 635 636 // modifiers: 637 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); } 638 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 639 return __tree_.__insert_unique(__p, __v); 640 } 641 642 template <class _InputIterator> 643 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 644 for (const_iterator __e = cend(); __f != __l; ++__f) 645 __tree_.__insert_unique(__e, *__f); 646 } 647 648 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); } 649 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); } 650 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); } 651 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 652 653 _LIBCPP_HIDE_FROM_ABI void swap(set& __s) { __tree_.swap(__s.__tree_); } 654 655 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); } 656 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); } 657 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); } 658 659 // set operations: 660 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 661 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 662 663 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); } 664 665 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 666 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 667 668 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 669 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 670 671 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 672 return __tree_.__equal_range_unique(__k); 673 } 674 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 675 return __tree_.__equal_range_unique(__k); 676 } 677}; 678 679template <class _Key, class _Compare, class _Allocator> 680inline _LIBCPP_HIDE_FROM_ABI bool 681operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 682 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 683} 684 685template <class _Key, class _Compare, class _Allocator> 686inline _LIBCPP_HIDE_FROM_ABI bool 687operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 688 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 689} 690 691template <class _Key, class _Compare, class _Allocator> 692inline _LIBCPP_HIDE_FROM_ABI bool 693operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 694 return !(__x == __y); 695} 696 697template <class _Key, class _Compare, class _Allocator> 698inline _LIBCPP_HIDE_FROM_ABI bool 699operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 700 return __y < __x; 701} 702 703template <class _Key, class _Compare, class _Allocator> 704inline _LIBCPP_HIDE_FROM_ABI bool 705operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 706 return !(__x < __y); 707} 708 709template <class _Key, class _Compare, class _Allocator> 710inline _LIBCPP_HIDE_FROM_ABI bool 711operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 712 return !(__y < __x); 713} 714 715// specialized algorithms: 716template <class _Key, class _Compare, class _Allocator> 717inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y) { 718 __x.swap(__y); 719} 720 721template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> > 722class _LIBCPP_TEMPLATE_VIS multiset { 723public: 724 // types: 725 typedef _Key key_type; 726 typedef key_type value_type; 727 typedef __type_identity_t<_Compare> key_compare; 728 typedef key_compare value_compare; 729 typedef __type_identity_t<_Allocator> allocator_type; 730 typedef value_type& reference; 731 typedef const value_type& const_reference; 732 733 static_assert(is_same<typename allocator_type::value_type, value_type>::value, 734 "Allocator::value_type must be same type as value_type"); 735 736private: 737 typedef __tree<value_type, value_compare, allocator_type> __base; 738 typedef allocator_traits<allocator_type> __alloc_traits; 739 740 static_assert(__check_valid_allocator<allocator_type>::value, ""); 741 742 __base __tree_; 743 744public: 745 typedef typename __base::pointer pointer; 746 typedef typename __base::const_pointer const_pointer; 747 typedef typename __base::size_type size_type; 748 typedef typename __base::difference_type difference_type; 749 typedef typename __base::const_iterator iterator; 750 typedef typename __base::const_iterator const_iterator; 751 typedef std::reverse_iterator<iterator> reverse_iterator; 752 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 753 754 template <class _Key2, class _Compare2, class _Alloc2> 755 friend class _LIBCPP_TEMPLATE_VIS set; 756 template <class _Key2, class _Compare2, class _Alloc2> 757 friend class _LIBCPP_TEMPLATE_VIS multiset; 758 759 // construct/copy/destroy: 760 _LIBCPP_HIDE_FROM_ABI multiset() : __tree_(value_compare()) {} 761 762 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) : __tree_(__comp) {} 763 764 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a) 765 : __tree_(__comp, __a) {} 766 template <class _InputIterator> 767 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare()) 768 : __tree_(__comp) { 769 insert(__f, __l); 770 } 771 772 template <class _InputIterator> 773 _LIBCPP_HIDE_FROM_ABI 774 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a) 775 : __tree_(__comp, __a) { 776 insert(__f, __l); 777 } 778 779 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s) 780 : __tree_(__s.__tree_.value_comp(), 781 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) { 782 insert(__s.begin(), __s.end()); 783 } 784 785 _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) { 786 __tree_ = __s.__tree_; 787 return *this; 788 } 789 790 _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {} 791 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a) 792 : __tree_(__s.__tree_.value_comp(), __a) { 793 insert(__s.begin(), __s.end()); 794 } 795 796 _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 797 798 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 799 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 800 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 801 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 802 803 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 804 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 805 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 806 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 807 808 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 809 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 810 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 811 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 812 813 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 814 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 815 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 816 817 // modifiers: 818 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); } 819 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 820 return __tree_.__insert_multi(__p, __v); 821 } 822 823 template <class _InputIterator> 824 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 825 for (const_iterator __e = cend(); __f != __l; ++__f) 826 __tree_.__insert_multi(__e, *__f); 827 } 828 829 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); } 830 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); } 831 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); } 832 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 833 834 _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) { __tree_.swap(__s.__tree_); } 835 836 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); } 837 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); } 838 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); } 839 840 // set operations: 841 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 842 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 843 844 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); } 845 846 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 847 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 848 849 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 850 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 851 852 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 853 return __tree_.__equal_range_multi(__k); 854 } 855 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 856 return __tree_.__equal_range_multi(__k); 857 } 858}; 859 860template <class _Key, class _Compare, class _Allocator> 861inline _LIBCPP_HIDE_FROM_ABI bool 862operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 863 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 864} 865 866template <class _Key, class _Compare, class _Allocator> 867inline _LIBCPP_HIDE_FROM_ABI bool 868operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 869 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 870} 871 872template <class _Key, class _Compare, class _Allocator> 873inline _LIBCPP_HIDE_FROM_ABI bool 874operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 875 return !(__x == __y); 876} 877 878template <class _Key, class _Compare, class _Allocator> 879inline _LIBCPP_HIDE_FROM_ABI bool 880operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 881 return __y < __x; 882} 883 884template <class _Key, class _Compare, class _Allocator> 885inline _LIBCPP_HIDE_FROM_ABI bool 886operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 887 return !(__x < __y); 888} 889 890template <class _Key, class _Compare, class _Allocator> 891inline _LIBCPP_HIDE_FROM_ABI bool 892operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 893 return !(__y < __x); 894} 895 896template <class _Key, class _Compare, class _Allocator> 897inline _LIBCPP_HIDE_FROM_ABI void 898swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y) { 899 __x.swap(__y); 900} 901 902_LIBCPP_END_NAMESPACE_STD 903 904_LIBCPP_POP_MACROS 905 906#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) 907# include <__cxx03/cstdlib> 908# include <__cxx03/functional> 909# include <__cxx03/iterator> 910# include <__cxx03/stdexcept> 911# include <__cxx03/type_traits> 912#endif 913 914#endif // _LIBCPP___CXX03_SET 915