xref: /freebsd/contrib/llvm-project/libcxx/include/set (revision 81ad626541db97eb356e2c1d4a20eb2a26a766ab)
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