Warning, /include/c++/v1/__cxx03/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___CXX03_SET
0011 #define _LIBCPP___CXX03_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 #include <__cxx03/__algorithm/equal.h>
0516 #include <__cxx03/__algorithm/lexicographical_compare.h>
0517 #include <__cxx03/__algorithm/lexicographical_compare_three_way.h>
0518 #include <__cxx03/__assert>
0519 #include <__cxx03/__config>
0520 #include <__cxx03/__functional/is_transparent.h>
0521 #include <__cxx03/__functional/operations.h>
0522 #include <__cxx03/__iterator/erase_if_container.h>
0523 #include <__cxx03/__iterator/iterator_traits.h>
0524 #include <__cxx03/__iterator/ranges_iterator_traits.h>
0525 #include <__cxx03/__iterator/reverse_iterator.h>
0526 #include <__cxx03/__memory/allocator.h>
0527 #include <__cxx03/__memory_resource/polymorphic_allocator.h>
0528 #include <__cxx03/__node_handle>
0529 #include <__cxx03/__ranges/concepts.h>
0530 #include <__cxx03/__ranges/container_compatible_range.h>
0531 #include <__cxx03/__ranges/from_range.h>
0532 #include <__cxx03/__tree>
0533 #include <__cxx03/__type_traits/is_allocator.h>
0534 #include <__cxx03/__utility/forward.h>
0535 #include <__cxx03/version>
0536
0537 // standard-mandated includes
0538
0539 // [iterator.range]
0540 #include <__cxx03/__iterator/access.h>
0541 #include <__cxx03/__iterator/data.h>
0542 #include <__cxx03/__iterator/empty.h>
0543 #include <__cxx03/__iterator/reverse_access.h>
0544 #include <__cxx03/__iterator/size.h>
0545
0546 // [associative.set.syn]
0547 #include <__cxx03/compare>
0548 #include <__cxx03/initializer_list>
0549
0550 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0551 # pragma GCC system_header
0552 #endif
0553
0554 _LIBCPP_PUSH_MACROS
0555 #include <__cxx03/__undef_macros>
0556
0557 _LIBCPP_BEGIN_NAMESPACE_STD
0558
0559 template <class _Key, class _Compare, class _Allocator>
0560 class multiset;
0561
0562 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
0563 class _LIBCPP_TEMPLATE_VIS set {
0564 public:
0565 // types:
0566 typedef _Key key_type;
0567 typedef key_type value_type;
0568 typedef __type_identity_t<_Compare> key_compare;
0569 typedef key_compare value_compare;
0570 typedef __type_identity_t<_Allocator> allocator_type;
0571 typedef value_type& reference;
0572 typedef const value_type& const_reference;
0573
0574 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
0575 "Allocator::value_type must be same type as value_type");
0576
0577 private:
0578 typedef __tree<value_type, value_compare, allocator_type> __base;
0579 typedef allocator_traits<allocator_type> __alloc_traits;
0580
0581 static_assert(__check_valid_allocator<allocator_type>::value, "");
0582
0583 __base __tree_;
0584
0585 public:
0586 typedef typename __base::pointer pointer;
0587 typedef typename __base::const_pointer const_pointer;
0588 typedef typename __base::size_type size_type;
0589 typedef typename __base::difference_type difference_type;
0590 typedef typename __base::const_iterator iterator;
0591 typedef typename __base::const_iterator const_iterator;
0592 typedef std::reverse_iterator<iterator> reverse_iterator;
0593 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
0594
0595 #if _LIBCPP_STD_VER >= 17
0596 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
0597 typedef __insert_return_type<iterator, node_type> insert_return_type;
0598 #endif
0599
0600 template <class _Key2, class _Compare2, class _Alloc2>
0601 friend class _LIBCPP_TEMPLATE_VIS set;
0602 template <class _Key2, class _Compare2, class _Alloc2>
0603 friend class _LIBCPP_TEMPLATE_VIS multiset;
0604
0605 _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_(
0606 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
0607 is_nothrow_copy_constructible<key_compare>::value)
0608 : __tree_(value_compare()) {}
0609
0610 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_(
0611 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
0612 : __tree_(__comp) {}
0613
0614 _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {}
0615 template <class _InputIterator>
0616 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
0617 : __tree_(__comp) {
0618 insert(__f, __l);
0619 }
0620
0621 template <class _InputIterator>
0622 _LIBCPP_HIDE_FROM_ABI
0623 set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
0624 : __tree_(__comp, __a) {
0625 insert(__f, __l);
0626 }
0627
0628 #if _LIBCPP_STD_VER >= 23
0629 template <_ContainerCompatibleRange<value_type> _Range>
0630 _LIBCPP_HIDE_FROM_ABI
0631 set(from_range_t,
0632 _Range&& __range,
0633 const key_compare& __comp = key_compare(),
0634 const allocator_type& __a = allocator_type())
0635 : __tree_(__comp, __a) {
0636 insert_range(std::forward<_Range>(__range));
0637 }
0638 #endif
0639
0640 #if _LIBCPP_STD_VER >= 14
0641 template <class _InputIterator>
0642 _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
0643 : set(__f, __l, key_compare(), __a) {}
0644 #endif
0645
0646 #if _LIBCPP_STD_VER >= 23
0647 template <_ContainerCompatibleRange<value_type> _Range>
0648 _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a)
0649 : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
0650 #endif
0651
0652 _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); }
0653
0654 _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) {
0655 __tree_ = __s.__tree_;
0656 return *this;
0657 }
0658
0659 #ifndef _LIBCPP_CXX03_LANG
0660 _LIBCPP_HIDE_FROM_ABI set(set&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
0661 : __tree_(std::move(__s.__tree_)) {}
0662 #endif // _LIBCPP_CXX03_LANG
0663
0664 _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {}
0665
0666 _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) {
0667 insert(__s.begin(), __s.end());
0668 }
0669
0670 #ifndef _LIBCPP_CXX03_LANG
0671 _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a);
0672
0673 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
0674 : __tree_(__comp) {
0675 insert(__il.begin(), __il.end());
0676 }
0677
0678 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
0679 : __tree_(__comp, __a) {
0680 insert(__il.begin(), __il.end());
0681 }
0682
0683 # if _LIBCPP_STD_VER >= 14
0684 _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a)
0685 : set(__il, key_compare(), __a) {}
0686 # endif
0687
0688 _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) {
0689 __tree_.__assign_unique(__il.begin(), __il.end());
0690 return *this;
0691 }
0692
0693 _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) noexcept(is_nothrow_move_assignable<__base>::value) {
0694 __tree_ = std::move(__s.__tree_);
0695 return *this;
0696 }
0697 #endif // _LIBCPP_CXX03_LANG
0698
0699 _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
0700
0701 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
0702 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
0703 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
0704 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
0705
0706 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
0707 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
0708 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
0709 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
0710
0711 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
0712 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
0713 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
0714 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
0715
0716 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
0717 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
0718 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
0719
0720 // modifiers:
0721 #ifndef _LIBCPP_CXX03_LANG
0722 template <class... _Args>
0723 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) {
0724 return __tree_.__emplace_unique(std::forward<_Args>(__args)...);
0725 }
0726 template <class... _Args>
0727 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
0728 return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...);
0729 }
0730 #endif // _LIBCPP_CXX03_LANG
0731
0732 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
0733 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
0734 return __tree_.__insert_unique(__p, __v);
0735 }
0736
0737 template <class _InputIterator>
0738 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
0739 for (const_iterator __e = cend(); __f != __l; ++__f)
0740 __tree_.__insert_unique(__e, *__f);
0741 }
0742
0743 #if _LIBCPP_STD_VER >= 23
0744 template <_ContainerCompatibleRange<value_type> _Range>
0745 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
0746 const_iterator __end = cend();
0747 for (auto&& __element : __range) {
0748 __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element));
0749 }
0750 }
0751 #endif
0752
0753 #ifndef _LIBCPP_CXX03_LANG
0754 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) {
0755 return __tree_.__insert_unique(std::move(__v));
0756 }
0757
0758 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
0759 return __tree_.__insert_unique(__p, std::move(__v));
0760 }
0761
0762 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
0763 #endif // _LIBCPP_CXX03_LANG
0764
0765 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
0766 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
0767 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
0768 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
0769
0770 #if _LIBCPP_STD_VER >= 17
0771 _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) {
0772 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0773 "node_type with incompatible allocator passed to set::insert()");
0774 return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh));
0775 }
0776 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
0777 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
0778 "node_type with incompatible allocator passed to set::insert()");
0779 return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh));
0780 }
0781 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
0782 return __tree_.template __node_handle_extract<node_type>(__key);
0783 }
0784 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
0785 return __tree_.template __node_handle_extract<node_type>(__it);
0786 }
0787 template <class _Compare2>
0788 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
0789 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0790 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0791 __tree_.__node_handle_merge_unique(__source.__tree_);
0792 }
0793 template <class _Compare2>
0794 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
0795 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0796 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0797 __tree_.__node_handle_merge_unique(__source.__tree_);
0798 }
0799 template <class _Compare2>
0800 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) {
0801 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0802 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0803 __tree_.__node_handle_merge_unique(__source.__tree_);
0804 }
0805 template <class _Compare2>
0806 _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) {
0807 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
0808 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
0809 __tree_.__node_handle_merge_unique(__source.__tree_);
0810 }
0811 #endif
0812
0813 _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) { __tree_.swap(__s.__tree_); }
0814
0815 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
0816 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
0817 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
0818
0819 // set operations:
0820 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
0821 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
0822 #if _LIBCPP_STD_VER >= 14
0823 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0824 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
0825 return __tree_.find(__k);
0826 }
0827 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0828 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
0829 return __tree_.find(__k);
0830 }
0831 #endif
0832
0833 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
0834 #if _LIBCPP_STD_VER >= 14
0835 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0836 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
0837 return __tree_.__count_multi(__k);
0838 }
0839 #endif
0840
0841 #if _LIBCPP_STD_VER >= 20
0842 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
0843 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0844 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
0845 return find(__k) != end();
0846 }
0847 #endif // _LIBCPP_STD_VER >= 20
0848
0849 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
0850 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
0851 #if _LIBCPP_STD_VER >= 14
0852 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0853 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
0854 return __tree_.lower_bound(__k);
0855 }
0856
0857 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0858 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
0859 return __tree_.lower_bound(__k);
0860 }
0861 #endif
0862
0863 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
0864 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
0865 #if _LIBCPP_STD_VER >= 14
0866 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0867 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
0868 return __tree_.upper_bound(__k);
0869 }
0870 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0871 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
0872 return __tree_.upper_bound(__k);
0873 }
0874 #endif
0875
0876 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
0877 return __tree_.__equal_range_unique(__k);
0878 }
0879 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
0880 return __tree_.__equal_range_unique(__k);
0881 }
0882 #if _LIBCPP_STD_VER >= 14
0883 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0884 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
0885 return __tree_.__equal_range_multi(__k);
0886 }
0887 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
0888 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
0889 return __tree_.__equal_range_multi(__k);
0890 }
0891 #endif
0892 };
0893
0894 #if _LIBCPP_STD_VER >= 17
0895 template <class _InputIterator,
0896 class _Compare = less<__iter_value_type<_InputIterator>>,
0897 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
0898 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
0899 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
0900 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
0901 set(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
0902 -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
0903
0904 # if _LIBCPP_STD_VER >= 23
0905 template <ranges::input_range _Range,
0906 class _Compare = less<ranges::range_value_t<_Range>>,
0907 class _Allocator = allocator<ranges::range_value_t<_Range>>,
0908 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
0909 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
0910 set(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
0911 -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>;
0912 # endif
0913
0914 template <class _Key,
0915 class _Compare = less<_Key>,
0916 class _Allocator = allocator<_Key>,
0917 class = enable_if_t<!__is_allocator<_Compare>::value, void>,
0918 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0919 set(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>;
0920
0921 template <class _InputIterator,
0922 class _Allocator,
0923 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
0924 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0925 set(_InputIterator,
0926 _InputIterator,
0927 _Allocator) -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
0928
0929 # if _LIBCPP_STD_VER >= 23
0930 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0931 set(from_range_t,
0932 _Range&&,
0933 _Allocator) -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
0934 # endif
0935
0936 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
0937 set(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>;
0938 #endif
0939
0940 #ifndef _LIBCPP_CXX03_LANG
0941
0942 template <class _Key, class _Compare, class _Allocator>
0943 set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) {
0944 if (__a != __s.get_allocator()) {
0945 const_iterator __e = cend();
0946 while (!__s.empty())
0947 insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
0948 }
0949 }
0950
0951 #endif // _LIBCPP_CXX03_LANG
0952
0953 template <class _Key, class _Compare, class _Allocator>
0954 inline _LIBCPP_HIDE_FROM_ABI bool
0955 operator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0956 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
0957 }
0958
0959 #if _LIBCPP_STD_VER <= 17
0960
0961 template <class _Key, class _Compare, class _Allocator>
0962 inline _LIBCPP_HIDE_FROM_ABI bool
0963 operator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0964 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
0965 }
0966
0967 template <class _Key, class _Compare, class _Allocator>
0968 inline _LIBCPP_HIDE_FROM_ABI bool
0969 operator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0970 return !(__x == __y);
0971 }
0972
0973 template <class _Key, class _Compare, class _Allocator>
0974 inline _LIBCPP_HIDE_FROM_ABI bool
0975 operator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0976 return __y < __x;
0977 }
0978
0979 template <class _Key, class _Compare, class _Allocator>
0980 inline _LIBCPP_HIDE_FROM_ABI bool
0981 operator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0982 return !(__x < __y);
0983 }
0984
0985 template <class _Key, class _Compare, class _Allocator>
0986 inline _LIBCPP_HIDE_FROM_ABI bool
0987 operator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) {
0988 return !(__y < __x);
0989 }
0990
0991 #else // _LIBCPP_STD_VER <= 17
0992
0993 template <class _Key, class _Allocator>
0994 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
0995 operator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) {
0996 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
0997 }
0998
0999 #endif // _LIBCPP_STD_VER <= 17
1000
1001 // specialized algorithms:
1002 template <class _Key, class _Compare, class _Allocator>
1003 inline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y)
1004 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1005 __x.swap(__y);
1006 }
1007
1008 #if _LIBCPP_STD_VER >= 20
1009 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1010 inline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type
1011 erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1012 return std::__libcpp_erase_if_container(__c, __pred);
1013 }
1014 #endif
1015
1016 template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >
1017 class _LIBCPP_TEMPLATE_VIS multiset {
1018 public:
1019 // types:
1020 typedef _Key key_type;
1021 typedef key_type value_type;
1022 typedef __type_identity_t<_Compare> key_compare;
1023 typedef key_compare value_compare;
1024 typedef __type_identity_t<_Allocator> allocator_type;
1025 typedef value_type& reference;
1026 typedef const value_type& const_reference;
1027
1028 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1029 "Allocator::value_type must be same type as value_type");
1030
1031 private:
1032 typedef __tree<value_type, value_compare, allocator_type> __base;
1033 typedef allocator_traits<allocator_type> __alloc_traits;
1034
1035 static_assert(__check_valid_allocator<allocator_type>::value, "");
1036
1037 __base __tree_;
1038
1039 public:
1040 typedef typename __base::pointer pointer;
1041 typedef typename __base::const_pointer const_pointer;
1042 typedef typename __base::size_type size_type;
1043 typedef typename __base::difference_type difference_type;
1044 typedef typename __base::const_iterator iterator;
1045 typedef typename __base::const_iterator const_iterator;
1046 typedef std::reverse_iterator<iterator> reverse_iterator;
1047 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1048
1049 #if _LIBCPP_STD_VER >= 17
1050 typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
1051 #endif
1052
1053 template <class _Key2, class _Compare2, class _Alloc2>
1054 friend class _LIBCPP_TEMPLATE_VIS set;
1055 template <class _Key2, class _Compare2, class _Alloc2>
1056 friend class _LIBCPP_TEMPLATE_VIS multiset;
1057
1058 // construct/copy/destroy:
1059 _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_(
1060 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&&
1061 is_nothrow_copy_constructible<key_compare>::value)
1062 : __tree_(value_compare()) {}
1063
1064 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_(
1065 is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value)
1066 : __tree_(__comp) {}
1067
1068 _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a)
1069 : __tree_(__comp, __a) {}
1070 template <class _InputIterator>
1071 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare())
1072 : __tree_(__comp) {
1073 insert(__f, __l);
1074 }
1075
1076 #if _LIBCPP_STD_VER >= 14
1077 template <class _InputIterator>
1078 _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1079 : multiset(__f, __l, key_compare(), __a) {}
1080 #endif
1081
1082 template <class _InputIterator>
1083 _LIBCPP_HIDE_FROM_ABI
1084 multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a)
1085 : __tree_(__comp, __a) {
1086 insert(__f, __l);
1087 }
1088
1089 #if _LIBCPP_STD_VER >= 23
1090 template <_ContainerCompatibleRange<value_type> _Range>
1091 _LIBCPP_HIDE_FROM_ABI
1092 multiset(from_range_t,
1093 _Range&& __range,
1094 const key_compare& __comp = key_compare(),
1095 const allocator_type& __a = allocator_type())
1096 : __tree_(__comp, __a) {
1097 insert_range(std::forward<_Range>(__range));
1098 }
1099
1100 template <_ContainerCompatibleRange<value_type> _Range>
1101 _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a)
1102 : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {}
1103 #endif
1104
1105 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s)
1106 : __tree_(__s.__tree_.value_comp(),
1107 __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) {
1108 insert(__s.begin(), __s.end());
1109 }
1110
1111 _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) {
1112 __tree_ = __s.__tree_;
1113 return *this;
1114 }
1115
1116 #ifndef _LIBCPP_CXX03_LANG
1117 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) noexcept(is_nothrow_move_constructible<__base>::value)
1118 : __tree_(std::move(__s.__tree_)) {}
1119
1120 _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a);
1121 #endif // _LIBCPP_CXX03_LANG
1122 _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {}
1123 _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a)
1124 : __tree_(__s.__tree_.value_comp(), __a) {
1125 insert(__s.begin(), __s.end());
1126 }
1127
1128 #ifndef _LIBCPP_CXX03_LANG
1129 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
1130 : __tree_(__comp) {
1131 insert(__il.begin(), __il.end());
1132 }
1133
1134 _LIBCPP_HIDE_FROM_ABI
1135 multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a)
1136 : __tree_(__comp, __a) {
1137 insert(__il.begin(), __il.end());
1138 }
1139
1140 # if _LIBCPP_STD_VER >= 14
1141 _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a)
1142 : multiset(__il, key_compare(), __a) {}
1143 # endif
1144
1145 _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) {
1146 __tree_.__assign_multi(__il.begin(), __il.end());
1147 return *this;
1148 }
1149
1150 _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) {
1151 __tree_ = std::move(__s.__tree_);
1152 return *this;
1153 }
1154 #endif // _LIBCPP_CXX03_LANG
1155
1156 _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1157
1158 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1159 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1160 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1161 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1162
1163 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1164 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1165 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1166 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1167
1168 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1169 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1170 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1171 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1172
1173 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1174 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1175 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1176
1177 // modifiers:
1178 #ifndef _LIBCPP_CXX03_LANG
1179 template <class... _Args>
1180 _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) {
1181 return __tree_.__emplace_multi(std::forward<_Args>(__args)...);
1182 }
1183 template <class... _Args>
1184 _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) {
1185 return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...);
1186 }
1187 #endif // _LIBCPP_CXX03_LANG
1188
1189 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1190 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1191 return __tree_.__insert_multi(__p, __v);
1192 }
1193
1194 template <class _InputIterator>
1195 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1196 for (const_iterator __e = cend(); __f != __l; ++__f)
1197 __tree_.__insert_multi(__e, *__f);
1198 }
1199
1200 #if _LIBCPP_STD_VER >= 23
1201 template <_ContainerCompatibleRange<value_type> _Range>
1202 _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) {
1203 const_iterator __end = cend();
1204 for (auto&& __element : __range) {
1205 __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element));
1206 }
1207 }
1208 #endif
1209
1210 #ifndef _LIBCPP_CXX03_LANG
1211 _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); }
1212
1213 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) {
1214 return __tree_.__insert_multi(__p, std::move(__v));
1215 }
1216
1217 _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); }
1218 #endif // _LIBCPP_CXX03_LANG
1219
1220 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); }
1221 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1222 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); }
1223 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1224
1225 #if _LIBCPP_STD_VER >= 17
1226 _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) {
1227 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1228 "node_type with incompatible allocator passed to multiset::insert()");
1229 return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh));
1230 }
1231 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) {
1232 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(),
1233 "node_type with incompatible allocator passed to multiset::insert()");
1234 return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh));
1235 }
1236 _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) {
1237 return __tree_.template __node_handle_extract<node_type>(__key);
1238 }
1239 _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) {
1240 return __tree_.template __node_handle_extract<node_type>(__it);
1241 }
1242 template <class _Compare2>
1243 _LIBCPP_HIDE_FROM_ABI void merge(multiset<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(multiset<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 template <class _Compare2>
1255 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) {
1256 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1257 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1258 __tree_.__node_handle_merge_multi(__source.__tree_);
1259 }
1260 template <class _Compare2>
1261 _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) {
1262 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1263 __source.get_allocator() == get_allocator(), "merging container with incompatible allocator");
1264 __tree_.__node_handle_merge_multi(__source.__tree_);
1265 }
1266 #endif
1267
1268 _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable_v<__base>) {
1269 __tree_.swap(__s.__tree_);
1270 }
1271
1272 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); }
1273 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); }
1274 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); }
1275
1276 // set operations:
1277 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1278 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1279 #if _LIBCPP_STD_VER >= 14
1280 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1281 _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) {
1282 return __tree_.find(__k);
1283 }
1284 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1285 _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const {
1286 return __tree_.find(__k);
1287 }
1288 #endif
1289
1290 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1291 #if _LIBCPP_STD_VER >= 14
1292 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1293 _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const {
1294 return __tree_.__count_multi(__k);
1295 }
1296 #endif
1297
1298 #if _LIBCPP_STD_VER >= 20
1299 _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); }
1300 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1301 _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const {
1302 return find(__k) != end();
1303 }
1304 #endif // _LIBCPP_STD_VER >= 20
1305
1306 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1307 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1308 #if _LIBCPP_STD_VER >= 14
1309 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1310 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
1311 return __tree_.lower_bound(__k);
1312 }
1313
1314 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1315 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const {
1316 return __tree_.lower_bound(__k);
1317 }
1318 #endif
1319
1320 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1321 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1322 #if _LIBCPP_STD_VER >= 14
1323 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1324 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
1325 return __tree_.upper_bound(__k);
1326 }
1327 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1328 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const {
1329 return __tree_.upper_bound(__k);
1330 }
1331 #endif
1332
1333 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1334 return __tree_.__equal_range_multi(__k);
1335 }
1336 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1337 return __tree_.__equal_range_multi(__k);
1338 }
1339 #if _LIBCPP_STD_VER >= 14
1340 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1341 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) {
1342 return __tree_.__equal_range_multi(__k);
1343 }
1344 template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
1345 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const {
1346 return __tree_.__equal_range_multi(__k);
1347 }
1348 #endif
1349 };
1350
1351 #if _LIBCPP_STD_VER >= 17
1352 template <class _InputIterator,
1353 class _Compare = less<__iter_value_type<_InputIterator>>,
1354 class _Allocator = allocator<__iter_value_type<_InputIterator>>,
1355 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1356 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1357 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1358 multiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator())
1359 -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>;
1360
1361 # if _LIBCPP_STD_VER >= 23
1362 template <ranges::input_range _Range,
1363 class _Compare = less<ranges::range_value_t<_Range>>,
1364 class _Allocator = allocator<ranges::range_value_t<_Range>>,
1365 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1366 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1367 multiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator())
1368 -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>;
1369 # endif
1370
1371 template <class _Key,
1372 class _Compare = less<_Key>,
1373 class _Allocator = allocator<_Key>,
1374 class = enable_if_t<__is_allocator<_Allocator>::value, void>,
1375 class = enable_if_t<!__is_allocator<_Compare>::value, void>>
1376 multiset(initializer_list<_Key>,
1377 _Compare = _Compare(),
1378 _Allocator = _Allocator()) -> multiset<_Key, _Compare, _Allocator>;
1379
1380 template <class _InputIterator,
1381 class _Allocator,
1382 class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>,
1383 class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1384 multiset(_InputIterator, _InputIterator, _Allocator)
1385 -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>;
1386
1387 # if _LIBCPP_STD_VER >= 23
1388 template <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1389 multiset(from_range_t,
1390 _Range&&,
1391 _Allocator) -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>;
1392 # endif
1393
1394 template <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>>
1395 multiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>;
1396 #endif
1397
1398 #ifndef _LIBCPP_CXX03_LANG
1399
1400 template <class _Key, class _Compare, class _Allocator>
1401 multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
1402 : __tree_(std::move(__s.__tree_), __a) {
1403 if (__a != __s.get_allocator()) {
1404 const_iterator __e = cend();
1405 while (!__s.empty())
1406 insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_));
1407 }
1408 }
1409
1410 #endif // _LIBCPP_CXX03_LANG
1411
1412 template <class _Key, class _Compare, class _Allocator>
1413 inline _LIBCPP_HIDE_FROM_ABI bool
1414 operator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1415 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1416 }
1417
1418 #if _LIBCPP_STD_VER <= 17
1419
1420 template <class _Key, class _Compare, class _Allocator>
1421 inline _LIBCPP_HIDE_FROM_ABI bool
1422 operator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1423 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1424 }
1425
1426 template <class _Key, class _Compare, class _Allocator>
1427 inline _LIBCPP_HIDE_FROM_ABI bool
1428 operator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1429 return !(__x == __y);
1430 }
1431
1432 template <class _Key, class _Compare, class _Allocator>
1433 inline _LIBCPP_HIDE_FROM_ABI bool
1434 operator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1435 return __y < __x;
1436 }
1437
1438 template <class _Key, class _Compare, class _Allocator>
1439 inline _LIBCPP_HIDE_FROM_ABI bool
1440 operator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1441 return !(__x < __y);
1442 }
1443
1444 template <class _Key, class _Compare, class _Allocator>
1445 inline _LIBCPP_HIDE_FROM_ABI bool
1446 operator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) {
1447 return !(__y < __x);
1448 }
1449
1450 #else // _LIBCPP_STD_VER <= 17
1451
1452 template <class _Key, class _Allocator>
1453 _LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key>
1454 operator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) {
1455 return std::lexicographical_compare_three_way(__x.begin(), __x.end(), __y.begin(), __y.end(), __synth_three_way);
1456 }
1457
1458 #endif // _LIBCPP_STD_VER <= 17
1459
1460 template <class _Key, class _Compare, class _Allocator>
1461 inline _LIBCPP_HIDE_FROM_ABI void
1462 swap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y)
1463 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
1464 __x.swap(__y);
1465 }
1466
1467 #if _LIBCPP_STD_VER >= 20
1468 template <class _Key, class _Compare, class _Allocator, class _Predicate>
1469 inline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type
1470 erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) {
1471 return std::__libcpp_erase_if_container(__c, __pred);
1472 }
1473 #endif
1474
1475 _LIBCPP_END_NAMESPACE_STD
1476
1477 #if _LIBCPP_STD_VER >= 17
1478 _LIBCPP_BEGIN_NAMESPACE_STD
1479 namespace pmr {
1480 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1481 using set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1482
1483 template <class _KeyT, class _CompareT = std::less<_KeyT>>
1484 using multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>;
1485 } // namespace pmr
1486 _LIBCPP_END_NAMESPACE_STD
1487 #endif
1488
1489 _LIBCPP_POP_MACROS
1490
1491 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
1492 # include <__cxx03/concepts>
1493 # include <__cxx03/cstdlib>
1494 # include <__cxx03/functional>
1495 # include <__cxx03/iterator>
1496 # include <__cxx03/stdexcept>
1497 # include <__cxx03/type_traits>
1498 #endif
1499
1500 #endif // _LIBCPP___CXX03_SET
