Warning, /include/c++/v1/set is written in an unsupported language. File is not indexed.
0001 // -*- C++ -*-
0002 //===----------------------------------------------------------------------===//
0003 //
0004 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0005 // See https://llvm.org/LICENSE.txt for license information.
0006 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0007 //
0008 //===----------------------------------------------------------------------===//
0009
0010 #ifndef _LIBCPP_SET
0011 #define _LIBCPP_SET
0012
0013 /*
0014
0015 set synopsis
0016
0017 namespace std
0018 {
0019
0020 template <class Key, class Compare = less<Key>,
0021 class Allocator = allocator<Key>>
0022 class set
0023 {
0024 public:
0025 // types:
0026 typedef Key key_type;
0027 typedef key_type value_type;
0028 typedef Compare key_compare;
0029 typedef key_compare value_compare;
0030 typedef Allocator allocator_type;
0031 typedef typename allocator_type::reference reference;
0032 typedef typename allocator_type::const_reference const_reference;
0033 typedef typename allocator_type::size_type size_type;
0034 typedef typename allocator_type::difference_type difference_type;
0035 typedef typename allocator_type::pointer pointer;
0036 typedef typename allocator_type::const_pointer const_pointer;
0037
0038 typedef implementation-defined iterator;
0039 typedef implementation-defined const_iterator;
0040 typedef std::reverse_iterator<iterator> reverse_iterator;
0041 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0042 typedef unspecified node_type; // C++17
0043 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
0044
0045 // construct/copy/destroy:
0046 set()
0047 noexcept(
0048 is_nothrow_default_constructible<allocator_type>::value &&
0049 is_nothrow_default_constructible<key_compare>::value &&
0050 is_nothrow_copy_constructible<key_compare>::value);
0051 explicit set(const value_compare& comp);
0052 set(const value_compare& comp, const allocator_type& a);
0053 template <class InputIterator>
0054 set(InputIterator first, InputIterator last,
0055 const value_compare& comp = value_compare());
0056 template <class InputIterator>
0057 set(InputIterator first, InputIterator last, const value_compare& comp,
0058 const allocator_type& a);
0059 template<container-compatible-range<value_type> R>
0060 set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
0061 set(const set& s);
0062 set(set&& s)
0063 noexcept(
0064 is_nothrow_move_constructible<allocator_type>::value &&
0065 is_nothrow_move_constructible<key_compare>::value);
0066 explicit set(const allocator_type& a);
0067 set(const set& s, const allocator_type& a);
0068 set(set&& s, const allocator_type& a);
0069 set(initializer_list<value_type> il, const value_compare& comp = value_compare());
0070 set(initializer_list<value_type> il, const value_compare& comp,
0071 const allocator_type& a);
0072 template <class InputIterator>
0073 set(InputIterator first, InputIterator last, const allocator_type& a)
0074 : set(first, last, Compare(), a) {} // C++14
0075 template<container-compatible-range<value_type> R>
0076 set(from_range_t, R&& rg, const Allocator& a))
0077 : set(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
0078 set(initializer_list<value_type> il, const allocator_type& a)
0079 : set(il, Compare(), a) {} // C++14
0080 ~set();
0081
0082 set& operator=(const set& s);
0083 set& operator=(set&& s)
0084 noexcept(
0085 allocator_type::propagate_on_container_move_assignment::value &&
0086 is_nothrow_move_assignable<allocator_type>::value &&
0087 is_nothrow_move_assignable<key_compare>::value);
0088 set& operator=(initializer_list<value_type> il);
0089
0090 // iterators:
0091 iterator begin() noexcept;
0092 const_iterator begin() const noexcept;
0093 iterator end() noexcept;
0094 const_iterator end() const noexcept;
0095
0096 reverse_iterator rbegin() noexcept;
0097 const_reverse_iterator rbegin() const noexcept;
0098 reverse_iterator rend() noexcept;
0099 const_reverse_iterator rend() const noexcept;
0100
0101 const_iterator cbegin() const noexcept;
0102 const_iterator cend() const noexcept;
0103 const_reverse_iterator crbegin() const noexcept;
0104 const_reverse_iterator crend() const noexcept;
0105
0106 // capacity:
0107 bool empty() const noexcept;
0108 size_type size() const noexcept;
0109 size_type max_size() const noexcept;
0110
0111 // modifiers:
0112 template <class... Args>
0113 pair<iterator, bool> emplace(Args&&... args);
0114 template <class... Args>
0115 iterator emplace_hint(const_iterator position, Args&&... args);
0116 pair<iterator,bool> insert(const value_type& v);
0117 pair<iterator,bool> insert(value_type&& v);
0118 iterator insert(const_iterator position, const value_type& v);
0119 iterator insert(const_iterator position, value_type&& v);
0120 template <class InputIterator>
0121 void insert(InputIterator first, InputIterator last);
0122 template<container-compatible-range<value_type> R>
0123 void insert_range(R&& rg); // C++23
0124 void insert(initializer_list<value_type> il);
0125
0126 node_type extract(const_iterator position); // C++17
0127 node_type extract(const key_type& x); // C++17
0128 insert_return_type insert(node_type&& nh); // C++17
0129 iterator insert(const_iterator hint, node_type&& nh); // C++17
0130
0131 iterator erase(const_iterator position);
0132 iterator erase(iterator position); // C++14
0133 size_type erase(const key_type& k);
0134 iterator erase(const_iterator first, const_iterator last);
0135 void clear() noexcept;
0136
0137 template<class C2>
0138 void merge(set<Key, C2, Allocator>& source); // C++17
0139 template<class C2>
0140 void merge(set<Key, C2, Allocator>&& source); // C++17
0141 template<class C2>
0142 void merge(multiset<Key, C2, Allocator>& source); // C++17
0143 template<class C2>
0144 void merge(multiset<Key, C2, Allocator>&& source); // C++17
0145
0146 void swap(set& s)
0147 noexcept(
0148 __is_nothrow_swappable<key_compare>::value &&
0149 (!allocator_type::propagate_on_container_swap::value ||
0150 __is_nothrow_swappable<allocator_type>::value));
0151
0152 // observers:
0153 allocator_type get_allocator() const noexcept;
0154 key_compare key_comp() const;
0155 value_compare value_comp() const;
0156
0157 // set operations:
0158 iterator find(const key_type& k);
0159 const_iterator find(const key_type& k) const;
0160 template<typename K>
0161 iterator find(const K& x);
0162 template<typename K>
0163 const_iterator find(const K& x) const; // C++14
0164
0165 template<typename K>
0166 size_type count(const K& x) const; // C++14
0167 size_type count(const key_type& k) const;
0168
0169 bool contains(const key_type& x) const; // C++20
0170 template<class K> bool contains(const K& x) const; // C++20
0171
0172 iterator lower_bound(const key_type& k);
0173 const_iterator lower_bound(const key_type& k) const;
0174 template<typename K>
0175 iterator lower_bound(const K& x); // C++14
0176 template<typename K>
0177 const_iterator lower_bound(const K& x) const; // C++14
0178
0179 iterator upper_bound(const key_type& k);
0180 const_iterator upper_bound(const key_type& k) const;
0181 template<typename K>
0182 iterator upper_bound(const K& x); // C++14
0183 template<typename K>
0184 const_iterator upper_bound(const K& x) const; // C++14
0185 pair<iterator,iterator> equal_range(const key_type& k);
0186 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
0187 template<typename K>
0188 pair<iterator,iterator> equal_range(const K& x); // C++14
0189 template<typename K>
0190 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
0191 };
0192
0193 template <class InputIterator,
0194 class Compare = less<typename iterator_traits<InputIterator>::value_type>,
0195 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0196 set(InputIterator, InputIterator,
0197 Compare = Compare(), Allocator = Allocator())
0198 -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
0199
0200 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
0201 class Allocator = allocator<ranges::range_value_t<R>>>
0202 set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
0203 -> set<ranges::range_value_t<R>, Compare, Allocator>; // C++23
0204
0205 template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
0206 set(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
0207 -> set<Key, Compare, Allocator>; // C++17
0208
0209 template<class InputIterator, class Allocator>
0210 set(InputIterator, InputIterator, Allocator)
0211 -> set<typename iterator_traits<InputIterator>::value_type,
0212 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
0213
0214 template<ranges::input_range R, class Allocator>
0215 set(from_range_t, R&&, Allocator)
0216 -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; // C++23
0217
0218 template<class Key, class Allocator>
0219 set(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17
0220
0221 template <class Key, class Compare, class Allocator>
0222 bool
0223 operator==(const set<Key, Compare, Allocator>& x,
0224 const set<Key, Compare, Allocator>& y);
0225
0226 template <class Key, class Compare, class Allocator>
0227 bool
0228 operator< (const set<Key, Compare, Allocator>& x,
0229 const set<Key, Compare, Allocator>& y); // removed in C++20
0230
0231 template <class Key, class Compare, class Allocator>
0232 bool
0233 operator!=(const set<Key, Compare, Allocator>& x,
0234 const set<Key, Compare, Allocator>& y); // removed in C++20
0235
0236 template <class Key, class Compare, class Allocator>
0237 bool
0238 operator> (const set<Key, Compare, Allocator>& x,
0239 const set<Key, Compare, Allocator>& y); // removed in C++20
0240
0241 template <class Key, class Compare, class Allocator>
0242 bool
0243 operator>=(const set<Key, Compare, Allocator>& x,
0244 const set<Key, Compare, Allocator>& y); // removed in C++20
0245
0246 template <class Key, class Compare, class Allocator>
0247 bool
0248 operator<=(const set<Key, Compare, Allocator>& x,
0249 const set<Key, Compare, Allocator>& y); // removed in C++20
0250
0251 template<class Key, class Compare, class Allocator>
0252 synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x,
0253 const set<Key, Compare, Allocator>& y); // since C++20
0254
0255 // specialized algorithms:
0256 template <class Key, class Compare, class Allocator>
0257 void
0258 swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y)
0259 noexcept(noexcept(x.swap(y)));
0260
0261 template <class Key, class Compare, class Allocator, class Predicate>
0262 typename set<Key, Compare, Allocator>::size_type
0263 erase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20
0264
0265 template <class Key, class Compare = less<Key>,
0266 class Allocator = allocator<Key>>
0267 class multiset
0268 {
0269 public:
0270 // types:
0271 typedef Key key_type;
0272 typedef key_type value_type;
0273 typedef Compare key_compare;
0274 typedef key_compare value_compare;
0275 typedef Allocator allocator_type;
0276 typedef typename allocator_type::reference reference;
0277 typedef typename allocator_type::const_reference const_reference;
0278 typedef typename allocator_type::size_type size_type;
0279 typedef typename allocator_type::difference_type difference_type;
0280 typedef typename allocator_type::pointer pointer;
0281 typedef typename allocator_type::const_pointer const_pointer;
0282
0283 typedef implementation-defined iterator;
0284 typedef implementation-defined const_iterator;
0285 typedef std::reverse_iterator<iterator> reverse_iterator;
0286 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0287 typedef unspecified node_type; // C++17
0288
0289 // construct/copy/destroy:
0290 multiset()
0291 noexcept(
0292 is_nothrow_default_constructible<allocator_type>::value &&
0293 is_nothrow_default_constructible<key_compare>::value &&
0294 is_nothrow_copy_constructible<key_compare>::value);
0295 explicit multiset(const value_compare& comp);
0296 multiset(const value_compare& comp, const allocator_type& a);
0297 template <class InputIterator>
0298 multiset(InputIterator first, InputIterator last,
0299 const value_compare& comp = value_compare());
0300 template <class InputIterator>
0301 multiset(InputIterator first, InputIterator last,
0302 const value_compare& comp, const allocator_type& a);
0303 template<container-compatible-range<value_type> R>
0304 multiset(from_range_t, R&& rg,
0305 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
0306 multiset(const multiset& s);
0307 multiset(multiset&& s)
0308 noexcept(
0309 is_nothrow_move_constructible<allocator_type>::value &&
0310 is_nothrow_move_constructible<key_compare>::value);
0311 explicit multiset(const allocator_type& a);
0312 multiset(const multiset& s, const allocator_type& a);
0313 multiset(multiset&& s, const allocator_type& a);
0314 multiset(initializer_list<value_type> il, const value_compare& comp = value_compare());
0315 multiset(initializer_list<value_type> il, const value_compare& comp,
0316 const allocator_type& a);
0317 template <class InputIterator>
0318 multiset(InputIterator first, InputIterator last, const allocator_type& a)
0319 : set(first, last, Compare(), a) {} // C++14
0320 template<container-compatible-range<value_type> R>
0321 multiset(from_range_t, R&& rg, const Allocator& a))
0322 : multiset(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
0323 multiset(initializer_list<value_type> il, const allocator_type& a)
0324 : set(il, Compare(), a) {} // C++14
0325 ~multiset();
0326
0327 multiset& operator=(const multiset& s);
0328 multiset& operator=(multiset&& s)
0329 noexcept(
0330 allocator_type::propagate_on_container_move_assignment::value &&
0331 is_nothrow_move_assignable<allocator_type>::value &&
0332 is_nothrow_move_assignable<key_compare>::value);
0333 multiset& operator=(initializer_list<value_type> il);
0334
0335 // iterators:
0336 iterator begin() noexcept;
0337 const_iterator begin() const noexcept;
0338 iterator end() noexcept;
0339 const_iterator end() const noexcept;
0340
0341 reverse_iterator rbegin() noexcept;
0342 const_reverse_iterator rbegin() const noexcept;
0343 reverse_iterator rend() noexcept;
0344 const_reverse_iterator rend() const noexcept;
0345
0346 const_iterator cbegin() const noexcept;
0347 const_iterator cend() const noexcept;
0348 const_reverse_iterator crbegin() const noexcept;
0349 const_reverse_iterator crend() const noexcept;
0350
0351 // capacity:
0352 bool empty() const noexcept;
0353 size_type size() const noexcept;
0354 size_type max_size() const noexcept;
0355
0356 // modifiers:
0357 template <class... Args>
0358 iterator emplace(Args&&... args);
0359 template <class... Args>
0360 iterator emplace_hint(const_iterator position, Args&&... args);
0361 iterator insert(const value_type& v);
0362 iterator insert(value_type&& v);
0363 iterator insert(const_iterator position, const value_type& v);
0364 iterator insert(const_iterator position, value_type&& v);
0365 template <class InputIterator>
0366 void insert(InputIterator first, InputIterator last);
0367 template<container-compatible-range<value_type> R>
0368 void insert_range(R&& rg); // C++23
0369 void insert(initializer_list<value_type> il);
0370
0371 node_type extract(const_iterator position); // C++17
0372 node_type extract(const key_type& x); // C++17
0373 iterator insert(node_type&& nh); // C++17
0374 iterator insert(const_iterator hint, node_type&& nh); // C++17
0375
0376 iterator erase(const_iterator position);
0377 iterator erase(iterator position); // C++14
0378 size_type erase(const key_type& k);
0379 iterator erase(const_iterator first, const_iterator last);
0380 void clear() noexcept;
0381
0382 template<class C2>
0383 void merge(multiset<Key, C2, Allocator>& source); // C++17
0384 template<class C2>
0385 void merge(multiset<Key, C2, Allocator>&& source); // C++17
0386 template<class C2>
0387 void merge(set<Key, C2, Allocator>& source); // C++17
0388 template<class C2>
0389 void merge(set<Key, C2, Allocator>&& source); // C++17
0390
0391 void swap(multiset& s)
0392 noexcept(
0393 __is_nothrow_swappable<key_compare>::value &&
0394 (!allocator_type::propagate_on_container_swap::value ||
0395 __is_nothrow_swappable<allocator_type>::value));
0396
0397 // observers:
0398 allocator_type get_allocator() const noexcept;
0399 key_compare key_comp() const;
0400 value_compare value_comp() const;
0401
0402 // set operations:
0403 iterator find(const key_type& k);
0404 const_iterator find(const key_type& k) const;
0405 template<typename K>
0406 iterator find(const K& x);
0407 template<typename K>
0408 const_iterator find(const K& x) const; // C++14
0409
0410 template<typename K>
0411 size_type count(const K& x) const; // C++14
0412 size_type count(const key_type& k) const;
0413
0414 bool contains(const key_type& x) const; // C++20
0415 template<class K> bool contains(const K& x) const; // C++20
0416
0417 iterator lower_bound(const key_type& k);
0418 const_iterator lower_bound(const key_type& k) const;
0419 template<typename K>
0420 iterator lower_bound(const K& x); // C++14
0421 template<typename K>
0422 const_iterator lower_bound(const K& x) const; // C++14
0423
0424 iterator upper_bound(const key_type& k);
0425 const_iterator upper_bound(const key_type& k) const;
0426 template<typename K>
0427 iterator upper_bound(const K& x); // C++14
0428 template<typename K>
0429 const_iterator upper_bound(const K& x) const; // C++14
0430
0431 pair<iterator,iterator> equal_range(const key_type& k);
0432 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
0433 template<typename K>
0434 pair<iterator,iterator> equal_range(const K& x); // C++14
0435 template<typename K>
0436 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
0437 };
0438
0439 template <class InputIterator,
0440 class Compare = less<typename iterator_traits<InputIterator>::value_type>,
0441 class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
0442 multiset(InputIterator, InputIterator,
0443 Compare = Compare(), Allocator = Allocator())
0444 -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17
0445
0446 template<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>,
0447 class Allocator = allocator<ranges::range_value_t<R>>>
0448 multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
0449 -> multiset<ranges::range_value_t<R>, Compare, Allocator>;
0450
0451 template<class Key, class Compare = less<Key>, class Allocator = allocator<Key>>
0452 multiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator())
0453 -> multiset<Key, Compare, Allocator>; // C++17
0454
0455 template<class InputIterator, class Allocator>
0456 multiset(InputIterator, InputIterator, Allocator)
0457 -> multiset<typename iterator_traits<InputIterator>::value_type,
0458 less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17
0459
0460 template<ranges::input_range R, class Allocator>
0461 multiset(from_range_t, R&&, Allocator)
0462 -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>;
0463
0464 template<class Key, class Allocator>
0465 multiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17
0466
0467 template <class Key, class Compare, class Allocator>
0468 bool
0469 operator==(const multiset<Key, Compare, Allocator>& x,
0470 const multiset<Key, Compare, Allocator>& y);
0471
0472 template <class Key, class Compare, class Allocator>
0473 bool
0474 operator< (const multiset<Key, Compare, Allocator>& x,
0475 const multiset<Key, Compare, Allocator>& y); // removed in C++20
0476
0477 template <class Key, class Compare, class Allocator>
0478 bool
0479 operator!=(const multiset<Key, Compare, Allocator>& x,
0480 const multiset<Key, Compare, Allocator>& y); // removed in C++20
0481
0482 template <class Key, class Compare, class Allocator>
0483 bool
0484 operator> (const multiset<Key, Compare, Allocator>& x,
0485 const multiset<Key, Compare, Allocator>& y); // removed in C++20
0486
0487 template <class Key, class Compare, class Allocator>
0488 bool
0489 operator>=(const multiset<Key, Compare, Allocator>& x,
0490 const multiset<Key, Compare, Allocator>& y); // removed in C++20
0491
0492 template <class Key, class Compare, class Allocator>
0493 bool
0494 operator<=(const multiset<Key, Compare, Allocator>& x,
0495 const multiset<Key, Compare, Allocator>& y); // removed in C++20
0496
0497 template<class Key, class Compare, class Allocator>
0498 synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x,
0499 const multiset<Key, Compare, Allocator>& y); // since C++20
0500
0501 // specialized algorithms:
0502 template <class Key, class Compare, class Allocator>
0503 void
0504 swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
0505 noexcept(noexcept(x.swap(y)));
0506
0507 template <class Key, class Compare, class Allocator, class Predicate>
0508 typename multiset<Key, Compare, Allocator>::size_type
0509 erase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20
0510
0511 } // std
0512
0513 */
0514
0515 #if __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
0516 # include <__cxx03/set>
0517 #else
0518 # include <__algorithm/equal.h>
0519 # include <__algorithm/lexicographical_compare.h>
0520 # include <__algorithm/lexicographical_compare_three_way.h>
0521 # include <__assert>
0522 # include <__config>
0523 # include <__functional/is_transparent.h>
0524 # include <__functional/operations.h>
0525 # include <__iterator/erase_if_container.h>
0526 # include <__iterator/iterator_traits.h>
0527 # include <__iterator/ranges_iterator_traits.h>
0528 # include <__iterator/reverse_iterator.h>
0529 # include <__memory/allocator.h>
0530 # include <__memory/allocator_traits.h>
0531 # include <__memory_resource/polymorphic_allocator.h>
0532 # include <__node_handle>
0533 # include <__ranges/concepts.h>
0534 # include <__ranges/container_compatible_range.h>
0535 # include <__ranges/from_range.h>
0536 # include <__tree>
0537 # include <__type_traits/container_traits.h>
0538 # include <__type_traits/enable_if.h>
0539 # include <__type_traits/is_allocator.h>
0540 # include <__type_traits/is_nothrow_assignable.h>
0541 # include <__type_traits/is_nothrow_constructible.h>
0542 # include <__type_traits/is_same.h>
0543 # include <__type_traits/is_swappable.h>
0544 # include <__type_traits/type_identity.h>
0545 # include <__utility/forward.h>
0546 # include <__utility/move.h>
0547 # include <__utility/pair.h>
0548 # include <version>
0549
0550 // standard-mandated includes
0551
0552 // [iterator.range]
0553 # include <__iterator/access.h>
0554 # include <__iterator/data.h>
0555 # include <__iterator/empty.h>
0556 # include <__iterator/reverse_access.h>
0557 # include <__iterator/size.h>
0558
0559 // [associative.set.syn]
0560 # include <compare>
0561 # include <initializer_list>
0562
0563 # if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0564 # pragma GCC system_header
0565 # endif
0566
0567 _LIBCPP_PUSH_MACROS
0568 # include <__undef_macros>
0569
0570 _LIBCPP_BEGIN_NAMESPACE_STD
0571
0572 template <class _Key, class _Compare, class _Allocator>
0573 class multiset;
0574
0575 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
0576 class _LIBCPP_TEMPLATE_VIS set {
0577 public:
0578 // types:
0579 typedef _Key key_type;
0580 typedef key_type value_type;
0581 typedef __type_identity_t<_Compare> key_compare;
0582 typedef key_compare value_compare;
0583 typedef __type_identity_t<_Allocator> allocator_type;
0584 typedef value_type& reference;
0585 typedef const value_type& const_reference;
0586
0587 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
0588 "Allocator::value_type must be same type as value_type");
0589
0590 private:
0591 typedef __tree<value_type, value_compare, allocator_type> __base;
0592 typedef allocator_traits<allocator_type> __alloc_traits;
0593
0594 static_assert(__check_valid_allocator<allocator_type>::value, "");
0595
0596 __base __tree_;
0597
0598 public:
0599 typedef typename __base::pointer pointer;
0600 typedef typename __base::const_pointer const_pointer;
0601 typedef typename __base::size_type size_type;
0602 typedef typename __base::difference_type difference_type;
0603 typedef typename __base::const_iterator iterator;
0604 typedef typename __base::const_iterator const_iterator;
0605 typedef std::reverse_iterator<iterator> reverse_iterator;
0606 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0607
0608 # if _LIBCPP_STD_VER >= 17
0609 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
0610 typedef __insert_return_type<iterator, node_type> insert_return_type;
0611 # endif
0612
0613 template <class _Key2, class _Compare2, class _Alloc2>
0614 friend class _LIBCPP_TEMPLATE_VIS set;
0615 template <class _Key2, class _Compare2, class _Alloc2>
0616 friend class _LIBCPP_TEMPLATE_VIS multiset;
0617
0618 _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_(
0619 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
0620 is_nothrow_copy_constructible<key_compare>::value)
0621 : __tree_(value_compare()) {}
0622
0623 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_(
0624 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
0625 : __tree_(__comp) {}
0626
0627 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}
0628 template <class _InputIterator>
0629 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
0630 : __tree_(__comp) {
0631 insert(__f, __l);
0632 }
0633
0634 template <class _InputIterator>
0635 _LIBCPP_HIDE_FROM_ABI
0636 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
0637 : __tree_(__comp, __a) {
0638 insert(__f, __l);
0639 }
0640
0641 # if _LIBCPP_STD_VER >= 23
0642 template <_ContainerCompatibleRange<value_type> _Range>
0643 _LIBCPP_HIDE_FROM_ABI
0644 set(from_range_t,
0645 _Range&& __range,
0646 const key_compare& __comp = key_compare(),
0647 const allocator_type& __a = allocator_type())
0648 : __tree_(__comp, __a) {
0649 insert_range(std::forward<_Range>(__range));
0650 }
0651 # endif
0652
0653 # if _LIBCPP_STD_VER >= 14
0654 template <class _InputIterator>
0655 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
0656 : set(__f, __l, key_compare(), __a) {}
0657 # endif
0658
0659 # if _LIBCPP_STD_VER >= 23
0660 template <_ContainerCompatibleRange<value_type> _Range>
0661 _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a)
0662 : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
0663 # endif
0664
0665 _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); }
0666
0667 _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) {
0668 __tree_ = __s.__tree_;
0669 return *this;
0670 }
0671
0672 # ifndef _LIBCPP_CXX03_LANG
0673 _LIBCPP_HIDE_FROM_ABI set(set&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
0674 : __tree_(std::move(__s.__tree_)) {}
0675 # endif // _LIBCPP_CXX03_LANG
0676
0677 _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}
0678
0679 _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) {
0680 insert(__s.begin(), __s.end());
0681 }
0682
0683 # ifndef _LIBCPP_CXX03_LANG
0684 _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
0685
0686 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
0687 : __tree_(__comp) {
0688 insert(__il.begin(), __il.end());
0689 }
0690
0691 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
0692 : __tree_(__comp, __a) {
0693 insert(__il.begin(), __il.end());
0694 }
0695
0696 # if _LIBCPP_STD_VER >= 14
0697 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a)
0698 : set(__il, key_compare(), __a) {}
0699 # endif
0700
0701 _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) {
0702 __tree_.__assign_unique(__il.begin(), __il.end());
0703 return *this;
0704 }
0705
0706 _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) noexcept(is_nothrow_move_assignable<__base>::value) {
0707 __tree_ = std::move(__s.__tree_);
0708 return *this;
0709 }
0710 # endif // _LIBCPP_CXX03_LANG
0711
0712 _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
0713
0714 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
0715 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
0716 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
0717 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
0718
0719 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
0720 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
0721 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
0722 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
0723
0724 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
0725 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
0726 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
0727 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
0728
0729 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
0730 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
0731 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
0732
0733 // modifiers:
0734 # ifndef _LIBCPP_CXX03_LANG
0735 template <class... _Args>
0736 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
0737 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
0738 }
0739 template <class... _Args>
0740 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
0741 return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
0742 }
0743 # endif // _LIBCPP_CXX03_LANG
0744
0745 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
0746 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
0747 return __tree_.__insert_unique(__p, __v);
0748 }
0749
0750 template <class _InputIterator>
0751 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
0752 for (const_iterator __e = cend(); __f != __l; ++__f)
0753 __tree_.__insert_unique(__e, *__f);
0754 }
0755
0756 # if _LIBCPP_STD_VER >= 23
0757 template <_ContainerCompatibleRange<value_type> _Range>
0758 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
0759 const_iterator __end = cend();
0760 for (auto&& __element : __range) {
0761 __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
0762 }
0763 }
0764 # endif
0765
0766 # ifndef _LIBCPP_CXX03_LANG
0767 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
0768 return __tree_.__insert_unique(std::move(__v));
0769 }
0770
0771 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
0772 return __tree_.__insert_unique(__p, std::move(__v));
0773 }
0774
0775 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
0776 # endif // _LIBCPP_CXX03_LANG
0777
0778 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
0779 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
0780 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
0781 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
0782
0783 # if _LIBCPP_STD_VER >= 17
0784 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
0785 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0786 "node_type with incompatible allocator passed to set::insert()");
0787 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
0788 }
0789 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
0790 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0791 "node_type with incompatible allocator passed to set::insert()");
0792 return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));
0793 }
0794 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
0795 return __tree_.template __node_handle_extract<node_type>(__key);
0796 }
0797 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
0798 return __tree_.template __node_handle_extract<node_type>(__it);
0799 }
0800 template <class _Compare2>
0801 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
0802 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0803 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0804 __tree_.__node_handle_merge_unique(__source.__tree_);
0805 }
0806 template <class _Compare2>
0807 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
0808 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0809 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0810 __tree_.__node_handle_merge_unique(__source.__tree_);
0811 }
0812 template <class _Compare2>
0813 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
0814 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0815 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0816 __tree_.__node_handle_merge_unique(__source.__tree_);
0817 }
0818 template <class _Compare2>
0819 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
0820 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0821 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0822 __tree_.__node_handle_merge_unique(__source.__tree_);
0823 }
0824 # endif
0825
0826 _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__s.__tree_); }
0827
0828 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
0829 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
0830 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
0831
0832 // set operations:
0833 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
0834 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
0835 # if _LIBCPP_STD_VER >= 14
0836 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0837 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
0838 return __tree_.find(__k);
0839 }
0840 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0841 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
0842 return __tree_.find(__k);
0843 }
0844 # endif
0845
0846 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
0847 # if _LIBCPP_STD_VER >= 14
0848 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0849 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
0850 return __tree_.__count_multi(__k);
0851 }
0852 # endif
0853
0854 # if _LIBCPP_STD_VER >= 20
0855 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
0856 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0857 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
0858 return find(__k) != end();
0859 }
0860 # endif // _LIBCPP_STD_VER >= 20
0861
0862 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
0863 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
0864 # if _LIBCPP_STD_VER >= 14
0865 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0866 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
0867 return __tree_.lower_bound(__k);
0868 }
0869
0870 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0871 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
0872 return __tree_.lower_bound(__k);
0873 }
0874 # endif
0875
0876 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
0877 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
0878 # if _LIBCPP_STD_VER >= 14
0879 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0880 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
0881 return __tree_.upper_bound(__k);
0882 }
0883 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0884 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
0885 return __tree_.upper_bound(__k);
0886 }
0887 # endif
0888
0889 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
0890 return __tree_.__equal_range_unique(__k);
0891 }
0892 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0893 return __tree_.__equal_range_unique(__k);
0894 }
0895 # if _LIBCPP_STD_VER >= 14
0896 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0897 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
0898 return __tree_.__equal_range_multi(__k);
0899 }
0900 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0901 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
0902 return __tree_.__equal_range_multi(__k);
0903 }
0904 # endif
0905 };
0906
0907 # if _LIBCPP_STD_VER >= 17
0908 template <class _InputIterator,
0909 class _Compare = less<__iter_value_type<_InputIterator>>,
0910 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
0911 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
0912 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
0913 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
0914 set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
0915 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
0916
0917 # if _LIBCPP_STD_VER >= 23
0918 template <ranges::input_range _Range,
0919 class _Compare = less<ranges::range_value_t<_Range>>,
0920 class _Allocator = allocator<ranges::range_value_t<_Range>>,
0921 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
0922 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
0923 set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
0924 -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
0925 # endif
0926
0927 template <class _Key,
0928 class _Compare = less<_Key>,
0929 class _Allocator = allocator<_Key>,
0930 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
0931 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0932 set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;
0933
0934 template <class _InputIterator,
0935 class _Allocator,
0936 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
0937 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0938 set(_InputIterator,
0939 _InputIterator,
0940 _Allocator) -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
0941
0942 # if _LIBCPP_STD_VER >= 23
0943 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0944 set(from_range_t,
0945 _Range&&,
0946 _Allocator) -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
0947 # endif
0948
0949 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0950 set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;
0951 # endif
0952
0953 # ifndef _LIBCPP_CXX03_LANG
0954
0955 template <class _Key, class _Compare, class _Allocator>
0956 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) {
0957 if (__a != __s.get_allocator()) {
0958 const_iterator __e = cend();
0959 while (!__s.empty())
0960 insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
0961 }
0962 }
0963
0964 # endif // _LIBCPP_CXX03_LANG
0965
0966 template <class _Key, class _Compare, class _Allocator>
0967 inline _LIBCPP_HIDE_FROM_ABI bool
0968 operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0969 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
0970 }
0971
0972 # if _LIBCPP_STD_VER <= 17
0973
0974 template <class _Key, class _Compare, class _Allocator>
0975 inline _LIBCPP_HIDE_FROM_ABI bool
0976 operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0977 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
0978 }
0979
0980 template <class _Key, class _Compare, class _Allocator>
0981 inline _LIBCPP_HIDE_FROM_ABI bool
0982 operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0983 return !(__x == __y);
0984 }
0985
0986 template <class _Key, class _Compare, class _Allocator>
0987 inline _LIBCPP_HIDE_FROM_ABI bool
0988 operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0989 return __y < __x;
0990 }
0991
0992 template <class _Key, class _Compare, class _Allocator>
0993 inline _LIBCPP_HIDE_FROM_ABI bool
0994 operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0995 return !(__x < __y);
0996 }
0997
0998 template <class _Key, class _Compare, class _Allocator>
0999 inline _LIBCPP_HIDE_FROM_ABI bool
1000 operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1001 return !(__y < __x);
1002 }
1003
1004 # else // _LIBCPP_STD_VER <= 17
1005
1006 template <class _Key, class _Compare, class _Allocator>
1007 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1008 operator<=>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
1009 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
1010 }
1011
1012 # endif // _LIBCPP_STD_VER <= 17
1013
1014 // specialized algorithms:
1015 template <class _Key, class _Compare, class _Allocator>
1016 inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y)
1017 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1018 __x.swap(__y);
1019 }
1020
1021 # if _LIBCPP_STD_VER >= 20
1022 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1023 inline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type
1024 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1025 return std::__libcpp_erase_if_container(__c, __pred);
1026 }
1027 # endif
1028
1029 template <class _Key, class _Compare, class _Allocator>
1030 struct __container_traits<set<_Key, _Compare, _Allocator> > {
1031 // http://eel.is/c++draft/associative.reqmts.except#2
1032 // For associative containers, if an exception is thrown by any operation from within
1033 // an insert or emplace function inserting a single element, the insertion has no effect.
1034 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1035 };
1036
1037 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
1038 class _LIBCPP_TEMPLATE_VIS multiset {
1039 public:
1040 // types:
1041 typedef _Key key_type;
1042 typedef key_type value_type;
1043 typedef __type_identity_t<_Compare> key_compare;
1044 typedef key_compare value_compare;
1045 typedef __type_identity_t<_Allocator> allocator_type;
1046 typedef value_type& reference;
1047 typedef const value_type& const_reference;
1048
1049 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1050 "Allocator::value_type must be same type as value_type");
1051
1052 private:
1053 typedef __tree<value_type, value_compare, allocator_type> __base;
1054 typedef allocator_traits<allocator_type> __alloc_traits;
1055
1056 static_assert(__check_valid_allocator<allocator_type>::value, "");
1057
1058 __base __tree_;
1059
1060 public:
1061 typedef typename __base::pointer pointer;
1062 typedef typename __base::const_pointer const_pointer;
1063 typedef typename __base::size_type size_type;
1064 typedef typename __base::difference_type difference_type;
1065 typedef typename __base::const_iterator iterator;
1066 typedef typename __base::const_iterator const_iterator;
1067 typedef std::reverse_iterator<iterator> reverse_iterator;
1068 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1069
1070 # if _LIBCPP_STD_VER >= 17
1071 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1072 # endif
1073
1074 template <class _Key2, class _Compare2, class _Alloc2>
1075 friend class _LIBCPP_TEMPLATE_VIS set;
1076 template <class _Key2, class _Compare2, class _Alloc2>
1077 friend class _LIBCPP_TEMPLATE_VIS multiset;
1078
1079 // construct/copy/destroy:
1080 _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_(
1081 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1082 is_nothrow_copy_constructible<key_compare>::value)
1083 : __tree_(value_compare()) {}
1084
1085 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_(
1086 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1087 : __tree_(__comp) {}
1088
1089 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)
1090 : __tree_(__comp, __a) {}
1091 template <class _InputIterator>
1092 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
1093 : __tree_(__comp) {
1094 insert(__f, __l);
1095 }
1096
1097 # if _LIBCPP_STD_VER >= 14
1098 template <class _InputIterator>
1099 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1100 : multiset(__f, __l, key_compare(), __a) {}
1101 # endif
1102
1103 template <class _InputIterator>
1104 _LIBCPP_HIDE_FROM_ABI
1105 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
1106 : __tree_(__comp, __a) {
1107 insert(__f, __l);
1108 }
1109
1110 # if _LIBCPP_STD_VER >= 23
1111 template <_ContainerCompatibleRange<value_type> _Range>
1112 _LIBCPP_HIDE_FROM_ABI
1113 multiset(from_range_t,
1114 _Range&& __range,
1115 const key_compare& __comp = key_compare(),
1116 const allocator_type& __a = allocator_type())
1117 : __tree_(__comp, __a) {
1118 insert_range(std::forward<_Range>(__range));
1119 }
1120
1121 template <_ContainerCompatibleRange<value_type> _Range>
1122 _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1123 : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1124 # endif
1125
1126 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s)
1127 : __tree_(__s.__tree_.value_comp(),
1128 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) {
1129 insert(__s.begin(), __s.end());
1130 }
1131
1132 _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) {
1133 __tree_ = __s.__tree_;
1134 return *this;
1135 }
1136
1137 # ifndef _LIBCPP_CXX03_LANG
1138 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
1139 : __tree_(std::move(__s.__tree_)) {}
1140
1141 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1142 # endif // _LIBCPP_CXX03_LANG
1143 _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}
1144 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a)
1145 : __tree_(__s.__tree_.value_comp(), __a) {
1146 insert(__s.begin(), __s.end());
1147 }
1148
1149 # ifndef _LIBCPP_CXX03_LANG
1150 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1151 : __tree_(__comp) {
1152 insert(__il.begin(), __il.end());
1153 }
1154
1155 _LIBCPP_HIDE_FROM_ABI
1156 multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
1157 : __tree_(__comp, __a) {
1158 insert(__il.begin(), __il.end());
1159 }
1160
1161 # if _LIBCPP_STD_VER >= 14
1162 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a)
1163 : multiset(__il, key_compare(), __a) {}
1164 # endif
1165
1166 _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) {
1167 __tree_.__assign_multi(__il.begin(), __il.end());
1168 return *this;
1169 }
1170
1171 _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1172 __tree_ = std::move(__s.__tree_);
1173 return *this;
1174 }
1175 # endif // _LIBCPP_CXX03_LANG
1176
1177 _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1178
1179 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1180 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1181 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1182 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1183
1184 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1185 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1186 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1187 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1188
1189 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1190 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1191 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1192 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1193
1194 [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1195 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1196 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1197
1198 // modifiers:
1199 # ifndef _LIBCPP_CXX03_LANG
1200 template <class... _Args>
1201 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1202 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1203 }
1204 template <class... _Args>
1205 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1206 return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1207 }
1208 # endif // _LIBCPP_CXX03_LANG
1209
1210 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1211 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1212 return __tree_.__insert_multi(__p, __v);
1213 }
1214
1215 template <class _InputIterator>
1216 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1217 for (const_iterator __e = cend(); __f != __l; ++__f)
1218 __tree_.__insert_multi(__e, *__f);
1219 }
1220
1221 # if _LIBCPP_STD_VER >= 23
1222 template <_ContainerCompatibleRange<value_type> _Range>
1223 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1224 const_iterator __end = cend();
1225 for (auto&& __element : __range) {
1226 __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1227 }
1228 }
1229 # endif
1230
1231 # ifndef _LIBCPP_CXX03_LANG
1232 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1233
1234 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1235 return __tree_.__insert_multi(__p, std::move(__v));
1236 }
1237
1238 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1239 # endif // _LIBCPP_CXX03_LANG
1240
1241 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
1242 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1243 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
1244 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1245
1246 # if _LIBCPP_STD_VER >= 17
1247 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1248 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1249 "node_type with incompatible allocator passed to multiset::insert()");
1250 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1251 }
1252 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1253 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1254 "node_type with incompatible allocator passed to multiset::insert()");
1255 return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1256 }
1257 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1258 return __tree_.template __node_handle_extract<node_type>(__key);
1259 }
1260 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1261 return __tree_.template __node_handle_extract<node_type>(__it);
1262 }
1263 template <class _Compare2>
1264 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
1265 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1266 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1267 __tree_.__node_handle_merge_multi(__source.__tree_);
1268 }
1269 template <class _Compare2>
1270 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
1271 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1272 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1273 __tree_.__node_handle_merge_multi(__source.__tree_);
1274 }
1275 template <class _Compare2>
1276 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
1277 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1278 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1279 __tree_.__node_handle_merge_multi(__source.__tree_);
1280 }
1281 template <class _Compare2>
1282 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
1283 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1284 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1285 __tree_.__node_handle_merge_multi(__source.__tree_);
1286 }
1287 # endif
1288
1289 _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1290 __tree_.swap(__s.__tree_);
1291 }
1292
1293 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
1294 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
1295 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
1296
1297 // set operations:
1298 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1299 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1300 # if _LIBCPP_STD_VER >= 14
1301 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1302 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1303 return __tree_.find(__k);
1304 }
1305 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1306 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1307 return __tree_.find(__k);
1308 }
1309 # endif
1310
1311 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1312 # if _LIBCPP_STD_VER >= 14
1313 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1314 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1315 return __tree_.__count_multi(__k);
1316 }
1317 # endif
1318
1319 # if _LIBCPP_STD_VER >= 20
1320 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1321 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1322 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1323 return find(__k) != end();
1324 }
1325 # endif // _LIBCPP_STD_VER >= 20
1326
1327 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1328 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1329 # if _LIBCPP_STD_VER >= 14
1330 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1331 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1332 return __tree_.lower_bound(__k);
1333 }
1334
1335 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1336 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1337 return __tree_.lower_bound(__k);
1338 }
1339 # endif
1340
1341 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1342 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1343 # if _LIBCPP_STD_VER >= 14
1344 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1345 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1346 return __tree_.upper_bound(__k);
1347 }
1348 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1349 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1350 return __tree_.upper_bound(__k);
1351 }
1352 # endif
1353
1354 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1355 return __tree_.__equal_range_multi(__k);
1356 }
1357 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1358 return __tree_.__equal_range_multi(__k);
1359 }
1360 # if _LIBCPP_STD_VER >= 14
1361 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1362 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1363 return __tree_.__equal_range_multi(__k);
1364 }
1365 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1366 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1367 return __tree_.__equal_range_multi(__k);
1368 }
1369 # endif
1370 };
1371
1372 # if _LIBCPP_STD_VER >= 17
1373 template <class _InputIterator,
1374 class _Compare = less<__iter_value_type<_InputIterator>>,
1375 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1376 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1377 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1378 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1379 multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1380 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1381
1382 # if _LIBCPP_STD_VER >= 23
1383 template <ranges::input_range _Range,
1384 class _Compare = less<ranges::range_value_t<_Range>>,
1385 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1386 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1387 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1388 multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1389 -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1390 # endif
1391
1392 template <class _Key,
1393 class _Compare = less<_Key>,
1394 class _Allocator = allocator<_Key>,
1395 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1396 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1397 multiset(initializer_list<_Key>,
1398 _Compare = _Compare(),
1399 _Allocator = _Allocator()) -> multiset<_Key, _Compare, _Allocator>;
1400
1401 template <class _InputIterator,
1402 class _Allocator,
1403 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1404 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1405 multiset(_InputIterator, _InputIterator, _Allocator)
1406 -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
1407
1408 # if _LIBCPP_STD_VER >= 23
1409 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1410 multiset(from_range_t,
1411 _Range&&,
1412 _Allocator) -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1413 # endif
1414
1415 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1416 multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;
1417 # endif
1418
1419 # ifndef _LIBCPP_CXX03_LANG
1420
1421 template <class _Key, class _Compare, class _Allocator>
1422 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1423 : __tree_(std::move(__s.__tree_), __a) {
1424 if (__a != __s.get_allocator()) {
1425 const_iterator __e = cend();
1426 while (!__s.empty())
1427 insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
1428 }
1429 }
1430
1431 # endif // _LIBCPP_CXX03_LANG
1432
1433 template <class _Key, class _Compare, class _Allocator>
1434 inline _LIBCPP_HIDE_FROM_ABI bool
1435 operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1436 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1437 }
1438
1439 # if _LIBCPP_STD_VER <= 17
1440
1441 template <class _Key, class _Compare, class _Allocator>
1442 inline _LIBCPP_HIDE_FROM_ABI bool
1443 operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1444 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1445 }
1446
1447 template <class _Key, class _Compare, class _Allocator>
1448 inline _LIBCPP_HIDE_FROM_ABI bool
1449 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1450 return !(__x == __y);
1451 }
1452
1453 template <class _Key, class _Compare, class _Allocator>
1454 inline _LIBCPP_HIDE_FROM_ABI bool
1455 operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1456 return __y < __x;
1457 }
1458
1459 template <class _Key, class _Compare, class _Allocator>
1460 inline _LIBCPP_HIDE_FROM_ABI bool
1461 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1462 return !(__x < __y);
1463 }
1464
1465 template <class _Key, class _Compare, class _Allocator>
1466 inline _LIBCPP_HIDE_FROM_ABI bool
1467 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1468 return !(__y < __x);
1469 }
1470
1471 # else // _LIBCPP_STD_VER <= 17
1472
1473 template <class _Key, class _Compare, class _Allocator>
1474 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1475 operator<=>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1476 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
1477 }
1478
1479 # endif // _LIBCPP_STD_VER <= 17
1480
1481 template <class _Key, class _Compare, class _Allocator>
1482 inline _LIBCPP_HIDE_FROM_ABI void
1483 swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)
1484 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1485 __x.swap(__y);
1486 }
1487
1488 # if _LIBCPP_STD_VER >= 20
1489 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1490 inline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type
1491 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1492 return std::__libcpp_erase_if_container(__c, __pred);
1493 }
1494 # endif
1495
1496 template <class _Key, class _Compare, class _Allocator>
1497 struct __container_traits<multiset<_Key, _Compare, _Allocator> > {
1498 // http://eel.is/c++draft/associative.reqmts.except#2
1499 // For associative containers, if an exception is thrown by any operation from within
1500 // an insert or emplace function inserting a single element, the insertion has no effect.
1501 static _LIBCPP_CONSTEXPR const bool __emplacement_has_strong_exception_safety_guarantee = true;
1502 };
1503
1504 _LIBCPP_END_NAMESPACE_STD
1505
1506 # if _LIBCPP_STD_VER >= 17
1507 _LIBCPP_BEGIN_NAMESPACE_STD
1508 namespace pmr {
1509 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1510 using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1511
1512 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1513 using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1514 } // namespace pmr
1515 _LIBCPP_END_NAMESPACE_STD
1516 # endif
1517
1518 _LIBCPP_POP_MACROS
1519
1520 # if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1521 # include <concepts>
1522 # include <cstdlib>
1523 # include <functional>
1524 # include <iterator>
1525 # include <stdexcept>
1526 # include <type_traits>
1527 # endif
1528 #endif // __cplusplus < 201103L && defined(_LIBCPP_USE_FROZEN_CXX03_HEADERS)
1529
1530 #endif // _LIBCPP_SET
