10b57cec5SDimitry Andric// -*- C++ -*- 2349cc55cSDimitry Andric//===----------------------------------------------------------------------===// 30b57cec5SDimitry Andric// 40b57cec5SDimitry Andric// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 50b57cec5SDimitry Andric// See https://llvm.org/LICENSE.txt for license information. 60b57cec5SDimitry Andric// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 70b57cec5SDimitry Andric// 80b57cec5SDimitry Andric//===----------------------------------------------------------------------===// 90b57cec5SDimitry Andric 100b57cec5SDimitry Andric#ifndef _LIBCPP_SET 110b57cec5SDimitry Andric#define _LIBCPP_SET 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric/* 140b57cec5SDimitry Andric 150b57cec5SDimitry Andric set synopsis 160b57cec5SDimitry Andric 170b57cec5SDimitry Andricnamespace std 180b57cec5SDimitry Andric{ 190b57cec5SDimitry Andric 200b57cec5SDimitry Andrictemplate <class Key, class Compare = less<Key>, 210b57cec5SDimitry Andric class Allocator = allocator<Key>> 220b57cec5SDimitry Andricclass set 230b57cec5SDimitry Andric{ 240b57cec5SDimitry Andricpublic: 250b57cec5SDimitry Andric // types: 260b57cec5SDimitry Andric typedef Key key_type; 270b57cec5SDimitry Andric typedef key_type value_type; 280b57cec5SDimitry Andric typedef Compare key_compare; 290b57cec5SDimitry Andric typedef key_compare value_compare; 300b57cec5SDimitry Andric typedef Allocator allocator_type; 310b57cec5SDimitry Andric typedef typename allocator_type::reference reference; 320b57cec5SDimitry Andric typedef typename allocator_type::const_reference const_reference; 330b57cec5SDimitry Andric typedef typename allocator_type::size_type size_type; 340b57cec5SDimitry Andric typedef typename allocator_type::difference_type difference_type; 350b57cec5SDimitry Andric typedef typename allocator_type::pointer pointer; 360b57cec5SDimitry Andric typedef typename allocator_type::const_pointer const_pointer; 370b57cec5SDimitry Andric 380b57cec5SDimitry Andric typedef implementation-defined iterator; 390b57cec5SDimitry Andric typedef implementation-defined const_iterator; 400b57cec5SDimitry Andric typedef std::reverse_iterator<iterator> reverse_iterator; 410b57cec5SDimitry Andric typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 420b57cec5SDimitry Andric typedef unspecified node_type; // C++17 430b57cec5SDimitry Andric typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17 440b57cec5SDimitry Andric 450b57cec5SDimitry Andric // construct/copy/destroy: 460b57cec5SDimitry Andric set() 470b57cec5SDimitry Andric noexcept( 480b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 490b57cec5SDimitry Andric is_nothrow_default_constructible<key_compare>::value && 500b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value); 510b57cec5SDimitry Andric explicit set(const value_compare& comp); 520b57cec5SDimitry Andric set(const value_compare& comp, const allocator_type& a); 530b57cec5SDimitry Andric template <class InputIterator> 540b57cec5SDimitry Andric set(InputIterator first, InputIterator last, 550b57cec5SDimitry Andric const value_compare& comp = value_compare()); 560b57cec5SDimitry Andric template <class InputIterator> 570b57cec5SDimitry Andric set(InputIterator first, InputIterator last, const value_compare& comp, 580b57cec5SDimitry Andric const allocator_type& a); 5906c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 6006c3fb27SDimitry Andric set(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 610b57cec5SDimitry Andric set(const set& s); 620b57cec5SDimitry Andric set(set&& s) 630b57cec5SDimitry Andric noexcept( 640b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value && 650b57cec5SDimitry Andric is_nothrow_move_constructible<key_compare>::value); 660b57cec5SDimitry Andric explicit set(const allocator_type& a); 670b57cec5SDimitry Andric set(const set& s, const allocator_type& a); 680b57cec5SDimitry Andric set(set&& s, const allocator_type& a); 690b57cec5SDimitry Andric set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 700b57cec5SDimitry Andric set(initializer_list<value_type> il, const value_compare& comp, 710b57cec5SDimitry Andric const allocator_type& a); 720b57cec5SDimitry Andric template <class InputIterator> 730b57cec5SDimitry Andric set(InputIterator first, InputIterator last, const allocator_type& a) 740b57cec5SDimitry Andric : set(first, last, Compare(), a) {} // C++14 7506c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 7606c3fb27SDimitry Andric set(from_range_t, R&& rg, const Allocator& a)) 7706c3fb27SDimitry Andric : set(from_range, std::forward<R>(rg), Compare(), a) { } // C++23 780b57cec5SDimitry Andric set(initializer_list<value_type> il, const allocator_type& a) 790b57cec5SDimitry Andric : set(il, Compare(), a) {} // C++14 800b57cec5SDimitry Andric ~set(); 810b57cec5SDimitry Andric 820b57cec5SDimitry Andric set& operator=(const set& s); 830b57cec5SDimitry Andric set& operator=(set&& s) 840b57cec5SDimitry Andric noexcept( 850b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 860b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 870b57cec5SDimitry Andric is_nothrow_move_assignable<key_compare>::value); 880b57cec5SDimitry Andric set& operator=(initializer_list<value_type> il); 890b57cec5SDimitry Andric 900b57cec5SDimitry Andric // iterators: 910b57cec5SDimitry Andric iterator begin() noexcept; 920b57cec5SDimitry Andric const_iterator begin() const noexcept; 930b57cec5SDimitry Andric iterator end() noexcept; 940b57cec5SDimitry Andric const_iterator end() const noexcept; 950b57cec5SDimitry Andric 960b57cec5SDimitry Andric reverse_iterator rbegin() noexcept; 970b57cec5SDimitry Andric const_reverse_iterator rbegin() const noexcept; 980b57cec5SDimitry Andric reverse_iterator rend() noexcept; 990b57cec5SDimitry Andric const_reverse_iterator rend() const noexcept; 1000b57cec5SDimitry Andric 1010b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 1020b57cec5SDimitry Andric const_iterator cend() const noexcept; 1030b57cec5SDimitry Andric const_reverse_iterator crbegin() const noexcept; 1040b57cec5SDimitry Andric const_reverse_iterator crend() const noexcept; 1050b57cec5SDimitry Andric 1060b57cec5SDimitry Andric // capacity: 1070b57cec5SDimitry Andric bool empty() const noexcept; 1080b57cec5SDimitry Andric size_type size() const noexcept; 1090b57cec5SDimitry Andric size_type max_size() const noexcept; 1100b57cec5SDimitry Andric 1110b57cec5SDimitry Andric // modifiers: 1120b57cec5SDimitry Andric template <class... Args> 1130b57cec5SDimitry Andric pair<iterator, bool> emplace(Args&&... args); 1140b57cec5SDimitry Andric template <class... Args> 1150b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 1160b57cec5SDimitry Andric pair<iterator,bool> insert(const value_type& v); 1170b57cec5SDimitry Andric pair<iterator,bool> insert(value_type&& v); 1180b57cec5SDimitry Andric iterator insert(const_iterator position, const value_type& v); 1190b57cec5SDimitry Andric iterator insert(const_iterator position, value_type&& v); 1200b57cec5SDimitry Andric template <class InputIterator> 1210b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 12206c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 12306c3fb27SDimitry Andric void insert_range(R&& rg); // C++23 1240b57cec5SDimitry Andric void insert(initializer_list<value_type> il); 1250b57cec5SDimitry Andric 1260b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 1270b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 1280b57cec5SDimitry Andric insert_return_type insert(node_type&& nh); // C++17 1290b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 1300b57cec5SDimitry Andric 1310b57cec5SDimitry Andric iterator erase(const_iterator position); 1320b57cec5SDimitry Andric iterator erase(iterator position); // C++14 1330b57cec5SDimitry Andric size_type erase(const key_type& k); 1340b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 1350b57cec5SDimitry Andric void clear() noexcept; 1360b57cec5SDimitry Andric 1370b57cec5SDimitry Andric template<class C2> 1380b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>& source); // C++17 1390b57cec5SDimitry Andric template<class C2> 1400b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>&& source); // C++17 1410b57cec5SDimitry Andric template<class C2> 1420b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>& source); // C++17 1430b57cec5SDimitry Andric template<class C2> 1440b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>&& source); // C++17 1450b57cec5SDimitry Andric 1460b57cec5SDimitry Andric void swap(set& s) 1470b57cec5SDimitry Andric noexcept( 1480b57cec5SDimitry Andric __is_nothrow_swappable<key_compare>::value && 1490b57cec5SDimitry Andric (!allocator_type::propagate_on_container_swap::value || 1500b57cec5SDimitry Andric __is_nothrow_swappable<allocator_type>::value)); 1510b57cec5SDimitry Andric 1520b57cec5SDimitry Andric // observers: 1530b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 1540b57cec5SDimitry Andric key_compare key_comp() const; 1550b57cec5SDimitry Andric value_compare value_comp() const; 1560b57cec5SDimitry Andric 1570b57cec5SDimitry Andric // set operations: 1580b57cec5SDimitry Andric iterator find(const key_type& k); 1590b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 1600b57cec5SDimitry Andric template<typename K> 1610b57cec5SDimitry Andric iterator find(const K& x); 1620b57cec5SDimitry Andric template<typename K> 1630b57cec5SDimitry Andric const_iterator find(const K& x) const; // C++14 164fe6060f1SDimitry Andric 1650b57cec5SDimitry Andric template<typename K> 1660b57cec5SDimitry Andric size_type count(const K& x) const; // C++14 1670b57cec5SDimitry Andric size_type count(const key_type& k) const; 168fe6060f1SDimitry Andric 1690b57cec5SDimitry Andric bool contains(const key_type& x) const; // C++20 170fe6060f1SDimitry Andric template<class K> bool contains(const K& x) const; // C++20 171fe6060f1SDimitry Andric 1720b57cec5SDimitry Andric iterator lower_bound(const key_type& k); 1730b57cec5SDimitry Andric const_iterator lower_bound(const key_type& k) const; 1740b57cec5SDimitry Andric template<typename K> 1750b57cec5SDimitry Andric iterator lower_bound(const K& x); // C++14 1760b57cec5SDimitry Andric template<typename K> 1770b57cec5SDimitry Andric const_iterator lower_bound(const K& x) const; // C++14 1780b57cec5SDimitry Andric 1790b57cec5SDimitry Andric iterator upper_bound(const key_type& k); 1800b57cec5SDimitry Andric const_iterator upper_bound(const key_type& k) const; 1810b57cec5SDimitry Andric template<typename K> 1820b57cec5SDimitry Andric iterator upper_bound(const K& x); // C++14 1830b57cec5SDimitry Andric template<typename K> 1840b57cec5SDimitry Andric const_iterator upper_bound(const K& x) const; // C++14 1850b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const key_type& k); 1860b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 1870b57cec5SDimitry Andric template<typename K> 1880b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const K& x); // C++14 1890b57cec5SDimitry Andric template<typename K> 1900b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 1910b57cec5SDimitry Andric}; 1920b57cec5SDimitry Andric 193349cc55cSDimitry Andrictemplate <class InputIterator, 194349cc55cSDimitry Andric class Compare = less<typename iterator_traits<InputIterator>::value_type>, 195349cc55cSDimitry Andric class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 196349cc55cSDimitry Andricset(InputIterator, InputIterator, 197349cc55cSDimitry Andric Compare = Compare(), Allocator = Allocator()) 198349cc55cSDimitry Andric -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 199349cc55cSDimitry Andric 20006c3fb27SDimitry Andrictemplate<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>, 20106c3fb27SDimitry Andric class Allocator = allocator<ranges::range_value_t<R>>> 20206c3fb27SDimitry Andric set(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) 20306c3fb27SDimitry Andric -> set<ranges::range_value_t<R>, Compare, Allocator>; // C++23 20406c3fb27SDimitry Andric 205349cc55cSDimitry Andrictemplate<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 206349cc55cSDimitry Andricset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 207349cc55cSDimitry Andric -> set<Key, Compare, Allocator>; // C++17 208349cc55cSDimitry Andric 209349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 210349cc55cSDimitry Andricset(InputIterator, InputIterator, Allocator) 211349cc55cSDimitry Andric -> set<typename iterator_traits<InputIterator>::value_type, 212349cc55cSDimitry Andric less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 213349cc55cSDimitry Andric 21406c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 21506c3fb27SDimitry Andric set(from_range_t, R&&, Allocator) 21606c3fb27SDimitry Andric -> set<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; // C++23 21706c3fb27SDimitry Andric 218349cc55cSDimitry Andrictemplate<class Key, class Allocator> 219349cc55cSDimitry Andricset(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17 220349cc55cSDimitry Andric 2210b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2220b57cec5SDimitry Andricbool 2230b57cec5SDimitry Andricoperator==(const set<Key, Compare, Allocator>& x, 2240b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2250b57cec5SDimitry Andric 2260b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2270b57cec5SDimitry Andricbool 2280b57cec5SDimitry Andricoperator< (const set<Key, Compare, Allocator>& x, 22906c3fb27SDimitry Andric const set<Key, Compare, Allocator>& y); // removed in C++20 2300b57cec5SDimitry Andric 2310b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2320b57cec5SDimitry Andricbool 2330b57cec5SDimitry Andricoperator!=(const set<Key, Compare, Allocator>& x, 23406c3fb27SDimitry Andric const set<Key, Compare, Allocator>& y); // removed in C++20 2350b57cec5SDimitry Andric 2360b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2370b57cec5SDimitry Andricbool 2380b57cec5SDimitry Andricoperator> (const set<Key, Compare, Allocator>& x, 23906c3fb27SDimitry Andric const set<Key, Compare, Allocator>& y); // removed in C++20 2400b57cec5SDimitry Andric 2410b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2420b57cec5SDimitry Andricbool 2430b57cec5SDimitry Andricoperator>=(const set<Key, Compare, Allocator>& x, 24406c3fb27SDimitry Andric const set<Key, Compare, Allocator>& y); // removed in C++20 2450b57cec5SDimitry Andric 2460b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2470b57cec5SDimitry Andricbool 2480b57cec5SDimitry Andricoperator<=(const set<Key, Compare, Allocator>& x, 24906c3fb27SDimitry Andric const set<Key, Compare, Allocator>& y); // removed in C++20 25006c3fb27SDimitry Andric 25106c3fb27SDimitry Andrictemplate<class Key, class Compare, class Allocator> 25206c3fb27SDimitry Andric synth-three-way-result<Key> operator<=>(const set<Key, Compare, Allocator>& x, 25306c3fb27SDimitry Andric const set<Key, Compare, Allocator>& y); // since C++20 2540b57cec5SDimitry Andric 2550b57cec5SDimitry Andric// specialized algorithms: 2560b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2570b57cec5SDimitry Andricvoid 2580b57cec5SDimitry Andricswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 2590b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 2600b57cec5SDimitry Andric 2610b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator, class Predicate> 2625ffd83dbSDimitry Andrictypename set<Key, Compare, Allocator>::size_type 2635ffd83dbSDimitry Andricerase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 2640b57cec5SDimitry Andric 2650b57cec5SDimitry Andrictemplate <class Key, class Compare = less<Key>, 2660b57cec5SDimitry Andric class Allocator = allocator<Key>> 2670b57cec5SDimitry Andricclass multiset 2680b57cec5SDimitry Andric{ 2690b57cec5SDimitry Andricpublic: 2700b57cec5SDimitry Andric // types: 2710b57cec5SDimitry Andric typedef Key key_type; 2720b57cec5SDimitry Andric typedef key_type value_type; 2730b57cec5SDimitry Andric typedef Compare key_compare; 2740b57cec5SDimitry Andric typedef key_compare value_compare; 2750b57cec5SDimitry Andric typedef Allocator allocator_type; 2760b57cec5SDimitry Andric typedef typename allocator_type::reference reference; 2770b57cec5SDimitry Andric typedef typename allocator_type::const_reference const_reference; 2780b57cec5SDimitry Andric typedef typename allocator_type::size_type size_type; 2790b57cec5SDimitry Andric typedef typename allocator_type::difference_type difference_type; 2800b57cec5SDimitry Andric typedef typename allocator_type::pointer pointer; 2810b57cec5SDimitry Andric typedef typename allocator_type::const_pointer const_pointer; 2820b57cec5SDimitry Andric 2830b57cec5SDimitry Andric typedef implementation-defined iterator; 2840b57cec5SDimitry Andric typedef implementation-defined const_iterator; 2850b57cec5SDimitry Andric typedef std::reverse_iterator<iterator> reverse_iterator; 2860b57cec5SDimitry Andric typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 2870b57cec5SDimitry Andric typedef unspecified node_type; // C++17 2880b57cec5SDimitry Andric 2890b57cec5SDimitry Andric // construct/copy/destroy: 2900b57cec5SDimitry Andric multiset() 2910b57cec5SDimitry Andric noexcept( 2920b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 2930b57cec5SDimitry Andric is_nothrow_default_constructible<key_compare>::value && 2940b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value); 2950b57cec5SDimitry Andric explicit multiset(const value_compare& comp); 2960b57cec5SDimitry Andric multiset(const value_compare& comp, const allocator_type& a); 2970b57cec5SDimitry Andric template <class InputIterator> 2980b57cec5SDimitry Andric multiset(InputIterator first, InputIterator last, 2990b57cec5SDimitry Andric const value_compare& comp = value_compare()); 3000b57cec5SDimitry Andric template <class InputIterator> 3010b57cec5SDimitry Andric multiset(InputIterator first, InputIterator last, 3020b57cec5SDimitry Andric const value_compare& comp, const allocator_type& a); 30306c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 30406c3fb27SDimitry Andric multiset(from_range_t, R&& rg, 30506c3fb27SDimitry Andric const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23 3060b57cec5SDimitry Andric multiset(const multiset& s); 3070b57cec5SDimitry Andric multiset(multiset&& s) 3080b57cec5SDimitry Andric noexcept( 3090b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value && 3100b57cec5SDimitry Andric is_nothrow_move_constructible<key_compare>::value); 3110b57cec5SDimitry Andric explicit multiset(const allocator_type& a); 3120b57cec5SDimitry Andric multiset(const multiset& s, const allocator_type& a); 3130b57cec5SDimitry Andric multiset(multiset&& s, const allocator_type& a); 3140b57cec5SDimitry Andric multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 3150b57cec5SDimitry Andric multiset(initializer_list<value_type> il, const value_compare& comp, 3160b57cec5SDimitry Andric const allocator_type& a); 3170b57cec5SDimitry Andric template <class InputIterator> 3180b57cec5SDimitry Andric multiset(InputIterator first, InputIterator last, const allocator_type& a) 3190b57cec5SDimitry Andric : set(first, last, Compare(), a) {} // C++14 32006c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 32106c3fb27SDimitry Andric multiset(from_range_t, R&& rg, const Allocator& a)) 32206c3fb27SDimitry Andric : multiset(from_range, std::forward<R>(rg), Compare(), a) { } // C++23 3230b57cec5SDimitry Andric multiset(initializer_list<value_type> il, const allocator_type& a) 3240b57cec5SDimitry Andric : set(il, Compare(), a) {} // C++14 3250b57cec5SDimitry Andric ~multiset(); 3260b57cec5SDimitry Andric 3270b57cec5SDimitry Andric multiset& operator=(const multiset& s); 3280b57cec5SDimitry Andric multiset& operator=(multiset&& s) 3290b57cec5SDimitry Andric noexcept( 3300b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 3310b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 3320b57cec5SDimitry Andric is_nothrow_move_assignable<key_compare>::value); 3330b57cec5SDimitry Andric multiset& operator=(initializer_list<value_type> il); 3340b57cec5SDimitry Andric 3350b57cec5SDimitry Andric // iterators: 3360b57cec5SDimitry Andric iterator begin() noexcept; 3370b57cec5SDimitry Andric const_iterator begin() const noexcept; 3380b57cec5SDimitry Andric iterator end() noexcept; 3390b57cec5SDimitry Andric const_iterator end() const noexcept; 3400b57cec5SDimitry Andric 3410b57cec5SDimitry Andric reverse_iterator rbegin() noexcept; 3420b57cec5SDimitry Andric const_reverse_iterator rbegin() const noexcept; 3430b57cec5SDimitry Andric reverse_iterator rend() noexcept; 3440b57cec5SDimitry Andric const_reverse_iterator rend() const noexcept; 3450b57cec5SDimitry Andric 3460b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 3470b57cec5SDimitry Andric const_iterator cend() const noexcept; 3480b57cec5SDimitry Andric const_reverse_iterator crbegin() const noexcept; 3490b57cec5SDimitry Andric const_reverse_iterator crend() const noexcept; 3500b57cec5SDimitry Andric 3510b57cec5SDimitry Andric // capacity: 3520b57cec5SDimitry Andric bool empty() const noexcept; 3530b57cec5SDimitry Andric size_type size() const noexcept; 3540b57cec5SDimitry Andric size_type max_size() const noexcept; 3550b57cec5SDimitry Andric 3560b57cec5SDimitry Andric // modifiers: 3570b57cec5SDimitry Andric template <class... Args> 3580b57cec5SDimitry Andric iterator emplace(Args&&... args); 3590b57cec5SDimitry Andric template <class... Args> 3600b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 3610b57cec5SDimitry Andric iterator insert(const value_type& v); 3620b57cec5SDimitry Andric iterator insert(value_type&& v); 3630b57cec5SDimitry Andric iterator insert(const_iterator position, const value_type& v); 3640b57cec5SDimitry Andric iterator insert(const_iterator position, value_type&& v); 3650b57cec5SDimitry Andric template <class InputIterator> 3660b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 36706c3fb27SDimitry Andric template<container-compatible-range<value_type> R> 36806c3fb27SDimitry Andric void insert_range(R&& rg); // C++23 3690b57cec5SDimitry Andric void insert(initializer_list<value_type> il); 3700b57cec5SDimitry Andric 3710b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 3720b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 3730b57cec5SDimitry Andric iterator insert(node_type&& nh); // C++17 3740b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 3750b57cec5SDimitry Andric 3760b57cec5SDimitry Andric iterator erase(const_iterator position); 3770b57cec5SDimitry Andric iterator erase(iterator position); // C++14 3780b57cec5SDimitry Andric size_type erase(const key_type& k); 3790b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 3800b57cec5SDimitry Andric void clear() noexcept; 3810b57cec5SDimitry Andric 3820b57cec5SDimitry Andric template<class C2> 3830b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>& source); // C++17 3840b57cec5SDimitry Andric template<class C2> 3850b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>&& source); // C++17 3860b57cec5SDimitry Andric template<class C2> 3870b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>& source); // C++17 3880b57cec5SDimitry Andric template<class C2> 3890b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>&& source); // C++17 3900b57cec5SDimitry Andric 3910b57cec5SDimitry Andric void swap(multiset& s) 3920b57cec5SDimitry Andric noexcept( 3930b57cec5SDimitry Andric __is_nothrow_swappable<key_compare>::value && 3940b57cec5SDimitry Andric (!allocator_type::propagate_on_container_swap::value || 3950b57cec5SDimitry Andric __is_nothrow_swappable<allocator_type>::value)); 3960b57cec5SDimitry Andric 3970b57cec5SDimitry Andric // observers: 3980b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 3990b57cec5SDimitry Andric key_compare key_comp() const; 4000b57cec5SDimitry Andric value_compare value_comp() const; 4010b57cec5SDimitry Andric 4020b57cec5SDimitry Andric // set operations: 4030b57cec5SDimitry Andric iterator find(const key_type& k); 4040b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 4050b57cec5SDimitry Andric template<typename K> 4060b57cec5SDimitry Andric iterator find(const K& x); 4070b57cec5SDimitry Andric template<typename K> 4080b57cec5SDimitry Andric const_iterator find(const K& x) const; // C++14 409fe6060f1SDimitry Andric 4100b57cec5SDimitry Andric template<typename K> 4110b57cec5SDimitry Andric size_type count(const K& x) const; // C++14 4120b57cec5SDimitry Andric size_type count(const key_type& k) const; 413fe6060f1SDimitry Andric 4140b57cec5SDimitry Andric bool contains(const key_type& x) const; // C++20 415fe6060f1SDimitry Andric template<class K> bool contains(const K& x) const; // C++20 416fe6060f1SDimitry Andric 4170b57cec5SDimitry Andric iterator lower_bound(const key_type& k); 4180b57cec5SDimitry Andric const_iterator lower_bound(const key_type& k) const; 4190b57cec5SDimitry Andric template<typename K> 4200b57cec5SDimitry Andric iterator lower_bound(const K& x); // C++14 4210b57cec5SDimitry Andric template<typename K> 4220b57cec5SDimitry Andric const_iterator lower_bound(const K& x) const; // C++14 4230b57cec5SDimitry Andric 4240b57cec5SDimitry Andric iterator upper_bound(const key_type& k); 4250b57cec5SDimitry Andric const_iterator upper_bound(const key_type& k) const; 4260b57cec5SDimitry Andric template<typename K> 4270b57cec5SDimitry Andric iterator upper_bound(const K& x); // C++14 4280b57cec5SDimitry Andric template<typename K> 4290b57cec5SDimitry Andric const_iterator upper_bound(const K& x) const; // C++14 4300b57cec5SDimitry Andric 4310b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const key_type& k); 4320b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 4330b57cec5SDimitry Andric template<typename K> 4340b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const K& x); // C++14 4350b57cec5SDimitry Andric template<typename K> 4360b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 4370b57cec5SDimitry Andric}; 4380b57cec5SDimitry Andric 439349cc55cSDimitry Andrictemplate <class InputIterator, 440349cc55cSDimitry Andric class Compare = less<typename iterator_traits<InputIterator>::value_type>, 441349cc55cSDimitry Andric class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 442349cc55cSDimitry Andricmultiset(InputIterator, InputIterator, 443349cc55cSDimitry Andric Compare = Compare(), Allocator = Allocator()) 444349cc55cSDimitry Andric -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 445349cc55cSDimitry Andric 44606c3fb27SDimitry Andrictemplate<ranges::input_range R, class Compare = less<ranges::range_value_t<R>>, 44706c3fb27SDimitry Andric class Allocator = allocator<ranges::range_value_t<R>>> 44806c3fb27SDimitry Andric multiset(from_range_t, R&&, Compare = Compare(), Allocator = Allocator()) 44906c3fb27SDimitry Andric -> multiset<ranges::range_value_t<R>, Compare, Allocator>; 45006c3fb27SDimitry Andric 451349cc55cSDimitry Andrictemplate<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 452349cc55cSDimitry Andricmultiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 453349cc55cSDimitry Andric -> multiset<Key, Compare, Allocator>; // C++17 454349cc55cSDimitry Andric 455349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 456349cc55cSDimitry Andricmultiset(InputIterator, InputIterator, Allocator) 457349cc55cSDimitry Andric -> multiset<typename iterator_traits<InputIterator>::value_type, 458349cc55cSDimitry Andric less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 459349cc55cSDimitry Andric 46006c3fb27SDimitry Andrictemplate<ranges::input_range R, class Allocator> 46106c3fb27SDimitry Andric multiset(from_range_t, R&&, Allocator) 46206c3fb27SDimitry Andric -> multiset<ranges::range_value_t<R>, less<ranges::range_value_t<R>>, Allocator>; 46306c3fb27SDimitry Andric 464349cc55cSDimitry Andrictemplate<class Key, class Allocator> 465349cc55cSDimitry Andricmultiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17 466349cc55cSDimitry Andric 4670b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4680b57cec5SDimitry Andricbool 4690b57cec5SDimitry Andricoperator==(const multiset<Key, Compare, Allocator>& x, 4700b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4710b57cec5SDimitry Andric 4720b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4730b57cec5SDimitry Andricbool 4740b57cec5SDimitry Andricoperator< (const multiset<Key, Compare, Allocator>& x, 47506c3fb27SDimitry Andric const multiset<Key, Compare, Allocator>& y); // removed in C++20 4760b57cec5SDimitry Andric 4770b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4780b57cec5SDimitry Andricbool 4790b57cec5SDimitry Andricoperator!=(const multiset<Key, Compare, Allocator>& x, 48006c3fb27SDimitry Andric const multiset<Key, Compare, Allocator>& y); // removed in C++20 4810b57cec5SDimitry Andric 4820b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4830b57cec5SDimitry Andricbool 4840b57cec5SDimitry Andricoperator> (const multiset<Key, Compare, Allocator>& x, 48506c3fb27SDimitry Andric const multiset<Key, Compare, Allocator>& y); // removed in C++20 4860b57cec5SDimitry Andric 4870b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4880b57cec5SDimitry Andricbool 4890b57cec5SDimitry Andricoperator>=(const multiset<Key, Compare, Allocator>& x, 49006c3fb27SDimitry Andric const multiset<Key, Compare, Allocator>& y); // removed in C++20 4910b57cec5SDimitry Andric 4920b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4930b57cec5SDimitry Andricbool 4940b57cec5SDimitry Andricoperator<=(const multiset<Key, Compare, Allocator>& x, 49506c3fb27SDimitry Andric const multiset<Key, Compare, Allocator>& y); // removed in C++20 49606c3fb27SDimitry Andric 49706c3fb27SDimitry Andrictemplate<class Key, class Compare, class Allocator> 49806c3fb27SDimitry Andric synth-three-way-result<Key> operator<=>(const multiset<Key, Compare, Allocator>& x, 49906c3fb27SDimitry Andric const multiset<Key, Compare, Allocator>& y); // since C++20 5000b57cec5SDimitry Andric 5010b57cec5SDimitry Andric// specialized algorithms: 5020b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 5030b57cec5SDimitry Andricvoid 5040b57cec5SDimitry Andricswap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 5050b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 5060b57cec5SDimitry Andric 5070b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator, class Predicate> 5085ffd83dbSDimitry Andrictypename multiset<Key, Compare, Allocator>::size_type 5095ffd83dbSDimitry Andricerase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 5100b57cec5SDimitry Andric 5110b57cec5SDimitry Andric} // std 5120b57cec5SDimitry Andric 5130b57cec5SDimitry Andric*/ 5140b57cec5SDimitry Andric 51581ad6265SDimitry Andric#include <__algorithm/equal.h> 51681ad6265SDimitry Andric#include <__algorithm/lexicographical_compare.h> 51706c3fb27SDimitry Andric#include <__algorithm/lexicographical_compare_three_way.h> 51881ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler 51906c3fb27SDimitry Andric#include <__availability> 5200b57cec5SDimitry Andric#include <__config> 521fe6060f1SDimitry Andric#include <__functional/is_transparent.h> 52281ad6265SDimitry Andric#include <__functional/operations.h> 52381ad6265SDimitry Andric#include <__iterator/erase_if_container.h> 524349cc55cSDimitry Andric#include <__iterator/iterator_traits.h> 52506c3fb27SDimitry Andric#include <__iterator/ranges_iterator_traits.h> 52681ad6265SDimitry Andric#include <__iterator/reverse_iterator.h> 527bdd1243dSDimitry Andric#include <__memory/allocator.h> 528bdd1243dSDimitry Andric#include <__memory_resource/polymorphic_allocator.h> 5290b57cec5SDimitry Andric#include <__node_handle> 53006c3fb27SDimitry Andric#include <__ranges/concepts.h> 53106c3fb27SDimitry Andric#include <__ranges/container_compatible_range.h> 53206c3fb27SDimitry Andric#include <__ranges/from_range.h> 533fe6060f1SDimitry Andric#include <__tree> 534bdd1243dSDimitry Andric#include <__type_traits/is_allocator.h> 535fe6060f1SDimitry Andric#include <__utility/forward.h> 5360b57cec5SDimitry Andric#include <version> 5370b57cec5SDimitry Andric 53881ad6265SDimitry Andric// standard-mandated includes 53981ad6265SDimitry Andric 54081ad6265SDimitry Andric// [iterator.range] 54181ad6265SDimitry Andric#include <__iterator/access.h> 54281ad6265SDimitry Andric#include <__iterator/data.h> 54381ad6265SDimitry Andric#include <__iterator/empty.h> 54481ad6265SDimitry Andric#include <__iterator/reverse_access.h> 54581ad6265SDimitry Andric#include <__iterator/size.h> 54681ad6265SDimitry Andric 54781ad6265SDimitry Andric// [associative.set.syn] 54881ad6265SDimitry Andric#include <compare> 54981ad6265SDimitry Andric#include <initializer_list> 55081ad6265SDimitry Andric 5510b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 5520b57cec5SDimitry Andric# pragma GCC system_header 5530b57cec5SDimitry Andric#endif 5540b57cec5SDimitry Andric 555b3edf446SDimitry Andric_LIBCPP_PUSH_MACROS 556b3edf446SDimitry Andric#include <__undef_macros> 557b3edf446SDimitry Andric 5580b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 5590b57cec5SDimitry Andric 5600b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 5610b57cec5SDimitry Andricclass multiset; 5620b57cec5SDimitry Andric 563cb14a3feSDimitry Andrictemplate <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> > 564cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS set { 5650b57cec5SDimitry Andricpublic: 5660b57cec5SDimitry Andric // types: 5670b57cec5SDimitry Andric typedef _Key key_type; 5680b57cec5SDimitry Andric typedef key_type value_type; 56981ad6265SDimitry Andric typedef __type_identity_t<_Compare> key_compare; 5700b57cec5SDimitry Andric typedef key_compare value_compare; 57181ad6265SDimitry Andric typedef __type_identity_t<_Allocator> allocator_type; 5720b57cec5SDimitry Andric typedef value_type& reference; 5730b57cec5SDimitry Andric typedef const value_type& const_reference; 5740b57cec5SDimitry Andric 5750b57cec5SDimitry Andric static_assert((is_same<typename allocator_type::value_type, value_type>::value), 5760b57cec5SDimitry Andric "Allocator::value_type must be same type as value_type"); 5770b57cec5SDimitry Andric 5780b57cec5SDimitry Andricprivate: 5790b57cec5SDimitry Andric typedef __tree<value_type, value_compare, allocator_type> __base; 5800b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 5810b57cec5SDimitry Andric 582bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, 583bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 584bdd1243dSDimitry Andric "original allocator"); 585bdd1243dSDimitry Andric 5860b57cec5SDimitry Andric __base __tree_; 5870b57cec5SDimitry Andric 5880b57cec5SDimitry Andricpublic: 5890b57cec5SDimitry Andric typedef typename __base::pointer pointer; 5900b57cec5SDimitry Andric typedef typename __base::const_pointer const_pointer; 5910b57cec5SDimitry Andric typedef typename __base::size_type size_type; 5920b57cec5SDimitry Andric typedef typename __base::difference_type difference_type; 5930b57cec5SDimitry Andric typedef typename __base::const_iterator iterator; 5940b57cec5SDimitry Andric typedef typename __base::const_iterator const_iterator; 5955f757f3fSDimitry Andric typedef std::reverse_iterator<iterator> reverse_iterator; 5965f757f3fSDimitry Andric typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 5970b57cec5SDimitry Andric 59806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 5990b57cec5SDimitry Andric typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 6000b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 6010b57cec5SDimitry Andric#endif 6020b57cec5SDimitry Andric 6030b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 6040b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS set; 6050b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 6060b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS multiset; 6070b57cec5SDimitry Andric 608cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set() _NOEXCEPT_( 609cb14a3feSDimitry Andric is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&& 6100b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value) 6110b57cec5SDimitry Andric : __tree_(value_compare()) {} 6120b57cec5SDimitry Andric 613cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp) _NOEXCEPT_( 614cb14a3feSDimitry Andric is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value) 6150b57cec5SDimitry Andric : __tree_(__comp) {} 6160b57cec5SDimitry Andric 617cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {} 6180b57cec5SDimitry Andric template <class _InputIterator> 619cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare()) 620cb14a3feSDimitry Andric : __tree_(__comp) { 6210b57cec5SDimitry Andric insert(__f, __l); 6220b57cec5SDimitry Andric } 6230b57cec5SDimitry Andric 6240b57cec5SDimitry Andric template <class _InputIterator> 6255f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 626cb14a3feSDimitry Andric set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a) 627cb14a3feSDimitry Andric : __tree_(__comp, __a) { 6280b57cec5SDimitry Andric insert(__f, __l); 6290b57cec5SDimitry Andric } 6300b57cec5SDimitry Andric 63106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 63206c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 63306c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 634cb14a3feSDimitry Andric set(from_range_t, 635cb14a3feSDimitry Andric _Range&& __range, 636cb14a3feSDimitry Andric const key_compare& __comp = key_compare(), 63706c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 63806c3fb27SDimitry Andric : __tree_(__comp, __a) { 63906c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 64006c3fb27SDimitry Andric } 64106c3fb27SDimitry Andric#endif 64206c3fb27SDimitry Andric 64306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 6440b57cec5SDimitry Andric template <class _InputIterator> 645cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 6460b57cec5SDimitry Andric : set(__f, __l, key_compare(), __a) {} 6470b57cec5SDimitry Andric#endif 6480b57cec5SDimitry Andric 64906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 65006c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 651cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(from_range_t, _Range&& __range, const allocator_type& __a) 65206c3fb27SDimitry Andric : set(from_range, std::forward<_Range>(__range), key_compare(), __a) {} 65306c3fb27SDimitry Andric#endif 65406c3fb27SDimitry Andric 655cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); } 6560b57cec5SDimitry Andric 657cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set& operator=(const set& __s) { 6580b57cec5SDimitry Andric __tree_ = __s.__tree_; 6590b57cec5SDimitry Andric return *this; 6600b57cec5SDimitry Andric } 6610b57cec5SDimitry Andric 6620b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 663cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(set&& __s) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 6645f757f3fSDimitry Andric : __tree_(std::move(__s.__tree_)) {} 6650b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 6660b57cec5SDimitry Andric 667cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit set(const allocator_type& __a) : __tree_(__a) {} 6680b57cec5SDimitry Andric 669cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) { 6700b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 6710b57cec5SDimitry Andric } 6720b57cec5SDimitry Andric 6730b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 67406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI set(set&& __s, const allocator_type& __a); 6750b57cec5SDimitry Andric 676cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 677cb14a3feSDimitry Andric : __tree_(__comp) { 6780b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 6790b57cec5SDimitry Andric } 6800b57cec5SDimitry Andric 681cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a) 682cb14a3feSDimitry Andric : __tree_(__comp, __a) { 6830b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 6840b57cec5SDimitry Andric } 6850b57cec5SDimitry Andric 68606c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 14 687cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set(initializer_list<value_type> __il, const allocator_type& __a) 6880b57cec5SDimitry Andric : set(__il, key_compare(), __a) {} 6890b57cec5SDimitry Andric# endif 6900b57cec5SDimitry Andric 691cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set& operator=(initializer_list<value_type> __il) { 6920b57cec5SDimitry Andric __tree_.__assign_unique(__il.begin(), __il.end()); 6930b57cec5SDimitry Andric return *this; 6940b57cec5SDimitry Andric } 6950b57cec5SDimitry Andric 696cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI set& operator=(set&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) { 6975f757f3fSDimitry Andric __tree_ = std::move(__s.__tree_); 6980b57cec5SDimitry Andric return *this; 6990b57cec5SDimitry Andric } 7000b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7010b57cec5SDimitry Andric 702cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~set() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 7030b57cec5SDimitry Andric 704cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 705cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 706cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 707cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 7080b57cec5SDimitry Andric 709cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 710cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 711cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 712cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 7130b57cec5SDimitry Andric 714cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 715cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 716cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 717cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 7180b57cec5SDimitry Andric 719cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 720cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 721cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 7220b57cec5SDimitry Andric 7230b57cec5SDimitry Andric // modifiers: 7240b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 7250b57cec5SDimitry Andric template <class... _Args> 726cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> emplace(_Args&&... __args) { 727cb14a3feSDimitry Andric return __tree_.__emplace_unique(std::forward<_Args>(__args)...); 728cb14a3feSDimitry Andric } 7290b57cec5SDimitry Andric template <class... _Args> 730cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 731cb14a3feSDimitry Andric return __tree_.__emplace_hint_unique(__p, std::forward<_Args>(__args)...); 732cb14a3feSDimitry Andric } 7330b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7340b57cec5SDimitry Andric 735cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); } 736cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 737cb14a3feSDimitry Andric return __tree_.__insert_unique(__p, __v); 738cb14a3feSDimitry Andric } 7390b57cec5SDimitry Andric 7400b57cec5SDimitry Andric template <class _InputIterator> 741cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 7420b57cec5SDimitry Andric for (const_iterator __e = cend(); __f != __l; ++__f) 7430b57cec5SDimitry Andric __tree_.__insert_unique(__e, *__f); 7440b57cec5SDimitry Andric } 7450b57cec5SDimitry Andric 74606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 74706c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 748cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 74906c3fb27SDimitry Andric const_iterator __end = cend(); 75006c3fb27SDimitry Andric for (auto&& __element : __range) { 75106c3fb27SDimitry Andric __tree_.__insert_unique(__end, std::forward<decltype(__element)>(__element)); 75206c3fb27SDimitry Andric } 75306c3fb27SDimitry Andric } 75406c3fb27SDimitry Andric#endif 75506c3fb27SDimitry Andric 7560b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 757cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(value_type&& __v) { 758cb14a3feSDimitry Andric return __tree_.__insert_unique(std::move(__v)); 759cb14a3feSDimitry Andric } 7600b57cec5SDimitry Andric 761cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { 762cb14a3feSDimitry Andric return __tree_.__insert_unique(__p, std::move(__v)); 763cb14a3feSDimitry Andric } 7640b57cec5SDimitry Andric 765cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 7660b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7670b57cec5SDimitry Andric 768cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); } 769cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); } 770cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); } 771cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 7720b57cec5SDimitry Andric 77306c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 774cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI insert_return_type insert(node_type&& __nh) { 7751db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 7760b57cec5SDimitry Andric "node_type with incompatible allocator passed to set::insert()"); 777cb14a3feSDimitry Andric return __tree_.template __node_handle_insert_unique< node_type, insert_return_type>(std::move(__nh)); 7780b57cec5SDimitry Andric } 779cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 7801db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 7810b57cec5SDimitry Andric "node_type with incompatible allocator passed to set::insert()"); 782cb14a3feSDimitry Andric return __tree_.template __node_handle_insert_unique<node_type>(__hint, std::move(__nh)); 7830b57cec5SDimitry Andric } 784cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 7850b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__key); 7860b57cec5SDimitry Andric } 787cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 7880b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__it); 7890b57cec5SDimitry Andric } 7900b57cec5SDimitry Andric template <class _Compare2> 791cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) { 7921db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 793cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 7940b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 7950b57cec5SDimitry Andric } 7960b57cec5SDimitry Andric template <class _Compare2> 797cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) { 7981db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 799cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8000b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8010b57cec5SDimitry Andric } 8020b57cec5SDimitry Andric template <class _Compare2> 803cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) { 8041db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 805cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8060b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8070b57cec5SDimitry Andric } 8080b57cec5SDimitry Andric template <class _Compare2> 809cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) { 8101db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 811cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 8120b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8130b57cec5SDimitry Andric } 8140b57cec5SDimitry Andric#endif 8150b57cec5SDimitry Andric 816cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) { 817cb14a3feSDimitry Andric __tree_.swap(__s.__tree_); 818cb14a3feSDimitry Andric } 8190b57cec5SDimitry Andric 820cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); } 821cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); } 822cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); } 8230b57cec5SDimitry Andric 8240b57cec5SDimitry Andric // set operations: 825cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 826cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 82706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 8285f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 829cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 830cb14a3feSDimitry Andric return __tree_.find(__k); 831cb14a3feSDimitry Andric } 8325f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 833cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 834cb14a3feSDimitry Andric return __tree_.find(__k); 835cb14a3feSDimitry Andric } 8360b57cec5SDimitry Andric#endif 8370b57cec5SDimitry Andric 838cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); } 83906c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 8405f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 841cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 842cb14a3feSDimitry Andric return __tree_.__count_multi(__k); 843cb14a3feSDimitry Andric } 8440b57cec5SDimitry Andric#endif 8450b57cec5SDimitry Andric 84606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 847cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 8485f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 849cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 850cb14a3feSDimitry Andric return find(__k) != end(); 851cb14a3feSDimitry Andric } 85206c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 8530b57cec5SDimitry Andric 854cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 855cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 85606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 8575f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 858cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) { 859cb14a3feSDimitry Andric return __tree_.lower_bound(__k); 860cb14a3feSDimitry Andric } 8610b57cec5SDimitry Andric 8625f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 863cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const { 864cb14a3feSDimitry Andric return __tree_.lower_bound(__k); 865cb14a3feSDimitry Andric } 8660b57cec5SDimitry Andric#endif 8670b57cec5SDimitry Andric 868cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 869cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 87006c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 8715f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 872cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) { 873cb14a3feSDimitry Andric return __tree_.upper_bound(__k); 874cb14a3feSDimitry Andric } 8755f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 876cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const { 877cb14a3feSDimitry Andric return __tree_.upper_bound(__k); 878cb14a3feSDimitry Andric } 8790b57cec5SDimitry Andric#endif 8800b57cec5SDimitry Andric 881cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 882cb14a3feSDimitry Andric return __tree_.__equal_range_unique(__k); 883cb14a3feSDimitry Andric } 884cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 885cb14a3feSDimitry Andric return __tree_.__equal_range_unique(__k); 886cb14a3feSDimitry Andric } 88706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 8885f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 889cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 890cb14a3feSDimitry Andric return __tree_.__equal_range_multi(__k); 891cb14a3feSDimitry Andric } 8925f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 893cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 894cb14a3feSDimitry Andric return __tree_.__equal_range_multi(__k); 895cb14a3feSDimitry Andric } 8960b57cec5SDimitry Andric#endif 8970b57cec5SDimitry Andric}; 8980b57cec5SDimitry Andric 899349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 9000b57cec5SDimitry Andrictemplate <class _InputIterator, 901fe6060f1SDimitry Andric class _Compare = less<__iter_value_type<_InputIterator>>, 902fe6060f1SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 90306c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 904349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 905349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 9060b57cec5SDimitry Andricset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 907fe6060f1SDimitry Andric -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 9080b57cec5SDimitry Andric 90906c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 910cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 911cb14a3feSDimitry Andric class _Compare = less<ranges::range_value_t<_Range>>, 91206c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 91306c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 91406c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 91506c3fb27SDimitry Andricset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) 91606c3fb27SDimitry Andric -> set<ranges::range_value_t<_Range>, _Compare, _Allocator>; 91706c3fb27SDimitry Andric# endif 91806c3fb27SDimitry Andric 919cb14a3feSDimitry Andrictemplate <class _Key, 920cb14a3feSDimitry Andric class _Compare = less<_Key>, 9210b57cec5SDimitry Andric class _Allocator = allocator<_Key>, 922349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>, 923349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 924cb14a3feSDimitry Andricset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) -> set<_Key, _Compare, _Allocator>; 9250b57cec5SDimitry Andric 926cb14a3feSDimitry Andrictemplate <class _InputIterator, 927cb14a3feSDimitry Andric class _Allocator, 92806c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 929349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 9300b57cec5SDimitry Andricset(_InputIterator, _InputIterator, _Allocator) 931cb14a3feSDimitry Andric -> set<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>; 9320b57cec5SDimitry Andric 93306c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 934cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 93506c3fb27SDimitry Andricset(from_range_t, _Range&&, _Allocator) 93606c3fb27SDimitry Andric -> set<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>; 93706c3fb27SDimitry Andric# endif 93806c3fb27SDimitry Andric 939cb14a3feSDimitry Andrictemplate <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 940cb14a3feSDimitry Andricset(initializer_list<_Key>, _Allocator) -> set<_Key, less<_Key>, _Allocator>; 9410b57cec5SDimitry Andric#endif 9420b57cec5SDimitry Andric 9430b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 9440b57cec5SDimitry Andric 9450b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 946cb14a3feSDimitry Andricset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(std::move(__s.__tree_), __a) { 947cb14a3feSDimitry Andric if (__a != __s.get_allocator()) { 9480b57cec5SDimitry Andric const_iterator __e = cend(); 9490b57cec5SDimitry Andric while (!__s.empty()) 9505f757f3fSDimitry Andric insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_)); 9510b57cec5SDimitry Andric } 9520b57cec5SDimitry Andric} 9530b57cec5SDimitry Andric 9540b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 9550b57cec5SDimitry Andric 9560b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 957cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 958cb14a3feSDimitry Andricoperator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 9595f757f3fSDimitry Andric return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 9600b57cec5SDimitry Andric} 9610b57cec5SDimitry Andric 96206c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 96306c3fb27SDimitry Andric 9640b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 965cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 966cb14a3feSDimitry Andricoperator<(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 9675f757f3fSDimitry Andric return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 9680b57cec5SDimitry Andric} 9690b57cec5SDimitry Andric 9700b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 971cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 972cb14a3feSDimitry Andricoperator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 9730b57cec5SDimitry Andric return !(__x == __y); 9740b57cec5SDimitry Andric} 9750b57cec5SDimitry Andric 9760b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 977cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 978cb14a3feSDimitry Andricoperator>(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 9790b57cec5SDimitry Andric return __y < __x; 9800b57cec5SDimitry Andric} 9810b57cec5SDimitry Andric 9820b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 983cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 984cb14a3feSDimitry Andricoperator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 9850b57cec5SDimitry Andric return !(__x < __y); 9860b57cec5SDimitry Andric} 9870b57cec5SDimitry Andric 9880b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 989cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 990cb14a3feSDimitry Andricoperator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y) { 9910b57cec5SDimitry Andric return !(__y < __x); 9920b57cec5SDimitry Andric} 9930b57cec5SDimitry Andric 99406c3fb27SDimitry Andric#else // _LIBCPP_STD_VER <= 17 99506c3fb27SDimitry Andric 99606c3fb27SDimitry Andrictemplate <class _Key, class _Allocator> 99706c3fb27SDimitry Andric_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key> 99806c3fb27SDimitry Andricoperator<=>(const set<_Key, _Allocator>& __x, const set<_Key, _Allocator>& __y) { 99906c3fb27SDimitry Andric return std::lexicographical_compare_three_way( 100006c3fb27SDimitry Andric __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>); 100106c3fb27SDimitry Andric} 100206c3fb27SDimitry Andric 100306c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER <= 17 100406c3fb27SDimitry Andric 10050b57cec5SDimitry Andric// specialized algorithms: 10060b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1007cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void swap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y) 1008cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 10090b57cec5SDimitry Andric __x.swap(__y); 10100b57cec5SDimitry Andric} 10110b57cec5SDimitry Andric 101206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 10130b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator, class _Predicate> 1014cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename set<_Key, _Compare, _Allocator>::size_type 10155ffd83dbSDimitry Andricerase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 10165f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 10175ffd83dbSDimitry Andric} 10180b57cec5SDimitry Andric#endif 10190b57cec5SDimitry Andric 1020cb14a3feSDimitry Andrictemplate <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> > 1021cb14a3feSDimitry Andricclass _LIBCPP_TEMPLATE_VIS multiset { 10220b57cec5SDimitry Andricpublic: 10230b57cec5SDimitry Andric // types: 10240b57cec5SDimitry Andric typedef _Key key_type; 10250b57cec5SDimitry Andric typedef key_type value_type; 102681ad6265SDimitry Andric typedef __type_identity_t<_Compare> key_compare; 10270b57cec5SDimitry Andric typedef key_compare value_compare; 102881ad6265SDimitry Andric typedef __type_identity_t<_Allocator> allocator_type; 10290b57cec5SDimitry Andric typedef value_type& reference; 10300b57cec5SDimitry Andric typedef const value_type& const_reference; 10310b57cec5SDimitry Andric 10320b57cec5SDimitry Andric static_assert((is_same<typename allocator_type::value_type, value_type>::value), 10330b57cec5SDimitry Andric "Allocator::value_type must be same type as value_type"); 10340b57cec5SDimitry Andric 10350b57cec5SDimitry Andricprivate: 10360b57cec5SDimitry Andric typedef __tree<value_type, value_compare, allocator_type> __base; 10370b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 10380b57cec5SDimitry Andric 1039bdd1243dSDimitry Andric static_assert(is_same<allocator_type, __rebind_alloc<__alloc_traits, value_type> >::value, 1040bdd1243dSDimitry Andric "[allocator.requirements] states that rebinding an allocator to the same type should result in the " 1041bdd1243dSDimitry Andric "original allocator"); 1042bdd1243dSDimitry Andric 10430b57cec5SDimitry Andric __base __tree_; 10440b57cec5SDimitry Andric 10450b57cec5SDimitry Andricpublic: 10460b57cec5SDimitry Andric typedef typename __base::pointer pointer; 10470b57cec5SDimitry Andric typedef typename __base::const_pointer const_pointer; 10480b57cec5SDimitry Andric typedef typename __base::size_type size_type; 10490b57cec5SDimitry Andric typedef typename __base::difference_type difference_type; 10500b57cec5SDimitry Andric typedef typename __base::const_iterator iterator; 10510b57cec5SDimitry Andric typedef typename __base::const_iterator const_iterator; 10525f757f3fSDimitry Andric typedef std::reverse_iterator<iterator> reverse_iterator; 10535f757f3fSDimitry Andric typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 10540b57cec5SDimitry Andric 105506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 10560b57cec5SDimitry Andric typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 10570b57cec5SDimitry Andric#endif 10580b57cec5SDimitry Andric 10590b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 10600b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS set; 10610b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 10620b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS multiset; 10630b57cec5SDimitry Andric 10640b57cec5SDimitry Andric // construct/copy/destroy: 1065cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset() _NOEXCEPT_( 1066cb14a3feSDimitry Andric is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_default_constructible<key_compare>::value&& 10670b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value) 10680b57cec5SDimitry Andric : __tree_(value_compare()) {} 10690b57cec5SDimitry Andric 1070cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp) _NOEXCEPT_( 1071cb14a3feSDimitry Andric is_nothrow_default_constructible<allocator_type>::value&& is_nothrow_copy_constructible<key_compare>::value) 10720b57cec5SDimitry Andric : __tree_(__comp) {} 10730b57cec5SDimitry Andric 1074cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit multiset(const value_compare& __comp, const allocator_type& __a) 10750b57cec5SDimitry Andric : __tree_(__comp, __a) {} 10760b57cec5SDimitry Andric template <class _InputIterator> 1077cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare()) 1078cb14a3feSDimitry Andric : __tree_(__comp) { 10790b57cec5SDimitry Andric insert(__f, __l); 10800b57cec5SDimitry Andric } 10810b57cec5SDimitry Andric 108206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 10830b57cec5SDimitry Andric template <class _InputIterator> 1084cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 10850b57cec5SDimitry Andric : multiset(__f, __l, key_compare(), __a) {} 10860b57cec5SDimitry Andric#endif 10870b57cec5SDimitry Andric 10880b57cec5SDimitry Andric template <class _InputIterator> 10895f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1090cb14a3feSDimitry Andric multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a) 1091cb14a3feSDimitry Andric : __tree_(__comp, __a) { 10920b57cec5SDimitry Andric insert(__f, __l); 10930b57cec5SDimitry Andric } 10940b57cec5SDimitry Andric 109506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 109606c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 109706c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI 1098cb14a3feSDimitry Andric multiset(from_range_t, 1099cb14a3feSDimitry Andric _Range&& __range, 1100cb14a3feSDimitry Andric const key_compare& __comp = key_compare(), 110106c3fb27SDimitry Andric const allocator_type& __a = allocator_type()) 110206c3fb27SDimitry Andric : __tree_(__comp, __a) { 110306c3fb27SDimitry Andric insert_range(std::forward<_Range>(__range)); 110406c3fb27SDimitry Andric } 110506c3fb27SDimitry Andric 110606c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1107cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(from_range_t, _Range&& __range, const allocator_type& __a) 110806c3fb27SDimitry Andric : multiset(from_range, std::forward<_Range>(__range), key_compare(), __a) {} 110906c3fb27SDimitry Andric#endif 111006c3fb27SDimitry Andric 1111cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s) 11120b57cec5SDimitry Andric : __tree_(__s.__tree_.value_comp(), 1113cb14a3feSDimitry Andric __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) { 11140b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 11150b57cec5SDimitry Andric } 11160b57cec5SDimitry Andric 1117cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset& operator=(const multiset& __s) { 11180b57cec5SDimitry Andric __tree_ = __s.__tree_; 11190b57cec5SDimitry Andric return *this; 11200b57cec5SDimitry Andric } 11210b57cec5SDimitry Andric 11220b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1123cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 11245f757f3fSDimitry Andric : __tree_(std::move(__s.__tree_)) {} 11250b57cec5SDimitry Andric 112606c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(multiset&& __s, const allocator_type& __a); 11270b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 1128cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI explicit multiset(const allocator_type& __a) : __tree_(__a) {} 1129cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(const multiset& __s, const allocator_type& __a) 1130cb14a3feSDimitry Andric : __tree_(__s.__tree_.value_comp(), __a) { 11310b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 11320b57cec5SDimitry Andric } 11330b57cec5SDimitry Andric 11340b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1135cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 1136cb14a3feSDimitry Andric : __tree_(__comp) { 11370b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11380b57cec5SDimitry Andric } 11390b57cec5SDimitry Andric 11405f757f3fSDimitry Andric _LIBCPP_HIDE_FROM_ABI 1141cb14a3feSDimitry Andric multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a) 1142cb14a3feSDimitry Andric : __tree_(__comp, __a) { 11430b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11440b57cec5SDimitry Andric } 11450b57cec5SDimitry Andric 114606c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 14 1147cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset(initializer_list<value_type> __il, const allocator_type& __a) 11480b57cec5SDimitry Andric : multiset(__il, key_compare(), __a) {} 11490b57cec5SDimitry Andric# endif 11500b57cec5SDimitry Andric 1151cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset& operator=(initializer_list<value_type> __il) { 11520b57cec5SDimitry Andric __tree_.__assign_multi(__il.begin(), __il.end()); 11530b57cec5SDimitry Andric return *this; 11540b57cec5SDimitry Andric } 11550b57cec5SDimitry Andric 1156cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) { 11575f757f3fSDimitry Andric __tree_ = std::move(__s.__tree_); 11580b57cec5SDimitry Andric return *this; 11590b57cec5SDimitry Andric } 11600b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 11610b57cec5SDimitry Andric 1162cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI ~multiset() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); } 11630b57cec5SDimitry Andric 1164cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); } 1165cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); } 1166cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); } 1167cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); } 11680b57cec5SDimitry Andric 1169cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 1170cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 1171cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 1172cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 11730b57cec5SDimitry Andric 1174cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 1175cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 1176cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 1177cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 11780b57cec5SDimitry Andric 1179cb14a3feSDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; } 1180cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); } 1181cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); } 11820b57cec5SDimitry Andric 11830b57cec5SDimitry Andric // modifiers: 11840b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 11850b57cec5SDimitry Andric template <class... _Args> 1186cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace(_Args&&... __args) { 1187cb14a3feSDimitry Andric return __tree_.__emplace_multi(std::forward<_Args>(__args)...); 1188cb14a3feSDimitry Andric } 11890b57cec5SDimitry Andric template <class... _Args> 1190cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator emplace_hint(const_iterator __p, _Args&&... __args) { 1191cb14a3feSDimitry Andric return __tree_.__emplace_hint_multi(__p, std::forward<_Args>(__args)...); 1192cb14a3feSDimitry Andric } 11930b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 11940b57cec5SDimitry Andric 1195cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); } 1196cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) { 1197cb14a3feSDimitry Andric return __tree_.__insert_multi(__p, __v); 1198cb14a3feSDimitry Andric } 11990b57cec5SDimitry Andric 12000b57cec5SDimitry Andric template <class _InputIterator> 1201cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) { 12020b57cec5SDimitry Andric for (const_iterator __e = cend(); __f != __l; ++__f) 12030b57cec5SDimitry Andric __tree_.__insert_multi(__e, *__f); 12040b57cec5SDimitry Andric } 12050b57cec5SDimitry Andric 120606c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 23 120706c3fb27SDimitry Andric template <_ContainerCompatibleRange<value_type> _Range> 1208cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert_range(_Range&& __range) { 120906c3fb27SDimitry Andric const_iterator __end = cend(); 121006c3fb27SDimitry Andric for (auto&& __element : __range) { 121106c3fb27SDimitry Andric __tree_.__insert_multi(__end, std::forward<decltype(__element)>(__element)); 121206c3fb27SDimitry Andric } 121306c3fb27SDimitry Andric } 121406c3fb27SDimitry Andric#endif 121506c3fb27SDimitry Andric 12160b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 1217cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(value_type&& __v) { return __tree_.__insert_multi(std::move(__v)); } 12180b57cec5SDimitry Andric 1219cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, value_type&& __v) { 1220cb14a3feSDimitry Andric return __tree_.__insert_multi(__p, std::move(__v)); 1221cb14a3feSDimitry Andric } 12220b57cec5SDimitry Andric 1223cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void insert(initializer_list<value_type> __il) { insert(__il.begin(), __il.end()); } 12240b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12250b57cec5SDimitry Andric 1226cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p); } 1227cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); } 1228cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) { return __tree_.erase(__f, __l); } 1229cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); } 12300b57cec5SDimitry Andric 123106c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1232cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(node_type&& __nh) { 12331db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 12340b57cec5SDimitry Andric "node_type with incompatible allocator passed to multiset::insert()"); 1235cb14a3feSDimitry Andric return __tree_.template __node_handle_insert_multi<node_type>(std::move(__nh)); 12360b57cec5SDimitry Andric } 1237cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __hint, node_type&& __nh) { 12381db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__nh.empty() || __nh.get_allocator() == get_allocator(), 12390b57cec5SDimitry Andric "node_type with incompatible allocator passed to multiset::insert()"); 1240cb14a3feSDimitry Andric return __tree_.template __node_handle_insert_multi<node_type>(__hint, std::move(__nh)); 12410b57cec5SDimitry Andric } 1242cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(key_type const& __key) { 12430b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__key); 12440b57cec5SDimitry Andric } 1245cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI node_type extract(const_iterator __it) { 12460b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__it); 12470b57cec5SDimitry Andric } 12480b57cec5SDimitry Andric template <class _Compare2> 1249cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>& __source) { 12501db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1251cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 12520b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 12530b57cec5SDimitry Andric } 12540b57cec5SDimitry Andric template <class _Compare2> 1255cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(multiset<key_type, _Compare2, allocator_type>&& __source) { 12561db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1257cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 12580b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 12590b57cec5SDimitry Andric } 12600b57cec5SDimitry Andric template <class _Compare2> 1261cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>& __source) { 12621db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1263cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 12640b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 12650b57cec5SDimitry Andric } 12660b57cec5SDimitry Andric template <class _Compare2> 1267cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void merge(set<key_type, _Compare2, allocator_type>&& __source) { 12681db9f3b2SDimitry Andric _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1269cb14a3feSDimitry Andric __source.get_allocator() == get_allocator(), "merging container with incompatible allocator"); 12700b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 12710b57cec5SDimitry Andric } 12720b57cec5SDimitry Andric#endif 12730b57cec5SDimitry Andric 1274cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) { 1275cb14a3feSDimitry Andric __tree_.swap(__s.__tree_); 1276cb14a3feSDimitry Andric } 12770b57cec5SDimitry Andric 1278cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return __tree_.__alloc(); } 1279cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp(); } 1280cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return __tree_.value_comp(); } 12810b57cec5SDimitry Andric 12820b57cec5SDimitry Andric // set operations: 1283cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); } 1284cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); } 128506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 12865f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1287cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator find(const _K2& __k) { 1288cb14a3feSDimitry Andric return __tree_.find(__k); 1289cb14a3feSDimitry Andric } 12905f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1291cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator find(const _K2& __k) const { 1292cb14a3feSDimitry Andric return __tree_.find(__k); 1293cb14a3feSDimitry Andric } 12940b57cec5SDimitry Andric#endif 12950b57cec5SDimitry Andric 1296cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); } 129706c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 12985f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1299cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI size_type count(const _K2& __k) const { 1300cb14a3feSDimitry Andric return __tree_.__count_multi(__k); 1301cb14a3feSDimitry Andric } 13020b57cec5SDimitry Andric#endif 13030b57cec5SDimitry Andric 130406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 1305cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const key_type& __k) const { return find(__k) != end(); } 13065f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1307cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI bool contains(const _K2& __k) const { 1308cb14a3feSDimitry Andric return find(__k) != end(); 1309cb14a3feSDimitry Andric } 131006c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER >= 20 13110b57cec5SDimitry Andric 1312cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); } 1313cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); } 131406c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 13155f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1316cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) { 1317cb14a3feSDimitry Andric return __tree_.lower_bound(__k); 1318cb14a3feSDimitry Andric } 13190b57cec5SDimitry Andric 13205f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1321cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const _K2& __k) const { 1322cb14a3feSDimitry Andric return __tree_.lower_bound(__k); 1323cb14a3feSDimitry Andric } 13240b57cec5SDimitry Andric#endif 13250b57cec5SDimitry Andric 1326cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); } 1327cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); } 132806c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 13295f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1330cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) { 1331cb14a3feSDimitry Andric return __tree_.upper_bound(__k); 1332cb14a3feSDimitry Andric } 13335f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1334cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const _K2& __k) const { 1335cb14a3feSDimitry Andric return __tree_.upper_bound(__k); 1336cb14a3feSDimitry Andric } 13370b57cec5SDimitry Andric#endif 13380b57cec5SDimitry Andric 1339cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) { 1340cb14a3feSDimitry Andric return __tree_.__equal_range_multi(__k); 1341cb14a3feSDimitry Andric } 1342cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const { 1343cb14a3feSDimitry Andric return __tree_.__equal_range_multi(__k); 1344cb14a3feSDimitry Andric } 134506c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 14 13465f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1347cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const _K2& __k) { 1348cb14a3feSDimitry Andric return __tree_.__equal_range_multi(__k); 1349cb14a3feSDimitry Andric } 13505f757f3fSDimitry Andric template <typename _K2, enable_if_t<__is_transparent<_Compare, _K2>::value, int> = 0> 1351cb14a3feSDimitry Andric _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const _K2& __k) const { 1352cb14a3feSDimitry Andric return __tree_.__equal_range_multi(__k); 1353cb14a3feSDimitry Andric } 13540b57cec5SDimitry Andric#endif 13550b57cec5SDimitry Andric}; 13560b57cec5SDimitry Andric 1357349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 13580b57cec5SDimitry Andrictemplate <class _InputIterator, 1359fe6060f1SDimitry Andric class _Compare = less<__iter_value_type<_InputIterator>>, 1360fe6060f1SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 136106c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 1362349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 1363349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 13640b57cec5SDimitry Andricmultiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1365fe6060f1SDimitry Andric -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 13660b57cec5SDimitry Andric 136706c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 1368cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, 1369cb14a3feSDimitry Andric class _Compare = less<ranges::range_value_t<_Range>>, 137006c3fb27SDimitry Andric class _Allocator = allocator<ranges::range_value_t<_Range>>, 137106c3fb27SDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 137206c3fb27SDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 137306c3fb27SDimitry Andricmultiset(from_range_t, _Range&&, _Compare = _Compare(), _Allocator = _Allocator()) 137406c3fb27SDimitry Andric -> multiset<ranges::range_value_t<_Range>, _Compare, _Allocator>; 137506c3fb27SDimitry Andric# endif 137606c3fb27SDimitry Andric 1377cb14a3feSDimitry Andrictemplate <class _Key, 1378cb14a3feSDimitry Andric class _Compare = less<_Key>, 13790b57cec5SDimitry Andric class _Allocator = allocator<_Key>, 1380349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 1381349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 13820b57cec5SDimitry Andricmultiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 13830b57cec5SDimitry Andric -> multiset<_Key, _Compare, _Allocator>; 13840b57cec5SDimitry Andric 1385cb14a3feSDimitry Andrictemplate <class _InputIterator, 1386cb14a3feSDimitry Andric class _Allocator, 138706c3fb27SDimitry Andric class = enable_if_t<__has_input_iterator_category<_InputIterator>::value, void>, 1388349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 13890b57cec5SDimitry Andricmultiset(_InputIterator, _InputIterator, _Allocator) 1390cb14a3feSDimitry Andric -> multiset<__iter_value_type<_InputIterator>, less<__iter_value_type<_InputIterator>>, _Allocator>; 13910b57cec5SDimitry Andric 139206c3fb27SDimitry Andric# if _LIBCPP_STD_VER >= 23 1393cb14a3feSDimitry Andrictemplate <ranges::input_range _Range, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 139406c3fb27SDimitry Andricmultiset(from_range_t, _Range&&, _Allocator) 139506c3fb27SDimitry Andric -> multiset<ranges::range_value_t<_Range>, less<ranges::range_value_t<_Range>>, _Allocator>; 139606c3fb27SDimitry Andric# endif 139706c3fb27SDimitry Andric 1398cb14a3feSDimitry Andrictemplate <class _Key, class _Allocator, class = enable_if_t<__is_allocator<_Allocator>::value, void>> 1399cb14a3feSDimitry Andricmultiset(initializer_list<_Key>, _Allocator) -> multiset<_Key, less<_Key>, _Allocator>; 14000b57cec5SDimitry Andric#endif 14010b57cec5SDimitry Andric 14020b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 14030b57cec5SDimitry Andric 14040b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 14050b57cec5SDimitry Andricmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 1406cb14a3feSDimitry Andric : __tree_(std::move(__s.__tree_), __a) { 1407cb14a3feSDimitry Andric if (__a != __s.get_allocator()) { 14080b57cec5SDimitry Andric const_iterator __e = cend(); 14090b57cec5SDimitry Andric while (!__s.empty()) 14105f757f3fSDimitry Andric insert(__e, std::move(__s.__tree_.remove(__s.begin())->__value_)); 14110b57cec5SDimitry Andric } 14120b57cec5SDimitry Andric} 14130b57cec5SDimitry Andric 14140b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 14150b57cec5SDimitry Andric 14160b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1417cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 1418cb14a3feSDimitry Andricoperator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 14195f757f3fSDimitry Andric return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 14200b57cec5SDimitry Andric} 14210b57cec5SDimitry Andric 142206c3fb27SDimitry Andric#if _LIBCPP_STD_VER <= 17 142306c3fb27SDimitry Andric 14240b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1425cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 1426cb14a3feSDimitry Andricoperator<(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 14275f757f3fSDimitry Andric return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 14280b57cec5SDimitry Andric} 14290b57cec5SDimitry Andric 14300b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1431cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 1432cb14a3feSDimitry Andricoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 14330b57cec5SDimitry Andric return !(__x == __y); 14340b57cec5SDimitry Andric} 14350b57cec5SDimitry Andric 14360b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1437cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 1438cb14a3feSDimitry Andricoperator>(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 14390b57cec5SDimitry Andric return __y < __x; 14400b57cec5SDimitry Andric} 14410b57cec5SDimitry Andric 14420b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1443cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 1444cb14a3feSDimitry Andricoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 14450b57cec5SDimitry Andric return !(__x < __y); 14460b57cec5SDimitry Andric} 14470b57cec5SDimitry Andric 14480b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1449cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI bool 1450cb14a3feSDimitry Andricoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y) { 14510b57cec5SDimitry Andric return !(__y < __x); 14520b57cec5SDimitry Andric} 14530b57cec5SDimitry Andric 145406c3fb27SDimitry Andric#else // _LIBCPP_STD_VER <= 17 145506c3fb27SDimitry Andric 145606c3fb27SDimitry Andrictemplate <class _Key, class _Allocator> 145706c3fb27SDimitry Andric_LIBCPP_HIDE_FROM_ABI __synth_three_way_result<_Key> 145806c3fb27SDimitry Andricoperator<=>(const multiset<_Key, _Allocator>& __x, const multiset<_Key, _Allocator>& __y) { 145906c3fb27SDimitry Andric return std::lexicographical_compare_three_way( 146006c3fb27SDimitry Andric __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Key, _Key>); 146106c3fb27SDimitry Andric} 146206c3fb27SDimitry Andric 146306c3fb27SDimitry Andric#endif // _LIBCPP_STD_VER <= 17 146406c3fb27SDimitry Andric 14650b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 1466cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI void 1467cb14a3feSDimitry Andricswap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y) 1468cb14a3feSDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { 14690b57cec5SDimitry Andric __x.swap(__y); 14700b57cec5SDimitry Andric} 14710b57cec5SDimitry Andric 147206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 20 14730b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator, class _Predicate> 1474cb14a3feSDimitry Andricinline _LIBCPP_HIDE_FROM_ABI typename multiset<_Key, _Compare, _Allocator>::size_type 14755ffd83dbSDimitry Andricerase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 14765f757f3fSDimitry Andric return std::__libcpp_erase_if_container(__c, __pred); 14775ffd83dbSDimitry Andric} 14780b57cec5SDimitry Andric#endif 14790b57cec5SDimitry Andric 14800b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 14810b57cec5SDimitry Andric 148206c3fb27SDimitry Andric#if _LIBCPP_STD_VER >= 17 1483bdd1243dSDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 1484bdd1243dSDimitry Andricnamespace pmr { 1485bdd1243dSDimitry Andrictemplate <class _KeyT, class _CompareT = std::less<_KeyT>> 148606c3fb27SDimitry Andricusing set _LIBCPP_AVAILABILITY_PMR = std::set<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>; 1487bdd1243dSDimitry Andric 1488bdd1243dSDimitry Andrictemplate <class _KeyT, class _CompareT = std::less<_KeyT>> 148906c3fb27SDimitry Andricusing multiset _LIBCPP_AVAILABILITY_PMR = std::multiset<_KeyT, _CompareT, polymorphic_allocator<_KeyT>>; 1490bdd1243dSDimitry Andric} // namespace pmr 1491bdd1243dSDimitry Andric_LIBCPP_END_NAMESPACE_STD 1492bdd1243dSDimitry Andric#endif 1493bdd1243dSDimitry Andric 1494b3edf446SDimitry Andric_LIBCPP_POP_MACROS 1495b3edf446SDimitry Andric 1496bdd1243dSDimitry Andric#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 1497bdd1243dSDimitry Andric# include <concepts> 149806c3fb27SDimitry Andric# include <cstdlib> 1499bdd1243dSDimitry Andric# include <functional> 1500bdd1243dSDimitry Andric# include <iterator> 15015f757f3fSDimitry Andric# include <stdexcept> 150206c3fb27SDimitry Andric# include <type_traits> 1503bdd1243dSDimitry Andric#endif 1504bdd1243dSDimitry Andric 15050b57cec5SDimitry Andric#endif // _LIBCPP_SET 1506