1492 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_SET11#define _LIBCPP_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#if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)516# include <__cxx03/set>517#else518# include <__algorithm/equal.h>519# include <__algorithm/lexicographical_compare.h>520# include <__algorithm/lexicographical_compare_three_way.h>521# include <__assert>522# include <__config>523# include <__functional/is_transparent.h>524# include <__functional/operations.h>525# include <__iterator/erase_if_container.h>526# include <__iterator/iterator_traits.h>527# include <__iterator/reverse_iterator.h>528# include <__memory/allocator.h>529# include <__memory/allocator_traits.h>530# include <__memory_resource/polymorphic_allocator.h>531# include <__node_handle>532# include <__ranges/access.h>533# include <__ranges/concepts.h>534# include <__ranges/container_compatible_range.h>535# include <__ranges/from_range.h>536# include <__tree>537# include <__type_traits/container_traits.h>538# include <__type_traits/enable_if.h>539# include <__type_traits/is_allocator.h>540# include <__type_traits/is_nothrow_constructible.h>541# include <__type_traits/is_same.h>542# include <__type_traits/is_swappable.h>543# include <__type_traits/type_identity.h>544# include <__utility/forward.h>545# include <__utility/move.h>546# include <__utility/pair.h>547# include <version>548 549// standard-mandated includes550 551// [iterator.range]552# include <__iterator/access.h>553# include <__iterator/data.h>554# include <__iterator/empty.h>555# include <__iterator/reverse_access.h>556# include <__iterator/size.h>557 558// [associative.set.syn]559# include <compare>560# include <initializer_list>561 562# if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)563# pragma GCC system_header564# endif565 566_LIBCPP_PUSH_MACROS567# include <__undef_macros>568 569_LIBCPP_BEGIN_NAMESPACE_STD570 571template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >572class multiset;573 574template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >575class set {576public:577 // types:578 typedef _Key key_type;579 typedef key_type value_type;580 typedef __type_identity_t<_Compare> key_compare;581 typedef key_compare value_compare;582 typedef __type_identity_t<_Allocator> allocator_type;583 typedef value_type& reference;584 typedef const value_type& const_reference;585 586 static_assert(is_same<typename allocator_type::value_type, value_type>::value,587 "Allocator::value_type must be same type as value_type");588 589private:590 typedef __tree<value_type, value_compare, allocator_type> __base;591 typedef allocator_traits<allocator_type> __alloc_traits;592 593 static_assert(__check_valid_allocator<allocator_type>::value, "");594 595 __base __tree_;596 597public:598 typedef typename __base::pointer pointer;599 typedef typename __base::const_pointer const_pointer;600 typedef typename __base::size_type size_type;601 typedef typename __base::difference_type difference_type;602 typedef typename __base::const_iterator iterator;603 typedef typename __base::const_iterator const_iterator;604 typedef std::reverse_iterator<iterator> reverse_iterator;605 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;606 607# if _LIBCPP_STD_VER >= 17608 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;609 typedef __insert_return_type<iterator, node_type> insert_return_type;610# endif611 612 template <class _Key2, class _Compare2, class _Alloc2>613 friend class set;614 template <class _Key2, class _Compare2, class _Alloc2>615 friend class multiset;616 617 _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_(618 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&619 is_nothrow_copy_constructible<key_compare>::value)620 : __tree_(value_compare()) {}621 622 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_(623 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)624 : __tree_(__comp) {}625 626 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}627 template <class _InputIterator>628 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())629 : __tree_(__comp) {630 insert(__f, __l);631 }632 633 template <class _InputIterator>634 _LIBCPP_HIDE_FROM_ABI635 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)636 : __tree_(__comp, __a) {637 insert(__f, __l);638 }639 640# if _LIBCPP_STD_VER >= 23641 template <_ContainerCompatibleRange<value_type> _Range>642 _LIBCPP_HIDE_FROM_ABI643 set(from_range_t,644 _Range&& __range,645 const key_compare& __comp = key_compare(),646 const allocator_type& __a = allocator_type())647 : __tree_(__comp, __a) {648 insert_range(std::forward<_Range>(__range));649 }650# endif651 652# if _LIBCPP_STD_VER >= 14653 template <class _InputIterator>654 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)655 : set(__f, __l, key_compare(), __a) {}656# endif657 658# if _LIBCPP_STD_VER >= 23659 template <_ContainerCompatibleRange<value_type> _Range>660 _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a)661 : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}662# endif663 664 _LIBCPP_HIDE_FROM_ABI set(const set& __s) = default;665 666 _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) = default;667 668# ifndef _LIBCPP_CXX03_LANG669 _LIBCPP_HIDE_FROM_ABI set(set&& __s) = default;670# endif // _LIBCPP_CXX03_LANG671 672 _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}673 674 _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __alloc) : __tree_(__s.__tree_, __alloc) {}675 676# ifndef _LIBCPP_CXX03_LANG677 _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __alloc) : __tree_(std::move(__s.__tree_), __alloc) {}678 679 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())680 : __tree_(__comp) {681 insert(__il.begin(), __il.end());682 }683 684 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)685 : __tree_(__comp, __a) {686 insert(__il.begin(), __il.end());687 }688 689# if _LIBCPP_STD_VER >= 14690 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a)691 : set(__il, key_compare(), __a) {}692# endif693 694 _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) {695 __tree_.__assign_unique(__il.begin(), __il.end());696 return *this;697 }698 699 _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) = default;700# endif // _LIBCPP_CXX03_LANG701 702 _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), ""); }703 704 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }705 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }706 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }707 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }708 709 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }710 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }711 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }712 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }713 714 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }715 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }716 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }717 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }718 719 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }720 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }721 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }722 723 // modifiers:724# ifndef _LIBCPP_CXX03_LANG725 template <class... _Args>726 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {727 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);728 }729 template <class... _Args>730 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {731 return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...).first;732 }733# endif // _LIBCPP_CXX03_LANG734 735 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__emplace_unique(__v); }736 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {737 return __tree_.__emplace_hint_unique(__p, __v).first;738 }739 740 template <class _InputIterator>741 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {742 __tree_.__insert_range_unique(__first, __last);743 }744 745# if _LIBCPP_STD_VER >= 23746 template <_ContainerCompatibleRange<value_type> _Range>747 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {748 __tree_.__insert_range_unique(ranges::begin(__range), ranges::end(__range));749 }750# endif751 752# ifndef _LIBCPP_CXX03_LANG753 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {754 return __tree_.__emplace_unique(std::move(__v));755 }756 757 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {758 return __tree_.__emplace_hint_unique(__p, std::move(__v)).first;759 }760 761 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }762# endif // _LIBCPP_CXX03_LANG763 764 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }765 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }766 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }767 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }768 769# if _LIBCPP_STD_VER >= 17770 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {771 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),772 "node_type with incompatible allocator passed to set::insert()");773 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));774 }775 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {776 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),777 "node_type with incompatible allocator passed to set::insert()");778 return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));779 }780 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {781 return __tree_.template __node_handle_extract<node_type>(__key);782 }783 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {784 return __tree_.template __node_handle_extract<node_type>(__it);785 }786 template <class _Compare2>787 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {788 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(789 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");790 __tree_.__node_handle_merge_unique(__source.__tree_);791 }792 template <class _Compare2>793 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {794 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(795 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");796 __tree_.__node_handle_merge_unique(__source.__tree_);797 }798 template <class _Compare2>799 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {800 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(801 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");802 __tree_.__node_handle_merge_unique(__source.__tree_);803 }804 template <class _Compare2>805 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {806 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(807 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");808 __tree_.__node_handle_merge_unique(__source.__tree_);809 }810# endif811 812 _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__s.__tree_); }813 814 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }815 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }816 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }817 818 // set operations:819 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }820 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }821# if _LIBCPP_STD_VER >= 14822 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>823 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {824 return __tree_.find(__k);825 }826 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>827 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {828 return __tree_.find(__k);829 }830# endif831 832 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }833# if _LIBCPP_STD_VER >= 14834 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>835 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {836 return __tree_.__count_multi(__k);837 }838# endif839 840# if _LIBCPP_STD_VER >= 20841 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }842 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>843 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {844 return find(__k) != end();845 }846# endif // _LIBCPP_STD_VER >= 20847 848 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.__lower_bound_unique(__k); }849 850 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const {851 return __tree_.__lower_bound_unique(__k);852 }853 854 // The transparent versions of the lookup functions use the _multi version, since a non-element key is allowed to855 // match multiple elements.856# if _LIBCPP_STD_VER >= 14857 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>858 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {859 return __tree_.__lower_bound_multi(__k);860 }861 862 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>863 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {864 return __tree_.__lower_bound_multi(__k);865 }866# endif867 868 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.__upper_bound_unique(__k); }869 870 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const {871 return __tree_.__upper_bound_unique(__k);872 }873 874# if _LIBCPP_STD_VER >= 14875 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>876 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {877 return __tree_.__upper_bound_multi(__k);878 }879 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>880 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {881 return __tree_.__upper_bound_multi(__k);882 }883# endif884 885 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {886 return __tree_.__equal_range_unique(__k);887 }888 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {889 return __tree_.__equal_range_unique(__k);890 }891# if _LIBCPP_STD_VER >= 14892 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>893 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {894 return __tree_.__equal_range_multi(__k);895 }896 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>897 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {898 return __tree_.__equal_range_multi(__k);899 }900# endif901};902 903# if _LIBCPP_STD_VER >= 17904template <class _InputIterator,905 class _Compare = less<__iterator_value_type<_InputIterator>>,906 class _Allocator = allocator<__iterator_value_type<_InputIterator>>,907 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,908 class = enable_if_t<__is_allocator_v<_Allocator>>,909 class = enable_if_t<!__is_allocator_v<_Compare>>>910set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())911 -> set<__iterator_value_type<_InputIterator>, _Compare, _Allocator>;912 913# if _LIBCPP_STD_VER >= 23914template <ranges::input_range _Range,915 class _Compare = less<ranges::range_value_t<_Range>>,916 class _Allocator = allocator<ranges::range_value_t<_Range>>,917 class = enable_if_t<__is_allocator_v<_Allocator>>,918 class = enable_if_t<!__is_allocator_v<_Compare>>>919set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())920 -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;921# endif922 923template <class _Key,924 class _Compare = less<_Key>,925 class _Allocator = allocator<_Key>,926 class = enable_if_t<!__is_allocator_v<_Compare>>,927 class = enable_if_t<__is_allocator_v<_Allocator>>>928set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;929 930template <class _InputIterator,931 class _Allocator,932 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,933 class = enable_if_t<__is_allocator_v<_Allocator>>>934set(_InputIterator, _InputIterator, _Allocator)935 -> set<__iterator_value_type<_InputIterator>, less<__iterator_value_type<_InputIterator>>, _Allocator>;936 937# if _LIBCPP_STD_VER >= 23938template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>939set(from_range_t, _Range&&, _Allocator)940 -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;941# endif942 943template <class _Key, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>944set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;945# endif946 947template <class _Key, class _Compare, class _Allocator>948inline _LIBCPP_HIDE_FROM_ABI bool949operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {950 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());951}952 953# if _LIBCPP_STD_VER <= 17954 955template <class _Key, class _Compare, class _Allocator>956inline _LIBCPP_HIDE_FROM_ABI bool957operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {958 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());959}960 961template <class _Key, class _Compare, class _Allocator>962inline _LIBCPP_HIDE_FROM_ABI bool963operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {964 return !(__x == __y);965}966 967template <class _Key, class _Compare, class _Allocator>968inline _LIBCPP_HIDE_FROM_ABI bool969operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {970 return __y < __x;971}972 973template <class _Key, class _Compare, class _Allocator>974inline _LIBCPP_HIDE_FROM_ABI bool975operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {976 return !(__x < __y);977}978 979template <class _Key, class _Compare, class _Allocator>980inline _LIBCPP_HIDE_FROM_ABI bool981operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {982 return !(__y < __x);983}984 985# else // _LIBCPP_STD_VER <= 17986 987template <class _Key, class _Compare, class _Allocator>988_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>989operator<=>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {990 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);991}992 993# endif // _LIBCPP_STD_VER <= 17994 995// specialized algorithms:996template <class _Key, class _Compare, class _Allocator>997inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y)998 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {999 __x.swap(__y);1000}1001 1002# if _LIBCPP_STD_VER >= 201003template <class _Key, class _Compare, class _Allocator, class _Predicate>1004inline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type1005erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {1006 return std::__libcpp_erase_if_container(__c, __pred);1007}1008# endif1009 1010template <class _Key, class _Compare, class _Allocator>1011struct __container_traits<set<_Key, _Compare, _Allocator> > {1012 // http://eel.is/c++draft/associative.reqmts.except#21013 // For associative containers, if an exception is thrown by any operation from within1014 // an insert or emplace function inserting a single element, the insertion has no effect.1015 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;1016 1017 static _LIBCPP_CONSTEXPR const bool __reservable = false;1018};1019 1020template <class _Key, class _Compare, class _Allocator>1021class multiset {1022public:1023 // types:1024 typedef _Key key_type;1025 typedef key_type value_type;1026 typedef __type_identity_t<_Compare> key_compare;1027 typedef key_compare value_compare;1028 typedef __type_identity_t<_Allocator> allocator_type;1029 typedef value_type& reference;1030 typedef const value_type& const_reference;1031 1032 static_assert(is_same<typename allocator_type::value_type, value_type>::value,1033 "Allocator::value_type must be same type as value_type");1034 1035private:1036 typedef __tree<value_type, value_compare, allocator_type> __base;1037 typedef allocator_traits<allocator_type> __alloc_traits;1038 1039 static_assert(__check_valid_allocator<allocator_type>::value, "");1040 1041 __base __tree_;1042 1043public:1044 typedef typename __base::pointer pointer;1045 typedef typename __base::const_pointer const_pointer;1046 typedef typename __base::size_type size_type;1047 typedef typename __base::difference_type difference_type;1048 typedef typename __base::const_iterator iterator;1049 typedef typename __base::const_iterator const_iterator;1050 typedef std::reverse_iterator<iterator> reverse_iterator;1051 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;1052 1053# if _LIBCPP_STD_VER >= 171054 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;1055# endif1056 1057 template <class _Key2, class _Compare2, class _Alloc2>1058 friend class set;1059 template <class _Key2, class _Compare2, class _Alloc2>1060 friend class multiset;1061 1062 // construct/copy/destroy:1063 _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_(1064 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&1065 is_nothrow_copy_constructible<key_compare>::value)1066 : __tree_(value_compare()) {}1067 1068 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_(1069 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)1070 : __tree_(__comp) {}1071 1072 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)1073 : __tree_(__comp, __a) {}1074 template <class _InputIterator>1075 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())1076 : __tree_(__comp) {1077 insert(__f, __l);1078 }1079 1080# if _LIBCPP_STD_VER >= 141081 template <class _InputIterator>1082 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)1083 : multiset(__f, __l, key_compare(), __a) {}1084# endif1085 1086 template <class _InputIterator>1087 _LIBCPP_HIDE_FROM_ABI1088 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)1089 : __tree_(__comp, __a) {1090 insert(__f, __l);1091 }1092 1093# if _LIBCPP_STD_VER >= 231094 template <_ContainerCompatibleRange<value_type> _Range>1095 _LIBCPP_HIDE_FROM_ABI1096 multiset(from_range_t,1097 _Range&& __range,1098 const key_compare& __comp = key_compare(),1099 const allocator_type& __a = allocator_type())1100 : __tree_(__comp, __a) {1101 insert_range(std::forward<_Range>(__range));1102 }1103 1104 template <_ContainerCompatibleRange<value_type> _Range>1105 _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a)1106 : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}1107# endif1108 1109 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s) = default;1110 1111 _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) = default;1112 1113# ifndef _LIBCPP_CXX03_LANG1114 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) = default;1115 1116 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) {}1117# endif // _LIBCPP_CXX03_LANG1118 _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}1119 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a) : __tree_(__s.__tree_, __a) {}1120 1121# ifndef _LIBCPP_CXX03_LANG1122 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())1123 : __tree_(__comp) {1124 insert(__il.begin(), __il.end());1125 }1126 1127 _LIBCPP_HIDE_FROM_ABI1128 multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)1129 : __tree_(__comp, __a) {1130 insert(__il.begin(), __il.end());1131 }1132 1133# if _LIBCPP_STD_VER >= 141134 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a)1135 : multiset(__il, key_compare(), __a) {}1136# endif1137 1138 _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) {1139 __tree_.__assign_multi(__il.begin(), __il.end());1140 return *this;1141 }1142 1143 _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) = default;1144# endif // _LIBCPP_CXX03_LANG1145 1146 _LIBCPP_HIDE_FROM_ABI ~multiset() {1147 static_assert(sizeof(std::__diagnose_non_const_comparator<_Key, _Compare>()), "");1148 }1149 1150 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }1151 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }1152 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }1153 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }1154 1155 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }1156 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }1157 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }1158 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }1159 1160 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }1161 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }1162 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }1163 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }1164 1165 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }1166 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }1167 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }1168 1169 // modifiers:1170# ifndef _LIBCPP_CXX03_LANG1171 template <class... _Args>1172 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {1173 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);1174 }1175 template <class... _Args>1176 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {1177 return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);1178 }1179# endif // _LIBCPP_CXX03_LANG1180 1181 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__emplace_multi(__v); }1182 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {1183 return __tree_.__emplace_hint_multi(__p, __v);1184 }1185 1186 template <class _InputIterator>1187 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __first, _InputIterator __last) {1188 __tree_.__insert_range_multi(__first, __last);1189 }1190 1191# if _LIBCPP_STD_VER >= 231192 template <_ContainerCompatibleRange<value_type> _Range>1193 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {1194 __tree_.__insert_range_multi(ranges::begin(__range), ranges::end(__range));1195 }1196# endif1197 1198# ifndef _LIBCPP_CXX03_LANG1199 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__emplace_multi(std::move(__v)); }1200 1201 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {1202 return __tree_.__emplace_hint_multi(__p, std::move(__v));1203 }1204 1205 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }1206# endif // _LIBCPP_CXX03_LANG1207 1208 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }1209 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }1210 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }1211 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }1212 1213# if _LIBCPP_STD_VER >= 171214 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {1215 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1216 "node_type with incompatible allocator passed to multiset::insert()");1217 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));1218 }1219 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {1220 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),1221 "node_type with incompatible allocator passed to multiset::insert()");1222 return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));1223 }1224 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {1225 return __tree_.template __node_handle_extract<node_type>(__key);1226 }1227 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {1228 return __tree_.template __node_handle_extract<node_type>(__it);1229 }1230 template <class _Compare2>1231 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {1232 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1233 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1234 __tree_.__node_handle_merge_multi(__source.__tree_);1235 }1236 template <class _Compare2>1237 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {1238 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1239 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1240 __tree_.__node_handle_merge_multi(__source.__tree_);1241 }1242 template <class _Compare2>1243 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {1244 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1245 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1246 __tree_.__node_handle_merge_multi(__source.__tree_);1247 }1248 template <class _Compare2>1249 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {1250 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(1251 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");1252 __tree_.__node_handle_merge_multi(__source.__tree_);1253 }1254# endif1255 1256 _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {1257 __tree_.swap(__s.__tree_);1258 }1259 1260 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }1261 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }1262 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }1263 1264 // set operations:1265 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }1266 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }1267# if _LIBCPP_STD_VER >= 141268 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1269 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {1270 return __tree_.find(__k);1271 }1272 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1273 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {1274 return __tree_.find(__k);1275 }1276# endif1277 1278 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }1279# if _LIBCPP_STD_VER >= 141280 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1281 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {1282 return __tree_.__count_multi(__k);1283 }1284# endif1285 1286# if _LIBCPP_STD_VER >= 201287 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }1288 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1289 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {1290 return find(__k) != end();1291 }1292# endif // _LIBCPP_STD_VER >= 201293 1294 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.__lower_bound_multi(__k); }1295 1296 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const {1297 return __tree_.__lower_bound_multi(__k);1298 }1299 1300# if _LIBCPP_STD_VER >= 141301 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1302 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {1303 return __tree_.__lower_bound_multi(__k);1304 }1305 1306 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1307 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {1308 return __tree_.__lower_bound_multi(__k);1309 }1310# endif1311 1312 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.__upper_bound_multi(__k); }1313 1314 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const {1315 return __tree_.__upper_bound_multi(__k);1316 }1317 1318# if _LIBCPP_STD_VER >= 141319 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1320 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {1321 return __tree_.__upper_bound_multi(__k);1322 }1323 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1324 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {1325 return __tree_.__upper_bound_multi(__k);1326 }1327# endif1328 1329 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {1330 return __tree_.__equal_range_multi(__k);1331 }1332 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {1333 return __tree_.__equal_range_multi(__k);1334 }1335# if _LIBCPP_STD_VER >= 141336 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1337 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {1338 return __tree_.__equal_range_multi(__k);1339 }1340 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>1341 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {1342 return __tree_.__equal_range_multi(__k);1343 }1344# endif1345};1346 1347# if _LIBCPP_STD_VER >= 171348template <class _InputIterator,1349 class _Compare = less<__iterator_value_type<_InputIterator>>,1350 class _Allocator = allocator<__iterator_value_type<_InputIterator>>,1351 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,1352 class = enable_if_t<__is_allocator_v<_Allocator>>,1353 class = enable_if_t<!__is_allocator_v<_Compare>>>1354multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())1355 -> multiset<__iterator_value_type<_InputIterator>, _Compare, _Allocator>;1356 1357# if _LIBCPP_STD_VER >= 231358template <ranges::input_range _Range,1359 class _Compare = less<ranges::range_value_t<_Range>>,1360 class _Allocator = allocator<ranges::range_value_t<_Range>>,1361 class = enable_if_t<__is_allocator_v<_Allocator>>,1362 class = enable_if_t<!__is_allocator_v<_Compare>>>1363multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())1364 -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;1365# endif1366 1367template <class _Key,1368 class _Compare = less<_Key>,1369 class _Allocator = allocator<_Key>,1370 class = enable_if_t<__is_allocator_v<_Allocator>>,1371 class = enable_if_t<!__is_allocator_v<_Compare>>>1372multiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator())1373 -> multiset<_Key, _Compare, _Allocator>;1374 1375template <class _InputIterator,1376 class _Allocator,1377 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,1378 class = enable_if_t<__is_allocator_v<_Allocator>>>1379multiset(_InputIterator, _InputIterator, _Allocator)1380 -> multiset<__iterator_value_type<_InputIterator>, less<__iterator_value_type<_InputIterator>>, _Allocator>;1381 1382# if _LIBCPP_STD_VER >= 231383template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1384multiset(from_range_t, _Range&&, _Allocator)1385 -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;1386# endif1387 1388template <class _Key, class _Allocator, class = enable_if_t<__is_allocator_v<_Allocator>>>1389multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;1390# endif1391 1392template <class _Key, class _Compare, class _Allocator>1393inline _LIBCPP_HIDE_FROM_ABI bool1394operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1395 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());1396}1397 1398# if _LIBCPP_STD_VER <= 171399 1400template <class _Key, class _Compare, class _Allocator>1401inline _LIBCPP_HIDE_FROM_ABI bool1402operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1403 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());1404}1405 1406template <class _Key, class _Compare, class _Allocator>1407inline _LIBCPP_HIDE_FROM_ABI bool1408operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1409 return !(__x == __y);1410}1411 1412template <class _Key, class _Compare, class _Allocator>1413inline _LIBCPP_HIDE_FROM_ABI bool1414operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1415 return __y < __x;1416}1417 1418template <class _Key, class _Compare, class _Allocator>1419inline _LIBCPP_HIDE_FROM_ABI bool1420operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1421 return !(__x < __y);1422}1423 1424template <class _Key, class _Compare, class _Allocator>1425inline _LIBCPP_HIDE_FROM_ABI bool1426operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1427 return !(__y < __x);1428}1429 1430# else // _LIBCPP_STD_VER <= 171431 1432template <class _Key, class _Compare, class _Allocator>1433_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>1434operator<=>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {1435 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);1436}1437 1438# endif // _LIBCPP_STD_VER <= 171439 1440template <class _Key, class _Compare, class _Allocator>1441inline _LIBCPP_HIDE_FROM_ABI void1442swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)1443 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {1444 __x.swap(__y);1445}1446 1447# if _LIBCPP_STD_VER >= 201448template <class _Key, class _Compare, class _Allocator, class _Predicate>1449inline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type1450erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {1451 return std::__libcpp_erase_if_container(__c, __pred);1452}1453# endif1454 1455template <class _Key, class _Compare, class _Allocator>1456struct __container_traits<multiset<_Key, _Compare, _Allocator> > {1457 // http://eel.is/c++draft/associative.reqmts.except#21458 // For associative containers, if an exception is thrown by any operation from within1459 // an insert or emplace function inserting a single element, the insertion has no effect.1460 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;1461 1462 static _LIBCPP_CONSTEXPR const bool __reservable = false;1463};1464 1465_LIBCPP_END_NAMESPACE_STD1466 1467# if _LIBCPP_STD_VER >= 171468_LIBCPP_BEGIN_NAMESPACE_STD1469namespace pmr {1470template <class _KeyT, class _CompareT = std::less<_KeyT>>1471using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;1472 1473template <class _KeyT, class _CompareT = std::less<_KeyT>>1474using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;1475} // namespace pmr1476_LIBCPP_END_NAMESPACE_STD1477# endif1478 1479_LIBCPP_POP_MACROS1480 1481# if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 201482# include <concepts>1483# include <cstdlib>1484# include <functional>1485# include <iterator>1486# include <stdexcept>1487# include <type_traits>1488# endif1489#endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)1490 1491#endif // _LIBCPP_SET1492