915 lines · plain
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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___CXX03_SET11#define _LIBCPP___CXX03_SET12 13/*14 15 set synopsis16 17namespace std18{19 20template <class Key, class Compare = less<Key>,21 class Allocator = allocator<Key>>22class set23{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++1743 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++1744 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++2361 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++1475 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++2378 set(initializer_list<value_type> il, const allocator_type& a)79 : set(il, Compare(), a) {} // C++1480 ~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++23124 void insert(initializer_list<value_type> il);125 126 node_type extract(const_iterator position); // C++17127 node_type extract(const key_type& x); // C++17128 insert_return_type insert(node_type&& nh); // C++17129 iterator insert(const_iterator hint, node_type&& nh); // C++17130 131 iterator erase(const_iterator position);132 iterator erase(iterator position); // C++14133 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++17139 template<class C2>140 void merge(set<Key, C2, Allocator>&& source); // C++17141 template<class C2>142 void merge(multiset<Key, C2, Allocator>& source); // C++17143 template<class C2>144 void merge(multiset<Key, C2, Allocator>&& source); // C++17145 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++14164 165 template<typename K>166 size_type count(const K& x) const; // C++14167 size_type count(const key_type& k) const;168 169 bool contains(const key_type& x) const; // C++20170 template<class K> bool contains(const K& x) const; // C++20171 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++14176 template<typename K>177 const_iterator lower_bound(const K& x) const; // C++14178 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++14183 template<typename K>184 const_iterator upper_bound(const K& x) const; // C++14185 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++14189 template<typename K>190 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14191};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++17199 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++23204 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++17208 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++17213 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++23217 218template<class Key, class Allocator>219set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17220 221template <class Key, class Compare, class Allocator>222bool223operator==(const set<Key, Compare, Allocator>& x,224 const set<Key, Compare, Allocator>& y);225 226template <class Key, class Compare, class Allocator>227bool228operator< (const set<Key, Compare, Allocator>& x,229 const set<Key, Compare, Allocator>& y); // removed in C++20230 231template <class Key, class Compare, class Allocator>232bool233operator!=(const set<Key, Compare, Allocator>& x,234 const set<Key, Compare, Allocator>& y); // removed in C++20235 236template <class Key, class Compare, class Allocator>237bool238operator> (const set<Key, Compare, Allocator>& x,239 const set<Key, Compare, Allocator>& y); // removed in C++20240 241template <class Key, class Compare, class Allocator>242bool243operator>=(const set<Key, Compare, Allocator>& x,244 const set<Key, Compare, Allocator>& y); // removed in C++20245 246template <class Key, class Compare, class Allocator>247bool248operator<=(const set<Key, Compare, Allocator>& x,249 const set<Key, Compare, Allocator>& y); // removed in C++20250 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++20254 255// specialized algorithms:256template <class Key, class Compare, class Allocator>257void258swap(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_type263erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20264 265template <class Key, class Compare = less<Key>,266 class Allocator = allocator<Key>>267class multiset268{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++17288 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++23306 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++14320 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++23323 multiset(initializer_list<value_type> il, const allocator_type& a)324 : set(il, Compare(), a) {} // C++14325 ~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++23369 void insert(initializer_list<value_type> il);370 371 node_type extract(const_iterator position); // C++17372 node_type extract(const key_type& x); // C++17373 iterator insert(node_type&& nh); // C++17374 iterator insert(const_iterator hint, node_type&& nh); // C++17375 376 iterator erase(const_iterator position);377 iterator erase(iterator position); // C++14378 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++17384 template<class C2>385 void merge(multiset<Key, C2, Allocator>&& source); // C++17386 template<class C2>387 void merge(set<Key, C2, Allocator>& source); // C++17388 template<class C2>389 void merge(set<Key, C2, Allocator>&& source); // C++17390 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++14409 410 template<typename K>411 size_type count(const K& x) const; // C++14412 size_type count(const key_type& k) const;413 414 bool contains(const key_type& x) const; // C++20415 template<class K> bool contains(const K& x) const; // C++20416 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++14421 template<typename K>422 const_iterator lower_bound(const K& x) const; // C++14423 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++14428 template<typename K>429 const_iterator upper_bound(const K& x) const; // C++14430 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++14435 template<typename K>436 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14437};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++17445 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++17454 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++17459 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++17466 467template <class Key, class Compare, class Allocator>468bool469operator==(const multiset<Key, Compare, Allocator>& x,470 const multiset<Key, Compare, Allocator>& y);471 472template <class Key, class Compare, class Allocator>473bool474operator< (const multiset<Key, Compare, Allocator>& x,475 const multiset<Key, Compare, Allocator>& y); // removed in C++20476 477template <class Key, class Compare, class Allocator>478bool479operator!=(const multiset<Key, Compare, Allocator>& x,480 const multiset<Key, Compare, Allocator>& y); // removed in C++20481 482template <class Key, class Compare, class Allocator>483bool484operator> (const multiset<Key, Compare, Allocator>& x,485 const multiset<Key, Compare, Allocator>& y); // removed in C++20486 487template <class Key, class Compare, class Allocator>488bool489operator>=(const multiset<Key, Compare, Allocator>& x,490 const multiset<Key, Compare, Allocator>& y); // removed in C++20491 492template <class Key, class Compare, class Allocator>493bool494operator<=(const multiset<Key, Compare, Allocator>& x,495 const multiset<Key, Compare, Allocator>& y); // removed in C++20496 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++20500 501// specialized algorithms:502template <class Key, class Compare, class Allocator>503void504swap(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_type509erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20510 511} // std512 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 includes530 531// [iterator.range]532#include <__cxx03/__iterator/access.h>533 534#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)535# pragma GCC system_header536#endif537 538_LIBCPP_PUSH_MACROS539#include <__cxx03/__undef_macros>540 541_LIBCPP_BEGIN_NAMESPACE_STD542 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_ABI597 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 bool681operator==(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 bool687operator<(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 bool693operator!=(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 bool699operator>(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 bool705operator>=(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 bool711operator<=(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_ABI774 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 bool862operator==(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 bool868operator<(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 bool874operator!=(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 bool880operator>(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 bool886operator>=(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 bool892operator<=(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 void898swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y) {899 __x.swap(__y);900}901 902_LIBCPP_END_NAMESPACE_STD903 904_LIBCPP_POP_MACROS905 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#endif913 914#endif // _LIBCPP___CXX03_SET915