diff options
Diffstat (limited to 'tests/libcxx/include/map')
| -rw-r--r-- | tests/libcxx/include/map | 1830 |
1 files changed, 0 insertions, 1830 deletions
diff --git a/tests/libcxx/include/map b/tests/libcxx/include/map deleted file mode 100644 index 387c6b50..00000000 --- a/tests/libcxx/include/map +++ /dev/null @@ -1,1830 +0,0 @@ -// -*- C++ -*- -//===----------------------------- map ------------------------------------===// -// -// 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_MAP -#define _LIBCPP_MAP - -/* - - map synopsis - -namespace std -{ - -template <class Key, class T, class Compare = less<Key>, - class Allocator = allocator<pair<const Key, T>>> -class map -{ -public: - // types: - typedef Key key_type; - typedef T mapped_type; - typedef pair<const key_type, mapped_type> value_type; - typedef Compare key_compare; - typedef Allocator allocator_type; - typedef typename allocator_type::reference reference; - typedef typename allocator_type::const_reference const_reference; - typedef typename allocator_type::pointer pointer; - typedef typename allocator_type::const_pointer const_pointer; - typedef typename allocator_type::size_type size_type; - typedef typename allocator_type::difference_type difference_type; - - 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; - - class value_compare - : public binary_function<value_type, value_type, bool> - { - friend class map; - protected: - key_compare comp; - - value_compare(key_compare c); - public: - bool operator()(const value_type& x, const value_type& y) const; - }; - - // construct/copy/destroy: - map(); - explicit map(const key_compare& comp); - map(const key_compare& comp, const allocator_type& a); - template <class InputIterator> - map(InputIterator first, InputIterator last, - const key_compare& comp = key_compare()); - template <class InputIterator> - map(InputIterator first, InputIterator last, - const key_compare& comp, const allocator_type& a); - map(const map& m); - map(map&& m); - explicit map(const allocator_type& a); - map(const map& m, const allocator_type& a); - map(map&& m, const allocator_type& a); - map(initializer_list<value_type> il, const key_compare& comp = key_compare()); - map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a); - ~map(); - - map& operator=(const map& m); - map& operator=(map&& m); - map& 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; - - // element access: - mapped_type& operator[](const key_type& k); - mapped_type& operator[](key_type&& k); - - mapped_type& at(const key_type& k); - const mapped_type& at(const key_type& k) 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); - template <class P> - pair<iterator, bool> insert(P&& p); - iterator insert(const_iterator position, const value_type& v); - template <class P> - iterator insert(const_iterator position, P&& p); - 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(map& m); - - // observers: - allocator_type get_allocator() const; - key_compare key_comp() const; - value_compare value_comp() const; - - // map 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 T, class Compare, class Allocator> -bool -operator==(const map<Key, T, Compare, Allocator>& x, - const map<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator< (const map<Key, T, Compare, Allocator>& x, - const map<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator!=(const map<Key, T, Compare, Allocator>& x, - const map<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator> (const map<Key, T, Compare, Allocator>& x, - const map<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator>=(const map<Key, T, Compare, Allocator>& x, - const map<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator<=(const map<Key, T, Compare, Allocator>& x, - const map<Key, T, Compare, Allocator>& y); - -// specialized algorithms: -template <class Key, class T, class Compare, class Allocator> -void -swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare = less<Key>, - class Allocator = allocator<pair<const Key, T>>> -class multimap -{ -public: - // types: - typedef Key key_type; - typedef T mapped_type; - typedef pair<const key_type,mapped_type> value_type; - typedef Compare key_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; - - class value_compare - : public binary_function<value_type,value_type,bool> - { - friend class multimap; - protected: - key_compare comp; - value_compare(key_compare c); - public: - bool operator()(const value_type& x, const value_type& y) const; - }; - - // construct/copy/destroy: - explicit multimap(const key_compare& comp = key_compare()); - multimap(const key_compare& comp, const allocator_type& a); - template <class InputIterator> - multimap(InputIterator first, InputIterator last, const key_compare& comp); - template <class InputIterator> - multimap(InputIterator first, InputIterator last, const key_compare& comp, - const allocator_type& a); - multimap(const multimap& m); - multimap(multimap&& m); - explicit multimap(const allocator_type& a); - multimap(const multimap& m, const allocator_type& a); - multimap(multimap&& m, const allocator_type& a); - multimap(initializer_list<value_type> il, const key_compare& comp = key_compare()); - multimap(initializer_list<value_type> il, const key_compare& comp, - const allocator_type& a); - ~multimap(); - - multimap& operator=(const multimap& m); - multimap& operator=(multimap&& m); - multimap& 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); - template <class P> - iterator insert(P&& p); - iterator insert(const_iterator position, const value_type& v); - template <class P> - iterator insert(const_iterator position, P&& p); - 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(multimap& m); - - // observers: - allocator_type get_allocator() const; - key_compare key_comp() const; - value_compare value_comp() const; - - // map 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 T, class Compare, class Allocator> -bool -operator==(const multimap<Key, T, Compare, Allocator>& x, - const multimap<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator< (const multimap<Key, T, Compare, Allocator>& x, - const multimap<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator!=(const multimap<Key, T, Compare, Allocator>& x, - const multimap<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator> (const multimap<Key, T, Compare, Allocator>& x, - const multimap<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator>=(const multimap<Key, T, Compare, Allocator>& x, - const multimap<Key, T, Compare, Allocator>& y); - -template <class Key, class T, class Compare, class Allocator> -bool -operator<=(const multimap<Key, T, Compare, Allocator>& x, - const multimap<Key, T, Compare, Allocator>& y); - -// specialized algorithms: -template <class Key, class T, class Compare, class Allocator> -void -swap(multimap<Key, T, Compare, Allocator>& x, - multimap<Key, T, Compare, Allocator>& y); - -} // std - -*/ - -#include <__config> -#include <__tree> -#include <iterator> -#include <memory> -#include <utility> -#include <functional> -#include <initializer_list> - -#pragma GCC system_header - -_LIBCPP_BEGIN_NAMESPACE_STD - -template <class _Key, class _Tp, class _Compare, bool = is_empty<_Compare>::value> -class __map_value_compare - : private _Compare -{ - typedef pair<typename std::remove_const<_Key>::type, _Tp> _P; - typedef pair<const _Key, _Tp> _CP; -public: - _LIBCPP_INLINE_VISIBILITY - __map_value_compare() : _Compare() {} - _LIBCPP_INLINE_VISIBILITY - __map_value_compare(_Compare c) : _Compare(c) {} - _LIBCPP_INLINE_VISIBILITY - const _Compare& key_comp() const {return *this;} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _CP& __x, const _CP& __y) const - {return static_cast<const _Compare&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _CP& __x, const _P& __y) const - {return static_cast<const _Compare&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _CP& __x, const _Key& __y) const - {return static_cast<const _Compare&>(*this)(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _P& __x, const _CP& __y) const - {return static_cast<const _Compare&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _P& __x, const _P& __y) const - {return static_cast<const _Compare&>(*this)(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _P& __x, const _Key& __y) const - {return static_cast<const _Compare&>(*this)(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _CP& __y) const - {return static_cast<const _Compare&>(*this)(__x, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _P& __y) const - {return static_cast<const _Compare&>(*this)(__x, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _Key& __y) const - {return static_cast<const _Compare&>(*this)(__x, __y);} -}; - -template <class _Key, class _Tp, class _Compare> -class __map_value_compare<_Key, _Tp, _Compare, false> -{ - _Compare comp; - - typedef pair<typename std::remove_const<_Key>::type, _Tp> _P; - typedef pair<const _Key, _Tp> _CP; - -public: - _LIBCPP_INLINE_VISIBILITY - __map_value_compare() : comp() {} - _LIBCPP_INLINE_VISIBILITY - __map_value_compare(_Compare c) : comp(c) {} - _LIBCPP_INLINE_VISIBILITY - const _Compare& key_comp() const {return comp;} - - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _CP& __x, const _CP& __y) const - {return comp(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _CP& __x, const _P& __y) const - {return comp(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _CP& __x, const _Key& __y) const - {return comp(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _P& __x, const _CP& __y) const - {return comp(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _P& __x, const _P& __y) const - {return comp(__x.first, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _P& __x, const _Key& __y) const - {return comp(__x.first, __y);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _CP& __y) const - {return comp(__x, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _P& __y) const - {return comp(__x, __y.first);} - _LIBCPP_INLINE_VISIBILITY - bool operator()(const _Key& __x, const _Key& __y) const - {return comp(__x, __y);} -}; - -template <class _Allocator> -class __map_node_destructor -{ - typedef _Allocator allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::value_type::value_type value_type; -public: - typedef typename __alloc_traits::pointer pointer; -private: - typedef typename value_type::first_type first_type; - typedef typename value_type::second_type second_type; - - allocator_type& __na_; - - __map_node_destructor& operator=(const __map_node_destructor&); - -public: - bool __first_constructed; - bool __second_constructed; - - _LIBCPP_INLINE_VISIBILITY - explicit __map_node_destructor(allocator_type& __na) - : __na_(__na), - __first_constructed(false), - __second_constructed(false) - {} - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - _LIBCPP_INLINE_VISIBILITY - __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) - : __na_(__x.__na_), - __first_constructed(__x.__value_constructed), - __second_constructed(__x.__value_constructed) - { - __x.__value_constructed = false; - } -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _LIBCPP_INLINE_VISIBILITY - void operator()(pointer __p) - { - if (__second_constructed) - __alloc_traits::destroy(__na_, addressof(__p->__value_.second)); - if (__first_constructed) - __alloc_traits::destroy(__na_, addressof(__p->__value_.first)); - if (__p) - __alloc_traits::deallocate(__na_, __p, 1); - } -}; - -template <class, class, class, class> class map; -template <class, class, class, class> class multimap; -template <class> class __map_const_iterator; - -template <class _TreeIterator> -class _LIBCPP_VISIBLE __map_iterator -{ - _TreeIterator __i_; - - typedef typename _TreeIterator::__pointer_traits __pointer_traits; - typedef const typename _TreeIterator::value_type::first_type key_type; - typedef typename _TreeIterator::value_type::second_type mapped_type; -public: - typedef bidirectional_iterator_tag iterator_category; - typedef pair<key_type, mapped_type> value_type; - typedef typename _TreeIterator::difference_type difference_type; - typedef value_type& reference; - typedef typename __pointer_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY - __map_iterator() {} - - _LIBCPP_INLINE_VISIBILITY - __map_iterator(_TreeIterator __i) : __i_(__i) {} - - _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return *operator->();} - _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return (pointer)__i_.operator->();} - - _LIBCPP_INLINE_VISIBILITY - __map_iterator& operator++() {++__i_; return *this;} - _LIBCPP_INLINE_VISIBILITY - __map_iterator operator++(int) - { - __map_iterator __t(*this); - ++(*this); - return __t; - } - - _LIBCPP_INLINE_VISIBILITY - __map_iterator& operator--() {--__i_; return *this;} - _LIBCPP_INLINE_VISIBILITY - __map_iterator operator--(int) - { - __map_iterator __t(*this); - --(*this); - return __t; - } - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __map_iterator& __x, const __map_iterator& __y) - {return __x.__i_ == __y.__i_;} - friend - _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __map_iterator& __x, const __map_iterator& __y) - {return __x.__i_ != __y.__i_;} - - template <class, class, class, class> friend class _LIBCPP_VISIBLE map; - template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap; - template <class> friend class _LIBCPP_VISIBLE __map_const_iterator; -}; - -template <class _TreeIterator> -class _LIBCPP_VISIBLE __map_const_iterator -{ - _TreeIterator __i_; - - typedef typename _TreeIterator::__pointer_traits __pointer_traits; - typedef const typename _TreeIterator::value_type::first_type key_type; - typedef typename _TreeIterator::value_type::second_type mapped_type; -public: - typedef bidirectional_iterator_tag iterator_category; - typedef pair<key_type, mapped_type> value_type; - typedef typename _TreeIterator::difference_type difference_type; - typedef const value_type& reference; - typedef typename __pointer_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator() {} - - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator(_TreeIterator __i) : __i_(__i) {} - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator( - __map_iterator<typename _TreeIterator::__non_const_iterator> __i) - : __i_(__i.__i_) {} - - _LIBCPP_INLINE_VISIBILITY - reference operator*() const {return *operator->();} - _LIBCPP_INLINE_VISIBILITY - pointer operator->() const {return (pointer)__i_.operator->();} - - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator& operator++() {++__i_; return *this;} - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator operator++(int) - { - __map_const_iterator __t(*this); - ++(*this); - return __t; - } - - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator& operator--() {--__i_; return *this;} - _LIBCPP_INLINE_VISIBILITY - __map_const_iterator operator--(int) - { - __map_const_iterator __t(*this); - --(*this); - return __t; - } - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) - {return __x.__i_ == __y.__i_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) - {return __x.__i_ != __y.__i_;} - - template <class, class, class, class> friend class _LIBCPP_VISIBLE map; - template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap; - template <class, class, class> friend class _LIBCPP_VISIBLE __tree_const_iterator; -}; - -template <class _Key, class _Tp, class _Compare = less<_Key>, - class _Allocator = allocator<pair<const _Key, _Tp> > > -class _LIBCPP_VISIBLE map -{ -public: - // types: - typedef _Key key_type; - typedef _Tp mapped_type; - typedef pair<const key_type, mapped_type> value_type; - typedef _Compare key_compare; - typedef _Allocator allocator_type; - typedef value_type& reference; - typedef const value_type& const_reference; - - class _LIBCPP_VISIBLE value_compare - : public binary_function<value_type, value_type, bool> - { - friend class map; - protected: - key_compare comp; - - _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {} - public: - _LIBCPP_INLINE_VISIBILITY - bool operator()(const value_type& __x, const value_type& __y) const - {return comp(__x.first, __y.first);} - }; - -private: - typedef pair<key_type, mapped_type> __value_type; - typedef __map_value_compare<key_type, mapped_type, key_compare> __vc; - typedef typename allocator_traits<allocator_type>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind_alloc<__value_type> -#else - rebind_alloc<__value_type>::other -#endif - __allocator_type; - typedef __tree<__value_type, __vc, __allocator_type> __base; - typedef typename __base::__node_traits __node_traits; - typedef allocator_traits<allocator_type> __alloc_traits; - - __base __tree_; - -public: - typedef typename __alloc_traits::pointer pointer; - typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; - typedef __map_iterator<typename __base::iterator> iterator; - typedef __map_const_iterator<typename __base::const_iterator> const_iterator; - typedef _STD::reverse_iterator<iterator> reverse_iterator; - typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator; - - _LIBCPP_INLINE_VISIBILITY - explicit map(const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) {} - - _LIBCPP_INLINE_VISIBILITY - explicit map(const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), __a) {} - - template <class _InputIterator> - _LIBCPP_INLINE_VISIBILITY - map(_InputIterator __f, _InputIterator __l, - const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) - { - insert(__f, __l); - } - - template <class _InputIterator> - _LIBCPP_INLINE_VISIBILITY - map(_InputIterator __f, _InputIterator __l, - const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), __a) - { - insert(__f, __l); - } - - _LIBCPP_INLINE_VISIBILITY - map(const map& __m) - : __tree_(__m.__tree_) - { - insert(__m.begin(), __m.end()); - } - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _LIBCPP_INLINE_VISIBILITY - map(map&& __m) - : __tree_(_STD::move(__m.__tree_)) - { - } - - map(map&& __m, const allocator_type& __a); - - _LIBCPP_INLINE_VISIBILITY - map(initializer_list<value_type> __il, const key_compare& __comp = key_compare()) - : __tree_(__vc(__comp)) - { - insert(__il.begin(), __il.end()); - } - - _LIBCPP_INLINE_VISIBILITY - map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a) - : __tree_(__vc(__comp), __a) - { - insert(__il.begin(), __il.end()); - } - - _LIBCPP_INLINE_VISIBILITY - map& operator=(map&& __m) - { - __tree_ = _STD::move(__m.__tree_); - return *this; - } - - _LIBCPP_INLINE_VISIBILITY - map& operator=(initializer_list<value_type> __il) - { - __tree_.__assign_unique(__il.begin(), __il.end()); - return *this; - } - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _LIBCPP_INLINE_VISIBILITY - explicit map(const allocator_type& __a) - : __tree_(__a) - { - } - - _LIBCPP_INLINE_VISIBILITY - map(const map& __m, const allocator_type& __a) - : __tree_(__m.__tree_.value_comp(), __a) - { - insert(__m.begin(), __m.end()); - } - - _LIBCPP_INLINE_VISIBILITY - iterator begin() {return __tree_.begin();} - _LIBCPP_INLINE_VISIBILITY - const_iterator begin() const {return __tree_.begin();} - _LIBCPP_INLINE_VISIBILITY - iterator end() {return __tree_.end();} - _LIBCPP_INLINE_VISIBILITY - const_iterator end() const {return __tree_.end();} - - _LIBCPP_INLINE_VISIBILITY - reverse_iterator rbegin() {return reverse_iterator(end());} - _LIBCPP_INLINE_VISIBILITY - const_reverse_iterator rbegin() const {return const_reverse_iterator(end());} - _LIBCPP_INLINE_VISIBILITY - reverse_iterator rend() {return reverse_iterator(begin());} - _LIBCPP_INLINE_VISIBILITY - const_reverse_iterator rend() const {return const_reverse_iterator(begin());} - - _LIBCPP_INLINE_VISIBILITY - const_iterator cbegin() const {return begin();} - _LIBCPP_INLINE_VISIBILITY - const_iterator cend() const {return end();} - _LIBCPP_INLINE_VISIBILITY - const_reverse_iterator crbegin() const {return rbegin();} - _LIBCPP_INLINE_VISIBILITY - const_reverse_iterator crend() const {return rend();} - - _LIBCPP_INLINE_VISIBILITY - bool empty() const {return __tree_.size() == 0;} - _LIBCPP_INLINE_VISIBILITY - size_type size() const {return __tree_.size();} - _LIBCPP_INLINE_VISIBILITY - size_type max_size() const {return __tree_.max_size();} - - mapped_type& operator[](const key_type& __k); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - mapped_type& operator[](key_type&& __k); -#endif - - mapped_type& at(const key_type& __k); - const mapped_type& at(const key_type& __k) const; - - _LIBCPP_INLINE_VISIBILITY - allocator_type get_allocator() const {return __tree_.__alloc();} - _LIBCPP_INLINE_VISIBILITY - key_compare key_comp() const {return __tree_.value_comp().key_comp();} - _LIBCPP_INLINE_VISIBILITY - value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());} - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _LIBCPP_INLINE_VISIBILITY - pair<iterator, bool> - emplace() {return __tree_.__emplace_unique();} - - template <class _A0, - class = typename enable_if<is_convertible<_A0, value_type>::value>::type> - _LIBCPP_INLINE_VISIBILITY - pair<iterator, bool> - emplace(_A0&& __a0) - {return __tree_.__emplace_unique(_STD::forward<_A0>(__a0));} - -#ifndef _LIBCPP_HAS_NO_VARIADICS - - template <class _A0, class ..._Args, - class = typename enable_if<is_convertible<_A0, key_type>::value>::type> - pair<iterator, bool> - emplace(_A0&& __a0, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS - - _LIBCPP_INLINE_VISIBILITY - iterator - emplace_hint(const_iterator __p) - {return __tree_.__emplace_hint_unique(__p.__i_);} - - template <class _A0, - class = typename enable_if<is_convertible<_A0, value_type>::value>::type> - _LIBCPP_INLINE_VISIBILITY - iterator - emplace_hint(const_iterator __p, _A0&& __a0) - {return __tree_.__emplace_hint_unique(__p.__i_, _STD::forward<_A0>(__a0));} - -#ifndef _LIBCPP_HAS_NO_VARIADICS - - template <class _A0, class ..._Args, - class = typename enable_if<is_convertible<_A0, key_type>::value>::type> - iterator - emplace_hint(const_iterator __p, _A0&& __a0, _Args&& ...__args); - -#endif // _LIBCPP_HAS_NO_VARIADICS - - template <class _P, - class = typename enable_if<is_convertible<_P, value_type>::value>::type> - _LIBCPP_INLINE_VISIBILITY - pair<iterator, bool> insert(_P&& __p) - {return __tree_.__insert_unique(_STD::forward<_P>(__p));} - - template <class _P, - class = typename enable_if<is_convertible<_P, value_type>::value>::type> - _LIBCPP_INLINE_VISIBILITY - iterator insert(const_iterator __pos, _P&& __p) - {return __tree_.__insert_unique(__pos.__i_, _STD::forward<_P>(__p));} - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - _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.__i_, __v);} - - template <class _InputIterator> - _LIBCPP_INLINE_VISIBILITY - void insert(_InputIterator __f, _InputIterator __l) - { - for (const_iterator __e = cend(); __f != __l; ++__f) - insert(__e.__i_, *__f); - } - - _LIBCPP_INLINE_VISIBILITY - void insert(initializer_list<value_type> __il) - {insert(__il.begin(), __il.end());} - - _LIBCPP_INLINE_VISIBILITY - iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);} - _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.__i_, __l.__i_);} - _LIBCPP_INLINE_VISIBILITY - void clear() {__tree_.clear();} - - _LIBCPP_INLINE_VISIBILITY - void swap(map& __m) {__tree_.swap(__m.__tree_);} - - _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);} - _LIBCPP_INLINE_VISIBILITY - size_type count(const key_type& __k) const - {return __tree_.__count_unique(__k);} - _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);} - _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);} - _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);} - -private: - typedef typename __base::__node __node; - typedef typename __base::__node_allocator __node_allocator; - typedef typename __base::__node_pointer __node_pointer; - typedef typename __base::__node_const_pointer __node_const_pointer; - typedef typename __base::__node_base_pointer __node_base_pointer; - typedef typename __base::__node_base_const_pointer __node_base_const_pointer; - typedef __map_node_destructor<__node_allocator> _D; - typedef unique_ptr<__node, _D> __node_holder; - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(); - template <class _A0, - class = typename enable_if<is_convertible<_A0, value_type>::value>::type> - __node_holder __construct_node(_A0&& __a0); -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class _A0, class ..._Args, - class = typename enable_if<is_convertible<_A0, key_type>::value>::type> - __node_holder __construct_node(_A0&& __a0, _Args&& ...__args); -#endif // _LIBCPP_HAS_NO_VARIADICS -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES - __node_holder __construct_node(const key_type& __k); -#endif - - __node_base_pointer& - __find_equal_key(__node_base_pointer& __parent, const key_type& __k); - __node_base_pointer& - __find_equal_key(const_iterator __hint, - __node_base_pointer& __parent, const key_type& __k); - __node_base_const_pointer - __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const; -}; - -// Find place to insert if __k doesn't exist -// Set __parent to parent of null leaf -// Return reference to |