libcxx initial import
git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@103490 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/set b/include/set
new file mode 100644
index 0000000..38e5ac1
--- /dev/null
+++ b/include/set
@@ -0,0 +1,841 @@
+// -*- C++ -*-
+//===---------------------------- set -------------------------------------===//
+//
+// ÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊÊThe LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_SET
+#define _LIBCPP_SET
+
+/*
+
+ set synopsis
+
+namespace 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:
+ explicit set(const value_compare& comp = value_compare());
+ 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);
+ 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);
+ ~set();
+
+ set& operator=(const set& s);
+ set& operator=(set&& s);
+ set& operator=(initializer_list<value_type> il);
+
+ // iterators:
+ iterator begin();
+ const_iterator begin() const;
+ iterator end();
+ const_iterator end() const;
+
+ reverse_iterator rbegin();
+ const_reverse_iterator rbegin() const;
+ reverse_iterator rend();
+ const_reverse_iterator rend() const;
+
+ const_iterator cbegin() const;
+ const_iterator cend() const;
+ const_reverse_iterator crbegin() const;
+ const_reverse_iterator crend() const;
+
+ // capacity:
+ bool empty() const;
+ size_type size() const;
+ size_type max_size() const;
+
+ // 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);
+ size_type erase(const key_type& k);
+ iterator erase(const_iterator first, const_iterator last);
+ void clear();
+
+ void swap(set& s);
+
+ // observers:
+ allocator_type get_allocator() const;
+ 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;
+ size_type count(const key_type& k) const;
+ iterator lower_bound(const key_type& k);
+ const_iterator lower_bound(const key_type& k) const;
+ iterator upper_bound(const key_type& k);
+ const_iterator upper_bound(const key_type& k) const;
+ pair<iterator,iterator> equal_range(const key_type& k);
+ pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
+};
+
+template <class Key, class Compare, class Allocator>
+bool
+operator==(const set<Key, Compare, Allocator>& x,
+ const set<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator< (const set<Key, Compare, Allocator>& x,
+ const set<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator!=(const set<Key, Compare, Allocator>& x,
+ const set<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator> (const set<Key, Compare, Allocator>& x,
+ const set<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator>=(const set<Key, Compare, Allocator>& x,
+ const set<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator<=(const set<Key, Compare, Allocator>& x,
+ const set<Key, Compare, Allocator>& y);
+
+// specialized algorithms:
+template <class Key, class Compare, class Allocator>
+void
+swap(set<Key, Compare, Allocator>& x, set<Key, Compare, Allocator>& 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:
+ explicit multiset(const value_compare& comp = value_compare());
+ 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);
+ 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);
+ ~multiset();
+
+ multiset& operator=(const multiset& s);
+ multiset& operator=(multiset&& s);
+ multiset& operator=(initializer_list<value_type> il);
+
+ // iterators:
+ iterator begin();
+ const_iterator begin() const;
+ iterator end();
+ const_iterator end() const;
+
+ reverse_iterator rbegin();
+ const_reverse_iterator rbegin() const;
+ reverse_iterator rend();
+ const_reverse_iterator rend() const;
+
+ const_iterator cbegin() const;
+ const_iterator cend() const;
+ const_reverse_iterator crbegin() const;
+ const_reverse_iterator crend() const;
+
+ // capacity:
+ bool empty() const;
+ size_type size() const;
+ size_type max_size() const;
+
+ // 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);
+ size_type erase(const key_type& k);
+ iterator erase(const_iterator first, const_iterator last);
+ void clear();
+
+ void swap(multiset& s);
+
+ // observers:
+ allocator_type get_allocator() const;
+ 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;
+ size_type count(const key_type& k) const;
+ iterator lower_bound(const key_type& k);
+ const_iterator lower_bound(const key_type& k) const;
+ iterator upper_bound(const key_type& k);
+ const_iterator upper_bound(const key_type& k) const;
+ pair<iterator,iterator> equal_range(const key_type& k);
+ pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
+};
+
+template <class Key, class Compare, class Allocator>
+bool
+operator==(const multiset<Key, Compare, Allocator>& x,
+ const multiset<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator< (const multiset<Key, Compare, Allocator>& x,
+ const multiset<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator!=(const multiset<Key, Compare, Allocator>& x,
+ const multiset<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator> (const multiset<Key, Compare, Allocator>& x,
+ const multiset<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator>=(const multiset<Key, Compare, Allocator>& x,
+ const multiset<Key, Compare, Allocator>& y);
+
+template <class Key, class Compare, class Allocator>
+bool
+operator<=(const multiset<Key, Compare, Allocator>& x,
+ const multiset<Key, Compare, Allocator>& y);
+
+// specialized algorithms:
+template <class Key, class Compare, class Allocator>
+void
+swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y);
+
+} // std
+
+*/
+
+#include <__config>
+#include <__tree>
+#include <functional>
+
+#pragma GCC system_header
+
+_LIBCPP_BEGIN_NAMESPACE_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 value_type& reference;
+ typedef const value_type& const_reference;
+
+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 _STD::reverse_iterator<iterator> reverse_iterator;
+ typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ explicit set(const value_compare& __comp = value_compare())
+ : __tree_(__comp) {}
+ set(const value_compare& __comp, const allocator_type& __a)
+ : __tree_(__comp, __a) {}
+ template <class _InputIterator>
+ set(_InputIterator __f, _InputIterator __l,
+ const value_compare& __comp = value_compare())
+ : __tree_(__comp)
+ {
+ insert(__f, __l);
+ }
+
+ template <class _InputIterator>
+ set(_InputIterator __f, _InputIterator __l, const value_compare& __comp,
+ const allocator_type& __a)
+ : __tree_(__comp, __a)
+ {
+ insert(__f, __l);
+ }
+
+ set(const set& __s)
+ : __tree_(__s.__tree_)
+ {
+ insert(__s.begin(), __s.end());
+ }
+
+#ifdef _LIBCPP_MOVE
+ set(set&& __s)
+ : __tree_(_STD::move(__s.__tree_)) {}
+#endif
+
+ explicit set(const allocator_type& __a)
+ : __tree_(__a) {}
+
+ set(const set& __s, const allocator_type& __a)
+ : __tree_(__s.__tree_.value_comp(), __a)
+ {
+ insert(__s.begin(), __s.end());
+ }
+
+#ifdef _LIBCPP_MOVE
+ set(set&& __s, const allocator_type& __a);
+#endif
+
+ set(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
+ : __tree_(__comp)
+ {
+ insert(__il.begin(), __il.end());
+ }
+
+ set(initializer_list<value_type> __il, const value_compare& __comp,
+ const allocator_type& __a)
+ : __tree_(__comp, __a)
+ {
+ insert(__il.begin(), __il.end());
+ }
+
+ set& operator=(initializer_list<value_type> __il)
+ {
+ __tree_.__assign_unique(__il.begin(), __il.end());
+ return *this;
+ }
+
+#ifdef _LIBCPP_MOVE
+ set& operator=(set&& __s)
+ {
+ __tree_ = _STD::move(__s.__tree_);
+ return *this;
+ }
+#endif
+
+ iterator begin() {return __tree_.begin();}
+ const_iterator begin() const {return __tree_.begin();}
+ iterator end() {return __tree_.end();}
+ const_iterator end() const {return __tree_.end();}
+
+ reverse_iterator rbegin() {return reverse_iterator(end());}
+ const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
+ reverse_iterator rend() {return reverse_iterator(begin());}
+ const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
+
+ const_iterator cbegin() const {return begin();}
+ const_iterator cend() const {return end();}
+ const_reverse_iterator crbegin() const {return rbegin();}
+ const_reverse_iterator crend() const {return rend();}
+
+ bool empty() const {return __tree_.size() == 0;}
+ size_type size() const {return __tree_.size();}
+ size_type max_size() const {return __tree_.max_size();}
+
+ // modifiers:
+#ifdef _LIBCPP_MOVE
+ template <class... _Args>
+ pair<iterator, bool> emplace(_Args&&... __args)
+ {return __tree_.__emplace_unique(_STD::forward<_Args>(__args)...);}
+ template <class... _Args>
+ iterator emplace_hint(const_iterator __p, _Args&&... __args)
+ {return __tree_.__emplace_hint_unique(__p, _STD::forward<_Args>(__args)...);}
+#endif
+ pair<iterator,bool> insert(const value_type& __v)
+ {return __tree_.__insert_unique(__v);}
+#ifdef _LIBCPP_MOVE
+ pair<iterator,bool> insert(value_type&& __v)
+ {return __tree_.__insert_unique(_STD::move(__v));}
+#endif
+ iterator insert(const_iterator __p, const value_type& __v)
+ {return __tree_.__insert_unique(__p, __v);}
+#ifdef _LIBCPP_MOVE
+ iterator insert(const_iterator __p, value_type&& __v)
+ {return __tree_.__insert_unique(__p, _STD::move(__v));}
+#endif
+ template <class _InputIterator>
+ void insert(_InputIterator __f, _InputIterator __l)
+ {
+ for (const_iterator __e = cend(); __f != __l; ++__f)
+ __tree_.__insert_unique(__e, *__f);
+ }
+
+ void insert(initializer_list<value_type> __il)
+ {insert(__il.begin(), __il.end());}
+
+ iterator erase(const_iterator __p) {return __tree_.erase(__p);}
+ size_type erase(const key_type& __k)
+ {return __tree_.__erase_unique(__k);}
+ iterator erase(const_iterator __f, const_iterator __l)
+ {return __tree_.erase(__f, __l);}
+ void clear() {__tree_.clear();}
+
+ void swap(set& __s) {__tree_.swap(__s.__tree_);}
+
+ allocator_type get_allocator() const {return __tree_.__alloc();}
+ key_compare key_comp() const {return __tree_.value_comp();}
+ value_compare value_comp() const {return __tree_.value_comp();}
+
+ // set operations:
+ iterator find(const key_type& __k) {return __tree_.find(__k);}
+ const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
+ size_type count(const key_type& __k) const
+ {return __tree_.__count_unique(__k);}
+ iterator lower_bound(const key_type& __k)
+ {return __tree_.lower_bound(__k);}
+ const_iterator lower_bound(const key_type& __k) const
+ {return __tree_.lower_bound(__k);}
+ iterator upper_bound(const key_type& __k)
+ {return __tree_.upper_bound(__k);}
+ const_iterator upper_bound(const key_type& __k) const
+ {return __tree_.upper_bound(__k);}
+ pair<iterator,iterator> equal_range(const key_type& __k)
+ {return __tree_.__equal_range_unique(__k);}
+ pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
+ {return __tree_.__equal_range_unique(__k);}
+};
+
+#ifdef _LIBCPP_MOVE
+
+template <class _Key, class _Compare, class _Allocator>
+set<_Key, _Compare, _Allocator>::set(set&& __s, const allocator_type& __a)
+ : __tree_(_STD::move(__s.__tree_), __a)
+{
+ if (__a != __s.get_allocator())
+ {
+ const_iterator __e = cend();
+ while (!__s.empty())
+ insert(__e, _STD::move(__s.__tree_.remove(__s.begin())->__value_));
+ }
+}
+
+#endif
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator==(const set<_Key, _Compare, _Allocator>& __x,
+ const set<_Key, _Compare, _Allocator>& __y)
+{
+ return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator< (const set<_Key, _Compare, _Allocator>& __x,
+ const set<_Key, _Compare, _Allocator>& __y)
+{
+ return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator!=(const set<_Key, _Compare, _Allocator>& __x,
+ const set<_Key, _Compare, _Allocator>& __y)
+{
+ return !(__x == __y);
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator> (const set<_Key, _Compare, _Allocator>& __x,
+ const set<_Key, _Compare, _Allocator>& __y)
+{
+ return __y < __x;
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator>=(const set<_Key, _Compare, _Allocator>& __x,
+ const set<_Key, _Compare, _Allocator>& __y)
+{
+ return !(__x < __y);
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator<=(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
+void
+swap(set<_Key, _Compare, _Allocator>& __x,
+ set<_Key, _Compare, _Allocator>& __y)
+{
+ __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 value_type& reference;
+ typedef const value_type& const_reference;
+
+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 _STD::reverse_iterator<iterator> reverse_iterator;
+ typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator;
+
+ // construct/copy/destroy:
+ explicit multiset(const value_compare& __comp = value_compare())
+ : __tree_(__comp) {}
+ multiset(const value_compare& __comp, const allocator_type& __a)
+ : __tree_(__comp, __a) {}
+ template <class _InputIterator>
+ multiset(_InputIterator __f, _InputIterator __l,
+ const value_compare& __comp = value_compare())
+ : __tree_(__comp)
+ {
+ insert(__f, __l);
+ }
+
+ template <class _InputIterator>
+ multiset(_InputIterator __f, _InputIterator __l,
+ const value_compare& __comp, const allocator_type& __a)
+ : __tree_(__comp, __a)
+ {
+ insert(__f, __l);
+ }
+
+ multiset(const multiset& __s)
+ : __tree_(__s.__tree_.value_comp(),
+ __alloc_traits::select_on_container_copy_construction(__s.__tree_.__alloc()))
+ {
+ insert(__s.begin(), __s.end());
+ }
+
+#ifdef _LIBCPP_MOVE
+ multiset(multiset&& __s)
+ : __tree_(_STD::move(__s.__tree_)) {}
+#endif
+ explicit multiset(const allocator_type& __a)
+ : __tree_(__a) {}
+ multiset(const multiset& __s, const allocator_type& __a)
+ : __tree_(__s.__tree_.value_comp(), __a)
+ {
+ insert(__s.begin(), __s.end());
+ }
+#ifdef _LIBCPP_MOVE
+ multiset(multiset&& __s, const allocator_type& __a);
+#endif
+
+ multiset(initializer_list<value_type> __il, const value_compare& __comp = value_compare())
+ : __tree_(__comp)
+ {
+ insert(__il.begin(), __il.end());
+ }
+
+ multiset(initializer_list<value_type> __il, const value_compare& __comp,
+ const allocator_type& __a)
+ : __tree_(__comp, __a)
+ {
+ insert(__il.begin(), __il.end());
+ }
+
+ multiset& operator=(initializer_list<value_type> __il)
+ {
+ __tree_.__assign_multi(__il.begin(), __il.end());
+ return *this;
+ }
+
+#ifdef _LIBCPP_MOVE
+ multiset& operator=(multiset&& __s)
+ {
+ __tree_ = _STD::move(__s.__tree_);
+ return *this;
+ }
+#endif
+
+ iterator begin() {return __tree_.begin();}
+ const_iterator begin() const {return __tree_.begin();}
+ iterator end() {return __tree_.end();}
+ const_iterator end() const {return __tree_.end();}
+
+ reverse_iterator rbegin() {return reverse_iterator(end());}
+ const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
+ reverse_iterator rend() {return reverse_iterator(begin());}
+ const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
+
+ const_iterator cbegin() const {return begin();}
+ const_iterator cend() const {return end();}
+ const_reverse_iterator crbegin() const {return rbegin();}
+ const_reverse_iterator crend() const {return rend();}
+
+ bool empty() const {return __tree_.size() == 0;}
+ size_type size() const {return __tree_.size();}
+ size_type max_size() const {return __tree_.max_size();}
+
+ // modifiers:
+#ifdef _LIBCPP_MOVE
+ template <class... _Args>
+ iterator emplace(_Args&&... __args)
+ {return __tree_.__emplace_multi(_STD::forward<_Args>(__args)...);}
+ template <class... _Args>
+ iterator emplace_hint(const_iterator __p, _Args&&... __args)
+ {return __tree_.__emplace_hint_multi(__p, _STD::forward<_Args>(__args)...);}
+#endif
+ iterator insert(const value_type& __v)
+ {return __tree_.__insert_multi(__v);}
+#ifdef _LIBCPP_MOVE
+ iterator insert(value_type&& __v)
+ {return __tree_.__insert_multi(_STD::move(__v));}
+#endif
+ iterator insert(const_iterator __p, const value_type& __v)
+ {return __tree_.__insert_multi(__p, __v);}
+#ifdef _LIBCPP_MOVE
+ iterator insert(const_iterator __p, value_type&& __v)
+ {return __tree_.__insert_multi(_STD::move(__v));}
+#endif
+ template <class _InputIterator>
+ void insert(_InputIterator __f, _InputIterator __l)
+ {
+ for (const_iterator __e = cend(); __f != __l; ++__f)
+ __tree_.__insert_multi(__e, *__f);
+ }
+
+ void insert(initializer_list<value_type> __il)
+ {insert(__il.begin(), __il.end());}
+
+ iterator erase(const_iterator __p) {return __tree_.erase(__p);}
+ size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
+ iterator erase(const_iterator __f, const_iterator __l)
+ {return __tree_.erase(__f, __l);}
+ void clear() {__tree_.clear();}
+
+ void swap(multiset& __s) {__tree_.swap(__s.__tree_);}
+
+ allocator_type get_allocator() const {return __tree_.__alloc();}
+ key_compare key_comp() const {return __tree_.value_comp();}
+ value_compare value_comp() const {return __tree_.value_comp();}
+
+ // set operations:
+ iterator find(const key_type& __k) {return __tree_.find(__k);}
+ const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
+ size_type count(const key_type& __k) const
+ {return __tree_.__count_multi(__k);}
+ iterator lower_bound(const key_type& __k)
+ {return __tree_.lower_bound(__k);}
+ const_iterator lower_bound(const key_type& __k) const
+ {return __tree_.lower_bound(__k);}
+ iterator upper_bound(const key_type& __k)
+ {return __tree_.upper_bound(__k);}
+ const_iterator upper_bound(const key_type& __k) const
+ {return __tree_.upper_bound(__k);}
+ pair<iterator,iterator> equal_range(const key_type& __k)
+ {return __tree_.__equal_range_multi(__k);}
+ pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
+ {return __tree_.__equal_range_multi(__k);}
+};
+
+#ifdef _LIBCPP_MOVE
+
+template <class _Key, class _Compare, class _Allocator>
+multiset<_Key, _Compare, _Allocator>::multiset(multiset&& __s, const allocator_type& __a)
+ : __tree_(_STD::move(__s.__tree_), __a)
+{
+ if (__a != __s.get_allocator())
+ {
+ const_iterator __e = cend();
+ while (!__s.empty())
+ insert(__e, _STD::move(__s.__tree_.remove(__s.begin())->__value_));
+ }
+}
+
+#endif
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator==(const multiset<_Key, _Compare, _Allocator>& __x,
+ const multiset<_Key, _Compare, _Allocator>& __y)
+{
+ return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator< (const multiset<_Key, _Compare, _Allocator>& __x,
+ const multiset<_Key, _Compare, _Allocator>& __y)
+{
+ return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator!=(const multiset<_Key, _Compare, _Allocator>& __x,
+ const multiset<_Key, _Compare, _Allocator>& __y)
+{
+ return !(__x == __y);
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator> (const multiset<_Key, _Compare, _Allocator>& __x,
+ const multiset<_Key, _Compare, _Allocator>& __y)
+{
+ return __y < __x;
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator>=(const multiset<_Key, _Compare, _Allocator>& __x,
+ const multiset<_Key, _Compare, _Allocator>& __y)
+{
+ return !(__x < __y);
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+bool
+operator<=(const multiset<_Key, _Compare, _Allocator>& __x,
+ const multiset<_Key, _Compare, _Allocator>& __y)
+{
+ return !(__y < __x);
+}
+
+template <class _Key, class _Compare, class _Allocator>
+inline
+void
+swap(multiset<_Key, _Compare, _Allocator>& __x,
+ multiset<_Key, _Compare, _Allocator>& __y)
+{
+ __x.swap(__y);
+}
+
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_SET