diff options
Diffstat (limited to 'tests/libcxx/include/deque')
| -rw-r--r-- | tests/libcxx/include/deque | 2774 |
1 files changed, 0 insertions, 2774 deletions
diff --git a/tests/libcxx/include/deque b/tests/libcxx/include/deque deleted file mode 100644 index 9bf301c9..00000000 --- a/tests/libcxx/include/deque +++ /dev/null @@ -1,2774 +0,0 @@ -// -*- C++ -*- -//===---------------------------- deque -----------------------------------===// -// -// 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_DEQUE -#define _LIBCPP_DEQUE - -/* - deque synopsis - -namespace std -{ - -template <class T, class Allocator = allocator<T> > -class deque -{ -public: - // types: - 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; - - // construct/copy/destroy: - deque(); - explicit deque(const allocator_type& a); - explicit deque(size_type n); - deque(size_type n, const value_type& v); - deque(size_type n, const value_type& v, const allocator_type& a); - template <class InputIterator> - deque(InputIterator f, InputIterator l); - template <class InputIterator> - deque(InputIterator f, InputIterator l, const allocator_type& a); - deque(const deque& c); - deque(deque&& c); - deque(initializer_list<value_type> il, const Allocator& a = allocator_type()); - deque(const deque& c, const allocator_type& a); - deque(deque&& c, const allocator_type& a); - ~deque(); - - deque& operator=(const deque& c); - deque& operator=(deque&& c); - deque& operator=(initializer_list<value_type> il); - - template <class InputIterator> - void assign(InputIterator f, InputIterator l); - void assign(size_type n, const value_type& v); - void assign(initializer_list<value_type> il); - - allocator_type get_allocator() const; - - // 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: - size_type size() const; - size_type max_size() const; - void resize(size_type n); - void resize(size_type n, const value_type& v); - void shrink_to_fit(); - bool empty() const; - - // element access: - reference operator[](size_type i); - const_reference operator[](size_type i) const; - reference at(size_type i); - const_reference at(size_type i) const; - reference front(); - const_reference front() const; - reference back(); - const_reference back() const; - - // modifiers: - void push_front(const value_type& v); - void push_front(value_type&& v); - void push_back(const value_type& v); - void push_back(value_type&& v); - 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); - iterator insert(const_iterator p, const value_type& v); - iterator insert(const_iterator p, value_type&& v); - iterator insert(const_iterator p, size_type n, const value_type& v); - template <class InputIterator> - iterator insert (const_iterator p, InputIterator f, InputIterator l); - iterator insert(const_iterator p, initializer_list<value_type> il); - void pop_front(); - void pop_back(); - iterator erase(const_iterator p); - iterator erase(const_iterator f, const_iterator l); - void swap(deque& c); - void clear(); -}; - -template <class T, class Allocator> - bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y); -template <class T, class Allocator> - bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); -template <class T, class Allocator> - bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); -template <class T, class Allocator> - bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); -template <class T, class Allocator> - bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); -template <class T, class Allocator> - bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); - -// specialized algorithms: -template <class T, class Allocator> - void swap(deque<T,Allocator>& x, deque<T,Allocator>& y); - -} // std - -*/ - -#pragma GCC system_header - -#include <__config> -#include <__split_buffer> -#include <type_traits> -#include <initializer_list> -#include <iterator> -#include <algorithm> -#include <stdexcept> - -_LIBCPP_BEGIN_NAMESPACE_STD - -template <class _Tp, class _Allocator> class __deque_base; - -template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, - class _DiffType, _DiffType _BlockSize> -class _LIBCPP_VISIBLE __deque_iterator; - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy_backward(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move_backward(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - -template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, - class _DiffType, _DiffType _BlockSize> -class _LIBCPP_VISIBLE __deque_iterator -{ - typedef _MapPointer __map_iterator; -public: - typedef _Pointer pointer; - typedef _DiffType difference_type; -private: - __map_iterator __m_iter_; - pointer __ptr_; - - static const difference_type __block_size = _BlockSize; -public: - typedef _ValueType value_type; - typedef random_access_iterator_tag iterator_category; - typedef _Reference reference; - - _LIBCPP_INLINE_VISIBILITY __deque_iterator() {} - - template <class _P, class _R, class _MP> - _LIBCPP_INLINE_VISIBILITY - __deque_iterator(const __deque_iterator<value_type, _P, _R, _MP, difference_type, __block_size>& __it, - typename enable_if<is_convertible<_P, pointer>::value>::type* = 0) - : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {} - - _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;} - _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;} - - _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++() - { - if (++__ptr_ - *__m_iter_ == __block_size) - { - ++__m_iter_; - __ptr_ = *__m_iter_; - } - return *this; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int) - { - __deque_iterator __tmp = *this; - ++(*this); - return __tmp; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--() - { - if (__ptr_ == *__m_iter_) - { - --__m_iter_; - __ptr_ = *__m_iter_ + __block_size; - } - --__ptr_; - return *this; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int) - { - __deque_iterator __tmp = *this; - --(*this); - return __tmp; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n) - { - if (__n != 0) - { - __n += __ptr_ - *__m_iter_; - if (__n > 0) - { - __m_iter_ += __n / __block_size; - __ptr_ = *__m_iter_ + __n % __block_size; - } - else // (__n < 0) - { - difference_type __z = __block_size - 1 - __n; - __m_iter_ -= __z / __block_size; - __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size); - } - } - return *this; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n) - { - return *this += -__n; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const - { - __deque_iterator __t(*this); - __t += __n; - return __t; - } - - _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const - { - __deque_iterator __t(*this); - __t -= __n; - return __t; - } - - _LIBCPP_INLINE_VISIBILITY - friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it) - {return __it + __n;} - - _LIBCPP_INLINE_VISIBILITY - friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y) - { - if (__x != __y) - return (__x.__m_iter_ - __y.__m_iter_) * __block_size - + (__x.__ptr_ - *__x.__m_iter_) - - (__y.__ptr_ - *__y.__m_iter_); - return 0; - } - - _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const - {return *(*this + __n);} - - _LIBCPP_INLINE_VISIBILITY friend - bool operator==(const __deque_iterator& __x, const __deque_iterator& __y) - {return __x.__ptr_ == __y.__ptr_;} - - _LIBCPP_INLINE_VISIBILITY friend - bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y) - {return !(__x == __y);} - - _LIBCPP_INLINE_VISIBILITY friend - bool operator<(const __deque_iterator& __x, const __deque_iterator& __y) - {return __x.__m_iter_ < __y.__m_iter_ || - (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);} - - _LIBCPP_INLINE_VISIBILITY friend - bool operator>(const __deque_iterator& __x, const __deque_iterator& __y) - {return __y < __x;} - - _LIBCPP_INLINE_VISIBILITY friend - bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y) - {return !(__y < __x);} - - _LIBCPP_INLINE_VISIBILITY friend - bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y) - {return !(__x < __y);} - -private: - _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) - : __m_iter_(__m), __ptr_(__p) {} - - template <class _Tp, class _A> friend class __deque_base; - template <class _Tp, class _A> friend class _LIBCPP_VISIBLE deque; - template <class _V, class _P, class _R, class _MP, class _D, _D> - friend class _LIBCPP_VISIBLE __deque_iterator; - - template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - copy(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> - friend - _OutputIterator - copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - - template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - copy_backward(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> - friend - _OutputIterator - copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - - template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - move(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> - friend - _OutputIterator - move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); - - template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - move_backward(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> - friend - _OutputIterator - move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r); - - template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> - friend - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> - move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); -}; - -// copy - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) -{ - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; - while (__f != __l) - { - pointer __rb = __r.__ptr_; - pointer __re = *__r.__m_iter_ + _B2; - difference_type __bs = __re - __rb; - difference_type __n = __l - __f; - _RAIter __m = __l; - if (__n > __bs) - { - __n = __bs; - __m = __f + __n; - } - _STD::copy(__f, __m, __rb); - __f = __m; - __r += __n; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - pointer __fb = __f.__ptr_; - pointer __fe = *__f.__m_iter_ + _B1; - difference_type __bs = __fe - __fb; - if (__bs > __n) - { - __bs = __n; - __fe = __fb + __bs; - } - __r = _STD::copy(__fb, __fe, __r); - __n -= __bs; - __f += __bs; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - pointer __fb = __f.__ptr_; - pointer __fe = *__f.__m_iter_ + _B1; - difference_type __bs = __fe - __fb; - if (__bs > __n) - { - __bs = __n; - __fe = __fb + __bs; - } - __r = _STD::copy(__fb, __fe, __r); - __n -= __bs; - __f += __bs; - } - return __r; -} - -// copy_backward - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy_backward(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) -{ - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; - while (__f != __l) - { - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = prev(__r); - pointer __rb = *__rp.__m_iter_; - pointer __re = __rp.__ptr_ + 1; - difference_type __bs = __re - __rb; - difference_type __n = __l - __f; - _RAIter __m = __f; - if (__n > __bs) - { - __n = __bs; - __m = __l - __n; - } - _STD::copy_backward(__m, __l, __re); - __l = __m; - __r -= __n; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - --__l; - pointer __lb = *__l.__m_iter_; - pointer __le = __l.__ptr_ + 1; - difference_type __bs = __le - __lb; - if (__bs > __n) - { - __bs = __n; - __lb = __le - __bs; - } - __r = _STD::copy_backward(__lb, __le, __r); - __n -= __bs; - __l -= __bs - 1; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - --__l; - pointer __lb = *__l.__m_iter_; - pointer __le = __l.__ptr_ + 1; - difference_type __bs = __le - __lb; - if (__bs > __n) - { - __bs = __n; - __lb = __le - __bs; - } - __r = _STD::copy_backward(__lb, __le, __r); - __n -= __bs; - __l -= __bs - 1; - } - return __r; -} - -// move - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) -{ - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; - while (__f != __l) - { - pointer __rb = __r.__ptr_; - pointer __re = *__r.__m_iter_ + _B2; - difference_type __bs = __re - __rb; - difference_type __n = __l - __f; - _RAIter __m = __l; - if (__n > __bs) - { - __n = __bs; - __m = __f + __n; - } - _STD::move(__f, __m, __rb); - __f = __m; - __r += __n; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - pointer __fb = __f.__ptr_; - pointer __fe = *__f.__m_iter_ + _B1; - difference_type __bs = __fe - __fb; - if (__bs > __n) - { - __bs = __n; - __fe = __fb + __bs; - } - __r = _STD::move(__fb, __fe, __r); - __n -= __bs; - __f += __bs; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - pointer __fb = __f.__ptr_; - pointer __fe = *__f.__m_iter_ + _B1; - difference_type __bs = __fe - __fb; - if (__bs > __n) - { - __bs = __n; - __fe = __fb + __bs; - } - __r = _STD::move(__fb, __fe, __r); - __n -= __bs; - __f += __bs; - } - return __r; -} - -// move_backward - -template <class _RAIter, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move_backward(_RAIter __f, - _RAIter __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, - typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) -{ - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; - typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; - while (__f != __l) - { - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = prev(__r); - pointer __rb = *__rp.__m_iter_; - pointer __re = __rp.__ptr_ + 1; - difference_type __bs = __re - __rb; - difference_type __n = __l - __f; - _RAIter __m = __f; - if (__n > __bs) - { - __n = __bs; - __m = __l - __n; - } - _STD::move_backward(__m, __l, __re); - __l = __m; - __r -= __n; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _OutputIterator> -_OutputIterator -move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - _OutputIterator __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - --__l; - pointer __lb = *__l.__m_iter_; - pointer __le = __l.__ptr_ + 1; - difference_type __bs = __le - __lb; - if (__bs > __n) - { - __bs = __n; - __lb = __le - __bs; - } - __r = _STD::move_backward(__lb, __le, __r); - __n -= __bs; - __l -= __bs - 1; - } - return __r; -} - -template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, - class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> -__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> -move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, - __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, - __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) -{ - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; - typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; - difference_type __n = __l - __f; - while (__n > 0) - { - --__l; - pointer __lb = *__l.__m_iter_; - pointer __le = __l.__ptr_ + 1; - difference_type __bs = __le - __lb; - if (__bs > __n) - { - __bs = __n; - __lb = __le - __bs; - } - __r = _STD::move_backward(__lb, __le, __r); - __n -= __bs; - __l -= __bs - 1; - } - return __r; -} - -template <bool> -class __deque_base_common -{ -protected: - void __throw_length_error() const; - void __throw_out_of_range() const; -}; - -template <bool __b> -void -__deque_base_common<__b>::__throw_length_error() const -{ -#ifndef _LIBCPP_NO_EXCEPTIONS - throw length_error("deque"); -#endif -} - -template <bool __b> -void -__deque_base_common<__b>::__throw_out_of_range() const -{ -#ifndef _LIBCPP_NO_EXCEPTIONS - throw out_of_range("deque"); -#endif -} - -template <class _Tp, class _Allocator> -class __deque_base - : protected __deque_base_common<true> -{ - __deque_base(const __deque_base& __c); - __deque_base& operator=(const __deque_base& __c); -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; - - static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16; - - typedef typename __alloc_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind_alloc<pointer> -#else - rebind_alloc<pointer>::other -#endif - __pointer_allocator; - typedef allocator_traits<__pointer_allocator> __map_traits; - typedef typename __map_traits::pointer __map_pointer; - typedef typename __map_traits::const_pointer __map_const_pointer; - typedef __split_buffer<pointer, __pointer_allocator> __map; - - typedef __deque_iterator<value_type, pointer, reference, __map_pointer, - difference_type, __block_size> iterator; - typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, - difference_type, __block_size> const_iterator; - - __map __map_; - size_type __start_; - __compressed_pair<size_type, allocator_type> __size_; - - iterator begin(); - const_iterator begin() const; - iterator end(); - const_iterator end() const; - - _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();} - _LIBCPP_INLINE_VISIBILITY const size_type& size() const {return __size_.first();} - _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();} - _LIBCPP_INLINE_VISIBILITY const allocator_type& __alloc() const {return __size_.second();} - - __deque_base(); - explicit __deque_base(const allocator_type& __a); - ~__deque_base(); - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - - __deque_base(__deque_base&& __c); - __deque_base(__deque_base&& __c, const allocator_type& __a); - -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - void swap(__deque_base& __c); - void clear(); - - bool __invariants() const; - - _LIBCPP_INLINE_VISIBILITY - void __move_assign(__deque_base& __c) - { - __map_ = _STD::move(__c.__map_); - __start_ = __c.__start_; - size() = __c.size(); - __move_assign_alloc(__c); - __c.__start_ = __c.size() = 0; - } - - _LIBCPP_INLINE_VISIBILITY - void __move_assign_alloc(__deque_base& __c) - {__move_assign_alloc(__c, integral_constant<bool, - __alloc_traits::propagate_on_container_move_assignment::value>());} - -private: - _LIBCPP_INLINE_VISIBILITY - void __move_assign_alloc(const __deque_base& __c, true_type) - { - __alloc() = _STD::move(__c.__alloc()); - } - - _LIBCPP_INLINE_VISIBILITY - void __move_assign_alloc(const __deque_base& __c, false_type) - {} - - _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>());} |