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); 590b57cec5SDimitry Andric set(const set& s); 600b57cec5SDimitry Andric set(set&& s) 610b57cec5SDimitry Andric noexcept( 620b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value && 630b57cec5SDimitry Andric is_nothrow_move_constructible<key_compare>::value); 640b57cec5SDimitry Andric explicit set(const allocator_type& a); 650b57cec5SDimitry Andric set(const set& s, const allocator_type& a); 660b57cec5SDimitry Andric set(set&& s, const allocator_type& a); 670b57cec5SDimitry Andric set(initializer_list<value_type> il, const value_compare& comp = value_compare()); 680b57cec5SDimitry Andric set(initializer_list<value_type> il, const value_compare& comp, 690b57cec5SDimitry Andric const allocator_type& a); 700b57cec5SDimitry Andric template <class InputIterator> 710b57cec5SDimitry Andric set(InputIterator first, InputIterator last, const allocator_type& a) 720b57cec5SDimitry Andric : set(first, last, Compare(), a) {} // C++14 730b57cec5SDimitry Andric set(initializer_list<value_type> il, const allocator_type& a) 740b57cec5SDimitry Andric : set(il, Compare(), a) {} // C++14 750b57cec5SDimitry Andric ~set(); 760b57cec5SDimitry Andric 770b57cec5SDimitry Andric set& operator=(const set& s); 780b57cec5SDimitry Andric set& operator=(set&& s) 790b57cec5SDimitry Andric noexcept( 800b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 810b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 820b57cec5SDimitry Andric is_nothrow_move_assignable<key_compare>::value); 830b57cec5SDimitry Andric set& operator=(initializer_list<value_type> il); 840b57cec5SDimitry Andric 850b57cec5SDimitry Andric // iterators: 860b57cec5SDimitry Andric iterator begin() noexcept; 870b57cec5SDimitry Andric const_iterator begin() const noexcept; 880b57cec5SDimitry Andric iterator end() noexcept; 890b57cec5SDimitry Andric const_iterator end() const noexcept; 900b57cec5SDimitry Andric 910b57cec5SDimitry Andric reverse_iterator rbegin() noexcept; 920b57cec5SDimitry Andric const_reverse_iterator rbegin() const noexcept; 930b57cec5SDimitry Andric reverse_iterator rend() noexcept; 940b57cec5SDimitry Andric const_reverse_iterator rend() const noexcept; 950b57cec5SDimitry Andric 960b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 970b57cec5SDimitry Andric const_iterator cend() const noexcept; 980b57cec5SDimitry Andric const_reverse_iterator crbegin() const noexcept; 990b57cec5SDimitry Andric const_reverse_iterator crend() const noexcept; 1000b57cec5SDimitry Andric 1010b57cec5SDimitry Andric // capacity: 1020b57cec5SDimitry Andric bool empty() const noexcept; 1030b57cec5SDimitry Andric size_type size() const noexcept; 1040b57cec5SDimitry Andric size_type max_size() const noexcept; 1050b57cec5SDimitry Andric 1060b57cec5SDimitry Andric // modifiers: 1070b57cec5SDimitry Andric template <class... Args> 1080b57cec5SDimitry Andric pair<iterator, bool> emplace(Args&&... args); 1090b57cec5SDimitry Andric template <class... Args> 1100b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 1110b57cec5SDimitry Andric pair<iterator,bool> insert(const value_type& v); 1120b57cec5SDimitry Andric pair<iterator,bool> insert(value_type&& v); 1130b57cec5SDimitry Andric iterator insert(const_iterator position, const value_type& v); 1140b57cec5SDimitry Andric iterator insert(const_iterator position, value_type&& v); 1150b57cec5SDimitry Andric template <class InputIterator> 1160b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 1170b57cec5SDimitry Andric void insert(initializer_list<value_type> il); 1180b57cec5SDimitry Andric 1190b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 1200b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 1210b57cec5SDimitry Andric insert_return_type insert(node_type&& nh); // C++17 1220b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 1230b57cec5SDimitry Andric 1240b57cec5SDimitry Andric iterator erase(const_iterator position); 1250b57cec5SDimitry Andric iterator erase(iterator position); // C++14 1260b57cec5SDimitry Andric size_type erase(const key_type& k); 1270b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 1280b57cec5SDimitry Andric void clear() noexcept; 1290b57cec5SDimitry Andric 1300b57cec5SDimitry Andric template<class C2> 1310b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>& source); // C++17 1320b57cec5SDimitry Andric template<class C2> 1330b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>&& source); // C++17 1340b57cec5SDimitry Andric template<class C2> 1350b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>& source); // C++17 1360b57cec5SDimitry Andric template<class C2> 1370b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>&& source); // C++17 1380b57cec5SDimitry Andric 1390b57cec5SDimitry Andric void swap(set& s) 1400b57cec5SDimitry Andric noexcept( 1410b57cec5SDimitry Andric __is_nothrow_swappable<key_compare>::value && 1420b57cec5SDimitry Andric (!allocator_type::propagate_on_container_swap::value || 1430b57cec5SDimitry Andric __is_nothrow_swappable<allocator_type>::value)); 1440b57cec5SDimitry Andric 1450b57cec5SDimitry Andric // observers: 1460b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 1470b57cec5SDimitry Andric key_compare key_comp() const; 1480b57cec5SDimitry Andric value_compare value_comp() const; 1490b57cec5SDimitry Andric 1500b57cec5SDimitry Andric // set operations: 1510b57cec5SDimitry Andric iterator find(const key_type& k); 1520b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 1530b57cec5SDimitry Andric template<typename K> 1540b57cec5SDimitry Andric iterator find(const K& x); 1550b57cec5SDimitry Andric template<typename K> 1560b57cec5SDimitry Andric const_iterator find(const K& x) const; // C++14 157fe6060f1SDimitry Andric 1580b57cec5SDimitry Andric template<typename K> 1590b57cec5SDimitry Andric size_type count(const K& x) const; // C++14 1600b57cec5SDimitry Andric size_type count(const key_type& k) const; 161fe6060f1SDimitry Andric 1620b57cec5SDimitry Andric bool contains(const key_type& x) const; // C++20 163fe6060f1SDimitry Andric template<class K> bool contains(const K& x) const; // C++20 164fe6060f1SDimitry Andric 1650b57cec5SDimitry Andric iterator lower_bound(const key_type& k); 1660b57cec5SDimitry Andric const_iterator lower_bound(const key_type& k) const; 1670b57cec5SDimitry Andric template<typename K> 1680b57cec5SDimitry Andric iterator lower_bound(const K& x); // C++14 1690b57cec5SDimitry Andric template<typename K> 1700b57cec5SDimitry Andric const_iterator lower_bound(const K& x) const; // C++14 1710b57cec5SDimitry Andric 1720b57cec5SDimitry Andric iterator upper_bound(const key_type& k); 1730b57cec5SDimitry Andric const_iterator upper_bound(const key_type& k) const; 1740b57cec5SDimitry Andric template<typename K> 1750b57cec5SDimitry Andric iterator upper_bound(const K& x); // C++14 1760b57cec5SDimitry Andric template<typename K> 1770b57cec5SDimitry Andric const_iterator upper_bound(const K& x) const; // C++14 1780b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const key_type& k); 1790b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 1800b57cec5SDimitry Andric template<typename K> 1810b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const K& x); // C++14 1820b57cec5SDimitry Andric template<typename K> 1830b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 1840b57cec5SDimitry Andric}; 1850b57cec5SDimitry Andric 186349cc55cSDimitry Andrictemplate <class InputIterator, 187349cc55cSDimitry Andric class Compare = less<typename iterator_traits<InputIterator>::value_type>, 188349cc55cSDimitry Andric class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 189349cc55cSDimitry Andricset(InputIterator, InputIterator, 190349cc55cSDimitry Andric Compare = Compare(), Allocator = Allocator()) 191349cc55cSDimitry Andric -> set<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 192349cc55cSDimitry Andric 193349cc55cSDimitry Andrictemplate<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 194349cc55cSDimitry Andricset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 195349cc55cSDimitry Andric -> set<Key, Compare, Allocator>; // C++17 196349cc55cSDimitry Andric 197349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 198349cc55cSDimitry Andricset(InputIterator, InputIterator, Allocator) 199349cc55cSDimitry Andric -> set<typename iterator_traits<InputIterator>::value_type, 200349cc55cSDimitry Andric less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 201349cc55cSDimitry Andric 202349cc55cSDimitry Andrictemplate<class Key, class Allocator> 203349cc55cSDimitry Andricset(initializer_list<Key>, Allocator) -> set<Key, less<Key>, Allocator>; // C++17 204349cc55cSDimitry Andric 2050b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2060b57cec5SDimitry Andricbool 2070b57cec5SDimitry Andricoperator==(const set<Key, Compare, Allocator>& x, 2080b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2090b57cec5SDimitry Andric 2100b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2110b57cec5SDimitry Andricbool 2120b57cec5SDimitry Andricoperator< (const set<Key, Compare, Allocator>& x, 2130b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2140b57cec5SDimitry Andric 2150b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2160b57cec5SDimitry Andricbool 2170b57cec5SDimitry Andricoperator!=(const set<Key, Compare, Allocator>& x, 2180b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2190b57cec5SDimitry Andric 2200b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2210b57cec5SDimitry Andricbool 2220b57cec5SDimitry Andricoperator> (const set<Key, Compare, Allocator>& x, 2230b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2240b57cec5SDimitry Andric 2250b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2260b57cec5SDimitry Andricbool 2270b57cec5SDimitry Andricoperator>=(const set<Key, Compare, Allocator>& x, 2280b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2290b57cec5SDimitry Andric 2300b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2310b57cec5SDimitry Andricbool 2320b57cec5SDimitry Andricoperator<=(const set<Key, Compare, Allocator>& x, 2330b57cec5SDimitry Andric const set<Key, Compare, Allocator>& y); 2340b57cec5SDimitry Andric 2350b57cec5SDimitry Andric// specialized algorithms: 2360b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 2370b57cec5SDimitry Andricvoid 2380b57cec5SDimitry Andricswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) 2390b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 2400b57cec5SDimitry Andric 2410b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator, class Predicate> 2425ffd83dbSDimitry Andrictypename set<Key, Compare, Allocator>::size_type 2435ffd83dbSDimitry Andricerase_if(set<Key, Compare, Allocator>& c, Predicate pred); // C++20 2440b57cec5SDimitry Andric 2450b57cec5SDimitry Andrictemplate <class Key, class Compare = less<Key>, 2460b57cec5SDimitry Andric class Allocator = allocator<Key>> 2470b57cec5SDimitry Andricclass multiset 2480b57cec5SDimitry Andric{ 2490b57cec5SDimitry Andricpublic: 2500b57cec5SDimitry Andric // types: 2510b57cec5SDimitry Andric typedef Key key_type; 2520b57cec5SDimitry Andric typedef key_type value_type; 2530b57cec5SDimitry Andric typedef Compare key_compare; 2540b57cec5SDimitry Andric typedef key_compare value_compare; 2550b57cec5SDimitry Andric typedef Allocator allocator_type; 2560b57cec5SDimitry Andric typedef typename allocator_type::reference reference; 2570b57cec5SDimitry Andric typedef typename allocator_type::const_reference const_reference; 2580b57cec5SDimitry Andric typedef typename allocator_type::size_type size_type; 2590b57cec5SDimitry Andric typedef typename allocator_type::difference_type difference_type; 2600b57cec5SDimitry Andric typedef typename allocator_type::pointer pointer; 2610b57cec5SDimitry Andric typedef typename allocator_type::const_pointer const_pointer; 2620b57cec5SDimitry Andric 2630b57cec5SDimitry Andric typedef implementation-defined iterator; 2640b57cec5SDimitry Andric typedef implementation-defined const_iterator; 2650b57cec5SDimitry Andric typedef std::reverse_iterator<iterator> reverse_iterator; 2660b57cec5SDimitry Andric typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 2670b57cec5SDimitry Andric typedef unspecified node_type; // C++17 2680b57cec5SDimitry Andric 2690b57cec5SDimitry Andric // construct/copy/destroy: 2700b57cec5SDimitry Andric multiset() 2710b57cec5SDimitry Andric noexcept( 2720b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 2730b57cec5SDimitry Andric is_nothrow_default_constructible<key_compare>::value && 2740b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value); 2750b57cec5SDimitry Andric explicit multiset(const value_compare& comp); 2760b57cec5SDimitry Andric multiset(const value_compare& comp, const allocator_type& a); 2770b57cec5SDimitry Andric template <class InputIterator> 2780b57cec5SDimitry Andric multiset(InputIterator first, InputIterator last, 2790b57cec5SDimitry Andric const value_compare& comp = value_compare()); 2800b57cec5SDimitry Andric template <class InputIterator> 2810b57cec5SDimitry Andric multiset(InputIterator first, InputIterator last, 2820b57cec5SDimitry Andric const value_compare& comp, const allocator_type& a); 2830b57cec5SDimitry Andric multiset(const multiset& s); 2840b57cec5SDimitry Andric multiset(multiset&& s) 2850b57cec5SDimitry Andric noexcept( 2860b57cec5SDimitry Andric is_nothrow_move_constructible<allocator_type>::value && 2870b57cec5SDimitry Andric is_nothrow_move_constructible<key_compare>::value); 2880b57cec5SDimitry Andric explicit multiset(const allocator_type& a); 2890b57cec5SDimitry Andric multiset(const multiset& s, const allocator_type& a); 2900b57cec5SDimitry Andric multiset(multiset&& s, const allocator_type& a); 2910b57cec5SDimitry Andric multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); 2920b57cec5SDimitry Andric multiset(initializer_list<value_type> il, const value_compare& comp, 2930b57cec5SDimitry Andric const allocator_type& a); 2940b57cec5SDimitry Andric template <class InputIterator> 2950b57cec5SDimitry Andric multiset(InputIterator first, InputIterator last, const allocator_type& a) 2960b57cec5SDimitry Andric : set(first, last, Compare(), a) {} // C++14 2970b57cec5SDimitry Andric multiset(initializer_list<value_type> il, const allocator_type& a) 2980b57cec5SDimitry Andric : set(il, Compare(), a) {} // C++14 2990b57cec5SDimitry Andric ~multiset(); 3000b57cec5SDimitry Andric 3010b57cec5SDimitry Andric multiset& operator=(const multiset& s); 3020b57cec5SDimitry Andric multiset& operator=(multiset&& s) 3030b57cec5SDimitry Andric noexcept( 3040b57cec5SDimitry Andric allocator_type::propagate_on_container_move_assignment::value && 3050b57cec5SDimitry Andric is_nothrow_move_assignable<allocator_type>::value && 3060b57cec5SDimitry Andric is_nothrow_move_assignable<key_compare>::value); 3070b57cec5SDimitry Andric multiset& operator=(initializer_list<value_type> il); 3080b57cec5SDimitry Andric 3090b57cec5SDimitry Andric // iterators: 3100b57cec5SDimitry Andric iterator begin() noexcept; 3110b57cec5SDimitry Andric const_iterator begin() const noexcept; 3120b57cec5SDimitry Andric iterator end() noexcept; 3130b57cec5SDimitry Andric const_iterator end() const noexcept; 3140b57cec5SDimitry Andric 3150b57cec5SDimitry Andric reverse_iterator rbegin() noexcept; 3160b57cec5SDimitry Andric const_reverse_iterator rbegin() const noexcept; 3170b57cec5SDimitry Andric reverse_iterator rend() noexcept; 3180b57cec5SDimitry Andric const_reverse_iterator rend() const noexcept; 3190b57cec5SDimitry Andric 3200b57cec5SDimitry Andric const_iterator cbegin() const noexcept; 3210b57cec5SDimitry Andric const_iterator cend() const noexcept; 3220b57cec5SDimitry Andric const_reverse_iterator crbegin() const noexcept; 3230b57cec5SDimitry Andric const_reverse_iterator crend() const noexcept; 3240b57cec5SDimitry Andric 3250b57cec5SDimitry Andric // capacity: 3260b57cec5SDimitry Andric bool empty() const noexcept; 3270b57cec5SDimitry Andric size_type size() const noexcept; 3280b57cec5SDimitry Andric size_type max_size() const noexcept; 3290b57cec5SDimitry Andric 3300b57cec5SDimitry Andric // modifiers: 3310b57cec5SDimitry Andric template <class... Args> 3320b57cec5SDimitry Andric iterator emplace(Args&&... args); 3330b57cec5SDimitry Andric template <class... Args> 3340b57cec5SDimitry Andric iterator emplace_hint(const_iterator position, Args&&... args); 3350b57cec5SDimitry Andric iterator insert(const value_type& v); 3360b57cec5SDimitry Andric iterator insert(value_type&& v); 3370b57cec5SDimitry Andric iterator insert(const_iterator position, const value_type& v); 3380b57cec5SDimitry Andric iterator insert(const_iterator position, value_type&& v); 3390b57cec5SDimitry Andric template <class InputIterator> 3400b57cec5SDimitry Andric void insert(InputIterator first, InputIterator last); 3410b57cec5SDimitry Andric void insert(initializer_list<value_type> il); 3420b57cec5SDimitry Andric 3430b57cec5SDimitry Andric node_type extract(const_iterator position); // C++17 3440b57cec5SDimitry Andric node_type extract(const key_type& x); // C++17 3450b57cec5SDimitry Andric iterator insert(node_type&& nh); // C++17 3460b57cec5SDimitry Andric iterator insert(const_iterator hint, node_type&& nh); // C++17 3470b57cec5SDimitry Andric 3480b57cec5SDimitry Andric iterator erase(const_iterator position); 3490b57cec5SDimitry Andric iterator erase(iterator position); // C++14 3500b57cec5SDimitry Andric size_type erase(const key_type& k); 3510b57cec5SDimitry Andric iterator erase(const_iterator first, const_iterator last); 3520b57cec5SDimitry Andric void clear() noexcept; 3530b57cec5SDimitry Andric 3540b57cec5SDimitry Andric template<class C2> 3550b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>& source); // C++17 3560b57cec5SDimitry Andric template<class C2> 3570b57cec5SDimitry Andric void merge(multiset<Key, C2, Allocator>&& source); // C++17 3580b57cec5SDimitry Andric template<class C2> 3590b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>& source); // C++17 3600b57cec5SDimitry Andric template<class C2> 3610b57cec5SDimitry Andric void merge(set<Key, C2, Allocator>&& source); // C++17 3620b57cec5SDimitry Andric 3630b57cec5SDimitry Andric void swap(multiset& s) 3640b57cec5SDimitry Andric noexcept( 3650b57cec5SDimitry Andric __is_nothrow_swappable<key_compare>::value && 3660b57cec5SDimitry Andric (!allocator_type::propagate_on_container_swap::value || 3670b57cec5SDimitry Andric __is_nothrow_swappable<allocator_type>::value)); 3680b57cec5SDimitry Andric 3690b57cec5SDimitry Andric // observers: 3700b57cec5SDimitry Andric allocator_type get_allocator() const noexcept; 3710b57cec5SDimitry Andric key_compare key_comp() const; 3720b57cec5SDimitry Andric value_compare value_comp() const; 3730b57cec5SDimitry Andric 3740b57cec5SDimitry Andric // set operations: 3750b57cec5SDimitry Andric iterator find(const key_type& k); 3760b57cec5SDimitry Andric const_iterator find(const key_type& k) const; 3770b57cec5SDimitry Andric template<typename K> 3780b57cec5SDimitry Andric iterator find(const K& x); 3790b57cec5SDimitry Andric template<typename K> 3800b57cec5SDimitry Andric const_iterator find(const K& x) const; // C++14 381fe6060f1SDimitry Andric 3820b57cec5SDimitry Andric template<typename K> 3830b57cec5SDimitry Andric size_type count(const K& x) const; // C++14 3840b57cec5SDimitry Andric size_type count(const key_type& k) const; 385fe6060f1SDimitry Andric 3860b57cec5SDimitry Andric bool contains(const key_type& x) const; // C++20 387fe6060f1SDimitry Andric template<class K> bool contains(const K& x) const; // C++20 388fe6060f1SDimitry Andric 3890b57cec5SDimitry Andric iterator lower_bound(const key_type& k); 3900b57cec5SDimitry Andric const_iterator lower_bound(const key_type& k) const; 3910b57cec5SDimitry Andric template<typename K> 3920b57cec5SDimitry Andric iterator lower_bound(const K& x); // C++14 3930b57cec5SDimitry Andric template<typename K> 3940b57cec5SDimitry Andric const_iterator lower_bound(const K& x) const; // C++14 3950b57cec5SDimitry Andric 3960b57cec5SDimitry Andric iterator upper_bound(const key_type& k); 3970b57cec5SDimitry Andric const_iterator upper_bound(const key_type& k) const; 3980b57cec5SDimitry Andric template<typename K> 3990b57cec5SDimitry Andric iterator upper_bound(const K& x); // C++14 4000b57cec5SDimitry Andric template<typename K> 4010b57cec5SDimitry Andric const_iterator upper_bound(const K& x) const; // C++14 4020b57cec5SDimitry Andric 4030b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const key_type& k); 4040b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const key_type& k) const; 4050b57cec5SDimitry Andric template<typename K> 4060b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const K& x); // C++14 4070b57cec5SDimitry Andric template<typename K> 4080b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14 4090b57cec5SDimitry Andric}; 4100b57cec5SDimitry Andric 411349cc55cSDimitry Andrictemplate <class InputIterator, 412349cc55cSDimitry Andric class Compare = less<typename iterator_traits<InputIterator>::value_type>, 413349cc55cSDimitry Andric class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 414349cc55cSDimitry Andricmultiset(InputIterator, InputIterator, 415349cc55cSDimitry Andric Compare = Compare(), Allocator = Allocator()) 416349cc55cSDimitry Andric -> multiset<typename iterator_traits<InputIterator>::value_type, Compare, Allocator>; // C++17 417349cc55cSDimitry Andric 418349cc55cSDimitry Andrictemplate<class Key, class Compare = less<Key>, class Allocator = allocator<Key>> 419349cc55cSDimitry Andricmultiset(initializer_list<Key>, Compare = Compare(), Allocator = Allocator()) 420349cc55cSDimitry Andric -> multiset<Key, Compare, Allocator>; // C++17 421349cc55cSDimitry Andric 422349cc55cSDimitry Andrictemplate<class InputIterator, class Allocator> 423349cc55cSDimitry Andricmultiset(InputIterator, InputIterator, Allocator) 424349cc55cSDimitry Andric -> multiset<typename iterator_traits<InputIterator>::value_type, 425349cc55cSDimitry Andric less<typename iterator_traits<InputIterator>::value_type>, Allocator>; // C++17 426349cc55cSDimitry Andric 427349cc55cSDimitry Andrictemplate<class Key, class Allocator> 428349cc55cSDimitry Andricmultiset(initializer_list<Key>, Allocator) -> multiset<Key, less<Key>, Allocator>; // C++17 429349cc55cSDimitry Andric 4300b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4310b57cec5SDimitry Andricbool 4320b57cec5SDimitry Andricoperator==(const multiset<Key, Compare, Allocator>& x, 4330b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4340b57cec5SDimitry Andric 4350b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4360b57cec5SDimitry Andricbool 4370b57cec5SDimitry Andricoperator< (const multiset<Key, Compare, Allocator>& x, 4380b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4390b57cec5SDimitry Andric 4400b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4410b57cec5SDimitry Andricbool 4420b57cec5SDimitry Andricoperator!=(const multiset<Key, Compare, Allocator>& x, 4430b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4440b57cec5SDimitry Andric 4450b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4460b57cec5SDimitry Andricbool 4470b57cec5SDimitry Andricoperator> (const multiset<Key, Compare, Allocator>& x, 4480b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4490b57cec5SDimitry Andric 4500b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4510b57cec5SDimitry Andricbool 4520b57cec5SDimitry Andricoperator>=(const multiset<Key, Compare, Allocator>& x, 4530b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4540b57cec5SDimitry Andric 4550b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4560b57cec5SDimitry Andricbool 4570b57cec5SDimitry Andricoperator<=(const multiset<Key, Compare, Allocator>& x, 4580b57cec5SDimitry Andric const multiset<Key, Compare, Allocator>& y); 4590b57cec5SDimitry Andric 4600b57cec5SDimitry Andric// specialized algorithms: 4610b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator> 4620b57cec5SDimitry Andricvoid 4630b57cec5SDimitry Andricswap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) 4640b57cec5SDimitry Andric noexcept(noexcept(x.swap(y))); 4650b57cec5SDimitry Andric 4660b57cec5SDimitry Andrictemplate <class Key, class Compare, class Allocator, class Predicate> 4675ffd83dbSDimitry Andrictypename multiset<Key, Compare, Allocator>::size_type 4685ffd83dbSDimitry Andricerase_if(multiset<Key, Compare, Allocator>& c, Predicate pred); // C++20 4690b57cec5SDimitry Andric 4700b57cec5SDimitry Andric} // std 4710b57cec5SDimitry Andric 4720b57cec5SDimitry Andric*/ 4730b57cec5SDimitry Andric 474*81ad6265SDimitry Andric#include <__algorithm/equal.h> 475*81ad6265SDimitry Andric#include <__algorithm/lexicographical_compare.h> 476*81ad6265SDimitry Andric#include <__assert> // all public C++ headers provide the assertion handler 4770b57cec5SDimitry Andric#include <__config> 478fe6060f1SDimitry Andric#include <__functional/is_transparent.h> 479*81ad6265SDimitry Andric#include <__functional/operations.h> 480*81ad6265SDimitry Andric#include <__iterator/erase_if_container.h> 481349cc55cSDimitry Andric#include <__iterator/iterator_traits.h> 482*81ad6265SDimitry Andric#include <__iterator/reverse_iterator.h> 4830b57cec5SDimitry Andric#include <__node_handle> 484fe6060f1SDimitry Andric#include <__tree> 485fe6060f1SDimitry Andric#include <__utility/forward.h> 4860b57cec5SDimitry Andric#include <version> 4870b57cec5SDimitry Andric 488*81ad6265SDimitry Andric#ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES 489*81ad6265SDimitry Andric# include <functional> 490*81ad6265SDimitry Andric# include <iterator> 491*81ad6265SDimitry Andric#endif 492*81ad6265SDimitry Andric 493*81ad6265SDimitry Andric// standard-mandated includes 494*81ad6265SDimitry Andric 495*81ad6265SDimitry Andric// [iterator.range] 496*81ad6265SDimitry Andric#include <__iterator/access.h> 497*81ad6265SDimitry Andric#include <__iterator/data.h> 498*81ad6265SDimitry Andric#include <__iterator/empty.h> 499*81ad6265SDimitry Andric#include <__iterator/reverse_access.h> 500*81ad6265SDimitry Andric#include <__iterator/size.h> 501*81ad6265SDimitry Andric 502*81ad6265SDimitry Andric// [associative.set.syn] 503*81ad6265SDimitry Andric#include <compare> 504*81ad6265SDimitry Andric#include <initializer_list> 505*81ad6265SDimitry Andric 5060b57cec5SDimitry Andric#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 5070b57cec5SDimitry Andric# pragma GCC system_header 5080b57cec5SDimitry Andric#endif 5090b57cec5SDimitry Andric 5100b57cec5SDimitry Andric_LIBCPP_BEGIN_NAMESPACE_STD 5110b57cec5SDimitry Andric 5120b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 5130b57cec5SDimitry Andricclass multiset; 5140b57cec5SDimitry Andric 5150b57cec5SDimitry Andrictemplate <class _Key, class _Compare = less<_Key>, 5160b57cec5SDimitry Andric class _Allocator = allocator<_Key> > 5170b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS set 5180b57cec5SDimitry Andric{ 5190b57cec5SDimitry Andricpublic: 5200b57cec5SDimitry Andric // types: 5210b57cec5SDimitry Andric typedef _Key key_type; 5220b57cec5SDimitry Andric typedef key_type value_type; 523*81ad6265SDimitry Andric typedef __type_identity_t<_Compare> key_compare; 5240b57cec5SDimitry Andric typedef key_compare value_compare; 525*81ad6265SDimitry Andric typedef __type_identity_t<_Allocator> allocator_type; 5260b57cec5SDimitry Andric typedef value_type& reference; 5270b57cec5SDimitry Andric typedef const value_type& const_reference; 5280b57cec5SDimitry Andric 5290b57cec5SDimitry Andric static_assert((is_same<typename allocator_type::value_type, value_type>::value), 5300b57cec5SDimitry Andric "Allocator::value_type must be same type as value_type"); 5310b57cec5SDimitry Andric 5320b57cec5SDimitry Andricprivate: 5330b57cec5SDimitry Andric typedef __tree<value_type, value_compare, allocator_type> __base; 5340b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 5350b57cec5SDimitry Andric 5360b57cec5SDimitry Andric __base __tree_; 5370b57cec5SDimitry Andric 5380b57cec5SDimitry Andricpublic: 5390b57cec5SDimitry Andric typedef typename __base::pointer pointer; 5400b57cec5SDimitry Andric typedef typename __base::const_pointer const_pointer; 5410b57cec5SDimitry Andric typedef typename __base::size_type size_type; 5420b57cec5SDimitry Andric typedef typename __base::difference_type difference_type; 5430b57cec5SDimitry Andric typedef typename __base::const_iterator iterator; 5440b57cec5SDimitry Andric typedef typename __base::const_iterator const_iterator; 5450b57cec5SDimitry Andric typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 5460b57cec5SDimitry Andric typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 5470b57cec5SDimitry Andric 5480b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 5490b57cec5SDimitry Andric typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 5500b57cec5SDimitry Andric typedef __insert_return_type<iterator, node_type> insert_return_type; 5510b57cec5SDimitry Andric#endif 5520b57cec5SDimitry Andric 5530b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 5540b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS set; 5550b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 5560b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS multiset; 5570b57cec5SDimitry Andric 5580b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5590b57cec5SDimitry Andric set() 5600b57cec5SDimitry Andric _NOEXCEPT_( 5610b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 5620b57cec5SDimitry Andric is_nothrow_default_constructible<key_compare>::value && 5630b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value) 5640b57cec5SDimitry Andric : __tree_(value_compare()) {} 5650b57cec5SDimitry Andric 5660b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5670b57cec5SDimitry Andric explicit set(const value_compare& __comp) 5680b57cec5SDimitry Andric _NOEXCEPT_( 5690b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 5700b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value) 5710b57cec5SDimitry Andric : __tree_(__comp) {} 5720b57cec5SDimitry Andric 5730b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5740b57cec5SDimitry Andric explicit set(const value_compare& __comp, const allocator_type& __a) 5750b57cec5SDimitry Andric : __tree_(__comp, __a) {} 5760b57cec5SDimitry Andric template <class _InputIterator> 5770b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5780b57cec5SDimitry Andric set(_InputIterator __f, _InputIterator __l, 5790b57cec5SDimitry Andric const value_compare& __comp = value_compare()) 5800b57cec5SDimitry Andric : __tree_(__comp) 5810b57cec5SDimitry Andric { 5820b57cec5SDimitry Andric insert(__f, __l); 5830b57cec5SDimitry Andric } 5840b57cec5SDimitry Andric 5850b57cec5SDimitry Andric template <class _InputIterator> 5860b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5870b57cec5SDimitry Andric set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, 5880b57cec5SDimitry Andric const allocator_type& __a) 5890b57cec5SDimitry Andric : __tree_(__comp, __a) 5900b57cec5SDimitry Andric { 5910b57cec5SDimitry Andric insert(__f, __l); 5920b57cec5SDimitry Andric } 5930b57cec5SDimitry Andric 5940b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 5950b57cec5SDimitry Andric template <class _InputIterator> 5960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 5970b57cec5SDimitry Andric set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 5980b57cec5SDimitry Andric : set(__f, __l, key_compare(), __a) {} 5990b57cec5SDimitry Andric#endif 6000b57cec5SDimitry Andric 6010b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6020b57cec5SDimitry Andric set(const set& __s) 6030b57cec5SDimitry Andric : __tree_(__s.__tree_) 6040b57cec5SDimitry Andric { 6050b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 6060b57cec5SDimitry Andric } 6070b57cec5SDimitry Andric 6080b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6090b57cec5SDimitry Andric set& operator=(const set& __s) 6100b57cec5SDimitry Andric { 6110b57cec5SDimitry Andric __tree_ = __s.__tree_; 6120b57cec5SDimitry Andric return *this; 6130b57cec5SDimitry Andric } 6140b57cec5SDimitry Andric 6150b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 6160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6170b57cec5SDimitry Andric set(set&& __s) 6180b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 6190b57cec5SDimitry Andric : __tree_(_VSTD::move(__s.__tree_)) {} 6200b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 6210b57cec5SDimitry Andric 6220b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6230b57cec5SDimitry Andric explicit set(const allocator_type& __a) 6240b57cec5SDimitry Andric : __tree_(__a) {} 6250b57cec5SDimitry Andric 6260b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6270b57cec5SDimitry Andric set(const set& __s, const allocator_type& __a) 6280b57cec5SDimitry Andric : __tree_(__s.__tree_.value_comp(), __a) 6290b57cec5SDimitry Andric { 6300b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 6310b57cec5SDimitry Andric } 6320b57cec5SDimitry Andric 6330b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 6340b57cec5SDimitry Andric set(set&& __s, const allocator_type& __a); 6350b57cec5SDimitry Andric 6360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6370b57cec5SDimitry Andric set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 6380b57cec5SDimitry Andric : __tree_(__comp) 6390b57cec5SDimitry Andric { 6400b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 6410b57cec5SDimitry Andric } 6420b57cec5SDimitry Andric 6430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6440b57cec5SDimitry Andric set(initializer_list<value_type> __il, const value_compare& __comp, 6450b57cec5SDimitry Andric const allocator_type& __a) 6460b57cec5SDimitry Andric : __tree_(__comp, __a) 6470b57cec5SDimitry Andric { 6480b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 6490b57cec5SDimitry Andric } 6500b57cec5SDimitry Andric 6510b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 6520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6530b57cec5SDimitry Andric set(initializer_list<value_type> __il, const allocator_type& __a) 6540b57cec5SDimitry Andric : set(__il, key_compare(), __a) {} 6550b57cec5SDimitry Andric#endif 6560b57cec5SDimitry Andric 6570b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6580b57cec5SDimitry Andric set& operator=(initializer_list<value_type> __il) 6590b57cec5SDimitry Andric { 6600b57cec5SDimitry Andric __tree_.__assign_unique(__il.begin(), __il.end()); 6610b57cec5SDimitry Andric return *this; 6620b57cec5SDimitry Andric } 6630b57cec5SDimitry Andric 6640b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6650b57cec5SDimitry Andric set& operator=(set&& __s) 6660b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 6670b57cec5SDimitry Andric { 6680b57cec5SDimitry Andric __tree_ = _VSTD::move(__s.__tree_); 6690b57cec5SDimitry Andric return *this; 6700b57cec5SDimitry Andric } 6710b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 6720b57cec5SDimitry Andric 6730b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6740b57cec5SDimitry Andric ~set() { 6750b57cec5SDimitry Andric static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 6760b57cec5SDimitry Andric } 6770b57cec5SDimitry Andric 6780b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6790b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return __tree_.begin();} 6800b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6810b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 6820b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6830b57cec5SDimitry Andric iterator end() _NOEXCEPT {return __tree_.end();} 6840b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6850b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return __tree_.end();} 6860b57cec5SDimitry Andric 6870b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6880b57cec5SDimitry Andric reverse_iterator rbegin() _NOEXCEPT 6890b57cec5SDimitry Andric {return reverse_iterator(end());} 6900b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6910b57cec5SDimitry Andric const_reverse_iterator rbegin() const _NOEXCEPT 6920b57cec5SDimitry Andric {return const_reverse_iterator(end());} 6930b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6940b57cec5SDimitry Andric reverse_iterator rend() _NOEXCEPT 6950b57cec5SDimitry Andric {return reverse_iterator(begin());} 6960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 6970b57cec5SDimitry Andric const_reverse_iterator rend() const _NOEXCEPT 6980b57cec5SDimitry Andric {return const_reverse_iterator(begin());} 6990b57cec5SDimitry Andric 7000b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7010b57cec5SDimitry Andric const_iterator cbegin() const _NOEXCEPT {return begin();} 7020b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7030b57cec5SDimitry Andric const_iterator cend() const _NOEXCEPT {return end();} 7040b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7050b57cec5SDimitry Andric const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 7060b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7070b57cec5SDimitry Andric const_reverse_iterator crend() const _NOEXCEPT {return rend();} 7080b57cec5SDimitry Andric 7090b57cec5SDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 7100b57cec5SDimitry Andric bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 7110b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7120b57cec5SDimitry Andric size_type size() const _NOEXCEPT {return __tree_.size();} 7130b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7140b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 7150b57cec5SDimitry Andric 7160b57cec5SDimitry Andric // modifiers: 7170b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 7180b57cec5SDimitry Andric template <class... _Args> 7190b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7200b57cec5SDimitry Andric pair<iterator, bool> emplace(_Args&&... __args) 7210b57cec5SDimitry Andric {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} 7220b57cec5SDimitry Andric template <class... _Args> 7230b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7240b57cec5SDimitry Andric iterator emplace_hint(const_iterator __p, _Args&&... __args) 7250b57cec5SDimitry Andric {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);} 7260b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7270b57cec5SDimitry Andric 7280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7290b57cec5SDimitry Andric pair<iterator,bool> insert(const value_type& __v) 7300b57cec5SDimitry Andric {return __tree_.__insert_unique(__v);} 7310b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7320b57cec5SDimitry Andric iterator insert(const_iterator __p, const value_type& __v) 7330b57cec5SDimitry Andric {return __tree_.__insert_unique(__p, __v);} 7340b57cec5SDimitry Andric 7350b57cec5SDimitry Andric template <class _InputIterator> 7360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7370b57cec5SDimitry Andric void insert(_InputIterator __f, _InputIterator __l) 7380b57cec5SDimitry Andric { 7390b57cec5SDimitry Andric for (const_iterator __e = cend(); __f != __l; ++__f) 7400b57cec5SDimitry Andric __tree_.__insert_unique(__e, *__f); 7410b57cec5SDimitry Andric } 7420b57cec5SDimitry Andric 7430b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 7440b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7450b57cec5SDimitry Andric pair<iterator,bool> insert(value_type&& __v) 7460b57cec5SDimitry Andric {return __tree_.__insert_unique(_VSTD::move(__v));} 7470b57cec5SDimitry Andric 7480b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7490b57cec5SDimitry Andric iterator insert(const_iterator __p, value_type&& __v) 7500b57cec5SDimitry Andric {return __tree_.__insert_unique(__p, _VSTD::move(__v));} 7510b57cec5SDimitry Andric 7520b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7530b57cec5SDimitry Andric void insert(initializer_list<value_type> __il) 7540b57cec5SDimitry Andric {insert(__il.begin(), __il.end());} 7550b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 7560b57cec5SDimitry Andric 7570b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7580b57cec5SDimitry Andric iterator erase(const_iterator __p) {return __tree_.erase(__p);} 7590b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7600b57cec5SDimitry Andric size_type erase(const key_type& __k) 7610b57cec5SDimitry Andric {return __tree_.__erase_unique(__k);} 7620b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7630b57cec5SDimitry Andric iterator erase(const_iterator __f, const_iterator __l) 7640b57cec5SDimitry Andric {return __tree_.erase(__f, __l);} 7650b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7660b57cec5SDimitry Andric void clear() _NOEXCEPT {__tree_.clear();} 7670b57cec5SDimitry Andric 7680b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 7690b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7700b57cec5SDimitry Andric insert_return_type insert(node_type&& __nh) 7710b57cec5SDimitry Andric { 7720b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 7730b57cec5SDimitry Andric "node_type with incompatible allocator passed to set::insert()"); 7740b57cec5SDimitry Andric return __tree_.template __node_handle_insert_unique< 7750b57cec5SDimitry Andric node_type, insert_return_type>(_VSTD::move(__nh)); 7760b57cec5SDimitry Andric } 7770b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7780b57cec5SDimitry Andric iterator insert(const_iterator __hint, node_type&& __nh) 7790b57cec5SDimitry Andric { 7800b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 7810b57cec5SDimitry Andric "node_type with incompatible allocator passed to set::insert()"); 7820b57cec5SDimitry Andric return __tree_.template __node_handle_insert_unique<node_type>( 7830b57cec5SDimitry Andric __hint, _VSTD::move(__nh)); 7840b57cec5SDimitry Andric } 7850b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7860b57cec5SDimitry Andric node_type extract(key_type const& __key) 7870b57cec5SDimitry Andric { 7880b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__key); 7890b57cec5SDimitry Andric } 7900b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7910b57cec5SDimitry Andric node_type extract(const_iterator __it) 7920b57cec5SDimitry Andric { 7930b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__it); 7940b57cec5SDimitry Andric } 7950b57cec5SDimitry Andric template <class _Compare2> 7960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 7970b57cec5SDimitry Andric void merge(set<key_type, _Compare2, allocator_type>& __source) 7980b57cec5SDimitry Andric { 7990b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 8000b57cec5SDimitry Andric "merging container with incompatible allocator"); 8010b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8020b57cec5SDimitry Andric } 8030b57cec5SDimitry Andric template <class _Compare2> 8040b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8050b57cec5SDimitry Andric void merge(set<key_type, _Compare2, allocator_type>&& __source) 8060b57cec5SDimitry Andric { 8070b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 8080b57cec5SDimitry Andric "merging container with incompatible allocator"); 8090b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8100b57cec5SDimitry Andric } 8110b57cec5SDimitry Andric template <class _Compare2> 8120b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8130b57cec5SDimitry Andric void merge(multiset<key_type, _Compare2, allocator_type>& __source) 8140b57cec5SDimitry Andric { 8150b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 8160b57cec5SDimitry Andric "merging container with incompatible allocator"); 8170b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8180b57cec5SDimitry Andric } 8190b57cec5SDimitry Andric template <class _Compare2> 8200b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8210b57cec5SDimitry Andric void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 8220b57cec5SDimitry Andric { 8230b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 8240b57cec5SDimitry Andric "merging container with incompatible allocator"); 8250b57cec5SDimitry Andric __tree_.__node_handle_merge_unique(__source.__tree_); 8260b57cec5SDimitry Andric } 8270b57cec5SDimitry Andric#endif 8280b57cec5SDimitry Andric 8290b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8300b57cec5SDimitry Andric void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 8310b57cec5SDimitry Andric {__tree_.swap(__s.__tree_);} 8320b57cec5SDimitry Andric 8330b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8340b57cec5SDimitry Andric allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 8350b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8360b57cec5SDimitry Andric key_compare key_comp() const {return __tree_.value_comp();} 8370b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8380b57cec5SDimitry Andric value_compare value_comp() const {return __tree_.value_comp();} 8390b57cec5SDimitry Andric 8400b57cec5SDimitry Andric // set operations: 8410b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8420b57cec5SDimitry Andric iterator find(const key_type& __k) {return __tree_.find(__k);} 8430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8440b57cec5SDimitry Andric const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 8450b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 8460b57cec5SDimitry Andric template <typename _K2> 8470b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8480b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 8490b57cec5SDimitry Andric find(const _K2& __k) {return __tree_.find(__k);} 8500b57cec5SDimitry Andric template <typename _K2> 8510b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8520b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 8530b57cec5SDimitry Andric find(const _K2& __k) const {return __tree_.find(__k);} 8540b57cec5SDimitry Andric#endif 8550b57cec5SDimitry Andric 8560b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8570b57cec5SDimitry Andric size_type count(const key_type& __k) const 8580b57cec5SDimitry Andric {return __tree_.__count_unique(__k);} 8590b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 8600b57cec5SDimitry Andric template <typename _K2> 8610b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8620b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 8630b57cec5SDimitry Andric count(const _K2& __k) const {return __tree_.__count_multi(__k);} 8640b57cec5SDimitry Andric#endif 8650b57cec5SDimitry Andric 8660b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 8670b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8680b57cec5SDimitry Andric bool contains(const key_type& __k) const {return find(__k) != end();} 869fe6060f1SDimitry Andric template <typename _K2> 870fe6060f1SDimitry Andric _LIBCPP_INLINE_VISIBILITY 871fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 872fe6060f1SDimitry Andric contains(const _K2& __k) const { return find(__k) != end(); } 8730b57cec5SDimitry Andric#endif // _LIBCPP_STD_VER > 17 8740b57cec5SDimitry Andric 8750b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8760b57cec5SDimitry Andric iterator lower_bound(const key_type& __k) 8770b57cec5SDimitry Andric {return __tree_.lower_bound(__k);} 8780b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8790b57cec5SDimitry Andric const_iterator lower_bound(const key_type& __k) const 8800b57cec5SDimitry Andric {return __tree_.lower_bound(__k);} 8810b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 8820b57cec5SDimitry Andric template <typename _K2> 8830b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8840b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 8850b57cec5SDimitry Andric lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 8860b57cec5SDimitry Andric 8870b57cec5SDimitry Andric template <typename _K2> 8880b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8890b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 8900b57cec5SDimitry Andric lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 8910b57cec5SDimitry Andric#endif 8920b57cec5SDimitry Andric 8930b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8940b57cec5SDimitry Andric iterator upper_bound(const key_type& __k) 8950b57cec5SDimitry Andric {return __tree_.upper_bound(__k);} 8960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 8970b57cec5SDimitry Andric const_iterator upper_bound(const key_type& __k) const 8980b57cec5SDimitry Andric {return __tree_.upper_bound(__k);} 8990b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 9000b57cec5SDimitry Andric template <typename _K2> 9010b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9020b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 9030b57cec5SDimitry Andric upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 9040b57cec5SDimitry Andric template <typename _K2> 9050b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9060b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 9070b57cec5SDimitry Andric upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 9080b57cec5SDimitry Andric#endif 9090b57cec5SDimitry Andric 9100b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9110b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const key_type& __k) 9120b57cec5SDimitry Andric {return __tree_.__equal_range_unique(__k);} 9130b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9140b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 9150b57cec5SDimitry Andric {return __tree_.__equal_range_unique(__k);} 9160b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 9170b57cec5SDimitry Andric template <typename _K2> 9180b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9190b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 9200b57cec5SDimitry Andric equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 9210b57cec5SDimitry Andric template <typename _K2> 9220b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 9230b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 9240b57cec5SDimitry Andric equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 9250b57cec5SDimitry Andric#endif 9260b57cec5SDimitry Andric}; 9270b57cec5SDimitry Andric 928349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 9290b57cec5SDimitry Andrictemplate<class _InputIterator, 930fe6060f1SDimitry Andric class _Compare = less<__iter_value_type<_InputIterator>>, 931fe6060f1SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 932349cc55cSDimitry Andric class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 933349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 934349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 9350b57cec5SDimitry Andricset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 936fe6060f1SDimitry Andric -> set<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 9370b57cec5SDimitry Andric 9380b57cec5SDimitry Andrictemplate<class _Key, class _Compare = less<_Key>, 9390b57cec5SDimitry Andric class _Allocator = allocator<_Key>, 940349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>, 941349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 9420b57cec5SDimitry Andricset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 9430b57cec5SDimitry Andric -> set<_Key, _Compare, _Allocator>; 9440b57cec5SDimitry Andric 9450b57cec5SDimitry Andrictemplate<class _InputIterator, class _Allocator, 946349cc55cSDimitry Andric class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 947349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 9480b57cec5SDimitry Andricset(_InputIterator, _InputIterator, _Allocator) 949fe6060f1SDimitry Andric -> set<__iter_value_type<_InputIterator>, 950fe6060f1SDimitry Andric less<__iter_value_type<_InputIterator>>, _Allocator>; 9510b57cec5SDimitry Andric 9520b57cec5SDimitry Andrictemplate<class _Key, class _Allocator, 953349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 9540b57cec5SDimitry Andricset(initializer_list<_Key>, _Allocator) 9550b57cec5SDimitry Andric -> set<_Key, less<_Key>, _Allocator>; 9560b57cec5SDimitry Andric#endif 9570b57cec5SDimitry Andric 9580b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 9590b57cec5SDimitry Andric 9600b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 9610b57cec5SDimitry Andricset<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) 9620b57cec5SDimitry Andric : __tree_(_VSTD::move(__s.__tree_), __a) 9630b57cec5SDimitry Andric{ 9640b57cec5SDimitry Andric if (__a != __s.get_allocator()) 9650b57cec5SDimitry Andric { 9660b57cec5SDimitry Andric const_iterator __e = cend(); 9670b57cec5SDimitry Andric while (!__s.empty()) 9680b57cec5SDimitry Andric insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 9690b57cec5SDimitry Andric } 9700b57cec5SDimitry Andric} 9710b57cec5SDimitry Andric 9720b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 9730b57cec5SDimitry Andric 9740b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 9750b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 9760b57cec5SDimitry Andricbool 9770b57cec5SDimitry Andricoperator==(const set<_Key, _Compare, _Allocator>& __x, 9780b57cec5SDimitry Andric const set<_Key, _Compare, _Allocator>& __y) 9790b57cec5SDimitry Andric{ 9800b57cec5SDimitry Andric return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 9810b57cec5SDimitry Andric} 9820b57cec5SDimitry Andric 9830b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 9840b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 9850b57cec5SDimitry Andricbool 9860b57cec5SDimitry Andricoperator< (const set<_Key, _Compare, _Allocator>& __x, 9870b57cec5SDimitry Andric const set<_Key, _Compare, _Allocator>& __y) 9880b57cec5SDimitry Andric{ 9890b57cec5SDimitry Andric return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 9900b57cec5SDimitry Andric} 9910b57cec5SDimitry Andric 9920b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 9930b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 9940b57cec5SDimitry Andricbool 9950b57cec5SDimitry Andricoperator!=(const set<_Key, _Compare, _Allocator>& __x, 9960b57cec5SDimitry Andric const set<_Key, _Compare, _Allocator>& __y) 9970b57cec5SDimitry Andric{ 9980b57cec5SDimitry Andric return !(__x == __y); 9990b57cec5SDimitry Andric} 10000b57cec5SDimitry Andric 10010b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 10020b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10030b57cec5SDimitry Andricbool 10040b57cec5SDimitry Andricoperator> (const set<_Key, _Compare, _Allocator>& __x, 10050b57cec5SDimitry Andric const set<_Key, _Compare, _Allocator>& __y) 10060b57cec5SDimitry Andric{ 10070b57cec5SDimitry Andric return __y < __x; 10080b57cec5SDimitry Andric} 10090b57cec5SDimitry Andric 10100b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 10110b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10120b57cec5SDimitry Andricbool 10130b57cec5SDimitry Andricoperator>=(const set<_Key, _Compare, _Allocator>& __x, 10140b57cec5SDimitry Andric const set<_Key, _Compare, _Allocator>& __y) 10150b57cec5SDimitry Andric{ 10160b57cec5SDimitry Andric return !(__x < __y); 10170b57cec5SDimitry Andric} 10180b57cec5SDimitry Andric 10190b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 10200b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10210b57cec5SDimitry Andricbool 10220b57cec5SDimitry Andricoperator<=(const set<_Key, _Compare, _Allocator>& __x, 10230b57cec5SDimitry Andric const set<_Key, _Compare, _Allocator>& __y) 10240b57cec5SDimitry Andric{ 10250b57cec5SDimitry Andric return !(__y < __x); 10260b57cec5SDimitry Andric} 10270b57cec5SDimitry Andric 10280b57cec5SDimitry Andric// specialized algorithms: 10290b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 10300b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10310b57cec5SDimitry Andricvoid 10320b57cec5SDimitry Andricswap(set<_Key, _Compare, _Allocator>& __x, 10330b57cec5SDimitry Andric set<_Key, _Compare, _Allocator>& __y) 10340b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 10350b57cec5SDimitry Andric{ 10360b57cec5SDimitry Andric __x.swap(__y); 10370b57cec5SDimitry Andric} 10380b57cec5SDimitry Andric 10390b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 10400b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator, class _Predicate> 10410b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 10425ffd83dbSDimitry Andric typename set<_Key, _Compare, _Allocator>::size_type 10435ffd83dbSDimitry Andric erase_if(set<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 1044fe6060f1SDimitry Andric return _VSTD::__libcpp_erase_if_container(__c, __pred); 10455ffd83dbSDimitry Andric} 10460b57cec5SDimitry Andric#endif 10470b57cec5SDimitry Andric 10480b57cec5SDimitry Andrictemplate <class _Key, class _Compare = less<_Key>, 10490b57cec5SDimitry Andric class _Allocator = allocator<_Key> > 10500b57cec5SDimitry Andricclass _LIBCPP_TEMPLATE_VIS multiset 10510b57cec5SDimitry Andric{ 10520b57cec5SDimitry Andricpublic: 10530b57cec5SDimitry Andric // types: 10540b57cec5SDimitry Andric typedef _Key key_type; 10550b57cec5SDimitry Andric typedef key_type value_type; 1056*81ad6265SDimitry Andric typedef __type_identity_t<_Compare> key_compare; 10570b57cec5SDimitry Andric typedef key_compare value_compare; 1058*81ad6265SDimitry Andric typedef __type_identity_t<_Allocator> allocator_type; 10590b57cec5SDimitry Andric typedef value_type& reference; 10600b57cec5SDimitry Andric typedef const value_type& const_reference; 10610b57cec5SDimitry Andric 10620b57cec5SDimitry Andric static_assert((is_same<typename allocator_type::value_type, value_type>::value), 10630b57cec5SDimitry Andric "Allocator::value_type must be same type as value_type"); 10640b57cec5SDimitry Andric 10650b57cec5SDimitry Andricprivate: 10660b57cec5SDimitry Andric typedef __tree<value_type, value_compare, allocator_type> __base; 10670b57cec5SDimitry Andric typedef allocator_traits<allocator_type> __alloc_traits; 10680b57cec5SDimitry Andric 10690b57cec5SDimitry Andric __base __tree_; 10700b57cec5SDimitry Andric 10710b57cec5SDimitry Andricpublic: 10720b57cec5SDimitry Andric typedef typename __base::pointer pointer; 10730b57cec5SDimitry Andric typedef typename __base::const_pointer const_pointer; 10740b57cec5SDimitry Andric typedef typename __base::size_type size_type; 10750b57cec5SDimitry Andric typedef typename __base::difference_type difference_type; 10760b57cec5SDimitry Andric typedef typename __base::const_iterator iterator; 10770b57cec5SDimitry Andric typedef typename __base::const_iterator const_iterator; 10780b57cec5SDimitry Andric typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 10790b57cec5SDimitry Andric typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 10800b57cec5SDimitry Andric 10810b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 10820b57cec5SDimitry Andric typedef __set_node_handle<typename __base::__node, allocator_type> node_type; 10830b57cec5SDimitry Andric#endif 10840b57cec5SDimitry Andric 10850b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 10860b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS set; 10870b57cec5SDimitry Andric template <class _Key2, class _Compare2, class _Alloc2> 10880b57cec5SDimitry Andric friend class _LIBCPP_TEMPLATE_VIS multiset; 10890b57cec5SDimitry Andric 10900b57cec5SDimitry Andric // construct/copy/destroy: 10910b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 10920b57cec5SDimitry Andric multiset() 10930b57cec5SDimitry Andric _NOEXCEPT_( 10940b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 10950b57cec5SDimitry Andric is_nothrow_default_constructible<key_compare>::value && 10960b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value) 10970b57cec5SDimitry Andric : __tree_(value_compare()) {} 10980b57cec5SDimitry Andric 10990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11000b57cec5SDimitry Andric explicit multiset(const value_compare& __comp) 11010b57cec5SDimitry Andric _NOEXCEPT_( 11020b57cec5SDimitry Andric is_nothrow_default_constructible<allocator_type>::value && 11030b57cec5SDimitry Andric is_nothrow_copy_constructible<key_compare>::value) 11040b57cec5SDimitry Andric : __tree_(__comp) {} 11050b57cec5SDimitry Andric 11060b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11070b57cec5SDimitry Andric explicit multiset(const value_compare& __comp, const allocator_type& __a) 11080b57cec5SDimitry Andric : __tree_(__comp, __a) {} 11090b57cec5SDimitry Andric template <class _InputIterator> 11100b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11110b57cec5SDimitry Andric multiset(_InputIterator __f, _InputIterator __l, 11120b57cec5SDimitry Andric const value_compare& __comp = value_compare()) 11130b57cec5SDimitry Andric : __tree_(__comp) 11140b57cec5SDimitry Andric { 11150b57cec5SDimitry Andric insert(__f, __l); 11160b57cec5SDimitry Andric } 11170b57cec5SDimitry Andric 11180b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 11190b57cec5SDimitry Andric template <class _InputIterator> 11200b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11210b57cec5SDimitry Andric multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) 11220b57cec5SDimitry Andric : multiset(__f, __l, key_compare(), __a) {} 11230b57cec5SDimitry Andric#endif 11240b57cec5SDimitry Andric 11250b57cec5SDimitry Andric template <class _InputIterator> 11260b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11270b57cec5SDimitry Andric multiset(_InputIterator __f, _InputIterator __l, 11280b57cec5SDimitry Andric const value_compare& __comp, const allocator_type& __a) 11290b57cec5SDimitry Andric : __tree_(__comp, __a) 11300b57cec5SDimitry Andric { 11310b57cec5SDimitry Andric insert(__f, __l); 11320b57cec5SDimitry Andric } 11330b57cec5SDimitry Andric 11340b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11350b57cec5SDimitry Andric multiset(const multiset& __s) 11360b57cec5SDimitry Andric : __tree_(__s.__tree_.value_comp(), 11370b57cec5SDimitry Andric __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) 11380b57cec5SDimitry Andric { 11390b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 11400b57cec5SDimitry Andric } 11410b57cec5SDimitry Andric 11420b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11430b57cec5SDimitry Andric multiset& operator=(const multiset& __s) 11440b57cec5SDimitry Andric { 11450b57cec5SDimitry Andric __tree_ = __s.__tree_; 11460b57cec5SDimitry Andric return *this; 11470b57cec5SDimitry Andric } 11480b57cec5SDimitry Andric 11490b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 11500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11510b57cec5SDimitry Andric multiset(multiset&& __s) 11520b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 11530b57cec5SDimitry Andric : __tree_(_VSTD::move(__s.__tree_)) {} 11540b57cec5SDimitry Andric 11550b57cec5SDimitry Andric multiset(multiset&& __s, const allocator_type& __a); 11560b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 11570b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11580b57cec5SDimitry Andric explicit multiset(const allocator_type& __a) 11590b57cec5SDimitry Andric : __tree_(__a) {} 11600b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11610b57cec5SDimitry Andric multiset(const multiset& __s, const allocator_type& __a) 11620b57cec5SDimitry Andric : __tree_(__s.__tree_.value_comp(), __a) 11630b57cec5SDimitry Andric { 11640b57cec5SDimitry Andric insert(__s.begin(), __s.end()); 11650b57cec5SDimitry Andric } 11660b57cec5SDimitry Andric 11670b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 11680b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11690b57cec5SDimitry Andric multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) 11700b57cec5SDimitry Andric : __tree_(__comp) 11710b57cec5SDimitry Andric { 11720b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11730b57cec5SDimitry Andric } 11740b57cec5SDimitry Andric 11750b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11760b57cec5SDimitry Andric multiset(initializer_list<value_type> __il, const value_compare& __comp, 11770b57cec5SDimitry Andric const allocator_type& __a) 11780b57cec5SDimitry Andric : __tree_(__comp, __a) 11790b57cec5SDimitry Andric { 11800b57cec5SDimitry Andric insert(__il.begin(), __il.end()); 11810b57cec5SDimitry Andric } 11820b57cec5SDimitry Andric 11830b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 11840b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11850b57cec5SDimitry Andric multiset(initializer_list<value_type> __il, const allocator_type& __a) 11860b57cec5SDimitry Andric : multiset(__il, key_compare(), __a) {} 11870b57cec5SDimitry Andric#endif 11880b57cec5SDimitry Andric 11890b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11900b57cec5SDimitry Andric multiset& operator=(initializer_list<value_type> __il) 11910b57cec5SDimitry Andric { 11920b57cec5SDimitry Andric __tree_.__assign_multi(__il.begin(), __il.end()); 11930b57cec5SDimitry Andric return *this; 11940b57cec5SDimitry Andric } 11950b57cec5SDimitry Andric 11960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 11970b57cec5SDimitry Andric multiset& operator=(multiset&& __s) 11980b57cec5SDimitry Andric _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) 11990b57cec5SDimitry Andric { 12000b57cec5SDimitry Andric __tree_ = _VSTD::move(__s.__tree_); 12010b57cec5SDimitry Andric return *this; 12020b57cec5SDimitry Andric } 12030b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12040b57cec5SDimitry Andric 12050b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12060b57cec5SDimitry Andric ~multiset() { 12070b57cec5SDimitry Andric static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); 12080b57cec5SDimitry Andric } 12090b57cec5SDimitry Andric 12100b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12110b57cec5SDimitry Andric iterator begin() _NOEXCEPT {return __tree_.begin();} 12120b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12130b57cec5SDimitry Andric const_iterator begin() const _NOEXCEPT {return __tree_.begin();} 12140b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12150b57cec5SDimitry Andric iterator end() _NOEXCEPT {return __tree_.end();} 12160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12170b57cec5SDimitry Andric const_iterator end() const _NOEXCEPT {return __tree_.end();} 12180b57cec5SDimitry Andric 12190b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12200b57cec5SDimitry Andric reverse_iterator rbegin() _NOEXCEPT 12210b57cec5SDimitry Andric {return reverse_iterator(end());} 12220b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12230b57cec5SDimitry Andric const_reverse_iterator rbegin() const _NOEXCEPT 12240b57cec5SDimitry Andric {return const_reverse_iterator(end());} 12250b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12260b57cec5SDimitry Andric reverse_iterator rend() _NOEXCEPT 12270b57cec5SDimitry Andric {return reverse_iterator(begin());} 12280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12290b57cec5SDimitry Andric const_reverse_iterator rend() const _NOEXCEPT 12300b57cec5SDimitry Andric {return const_reverse_iterator(begin());} 12310b57cec5SDimitry Andric 12320b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12330b57cec5SDimitry Andric const_iterator cbegin() const _NOEXCEPT {return begin();} 12340b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12350b57cec5SDimitry Andric const_iterator cend() const _NOEXCEPT {return end();} 12360b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12370b57cec5SDimitry Andric const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} 12380b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12390b57cec5SDimitry Andric const_reverse_iterator crend() const _NOEXCEPT {return rend();} 12400b57cec5SDimitry Andric 12410b57cec5SDimitry Andric _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 12420b57cec5SDimitry Andric bool empty() const _NOEXCEPT {return __tree_.size() == 0;} 12430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12440b57cec5SDimitry Andric size_type size() const _NOEXCEPT {return __tree_.size();} 12450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12460b57cec5SDimitry Andric size_type max_size() const _NOEXCEPT {return __tree_.max_size();} 12470b57cec5SDimitry Andric 12480b57cec5SDimitry Andric // modifiers: 12490b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 12500b57cec5SDimitry Andric template <class... _Args> 12510b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12520b57cec5SDimitry Andric iterator emplace(_Args&&... __args) 12530b57cec5SDimitry Andric {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} 12540b57cec5SDimitry Andric template <class... _Args> 12550b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12560b57cec5SDimitry Andric iterator emplace_hint(const_iterator __p, _Args&&... __args) 12570b57cec5SDimitry Andric {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);} 12580b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12590b57cec5SDimitry Andric 12600b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12610b57cec5SDimitry Andric iterator insert(const value_type& __v) 12620b57cec5SDimitry Andric {return __tree_.__insert_multi(__v);} 12630b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12640b57cec5SDimitry Andric iterator insert(const_iterator __p, const value_type& __v) 12650b57cec5SDimitry Andric {return __tree_.__insert_multi(__p, __v);} 12660b57cec5SDimitry Andric 12670b57cec5SDimitry Andric template <class _InputIterator> 12680b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12690b57cec5SDimitry Andric void insert(_InputIterator __f, _InputIterator __l) 12700b57cec5SDimitry Andric { 12710b57cec5SDimitry Andric for (const_iterator __e = cend(); __f != __l; ++__f) 12720b57cec5SDimitry Andric __tree_.__insert_multi(__e, *__f); 12730b57cec5SDimitry Andric } 12740b57cec5SDimitry Andric 12750b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 12760b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12770b57cec5SDimitry Andric iterator insert(value_type&& __v) 12780b57cec5SDimitry Andric {return __tree_.__insert_multi(_VSTD::move(__v));} 12790b57cec5SDimitry Andric 12800b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12810b57cec5SDimitry Andric iterator insert(const_iterator __p, value_type&& __v) 12820b57cec5SDimitry Andric {return __tree_.__insert_multi(__p, _VSTD::move(__v));} 12830b57cec5SDimitry Andric 12840b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12850b57cec5SDimitry Andric void insert(initializer_list<value_type> __il) 12860b57cec5SDimitry Andric {insert(__il.begin(), __il.end());} 12870b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 12880b57cec5SDimitry Andric 12890b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12900b57cec5SDimitry Andric iterator erase(const_iterator __p) {return __tree_.erase(__p);} 12910b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12920b57cec5SDimitry Andric size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} 12930b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12940b57cec5SDimitry Andric iterator erase(const_iterator __f, const_iterator __l) 12950b57cec5SDimitry Andric {return __tree_.erase(__f, __l);} 12960b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 12970b57cec5SDimitry Andric void clear() _NOEXCEPT {__tree_.clear();} 12980b57cec5SDimitry Andric 12990b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 14 13000b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13010b57cec5SDimitry Andric iterator insert(node_type&& __nh) 13020b57cec5SDimitry Andric { 13030b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 13040b57cec5SDimitry Andric "node_type with incompatible allocator passed to multiset::insert()"); 13050b57cec5SDimitry Andric return __tree_.template __node_handle_insert_multi<node_type>( 13060b57cec5SDimitry Andric _VSTD::move(__nh)); 13070b57cec5SDimitry Andric } 13080b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13090b57cec5SDimitry Andric iterator insert(const_iterator __hint, node_type&& __nh) 13100b57cec5SDimitry Andric { 13110b57cec5SDimitry Andric _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(), 13120b57cec5SDimitry Andric "node_type with incompatible allocator passed to multiset::insert()"); 13130b57cec5SDimitry Andric return __tree_.template __node_handle_insert_multi<node_type>( 13140b57cec5SDimitry Andric __hint, _VSTD::move(__nh)); 13150b57cec5SDimitry Andric } 13160b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13170b57cec5SDimitry Andric node_type extract(key_type const& __key) 13180b57cec5SDimitry Andric { 13190b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__key); 13200b57cec5SDimitry Andric } 13210b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13220b57cec5SDimitry Andric node_type extract(const_iterator __it) 13230b57cec5SDimitry Andric { 13240b57cec5SDimitry Andric return __tree_.template __node_handle_extract<node_type>(__it); 13250b57cec5SDimitry Andric } 13260b57cec5SDimitry Andric template <class _Compare2> 13270b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13280b57cec5SDimitry Andric void merge(multiset<key_type, _Compare2, allocator_type>& __source) 13290b57cec5SDimitry Andric { 13300b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13310b57cec5SDimitry Andric "merging container with incompatible allocator"); 13320b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 13330b57cec5SDimitry Andric } 13340b57cec5SDimitry Andric template <class _Compare2> 13350b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13360b57cec5SDimitry Andric void merge(multiset<key_type, _Compare2, allocator_type>&& __source) 13370b57cec5SDimitry Andric { 13380b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13390b57cec5SDimitry Andric "merging container with incompatible allocator"); 13400b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 13410b57cec5SDimitry Andric } 13420b57cec5SDimitry Andric template <class _Compare2> 13430b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13440b57cec5SDimitry Andric void merge(set<key_type, _Compare2, allocator_type>& __source) 13450b57cec5SDimitry Andric { 13460b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13470b57cec5SDimitry Andric "merging container with incompatible allocator"); 13480b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 13490b57cec5SDimitry Andric } 13500b57cec5SDimitry Andric template <class _Compare2> 13510b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13520b57cec5SDimitry Andric void merge(set<key_type, _Compare2, allocator_type>&& __source) 13530b57cec5SDimitry Andric { 13540b57cec5SDimitry Andric _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(), 13550b57cec5SDimitry Andric "merging container with incompatible allocator"); 13560b57cec5SDimitry Andric __tree_.__node_handle_merge_multi(__source.__tree_); 13570b57cec5SDimitry Andric } 13580b57cec5SDimitry Andric#endif 13590b57cec5SDimitry Andric 13600b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13610b57cec5SDimitry Andric void swap(multiset& __s) 13620b57cec5SDimitry Andric _NOEXCEPT_(__is_nothrow_swappable<__base>::value) 13630b57cec5SDimitry Andric {__tree_.swap(__s.__tree_);} 13640b57cec5SDimitry Andric 13650b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13660b57cec5SDimitry Andric allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} 13670b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13680b57cec5SDimitry Andric key_compare key_comp() const {return __tree_.value_comp();} 13690b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13700b57cec5SDimitry Andric value_compare value_comp() const {return __tree_.value_comp();} 13710b57cec5SDimitry Andric 13720b57cec5SDimitry Andric // set operations: 13730b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13740b57cec5SDimitry Andric iterator find(const key_type& __k) {return __tree_.find(__k);} 13750b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13760b57cec5SDimitry Andric const_iterator find(const key_type& __k) const {return __tree_.find(__k);} 13770b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 13780b57cec5SDimitry Andric template <typename _K2> 13790b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1380fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 13810b57cec5SDimitry Andric find(const _K2& __k) {return __tree_.find(__k);} 13820b57cec5SDimitry Andric template <typename _K2> 13830b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1384fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 13850b57cec5SDimitry Andric find(const _K2& __k) const {return __tree_.find(__k);} 13860b57cec5SDimitry Andric#endif 13870b57cec5SDimitry Andric 13880b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13890b57cec5SDimitry Andric size_type count(const key_type& __k) const 13900b57cec5SDimitry Andric {return __tree_.__count_multi(__k);} 13910b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 13920b57cec5SDimitry Andric template <typename _K2> 13930b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 13940b57cec5SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type 13950b57cec5SDimitry Andric count(const _K2& __k) const {return __tree_.__count_multi(__k);} 13960b57cec5SDimitry Andric#endif 13970b57cec5SDimitry Andric 13980b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 13990b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14000b57cec5SDimitry Andric bool contains(const key_type& __k) const {return find(__k) != end();} 1401fe6060f1SDimitry Andric template <typename _K2> 1402fe6060f1SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1403fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type 1404fe6060f1SDimitry Andric contains(const _K2& __k) const { return find(__k) != end(); } 14050b57cec5SDimitry Andric#endif // _LIBCPP_STD_VER > 17 14060b57cec5SDimitry Andric 14070b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14080b57cec5SDimitry Andric iterator lower_bound(const key_type& __k) 14090b57cec5SDimitry Andric {return __tree_.lower_bound(__k);} 14100b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14110b57cec5SDimitry Andric const_iterator lower_bound(const key_type& __k) const 14120b57cec5SDimitry Andric {return __tree_.lower_bound(__k);} 14130b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 14140b57cec5SDimitry Andric template <typename _K2> 14150b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1416fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 14170b57cec5SDimitry Andric lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} 14180b57cec5SDimitry Andric 14190b57cec5SDimitry Andric template <typename _K2> 14200b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1421fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 14220b57cec5SDimitry Andric lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);} 14230b57cec5SDimitry Andric#endif 14240b57cec5SDimitry Andric 14250b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14260b57cec5SDimitry Andric iterator upper_bound(const key_type& __k) 14270b57cec5SDimitry Andric {return __tree_.upper_bound(__k);} 14280b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14290b57cec5SDimitry Andric const_iterator upper_bound(const key_type& __k) const 14300b57cec5SDimitry Andric {return __tree_.upper_bound(__k);} 14310b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 14320b57cec5SDimitry Andric template <typename _K2> 14330b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1434fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type 14350b57cec5SDimitry Andric upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} 14360b57cec5SDimitry Andric template <typename _K2> 14370b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1438fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type 14390b57cec5SDimitry Andric upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);} 14400b57cec5SDimitry Andric#endif 14410b57cec5SDimitry Andric 14420b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14430b57cec5SDimitry Andric pair<iterator,iterator> equal_range(const key_type& __k) 14440b57cec5SDimitry Andric {return __tree_.__equal_range_multi(__k);} 14450b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 14460b57cec5SDimitry Andric pair<const_iterator,const_iterator> equal_range(const key_type& __k) const 14470b57cec5SDimitry Andric {return __tree_.__equal_range_multi(__k);} 14480b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 11 14490b57cec5SDimitry Andric template <typename _K2> 14500b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1451fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type 14520b57cec5SDimitry Andric equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} 14530b57cec5SDimitry Andric template <typename _K2> 14540b57cec5SDimitry Andric _LIBCPP_INLINE_VISIBILITY 1455fe6060f1SDimitry Andric typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type 14560b57cec5SDimitry Andric equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);} 14570b57cec5SDimitry Andric#endif 14580b57cec5SDimitry Andric}; 14590b57cec5SDimitry Andric 1460349cc55cSDimitry Andric#if _LIBCPP_STD_VER >= 17 14610b57cec5SDimitry Andrictemplate<class _InputIterator, 1462fe6060f1SDimitry Andric class _Compare = less<__iter_value_type<_InputIterator>>, 1463fe6060f1SDimitry Andric class _Allocator = allocator<__iter_value_type<_InputIterator>>, 1464349cc55cSDimitry Andric class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 1465349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 1466349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 14670b57cec5SDimitry Andricmultiset(_InputIterator, _InputIterator, _Compare = _Compare(), _Allocator = _Allocator()) 1468fe6060f1SDimitry Andric -> multiset<__iter_value_type<_InputIterator>, _Compare, _Allocator>; 14690b57cec5SDimitry Andric 14700b57cec5SDimitry Andrictemplate<class _Key, class _Compare = less<_Key>, 14710b57cec5SDimitry Andric class _Allocator = allocator<_Key>, 1472349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>, 1473349cc55cSDimitry Andric class = enable_if_t<!__is_allocator<_Compare>::value, void>> 14740b57cec5SDimitry Andricmultiset(initializer_list<_Key>, _Compare = _Compare(), _Allocator = _Allocator()) 14750b57cec5SDimitry Andric -> multiset<_Key, _Compare, _Allocator>; 14760b57cec5SDimitry Andric 14770b57cec5SDimitry Andrictemplate<class _InputIterator, class _Allocator, 1478349cc55cSDimitry Andric class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value, void>, 1479349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 14800b57cec5SDimitry Andricmultiset(_InputIterator, _InputIterator, _Allocator) 1481fe6060f1SDimitry Andric -> multiset<__iter_value_type<_InputIterator>, 1482fe6060f1SDimitry Andric less<__iter_value_type<_InputIterator>>, _Allocator>; 14830b57cec5SDimitry Andric 14840b57cec5SDimitry Andrictemplate<class _Key, class _Allocator, 1485349cc55cSDimitry Andric class = enable_if_t<__is_allocator<_Allocator>::value, void>> 14860b57cec5SDimitry Andricmultiset(initializer_list<_Key>, _Allocator) 14870b57cec5SDimitry Andric -> multiset<_Key, less<_Key>, _Allocator>; 14880b57cec5SDimitry Andric#endif 14890b57cec5SDimitry Andric 14900b57cec5SDimitry Andric#ifndef _LIBCPP_CXX03_LANG 14910b57cec5SDimitry Andric 14920b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 14930b57cec5SDimitry Andricmultiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) 14940b57cec5SDimitry Andric : __tree_(_VSTD::move(__s.__tree_), __a) 14950b57cec5SDimitry Andric{ 14960b57cec5SDimitry Andric if (__a != __s.get_allocator()) 14970b57cec5SDimitry Andric { 14980b57cec5SDimitry Andric const_iterator __e = cend(); 14990b57cec5SDimitry Andric while (!__s.empty()) 15000b57cec5SDimitry Andric insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); 15010b57cec5SDimitry Andric } 15020b57cec5SDimitry Andric} 15030b57cec5SDimitry Andric 15040b57cec5SDimitry Andric#endif // _LIBCPP_CXX03_LANG 15050b57cec5SDimitry Andric 15060b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15070b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15080b57cec5SDimitry Andricbool 15090b57cec5SDimitry Andricoperator==(const multiset<_Key, _Compare, _Allocator>& __x, 15100b57cec5SDimitry Andric const multiset<_Key, _Compare, _Allocator>& __y) 15110b57cec5SDimitry Andric{ 15120b57cec5SDimitry Andric return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 15130b57cec5SDimitry Andric} 15140b57cec5SDimitry Andric 15150b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15160b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15170b57cec5SDimitry Andricbool 15180b57cec5SDimitry Andricoperator< (const multiset<_Key, _Compare, _Allocator>& __x, 15190b57cec5SDimitry Andric const multiset<_Key, _Compare, _Allocator>& __y) 15200b57cec5SDimitry Andric{ 15210b57cec5SDimitry Andric return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 15220b57cec5SDimitry Andric} 15230b57cec5SDimitry Andric 15240b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15250b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15260b57cec5SDimitry Andricbool 15270b57cec5SDimitry Andricoperator!=(const multiset<_Key, _Compare, _Allocator>& __x, 15280b57cec5SDimitry Andric const multiset<_Key, _Compare, _Allocator>& __y) 15290b57cec5SDimitry Andric{ 15300b57cec5SDimitry Andric return !(__x == __y); 15310b57cec5SDimitry Andric} 15320b57cec5SDimitry Andric 15330b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15340b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15350b57cec5SDimitry Andricbool 15360b57cec5SDimitry Andricoperator> (const multiset<_Key, _Compare, _Allocator>& __x, 15370b57cec5SDimitry Andric const multiset<_Key, _Compare, _Allocator>& __y) 15380b57cec5SDimitry Andric{ 15390b57cec5SDimitry Andric return __y < __x; 15400b57cec5SDimitry Andric} 15410b57cec5SDimitry Andric 15420b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15430b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15440b57cec5SDimitry Andricbool 15450b57cec5SDimitry Andricoperator>=(const multiset<_Key, _Compare, _Allocator>& __x, 15460b57cec5SDimitry Andric const multiset<_Key, _Compare, _Allocator>& __y) 15470b57cec5SDimitry Andric{ 15480b57cec5SDimitry Andric return !(__x < __y); 15490b57cec5SDimitry Andric} 15500b57cec5SDimitry Andric 15510b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15520b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15530b57cec5SDimitry Andricbool 15540b57cec5SDimitry Andricoperator<=(const multiset<_Key, _Compare, _Allocator>& __x, 15550b57cec5SDimitry Andric const multiset<_Key, _Compare, _Allocator>& __y) 15560b57cec5SDimitry Andric{ 15570b57cec5SDimitry Andric return !(__y < __x); 15580b57cec5SDimitry Andric} 15590b57cec5SDimitry Andric 15600b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator> 15610b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15620b57cec5SDimitry Andricvoid 15630b57cec5SDimitry Andricswap(multiset<_Key, _Compare, _Allocator>& __x, 15640b57cec5SDimitry Andric multiset<_Key, _Compare, _Allocator>& __y) 15650b57cec5SDimitry Andric _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 15660b57cec5SDimitry Andric{ 15670b57cec5SDimitry Andric __x.swap(__y); 15680b57cec5SDimitry Andric} 15690b57cec5SDimitry Andric 15700b57cec5SDimitry Andric#if _LIBCPP_STD_VER > 17 15710b57cec5SDimitry Andrictemplate <class _Key, class _Compare, class _Allocator, class _Predicate> 15720b57cec5SDimitry Andricinline _LIBCPP_INLINE_VISIBILITY 15735ffd83dbSDimitry Andric typename multiset<_Key, _Compare, _Allocator>::size_type 15745ffd83dbSDimitry Andric erase_if(multiset<_Key, _Compare, _Allocator>& __c, _Predicate __pred) { 1575fe6060f1SDimitry Andric return _VSTD::__libcpp_erase_if_container(__c, __pred); 15765ffd83dbSDimitry Andric} 15770b57cec5SDimitry Andric#endif 15780b57cec5SDimitry Andric 15790b57cec5SDimitry Andric_LIBCPP_END_NAMESPACE_STD 15800b57cec5SDimitry Andric 15810b57cec5SDimitry Andric#endif // _LIBCPP_SET 1582