diff options
Diffstat (limited to 'tests/libcxx/include/list')
| -rw-r--r-- | tests/libcxx/include/list | 1605 |
1 files changed, 1605 insertions, 0 deletions
diff --git a/tests/libcxx/include/list b/tests/libcxx/include/list new file mode 100644 index 00000000..1779c004 --- /dev/null +++ b/tests/libcxx/include/list @@ -0,0 +1,1605 @@ +// -*- C++ -*- +//===---------------------------- list ------------------------------------===// +// +// 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_LIST +#define _LIBCPP_LIST + +/* + list synopsis + +namespace std +{ + +template <class T, class Alloc = allocator<T> > +class list +{ +public: + + // types: + typedef T value_type; + typedef Alloc 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 implementation-defined iterator; + typedef implementation-defined const_iterator; + typedef implementation-defined size_type; + typedef implementation-defined difference_type; + typedef reverse_iterator<iterator> reverse_iterator; + typedef reverse_iterator<const_iterator> const_reverse_iterator; + + list(); + explicit list(const allocator_type& a); + explicit list(size_type n); + list(size_type n, const value_type& value); + list(size_type n, const value_type& value, const allocator_type& a); + template <class Iter> + list(Iter first, Iter last); + template <class Iter> + list(Iter first, Iter last, const allocator_type& a); + list(const list& x); + list(const list&, const allocator_type& a); + list(list&& x); + list(list&&, const allocator_type& a); + list(initializer_list<value_type>); + list(initializer_list<value_type>, const allocator_type& a); + + ~list(); + + list& operator=(const list& x); + list& operator=(list&& x); + list& operator=(initializer_list<value_type>); + template <class Iter> + void assign(Iter first, Iter last); + void assign(size_type n, const value_type& t); + void assign(initializer_list<value_type>); + + allocator_type get_allocator() const; + + 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; + + reference front(); + const_reference front() const; + reference back(); + const_reference back() const; + + bool empty() const; + size_type size() const; + size_type max_size() const; + + template <class... Args> + void emplace_front(Args&&... args); + void pop_front(); + template <class... Args> + void emplace_back(Args&&... args); + void pop_back(); + void push_front(const value_type& x); + void push_front(value_type&& x); + void push_back(const value_type& x); + void push_back(value_type&& x); + template <class... Args> + iterator emplace(const_iterator position, Args&&... args); + iterator insert(const_iterator position, const value_type& x); + iterator insert(const_iterator position, value_type&& x); + iterator insert(const_iterator position, size_type n, const value_type& x); + template <class Iter> + iterator insert(const_iterator position, Iter first, Iter last); + iterator insert(const_iterator position, initializer_list<value_type> il); + + iterator erase(const_iterator position); + iterator erase(const_iterator position, const_iterator last); + + void resize(size_type sz); + void resize(size_type sz, const value_type& c); + + void swap(list<value_type,allocator_type>&); + void clear(); + + void splice(const_iterator position, list& x); + void splice(const_iterator position, list&& x); + void splice(const_iterator position, list& x, const_iterator i); + void splice(const_iterator position, list&& x, const_iterator i); + void splice(const_iterator position, list& x, const_iterator first, + const_iterator last); + void splice(const_iterator position, list&& x, const_iterator first, + const_iterator last); + + void remove(const value_type& value); + template <class Pred> void remove_if(Pred pred); + void unique(); + template <class BinaryPredicate> + void unique(BinaryPredicate binary_pred); + void merge(list& x); + void merge(list&& x); + template <class Compare> + void merge(list& x, Compare comp); + template <class Compare> + void merge(list&& x, Compare comp); + void sort(); + template <class Compare> + void sort(Compare comp); + void reverse(); +}; + +template <class T, class Alloc> + bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y); +template <class T, class Alloc> + bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y); +template <class T, class Alloc> + bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y); +template <class T, class Alloc> + bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y); +template <class T, class Alloc> + bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y); +template <class T, class Alloc> + bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y); + +template <class T, class Alloc> + void swap(list<T,Alloc>& x, list<T,Alloc>& y); + +} // std + +*/ + +#include <__config> + +#include <memory> +#include <limits> +#include <initializer_list> +#include <iterator> +#include <algorithm> + +#pragma GCC system_header + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <class, class> struct __list_node; + +template <class _Tp, class _VoidPtr> +struct __list_node_base +{ + typedef typename pointer_traits<_VoidPtr>::template +#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES + rebind<__list_node<_Tp, _VoidPtr> > pointer; +#else + rebind<__list_node<_Tp, _VoidPtr> >::other pointer; +#endif + + pointer __prev_; + pointer __next_; + + _LIBCPP_INLINE_VISIBILITY + __list_node_base() + : __prev_(static_cast<pointer>(this)), + __next_(static_cast<pointer>(this)) + {} +}; + +template <class _Tp, class _VoidPtr> +struct __list_node + : public __list_node_base<_Tp, _VoidPtr> +{ + _Tp __value_; +}; + +template <class, class> class list; +template <class, class> class __list_imp; +template <class, class> class __list_const_iterator; + +template <class _Tp, class _VoidPtr> +class _LIBCPP_VISIBLE __list_iterator +{ + typedef typename pointer_traits<_VoidPtr>::template +#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES + rebind<__list_node<_Tp, _VoidPtr> > __node_pointer; +#else + rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer; +#endif + + __node_pointer __ptr_; + + _LIBCPP_INLINE_VISIBILITY + explicit __list_iterator(__node_pointer __p) : __ptr_(__p) {} + + template<class, class> friend class list; + template<class, class> friend class __list_imp; + template<class, class> friend class __list_const_iterator; +public: + typedef bidirectional_iterator_tag iterator_category; + typedef _Tp value_type; + typedef value_type& reference; + typedef typename pointer_traits<_VoidPtr>::template +#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES + rebind<value_type> +#else + rebind<value_type>::other +#endif + pointer; + typedef typename pointer_traits<pointer>::difference_type difference_type; + + _LIBCPP_INLINE_VISIBILITY + reference operator*() const {return __ptr_->__value_;} + _LIBCPP_INLINE_VISIBILITY + pointer operator->() const {return &(operator*());} + + _LIBCPP_INLINE_VISIBILITY + __list_iterator& operator++() {__ptr_ = __ptr_->__next_; return *this;} + _LIBCPP_INLINE_VISIBILITY + __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;} + + _LIBCPP_INLINE_VISIBILITY + __list_iterator& operator--() {__ptr_ = __ptr_->__prev_; return *this;} + _LIBCPP_INLINE_VISIBILITY + __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;} + + friend _LIBCPP_INLINE_VISIBILITY + bool operator==(const __list_iterator& __x, const __list_iterator& __y) + {return __x.__ptr_ == __y.__ptr_;} + friend _LIBCPP_INLINE_VISIBILITY + bool operator!=(const __list_iterator& __x, const __list_iterator& __y) + {return !(__x == __y);} +}; + +template <class _Tp, class _VoidPtr> +class _LIBCPP_VISIBLE __list_const_iterator +{ + typedef typename pointer_traits<_VoidPtr>::template +#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES + rebind<const __list_node<_Tp, _VoidPtr> > __node_pointer; +#else + rebind<const __list_node<_Tp, _VoidPtr> >::other __node_pointer; +#endif + + __node_pointer __ptr_; + + _LIBCPP_INLINE_VISIBILITY + explicit __list_const_iterator(__node_pointer __p) : __ptr_(__p) {} + + template<class, class> friend class list; + template<class, class> friend class __list_imp; +public: + typedef bidirectional_iterator_tag iterator_category; + typedef _Tp value_type; + typedef const value_type& reference; + typedef typename pointer_traits<_VoidPtr>::template +#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES + rebind<const value_type> +#else + rebind<const value_type>::other +#endif + pointer; + typedef typename pointer_traits<pointer>::difference_type difference_type; + + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator(__list_iterator<_Tp, _VoidPtr> __p) : __ptr_(__p.__ptr_) {} + + _LIBCPP_INLINE_VISIBILITY + reference operator*() const {return __ptr_->__value_;} + _LIBCPP_INLINE_VISIBILITY + pointer operator->() const {return &(operator*());} + + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator& operator++() {__ptr_ = __ptr_->__next_; return *this;} + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;} + + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator& operator--() {__ptr_ = __ptr_->__prev_; return *this;} + _LIBCPP_INLINE_VISIBILITY + __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;} + + friend _LIBCPP_INLINE_VISIBILITY + bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y) + {return __x.__ptr_ == __y.__ptr_;} + friend _LIBCPP_INLINE_VISIBILITY + bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y) + {return !(__x == __y);} +}; + +template <class _Tp, class _Alloc> +class __list_imp +{ + __list_imp(const __list_imp&); + __list_imp& operator=(const __list_imp&); +protected: + typedef _Tp value_type; + typedef _Alloc allocator_type; + typedef allocator_traits<allocator_type> __alloc_traits; + typedef typename __alloc_traits::size_type size_type; + typedef typename __alloc_traits::void_pointer __void_pointer; + typedef __list_iterator<value_type, __void_pointer> iterator; + typedef __list_const_iterator<value_type, __void_pointer> const_iterator; + typedef __list_node_base<value_type, __void_pointer> __node_base; + typedef __list_node<value_type, __void_pointer> __node; + typedef typename __alloc_traits::template +#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES + rebind_alloc<__node> +#else + rebind_alloc<__node>::other +#endif + __node_allocator; + typedef allocator_traits<__node_allocator> __node_alloc_traits; + typedef typename __node_alloc_traits::pointer __node_pointer; + typedef typename __node_alloc_traits::const_pointer __node_const_pointer; + typedef typename __alloc_traits::pointer pointer; + typedef typename __alloc_traits::const_pointer const_pointer; + typedef typename __alloc_traits::difference_type difference_type; + + __node_base __end_; + __compressed_pair<size_type, __node_allocator> __size_alloc_; + + _LIBCPP_INLINE_VISIBILITY + size_type& __sz() {return __size_alloc_.first();} + _LIBCPP_INLINE_VISIBILITY + const size_type& __sz() const {return __size_alloc_.first();} + _LIBCPP_INLINE_VISIBILITY + __node_allocator& __node_alloc() {return __size_alloc_.second();} + _LIBCPP_INLINE_VISIBILITY + const __node_allocator& __node_alloc() const {return __size_alloc_.second();} + + static void __unlink_nodes(__node_base& __f, __node_base& __l); + + __list_imp(); + __list_imp(const allocator_type& __a); + ~__list_imp(); + void clear(); + _LIBCPP_INLINE_VISIBILITY + bool empty() const {return __sz() == 0;} + + _LIBCPP_INLINE_VISIBILITY + iterator begin() {return iterator(__end_.__next_);} + _LIBCPP_INLINE_VISIBILITY + const_iterator begin() const {return const_iterator(__end_.__next_);} + _LIBCPP_INLINE_VISIBILITY + iterator end() {return iterator(static_cast<__node_pointer> (&__end_));} + _LIBCPP_INLINE_VISIBILITY + const_iterator end() const {return const_iterator(static_cast<__node_const_pointer>(&__end_));} + + void swap(__list_imp& __c); + + _LIBCPP_INLINE_VISIBILITY + void __copy_assign_alloc(const __list_imp& __c) + {__copy_assign_alloc(__c, integral_constant<bool, + __node_alloc_traits::propagate_on_container_copy_assignment::value>());} + + _LIBCPP_INLINE_VISIBILITY + void __move_assign_alloc(__list_imp& __c) + {__move_assign_alloc(__c, integral_constant<bool, + __node_alloc_traits::propagate_on_container_move_assignment::value>());} + +private: + _LIBCPP_INLINE_VISIBILITY + static void __swap_alloc(__node_allocator& __x, __node_allocator& __y) + {__swap_alloc(__x, __y, integral_constant<bool, + __node_alloc_traits::propagate_on_container_swap::value>());} + _LIBCPP_INLINE_VISIBILITY + static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type) + { + using _STD::swap; + swap(__x, __y); + } + _LIBCPP_INLINE_VISIBILITY + static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type) + {} + + _LIBCPP_INLINE_VISIBILITY + void __copy_assign_alloc(const __list_imp& __c, true_type) + { + if (__node_alloc() != __c.__node_alloc()) + clear(); + __node_alloc() = __c.__node_alloc(); + } + + _LIBCPP_INLINE_VISIBILITY + void __copy_assign_alloc(const __list_imp& __c, false_type) + {} + + _LIBCPP_INLINE_VISIBILITY + void __move_assign_alloc(const __list_imp& __c, true_type) + { + __node_alloc() = _STD::move(__c.__node_alloc()); + } + + _LIBCPP_INLINE_VISIBILITY + void __move_assign_alloc(const __list_imp& __c, false_type) + {} +}; + +// Unlink nodes [__f, __l] +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +void +__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_base& __f, __node_base& __l) +{ + __f.__prev_->__next_ = __l.__next_; + __l.__next_->__prev_ = __f.__prev_; +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +__list_imp<_Tp, _Alloc>::__list_imp() + : __size_alloc_(0) +{ +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a) + : __size_alloc_(0, __node_allocator(__a)) +{ +} + +template <class _Tp, class _Alloc> +__list_imp<_Tp, _Alloc>::~__list_imp() +{ + clear(); +} + +template <class _Tp, class _Alloc> +void +__list_imp<_Tp, _Alloc>::clear() +{ + if (!empty()) + { + __node_allocator& __na = __node_alloc(); + iterator __f = begin(); + iterator __l = end(); + __unlink_nodes(*__f.__ptr_, *__l.__ptr_->__prev_); + __sz() = 0; + while (__f != __l) + { + __node& __n = *__f.__ptr_; + ++__f; + __node_alloc_traits::destroy(__na, addressof(__n.__value_)); + __node_alloc_traits::deallocate(__na, addressof(__n), 1); + } + } +} + +template <class _Tp, class _Alloc> +void +__list_imp<_Tp, _Alloc>::swap(__list_imp& __c) +{ + using _STD::swap; + __swap_alloc(__node_alloc(), __c.__node_alloc()); + swap(__sz(), __c.__sz()); + swap(__end_, __c.__end_); + if (__sz() == 0) + __end_.__next_ = __end_.__prev_ = &static_cast<__node&>(__end_); + else + __end_.__prev_->__next_ = __end_.__next_->__prev_ + = &static_cast<__node&>(__end_); + if (__c.__sz() == 0) + __c.__end_.__next_ = __c.__end_.__prev_ + = &static_cast<__node&>(__c.__end_); + else + __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_ + = &static_cast<__node&>(__c.__end_); +} + +template <class _Tp, class _Alloc = allocator<_Tp> > +class _LIBCPP_VISIBLE list + : private __list_imp<_Tp, _Alloc> +{ + typedef __list_imp<_Tp, _Alloc> base; + typedef typename base::__node __node; + typedef typename base::__node_allocator __node_allocator; + typedef typename base::__node_pointer __node_pointer; + typedef typename base::__node_alloc_traits __node_alloc_traits; + +public: + typedef _Tp value_type; + typedef _Alloc allocator_type; + static_assert((is_same<value_type, typename allocator_type::value_type>::value), + "Invalid allocator::value_type"); + typedef value_type& reference; + typedef const value_type& const_reference; + 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::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; + + _LIBCPP_INLINE_VISIBILITY + list() {} + _LIBCPP_INLINE_VISIBILITY + list(const allocator_type& __a) : base(__a) {} + list(size_type __n); + list(size_type __n, const value_type& __x); + list(size_type __n, const value_type& __x, const allocator_type& __a); + template <class _InpIter> + list(_InpIter __f, _InpIter __l, + typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); + template <class _InpIter> + list(_InpIter __f, _InpIter __l, const allocator_type& __a, + typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); + + list(const list& __c); + list(const list& __c, const allocator_type& __a); + list& operator=(const list& __c); + list(initializer_list<value_type> __il); + list(initializer_list<value_type> __il, const allocator_type& __a); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + list(list&& __c); + list(list&& __c, const allocator_type& __a); + list& operator=(list&& __c); +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + list& operator=(initializer_list<value_type> __il) + {assign(__il.begin(), __il.end()); return *this;} + + template <class _InpIter> + void assign(_InpIter __f, _InpIter __l, + typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); + void assign(size_type __n, const value_type& __x); + _LIBCPP_INLINE_VISIBILITY + void assign(initializer_list<value_type> __il) + {assign(__il.begin(), __il.end());} + + allocator_type get_allocator() const; + + _LIBCPP_INLINE_VISIBILITY + size_type size() const {return base::__sz();} + _LIBCPP_INLINE_VISIBILITY + bool empty() const {return base::empty();} + _LIBCPP_INLINE_VISIBILITY + size_type max_size() const {return numeric_limits<difference_type>::max();} + + _LIBCPP_INLINE_VISIBILITY + iterator begin() {return base::begin();} + _LIBCPP_INLINE_VISIBILITY + const_iterator begin() const {return base::begin();} + _LIBCPP_INLINE_VISIBILITY + iterator end() {return base::end();} + _LIBCPP_INLINE_VISIBILITY + const_iterator end() const {return base::end();} + _LIBCPP_INLINE_VISIBILITY + const_iterator cbegin() const {return base::begin();} + _LIBCPP_INLINE_VISIBILITY + const_iterator cend() const {return base::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_reverse_iterator crbegin() const {return const_reverse_iterator(end());} + _LIBCPP_INLINE_VISIBILITY + const_reverse_iterator crend() const {return const_reverse_iterator(begin());} + + _LIBCPP_INLINE_VISIBILITY + reference front() {return base::__end_.__next_->__value_;} + _LIBCPP_INLINE_VISIBILITY + const_reference front() const {return base::__end_.__next_->__value_;} + _LIBCPP_INLINE_VISIBILITY + reference back() {return base::__end_.__prev_->__value_;} + _LIBCPP_INLINE_VISIBILITY + const_reference back() const {return base::__end_.__prev_->__value_;} + +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + void push_front(value_type&& __x); + void push_back(value_type&& __x); +#ifndef _LIBCPP_HAS_NO_VARIADICS + template <class... _Args> + void emplace_front(_Args&&... __args); + template <class... _Args> + void emplace_back(_Args&&... __args); + template <class... _Args> + iterator emplace(const_iterator __p, _Args&&... __args); +#endif // _LIBCPP_HAS_NO_VARIADICS + iterator insert(const_iterator __p, value_type&& __x); +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + + void push_front(const value_type& __x); + void push_back(const value_type& __x); + + iterator insert(const_iterator __p, const value_type& __x); + iterator insert(const_iterator __p, size_type __n, const value_type& __x); + template <class _InpIter> + iterator insert(const_iterator __p, _InpIter __f, _InpIter __l, + typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0); + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __p, initializer_list<value_type> __il) + {return insert(__p, __il.begin(), __il.end());} + + _LIBCPP_INLINE_VISIBILITY + void swap(list& __c) {base::swap(__c);} + _LIBCPP_INLINE_VISIBILITY + void clear() {base::clear();} + + void pop_front(); + void pop_back(); + + iterator erase(const_iterator __p); + iterator erase(const_iterator __f, const_iterator __l); + + void resize(size_type __n); + void resize(size_type __n, const value_type& __x); + + void splice(const_iterator __p, list& __c); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + void splice(const_iterator __p, list&& __c) {splice(__p, __c);} +#endif + void splice(const_iterator __p, list& __c, const_iterator __i); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + void splice(const_iterator __p, list&& __c, const_iterator __i) + {splice(__p, __c, __i);} +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l) + {splice(__p, __c, __f, __l);} +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + + void remove(const value_type& __x); + template <class _Pred> void remove_if(_Pred __pred); + void unique(); + template <class _BinaryPred> + void unique(_BinaryPred __binary_pred); + void merge(list& __c); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + void merge(list&& __c) {merge(__c);} +#endif + template <class _Comp> + void merge(list& __c, _Comp __comp); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + template <class _Comp> + _LIBCPP_INLINE_VISIBILITY + void merge(list&& __c, _Comp __comp) {merge(__c, __comp);} +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + void sort(); + template <class _Comp> + void sort(_Comp __comp); + + void reverse(); + +private: + static void __link_nodes(__node& __p, __node& __f, __node& __l); + iterator __iterator(size_type __n); + template <class _Comp> + static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp); + + void __move_assign(list& __c, true_type); + void __move_assign(list& __c, false_type); +}; + +// Link in nodes [__f, __l] just prior to __p +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +void +list<_Tp, _Alloc>::__link_nodes(__node& __p, __node& __f, __node& __l) +{ + __p.__prev_->__next_ = &__f; + __f.__prev_ = __p.__prev_; + __p.__prev_ = &__l; + __l.__next_ = &__p; +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +typename list<_Tp, _Alloc>::iterator +list<_Tp, _Alloc>::__iterator(size_type __n) +{ + return __n <= base::__sz() / 2 ? next(begin(), __n) + : prev(end(), base::__sz() - __n); +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(size_type __n) +{ + for (; __n > 0; --__n) +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + emplace_back(); +#else + push_back(value_type()); +#endif +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(size_type __n, const value_type& __x) +{ + for (; __n > 0; --__n) + push_back(__x); +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a) + : base(__a) +{ + for (; __n > 0; --__n) + push_back(__x); +} + +template <class _Tp, class _Alloc> +template <class _InpIter> +list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, + typename enable_if<__is_input_iterator<_InpIter>::value>::type*) +{ + for (; __f != __l; ++__f) + push_back(*__f); +} + +template <class _Tp, class _Alloc> +template <class _InpIter> +list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a, + typename enable_if<__is_input_iterator<_InpIter>::value>::type*) + : base(__a) +{ + for (; __f != __l; ++__f) + push_back(*__f); +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(const list& __c) + : base(allocator_type( + __node_alloc_traits::select_on_container_copy_construction( + __c.__node_alloc()))) +{ + for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) + push_back(*__i); +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a) + : base(__a) +{ + for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i) + push_back(*__i); +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a) + : base(__a) +{ + for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), + __e = __il.end(); __i != __e; ++__i) + push_back(*__i); +} + +template <class _Tp, class _Alloc> +list<_Tp, _Alloc>::list(initializer_list<value_type> __il) +{ + for (typename initializer_list<value_type>::const_iterator __i = __il.begin(), + __e = __il.end(); __i != __e; ++__i) + push_back(*__i); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +list<_Tp, _Alloc>& +list<_Tp, _Alloc>::operator=(const list& __c) +{ + if (this != &__c) + { + base::__copy_assign_alloc(__c); + assign(__c.begin(), __c.end()); + } + return *this; +} + +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +list<_Tp, _Alloc>::list(list&& __c) + : base(allocator_type(_STD::move(__c.__node_alloc()))) +{ + splice(end(), __c); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a) + : base(__a) +{ + if (__a == __c.get_allocator()) + splice(end(), __c); + else + { + typedef move_iterator<iterator> _I; + assign(_I(__c.begin()), _I(__c.end())); + } +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +list<_Tp, _Alloc>& +list<_Tp, _Alloc>::operator=(list&& __c) +{ + __move_assign(__c, integral_constant<bool, + __node_alloc_traits::propagate_on_container_move_assignment::value>()); + return *this; +} + +template <class _Tp, class _Alloc> +void +list<_Tp, _Alloc>::__move_assign(list& __c, false_type) +{ + if (base::__node_alloc() != __c.__node_alloc()) + { + typedef move_iterator<iterator> _I; + assign(_I(__c.begin()), _I(__c.end())); + } + else + __move_assign(__c, true_type()); +} + +template <class _Tp, class _Alloc> +void +list<_Tp, _Alloc>::__move_assign(list& __c, true_type) +{ + clear(); + base::__move_assign_alloc(__c); + splice(end(), __c); +} + +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + +template <class _Tp, class _Alloc> +template <class _InpIter> +void +list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l, + typename enable_if<__is_input_iterator<_InpIter>::value>::type*) +{ + iterator __i = begin(); + iterator __e = end(); + for (; __f != __l && __i != __e; ++__f, ++__i) + *__i = *__f; + if (__i == __e) + insert(__e, __f, __l); + else + erase(__i, __e); +} + +template <class _Tp, class _Alloc> +void +list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x) +{ + iterator __i = begin(); + iterator __e = end(); + for (; __n > 0 && __i != __e; --__n, ++__i) + *__i = __x; + if (__i == __e) + insert(__e, __n, __x); + else + erase(__i, __e); +} + +template <class _Tp, class _Alloc> +inline _LIBCPP_INLINE_VISIBILITY +_Alloc +list<_Tp, _Alloc>::get_allocator() const +{ + return allocator_type(base::__node_alloc()); +} + +template <class _Tp, class _Alloc> +typename list<_Tp, _Alloc>::iterator +list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x) +{ + __node_allocator& __na = base::__node_alloc(); + typedef __allocator_destructor<__node_allocator> _D; + unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + __hold->__prev_ = 0; + __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x); + __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold); + ++base::__sz(); + return iterator(__hold.release()); +} + +template <class _Tp, class _Alloc> +typename list<_Tp, _Alloc>::iterator +list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x) +{ + iterator __r(const_cast<__node_pointer>(__p.__ptr_)); + if (__n > 0) + { + size_type __ds = 0; + __node_allocator& __na = base::__node_alloc(); + typedef __allocator_destructor<__node_allocator> _D; + unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + __hold->__prev_ = 0; + __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x); + ++__ds; + __r = iterator(__hold.get()); + __hold.release(); + iterator __e = __r; +#ifndef _LIBCPP_NO_EXCEPTIONS + try + { +#endif // _LIBCPP_NO_EXCEPTIONS + for (--__n; __n != 0; --__n, ++__e, ++__ds) + { + __hold.reset(__node_alloc_traits::allocate(__na, 1)); + __node_alloc_traits::construct(__na, addressof(__hold->__value_), __x); + __e.__ptr_->__next_ = __hold.get(); + __hold->__prev_ = __e.__ptr_; + __hold.release(); + } +#ifndef _LIBCPP_NO_EXCEPTIONS + } + catch (...) + { + while (true) + { + __node_alloc_traits::destroy(__na, addressof(*__e)); + __node_pointer __prev = __e.__ptr_->__prev_; + __node_alloc_traits::deallocate(__na, __e.__ptr_, 1); + if (__prev == 0) + break; + __e = iterator(__prev); + } + throw; + } +#endif // _LIBCPP_NO_EXCEPTIONS + __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_); + base::__sz() += __ds; + } + return __r; +} + +template <class _Tp, class _Alloc> +template <class _InpIter> +typename list<_Tp, _Alloc>::iterator +list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l, + typename enable_if<__is_input_iterator<_InpIter>::value>::type*) +{ + iterator __r(const_cast<__node_pointer>(__p.__ptr_)); + if (__f != __l) + { + size_type __ds = 0; + __node_allocator& __na = base::__node_alloc(); + typedef __allocator_destructor<__node_allocator> _D; + unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1)); + __hold->__prev_ = 0; + __node_alloc_traits::construct(__na, addressof(__hold->__value_), *__f); + ++__ds; + __r = iterator(__hold.get()); + __hold.release(); + iterator __e = __r; +#ifndef _LIBCPP_NO_EXCEPTIONS + try + { +#endif // _LIBCPP_NO_EXCEPTIONS + for (++__f; __f != __l; ++__f, ++__e, ++__ds) + { + __hold.reset(__node_alloc_traits::allocate(__na, 1)); + __node_alloc_traits::construct(__na, addressof(__hold->__v |