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