diff options
Diffstat (limited to 'tests/libcxx/include/vector')
| -rw-r--r-- | tests/libcxx/include/vector | 2786 |
1 files changed, 2786 insertions, 0 deletions
diff --git a/tests/libcxx/include/vector b/tests/libcxx/include/vector new file mode 100644 index 00000000..7c0fc705 --- /dev/null +++ b/tests/libcxx/include/vector @@ -0,0 +1,2786 @@ +// -*- C++ -*- +//===------------------------------ vector --------------------------------===// +// +// 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_VECTOR +#define _LIBCPP_VECTOR + +/* + vector synopsis + +namespace std +{ + +template <class T, class Allocator = allocator<T> > +class vector +{ +public: + typedef T value_type; + typedef Allocator allocator_type; + typedef typename allocator_type::reference reference; + typedef typename allocator_type::const_reference const_reference; + typedef implementation-defined iterator; + typedef implementation-defined const_iterator; + 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 std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + + explicit vector(const allocator_type& = allocator_type()); + explicit vector(size_type n); + vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); + template <class InputIterator> + vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); + vector(const vector& x); + vector(vector&& x); + vector(initializer_list<value_type> il); + vector(initializer_list<value_type> il, const allocator_type& a); + ~vector(); + vector& operator=(const vector& x); + vector& operator=(vector&& x); + vector& operator=(initializer_list<value_type> il); + template <class InputIterator> + void assign(InputIterator first, InputIterator last); + void assign(size_type n, const value_type& u); + void assign(initializer_list<value_type> il); + + 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; + + size_type size() const; + size_type max_size() const; + size_type capacity() const; + bool empty() const; + void reserve(size_type n); + void shrink_to_fit(); + + reference operator[](size_type n); + const_reference operator[](size_type n) const; + reference at(size_type n); + const_reference at(size_type n) const; + + reference front(); + const_reference front() const; + reference back(); + const_reference back() const; + + value_type* data(); + const value_type* data() const; + + void push_back(const value_type& x); + void push_back(value_type&& x); + template <class... Args> + void emplace_back(Args&&... args); + void pop_back(); + + 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 InputIterator> + iterator insert(const_iterator position, InputIterator first, InputIterator last); + iterator insert(const_iterator position, initializer_list<value_type> il); + + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); + + void clear(); + + void resize(size_type sz); + void resize(size_type sz, const value_type& c); + + void swap(vector&); + + bool __invariants() const; +}; + +template <class Allocator = allocator<T> > +class vector<bool, Allocator> +{ +public: + typedef bool value_type; + typedef Allocator allocator_type; + typedef implementation-defined iterator; + typedef implementation-defined const_iterator; + typedef typename allocator_type::size_type size_type; + typedef typename allocator_type::difference_type difference_type; + typedef iterator pointer; + typedef const_iterator const_pointer; + typedef std::reverse_iterator<iterator> reverse_iterator; + typedef std::reverse_iterator<const_iterator> const_reverse_iterator; + + class reference + { + public: + reference(const reference&); + operator bool() const; + reference& operator=(const bool x); + reference& operator=(const reference& x); + iterator operator&() const; + void flip(); + }; + + class const_reference + { + public: + const_reference(const reference&); + operator bool() const; + const_iterator operator&() const; + }; + + explicit vector(const allocator_type& = allocator_type()); + explicit vector(size_type n, const value_type& value = value_type(), const allocator_type& = allocator_type()); + template <class InputIterator> + vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); + vector(const vector& x); + vector(vector&& x); + vector(initializer_list<value_type> il); + vector(initializer_list<value_type> il, const allocator_type& a); + ~vector(); + vector& operator=(const vector& x); + vector& operator=(vector&& x); + vector& operator=(initializer_list<value_type> il); + template <class InputIterator> + void assign(InputIterator first, InputIterator last); + void assign(size_type n, const value_type& u); + void assign(initializer_list<value_type> il); + + 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; + + size_type size() const; + size_type max_size() const; + size_type capacity() const; + bool empty() const; + void reserve(size_type n); + void shrink_to_fit(); + + reference operator[](size_type n); + const_reference operator[](size_type n) const; + reference at(size_type n); + const_reference at(size_type n) const; + + reference front(); + const_reference front() const; + reference back(); + const_reference back() const; + + void push_back(const value_type& x); + void pop_back(); + + iterator insert(const_iterator position, const value_type& x); + iterator insert(const_iterator position, size_type n, const value_type& x); + template <class InputIterator> + iterator insert(const_iterator position, InputIterator first, InputIterator last); + iterator insert(const_iterator position, initializer_list<value_type> il); + + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); + + void clear(); + + void resize(size_type sz); + void resize(size_type sz, value_type x); + + void swap(vector&); + void flip(); + + bool __invariants() const; +}; + +template <class Allocator> struct hash<std::vector<bool, Allocator>>; + +template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); +template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); +template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); +template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); +template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); +template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); + +template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y); + +} // std + +*/ + +#include <__config> +#include <__bit_reference> +#include <type_traits> +#include <climits> +#include <limits> +#include <initializer_list> +#include <memory> +#include <stdexcept> +#include <algorithm> +#include <cstring> +#include <__split_buffer> +#include <__functional_base> +#if defined(_LIBCPP_DEBUG) || defined(_LIBCPP_NO_EXCEPTIONS) + #include <cassert> +#endif + +#pragma GCC system_header + +_LIBCPP_BEGIN_NAMESPACE_STD + +template <bool> +class __vector_base_common +{ +protected: + _LIBCPP_ALWAYS_INLINE __vector_base_common() {} + void __throw_length_error() const; + void __throw_out_of_range() const; +}; + +template <bool __b> +void +__vector_base_common<__b>::__throw_length_error() const +{ +#ifndef _LIBCPP_NO_EXCEPTIONS + throw length_error("vector"); +#else + assert(!"vector length_error"); +#endif +} + +template <bool __b> +void +__vector_base_common<__b>::__throw_out_of_range() const +{ +#ifndef _LIBCPP_NO_EXCEPTIONS + throw out_of_range("vector"); +#else + assert(!"vector out_of_range"); +#endif +} + +extern template class __vector_base_common<true>; + +template <class _Tp, class _Allocator> +class __vector_base + : protected __vector_base_common<true> +{ +protected: + typedef _Tp value_type; + typedef _Allocator allocator_type; + typedef allocator_traits<allocator_type> __alloc_traits; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef typename __alloc_traits::size_type size_type; + typedef typename __alloc_traits::difference_type difference_type; + typedef typename __alloc_traits::pointer pointer; + typedef typename __alloc_traits::const_pointer const_pointer; + typedef pointer iterator; + typedef const_pointer const_iterator; + + pointer __begin_; + pointer __end_; + __compressed_pair<pointer, allocator_type> __end_cap_; + + _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __end_cap_.second();} + _LIBCPP_INLINE_VISIBILITY const allocator_type& __alloc() const {return __end_cap_.second();} + _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() {return __end_cap_.first();} + _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const {return __end_cap_.first();} + + _LIBCPP_INLINE_VISIBILITY __vector_base(); + _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a); + ~__vector_base(); + + _LIBCPP_INLINE_VISIBILITY void clear() {__destruct_at_end(__begin_);} + _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __begin_);} + + _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(const_pointer __new_last) + {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());} + _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(const_pointer __new_last, false_type); + _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(const_pointer __new_last, true_type); + + _LIBCPP_INLINE_VISIBILITY + void __copy_assign_alloc(const __vector_base& __c) + {__copy_assign_alloc(__c, integral_constant<bool, + __alloc_traits::propagate_on_container_copy_assignment::value>());} + + _LIBCPP_INLINE_VISIBILITY + void __move_assign_alloc(__vector_base& __c) + {__move_assign_alloc(__c, integral_constant<bool, + __alloc_traits::propagate_on_container_move_assignment::value>());} + + _LIBCPP_INLINE_VISIBILITY + static void __swap_alloc(allocator_type& __x, allocator_type& __y) + {__swap_alloc(__x, __y, integral_constant<bool, + __alloc_traits::propagate_on_container_swap::value>());} +private: + _LIBCPP_INLINE_VISIBILITY + void __copy_assign_alloc(const __vector_base& __c, true_type) + { + if (__alloc() != __c.__alloc()) + { + clear(); + __alloc_traits::deallocate(__alloc(), __begin_, capacity()); + __begin_ = __end_ = __end_cap() = nullptr; + } + __alloc() = __c.__alloc(); + } + + _LIBCPP_INLINE_VISIBILITY + void __copy_assign_alloc(const __vector_base& __c, false_type) + {} + + _LIBCPP_INLINE_VISIBILITY + void __move_assign_alloc(const __vector_base& __c, true_type) + { + __alloc() = _STD::move(__c.__alloc()); + } + + _LIBCPP_INLINE_VISIBILITY + void __move_assign_alloc(const __vector_base& __c, false_type) + {} + + _LIBCPP_INLINE_VISIBILITY + static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type) + { + using _STD::swap; + swap(__x, __y); + } + _LIBCPP_INLINE_VISIBILITY + static void __swap_alloc(allocator_type& __x, allocator_type& __y, false_type) + {} +}; + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +void +__vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, false_type) +{ + while (__new_last < __end_) + __alloc_traits::destroy(__alloc(), const_cast<pointer>(--__end_)); +} + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +void +__vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, true_type) +{ + __end_ = const_cast<pointer>(__new_last); +} + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +__vector_base<_Tp, _Allocator>::__vector_base() + : __begin_(0), + __end_(0), + __end_cap_(0) +{ +} + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a) + : __begin_(0), + __end_(0), + __end_cap_(0, __a) +{ +} + +template <class _Tp, class _Allocator> +__vector_base<_Tp, _Allocator>::~__vector_base() +{ + if (__begin_ != 0) + { + clear(); + __alloc_traits::deallocate(__alloc(), __begin_, capacity()); + } +} + +template <class _Tp, class _Allocator = allocator<_Tp> > +class _LIBCPP_VISIBLE vector + : private __vector_base<_Tp, _Allocator> +{ +private: + typedef __vector_base<_Tp, _Allocator> __base; +public: + typedef vector __self; + typedef _Tp value_type; + typedef _Allocator allocator_type; + typedef typename __base::__alloc_traits __alloc_traits; + typedef typename __base::reference reference; + typedef typename __base::const_reference const_reference; + typedef typename __base::size_type size_type; + typedef typename __base::difference_type difference_type; + typedef typename __base::pointer pointer; + typedef typename __base::const_pointer const_pointer; +#ifdef _LIBCPP_DEBUG + typedef __debug_iter<vector, pointer> iterator; + typedef __debug_iter<vector, const_pointer> const_iterator; + + friend class __debug_iter<vector, pointer>; + friend class __debug_iter<vector, const_pointer>; + + pair<iterator*, const_iterator*> __iterator_list_; + + _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;} + _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;} +#elif defined(_LIBCPP_RAW_ITERATORS) + typedef pointer iterator; + typedef const_pointer const_iterator; +#else // defined(_LIBCPP_RAW_ITERATORS) + typedef __wrap_iter<pointer> iterator; + typedef __wrap_iter<const_pointer> const_iterator; +#endif // defined(_LIBCPP_RAW_ITERATORS) + typedef _STD::reverse_iterator<iterator> reverse_iterator; + typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator; + + _LIBCPP_INLINE_VISIBILITY vector() {} + _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) : __base(__a) {} + explicit vector(size_type __n); + vector(size_type __n, const_reference __x); + vector(size_type __n, const_reference __x, const allocator_type& __a); + template <class _InputIterator> + vector(_InputIterator __first, _InputIterator __last, + typename enable_if<__is_input_iterator <_InputIterator>::value && + !__is_forward_iterator<_InputIterator>::value>::type* = 0); + template <class _InputIterator> + vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, + typename enable_if<__is_input_iterator <_InputIterator>::value && + !__is_forward_iterator<_InputIterator>::value>::type* = 0); + template <class _ForwardIterator> + vector(_ForwardIterator __first, _ForwardIterator __last, + typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); + template <class _ForwardIterator> + vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, + typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); + _LIBCPP_INLINE_VISIBILITY + vector(initializer_list<value_type> __il); + _LIBCPP_INLINE_VISIBILITY + vector(initializer_list<value_type> __il, const allocator_type& __a); +#ifdef _LIBCPP_DEBUG + _LIBCPP_INLINE_VISIBILITY + ~vector() {__invalidate_all_iterators();} +#endif + + vector(const vector& __x); + vector(const vector& __x, const allocator_type& __a); + _LIBCPP_INLINE_VISIBILITY + vector& operator=(const vector& __x); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + vector(vector&& __x); + _LIBCPP_INLINE_VISIBILITY + vector(vector&& __x, const allocator_type& __a); + _LIBCPP_INLINE_VISIBILITY + vector& operator=(vector&& __x); +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + _LIBCPP_INLINE_VISIBILITY + vector& operator=(initializer_list<value_type> __il) + {assign(__il.begin(), __il.end()); return *this;} + + template <class _InputIterator> + typename enable_if + < + __is_input_iterator <_InputIterator>::value && + !__is_forward_iterator<_InputIterator>::value, + void + >::type + assign(_InputIterator __first, _InputIterator __last); + template <class _ForwardIterator> + typename enable_if + < + __is_forward_iterator<_ForwardIterator>::value, + void + >::type + assign(_ForwardIterator __first, _ForwardIterator __last); + + void assign(size_type __n, const_reference __u); + _LIBCPP_INLINE_VISIBILITY + void assign(initializer_list<value_type> __il) + {assign(__il.begin(), __il.end());} + + _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const {return this->__alloc();} + + _LIBCPP_INLINE_VISIBILITY iterator begin(); + _LIBCPP_INLINE_VISIBILITY const_iterator begin() const; + _LIBCPP_INLINE_VISIBILITY iterator end(); + _LIBCPP_INLINE_VISIBILITY const_iterator end() const; + + _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 size_type size() const {return static_cast<size_type>(this->__end_ - this->__begin_);} + _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return __base::capacity();} + _LIBCPP_INLINE_VISIBILITY bool empty() const {return this->__begin_ == this->__end_;} + size_type max_size() const; + void reserve(size_type __n); + void shrink_to_fit(); + + _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); + _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; + reference at(size_type __n); + const_reference at(size_type __n) const; + + _LIBCPP_INLINE_VISIBILITY reference front() {return *this->__begin_;} + _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *this->__begin_;} + _LIBCPP_INLINE_VISIBILITY reference back() {return *(this->__end_ - 1);} + _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(this->__end_ - 1);} + + _LIBCPP_INLINE_VISIBILITY value_type* data() + {return _STD::__to_raw_pointer(this->__begin_);} + _LIBCPP_INLINE_VISIBILITY const value_type* data() const + {return _STD::__to_raw_pointer(this->__begin_);} + + _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + void push_back(value_type&& __x); +#ifndef _LIBCPP_HAS_NO_VARIADICS + template <class... _Args> + void emplace_back(_Args&&... __args); +#endif // _LIBCPP_HAS_NO_VARIADICS +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + void pop_back(); + + iterator insert(const_iterator __position, const_reference __x); +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + iterator insert(const_iterator __position, value_type&& __x); +#ifndef _LIBCPP_HAS_NO_VARIADICS + template <class... _Args> + iterator emplace(const_iterator __position, _Args&&... __args); +#endif // _LIBCPP_HAS_NO_VARIADICS +#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES + iterator insert(const_iterator __position, size_type __n, const_reference __x); + template <class _InputIterator> + typename enable_if + < + __is_input_iterator <_InputIterator>::value && + !__is_forward_iterator<_InputIterator>::value, + iterator + >::type + insert(const_iterator __position, _InputIterator __first, _InputIterator __last); + template <class _ForwardIterator> + typename enable_if + < + __is_forward_iterator<_ForwardIterator>::value, + iterator + >::type + insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); + _LIBCPP_INLINE_VISIBILITY + iterator insert(const_iterator __position, initializer_list<value_type> __il) + {return insert(__position, __il.begin(), __il.end());} + + _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); + iterator erase(const_iterator __first, const_iterator __last); + + _LIBCPP_INLINE_VISIBILITY void clear() {__base::clear();} + + void resize(size_type __sz); + void resize(size_type __sz, const_reference __x); + + void swap(vector&); + + bool __invariants() const; + +private: + _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); + void allocate(size_type __n); + void deallocate(); + _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; + void __construct_at_end(size_type __n); + void __construct_at_end(size_type __n, const_reference __x); + template <class _ForwardIterator> + typename enable_if + < + __is_forward_iterator<_ForwardIterator>::value, + void + >::type + __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); + void __move_construct_at_end(pointer __first, pointer __last); + void __append(size_type __n); + void __append(size_type __n, const_reference __x); + _LIBCPP_INLINE_VISIBILITY + iterator __make_iter(pointer __p); + _LIBCPP_INLINE_VISIBILITY + const_iterator __make_iter(const_pointer __p) const; + void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); + pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); + void __move_range(pointer __from_s, pointer __from_e, pointer __to); + void __move_assign(vector& __c, true_type); + void __move_assign(vector& __c, false_type); +}; + +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) +{ + for (pointer __p = this->__end_; this->__begin_ < __p;) + __v.push_front(_STD::move(*--__p)); + _STD::swap(this->__begin_, __v.__begin_); + _STD::swap(this->__end_, __v.__end_); + _STD::swap(this->__end_cap(), __v.__end_cap()); + __v.__first_ = __v.__begin_; + __invalidate_all_iterators(); +} + +template <class _Tp, class _Allocator> +typename vector<_Tp, _Allocator>::pointer +vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) +{ + pointer __r = __v.__begin_; + for (pointer __i = __p; this->__begin_ < __i;) + __v.push_front(_STD::move(*--__i)); + for (pointer __i = __p; __i < this->__end_; ++__i) + __v.push_back(_STD::move(*__i)); + _STD::swap(this->__begin_, __v.__begin_); + _STD::swap(this->__end_, __v.__end_); + _STD::swap(this->__end_cap(), __v.__end_cap()); + __v.__first_ = __v.__begin_; + __invalidate_all_iterators(); + return __r; +} + +// Allocate space for __n objects +// throws length_error if __n > max_size() +// throws (probably bad_alloc) if memory run out +// Precondition: __begin_ == __end_ == __end_cap() == 0 +// Precondition: __n > 0 +// Postcondition: capacity() == __n +// Postcondition: size() == 0 +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::allocate(size_type __n) +{ + if (__n > max_size()) + this->__throw_length_error(); + this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); + this->__end_cap() = this->__begin_ + __n; +} + +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::deallocate() +{ + if (this->__begin_ != 0) + { + clear(); + __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); + __invalidate_all_iterators(); + this->__begin_ = this->__end_ = this->__end_cap() = 0; + } +} + +template <class _Tp, class _Allocator> +typename vector<_Tp, _Allocator>::size_type +vector<_Tp, _Allocator>::max_size() const +{ + return _STD::min(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always +} + +// Precondition: __new_size > capacity() +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +typename vector<_Tp, _Allocator>::size_type +vector<_Tp, _Allocator>::__recommend(size_type __new_size) const +{ + const size_type __ms = max_size(); + if (__new_size > __ms) + this->__throw_length_error(); + const size_type __cap = capacity(); + if (__cap >= __ms / 2) + return __ms; + return _STD::max(2*__cap, __new_size); +} + +// Default constructs __n objects starting at __end_ +// throws if construction throws +// Precondition: __n > 0 +// Precondition: size() + __n <= capacity() +// Postcondition: size() == size() + __n +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::__construct_at_end(size_type __n) +{ + allocator_type& __a = this->__alloc(); + do + { + __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_)); + ++this->__end_; + --__n; + } while (__n > 0); +} + +// Copy constructs __n objects starting at __end_ from __x +// throws if construction throws +// Precondition: __n > 0 +// Precondition: size() + __n <= capacity() +// Postcondition: size() == old size() + __n +// Postcondition: [i] == __x for all i in [size() - __n, __n) +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +void +vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) +{ + allocator_type& __a = this->__alloc(); + do + { + __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), __x); + ++this->__end_; + --__n; + } while (__n > 0); +} + +template <class _Tp, class _Allocator> +template <class _ForwardIterator> +typename enable_if +< + __is_forward_iterator<_ForwardIterator>::value, + void +>::type +vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) +{ + allocator_type& __a = this->__alloc(); + for (; __first != __last; ++__first) + { + __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), *__first); + ++this->__end_; + } +} + +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last) +{ + allocator_type& __a = this->__alloc(); + for (; __first != __last; ++__first) + { + __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), + _STD::move(*__first)); + ++this->__end_; + } +} + +// Default constructs __n objects starting at __end_ +// throws if construction throws +// Postcondition: size() == size() + __n +// Exception safety: strong but assumes move ctor doesn't throw (copy ctor can) +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::__append(size_type __n) +{ + if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) + this->__construct_at_end(__n); + else + { + allocator_type& __a = this->__alloc(); + __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); + __v.__construct_at_end(__n); + __swap_out_circular_buffer(__v); + } +} + +// Default constructs __n objects starting at __end_ +// throws if construction throws +// Postcondition: size() == size() + __n +// Exception safety: strong but assumes move ctor doesn't throw (copy ctor can) +template <class _Tp, class _Allocator> +void +vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) +{ + if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) + this->__construct_at_end(__n, __x); + else + { + allocator_type& __a = this->__alloc(); + __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); + __v.__construct_at_end(__n, __x); + __swap_out_circular_buffer(__v); + } +} + +template <class _Tp, class _Allocator> +vector<_Tp, _Allocator>::vector(size_type __n) +{ + if (__n > 0) + { + allocate(__n); + __construct_at_end(__n); + } +} + +template <class _Tp, class _Allocator> +vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) +{ + if (__n > 0) + { + allocate(__n); + __construct_at_end(__n, __x); + } +} + +template <class _Tp, class _Allocator> +vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) + : __base(__a) +{ + if (__n > 0) + { + allocate(__n); + __construct_at_end(__n, __x); + } +} + +template <class _Tp, class _Allocator> +template <class _InputIterator> +vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, + typename enable_if<__is_input_iterator <_InputIterator>::value && + !__is_forward_iterator<_InputIterator>::value>::type*) +{ + for (; __first != __last; ++__first) + push_back(*__first); +} + +template <class _Tp, class _Allocator> +template <class _InputIterator> +vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, + typename enable_if<__is_input_iterator <_InputIterator>::value && + !__is_forward_iterator<_InputIterator>::value>::type*) + : __base(__a) +{ + for (; __first != __last; ++__first) + push_back(*__first); +} + +template <class _Tp, class _Allocator> +template <class _ForwardIterator> +vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, + typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) +{ + size_type __n = static_cast<size_type>(_STD::distance(__first, __last)); + if (__n > 0) + { + allocate(__n); + __construct_at_end(__first, __last); + } +} + +template <class _Tp, class _Allocator> +template <class _ForwardIterator> +vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, + typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) + : __base(__a) +{ + size_type __n = static_cast<size_type>(_STD::distance(__first, __last)); + if (__n > 0) + { + allocate(__n); + __construct_at_end(__first, __last); + } +} + +template <class _Tp, class _Allocator> +vector<_Tp, _Allocator>::vector(const vector& __x) + : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) +{ + size_type __n = __x.size(); + if (__n > 0) + { + allocate(__n); + __construct_at_end(__x.__begin_, __x.__end_); + } +} + +template <class _Tp, class _Allocator> +vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) + : __base(__a) +{ + size_type __n = __x.size(); + if (__n > 0) + { + allocate(__n); + __construct_at_end(__x.__begin_, __x.__end_); + } +} + +#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +vector<_Tp, _Allocator>::vector(vector&& __x) + : __base(_STD::move(__x.__alloc())) +{ + this->__begin_ = __x.__begin_; + this->__end_ = __x.__end_; + this->__end_cap() = __x.__end_cap(); + __x.__begin_ = __x.__end_ = __x.__end_cap() = 0; + __x.__invalidate_all_iterators(); +} + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) + : __base(__a) +{ + if (__a == __x.__alloc()) + { + this->__begin_ = __x.__begin_; + this->__end_ = __x.__end_; + this->__end_cap() = __x.__end_cap(); + __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; + __x.__invalidate_all_iterators(); + } + else + { + typedef move_iterator<iterator> _I; + assign(_I(__x.begin()), _I(__x.end())); + } +} + +template <class _Tp, class _Allocator> +_LIBCPP_INLINE_VISIBILITY inline +vector<_Tp, _Al |