Cider Isn't Darwin Emulation, Really
Something went wrong. Try again.
45 kB · 1218 lines
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219// -*- C++ -*-//===---------------------------- set -------------------------------------===////// The LLVM Compiler Infrastructure//// This file is dual licensed under the MIT and the University of Illinois Open// Source Licenses. See LICENSE.TXT for details.////===----------------------------------------------------------------------===//#ifndef _LIBCPP_SET#define _LIBCPP_SET/* set synopsisnamespace std{template <class Key, class Compare = less<Key>, class Allocator = allocator<Key>>class set{public: // types: typedef Key key_type; typedef key_type value_type; typedef Compare key_compare; typedef key_compare value_compare; typedef Allocator allocator_type; typedef typename allocator_type::reference reference; typedef typename allocator_type::const_reference const_reference; typedef typename allocator_type::size_type size_type; typedef typename allocator_type::difference_type difference_type; typedef typename allocator_type::pointer pointer; typedef typename allocator_type::const_pointer const_pointer; typedef implementation-defined iterator; typedef implementation-defined const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; // construct/copy/destroy: set() noexcept( is_nothrow_default_constructible<allocator_type>::value && is_nothrow_default_constructible<key_compare>::value && is_nothrow_copy_constructible<key_compare>::value); explicit set(const value_compare& comp); set(const value_compare& comp, const allocator_type& a); template <class InputIterator> set(InputIterator first, InputIterator last, const value_compare& comp = value_compare()); template <class InputIterator> set(InputIterator first, InputIterator last, const value_compare& comp, const allocator_type& a); set(const set& s); set(set&& s) noexcept( is_nothrow_move_constructible<allocator_type>::value && is_nothrow_move_constructible<key_compare>::value); explicit set(const allocator_type& a); set(const set& s, const allocator_type& a); set(set&& s, const allocator_type& a); set(initializer_list<value_type> il, const value_compare& comp = value_compare()); set(initializer_list<value_type> il, const value_compare& comp, const allocator_type& a); template <class InputIterator> set(InputIterator first, InputIterator last, const allocator_type& a) : set(first, last, Compare(), a) {} // C++14 set(initializer_list<value_type> il, const allocator_type& a) : set(il, Compare(), a) {} // C++14 ~set(); set& operator=(const set& s); set& operator=(set&& s) noexcept( allocator_type::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<allocator_type>::value && is_nothrow_move_assignable<key_compare>::value); set& operator=(initializer_list<value_type> il); // iterators: iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; // capacity: bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; // modifiers: template <class... Args> pair<iterator, bool> emplace(Args&&... args); template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args); pair<iterator,bool> insert(const value_type& v); pair<iterator,bool> insert(value_type&& v); iterator insert(const_iterator position, const value_type& v); iterator insert(const_iterator position, value_type&& v); template <class InputIterator> void insert(InputIterator first, InputIterator last); void insert(initializer_list<value_type> il); iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); iterator erase(const_iterator first, const_iterator last); void clear() noexcept; void swap(set& s) noexcept( __is_nothrow_swappable<key_compare>::value && (!allocator_type::propagate_on_container_swap::value || __is_nothrow_swappable<allocator_type>::value)); // observers: allocator_type get_allocator() const noexcept; key_compare key_comp() const; value_compare value_comp() const; // set operations: iterator find(const key_type& k); const_iterator find(const key_type& k) const; template<typename K> iterator find(const K& x); template<typename K> const_iterator find(const K& x) const; // C++14 template<typename K> size_type count(const K& x) const; // C++14 size_type count(const key_type& k) const; iterator lower_bound(const key_type& k); const_iterator lower_bound(const key_type& k) const; template<typename K> iterator lower_bound(const K& x); // C++14 template<typename K> const_iterator lower_bound(const K& x) const; // C++14 iterator upper_bound(const key_type& k); const_iterator upper_bound(const key_type& k) const; template<typename K> iterator upper_bound(const K& x); // C++14 template<typename K> const_iterator upper_bound(const K& x) const; // C++14 pair<iterator,iterator> equal_range(const key_type& k); pair<const_iterator,const_iterator> equal_range(const key_type& k) const; template<typename K> pair<iterator,iterator> equal_range(const K& x); // C++14 template<typename K> pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14};template <class Key, class Compare, class Allocator>booloperator==(const set<Key, Compare, Allocator>& x, const set<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator< (const set<Key, Compare, Allocator>& x, const set<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator!=(const set<Key, Compare, Allocator>& x, const set<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator> (const set<Key, Compare, Allocator>& x, const set<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator>=(const set<Key, Compare, Allocator>& x, const set<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator<=(const set<Key, Compare, Allocator>& x, const set<Key, Compare, Allocator>& y);// specialized algorithms:template <class Key, class Compare, class Allocator>voidswap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& y) noexcept(noexcept(x.swap(y)));template <class Key, class Compare = less<Key>, class Allocator = allocator<Key>>class multiset{public: // types: typedef Key key_type; typedef key_type value_type; typedef Compare key_compare; typedef key_compare value_compare; typedef Allocator allocator_type; typedef typename allocator_type::reference reference; typedef typename allocator_type::const_reference const_reference; typedef typename allocator_type::size_type size_type; typedef typename allocator_type::difference_type difference_type; typedef typename allocator_type::pointer pointer; typedef typename allocator_type::const_pointer const_pointer; typedef implementation-defined iterator; typedef implementation-defined const_iterator; typedef std::reverse_iterator<iterator> reverse_iterator; typedef std::reverse_iterator<const_iterator> const_reverse_iterator; // construct/copy/destroy: multiset() noexcept( is_nothrow_default_constructible<allocator_type>::value && is_nothrow_default_constructible<key_compare>::value && is_nothrow_copy_constructible<key_compare>::value); explicit multiset(const value_compare& comp); multiset(const value_compare& comp, const allocator_type& a); template <class InputIterator> multiset(InputIterator first, InputIterator last, const value_compare& comp = value_compare()); template <class InputIterator> multiset(InputIterator first, InputIterator last, const value_compare& comp, const allocator_type& a); multiset(const multiset& s); multiset(multiset&& s) noexcept( is_nothrow_move_constructible<allocator_type>::value && is_nothrow_move_constructible<key_compare>::value); explicit multiset(const allocator_type& a); multiset(const multiset& s, const allocator_type& a); multiset(multiset&& s, const allocator_type& a); multiset(initializer_list<value_type> il, const value_compare& comp = value_compare()); multiset(initializer_list<value_type> il, const value_compare& comp, const allocator_type& a); template <class InputIterator> multiset(InputIterator first, InputIterator last, const allocator_type& a) : set(first, last, Compare(), a) {} // C++14 multiset(initializer_list<value_type> il, const allocator_type& a) : set(il, Compare(), a) {} // C++14 ~multiset(); multiset& operator=(const multiset& s); multiset& operator=(multiset&& s) noexcept( allocator_type::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<allocator_type>::value && is_nothrow_move_assignable<key_compare>::value); multiset& operator=(initializer_list<value_type> il); // iterators: iterator begin() noexcept; const_iterator begin() const noexcept; iterator end() noexcept; const_iterator end() const noexcept; reverse_iterator rbegin() noexcept; const_reverse_iterator rbegin() const noexcept; reverse_iterator rend() noexcept; const_reverse_iterator rend() const noexcept; const_iterator cbegin() const noexcept; const_iterator cend() const noexcept; const_reverse_iterator crbegin() const noexcept; const_reverse_iterator crend() const noexcept; // capacity: bool empty() const noexcept; size_type size() const noexcept; size_type max_size() const noexcept; // modifiers: template <class... Args> iterator emplace(Args&&... args); template <class... Args> iterator emplace_hint(const_iterator position, Args&&... args); iterator insert(const value_type& v); iterator insert(value_type&& v); iterator insert(const_iterator position, const value_type& v); iterator insert(const_iterator position, value_type&& v); template <class InputIterator> void insert(InputIterator first, InputIterator last); void insert(initializer_list<value_type> il); iterator erase(const_iterator position); iterator erase(iterator position); // C++14 size_type erase(const key_type& k); iterator erase(const_iterator first, const_iterator last); void clear() noexcept; void swap(multiset& s) noexcept( __is_nothrow_swappable<key_compare>::value && (!allocator_type::propagate_on_container_swap::value || __is_nothrow_swappable<allocator_type>::value)); // observers: allocator_type get_allocator() const noexcept; key_compare key_comp() const; value_compare value_comp() const; // set operations: iterator find(const key_type& k); const_iterator find(const key_type& k) const; template<typename K> iterator find(const K& x); template<typename K> const_iterator find(const K& x) const; // C++14 size_type count(const key_type& k) const; iterator lower_bound(const key_type& k); const_iterator lower_bound(const key_type& k) const; template<typename K> iterator lower_bound(const K& x); // C++14 template<typename K> const_iterator lower_bound(const K& x) const; // C++14 iterator upper_bound(const key_type& k); const_iterator upper_bound(const key_type& k) const; template<typename K> iterator upper_bound(const K& x); // C++14 template<typename K> const_iterator upper_bound(const K& x) const; // C++14 pair<iterator,iterator> equal_range(const key_type& k); pair<const_iterator,const_iterator> equal_range(const key_type& k) const; template<typename K> pair<iterator,iterator> equal_range(const K& x); // C++14 template<typename K> pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14};template <class Key, class Compare, class Allocator>booloperator==(const multiset<Key, Compare, Allocator>& x, const multiset<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator< (const multiset<Key, Compare, Allocator>& x, const multiset<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator!=(const multiset<Key, Compare, Allocator>& x, const multiset<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator> (const multiset<Key, Compare, Allocator>& x, const multiset<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator>=(const multiset<Key, Compare, Allocator>& x, const multiset<Key, Compare, Allocator>& y);template <class Key, class Compare, class Allocator>booloperator<=(const multiset<Key, Compare, Allocator>& x, const multiset<Key, Compare, Allocator>& y);// specialized algorithms:template <class Key, class Compare, class Allocator>voidswap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y) noexcept(noexcept(x.swap(y)));} // std*/#include <__config>#include <__tree>#include <functional>#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)#pragma GCC system_header#endif_LIBCPP_BEGIN_NAMESPACE_STDtemplate <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >class _LIBCPP_TEMPLATE_VIS set{public: // types: typedef _Key key_type; typedef key_type value_type; typedef _Compare key_compare; typedef key_compare value_compare; typedef _Allocator allocator_type; typedef value_type& reference; typedef const value_type& const_reference; static_assert((is_same<typename allocator_type::value_type, value_type>::value), "Allocator::value_type must be same type as value_type");private: typedef __tree<value_type, value_compare, allocator_type> __base; typedef allocator_traits<allocator_type> __alloc_traits; typedef typename __base::__node_holder __node_holder; __base __tree_;public: typedef typename __base::pointer pointer; typedef typename __base::const_pointer const_pointer; typedef typename __base::size_type size_type; typedef typename __base::difference_type difference_type; typedef typename __base::const_iterator iterator; typedef typename __base::const_iterator const_iterator; typedef _VSTD::reverse_iterator<iterator> reverse_iterator; typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; _LIBCPP_INLINE_VISIBILITY set() _NOEXCEPT_( is_nothrow_default_constructible<allocator_type>::value && is_nothrow_default_constructible<key_compare>::value && is_nothrow_copy_constructible<key_compare>::value) : __tree_(value_compare()) {} _LIBCPP_INLINE_VISIBILITY explicit set(const value_compare& __comp) _NOEXCEPT_( is_nothrow_default_constructible<allocator_type>::value && is_nothrow_copy_constructible<key_compare>::value) : __tree_(__comp) {} _LIBCPP_INLINE_VISIBILITY explicit set(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {} template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY set(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare()) : __tree_(__comp) { insert(__f, __l); } template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY set(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) { insert(__f, __l); }#if _LIBCPP_STD_VER > 11 template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY set(_InputIterator __f, _InputIterator __l, const allocator_type& __a) : set(__f, __l, key_compare(), __a) {}#endif _LIBCPP_INLINE_VISIBILITY set(const set& __s) : __tree_(__s.__tree_) { insert(__s.begin(), __s.end()); } _LIBCPP_INLINE_VISIBILITY set& operator=(const set& __s) { __tree_ = __s.__tree_; return *this; }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY set(set&& __s) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) : __tree_(_VSTD::move(__s.__tree_)) {}#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY explicit set(const allocator_type& __a) : __tree_(__a) {} _LIBCPP_INLINE_VISIBILITY set(const set& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) { insert(__s.begin(), __s.end()); }#ifndef _LIBCPP_CXX03_LANG set(set&& __s, const allocator_type& __a); _LIBCPP_INLINE_VISIBILITY set(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) : __tree_(__comp) { insert(__il.begin(), __il.end()); } _LIBCPP_INLINE_VISIBILITY set(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) { insert(__il.begin(), __il.end()); }#if _LIBCPP_STD_VER > 11 _LIBCPP_INLINE_VISIBILITY set(initializer_list<value_type> __il, const allocator_type& __a) : set(__il, key_compare(), __a) {}#endif _LIBCPP_INLINE_VISIBILITY set& operator=(initializer_list<value_type> __il) { __tree_.__assign_unique(__il.begin(), __il.end()); return *this; } _LIBCPP_INLINE_VISIBILITY set& operator=(set&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) { __tree_ = _VSTD::move(__s.__tree_); return *this; }#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __tree_.begin();} _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __tree_.begin();} _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __tree_.end();} _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __tree_.end();} _LIBCPP_INLINE_VISIBILITY reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rbegin() const _NOEXCEPT {return const_reverse_iterator(end());} _LIBCPP_INLINE_VISIBILITY reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rend() const _NOEXCEPT {return const_reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY const_iterator cbegin() const _NOEXCEPT {return begin();} _LIBCPP_INLINE_VISIBILITY const_iterator cend() const _NOEXCEPT {return end();} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crend() const _NOEXCEPT {return rend();} _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return __tree_.size() == 0;} _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT {return __tree_.size();} _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT {return __tree_.max_size();} // modifiers:#ifndef _LIBCPP_CXX03_LANG template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> emplace(_Args&&... __args) {return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);} template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator emplace_hint(const_iterator __p, _Args&&... __args) {return __tree_.__emplace_hint_unique(__p, _VSTD::forward<_Args>(__args)...);}#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair<iterator,bool> insert(const value_type& __v) {return __tree_.__insert_unique(__v);} _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, const value_type& __v) {return __tree_.__insert_unique(__p, __v);} template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __f, _InputIterator __l) { for (const_iterator __e = cend(); __f != __l; ++__f) __tree_.__insert_unique(__e, *__f); }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY pair<iterator,bool> insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, value_type&& __v) {return __tree_.__insert_unique(__p, _VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY void insert(initializer_list<value_type> __il) {insert(__il.begin(), __il.end());}#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __tree_.erase(__p);} _LIBCPP_INLINE_VISIBILITY size_type erase(const key_type& __k) {return __tree_.__erase_unique(__k);} _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __f, const_iterator __l) {return __tree_.erase(__f, __l);} _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__tree_.clear();} _LIBCPP_INLINE_VISIBILITY void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) {__tree_.swap(__s.__tree_);} _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} _LIBCPP_INLINE_VISIBILITY key_compare key_comp() const {return __tree_.value_comp();} _LIBCPP_INLINE_VISIBILITY value_compare value_comp() const {return __tree_.value_comp();} // set operations: _LIBCPP_INLINE_VISIBILITY iterator find(const key_type& __k) {return __tree_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __tree_.find(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type find(const _K2& __k) {return __tree_.find(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type find(const _K2& __k) const {return __tree_.find(__k);}#endif _LIBCPP_INLINE_VISIBILITY size_type count(const key_type& __k) const {return __tree_.__count_unique(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type count(const _K2& __k) const {return __tree_.__count_unique(__k);}#endif _LIBCPP_INLINE_VISIBILITY iterator lower_bound(const key_type& __k) {return __tree_.lower_bound(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator lower_bound(const key_type& __k) const {return __tree_.lower_bound(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}#endif _LIBCPP_INLINE_VISIBILITY iterator upper_bound(const key_type& __k) {return __tree_.upper_bound(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator upper_bound(const key_type& __k) const {return __tree_.upper_bound(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}#endif _LIBCPP_INLINE_VISIBILITY pair<iterator,iterator> equal_range(const key_type& __k) {return __tree_.__equal_range_unique(__k);} _LIBCPP_INLINE_VISIBILITY pair<const_iterator,const_iterator> equal_range(const key_type& __k) const {return __tree_.__equal_range_unique(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}#endif};#ifndef _LIBCPP_CXX03_LANGtemplate <class _Key, class _Compare, class _Allocator>set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a) : __tree_(_VSTD::move(__s.__tree_), __a){ if (__a != __s.get_allocator()) { const_iterator __e = cend(); while (!__s.empty()) insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); }}#endif // _LIBCPP_CXX03_LANGtemplate <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator==(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y){ return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator< (const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y){ return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator!=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y){ return !(__x == __y);}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator> (const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y){ return __y < __x;}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator>=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y){ return !(__x < __y);}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator<=(const set<_Key, _Compare, _Allocator>& __x, const set<_Key, _Compare, _Allocator>& __y){ return !(__y < __x);}// specialized algorithms:template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYvoidswap(set<_Key, _Compare, _Allocator>& __x, set<_Key, _Compare, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))){ __x.swap(__y);}template <class _Key, class _Compare = less<_Key>, class _Allocator = allocator<_Key> >class _LIBCPP_TEMPLATE_VIS multiset{public: // types: typedef _Key key_type; typedef key_type value_type; typedef _Compare key_compare; typedef key_compare value_compare; typedef _Allocator allocator_type; typedef value_type& reference; typedef const value_type& const_reference; static_assert((is_same<typename allocator_type::value_type, value_type>::value), "Allocator::value_type must be same type as value_type");private: typedef __tree<value_type, value_compare, allocator_type> __base; typedef allocator_traits<allocator_type> __alloc_traits; typedef typename __base::__node_holder __node_holder; __base __tree_;public: typedef typename __base::pointer pointer; typedef typename __base::const_pointer const_pointer; typedef typename __base::size_type size_type; typedef typename __base::difference_type difference_type; typedef typename __base::const_iterator iterator; typedef typename __base::const_iterator const_iterator; typedef _VSTD::reverse_iterator<iterator> reverse_iterator; typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; // construct/copy/destroy: _LIBCPP_INLINE_VISIBILITY multiset() _NOEXCEPT_( is_nothrow_default_constructible<allocator_type>::value && is_nothrow_default_constructible<key_compare>::value && is_nothrow_copy_constructible<key_compare>::value) : __tree_(value_compare()) {} _LIBCPP_INLINE_VISIBILITY explicit multiset(const value_compare& __comp) _NOEXCEPT_( is_nothrow_default_constructible<allocator_type>::value && is_nothrow_copy_constructible<key_compare>::value) : __tree_(__comp) {} _LIBCPP_INLINE_VISIBILITY explicit multiset(const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) {} template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp = value_compare()) : __tree_(__comp) { insert(__f, __l); }#if _LIBCPP_STD_VER > 11 template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY multiset(_InputIterator __f, _InputIterator __l, const allocator_type& __a) : multiset(__f, __l, key_compare(), __a) {}#endif template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY multiset(_InputIterator __f, _InputIterator __l, const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) { insert(__f, __l); } _LIBCPP_INLINE_VISIBILITY multiset(const multiset& __s) : __tree_(__s.__tree_.value_comp(), __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc())) { insert(__s.begin(), __s.end()); } _LIBCPP_INLINE_VISIBILITY multiset& operator=(const multiset& __s) { __tree_ = __s.__tree_; return *this; }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY multiset(multiset&& __s) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) : __tree_(_VSTD::move(__s.__tree_)) {} multiset(multiset&& __s, const allocator_type& __a);#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY explicit multiset(const allocator_type& __a) : __tree_(__a) {} _LIBCPP_INLINE_VISIBILITY multiset(const multiset& __s, const allocator_type& __a) : __tree_(__s.__tree_.value_comp(), __a) { insert(__s.begin(), __s.end()); }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare()) : __tree_(__comp) { insert(__il.begin(), __il.end()); } _LIBCPP_INLINE_VISIBILITY multiset(initializer_list<value_type> __il, const value_compare& __comp, const allocator_type& __a) : __tree_(__comp, __a) { insert(__il.begin(), __il.end()); }#if _LIBCPP_STD_VER > 11 _LIBCPP_INLINE_VISIBILITY multiset(initializer_list<value_type> __il, const allocator_type& __a) : multiset(__il, key_compare(), __a) {}#endif _LIBCPP_INLINE_VISIBILITY multiset& operator=(initializer_list<value_type> __il) { __tree_.__assign_multi(__il.begin(), __il.end()); return *this; } _LIBCPP_INLINE_VISIBILITY multiset& operator=(multiset&& __s) _NOEXCEPT_(is_nothrow_move_assignable<__base>::value) { __tree_ = _VSTD::move(__s.__tree_); return *this; }#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return __tree_.begin();} _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return __tree_.begin();} _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return __tree_.end();} _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return __tree_.end();} _LIBCPP_INLINE_VISIBILITY reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rbegin() const _NOEXCEPT {return const_reverse_iterator(end());} _LIBCPP_INLINE_VISIBILITY reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rend() const _NOEXCEPT {return const_reverse_iterator(begin());} _LIBCPP_INLINE_VISIBILITY const_iterator cbegin() const _NOEXCEPT {return begin();} _LIBCPP_INLINE_VISIBILITY const_iterator cend() const _NOEXCEPT {return end();} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();} _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crend() const _NOEXCEPT {return rend();} _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return __tree_.size() == 0;} _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT {return __tree_.size();} _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT {return __tree_.max_size();} // modifiers:#ifndef _LIBCPP_CXX03_LANG template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator emplace(_Args&&... __args) {return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);} template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator emplace_hint(const_iterator __p, _Args&&... __args) {return __tree_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);} _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, const value_type& __v) {return __tree_.__insert_multi(__p, __v);} template <class _InputIterator> _LIBCPP_INLINE_VISIBILITY void insert(_InputIterator __f, _InputIterator __l) { for (const_iterator __e = cend(); __f != __l; ++__f) __tree_.__insert_multi(__e, *__f); }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator insert(value_type&& __v) {return __tree_.__insert_multi(_VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY iterator insert(const_iterator __p, value_type&& __v) {return __tree_.__insert_multi(__p, _VSTD::move(__v));} _LIBCPP_INLINE_VISIBILITY void insert(initializer_list<value_type> __il) {insert(__il.begin(), __il.end());}#endif // _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __p) {return __tree_.erase(__p);} _LIBCPP_INLINE_VISIBILITY size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);} _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __f, const_iterator __l) {return __tree_.erase(__f, __l);} _LIBCPP_INLINE_VISIBILITY void clear() _NOEXCEPT {__tree_.clear();} _LIBCPP_INLINE_VISIBILITY void swap(multiset& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value) {__tree_.swap(__s.__tree_);} _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();} _LIBCPP_INLINE_VISIBILITY key_compare key_comp() const {return __tree_.value_comp();} _LIBCPP_INLINE_VISIBILITY value_compare value_comp() const {return __tree_.value_comp();} // set operations: _LIBCPP_INLINE_VISIBILITY iterator find(const key_type& __k) {return __tree_.find(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator find(const key_type& __k) const {return __tree_.find(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type find(const _K2& __k) {return __tree_.find(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type find(const _K2& __k) const {return __tree_.find(__k);}#endif _LIBCPP_INLINE_VISIBILITY size_type count(const key_type& __k) const {return __tree_.__count_multi(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type count(const _K2& __k) {return __tree_.__count_multi(__k);}#endif _LIBCPP_INLINE_VISIBILITY iterator lower_bound(const key_type& __k) {return __tree_.lower_bound(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator lower_bound(const key_type& __k) const {return __tree_.lower_bound(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}#endif _LIBCPP_INLINE_VISIBILITY iterator upper_bound(const key_type& __k) {return __tree_.upper_bound(__k);} _LIBCPP_INLINE_VISIBILITY const_iterator upper_bound(const key_type& __k) const {return __tree_.upper_bound(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,iterator>::type upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,const_iterator>::type upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}#endif _LIBCPP_INLINE_VISIBILITY pair<iterator,iterator> equal_range(const key_type& __k) {return __tree_.__equal_range_multi(__k);} _LIBCPP_INLINE_VISIBILITY pair<const_iterator,const_iterator> equal_range(const key_type& __k) const {return __tree_.__equal_range_multi(__k);}#if _LIBCPP_STD_VER > 11 template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);} template <typename _K2> _LIBCPP_INLINE_VISIBILITY typename _VSTD::enable_if<_VSTD::__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}#endif};#ifndef _LIBCPP_CXX03_LANGtemplate <class _Key, class _Compare, class _Allocator>multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a) : __tree_(_VSTD::move(__s.__tree_), __a){ if (__a != __s.get_allocator()) { const_iterator __e = cend(); while (!__s.empty()) insert(__e, _VSTD::move(__s.__tree_.remove(__s.begin())->__value_)); }}#endif // _LIBCPP_CXX03_LANGtemplate <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator==(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y){ return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator< (const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y){ return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator!=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y){ return !(__x == __y);}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator> (const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y){ return __y < __x;}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator>=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y){ return !(__x < __y);}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYbooloperator<=(const multiset<_Key, _Compare, _Allocator>& __x, const multiset<_Key, _Compare, _Allocator>& __y){ return !(__y < __x);}template <class _Key, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYvoidswap(multiset<_Key, _Compare, _Allocator>& __x, multiset<_Key, _Compare, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))){ __x.swap(__y);}_LIBCPP_END_NAMESPACE_STD#endif // _LIBCPP_SET