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