deque revision 278724
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===---------------------------- deque -----------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_DEQUE 12227825Stheraven#define _LIBCPP_DEQUE 13227825Stheraven 14227825Stheraven/* 15227825Stheraven deque synopsis 16227825Stheraven 17227825Stheravennamespace std 18227825Stheraven{ 19227825Stheraven 20227825Stheraventemplate <class T, class Allocator = allocator<T> > 21227825Stheravenclass deque 22227825Stheraven{ 23227825Stheravenpublic: 24227825Stheraven // types: 25227825Stheraven typedef T value_type; 26227825Stheraven typedef Allocator allocator_type; 27227825Stheraven 28227825Stheraven typedef typename allocator_type::reference reference; 29227825Stheraven typedef typename allocator_type::const_reference const_reference; 30227825Stheraven typedef implementation-defined iterator; 31227825Stheraven typedef implementation-defined const_iterator; 32227825Stheraven typedef typename allocator_type::size_type size_type; 33227825Stheraven typedef typename allocator_type::difference_type difference_type; 34227825Stheraven 35227825Stheraven typedef typename allocator_type::pointer pointer; 36227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 37227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 38227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 39227825Stheraven 40227825Stheraven // construct/copy/destroy: 41227825Stheraven deque() noexcept(is_nothrow_default_constructible<allocator_type>::value); 42227825Stheraven explicit deque(const allocator_type& a); 43227825Stheraven explicit deque(size_type n); 44262801Sdim explicit deque(size_type n, const allocator_type& a); // C++14 45227825Stheraven deque(size_type n, const value_type& v); 46227825Stheraven deque(size_type n, const value_type& v, const allocator_type& a); 47227825Stheraven template <class InputIterator> 48227825Stheraven deque(InputIterator f, InputIterator l); 49227825Stheraven template <class InputIterator> 50227825Stheraven deque(InputIterator f, InputIterator l, const allocator_type& a); 51227825Stheraven deque(const deque& c); 52227825Stheraven deque(deque&& c) 53227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 54227825Stheraven deque(initializer_list<value_type> il, const Allocator& a = allocator_type()); 55227825Stheraven deque(const deque& c, const allocator_type& a); 56227825Stheraven deque(deque&& c, const allocator_type& a); 57227825Stheraven ~deque(); 58227825Stheraven 59227825Stheraven deque& operator=(const deque& c); 60227825Stheraven deque& operator=(deque&& c) 61227825Stheraven noexcept( 62227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 63227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 64227825Stheraven deque& operator=(initializer_list<value_type> il); 65227825Stheraven 66227825Stheraven template <class InputIterator> 67227825Stheraven void assign(InputIterator f, InputIterator l); 68227825Stheraven void assign(size_type n, const value_type& v); 69227825Stheraven void assign(initializer_list<value_type> il); 70227825Stheraven 71227825Stheraven allocator_type get_allocator() const noexcept; 72227825Stheraven 73227825Stheraven // iterators: 74227825Stheraven 75227825Stheraven iterator begin() noexcept; 76227825Stheraven const_iterator begin() const noexcept; 77227825Stheraven iterator end() noexcept; 78227825Stheraven const_iterator end() const noexcept; 79227825Stheraven 80227825Stheraven reverse_iterator rbegin() noexcept; 81227825Stheraven const_reverse_iterator rbegin() const noexcept; 82227825Stheraven reverse_iterator rend() noexcept; 83227825Stheraven const_reverse_iterator rend() const noexcept; 84227825Stheraven 85227825Stheraven const_iterator cbegin() const noexcept; 86227825Stheraven const_iterator cend() const noexcept; 87227825Stheraven const_reverse_iterator crbegin() const noexcept; 88227825Stheraven const_reverse_iterator crend() const noexcept; 89227825Stheraven 90227825Stheraven // capacity: 91227825Stheraven size_type size() const noexcept; 92227825Stheraven size_type max_size() const noexcept; 93227825Stheraven void resize(size_type n); 94227825Stheraven void resize(size_type n, const value_type& v); 95227825Stheraven void shrink_to_fit(); 96227825Stheraven bool empty() const noexcept; 97227825Stheraven 98227825Stheraven // element access: 99227825Stheraven reference operator[](size_type i); 100227825Stheraven const_reference operator[](size_type i) const; 101227825Stheraven reference at(size_type i); 102227825Stheraven const_reference at(size_type i) const; 103227825Stheraven reference front(); 104227825Stheraven const_reference front() const; 105227825Stheraven reference back(); 106227825Stheraven const_reference back() const; 107227825Stheraven 108227825Stheraven // modifiers: 109227825Stheraven void push_front(const value_type& v); 110227825Stheraven void push_front(value_type&& v); 111227825Stheraven void push_back(const value_type& v); 112227825Stheraven void push_back(value_type&& v); 113227825Stheraven template <class... Args> void emplace_front(Args&&... args); 114227825Stheraven template <class... Args> void emplace_back(Args&&... args); 115227825Stheraven template <class... Args> iterator emplace(const_iterator p, Args&&... args); 116227825Stheraven iterator insert(const_iterator p, const value_type& v); 117227825Stheraven iterator insert(const_iterator p, value_type&& v); 118227825Stheraven iterator insert(const_iterator p, size_type n, const value_type& v); 119227825Stheraven template <class InputIterator> 120227825Stheraven iterator insert (const_iterator p, InputIterator f, InputIterator l); 121227825Stheraven iterator insert(const_iterator p, initializer_list<value_type> il); 122227825Stheraven void pop_front(); 123227825Stheraven void pop_back(); 124227825Stheraven iterator erase(const_iterator p); 125227825Stheraven iterator erase(const_iterator f, const_iterator l); 126227825Stheraven void swap(deque& c) 127227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 128227825Stheraven __is_nothrow_swappable<allocator_type>::value); 129227825Stheraven void clear() noexcept; 130227825Stheraven}; 131227825Stheraven 132227825Stheraventemplate <class T, class Allocator> 133227825Stheraven bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 134227825Stheraventemplate <class T, class Allocator> 135227825Stheraven bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); 136227825Stheraventemplate <class T, class Allocator> 137227825Stheraven bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 138227825Stheraventemplate <class T, class Allocator> 139227825Stheraven bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); 140227825Stheraventemplate <class T, class Allocator> 141227825Stheraven bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 142227825Stheraventemplate <class T, class Allocator> 143227825Stheraven bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 144227825Stheraven 145227825Stheraven// specialized algorithms: 146227825Stheraventemplate <class T, class Allocator> 147227825Stheraven void swap(deque<T,Allocator>& x, deque<T,Allocator>& y) 148227825Stheraven noexcept(noexcept(x.swap(y))); 149227825Stheraven 150227825Stheraven} // std 151227825Stheraven 152227825Stheraven*/ 153227825Stheraven 154227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 155227825Stheraven#pragma GCC system_header 156227825Stheraven#endif 157227825Stheraven 158227825Stheraven#include <__config> 159227825Stheraven#include <__split_buffer> 160227825Stheraven#include <type_traits> 161227825Stheraven#include <initializer_list> 162227825Stheraven#include <iterator> 163227825Stheraven#include <algorithm> 164227825Stheraven#include <stdexcept> 165227825Stheraven 166232950Stheraven#include <__undef_min_max> 167232950Stheraven 168227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 169227825Stheraven 170227825Stheraventemplate <class _Tp, class _Allocator> class __deque_base; 171227825Stheraven 172227825Stheraventemplate <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 173227825Stheraven class _DiffType, _DiffType _BlockSize> 174262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __deque_iterator; 175227825Stheraven 176227825Stheraventemplate <class _RAIter, 177227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 178227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 179227825Stheravencopy(_RAIter __f, 180227825Stheraven _RAIter __l, 181227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 182227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); 183227825Stheraven 184227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 185227825Stheraven class _OutputIterator> 186227825Stheraven_OutputIterator 187227825Stheravencopy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 188227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 189227825Stheraven _OutputIterator __r); 190227825Stheraven 191227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 192227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 193227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 194227825Stheravencopy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 195227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 196227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 197227825Stheraven 198227825Stheraventemplate <class _RAIter, 199227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 200227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 201227825Stheravencopy_backward(_RAIter __f, 202227825Stheraven _RAIter __l, 203227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 204227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); 205227825Stheraven 206227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 207227825Stheraven class _OutputIterator> 208227825Stheraven_OutputIterator 209227825Stheravencopy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 210227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 211227825Stheraven _OutputIterator __r); 212227825Stheraven 213227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 214227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 215227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 216227825Stheravencopy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 217227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 218227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 219227825Stheraven 220227825Stheraventemplate <class _RAIter, 221227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 222227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 223227825Stheravenmove(_RAIter __f, 224227825Stheraven _RAIter __l, 225227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 226227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); 227227825Stheraven 228227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 229227825Stheraven class _OutputIterator> 230227825Stheraven_OutputIterator 231227825Stheravenmove(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 232227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 233227825Stheraven _OutputIterator __r); 234227825Stheraven 235227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 236227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 237227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 238227825Stheravenmove(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 239227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 240227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 241227825Stheraven 242227825Stheraventemplate <class _RAIter, 243227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 244227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 245227825Stheravenmove_backward(_RAIter __f, 246227825Stheraven _RAIter __l, 247227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 248227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); 249227825Stheraven 250227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 251227825Stheraven class _OutputIterator> 252227825Stheraven_OutputIterator 253227825Stheravenmove_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 254227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 255227825Stheraven _OutputIterator __r); 256227825Stheraven 257227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 258227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 259227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 260227825Stheravenmove_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 261227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 262227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 263227825Stheraven 264227825Stheraventemplate <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 265227825Stheraven class _DiffType, _DiffType _BlockSize> 266262801Sdimclass _LIBCPP_TYPE_VIS_ONLY __deque_iterator 267227825Stheraven{ 268227825Stheraven typedef _MapPointer __map_iterator; 269227825Stheravenpublic: 270227825Stheraven typedef _Pointer pointer; 271227825Stheraven typedef _DiffType difference_type; 272227825Stheravenprivate: 273227825Stheraven __map_iterator __m_iter_; 274227825Stheraven pointer __ptr_; 275227825Stheraven 276227825Stheraven static const difference_type __block_size = _BlockSize; 277227825Stheravenpublic: 278227825Stheraven typedef _ValueType value_type; 279227825Stheraven typedef random_access_iterator_tag iterator_category; 280227825Stheraven typedef _Reference reference; 281227825Stheraven 282262801Sdim _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT 283262801Sdim#if _LIBCPP_STD_VER > 11 284262801Sdim : __m_iter_(nullptr), __ptr_(nullptr) 285262801Sdim#endif 286262801Sdim {} 287227825Stheraven 288232950Stheraven template <class _Pp, class _Rp, class _MP> 289227825Stheraven _LIBCPP_INLINE_VISIBILITY 290232950Stheraven __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, __block_size>& __it, 291232950Stheraven typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT 292227825Stheraven : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {} 293227825Stheraven 294227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;} 295227825Stheraven _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;} 296227825Stheraven 297227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++() 298227825Stheraven { 299227825Stheraven if (++__ptr_ - *__m_iter_ == __block_size) 300227825Stheraven { 301227825Stheraven ++__m_iter_; 302227825Stheraven __ptr_ = *__m_iter_; 303227825Stheraven } 304227825Stheraven return *this; 305227825Stheraven } 306227825Stheraven 307227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int) 308227825Stheraven { 309227825Stheraven __deque_iterator __tmp = *this; 310227825Stheraven ++(*this); 311227825Stheraven return __tmp; 312227825Stheraven } 313227825Stheraven 314227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--() 315227825Stheraven { 316227825Stheraven if (__ptr_ == *__m_iter_) 317227825Stheraven { 318227825Stheraven --__m_iter_; 319227825Stheraven __ptr_ = *__m_iter_ + __block_size; 320227825Stheraven } 321227825Stheraven --__ptr_; 322227825Stheraven return *this; 323227825Stheraven } 324227825Stheraven 325227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int) 326227825Stheraven { 327227825Stheraven __deque_iterator __tmp = *this; 328227825Stheraven --(*this); 329227825Stheraven return __tmp; 330227825Stheraven } 331227825Stheraven 332227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n) 333227825Stheraven { 334227825Stheraven if (__n != 0) 335227825Stheraven { 336227825Stheraven __n += __ptr_ - *__m_iter_; 337227825Stheraven if (__n > 0) 338227825Stheraven { 339227825Stheraven __m_iter_ += __n / __block_size; 340227825Stheraven __ptr_ = *__m_iter_ + __n % __block_size; 341227825Stheraven } 342227825Stheraven else // (__n < 0) 343227825Stheraven { 344227825Stheraven difference_type __z = __block_size - 1 - __n; 345227825Stheraven __m_iter_ -= __z / __block_size; 346227825Stheraven __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size); 347227825Stheraven } 348227825Stheraven } 349227825Stheraven return *this; 350227825Stheraven } 351227825Stheraven 352227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n) 353227825Stheraven { 354227825Stheraven return *this += -__n; 355227825Stheraven } 356227825Stheraven 357227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const 358227825Stheraven { 359227825Stheraven __deque_iterator __t(*this); 360227825Stheraven __t += __n; 361227825Stheraven return __t; 362227825Stheraven } 363227825Stheraven 364227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const 365227825Stheraven { 366227825Stheraven __deque_iterator __t(*this); 367227825Stheraven __t -= __n; 368227825Stheraven return __t; 369227825Stheraven } 370227825Stheraven 371227825Stheraven _LIBCPP_INLINE_VISIBILITY 372227825Stheraven friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it) 373227825Stheraven {return __it + __n;} 374227825Stheraven 375227825Stheraven _LIBCPP_INLINE_VISIBILITY 376227825Stheraven friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y) 377227825Stheraven { 378227825Stheraven if (__x != __y) 379227825Stheraven return (__x.__m_iter_ - __y.__m_iter_) * __block_size 380227825Stheraven + (__x.__ptr_ - *__x.__m_iter_) 381227825Stheraven - (__y.__ptr_ - *__y.__m_iter_); 382227825Stheraven return 0; 383227825Stheraven } 384227825Stheraven 385227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const 386227825Stheraven {return *(*this + __n);} 387227825Stheraven 388227825Stheraven _LIBCPP_INLINE_VISIBILITY friend 389227825Stheraven bool operator==(const __deque_iterator& __x, const __deque_iterator& __y) 390227825Stheraven {return __x.__ptr_ == __y.__ptr_;} 391227825Stheraven 392227825Stheraven _LIBCPP_INLINE_VISIBILITY friend 393227825Stheraven bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y) 394227825Stheraven {return !(__x == __y);} 395227825Stheraven 396227825Stheraven _LIBCPP_INLINE_VISIBILITY friend 397227825Stheraven bool operator<(const __deque_iterator& __x, const __deque_iterator& __y) 398227825Stheraven {return __x.__m_iter_ < __y.__m_iter_ || 399227825Stheraven (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);} 400227825Stheraven 401227825Stheraven _LIBCPP_INLINE_VISIBILITY friend 402227825Stheraven bool operator>(const __deque_iterator& __x, const __deque_iterator& __y) 403227825Stheraven {return __y < __x;} 404227825Stheraven 405227825Stheraven _LIBCPP_INLINE_VISIBILITY friend 406227825Stheraven bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y) 407227825Stheraven {return !(__y < __x);} 408227825Stheraven 409227825Stheraven _LIBCPP_INLINE_VISIBILITY friend 410227825Stheraven bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y) 411227825Stheraven {return !(__x < __y);} 412227825Stheraven 413227825Stheravenprivate: 414227825Stheraven _LIBCPP_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT 415227825Stheraven : __m_iter_(__m), __ptr_(__p) {} 416227825Stheraven 417232950Stheraven template <class _Tp, class _Ap> friend class __deque_base; 418262801Sdim template <class _Tp, class _Ap> friend class _LIBCPP_TYPE_VIS_ONLY deque; 419232950Stheraven template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp> 420262801Sdim friend class _LIBCPP_TYPE_VIS_ONLY __deque_iterator; 421227825Stheraven 422227825Stheraven template <class _RAIter, 423227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 424227825Stheraven friend 425227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 426227825Stheraven copy(_RAIter __f, 427227825Stheraven _RAIter __l, 428227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 429227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); 430227825Stheraven 431227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 432227825Stheraven class _OutputIterator> 433227825Stheraven friend 434227825Stheraven _OutputIterator 435227825Stheraven copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 436227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 437227825Stheraven _OutputIterator __r); 438227825Stheraven 439227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 440227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 441227825Stheraven friend 442227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 443227825Stheraven copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 444227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 445227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 446227825Stheraven 447227825Stheraven template <class _RAIter, 448227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 449227825Stheraven friend 450227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 451227825Stheraven copy_backward(_RAIter __f, 452227825Stheraven _RAIter __l, 453227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 454227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); 455227825Stheraven 456227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 457227825Stheraven class _OutputIterator> 458227825Stheraven friend 459227825Stheraven _OutputIterator 460227825Stheraven copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 461227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 462227825Stheraven _OutputIterator __r); 463227825Stheraven 464227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 465227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 466227825Stheraven friend 467227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 468227825Stheraven copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 469227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 470227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 471227825Stheraven 472227825Stheraven template <class _RAIter, 473227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 474227825Stheraven friend 475227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 476227825Stheraven move(_RAIter __f, 477227825Stheraven _RAIter __l, 478227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 479227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); 480227825Stheraven 481227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 482227825Stheraven class _OutputIterator> 483227825Stheraven friend 484227825Stheraven _OutputIterator 485227825Stheraven move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 486227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 487227825Stheraven _OutputIterator __r); 488227825Stheraven 489227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 490227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 491227825Stheraven friend 492227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 493227825Stheraven move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 494227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 495227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 496227825Stheraven 497227825Stheraven template <class _RAIter, 498227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 499227825Stheraven friend 500227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 501227825Stheraven move_backward(_RAIter __f, 502227825Stheraven _RAIter __l, 503227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 504227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*); 505227825Stheraven 506227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 507227825Stheraven class _OutputIterator> 508227825Stheraven friend 509227825Stheraven _OutputIterator 510227825Stheraven move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 511227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 512227825Stheraven _OutputIterator __r); 513227825Stheraven 514227825Stheraven template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 515227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 516227825Stheraven friend 517227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 518227825Stheraven move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 519227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 520227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 521227825Stheraven}; 522227825Stheraven 523227825Stheraven// copy 524227825Stheraven 525227825Stheraventemplate <class _RAIter, 526227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 527227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 528227825Stheravencopy(_RAIter __f, 529227825Stheraven _RAIter __l, 530227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 531227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) 532227825Stheraven{ 533227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 534227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 535227825Stheraven while (__f != __l) 536227825Stheraven { 537227825Stheraven pointer __rb = __r.__ptr_; 538227825Stheraven pointer __re = *__r.__m_iter_ + _B2; 539227825Stheraven difference_type __bs = __re - __rb; 540227825Stheraven difference_type __n = __l - __f; 541227825Stheraven _RAIter __m = __l; 542227825Stheraven if (__n > __bs) 543227825Stheraven { 544227825Stheraven __n = __bs; 545227825Stheraven __m = __f + __n; 546227825Stheraven } 547227825Stheraven _VSTD::copy(__f, __m, __rb); 548227825Stheraven __f = __m; 549227825Stheraven __r += __n; 550227825Stheraven } 551227825Stheraven return __r; 552227825Stheraven} 553227825Stheraven 554227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 555227825Stheraven class _OutputIterator> 556227825Stheraven_OutputIterator 557227825Stheravencopy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 558227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 559227825Stheraven _OutputIterator __r) 560227825Stheraven{ 561227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 562227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 563227825Stheraven difference_type __n = __l - __f; 564227825Stheraven while (__n > 0) 565227825Stheraven { 566227825Stheraven pointer __fb = __f.__ptr_; 567227825Stheraven pointer __fe = *__f.__m_iter_ + _B1; 568227825Stheraven difference_type __bs = __fe - __fb; 569227825Stheraven if (__bs > __n) 570227825Stheraven { 571227825Stheraven __bs = __n; 572227825Stheraven __fe = __fb + __bs; 573227825Stheraven } 574227825Stheraven __r = _VSTD::copy(__fb, __fe, __r); 575227825Stheraven __n -= __bs; 576227825Stheraven __f += __bs; 577227825Stheraven } 578227825Stheraven return __r; 579227825Stheraven} 580227825Stheraven 581227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 582227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 583227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 584227825Stheravencopy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 585227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 586227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 587227825Stheraven{ 588227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 589227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 590227825Stheraven difference_type __n = __l - __f; 591227825Stheraven while (__n > 0) 592227825Stheraven { 593227825Stheraven pointer __fb = __f.__ptr_; 594227825Stheraven pointer __fe = *__f.__m_iter_ + _B1; 595227825Stheraven difference_type __bs = __fe - __fb; 596227825Stheraven if (__bs > __n) 597227825Stheraven { 598227825Stheraven __bs = __n; 599227825Stheraven __fe = __fb + __bs; 600227825Stheraven } 601227825Stheraven __r = _VSTD::copy(__fb, __fe, __r); 602227825Stheraven __n -= __bs; 603227825Stheraven __f += __bs; 604227825Stheraven } 605227825Stheraven return __r; 606227825Stheraven} 607227825Stheraven 608227825Stheraven// copy_backward 609227825Stheraven 610227825Stheraventemplate <class _RAIter, 611227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 612227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 613227825Stheravencopy_backward(_RAIter __f, 614227825Stheraven _RAIter __l, 615227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 616227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) 617227825Stheraven{ 618227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 619227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 620227825Stheraven while (__f != __l) 621227825Stheraven { 622227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r); 623227825Stheraven pointer __rb = *__rp.__m_iter_; 624227825Stheraven pointer __re = __rp.__ptr_ + 1; 625227825Stheraven difference_type __bs = __re - __rb; 626227825Stheraven difference_type __n = __l - __f; 627227825Stheraven _RAIter __m = __f; 628227825Stheraven if (__n > __bs) 629227825Stheraven { 630227825Stheraven __n = __bs; 631227825Stheraven __m = __l - __n; 632227825Stheraven } 633227825Stheraven _VSTD::copy_backward(__m, __l, __re); 634227825Stheraven __l = __m; 635227825Stheraven __r -= __n; 636227825Stheraven } 637227825Stheraven return __r; 638227825Stheraven} 639227825Stheraven 640227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 641227825Stheraven class _OutputIterator> 642227825Stheraven_OutputIterator 643227825Stheravencopy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 644227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 645227825Stheraven _OutputIterator __r) 646227825Stheraven{ 647227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 648227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 649227825Stheraven difference_type __n = __l - __f; 650227825Stheraven while (__n > 0) 651227825Stheraven { 652227825Stheraven --__l; 653227825Stheraven pointer __lb = *__l.__m_iter_; 654227825Stheraven pointer __le = __l.__ptr_ + 1; 655227825Stheraven difference_type __bs = __le - __lb; 656227825Stheraven if (__bs > __n) 657227825Stheraven { 658227825Stheraven __bs = __n; 659227825Stheraven __lb = __le - __bs; 660227825Stheraven } 661227825Stheraven __r = _VSTD::copy_backward(__lb, __le, __r); 662227825Stheraven __n -= __bs; 663227825Stheraven __l -= __bs - 1; 664227825Stheraven } 665227825Stheraven return __r; 666227825Stheraven} 667227825Stheraven 668227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 669227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 670227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 671227825Stheravencopy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 672227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 673227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 674227825Stheraven{ 675227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 676227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 677227825Stheraven difference_type __n = __l - __f; 678227825Stheraven while (__n > 0) 679227825Stheraven { 680227825Stheraven --__l; 681227825Stheraven pointer __lb = *__l.__m_iter_; 682227825Stheraven pointer __le = __l.__ptr_ + 1; 683227825Stheraven difference_type __bs = __le - __lb; 684227825Stheraven if (__bs > __n) 685227825Stheraven { 686227825Stheraven __bs = __n; 687227825Stheraven __lb = __le - __bs; 688227825Stheraven } 689227825Stheraven __r = _VSTD::copy_backward(__lb, __le, __r); 690227825Stheraven __n -= __bs; 691227825Stheraven __l -= __bs - 1; 692227825Stheraven } 693227825Stheraven return __r; 694227825Stheraven} 695227825Stheraven 696227825Stheraven// move 697227825Stheraven 698227825Stheraventemplate <class _RAIter, 699227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 700227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 701227825Stheravenmove(_RAIter __f, 702227825Stheraven _RAIter __l, 703227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 704227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) 705227825Stheraven{ 706227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 707227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 708227825Stheraven while (__f != __l) 709227825Stheraven { 710227825Stheraven pointer __rb = __r.__ptr_; 711227825Stheraven pointer __re = *__r.__m_iter_ + _B2; 712227825Stheraven difference_type __bs = __re - __rb; 713227825Stheraven difference_type __n = __l - __f; 714227825Stheraven _RAIter __m = __l; 715227825Stheraven if (__n > __bs) 716227825Stheraven { 717227825Stheraven __n = __bs; 718227825Stheraven __m = __f + __n; 719227825Stheraven } 720227825Stheraven _VSTD::move(__f, __m, __rb); 721227825Stheraven __f = __m; 722227825Stheraven __r += __n; 723227825Stheraven } 724227825Stheraven return __r; 725227825Stheraven} 726227825Stheraven 727227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 728227825Stheraven class _OutputIterator> 729227825Stheraven_OutputIterator 730227825Stheravenmove(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 731227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 732227825Stheraven _OutputIterator __r) 733227825Stheraven{ 734227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 735227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 736227825Stheraven difference_type __n = __l - __f; 737227825Stheraven while (__n > 0) 738227825Stheraven { 739227825Stheraven pointer __fb = __f.__ptr_; 740227825Stheraven pointer __fe = *__f.__m_iter_ + _B1; 741227825Stheraven difference_type __bs = __fe - __fb; 742227825Stheraven if (__bs > __n) 743227825Stheraven { 744227825Stheraven __bs = __n; 745227825Stheraven __fe = __fb + __bs; 746227825Stheraven } 747227825Stheraven __r = _VSTD::move(__fb, __fe, __r); 748227825Stheraven __n -= __bs; 749227825Stheraven __f += __bs; 750227825Stheraven } 751227825Stheraven return __r; 752227825Stheraven} 753227825Stheraven 754227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 755227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 756227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 757227825Stheravenmove(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 758227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 759227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 760227825Stheraven{ 761227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 762227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 763227825Stheraven difference_type __n = __l - __f; 764227825Stheraven while (__n > 0) 765227825Stheraven { 766227825Stheraven pointer __fb = __f.__ptr_; 767227825Stheraven pointer __fe = *__f.__m_iter_ + _B1; 768227825Stheraven difference_type __bs = __fe - __fb; 769227825Stheraven if (__bs > __n) 770227825Stheraven { 771227825Stheraven __bs = __n; 772227825Stheraven __fe = __fb + __bs; 773227825Stheraven } 774227825Stheraven __r = _VSTD::move(__fb, __fe, __r); 775227825Stheraven __n -= __bs; 776227825Stheraven __f += __bs; 777227825Stheraven } 778227825Stheraven return __r; 779227825Stheraven} 780227825Stheraven 781227825Stheraven// move_backward 782227825Stheraven 783227825Stheraventemplate <class _RAIter, 784227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 785227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 786227825Stheravenmove_backward(_RAIter __f, 787227825Stheraven _RAIter __l, 788227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 789227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) 790227825Stheraven{ 791227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 792227825Stheraven typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 793227825Stheraven while (__f != __l) 794227825Stheraven { 795227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r); 796227825Stheraven pointer __rb = *__rp.__m_iter_; 797227825Stheraven pointer __re = __rp.__ptr_ + 1; 798227825Stheraven difference_type __bs = __re - __rb; 799227825Stheraven difference_type __n = __l - __f; 800227825Stheraven _RAIter __m = __f; 801227825Stheraven if (__n > __bs) 802227825Stheraven { 803227825Stheraven __n = __bs; 804227825Stheraven __m = __l - __n; 805227825Stheraven } 806227825Stheraven _VSTD::move_backward(__m, __l, __re); 807227825Stheraven __l = __m; 808227825Stheraven __r -= __n; 809227825Stheraven } 810227825Stheraven return __r; 811227825Stheraven} 812227825Stheraven 813227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 814227825Stheraven class _OutputIterator> 815227825Stheraven_OutputIterator 816227825Stheravenmove_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 817227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 818227825Stheraven _OutputIterator __r) 819227825Stheraven{ 820227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 821227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 822227825Stheraven difference_type __n = __l - __f; 823227825Stheraven while (__n > 0) 824227825Stheraven { 825227825Stheraven --__l; 826227825Stheraven pointer __lb = *__l.__m_iter_; 827227825Stheraven pointer __le = __l.__ptr_ + 1; 828227825Stheraven difference_type __bs = __le - __lb; 829227825Stheraven if (__bs > __n) 830227825Stheraven { 831227825Stheraven __bs = __n; 832227825Stheraven __lb = __le - __bs; 833227825Stheraven } 834227825Stheraven __r = _VSTD::move_backward(__lb, __le, __r); 835227825Stheraven __n -= __bs; 836227825Stheraven __l -= __bs - 1; 837227825Stheraven } 838227825Stheraven return __r; 839227825Stheraven} 840227825Stheraven 841227825Stheraventemplate <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 842227825Stheraven class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 843227825Stheraven__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 844227825Stheravenmove_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 845227825Stheraven __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 846227825Stheraven __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 847227825Stheraven{ 848227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 849227825Stheraven typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 850227825Stheraven difference_type __n = __l - __f; 851227825Stheraven while (__n > 0) 852227825Stheraven { 853227825Stheraven --__l; 854227825Stheraven pointer __lb = *__l.__m_iter_; 855227825Stheraven pointer __le = __l.__ptr_ + 1; 856227825Stheraven difference_type __bs = __le - __lb; 857227825Stheraven if (__bs > __n) 858227825Stheraven { 859227825Stheraven __bs = __n; 860227825Stheraven __lb = __le - __bs; 861227825Stheraven } 862227825Stheraven __r = _VSTD::move_backward(__lb, __le, __r); 863227825Stheraven __n -= __bs; 864227825Stheraven __l -= __bs - 1; 865227825Stheraven } 866227825Stheraven return __r; 867227825Stheraven} 868227825Stheraven 869227825Stheraventemplate <bool> 870227825Stheravenclass __deque_base_common 871227825Stheraven{ 872227825Stheravenprotected: 873227825Stheraven void __throw_length_error() const; 874227825Stheraven void __throw_out_of_range() const; 875227825Stheraven}; 876227825Stheraven 877227825Stheraventemplate <bool __b> 878227825Stheravenvoid 879227825Stheraven__deque_base_common<__b>::__throw_length_error() const 880227825Stheraven{ 881227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 882227825Stheraven throw length_error("deque"); 883227825Stheraven#endif 884227825Stheraven} 885227825Stheraven 886227825Stheraventemplate <bool __b> 887227825Stheravenvoid 888227825Stheraven__deque_base_common<__b>::__throw_out_of_range() const 889227825Stheraven{ 890227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 891227825Stheraven throw out_of_range("deque"); 892227825Stheraven#endif 893227825Stheraven} 894227825Stheraven 895227825Stheraventemplate <class _Tp, class _Allocator> 896227825Stheravenclass __deque_base 897227825Stheraven : protected __deque_base_common<true> 898227825Stheraven{ 899227825Stheraven __deque_base(const __deque_base& __c); 900227825Stheraven __deque_base& operator=(const __deque_base& __c); 901227825Stheravenprotected: 902227825Stheraven typedef _Tp value_type; 903227825Stheraven typedef _Allocator allocator_type; 904227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 905227825Stheraven typedef value_type& reference; 906227825Stheraven typedef const value_type& const_reference; 907227825Stheraven typedef typename __alloc_traits::size_type size_type; 908227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 909227825Stheraven typedef typename __alloc_traits::pointer pointer; 910227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 911227825Stheraven 912227825Stheraven static const difference_type __block_size = sizeof(value_type) < 256 ? 4096 / sizeof(value_type) : 16; 913227825Stheraven 914227825Stheraven typedef typename __alloc_traits::template 915227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 916227825Stheraven rebind_alloc<pointer> 917227825Stheraven#else 918227825Stheraven rebind_alloc<pointer>::other 919227825Stheraven#endif 920227825Stheraven __pointer_allocator; 921227825Stheraven typedef allocator_traits<__pointer_allocator> __map_traits; 922227825Stheraven typedef typename __map_traits::pointer __map_pointer; 923253159Stheraven typedef typename __alloc_traits::template 924253159Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 925253159Stheraven rebind_alloc<const_pointer> 926253159Stheraven#else 927253159Stheraven rebind_alloc<const_pointer>::other 928253159Stheraven#endif 929253159Stheraven __const_pointer_allocator; 930253159Stheraven typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer; 931227825Stheraven typedef __split_buffer<pointer, __pointer_allocator> __map; 932227825Stheraven 933227825Stheraven typedef __deque_iterator<value_type, pointer, reference, __map_pointer, 934227825Stheraven difference_type, __block_size> iterator; 935227825Stheraven typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, 936227825Stheraven difference_type, __block_size> const_iterator; 937227825Stheraven 938227825Stheraven __map __map_; 939227825Stheraven size_type __start_; 940227825Stheraven __compressed_pair<size_type, allocator_type> __size_; 941227825Stheraven 942227825Stheraven iterator begin() _NOEXCEPT; 943227825Stheraven const_iterator begin() const _NOEXCEPT; 944227825Stheraven iterator end() _NOEXCEPT; 945227825Stheraven const_iterator end() const _NOEXCEPT; 946227825Stheraven 947227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();} 948227825Stheraven _LIBCPP_INLINE_VISIBILITY 949227825Stheraven const size_type& size() const _NOEXCEPT {return __size_.first();} 950227825Stheraven _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();} 951227825Stheraven _LIBCPP_INLINE_VISIBILITY 952227825Stheraven const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();} 953227825Stheraven 954227825Stheraven __deque_base() 955227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 956227825Stheraven explicit __deque_base(const allocator_type& __a); 957227825Stheravenpublic: 958227825Stheraven ~__deque_base(); 959227825Stheraven 960227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 961227825Stheraven 962227825Stheraven __deque_base(__deque_base&& __c) 963227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 964227825Stheraven __deque_base(__deque_base&& __c, const allocator_type& __a); 965227825Stheraven 966227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 967227825Stheraven void swap(__deque_base& __c) 968227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 969227825Stheraven __is_nothrow_swappable<allocator_type>::value); 970227825Stheravenprotected: 971227825Stheraven void clear() _NOEXCEPT; 972227825Stheraven 973227825Stheraven bool __invariants() const; 974227825Stheraven 975227825Stheraven _LIBCPP_INLINE_VISIBILITY 976227825Stheraven void __move_assign(__deque_base& __c) 977227825Stheraven _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 978227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 979227825Stheraven { 980227825Stheraven __map_ = _VSTD::move(__c.__map_); 981227825Stheraven __start_ = __c.__start_; 982227825Stheraven size() = __c.size(); 983227825Stheraven __move_assign_alloc(__c); 984227825Stheraven __c.__start_ = __c.size() = 0; 985227825Stheraven } 986227825Stheraven 987227825Stheraven _LIBCPP_INLINE_VISIBILITY 988227825Stheraven void __move_assign_alloc(__deque_base& __c) 989227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value || 990227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 991227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 992227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>());} 993227825Stheraven 994227825Stheravenprivate: 995227825Stheraven _LIBCPP_INLINE_VISIBILITY 996227825Stheraven void __move_assign_alloc(__deque_base& __c, true_type) 997227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 998227825Stheraven { 999227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 1000227825Stheraven } 1001227825Stheraven 1002227825Stheraven _LIBCPP_INLINE_VISIBILITY 1003232950Stheraven void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT 1004227825Stheraven {} 1005227825Stheraven 1006227825Stheraven _LIBCPP_INLINE_VISIBILITY 1007227825Stheraven static void __swap_alloc(allocator_type& __x, allocator_type& __y) 1008227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1009227825Stheraven __is_nothrow_swappable<allocator_type>::value) 1010227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 1011227825Stheraven __alloc_traits::propagate_on_container_swap::value>());} 1012227825Stheraven 1013227825Stheraven _LIBCPP_INLINE_VISIBILITY 1014227825Stheraven static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type) 1015227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value) 1016227825Stheraven { 1017227825Stheraven using _VSTD::swap; 1018227825Stheraven swap(__x, __y); 1019227825Stheraven } 1020227825Stheraven 1021227825Stheraven _LIBCPP_INLINE_VISIBILITY 1022232950Stheraven static void __swap_alloc(allocator_type&, allocator_type&, false_type) 1023227825Stheraven _NOEXCEPT 1024227825Stheraven {} 1025227825Stheraven}; 1026227825Stheraven 1027227825Stheraventemplate <class _Tp, class _Allocator> 1028227825Stheravenbool 1029227825Stheraven__deque_base<_Tp, _Allocator>::__invariants() const 1030227825Stheraven{ 1031227825Stheraven if (!__map_.__invariants()) 1032227825Stheraven return false; 1033227825Stheraven if (__map_.size() >= size_type(-1) / __block_size) 1034227825Stheraven return false; 1035227825Stheraven for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end(); 1036227825Stheraven __i != __e; ++__i) 1037227825Stheraven if (*__i == nullptr) 1038227825Stheraven return false; 1039227825Stheraven if (__map_.size() != 0) 1040227825Stheraven { 1041227825Stheraven if (size() >= __map_.size() * __block_size) 1042227825Stheraven return false; 1043227825Stheraven if (__start_ >= __map_.size() * __block_size - size()) 1044227825Stheraven return false; 1045227825Stheraven } 1046227825Stheraven else 1047227825Stheraven { 1048227825Stheraven if (size() != 0) 1049227825Stheraven return false; 1050227825Stheraven if (__start_ != 0) 1051227825Stheraven return false; 1052227825Stheraven } 1053227825Stheraven return true; 1054227825Stheraven} 1055227825Stheraven 1056227825Stheraventemplate <class _Tp, class _Allocator> 1057227825Stheraventypename __deque_base<_Tp, _Allocator>::iterator 1058227825Stheraven__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT 1059227825Stheraven{ 1060227825Stheraven __map_pointer __mp = __map_.begin() + __start_ / __block_size; 1061227825Stheraven return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); 1062227825Stheraven} 1063227825Stheraven 1064227825Stheraventemplate <class _Tp, class _Allocator> 1065227825Stheraventypename __deque_base<_Tp, _Allocator>::const_iterator 1066227825Stheraven__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT 1067227825Stheraven{ 1068253159Stheraven __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size); 1069227825Stheraven return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); 1070227825Stheraven} 1071227825Stheraven 1072227825Stheraventemplate <class _Tp, class _Allocator> 1073227825Stheraventypename __deque_base<_Tp, _Allocator>::iterator 1074227825Stheraven__deque_base<_Tp, _Allocator>::end() _NOEXCEPT 1075227825Stheraven{ 1076227825Stheraven size_type __p = size() + __start_; 1077227825Stheraven __map_pointer __mp = __map_.begin() + __p / __block_size; 1078227825Stheraven return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); 1079227825Stheraven} 1080227825Stheraven 1081227825Stheraventemplate <class _Tp, class _Allocator> 1082227825Stheraventypename __deque_base<_Tp, _Allocator>::const_iterator 1083227825Stheraven__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT 1084227825Stheraven{ 1085227825Stheraven size_type __p = size() + __start_; 1086253159Stheraven __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size); 1087227825Stheraven return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); 1088227825Stheraven} 1089227825Stheraven 1090227825Stheraventemplate <class _Tp, class _Allocator> 1091227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1092227825Stheraven__deque_base<_Tp, _Allocator>::__deque_base() 1093227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1094227825Stheraven : __start_(0), __size_(0) {} 1095227825Stheraven 1096227825Stheraventemplate <class _Tp, class _Allocator> 1097227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1098227825Stheraven__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a) 1099227825Stheraven : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {} 1100227825Stheraven 1101227825Stheraventemplate <class _Tp, class _Allocator> 1102227825Stheraven__deque_base<_Tp, _Allocator>::~__deque_base() 1103227825Stheraven{ 1104227825Stheraven clear(); 1105227825Stheraven typename __map::iterator __i = __map_.begin(); 1106227825Stheraven typename __map::iterator __e = __map_.end(); 1107227825Stheraven for (; __i != __e; ++__i) 1108227825Stheraven __alloc_traits::deallocate(__alloc(), *__i, __block_size); 1109227825Stheraven} 1110227825Stheraven 1111227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1112227825Stheraven 1113227825Stheraventemplate <class _Tp, class _Allocator> 1114227825Stheraven__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c) 1115227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1116227825Stheraven : __map_(_VSTD::move(__c.__map_)), 1117227825Stheraven __start_(_VSTD::move(__c.__start_)), 1118227825Stheraven __size_(_VSTD::move(__c.__size_)) 1119227825Stheraven{ 1120227825Stheraven __c.__start_ = 0; 1121227825Stheraven __c.size() = 0; 1122227825Stheraven} 1123227825Stheraven 1124227825Stheraventemplate <class _Tp, class _Allocator> 1125227825Stheraven__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a) 1126227825Stheraven : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)), 1127227825Stheraven __start_(_VSTD::move(__c.__start_)), 1128227825Stheraven __size_(_VSTD::move(__c.size()), __a) 1129227825Stheraven{ 1130227825Stheraven if (__a == __c.__alloc()) 1131227825Stheraven { 1132227825Stheraven __c.__start_ = 0; 1133227825Stheraven __c.size() = 0; 1134227825Stheraven } 1135227825Stheraven else 1136227825Stheraven { 1137227825Stheraven __map_.clear(); 1138227825Stheraven __start_ = 0; 1139227825Stheraven size() = 0; 1140227825Stheraven } 1141227825Stheraven} 1142227825Stheraven 1143227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1144227825Stheraven 1145227825Stheraventemplate <class _Tp, class _Allocator> 1146227825Stheravenvoid 1147227825Stheraven__deque_base<_Tp, _Allocator>::swap(__deque_base& __c) 1148227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value|| 1149227825Stheraven __is_nothrow_swappable<allocator_type>::value) 1150227825Stheraven{ 1151227825Stheraven __map_.swap(__c.__map_); 1152227825Stheraven _VSTD::swap(__start_, __c.__start_); 1153227825Stheraven _VSTD::swap(size(), __c.size()); 1154227825Stheraven __swap_alloc(__alloc(), __c.__alloc()); 1155227825Stheraven} 1156227825Stheraven 1157227825Stheraventemplate <class _Tp, class _Allocator> 1158227825Stheravenvoid 1159227825Stheraven__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT 1160227825Stheraven{ 1161227825Stheraven allocator_type& __a = __alloc(); 1162227825Stheraven for (iterator __i = begin(), __e = end(); __i != __e; ++__i) 1163227825Stheraven __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 1164227825Stheraven size() = 0; 1165227825Stheraven while (__map_.size() > 2) 1166227825Stheraven { 1167227825Stheraven __alloc_traits::deallocate(__a, __map_.front(), __block_size); 1168227825Stheraven __map_.pop_front(); 1169227825Stheraven } 1170227825Stheraven switch (__map_.size()) 1171227825Stheraven { 1172227825Stheraven case 1: 1173227825Stheraven __start_ = __block_size / 2; 1174227825Stheraven break; 1175227825Stheraven case 2: 1176227825Stheraven __start_ = __block_size; 1177227825Stheraven break; 1178227825Stheraven } 1179227825Stheraven} 1180227825Stheraven 1181227825Stheraventemplate <class _Tp, class _Allocator = allocator<_Tp> > 1182262801Sdimclass _LIBCPP_TYPE_VIS_ONLY deque 1183227825Stheraven : private __deque_base<_Tp, _Allocator> 1184227825Stheraven{ 1185227825Stheravenpublic: 1186227825Stheraven // types: 1187227825Stheraven 1188227825Stheraven typedef _Tp value_type; 1189227825Stheraven typedef _Allocator allocator_type; 1190227825Stheraven 1191227825Stheraven typedef __deque_base<value_type, allocator_type> __base; 1192227825Stheraven 1193227825Stheraven typedef typename __base::__alloc_traits __alloc_traits; 1194227825Stheraven typedef typename __base::reference reference; 1195227825Stheraven typedef typename __base::const_reference const_reference; 1196227825Stheraven typedef typename __base::iterator iterator; 1197227825Stheraven typedef typename __base::const_iterator const_iterator; 1198227825Stheraven typedef typename __base::size_type size_type; 1199227825Stheraven typedef typename __base::difference_type difference_type; 1200227825Stheraven 1201227825Stheraven typedef typename __base::pointer pointer; 1202227825Stheraven typedef typename __base::const_pointer const_pointer; 1203227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1204227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1205227825Stheraven 1206227825Stheraven // construct/copy/destroy: 1207227825Stheraven _LIBCPP_INLINE_VISIBILITY 1208227825Stheraven deque() 1209227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1210227825Stheraven {} 1211278724Sdim _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {} 1212227825Stheraven explicit deque(size_type __n); 1213262801Sdim#if _LIBCPP_STD_VER > 11 1214262801Sdim explicit deque(size_type __n, const _Allocator& __a); 1215262801Sdim#endif 1216227825Stheraven deque(size_type __n, const value_type& __v); 1217227825Stheraven deque(size_type __n, const value_type& __v, const allocator_type& __a); 1218227825Stheraven template <class _InputIter> 1219227825Stheraven deque(_InputIter __f, _InputIter __l, 1220227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0); 1221227825Stheraven template <class _InputIter> 1222227825Stheraven deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1223227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0); 1224227825Stheraven deque(const deque& __c); 1225227825Stheraven deque(const deque& __c, const allocator_type& __a); 1226227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1227227825Stheraven deque(initializer_list<value_type> __il); 1228227825Stheraven deque(initializer_list<value_type> __il, const allocator_type& __a); 1229227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1230227825Stheraven 1231227825Stheraven deque& operator=(const deque& __c); 1232227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1233227825Stheraven _LIBCPP_INLINE_VISIBILITY 1234227825Stheraven deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;} 1235227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1236227825Stheraven 1237227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1238227825Stheraven deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value); 1239227825Stheraven deque(deque&& __c, const allocator_type& __a); 1240227825Stheraven deque& operator=(deque&& __c) 1241227825Stheraven _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1242227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 1243227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1244227825Stheraven 1245227825Stheraven template <class _InputIter> 1246227825Stheraven void assign(_InputIter __f, _InputIter __l, 1247227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value && 1248227825Stheraven !__is_random_access_iterator<_InputIter>::value>::type* = 0); 1249227825Stheraven template <class _RAIter> 1250227825Stheraven void assign(_RAIter __f, _RAIter __l, 1251227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); 1252227825Stheraven void assign(size_type __n, const value_type& __v); 1253227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1254227825Stheraven _LIBCPP_INLINE_VISIBILITY 1255227825Stheraven void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());} 1256227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1257227825Stheraven 1258227825Stheraven allocator_type get_allocator() const _NOEXCEPT; 1259227825Stheraven 1260227825Stheraven // iterators: 1261227825Stheraven 1262227825Stheraven _LIBCPP_INLINE_VISIBILITY 1263227825Stheraven iterator begin() _NOEXCEPT {return __base::begin();} 1264227825Stheraven _LIBCPP_INLINE_VISIBILITY 1265227825Stheraven const_iterator begin() const _NOEXCEPT {return __base::begin();} 1266227825Stheraven _LIBCPP_INLINE_VISIBILITY 1267227825Stheraven iterator end() _NOEXCEPT {return __base::end();} 1268227825Stheraven _LIBCPP_INLINE_VISIBILITY 1269227825Stheraven const_iterator end() const _NOEXCEPT {return __base::end();} 1270227825Stheraven 1271227825Stheraven _LIBCPP_INLINE_VISIBILITY 1272227825Stheraven reverse_iterator rbegin() _NOEXCEPT 1273227825Stheraven {return reverse_iterator(__base::end());} 1274227825Stheraven _LIBCPP_INLINE_VISIBILITY 1275227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 1276227825Stheraven {return const_reverse_iterator(__base::end());} 1277227825Stheraven _LIBCPP_INLINE_VISIBILITY 1278227825Stheraven reverse_iterator rend() _NOEXCEPT 1279227825Stheraven {return reverse_iterator(__base::begin());} 1280227825Stheraven _LIBCPP_INLINE_VISIBILITY 1281227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 1282227825Stheraven {return const_reverse_iterator(__base::begin());} 1283227825Stheraven 1284227825Stheraven _LIBCPP_INLINE_VISIBILITY 1285227825Stheraven const_iterator cbegin() const _NOEXCEPT 1286227825Stheraven {return __base::begin();} 1287227825Stheraven _LIBCPP_INLINE_VISIBILITY 1288227825Stheraven const_iterator cend() const _NOEXCEPT 1289227825Stheraven {return __base::end();} 1290227825Stheraven _LIBCPP_INLINE_VISIBILITY 1291227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 1292227825Stheraven {return const_reverse_iterator(__base::end());} 1293227825Stheraven _LIBCPP_INLINE_VISIBILITY 1294227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 1295227825Stheraven {return const_reverse_iterator(__base::begin());} 1296227825Stheraven 1297227825Stheraven // capacity: 1298227825Stheraven _LIBCPP_INLINE_VISIBILITY 1299227825Stheraven size_type size() const _NOEXCEPT {return __base::size();} 1300227825Stheraven _LIBCPP_INLINE_VISIBILITY 1301227825Stheraven size_type max_size() const _NOEXCEPT 1302227825Stheraven {return __alloc_traits::max_size(__base::__alloc());} 1303227825Stheraven void resize(size_type __n); 1304227825Stheraven void resize(size_type __n, const value_type& __v); 1305227825Stheraven void shrink_to_fit() _NOEXCEPT; 1306227825Stheraven _LIBCPP_INLINE_VISIBILITY 1307227825Stheraven bool empty() const _NOEXCEPT {return __base::size() == 0;} 1308227825Stheraven 1309227825Stheraven // element access: 1310227825Stheraven reference operator[](size_type __i); 1311227825Stheraven const_reference operator[](size_type __i) const; 1312227825Stheraven reference at(size_type __i); 1313227825Stheraven const_reference at(size_type __i) const; 1314227825Stheraven reference front(); 1315227825Stheraven const_reference front() const; 1316227825Stheraven reference back(); 1317227825Stheraven const_reference back() const; 1318227825Stheraven 1319227825Stheraven // 23.2.2.3 modifiers: 1320227825Stheraven void push_front(const value_type& __v); 1321227825Stheraven void push_back(const value_type& __v); 1322227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1323227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1324227825Stheraven template <class... _Args> void emplace_front(_Args&&... __args); 1325227825Stheraven template <class... _Args> void emplace_back(_Args&&... __args); 1326227825Stheraven template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args); 1327227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1328227825Stheraven void push_front(value_type&& __v); 1329227825Stheraven void push_back(value_type&& __v); 1330227825Stheraven iterator insert(const_iterator __p, value_type&& __v); 1331227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1332227825Stheraven iterator insert(const_iterator __p, const value_type& __v); 1333227825Stheraven iterator insert(const_iterator __p, size_type __n, const value_type& __v); 1334227825Stheraven template <class _InputIter> 1335227825Stheraven iterator insert (const_iterator __p, _InputIter __f, _InputIter __l, 1336227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value 1337227825Stheraven &&!__is_bidirectional_iterator<_InputIter>::value>::type* = 0); 1338227825Stheraven template <class _BiIter> 1339227825Stheraven iterator insert (const_iterator __p, _BiIter __f, _BiIter __l, 1340227825Stheraven typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0); 1341227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1342227825Stheraven _LIBCPP_INLINE_VISIBILITY 1343227825Stheraven iterator insert(const_iterator __p, initializer_list<value_type> __il) 1344227825Stheraven {return insert(__p, __il.begin(), __il.end());} 1345227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1346227825Stheraven void pop_front(); 1347227825Stheraven void pop_back(); 1348227825Stheraven iterator erase(const_iterator __p); 1349227825Stheraven iterator erase(const_iterator __f, const_iterator __l); 1350227825Stheraven 1351227825Stheraven void swap(deque& __c) 1352227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1353227825Stheraven __is_nothrow_swappable<allocator_type>::value); 1354227825Stheraven void clear() _NOEXCEPT; 1355227825Stheraven 1356227825Stheraven _LIBCPP_INLINE_VISIBILITY 1357227825Stheraven bool __invariants() const {return __base::__invariants();} 1358227825Stheravenprivate: 1359253159Stheraven typedef typename __base::__map_const_pointer __map_const_pointer; 1360253159Stheraven 1361227825Stheraven _LIBCPP_INLINE_VISIBILITY 1362227825Stheraven static size_type __recommend_blocks(size_type __n) 1363227825Stheraven { 1364227825Stheraven return __n / __base::__block_size + (__n % __base::__block_size != 0); 1365227825Stheraven } 1366227825Stheraven _LIBCPP_INLINE_VISIBILITY 1367227825Stheraven size_type __capacity() const 1368227825Stheraven { 1369227825Stheraven return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1; 1370227825Stheraven } 1371227825Stheraven _LIBCPP_INLINE_VISIBILITY 1372227825Stheraven size_type __front_spare() const 1373227825Stheraven { 1374227825Stheraven return __base::__start_; 1375227825Stheraven } 1376227825Stheraven _LIBCPP_INLINE_VISIBILITY 1377227825Stheraven size_type __back_spare() const 1378227825Stheraven { 1379227825Stheraven return __capacity() - (__base::__start_ + __base::size()); 1380227825Stheraven } 1381227825Stheraven 1382227825Stheraven template <class _InpIter> 1383227825Stheraven void __append(_InpIter __f, _InpIter __l, 1384227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value && 1385227825Stheraven !__is_forward_iterator<_InpIter>::value>::type* = 0); 1386227825Stheraven template <class _ForIter> 1387227825Stheraven void __append(_ForIter __f, _ForIter __l, 1388227825Stheraven typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0); 1389227825Stheraven void __append(size_type __n); 1390227825Stheraven void __append(size_type __n, const value_type& __v); 1391227825Stheraven void __erase_to_end(const_iterator __f); 1392227825Stheraven void __add_front_capacity(); 1393227825Stheraven void __add_front_capacity(size_type __n); 1394227825Stheraven void __add_back_capacity(); 1395227825Stheraven void __add_back_capacity(size_type __n); 1396227825Stheraven iterator __move_and_check(iterator __f, iterator __l, iterator __r, 1397227825Stheraven const_pointer& __vt); 1398227825Stheraven iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r, 1399227825Stheraven const_pointer& __vt); 1400227825Stheraven void __move_construct_and_check(iterator __f, iterator __l, 1401227825Stheraven iterator __r, const_pointer& __vt); 1402227825Stheraven void __move_construct_backward_and_check(iterator __f, iterator __l, 1403227825Stheraven iterator __r, const_pointer& __vt); 1404227825Stheraven 1405227825Stheraven _LIBCPP_INLINE_VISIBILITY 1406227825Stheraven void __copy_assign_alloc(const deque& __c) 1407227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 1408227825Stheraven __alloc_traits::propagate_on_container_copy_assignment::value>());} 1409227825Stheraven 1410227825Stheraven _LIBCPP_INLINE_VISIBILITY 1411227825Stheraven void __copy_assign_alloc(const deque& __c, true_type) 1412227825Stheraven { 1413227825Stheraven if (__base::__alloc() != __c.__alloc()) 1414227825Stheraven { 1415227825Stheraven clear(); 1416227825Stheraven shrink_to_fit(); 1417227825Stheraven } 1418227825Stheraven __base::__alloc() = __c.__alloc(); 1419227825Stheraven __base::__map_.__alloc() = __c.__map_.__alloc(); 1420227825Stheraven } 1421227825Stheraven 1422227825Stheraven _LIBCPP_INLINE_VISIBILITY 1423232950Stheraven void __copy_assign_alloc(const deque&, false_type) 1424227825Stheraven {} 1425227825Stheraven 1426227825Stheraven void __move_assign(deque& __c, true_type) 1427227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 1428227825Stheraven void __move_assign(deque& __c, false_type); 1429227825Stheraven}; 1430227825Stheraven 1431227825Stheraventemplate <class _Tp, class _Allocator> 1432227825Stheravendeque<_Tp, _Allocator>::deque(size_type __n) 1433227825Stheraven{ 1434227825Stheraven if (__n > 0) 1435227825Stheraven __append(__n); 1436227825Stheraven} 1437227825Stheraven 1438262801Sdim#if _LIBCPP_STD_VER > 11 1439227825Stheraventemplate <class _Tp, class _Allocator> 1440262801Sdimdeque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a) 1441262801Sdim : __base(__a) 1442262801Sdim{ 1443262801Sdim if (__n > 0) 1444262801Sdim __append(__n); 1445262801Sdim} 1446262801Sdim#endif 1447262801Sdim 1448262801Sdimtemplate <class _Tp, class _Allocator> 1449227825Stheravendeque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v) 1450227825Stheraven{ 1451227825Stheraven if (__n > 0) 1452227825Stheraven __append(__n, __v); 1453227825Stheraven} 1454227825Stheraven 1455227825Stheraventemplate <class _Tp, class _Allocator> 1456227825Stheravendeque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a) 1457227825Stheraven : __base(__a) 1458227825Stheraven{ 1459227825Stheraven if (__n > 0) 1460227825Stheraven __append(__n, __v); 1461227825Stheraven} 1462227825Stheraven 1463227825Stheraventemplate <class _Tp, class _Allocator> 1464227825Stheraventemplate <class _InputIter> 1465227825Stheravendeque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, 1466227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value>::type*) 1467227825Stheraven{ 1468227825Stheraven __append(__f, __l); 1469227825Stheraven} 1470227825Stheraven 1471227825Stheraventemplate <class _Tp, class _Allocator> 1472227825Stheraventemplate <class _InputIter> 1473227825Stheravendeque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1474227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value>::type*) 1475227825Stheraven : __base(__a) 1476227825Stheraven{ 1477227825Stheraven __append(__f, __l); 1478227825Stheraven} 1479227825Stheraven 1480227825Stheraventemplate <class _Tp, class _Allocator> 1481227825Stheravendeque<_Tp, _Allocator>::deque(const deque& __c) 1482227825Stheraven : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc())) 1483227825Stheraven{ 1484227825Stheraven __append(__c.begin(), __c.end()); 1485227825Stheraven} 1486227825Stheraven 1487227825Stheraventemplate <class _Tp, class _Allocator> 1488227825Stheravendeque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a) 1489227825Stheraven : __base(__a) 1490227825Stheraven{ 1491227825Stheraven __append(__c.begin(), __c.end()); 1492227825Stheraven} 1493227825Stheraven 1494227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1495227825Stheraven 1496227825Stheraventemplate <class _Tp, class _Allocator> 1497227825Stheravendeque<_Tp, _Allocator>::deque(initializer_list<value_type> __il) 1498227825Stheraven{ 1499227825Stheraven __append(__il.begin(), __il.end()); 1500227825Stheraven} 1501227825Stheraven 1502227825Stheraventemplate <class _Tp, class _Allocator> 1503227825Stheravendeque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a) 1504227825Stheraven : __base(__a) 1505227825Stheraven{ 1506227825Stheraven __append(__il.begin(), __il.end()); 1507227825Stheraven} 1508227825Stheraven 1509227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1510227825Stheraven 1511227825Stheraventemplate <class _Tp, class _Allocator> 1512227825Stheravendeque<_Tp, _Allocator>& 1513227825Stheravendeque<_Tp, _Allocator>::operator=(const deque& __c) 1514227825Stheraven{ 1515227825Stheraven if (this != &__c) 1516227825Stheraven { 1517227825Stheraven __copy_assign_alloc(__c); 1518227825Stheraven assign(__c.begin(), __c.end()); 1519227825Stheraven } 1520227825Stheraven return *this; 1521227825Stheraven} 1522227825Stheraven 1523227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1524227825Stheraven 1525227825Stheraventemplate <class _Tp, class _Allocator> 1526227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1527227825Stheravendeque<_Tp, _Allocator>::deque(deque&& __c) 1528227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1529227825Stheraven : __base(_VSTD::move(__c)) 1530227825Stheraven{ 1531227825Stheraven} 1532227825Stheraven 1533227825Stheraventemplate <class _Tp, class _Allocator> 1534227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1535227825Stheravendeque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a) 1536227825Stheraven : __base(_VSTD::move(__c), __a) 1537227825Stheraven{ 1538227825Stheraven if (__a != __c.__alloc()) 1539227825Stheraven { 1540232950Stheraven typedef move_iterator<iterator> _Ip; 1541232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1542227825Stheraven } 1543227825Stheraven} 1544227825Stheraven 1545227825Stheraventemplate <class _Tp, class _Allocator> 1546227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1547227825Stheravendeque<_Tp, _Allocator>& 1548227825Stheravendeque<_Tp, _Allocator>::operator=(deque&& __c) 1549227825Stheraven _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1550227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 1551227825Stheraven{ 1552227825Stheraven __move_assign(__c, integral_constant<bool, 1553227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>()); 1554227825Stheraven return *this; 1555227825Stheraven} 1556227825Stheraven 1557227825Stheraventemplate <class _Tp, class _Allocator> 1558227825Stheravenvoid 1559227825Stheravendeque<_Tp, _Allocator>::__move_assign(deque& __c, false_type) 1560227825Stheraven{ 1561227825Stheraven if (__base::__alloc() != __c.__alloc()) 1562227825Stheraven { 1563232950Stheraven typedef move_iterator<iterator> _Ip; 1564232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1565227825Stheraven } 1566227825Stheraven else 1567227825Stheraven __move_assign(__c, true_type()); 1568227825Stheraven} 1569227825Stheraven 1570227825Stheraventemplate <class _Tp, class _Allocator> 1571227825Stheravenvoid 1572227825Stheravendeque<_Tp, _Allocator>::__move_assign(deque& __c, true_type) 1573227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1574227825Stheraven{ 1575227825Stheraven clear(); 1576227825Stheraven shrink_to_fit(); 1577227825Stheraven __base::__move_assign(__c); 1578227825Stheraven} 1579227825Stheraven 1580227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1581227825Stheraven 1582227825Stheraventemplate <class _Tp, class _Allocator> 1583227825Stheraventemplate <class _InputIter> 1584227825Stheravenvoid 1585227825Stheravendeque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l, 1586227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value && 1587227825Stheraven !__is_random_access_iterator<_InputIter>::value>::type*) 1588227825Stheraven{ 1589227825Stheraven iterator __i = __base::begin(); 1590227825Stheraven iterator __e = __base::end(); 1591278724Sdim for (; __f != __l && __i != __e; ++__f, (void) ++__i) 1592227825Stheraven *__i = *__f; 1593227825Stheraven if (__f != __l) 1594227825Stheraven __append(__f, __l); 1595227825Stheraven else 1596227825Stheraven __erase_to_end(__i); 1597227825Stheraven} 1598227825Stheraven 1599227825Stheraventemplate <class _Tp, class _Allocator> 1600227825Stheraventemplate <class _RAIter> 1601227825Stheravenvoid 1602227825Stheravendeque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l, 1603227825Stheraven typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) 1604227825Stheraven{ 1605227825Stheraven if (static_cast<size_type>(__l - __f) > __base::size()) 1606227825Stheraven { 1607227825Stheraven _RAIter __m = __f + __base::size(); 1608227825Stheraven _VSTD::copy(__f, __m, __base::begin()); 1609227825Stheraven __append(__m, __l); 1610227825Stheraven } 1611227825Stheraven else 1612227825Stheraven __erase_to_end(_VSTD::copy(__f, __l, __base::begin())); 1613227825Stheraven} 1614227825Stheraven 1615227825Stheraventemplate <class _Tp, class _Allocator> 1616227825Stheravenvoid 1617227825Stheravendeque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v) 1618227825Stheraven{ 1619227825Stheraven if (__n > __base::size()) 1620227825Stheraven { 1621227825Stheraven _VSTD::fill_n(__base::begin(), __base::size(), __v); 1622227825Stheraven __n -= __base::size(); 1623227825Stheraven __append(__n, __v); 1624227825Stheraven } 1625227825Stheraven else 1626227825Stheraven __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v)); 1627227825Stheraven} 1628227825Stheraven 1629227825Stheraventemplate <class _Tp, class _Allocator> 1630227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1631227825Stheraven_Allocator 1632227825Stheravendeque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT 1633227825Stheraven{ 1634227825Stheraven return __base::__alloc(); 1635227825Stheraven} 1636227825Stheraven 1637227825Stheraventemplate <class _Tp, class _Allocator> 1638227825Stheravenvoid 1639227825Stheravendeque<_Tp, _Allocator>::resize(size_type __n) 1640227825Stheraven{ 1641227825Stheraven if (__n > __base::size()) 1642227825Stheraven __append(__n - __base::size()); 1643227825Stheraven else if (__n < __base::size()) 1644227825Stheraven __erase_to_end(__base::begin() + __n); 1645227825Stheraven} 1646227825Stheraven 1647227825Stheraventemplate <class _Tp, class _Allocator> 1648227825Stheravenvoid 1649227825Stheravendeque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v) 1650227825Stheraven{ 1651227825Stheraven if (__n > __base::size()) 1652227825Stheraven __append(__n - __base::size(), __v); 1653227825Stheraven else if (__n < __base::size()) 1654227825Stheraven __erase_to_end(__base::begin() + __n); 1655227825Stheraven} 1656227825Stheraven 1657227825Stheraventemplate <class _Tp, class _Allocator> 1658227825Stheravenvoid 1659227825Stheravendeque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1660227825Stheraven{ 1661227825Stheraven allocator_type& __a = __base::__alloc(); 1662227825Stheraven if (empty()) 1663227825Stheraven { 1664227825Stheraven while (__base::__map_.size() > 0) 1665227825Stheraven { 1666227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 1667227825Stheraven __base::__map_.pop_back(); 1668227825Stheraven } 1669227825Stheraven __base::__start_ = 0; 1670227825Stheraven } 1671227825Stheraven else 1672227825Stheraven { 1673227825Stheraven if (__front_spare() >= __base::__block_size) 1674227825Stheraven { 1675227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 1676227825Stheraven __base::__map_.pop_front(); 1677227825Stheraven __base::__start_ -= __base::__block_size; 1678227825Stheraven } 1679227825Stheraven if (__back_spare() >= __base::__block_size) 1680227825Stheraven { 1681227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 1682227825Stheraven __base::__map_.pop_back(); 1683227825Stheraven } 1684227825Stheraven } 1685227825Stheraven __base::__map_.shrink_to_fit(); 1686227825Stheraven} 1687227825Stheraven 1688227825Stheraventemplate <class _Tp, class _Allocator> 1689227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1690227825Stheraventypename deque<_Tp, _Allocator>::reference 1691227825Stheravendeque<_Tp, _Allocator>::operator[](size_type __i) 1692227825Stheraven{ 1693227825Stheraven size_type __p = __base::__start_ + __i; 1694227825Stheraven return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1695227825Stheraven} 1696227825Stheraven 1697227825Stheraventemplate <class _Tp, class _Allocator> 1698227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1699227825Stheraventypename deque<_Tp, _Allocator>::const_reference 1700227825Stheravendeque<_Tp, _Allocator>::operator[](size_type __i) const 1701227825Stheraven{ 1702227825Stheraven size_type __p = __base::__start_ + __i; 1703227825Stheraven return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1704227825Stheraven} 1705227825Stheraven 1706227825Stheraventemplate <class _Tp, class _Allocator> 1707227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1708227825Stheraventypename deque<_Tp, _Allocator>::reference 1709227825Stheravendeque<_Tp, _Allocator>::at(size_type __i) 1710227825Stheraven{ 1711227825Stheraven if (__i >= __base::size()) 1712227825Stheraven __base::__throw_out_of_range(); 1713227825Stheraven size_type __p = __base::__start_ + __i; 1714227825Stheraven return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1715227825Stheraven} 1716227825Stheraven 1717227825Stheraventemplate <class _Tp, class _Allocator> 1718227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1719227825Stheraventypename deque<_Tp, _Allocator>::const_reference 1720227825Stheravendeque<_Tp, _Allocator>::at(size_type __i) const 1721227825Stheraven{ 1722227825Stheraven if (__i >= __base::size()) 1723227825Stheraven __base::__throw_out_of_range(); 1724227825Stheraven size_type __p = __base::__start_ + __i; 1725227825Stheraven return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1726227825Stheraven} 1727227825Stheraven 1728227825Stheraventemplate <class _Tp, class _Allocator> 1729227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1730227825Stheraventypename deque<_Tp, _Allocator>::reference 1731227825Stheravendeque<_Tp, _Allocator>::front() 1732227825Stheraven{ 1733227825Stheraven return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1734227825Stheraven + __base::__start_ % __base::__block_size); 1735227825Stheraven} 1736227825Stheraven 1737227825Stheraventemplate <class _Tp, class _Allocator> 1738227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1739227825Stheraventypename deque<_Tp, _Allocator>::const_reference 1740227825Stheravendeque<_Tp, _Allocator>::front() const 1741227825Stheraven{ 1742227825Stheraven return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1743227825Stheraven + __base::__start_ % __base::__block_size); 1744227825Stheraven} 1745227825Stheraven 1746227825Stheraventemplate <class _Tp, class _Allocator> 1747227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1748227825Stheraventypename deque<_Tp, _Allocator>::reference 1749227825Stheravendeque<_Tp, _Allocator>::back() 1750227825Stheraven{ 1751227825Stheraven size_type __p = __base::size() + __base::__start_ - 1; 1752227825Stheraven return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1753227825Stheraven} 1754227825Stheraven 1755227825Stheraventemplate <class _Tp, class _Allocator> 1756227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 1757227825Stheraventypename deque<_Tp, _Allocator>::const_reference 1758227825Stheravendeque<_Tp, _Allocator>::back() const 1759227825Stheraven{ 1760227825Stheraven size_type __p = __base::size() + __base::__start_ - 1; 1761227825Stheraven return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1762227825Stheraven} 1763227825Stheraven 1764227825Stheraventemplate <class _Tp, class _Allocator> 1765227825Stheravenvoid 1766227825Stheravendeque<_Tp, _Allocator>::push_back(const value_type& __v) 1767227825Stheraven{ 1768227825Stheraven allocator_type& __a = __base::__alloc(); 1769227825Stheraven if (__back_spare() == 0) 1770227825Stheraven __add_back_capacity(); 1771227825Stheraven // __back_spare() >= 1 1772227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 1773227825Stheraven ++__base::size(); 1774227825Stheraven} 1775227825Stheraven 1776227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1777227825Stheraven 1778227825Stheraventemplate <class _Tp, class _Allocator> 1779227825Stheravenvoid 1780227825Stheravendeque<_Tp, _Allocator>::push_back(value_type&& __v) 1781227825Stheraven{ 1782227825Stheraven allocator_type& __a = __base::__alloc(); 1783227825Stheraven if (__back_spare() == 0) 1784227825Stheraven __add_back_capacity(); 1785227825Stheraven // __back_spare() >= 1 1786227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 1787227825Stheraven ++__base::size(); 1788227825Stheraven} 1789227825Stheraven 1790227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1791227825Stheraven 1792227825Stheraventemplate <class _Tp, class _Allocator> 1793227825Stheraventemplate <class... _Args> 1794227825Stheravenvoid 1795227825Stheravendeque<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1796227825Stheraven{ 1797227825Stheraven allocator_type& __a = __base::__alloc(); 1798227825Stheraven if (__back_spare() == 0) 1799227825Stheraven __add_back_capacity(); 1800227825Stheraven // __back_spare() >= 1 1801227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 1802227825Stheraven ++__base::size(); 1803227825Stheraven} 1804227825Stheraven 1805227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1806227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1807227825Stheraven 1808227825Stheraventemplate <class _Tp, class _Allocator> 1809227825Stheravenvoid 1810227825Stheravendeque<_Tp, _Allocator>::push_front(const value_type& __v) 1811227825Stheraven{ 1812227825Stheraven allocator_type& __a = __base::__alloc(); 1813227825Stheraven if (__front_spare() == 0) 1814227825Stheraven __add_front_capacity(); 1815227825Stheraven // __front_spare() >= 1 1816227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 1817227825Stheraven --__base::__start_; 1818227825Stheraven ++__base::size(); 1819227825Stheraven} 1820227825Stheraven 1821227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1822227825Stheraven 1823227825Stheraventemplate <class _Tp, class _Allocator> 1824227825Stheravenvoid 1825227825Stheravendeque<_Tp, _Allocator>::push_front(value_type&& __v) 1826227825Stheraven{ 1827227825Stheraven allocator_type& __a = __base::__alloc(); 1828227825Stheraven if (__front_spare() == 0) 1829227825Stheraven __add_front_capacity(); 1830227825Stheraven // __front_spare() >= 1 1831227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 1832227825Stheraven --__base::__start_; 1833227825Stheraven ++__base::size(); 1834227825Stheraven} 1835227825Stheraven 1836227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1837227825Stheraven 1838227825Stheraventemplate <class _Tp, class _Allocator> 1839227825Stheraventemplate <class... _Args> 1840227825Stheravenvoid 1841227825Stheravendeque<_Tp, _Allocator>::emplace_front(_Args&&... __args) 1842227825Stheraven{ 1843227825Stheraven allocator_type& __a = __base::__alloc(); 1844227825Stheraven if (__front_spare() == 0) 1845227825Stheraven __add_front_capacity(); 1846227825Stheraven // __front_spare() >= 1 1847227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 1848227825Stheraven --__base::__start_; 1849227825Stheraven ++__base::size(); 1850227825Stheraven} 1851227825Stheraven 1852227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1853227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1854227825Stheraven 1855227825Stheraventemplate <class _Tp, class _Allocator> 1856227825Stheraventypename deque<_Tp, _Allocator>::iterator 1857227825Stheravendeque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v) 1858227825Stheraven{ 1859227825Stheraven size_type __pos = __p - __base::begin(); 1860227825Stheraven size_type __to_end = __base::size() - __pos; 1861227825Stheraven allocator_type& __a = __base::__alloc(); 1862227825Stheraven if (__pos < __to_end) 1863227825Stheraven { // insert by shifting things backward 1864227825Stheraven if (__front_spare() == 0) 1865227825Stheraven __add_front_capacity(); 1866227825Stheraven // __front_spare() >= 1 1867227825Stheraven if (__pos == 0) 1868227825Stheraven { 1869227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 1870227825Stheraven --__base::__start_; 1871227825Stheraven ++__base::size(); 1872227825Stheraven } 1873227825Stheraven else 1874227825Stheraven { 1875227825Stheraven const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 1876227825Stheraven iterator __b = __base::begin(); 1877227825Stheraven iterator __bm1 = _VSTD::prev(__b); 1878227825Stheraven if (__vt == pointer_traits<const_pointer>::pointer_to(*__b)) 1879227825Stheraven __vt = pointer_traits<const_pointer>::pointer_to(*__bm1); 1880227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 1881227825Stheraven --__base::__start_; 1882227825Stheraven ++__base::size(); 1883227825Stheraven if (__pos > 1) 1884227825Stheraven __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt); 1885227825Stheraven *__b = *__vt; 1886227825Stheraven } 1887227825Stheraven } 1888227825Stheraven else 1889227825Stheraven { // insert by shifting things forward 1890227825Stheraven if (__back_spare() == 0) 1891227825Stheraven __add_back_capacity(); 1892227825Stheraven // __back_capacity >= 1 1893227825Stheraven size_type __de = __base::size() - __pos; 1894227825Stheraven if (__de == 0) 1895227825Stheraven { 1896227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 1897227825Stheraven ++__base::size(); 1898227825Stheraven } 1899227825Stheraven else 1900227825Stheraven { 1901227825Stheraven const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 1902227825Stheraven iterator __e = __base::end(); 1903227825Stheraven iterator __em1 = _VSTD::prev(__e); 1904227825Stheraven if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1)) 1905227825Stheraven __vt = pointer_traits<const_pointer>::pointer_to(*__e); 1906227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 1907227825Stheraven ++__base::size(); 1908227825Stheraven if (__de > 1) 1909227825Stheraven __e = __move_backward_and_check(__e - __de, __em1, __e, __vt); 1910227825Stheraven *--__e = *__vt; 1911227825Stheraven } 1912227825Stheraven } 1913227825Stheraven return __base::begin() + __pos; 1914227825Stheraven} 1915227825Stheraven 1916227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1917227825Stheraven 1918227825Stheraventemplate <class _Tp, class _Allocator> 1919227825Stheraventypename deque<_Tp, _Allocator>::iterator 1920227825Stheravendeque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v) 1921227825Stheraven{ 1922227825Stheraven size_type __pos = __p - __base::begin(); 1923227825Stheraven size_type __to_end = __base::size() - __pos; 1924227825Stheraven allocator_type& __a = __base::__alloc(); 1925227825Stheraven if (__pos < __to_end) 1926227825Stheraven { // insert by shifting things backward 1927227825Stheraven if (__front_spare() == 0) 1928227825Stheraven __add_front_capacity(); 1929227825Stheraven // __front_spare() >= 1 1930227825Stheraven if (__pos == 0) 1931227825Stheraven { 1932227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 1933227825Stheraven --__base::__start_; 1934227825Stheraven ++__base::size(); 1935227825Stheraven } 1936227825Stheraven else 1937227825Stheraven { 1938227825Stheraven iterator __b = __base::begin(); 1939227825Stheraven iterator __bm1 = _VSTD::prev(__b); 1940227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 1941227825Stheraven --__base::__start_; 1942227825Stheraven ++__base::size(); 1943227825Stheraven if (__pos > 1) 1944227825Stheraven __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 1945227825Stheraven *__b = _VSTD::move(__v); 1946227825Stheraven } 1947227825Stheraven } 1948227825Stheraven else 1949227825Stheraven { // insert by shifting things forward 1950227825Stheraven if (__back_spare() == 0) 1951227825Stheraven __add_back_capacity(); 1952227825Stheraven // __back_capacity >= 1 1953227825Stheraven size_type __de = __base::size() - __pos; 1954227825Stheraven if (__de == 0) 1955227825Stheraven { 1956227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 1957227825Stheraven ++__base::size(); 1958227825Stheraven } 1959227825Stheraven else 1960227825Stheraven { 1961227825Stheraven iterator __e = __base::end(); 1962227825Stheraven iterator __em1 = _VSTD::prev(__e); 1963227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 1964227825Stheraven ++__base::size(); 1965227825Stheraven if (__de > 1) 1966227825Stheraven __e = _VSTD::move_backward(__e - __de, __em1, __e); 1967227825Stheraven *--__e = _VSTD::move(__v); 1968227825Stheraven } 1969227825Stheraven } 1970227825Stheraven return __base::begin() + __pos; 1971227825Stheraven} 1972227825Stheraven 1973227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1974227825Stheraven 1975227825Stheraventemplate <class _Tp, class _Allocator> 1976227825Stheraventemplate <class... _Args> 1977227825Stheraventypename deque<_Tp, _Allocator>::iterator 1978227825Stheravendeque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args) 1979227825Stheraven{ 1980227825Stheraven size_type __pos = __p - __base::begin(); 1981227825Stheraven size_type __to_end = __base::size() - __pos; 1982227825Stheraven allocator_type& __a = __base::__alloc(); 1983227825Stheraven if (__pos < __to_end) 1984227825Stheraven { // insert by shifting things backward 1985227825Stheraven if (__front_spare() == 0) 1986227825Stheraven __add_front_capacity(); 1987227825Stheraven // __front_spare() >= 1 1988227825Stheraven if (__pos == 0) 1989227825Stheraven { 1990227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 1991227825Stheraven --__base::__start_; 1992227825Stheraven ++__base::size(); 1993227825Stheraven } 1994227825Stheraven else 1995227825Stheraven { 1996241903Sdim value_type __tmp(_VSTD::forward<_Args>(__args)...); 1997227825Stheraven iterator __b = __base::begin(); 1998227825Stheraven iterator __bm1 = _VSTD::prev(__b); 1999227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2000227825Stheraven --__base::__start_; 2001227825Stheraven ++__base::size(); 2002227825Stheraven if (__pos > 1) 2003227825Stheraven __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 2004241903Sdim *__b = _VSTD::move(__tmp); 2005227825Stheraven } 2006227825Stheraven } 2007227825Stheraven else 2008227825Stheraven { // insert by shifting things forward 2009227825Stheraven if (__back_spare() == 0) 2010227825Stheraven __add_back_capacity(); 2011227825Stheraven // __back_capacity >= 1 2012227825Stheraven size_type __de = __base::size() - __pos; 2013227825Stheraven if (__de == 0) 2014227825Stheraven { 2015227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 2016227825Stheraven ++__base::size(); 2017227825Stheraven } 2018227825Stheraven else 2019227825Stheraven { 2020241903Sdim value_type __tmp(_VSTD::forward<_Args>(__args)...); 2021227825Stheraven iterator __e = __base::end(); 2022227825Stheraven iterator __em1 = _VSTD::prev(__e); 2023227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2024227825Stheraven ++__base::size(); 2025227825Stheraven if (__de > 1) 2026227825Stheraven __e = _VSTD::move_backward(__e - __de, __em1, __e); 2027241903Sdim *--__e = _VSTD::move(__tmp); 2028227825Stheraven } 2029227825Stheraven } 2030227825Stheraven return __base::begin() + __pos; 2031227825Stheraven} 2032227825Stheraven 2033227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 2034227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2035227825Stheraven 2036227825Stheraventemplate <class _Tp, class _Allocator> 2037227825Stheraventypename deque<_Tp, _Allocator>::iterator 2038227825Stheravendeque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) 2039227825Stheraven{ 2040227825Stheraven size_type __pos = __p - __base::begin(); 2041227825Stheraven size_type __to_end = __base::size() - __pos; 2042227825Stheraven allocator_type& __a = __base::__alloc(); 2043227825Stheraven if (__pos < __to_end) 2044227825Stheraven { // insert by shifting things backward 2045227825Stheraven if (__n > __front_spare()) 2046227825Stheraven __add_front_capacity(__n - __front_spare()); 2047227825Stheraven // __n <= __front_spare() 2048227825Stheraven size_type __old_n = __n; 2049227825Stheraven iterator __old_begin = __base::begin(); 2050227825Stheraven iterator __i = __old_begin; 2051227825Stheraven if (__n > __pos) 2052227825Stheraven { 2053227825Stheraven for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size()) 2054227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v); 2055227825Stheraven __n = __pos; 2056227825Stheraven } 2057227825Stheraven if (__n > 0) 2058227825Stheraven { 2059227825Stheraven const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2060227825Stheraven iterator __obn = __old_begin + __n; 2061227825Stheraven __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); 2062227825Stheraven if (__n < __pos) 2063227825Stheraven __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); 2064227825Stheraven _VSTD::fill_n(__old_begin, __n, *__vt); 2065227825Stheraven } 2066227825Stheraven } 2067227825Stheraven else 2068227825Stheraven { // insert by shifting things forward 2069227825Stheraven size_type __back_capacity = __back_spare(); 2070227825Stheraven if (__n > __back_capacity) 2071227825Stheraven __add_back_capacity(__n - __back_capacity); 2072227825Stheraven // __n <= __back_capacity 2073227825Stheraven size_type __old_n = __n; 2074227825Stheraven iterator __old_end = __base::end(); 2075227825Stheraven iterator __i = __old_end; 2076227825Stheraven size_type __de = __base::size() - __pos; 2077227825Stheraven if (__n > __de) 2078227825Stheraven { 2079227825Stheraven for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size()) 2080227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2081227825Stheraven __n = __de; 2082227825Stheraven } 2083227825Stheraven if (__n > 0) 2084227825Stheraven { 2085227825Stheraven const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2086227825Stheraven iterator __oen = __old_end - __n; 2087227825Stheraven __move_construct_and_check(__oen, __old_end, __i, __vt); 2088227825Stheraven if (__n < __de) 2089227825Stheraven __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); 2090227825Stheraven _VSTD::fill_n(__old_end - __n, __n, *__vt); 2091227825Stheraven } 2092227825Stheraven } 2093227825Stheraven return __base::begin() + __pos; 2094227825Stheraven} 2095227825Stheraven 2096227825Stheraventemplate <class _Tp, class _Allocator> 2097227825Stheraventemplate <class _InputIter> 2098227825Stheraventypename deque<_Tp, _Allocator>::iterator 2099227825Stheravendeque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, 2100227825Stheraven typename enable_if<__is_input_iterator<_InputIter>::value 2101227825Stheraven &&!__is_bidirectional_iterator<_InputIter>::value>::type*) 2102227825Stheraven{ 2103227825Stheraven __split_buffer<value_type, allocator_type&> __buf(__base::__alloc()); 2104227825Stheraven __buf.__construct_at_end(__f, __l); 2105227825Stheraven typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi; 2106227825Stheraven return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); 2107227825Stheraven} 2108227825Stheraven 2109227825Stheraventemplate <class _Tp, class _Allocator> 2110227825Stheraventemplate <class _BiIter> 2111227825Stheraventypename deque<_Tp, _Allocator>::iterator 2112227825Stheravendeque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, 2113227825Stheraven typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*) 2114227825Stheraven{ 2115227825Stheraven size_type __n = _VSTD::distance(__f, __l); 2116227825Stheraven size_type __pos = __p - __base::begin(); 2117227825Stheraven size_type __to_end = __base::size() - __pos; 2118227825Stheraven allocator_type& __a = __base::__alloc(); 2119227825Stheraven if (__pos < __to_end) 2120227825Stheraven { // insert by shifting things backward 2121227825Stheraven if (__n > __front_spare()) 2122227825Stheraven __add_front_capacity(__n - __front_spare()); 2123227825Stheraven // __n <= __front_spare() 2124227825Stheraven size_type __old_n = __n; 2125227825Stheraven iterator __old_begin = __base::begin(); 2126227825Stheraven iterator __i = __old_begin; 2127227825Stheraven _BiIter __m = __f; 2128227825Stheraven if (__n > __pos) 2129227825Stheraven { 2130227825Stheraven __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos); 2131227825Stheraven for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size()) 2132227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j); 2133227825Stheraven __n = __pos; 2134227825Stheraven } 2135227825Stheraven if (__n > 0) 2136227825Stheraven { 2137227825Stheraven iterator __obn = __old_begin + __n; 2138227825Stheraven for (iterator __j = __obn; __j != __old_begin;) 2139227825Stheraven { 2140227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j)); 2141227825Stheraven --__base::__start_; 2142227825Stheraven ++__base::size(); 2143227825Stheraven } 2144227825Stheraven if (__n < __pos) 2145227825Stheraven __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin); 2146227825Stheraven _VSTD::copy(__m, __l, __old_begin); 2147227825Stheraven } 2148227825Stheraven } 2149227825Stheraven else 2150227825Stheraven { // insert by shifting things forward 2151227825Stheraven size_type __back_capacity = __back_spare(); 2152227825Stheraven if (__n > __back_capacity) 2153227825Stheraven __add_back_capacity(__n - __back_capacity); 2154227825Stheraven // __n <= __back_capacity 2155227825Stheraven size_type __old_n = __n; 2156227825Stheraven iterator __old_end = __base::end(); 2157227825Stheraven iterator __i = __old_end; 2158227825Stheraven _BiIter __m = __l; 2159227825Stheraven size_type __de = __base::size() - __pos; 2160227825Stheraven if (__n > __de) 2161227825Stheraven { 2162227825Stheraven __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de); 2163278724Sdim for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size()) 2164227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j); 2165227825Stheraven __n = __de; 2166227825Stheraven } 2167227825Stheraven if (__n > 0) 2168227825Stheraven { 2169227825Stheraven iterator __oen = __old_end - __n; 2170227825Stheraven for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size()) 2171227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j)); 2172227825Stheraven if (__n < __de) 2173227825Stheraven __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end); 2174227825Stheraven _VSTD::copy_backward(__f, __m, __old_end); 2175227825Stheraven } 2176227825Stheraven } 2177227825Stheraven return __base::begin() + __pos; 2178227825Stheraven} 2179227825Stheraven 2180227825Stheraventemplate <class _Tp, class _Allocator> 2181227825Stheraventemplate <class _InpIter> 2182227825Stheravenvoid 2183227825Stheravendeque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, 2184227825Stheraven typename enable_if<__is_input_iterator<_InpIter>::value && 2185227825Stheraven !__is_forward_iterator<_InpIter>::value>::type*) 2186227825Stheraven{ 2187227825Stheraven for (; __f != __l; ++__f) 2188227825Stheraven push_back(*__f); 2189227825Stheraven} 2190227825Stheraven 2191227825Stheraventemplate <class _Tp, class _Allocator> 2192227825Stheraventemplate <class _ForIter> 2193227825Stheravenvoid 2194227825Stheravendeque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, 2195227825Stheraven typename enable_if<__is_forward_iterator<_ForIter>::value>::type*) 2196227825Stheraven{ 2197227825Stheraven size_type __n = _VSTD::distance(__f, __l); 2198227825Stheraven allocator_type& __a = __base::__alloc(); 2199227825Stheraven size_type __back_capacity = __back_spare(); 2200227825Stheraven if (__n > __back_capacity) 2201227825Stheraven __add_back_capacity(__n - __back_capacity); 2202227825Stheraven // __n <= __back_capacity 2203278724Sdim for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size()) 2204227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f); 2205227825Stheraven} 2206227825Stheraven 2207227825Stheraventemplate <class _Tp, class _Allocator> 2208227825Stheravenvoid 2209227825Stheravendeque<_Tp, _Allocator>::__append(size_type __n) 2210227825Stheraven{ 2211227825Stheraven allocator_type& __a = __base::__alloc(); 2212227825Stheraven size_type __back_capacity = __back_spare(); 2213227825Stheraven if (__n > __back_capacity) 2214227825Stheraven __add_back_capacity(__n - __back_capacity); 2215227825Stheraven // __n <= __back_capacity 2216227825Stheraven for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2217227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__i)); 2218227825Stheraven} 2219227825Stheraven 2220227825Stheraventemplate <class _Tp, class _Allocator> 2221227825Stheravenvoid 2222227825Stheravendeque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) 2223227825Stheraven{ 2224227825Stheraven allocator_type& __a = __base::__alloc(); 2225227825Stheraven size_type __back_capacity = __back_spare(); 2226227825Stheraven if (__n > __back_capacity) 2227227825Stheraven __add_back_capacity(__n - __back_capacity); 2228227825Stheraven // __n <= __back_capacity 2229227825Stheraven for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2230227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2231227825Stheraven} 2232227825Stheraven 2233227825Stheraven// Create front capacity for one block of elements. 2234227825Stheraven// Strong guarantee. Either do it or don't touch anything. 2235227825Stheraventemplate <class _Tp, class _Allocator> 2236227825Stheravenvoid 2237227825Stheravendeque<_Tp, _Allocator>::__add_front_capacity() 2238227825Stheraven{ 2239227825Stheraven allocator_type& __a = __base::__alloc(); 2240227825Stheraven if (__back_spare() >= __base::__block_size) 2241227825Stheraven { 2242227825Stheraven __base::__start_ += __base::__block_size; 2243227825Stheraven pointer __pt = __base::__map_.back(); 2244227825Stheraven __base::__map_.pop_back(); 2245227825Stheraven __base::__map_.push_front(__pt); 2246227825Stheraven } 2247227825Stheraven // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer 2248227825Stheraven else if (__base::__map_.size() < __base::__map_.capacity()) 2249227825Stheraven { // we can put the new buffer into the map, but don't shift things around 2250227825Stheraven // until all buffers are allocated. If we throw, we don't need to fix 2251227825Stheraven // anything up (any added buffers are undetectible) 2252227825Stheraven if (__base::__map_.__front_spare() > 0) 2253227825Stheraven __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2254227825Stheraven else 2255227825Stheraven { 2256227825Stheraven __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2257227825Stheraven // Done allocating, reorder capacity 2258227825Stheraven pointer __pt = __base::__map_.back(); 2259227825Stheraven __base::__map_.pop_back(); 2260227825Stheraven __base::__map_.push_front(__pt); 2261227825Stheraven } 2262227825Stheraven __base::__start_ = __base::__map_.size() == 1 ? 2263227825Stheraven __base::__block_size / 2 : 2264227825Stheraven __base::__start_ + __base::__block_size; 2265227825Stheraven } 2266227825Stheraven // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2267227825Stheraven else 2268227825Stheraven { 2269227825Stheraven __split_buffer<pointer, typename __base::__pointer_allocator&> 2270227825Stheraven __buf(max<size_type>(2 * __base::__map_.capacity(), 1), 2271227825Stheraven 0, __base::__map_.__alloc()); 2272227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2273227825Stheraven try 2274227825Stheraven { 2275227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2276227825Stheraven __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2277227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2278227825Stheraven } 2279227825Stheraven catch (...) 2280227825Stheraven { 2281227825Stheraven __alloc_traits::deallocate(__a, __buf.front(), __base::__block_size); 2282227825Stheraven throw; 2283227825Stheraven } 2284227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2285227825Stheraven for (typename __base::__map_pointer __i = __base::__map_.begin(); 2286227825Stheraven __i != __base::__map_.end(); ++__i) 2287227825Stheraven __buf.push_back(*__i); 2288227825Stheraven _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2289227825Stheraven _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2290227825Stheraven _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2291227825Stheraven _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2292227825Stheraven __base::__start_ = __base::__map_.size() == 1 ? 2293227825Stheraven __base::__block_size / 2 : 2294227825Stheraven __base::__start_ + __base::__block_size; 2295227825Stheraven } 2296227825Stheraven} 2297227825Stheraven 2298227825Stheraven// Create front capacity for __n elements. 2299227825Stheraven// Strong guarantee. Either do it or don't touch anything. 2300227825Stheraventemplate <class _Tp, class _Allocator> 2301227825Stheravenvoid 2302227825Stheravendeque<_Tp, _Allocator>::__add_front_capacity(size_type __n) 2303227825Stheraven{ 2304227825Stheraven allocator_type& __a = __base::__alloc(); 2305227825Stheraven size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2306227825Stheraven // Number of unused blocks at back: 2307227825Stheraven size_type __back_capacity = __back_spare() / __base::__block_size; 2308227825Stheraven __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need 2309227825Stheraven __nb -= __back_capacity; // number of blocks need to allocate 2310227825Stheraven // If __nb == 0, then we have sufficient capacity. 2311227825Stheraven if (__nb == 0) 2312227825Stheraven { 2313227825Stheraven __base::__start_ += __base::__block_size * __back_capacity; 2314227825Stheraven for (; __back_capacity > 0; --__back_capacity) 2315227825Stheraven { 2316227825Stheraven pointer __pt = __base::__map_.back(); 2317227825Stheraven __base::__map_.pop_back(); 2318227825Stheraven __base::__map_.push_front(__pt); 2319227825Stheraven } 2320227825Stheraven } 2321227825Stheraven // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2322227825Stheraven else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2323227825Stheraven { // we can put the new buffers into the map, but don't shift things around 2324227825Stheraven // until all buffers are allocated. If we throw, we don't need to fix 2325227825Stheraven // anything up (any added buffers are undetectible) 2326227825Stheraven for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1)) 2327227825Stheraven { 2328227825Stheraven if (__base::__map_.__front_spare() == 0) 2329227825Stheraven break; 2330227825Stheraven __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2331227825Stheraven } 2332227825Stheraven for (; __nb > 0; --__nb, ++__back_capacity) 2333227825Stheraven __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2334227825Stheraven // Done allocating, reorder capacity 2335227825Stheraven __base::__start_ += __back_capacity * __base::__block_size; 2336227825Stheraven for (; __back_capacity > 0; --__back_capacity) 2337227825Stheraven { 2338227825Stheraven pointer __pt = __base::__map_.back(); 2339227825Stheraven __base::__map_.pop_back(); 2340227825Stheraven __base::__map_.push_front(__pt); 2341227825Stheraven } 2342227825Stheraven } 2343227825Stheraven // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2344227825Stheraven else 2345227825Stheraven { 2346227825Stheraven size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty(); 2347227825Stheraven __split_buffer<pointer, typename __base::__pointer_allocator&> 2348227825Stheraven __buf(max<size_type>(2* __base::__map_.capacity(), 2349227825Stheraven __nb + __base::__map_.size()), 2350227825Stheraven 0, __base::__map_.__alloc()); 2351227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2352227825Stheraven try 2353227825Stheraven { 2354227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2355227825Stheraven for (; __nb > 0; --__nb) 2356227825Stheraven __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2357227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2358227825Stheraven } 2359227825Stheraven catch (...) 2360227825Stheraven { 2361227825Stheraven for (typename __base::__map_pointer __i = __buf.begin(); 2362227825Stheraven __i != __buf.end(); ++__i) 2363227825Stheraven __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2364227825Stheraven throw; 2365227825Stheraven } 2366227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2367227825Stheraven for (; __back_capacity > 0; --__back_capacity) 2368227825Stheraven { 2369227825Stheraven __buf.push_back(__base::__map_.back()); 2370227825Stheraven __base::__map_.pop_back(); 2371227825Stheraven } 2372227825Stheraven for (typename __base::__map_pointer __i = __base::__map_.begin(); 2373227825Stheraven __i != __base::__map_.end(); ++__i) 2374227825Stheraven __buf.push_back(*__i); 2375227825Stheraven _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2376227825Stheraven _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2377227825Stheraven _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2378227825Stheraven _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2379227825Stheraven __base::__start_ += __ds; 2380227825Stheraven } 2381227825Stheraven} 2382227825Stheraven 2383227825Stheraven// Create back capacity for one block of elements. 2384227825Stheraven// Strong guarantee. Either do it or don't touch anything. 2385227825Stheraventemplate <class _Tp, class _Allocator> 2386227825Stheravenvoid 2387227825Stheravendeque<_Tp, _Allocator>::__add_back_capacity() 2388227825Stheraven{ 2389227825Stheraven allocator_type& __a = __base::__alloc(); 2390227825Stheraven if (__front_spare() >= __base::__block_size) 2391227825Stheraven { 2392227825Stheraven __base::__start_ -= __base::__block_size; 2393227825Stheraven pointer __pt = __base::__map_.front(); 2394227825Stheraven __base::__map_.pop_front(); 2395227825Stheraven __base::__map_.push_back(__pt); 2396227825Stheraven } 2397227825Stheraven // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2398227825Stheraven else if (__base::__map_.size() < __base::__map_.capacity()) 2399227825Stheraven { // we can put the new buffer into the map, but don't shift things around 2400227825Stheraven // until it is allocated. If we throw, we don't need to fix 2401227825Stheraven // anything up (any added buffers are undetectible) 2402227825Stheraven if (__base::__map_.__back_spare() != 0) 2403227825Stheraven __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2404227825Stheraven else 2405227825Stheraven { 2406227825Stheraven __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2407227825Stheraven // Done allocating, reorder capacity 2408227825Stheraven pointer __pt = __base::__map_.front(); 2409227825Stheraven __base::__map_.pop_front(); 2410227825Stheraven __base::__map_.push_back(__pt); 2411227825Stheraven } 2412227825Stheraven } 2413227825Stheraven // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2414227825Stheraven else 2415227825Stheraven { 2416227825Stheraven __split_buffer<pointer, typename __base::__pointer_allocator&> 2417227825Stheraven __buf(max<size_type>(2* __base::__map_.capacity(), 1), 2418227825Stheraven __base::__map_.size(), 2419227825Stheraven __base::__map_.__alloc()); 2420227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2421227825Stheraven try 2422227825Stheraven { 2423227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2424227825Stheraven __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2425227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2426227825Stheraven } 2427227825Stheraven catch (...) 2428227825Stheraven { 2429227825Stheraven __alloc_traits::deallocate(__a, __buf.back(), __base::__block_size); 2430227825Stheraven throw; 2431227825Stheraven } 2432227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2433227825Stheraven for (typename __base::__map_pointer __i = __base::__map_.end(); 2434227825Stheraven __i != __base::__map_.begin();) 2435227825Stheraven __buf.push_front(*--__i); 2436227825Stheraven _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2437227825Stheraven _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2438227825Stheraven _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2439227825Stheraven _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2440227825Stheraven } 2441227825Stheraven} 2442227825Stheraven 2443227825Stheraven// Create back capacity for __n elements. 2444227825Stheraven// Strong guarantee. Either do it or don't touch anything. 2445227825Stheraventemplate <class _Tp, class _Allocator> 2446227825Stheravenvoid 2447227825Stheravendeque<_Tp, _Allocator>::__add_back_capacity(size_type __n) 2448227825Stheraven{ 2449227825Stheraven allocator_type& __a = __base::__alloc(); 2450227825Stheraven size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2451227825Stheraven // Number of unused blocks at front: 2452227825Stheraven size_type __front_capacity = __front_spare() / __base::__block_size; 2453227825Stheraven __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need 2454227825Stheraven __nb -= __front_capacity; // number of blocks need to allocate 2455227825Stheraven // If __nb == 0, then we have sufficient capacity. 2456227825Stheraven if (__nb == 0) 2457227825Stheraven { 2458227825Stheraven __base::__start_ -= __base::__block_size * __front_capacity; 2459227825Stheraven for (; __front_capacity > 0; --__front_capacity) 2460227825Stheraven { 2461227825Stheraven pointer __pt = __base::__map_.front(); 2462227825Stheraven __base::__map_.pop_front(); 2463227825Stheraven __base::__map_.push_back(__pt); 2464227825Stheraven } 2465227825Stheraven } 2466227825Stheraven // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2467227825Stheraven else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2468227825Stheraven { // we can put the new buffers into the map, but don't shift things around 2469227825Stheraven // until all buffers are allocated. If we throw, we don't need to fix 2470227825Stheraven // anything up (any added buffers are undetectible) 2471227825Stheraven for (; __nb > 0; --__nb) 2472227825Stheraven { 2473227825Stheraven if (__base::__map_.__back_spare() == 0) 2474227825Stheraven break; 2475227825Stheraven __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2476227825Stheraven } 2477227825Stheraven for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ += 2478227825Stheraven __base::__block_size - (__base::__map_.size() == 1)) 2479227825Stheraven __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2480227825Stheraven // Done allocating, reorder capacity 2481227825Stheraven __base::__start_ -= __base::__block_size * __front_capacity; 2482227825Stheraven for (; __front_capacity > 0; --__front_capacity) 2483227825Stheraven { 2484227825Stheraven pointer __pt = __base::__map_.front(); 2485227825Stheraven __base::__map_.pop_front(); 2486227825Stheraven __base::__map_.push_back(__pt); 2487227825Stheraven } 2488227825Stheraven } 2489227825Stheraven // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2490227825Stheraven else 2491227825Stheraven { 2492227825Stheraven size_type __ds = __front_capacity * __base::__block_size; 2493227825Stheraven __split_buffer<pointer, typename __base::__pointer_allocator&> 2494227825Stheraven __buf(max<size_type>(2* __base::__map_.capacity(), 2495227825Stheraven __nb + __base::__map_.size()), 2496227825Stheraven __base::__map_.size() - __front_capacity, 2497227825Stheraven __base::__map_.__alloc()); 2498227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2499227825Stheraven try 2500227825Stheraven { 2501227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2502227825Stheraven for (; __nb > 0; --__nb) 2503227825Stheraven __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2504227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2505227825Stheraven } 2506227825Stheraven catch (...) 2507227825Stheraven { 2508227825Stheraven for (typename __base::__map_pointer __i = __buf.begin(); 2509227825Stheraven __i != __buf.end(); ++__i) 2510227825Stheraven __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2511227825Stheraven throw; 2512227825Stheraven } 2513227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2514227825Stheraven for (; __front_capacity > 0; --__front_capacity) 2515227825Stheraven { 2516227825Stheraven __buf.push_back(__base::__map_.front()); 2517227825Stheraven __base::__map_.pop_front(); 2518227825Stheraven } 2519227825Stheraven for (typename __base::__map_pointer __i = __base::__map_.end(); 2520227825Stheraven __i != __base::__map_.begin();) 2521227825Stheraven __buf.push_front(*--__i); 2522227825Stheraven _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2523227825Stheraven _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2524227825Stheraven _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2525227825Stheraven _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2526227825Stheraven __base::__start_ -= __ds; 2527227825Stheraven } 2528227825Stheraven} 2529227825Stheraven 2530227825Stheraventemplate <class _Tp, class _Allocator> 2531227825Stheravenvoid 2532227825Stheravendeque<_Tp, _Allocator>::pop_front() 2533227825Stheraven{ 2534227825Stheraven allocator_type& __a = __base::__alloc(); 2535253159Stheraven __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() + 2536253159Stheraven __base::__start_ / __base::__block_size) + 2537253159Stheraven __base::__start_ % __base::__block_size)); 2538227825Stheraven --__base::size(); 2539227825Stheraven if (++__base::__start_ >= 2 * __base::__block_size) 2540227825Stheraven { 2541227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2542227825Stheraven __base::__map_.pop_front(); 2543227825Stheraven __base::__start_ -= __base::__block_size; 2544227825Stheraven } 2545227825Stheraven} 2546227825Stheraven 2547227825Stheraventemplate <class _Tp, class _Allocator> 2548227825Stheravenvoid 2549227825Stheravendeque<_Tp, _Allocator>::pop_back() 2550227825Stheraven{ 2551227825Stheraven allocator_type& __a = __base::__alloc(); 2552227825Stheraven size_type __p = __base::size() + __base::__start_ - 1; 2553253159Stheraven __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() + 2554253159Stheraven __p / __base::__block_size) + 2555253159Stheraven __p % __base::__block_size)); 2556227825Stheraven --__base::size(); 2557227825Stheraven if (__back_spare() >= 2 * __base::__block_size) 2558227825Stheraven { 2559227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2560227825Stheraven __base::__map_.pop_back(); 2561227825Stheraven } 2562227825Stheraven} 2563227825Stheraven 2564227825Stheraven// move assign [__f, __l) to [__r, __r + (__l-__f)). 2565227825Stheraven// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. 2566227825Stheraventemplate <class _Tp, class _Allocator> 2567227825Stheraventypename deque<_Tp, _Allocator>::iterator 2568227825Stheravendeque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, 2569227825Stheraven const_pointer& __vt) 2570227825Stheraven{ 2571227825Stheraven // as if 2572227825Stheraven // for (; __f != __l; ++__f, ++__r) 2573227825Stheraven // *__r = _VSTD::move(*__f); 2574227825Stheraven difference_type __n = __l - __f; 2575227825Stheraven while (__n > 0) 2576227825Stheraven { 2577227825Stheraven pointer __fb = __f.__ptr_; 2578227825Stheraven pointer __fe = *__f.__m_iter_ + __base::__block_size; 2579227825Stheraven difference_type __bs = __fe - __fb; 2580227825Stheraven if (__bs > __n) 2581227825Stheraven { 2582227825Stheraven __bs = __n; 2583227825Stheraven __fe = __fb + __bs; 2584227825Stheraven } 2585227825Stheraven if (__fb <= __vt && __vt < __fe) 2586253159Stheraven __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_; 2587227825Stheraven __r = _VSTD::move(__fb, __fe, __r); 2588227825Stheraven __n -= __bs; 2589227825Stheraven __f += __bs; 2590227825Stheraven } 2591227825Stheraven return __r; 2592227825Stheraven} 2593227825Stheraven 2594227825Stheraven// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. 2595227825Stheraven// If __vt points into [__f, __l), then add (__r - __l) to __vt. 2596227825Stheraventemplate <class _Tp, class _Allocator> 2597227825Stheraventypename deque<_Tp, _Allocator>::iterator 2598227825Stheravendeque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, 2599227825Stheraven const_pointer& __vt) 2600227825Stheraven{ 2601227825Stheraven // as if 2602227825Stheraven // while (__f != __l) 2603227825Stheraven // *--__r = _VSTD::move(*--__l); 2604227825Stheraven difference_type __n = __l - __f; 2605227825Stheraven while (__n > 0) 2606227825Stheraven { 2607227825Stheraven --__l; 2608227825Stheraven pointer __lb = *__l.__m_iter_; 2609227825Stheraven pointer __le = __l.__ptr_ + 1; 2610227825Stheraven difference_type __bs = __le - __lb; 2611227825Stheraven if (__bs > __n) 2612227825Stheraven { 2613227825Stheraven __bs = __n; 2614227825Stheraven __lb = __le - __bs; 2615227825Stheraven } 2616227825Stheraven if (__lb <= __vt && __vt < __le) 2617253159Stheraven __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_; 2618227825Stheraven __r = _VSTD::move_backward(__lb, __le, __r); 2619227825Stheraven __n -= __bs; 2620227825Stheraven __l -= __bs - 1; 2621227825Stheraven } 2622227825Stheraven return __r; 2623227825Stheraven} 2624227825Stheraven 2625227825Stheraven// move construct [__f, __l) to [__r, __r + (__l-__f)). 2626227825Stheraven// If __vt points into [__f, __l), then add (__r - __f) to __vt. 2627227825Stheraventemplate <class _Tp, class _Allocator> 2628227825Stheravenvoid 2629227825Stheravendeque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, 2630227825Stheraven iterator __r, const_pointer& __vt) 2631227825Stheraven{ 2632227825Stheraven allocator_type& __a = __base::__alloc(); 2633227825Stheraven // as if 2634227825Stheraven // for (; __f != __l; ++__r, ++__f, ++__base::size()) 2635227825Stheraven // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f)); 2636227825Stheraven difference_type __n = __l - __f; 2637227825Stheraven while (__n > 0) 2638227825Stheraven { 2639227825Stheraven pointer __fb = __f.__ptr_; 2640227825Stheraven pointer __fe = *__f.__m_iter_ + __base::__block_size; 2641227825Stheraven difference_type __bs = __fe - __fb; 2642227825Stheraven if (__bs > __n) 2643227825Stheraven { 2644227825Stheraven __bs = __n; 2645227825Stheraven __fe = __fb + __bs; 2646227825Stheraven } 2647227825Stheraven if (__fb <= __vt && __vt < __fe) 2648253159Stheraven __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_; 2649227825Stheraven for (; __fb != __fe; ++__fb, ++__r, ++__base::size()) 2650227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb)); 2651227825Stheraven __n -= __bs; 2652227825Stheraven __f += __bs; 2653227825Stheraven } 2654227825Stheraven} 2655227825Stheraven 2656227825Stheraven// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. 2657227825Stheraven// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. 2658227825Stheraventemplate <class _Tp, class _Allocator> 2659227825Stheravenvoid 2660227825Stheravendeque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l, 2661227825Stheraven iterator __r, const_pointer& __vt) 2662227825Stheraven{ 2663227825Stheraven allocator_type& __a = __base::__alloc(); 2664227825Stheraven // as if 2665227825Stheraven // for (iterator __j = __l; __j != __f;) 2666227825Stheraven // { 2667227825Stheraven // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j)); 2668227825Stheraven // --__base::__start_; 2669227825Stheraven // ++__base::size(); 2670227825Stheraven // } 2671227825Stheraven difference_type __n = __l - __f; 2672227825Stheraven while (__n > 0) 2673227825Stheraven { 2674227825Stheraven --__l; 2675227825Stheraven pointer __lb = *__l.__m_iter_; 2676227825Stheraven pointer __le = __l.__ptr_ + 1; 2677227825Stheraven difference_type __bs = __le - __lb; 2678227825Stheraven if (__bs > __n) 2679227825Stheraven { 2680227825Stheraven __bs = __n; 2681227825Stheraven __lb = __le - __bs; 2682227825Stheraven } 2683227825Stheraven if (__lb <= __vt && __vt < __le) 2684253159Stheraven __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_; 2685227825Stheraven while (__le != __lb) 2686227825Stheraven { 2687227825Stheraven __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le)); 2688227825Stheraven --__base::__start_; 2689227825Stheraven ++__base::size(); 2690227825Stheraven } 2691227825Stheraven __n -= __bs; 2692227825Stheraven __l -= __bs - 1; 2693227825Stheraven } 2694227825Stheraven} 2695227825Stheraven 2696227825Stheraventemplate <class _Tp, class _Allocator> 2697227825Stheraventypename deque<_Tp, _Allocator>::iterator 2698227825Stheravendeque<_Tp, _Allocator>::erase(const_iterator __f) 2699227825Stheraven{ 2700227825Stheraven difference_type __n = 1; 2701227825Stheraven iterator __b = __base::begin(); 2702227825Stheraven difference_type __pos = __f - __b; 2703227825Stheraven iterator __p = __b + __pos; 2704227825Stheraven allocator_type& __a = __base::__alloc(); 2705227825Stheraven if (__pos < (__base::size() - 1) / 2) 2706227825Stheraven { // erase from front 2707227825Stheraven _VSTD::move_backward(__b, __p, _VSTD::next(__p)); 2708227825Stheraven __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2709227825Stheraven --__base::size(); 2710227825Stheraven ++__base::__start_; 2711227825Stheraven if (__front_spare() >= 2 * __base::__block_size) 2712227825Stheraven { 2713227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2714227825Stheraven __base::__map_.pop_front(); 2715227825Stheraven __base::__start_ -= __base::__block_size; 2716227825Stheraven } 2717227825Stheraven } 2718227825Stheraven else 2719227825Stheraven { // erase from back 2720227825Stheraven iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p); 2721227825Stheraven __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2722227825Stheraven --__base::size(); 2723227825Stheraven if (__back_spare() >= 2 * __base::__block_size) 2724227825Stheraven { 2725227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2726227825Stheraven __base::__map_.pop_back(); 2727227825Stheraven } 2728227825Stheraven } 2729227825Stheraven return __base::begin() + __pos; 2730227825Stheraven} 2731227825Stheraven 2732227825Stheraventemplate <class _Tp, class _Allocator> 2733227825Stheraventypename deque<_Tp, _Allocator>::iterator 2734227825Stheravendeque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) 2735227825Stheraven{ 2736227825Stheraven difference_type __n = __l - __f; 2737227825Stheraven iterator __b = __base::begin(); 2738227825Stheraven difference_type __pos = __f - __b; 2739227825Stheraven iterator __p = __b + __pos; 2740227825Stheraven if (__n > 0) 2741227825Stheraven { 2742227825Stheraven allocator_type& __a = __base::__alloc(); 2743227825Stheraven if (__pos < (__base::size() - __n) / 2) 2744227825Stheraven { // erase from front 2745227825Stheraven iterator __i = _VSTD::move_backward(__b, __p, __p + __n); 2746227825Stheraven for (; __b != __i; ++__b) 2747227825Stheraven __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2748227825Stheraven __base::size() -= __n; 2749227825Stheraven __base::__start_ += __n; 2750227825Stheraven while (__front_spare() >= 2 * __base::__block_size) 2751227825Stheraven { 2752227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2753227825Stheraven __base::__map_.pop_front(); 2754227825Stheraven __base::__start_ -= __base::__block_size; 2755227825Stheraven } 2756227825Stheraven } 2757227825Stheraven else 2758227825Stheraven { // erase from back 2759227825Stheraven iterator __i = _VSTD::move(__p + __n, __base::end(), __p); 2760227825Stheraven for (iterator __e = __base::end(); __i != __e; ++__i) 2761227825Stheraven __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2762227825Stheraven __base::size() -= __n; 2763227825Stheraven while (__back_spare() >= 2 * __base::__block_size) 2764227825Stheraven { 2765227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2766227825Stheraven __base::__map_.pop_back(); 2767227825Stheraven } 2768227825Stheraven } 2769227825Stheraven } 2770227825Stheraven return __base::begin() + __pos; 2771227825Stheraven} 2772227825Stheraven 2773227825Stheraventemplate <class _Tp, class _Allocator> 2774227825Stheravenvoid 2775227825Stheravendeque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) 2776227825Stheraven{ 2777227825Stheraven iterator __e = __base::end(); 2778227825Stheraven difference_type __n = __e - __f; 2779227825Stheraven if (__n > 0) 2780227825Stheraven { 2781227825Stheraven allocator_type& __a = __base::__alloc(); 2782227825Stheraven iterator __b = __base::begin(); 2783227825Stheraven difference_type __pos = __f - __b; 2784227825Stheraven for (iterator __p = __b + __pos; __p != __e; ++__p) 2785227825Stheraven __alloc_traits::destroy(__a, _VSTD::addressof(*__p)); 2786227825Stheraven __base::size() -= __n; 2787227825Stheraven while (__back_spare() >= 2 * __base::__block_size) 2788227825Stheraven { 2789227825Stheraven __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2790227825Stheraven __base::__map_.pop_back(); 2791227825Stheraven } 2792227825Stheraven } 2793227825Stheraven} 2794227825Stheraven 2795227825Stheraventemplate <class _Tp, class _Allocator> 2796227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2797227825Stheravenvoid 2798227825Stheravendeque<_Tp, _Allocator>::swap(deque& __c) 2799227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2800227825Stheraven __is_nothrow_swappable<allocator_type>::value) 2801227825Stheraven{ 2802227825Stheraven __base::swap(__c); 2803227825Stheraven} 2804227825Stheraven 2805227825Stheraventemplate <class _Tp, class _Allocator> 2806227825Stheraveninline _LIBCPP_INLINE_VISIBILITY 2807227825Stheravenvoid 2808227825Stheravendeque<_Tp, _Allocator>::clear() _NOEXCEPT 2809227825Stheraven{ 2810227825Stheraven __base::clear(); 2811227825Stheraven} 2812227825Stheraven 2813227825Stheraventemplate <class _Tp, class _Allocator> 2814262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2815227825Stheravenbool 2816227825Stheravenoperator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2817227825Stheraven{ 2818227825Stheraven const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); 2819227825Stheraven return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2820227825Stheraven} 2821227825Stheraven 2822227825Stheraventemplate <class _Tp, class _Allocator> 2823262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2824227825Stheravenbool 2825227825Stheravenoperator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2826227825Stheraven{ 2827227825Stheraven return !(__x == __y); 2828227825Stheraven} 2829227825Stheraven 2830227825Stheraventemplate <class _Tp, class _Allocator> 2831262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2832227825Stheravenbool 2833227825Stheravenoperator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2834227825Stheraven{ 2835227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2836227825Stheraven} 2837227825Stheraven 2838227825Stheraventemplate <class _Tp, class _Allocator> 2839262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2840227825Stheravenbool 2841227825Stheravenoperator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2842227825Stheraven{ 2843227825Stheraven return __y < __x; 2844227825Stheraven} 2845227825Stheraven 2846227825Stheraventemplate <class _Tp, class _Allocator> 2847262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2848227825Stheravenbool 2849227825Stheravenoperator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2850227825Stheraven{ 2851227825Stheraven return !(__x < __y); 2852227825Stheraven} 2853227825Stheraven 2854227825Stheraventemplate <class _Tp, class _Allocator> 2855262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2856227825Stheravenbool 2857227825Stheravenoperator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2858227825Stheraven{ 2859227825Stheraven return !(__y < __x); 2860227825Stheraven} 2861227825Stheraven 2862227825Stheraventemplate <class _Tp, class _Allocator> 2863262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2864227825Stheravenvoid 2865227825Stheravenswap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) 2866227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2867227825Stheraven{ 2868227825Stheraven __x.swap(__y); 2869227825Stheraven} 2870227825Stheraven 2871227825Stheraven_LIBCPP_END_NAMESPACE_STD 2872227825Stheraven 2873227825Stheraven#endif // _LIBCPP_DEQUE 2874