codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===---------------------------- deque -----------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_DEQUE11#define _LIBCUDACXX_DEQUE12 13/*14 deque synopsis15 16namespace std17{18 19template <class T, class Allocator = allocator<T> >20class deque21{22public:23 // types:24 typedef T value_type;25 typedef Allocator allocator_type;26 27 typedef typename allocator_type::reference reference;28 typedef typename allocator_type::const_reference const_reference;29 typedef implementation-defined iterator;30 typedef implementation-defined const_iterator;31 typedef typename allocator_type::size_type size_type;32 typedef typename allocator_type::difference_type difference_type;33 34 typedef typename allocator_type::pointer pointer;35 typedef typename allocator_type::const_pointer const_pointer;36 typedef std::reverse_iterator<iterator> reverse_iterator;37 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;38 39 // construct/copy/destroy:40 deque() noexcept(is_nothrow_default_constructible<allocator_type>::value);41 explicit deque(const allocator_type& a);42 explicit deque(size_type n);43 explicit deque(size_type n, const allocator_type& a); // C++1444 deque(size_type n, const value_type& v);45 deque(size_type n, const value_type& v, const allocator_type& a);46 template <class InputIterator>47 deque(InputIterator f, InputIterator l);48 template <class InputIterator>49 deque(InputIterator f, InputIterator l, const allocator_type& a);50 deque(const deque& c);51 deque(deque&& c)52 noexcept(is_nothrow_move_constructible<allocator_type>::value);53 deque(initializer_list<value_type> il, const Allocator& a = allocator_type());54 deque(const deque& c, const allocator_type& a);55 deque(deque&& c, const allocator_type& a);56 ~deque();57 58 deque& operator=(const deque& c);59 deque& operator=(deque&& c)60 noexcept(61 allocator_type::propagate_on_container_move_assignment::value &&62 is_nothrow_move_assignable<allocator_type>::value);63 deque& operator=(initializer_list<value_type> il);64 65 template <class InputIterator>66 void assign(InputIterator f, InputIterator l);67 void assign(size_type n, const value_type& v);68 void assign(initializer_list<value_type> il);69 70 allocator_type get_allocator() const noexcept;71 72 // iterators:73 74 iterator begin() noexcept;75 const_iterator begin() const noexcept;76 iterator end() noexcept;77 const_iterator end() const noexcept;78 79 reverse_iterator rbegin() noexcept;80 const_reverse_iterator rbegin() const noexcept;81 reverse_iterator rend() noexcept;82 const_reverse_iterator rend() const noexcept;83 84 const_iterator cbegin() const noexcept;85 const_iterator cend() const noexcept;86 const_reverse_iterator crbegin() const noexcept;87 const_reverse_iterator crend() const noexcept;88 89 // capacity:90 size_type size() const noexcept;91 size_type max_size() const noexcept;92 void resize(size_type n);93 void resize(size_type n, const value_type& v);94 void shrink_to_fit();95 bool empty() const noexcept;96 97 // element access:98 reference operator[](size_type i);99 const_reference operator[](size_type i) const;100 reference at(size_type i);101 const_reference at(size_type i) const;102 reference front();103 const_reference front() const;104 reference back();105 const_reference back() const;106 107 // modifiers:108 void push_front(const value_type& v);109 void push_front(value_type&& v);110 void push_back(const value_type& v);111 void push_back(value_type&& v);112 template <class... Args> reference emplace_front(Args&&... args); // reference in C++17113 template <class... Args> reference emplace_back(Args&&... args); // reference in C++17114 template <class... Args> iterator emplace(const_iterator p, Args&&... args);115 iterator insert(const_iterator p, const value_type& v);116 iterator insert(const_iterator p, value_type&& v);117 iterator insert(const_iterator p, size_type n, const value_type& v);118 template <class InputIterator>119 iterator insert(const_iterator p, InputIterator f, InputIterator l);120 iterator insert(const_iterator p, initializer_list<value_type> il);121 void pop_front();122 void pop_back();123 iterator erase(const_iterator p);124 iterator erase(const_iterator f, const_iterator l);125 void swap(deque& c)126 noexcept(allocator_traits<allocator_type>::is_always_equal::value); // C++17127 void clear() noexcept;128};129 130template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>131 deque(InputIterator, InputIterator, Allocator = Allocator())132 -> deque<typename iterator_traits<InputIterator>::value_type, Allocator>;133 134template <class T, class Allocator>135 bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y);136template <class T, class Allocator>137 bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y);138template <class T, class Allocator>139 bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);140template <class T, class Allocator>141 bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y);142template <class T, class Allocator>143 bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);144template <class T, class Allocator>145 bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y);146 147// specialized algorithms:148template <class T, class Allocator>149 void swap(deque<T,Allocator>& x, deque<T,Allocator>& y)150 noexcept(noexcept(x.swap(y)));151 152template <class T, class Allocator, class U>153 void erase(deque<T, Allocator>& c, const U& value); // C++20154template <class T, class Allocator, class Predicate>155 void erase_if(deque<T, Allocator>& c, Predicate pred); // C++20156 157} // std158 159*/160 161#include <__config>162#include <__split_buffer>163#include <type_traits>164#include <initializer_list>165#include <iterator>166#include <algorithm>167#include <stdexcept>168#include <version>169 170#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)171# pragma GCC system_header172#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)173# pragma clang system_header174#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)175# pragma system_header176#endif // no system header177 178_LIBCUDACXX_PUSH_MACROS179#include <__undef_macros>180 181 182_LIBCUDACXX_BEGIN_NAMESPACE_STD183 184template <class _Tp, class _Allocator> class __deque_base;185template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCUDACXX_TEMPLATE_VIS deque;186 187template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,188 class _DiffType, _DiffType _BlockSize>189class _LIBCUDACXX_TEMPLATE_VIS __deque_iterator;190 191template <class _RAIter,192 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>193__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>194copy(_RAIter __f,195 _RAIter __l,196 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,197 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);198 199template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,200 class _OutputIterator>201_OutputIterator202copy(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,203 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,204 _OutputIterator __r);205 206template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,207 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>208__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>209copy(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,210 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,211 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);212 213template <class _RAIter,214 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>215__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>216copy_backward(_RAIter __f,217 _RAIter __l,218 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,219 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);220 221template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,222 class _OutputIterator>223_OutputIterator224copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,225 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,226 _OutputIterator __r);227 228template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,229 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>230__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>231copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,232 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,233 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);234 235template <class _RAIter,236 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>237__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>238move(_RAIter __f,239 _RAIter __l,240 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,241 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);242 243template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,244 class _OutputIterator>245_OutputIterator246move(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,247 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,248 _OutputIterator __r);249 250template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,251 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>252__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>253move(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,254 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,255 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);256 257template <class _RAIter,258 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>259__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>260move_backward(_RAIter __f,261 _RAIter __l,262 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,263 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0);264 265template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,266 class _OutputIterator>267_OutputIterator268move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,269 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,270 _OutputIterator __r);271 272template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,273 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>274__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>275move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,276 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,277 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);278 279template <class _ValueType, class _DiffType>280struct __deque_block_size {281 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16;282};283 284template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,285 class _DiffType, _DiffType _BS =286#ifdef _LIBCUDACXX_ABI_INCOMPLETE_TYPES_IN_DEQUE287// Keep template parameter to avoid changing all template declarations thoughout288// this file.289 0290#else291 __deque_block_size<_ValueType, _DiffType>::value292#endif293 >294class _LIBCUDACXX_TEMPLATE_VIS __deque_iterator295{296 typedef _MapPointer __map_iterator;297public:298 typedef _Pointer pointer;299 typedef _DiffType difference_type;300private:301 __map_iterator __m_iter_;302 pointer __ptr_;303 304 static const difference_type __block_size;305public:306 typedef _ValueType value_type;307 typedef random_access_iterator_tag iterator_category;308 typedef _Reference reference;309 310 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator() noexcept311#if _LIBCUDACXX_STD_VER > 11312 : __m_iter_(nullptr), __ptr_(nullptr)313#endif314 {}315 316 template <class _Pp, class _Rp, class _MP>317 _LIBCUDACXX_INLINE_VISIBILITY318 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it,319 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) noexcept320 : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {}321 322 _LIBCUDACXX_INLINE_VISIBILITY reference operator*() const {return *__ptr_;}323 _LIBCUDACXX_INLINE_VISIBILITY pointer operator->() const {return __ptr_;}324 325 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator& operator++()326 {327 if (++__ptr_ - *__m_iter_ == __block_size)328 {329 ++__m_iter_;330 __ptr_ = *__m_iter_;331 }332 return *this;333 }334 335 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator operator++(int)336 {337 __deque_iterator __tmp = *this;338 ++(*this);339 return __tmp;340 }341 342 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator& operator--()343 {344 if (__ptr_ == *__m_iter_)345 {346 --__m_iter_;347 __ptr_ = *__m_iter_ + __block_size;348 }349 --__ptr_;350 return *this;351 }352 353 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator operator--(int)354 {355 __deque_iterator __tmp = *this;356 --(*this);357 return __tmp;358 }359 360 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n)361 {362 if (__n != 0)363 {364 __n += __ptr_ - *__m_iter_;365 if (__n > 0)366 {367 __m_iter_ += __n / __block_size;368 __ptr_ = *__m_iter_ + __n % __block_size;369 }370 else // (__n < 0)371 {372 difference_type __z = __block_size - 1 - __n;373 __m_iter_ -= __z / __block_size;374 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size);375 }376 }377 return *this;378 }379 380 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n)381 {382 return *this += -__n;383 }384 385 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const386 {387 __deque_iterator __t(*this);388 __t += __n;389 return __t;390 }391 392 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const393 {394 __deque_iterator __t(*this);395 __t -= __n;396 return __t;397 }398 399 _LIBCUDACXX_INLINE_VISIBILITY400 friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it)401 {return __it + __n;}402 403 _LIBCUDACXX_INLINE_VISIBILITY404 friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y)405 {406 if (__x != __y)407 return (__x.__m_iter_ - __y.__m_iter_) * __block_size408 + (__x.__ptr_ - *__x.__m_iter_)409 - (__y.__ptr_ - *__y.__m_iter_);410 return 0;411 }412 413 _LIBCUDACXX_INLINE_VISIBILITY reference operator[](difference_type __n) const414 {return *(*this + __n);}415 416 _LIBCUDACXX_INLINE_VISIBILITY friend417 bool operator==(const __deque_iterator& __x, const __deque_iterator& __y)418 {return __x.__ptr_ == __y.__ptr_;}419 420 _LIBCUDACXX_INLINE_VISIBILITY friend421 bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y)422 {return !(__x == __y);}423 424 _LIBCUDACXX_INLINE_VISIBILITY friend425 bool operator<(const __deque_iterator& __x, const __deque_iterator& __y)426 {return __x.__m_iter_ < __y.__m_iter_ ||427 (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);}428 429 _LIBCUDACXX_INLINE_VISIBILITY friend430 bool operator>(const __deque_iterator& __x, const __deque_iterator& __y)431 {return __y < __x;}432 433 _LIBCUDACXX_INLINE_VISIBILITY friend434 bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y)435 {return !(__y < __x);}436 437 _LIBCUDACXX_INLINE_VISIBILITY friend438 bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y)439 {return !(__x < __y);}440 441private:442 _LIBCUDACXX_INLINE_VISIBILITY __deque_iterator(__map_iterator __m, pointer __p) noexcept443 : __m_iter_(__m), __ptr_(__p) {}444 445 template <class _Tp, class _Ap> friend class __deque_base;446 template <class _Tp, class _Ap> friend class _LIBCUDACXX_TEMPLATE_VIS deque;447 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp>448 friend class _LIBCUDACXX_TEMPLATE_VIS __deque_iterator;449 450 template <class _RAIter,451 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>452 friend453 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>454 copy(_RAIter __f,455 _RAIter __l,456 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,457 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);458 459 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,460 class _OutputIterator>461 friend462 _OutputIterator463 copy(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,464 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,465 _OutputIterator __r);466 467 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,468 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>469 friend470 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>471 copy(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,472 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,473 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);474 475 template <class _RAIter,476 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>477 friend478 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>479 copy_backward(_RAIter __f,480 _RAIter __l,481 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,482 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);483 484 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,485 class _OutputIterator>486 friend487 _OutputIterator488 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,489 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,490 _OutputIterator __r);491 492 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,493 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>494 friend495 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>496 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,497 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,498 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);499 500 template <class _RAIter,501 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>502 friend503 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>504 move(_RAIter __f,505 _RAIter __l,506 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,507 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);508 509 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,510 class _OutputIterator>511 friend512 _OutputIterator513 move(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,514 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,515 _OutputIterator __r);516 517 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,518 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>519 friend520 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>521 move(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,522 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,523 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);524 525 template <class _RAIter,526 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>527 friend528 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>529 move_backward(_RAIter __f,530 _RAIter __l,531 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,532 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*);533 534 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,535 class _OutputIterator>536 friend537 _OutputIterator538 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,539 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,540 _OutputIterator __r);541 542 template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,543 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>544 friend545 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>546 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,547 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,548 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r);549};550 551template <class _ValueType, class _Pointer, class _Reference, class _MapPointer,552 class _DiffType, _DiffType _BlockSize>553const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer,554 _DiffType, _BlockSize>::__block_size =555 __deque_block_size<_ValueType, _DiffType>::value;556 557// copy558 559template <class _RAIter,560 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>561__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>562copy(_RAIter __f,563 _RAIter __l,564 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,565 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)566{567 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::difference_type difference_type;568 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::pointer pointer;569 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::__block_size;570 while (__f != __l)571 {572 pointer __rb = __r.__ptr_;573 pointer __re = *__r.__m_iter_ + __block_size;574 difference_type __bs = __re - __rb;575 difference_type __n = __l - __f;576 _RAIter __m = __l;577 if (__n > __bs)578 {579 __n = __bs;580 __m = __f + __n;581 }582 _CUDA_VSTD::copy(__f, __m, __rb);583 __f = __m;584 __r += __n;585 }586 return __r;587}588 589template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,590 class _OutputIterator>591_OutputIterator592copy(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,593 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,594 _OutputIterator __r)595{596 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;597 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;598 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::__block_size;599 difference_type __n = __l - __f;600 while (__n > 0)601 {602 pointer __fb = __f.__ptr_;603 pointer __fe = *__f.__m_iter_ + __block_size;604 difference_type __bs = __fe - __fb;605 if (__bs > __n)606 {607 __bs = __n;608 __fe = __fb + __bs;609 }610 __r = _CUDA_VSTD::copy(__fb, __fe, __r);611 __n -= __bs;612 __f += __bs;613 }614 return __r;615}616 617template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,618 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>619__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>620copy(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,621 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,622 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r)623{624 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;625 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;626 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::__block_size;627 difference_type __n = __l - __f;628 while (__n > 0)629 {630 pointer __fb = __f.__ptr_;631 pointer __fe = *__f.__m_iter_ + __block_size;632 difference_type __bs = __fe - __fb;633 if (__bs > __n)634 {635 __bs = __n;636 __fe = __fb + __bs;637 }638 __r = _CUDA_VSTD::copy(__fb, __fe, __r);639 __n -= __bs;640 __f += __bs;641 }642 return __r;643}644 645// copy_backward646 647template <class _RAIter,648 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>649__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>650copy_backward(_RAIter __f,651 _RAIter __l,652 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,653 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)654{655 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::difference_type difference_type;656 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::pointer pointer;657 while (__f != __l)658 {659 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __rp = _CUDA_VSTD::prev(__r);660 pointer __rb = *__rp.__m_iter_;661 pointer __re = __rp.__ptr_ + 1;662 difference_type __bs = __re - __rb;663 difference_type __n = __l - __f;664 _RAIter __m = __f;665 if (__n > __bs)666 {667 __n = __bs;668 __m = __l - __n;669 }670 _CUDA_VSTD::copy_backward(__m, __l, __re);671 __l = __m;672 __r -= __n;673 }674 return __r;675}676 677template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,678 class _OutputIterator>679_OutputIterator680copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,681 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,682 _OutputIterator __r)683{684 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;685 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;686 difference_type __n = __l - __f;687 while (__n > 0)688 {689 --__l;690 pointer __lb = *__l.__m_iter_;691 pointer __le = __l.__ptr_ + 1;692 difference_type __bs = __le - __lb;693 if (__bs > __n)694 {695 __bs = __n;696 __lb = __le - __bs;697 }698 __r = _CUDA_VSTD::copy_backward(__lb, __le, __r);699 __n -= __bs;700 __l -= __bs - 1;701 }702 return __r;703}704 705template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,706 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>707__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>708copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,709 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,710 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r)711{712 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;713 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;714 difference_type __n = __l - __f;715 while (__n > 0)716 {717 --__l;718 pointer __lb = *__l.__m_iter_;719 pointer __le = __l.__ptr_ + 1;720 difference_type __bs = __le - __lb;721 if (__bs > __n)722 {723 __bs = __n;724 __lb = __le - __bs;725 }726 __r = _CUDA_VSTD::copy_backward(__lb, __le, __r);727 __n -= __bs;728 __l -= __bs - 1;729 }730 return __r;731}732 733// move734 735template <class _RAIter,736 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>737__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>738move(_RAIter __f,739 _RAIter __l,740 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,741 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)742{743 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::difference_type difference_type;744 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::pointer pointer;745 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::__block_size;746 while (__f != __l)747 {748 pointer __rb = __r.__ptr_;749 pointer __re = *__r.__m_iter_ + __block_size;750 difference_type __bs = __re - __rb;751 difference_type __n = __l - __f;752 _RAIter __m = __l;753 if (__n > __bs)754 {755 __n = __bs;756 __m = __f + __n;757 }758 _CUDA_VSTD::move(__f, __m, __rb);759 __f = __m;760 __r += __n;761 }762 return __r;763}764 765template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,766 class _OutputIterator>767_OutputIterator768move(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,769 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,770 _OutputIterator __r)771{772 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;773 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;774 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::__block_size;775 difference_type __n = __l - __f;776 while (__n > 0)777 {778 pointer __fb = __f.__ptr_;779 pointer __fe = *__f.__m_iter_ + __block_size;780 difference_type __bs = __fe - __fb;781 if (__bs > __n)782 {783 __bs = __n;784 __fe = __fb + __bs;785 }786 __r = _CUDA_VSTD::move(__fb, __fe, __r);787 __n -= __bs;788 __f += __bs;789 }790 return __r;791}792 793template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,794 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>795__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>796move(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,797 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,798 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r)799{800 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;801 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;802 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::__block_size;803 difference_type __n = __l - __f;804 while (__n > 0)805 {806 pointer __fb = __f.__ptr_;807 pointer __fe = *__f.__m_iter_ + __block_size;808 difference_type __bs = __fe - __fb;809 if (__bs > __n)810 {811 __bs = __n;812 __fe = __fb + __bs;813 }814 __r = _CUDA_VSTD::move(__fb, __fe, __r);815 __n -= __bs;816 __f += __bs;817 }818 return __r;819}820 821// move_backward822 823template <class _RAIter,824 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>825__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>826move_backward(_RAIter __f,827 _RAIter __l,828 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r,829 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*)830{831 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::difference_type difference_type;832 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>::pointer pointer;833 while (__f != __l)834 {835 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __rp = _CUDA_VSTD::prev(__r);836 pointer __rb = *__rp.__m_iter_;837 pointer __re = __rp.__ptr_ + 1;838 difference_type __bs = __re - __rb;839 difference_type __n = __l - __f;840 _RAIter __m = __f;841 if (__n > __bs)842 {843 __n = __bs;844 __m = __l - __n;845 }846 _CUDA_VSTD::move_backward(__m, __l, __re);847 __l = __m;848 __r -= __n;849 }850 return __r;851}852 853template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,854 class _OutputIterator>855_OutputIterator856move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,857 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,858 _OutputIterator __r)859{860 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;861 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;862 difference_type __n = __l - __f;863 while (__n > 0)864 {865 --__l;866 pointer __lb = *__l.__m_iter_;867 pointer __le = __l.__ptr_ + 1;868 difference_type __bs = __le - __lb;869 if (__bs > __n)870 {871 __bs = __n;872 __lb = __le - __bs;873 }874 __r = _CUDA_VSTD::move_backward(__lb, __le, __r);875 __n -= __bs;876 __l -= __bs - 1;877 }878 return __r;879}880 881template <class _V1, class _P1, class _R1, class _M1, class _Diff1, _Diff1 _B1,882 class _V2, class _P2, class _R2, class _M2, class _Diff2, _Diff2 _B2>883__deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2>884move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __f,885 __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1> __l,886 __deque_iterator<_V2, _P2, _R2, _M2, _Diff2, _B2> __r)887{888 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::difference_type difference_type;889 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _Diff1, _B1>::pointer pointer;890 difference_type __n = __l - __f;891 while (__n > 0)892 {893 --__l;894 pointer __lb = *__l.__m_iter_;895 pointer __le = __l.__ptr_ + 1;896 difference_type __bs = __le - __lb;897 if (__bs > __n)898 {899 __bs = __n;900 __lb = __le - __bs;901 }902 __r = _CUDA_VSTD::move_backward(__lb, __le, __r);903 __n -= __bs;904 __l -= __bs - 1;905 }906 return __r;907}908 909template <bool>910class __deque_base_common911{912protected:913 _LIBCUDACXX_NORETURN void __throw_length_error() const;914 _LIBCUDACXX_NORETURN void __throw_out_of_range() const;915};916 917template <bool __b>918void919__deque_base_common<__b>::__throw_length_error() const920{921 _CUDA_VSTD::__throw_length_error("deque");922}923 924template <bool __b>925void926__deque_base_common<__b>::__throw_out_of_range() const927{928 _CUDA_VSTD::__throw_out_of_range("deque");929}930 931template <class _Tp, class _Allocator>932class __deque_base933 : protected __deque_base_common<true>934{935 __deque_base(const __deque_base& __c);936 __deque_base& operator=(const __deque_base& __c);937public:938 typedef _Allocator allocator_type;939 typedef allocator_traits<allocator_type> __alloc_traits;940 typedef typename __alloc_traits::size_type size_type;941 942 typedef _Tp value_type;943 typedef value_type& reference;944 typedef const value_type& const_reference;945 typedef typename __alloc_traits::difference_type difference_type;946 typedef typename __alloc_traits::pointer pointer;947 typedef typename __alloc_traits::const_pointer const_pointer;948 949 static const difference_type __block_size;950 951 typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator;952 typedef allocator_traits<__pointer_allocator> __map_traits;953 typedef typename __map_traits::pointer __map_pointer;954 typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator;955 typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer;956 typedef __split_buffer<pointer, __pointer_allocator> __map;957 958 typedef __deque_iterator<value_type, pointer, reference, __map_pointer,959 difference_type> iterator;960 typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer,961 difference_type> const_iterator;962 963 struct __deque_block_range {964 explicit __deque_block_range(pointer __b, pointer __e) noexcept : __begin_(__b), __end_(__e) {}965 const pointer __begin_;966 const pointer __end_;967 };968 969 struct __deque_range {970 iterator __pos_;971 const iterator __end_;972 973 __deque_range(iterator __pos, iterator __e) noexcept974 : __pos_(__pos), __end_(__e) {}975 976 explicit operator bool() const noexcept {977 return __pos_ != __end_;978 }979 980 __deque_range begin() const {981 return *this;982 }983 984 __deque_range end() const {985 return __deque_range(__end_, __end_);986 }987 __deque_block_range operator*() const noexcept {988 if (__pos_.__m_iter_ == __end_.__m_iter_) {989 return __deque_block_range(__pos_.__ptr_, __end_.__ptr_);990 }991 return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size);992 }993 994 __deque_range& operator++() noexcept {995 if (__pos_.__m_iter_ == __end_.__m_iter_) {996 __pos_ = __end_;997 } else {998 ++__pos_.__m_iter_;999 __pos_.__ptr_ = *__pos_.__m_iter_;1000 }1001 return *this;1002 }1003 1004 1005 friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) {1006 return __lhs.__pos_ == __rhs.__pos_;1007 }1008 friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) {1009 return !(__lhs == __rhs);1010 }1011 };1012 1013 1014 1015 struct _ConstructTransaction {1016 _ConstructTransaction(__deque_base* __db, __deque_block_range& __r)1017 : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {}1018 1019 1020 ~_ConstructTransaction() {1021 __base_->size() += (__pos_ - __begin_);1022 }1023 1024 pointer __pos_;1025 const pointer __end_;1026 private:1027 const pointer __begin_;1028 __deque_base * const __base_;1029 };1030 1031protected:1032 __map __map_;1033 size_type __start_;1034 __compressed_pair<size_type, allocator_type> __size_;1035 1036 iterator begin() noexcept;1037 const_iterator begin() const noexcept;1038 iterator end() noexcept;1039 const_iterator end() const noexcept;1040 1041 _LIBCUDACXX_INLINE_VISIBILITY size_type& size() {return __size_.first();}1042 _LIBCUDACXX_INLINE_VISIBILITY1043 const size_type& size() const noexcept {return __size_.first();}1044 _LIBCUDACXX_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();}1045 _LIBCUDACXX_INLINE_VISIBILITY1046 const allocator_type& __alloc() const noexcept {return __size_.second();}1047 1048 _LIBCUDACXX_INLINE_VISIBILITY1049 __deque_base()1050 noexcept(is_nothrow_default_constructible<allocator_type>::value);1051 _LIBCUDACXX_INLINE_VISIBILITY1052 explicit __deque_base(const allocator_type& __a);1053public:1054 ~__deque_base();1055 1056 __deque_base(__deque_base&& __c)1057 noexcept(is_nothrow_move_constructible<allocator_type>::value);1058 __deque_base(__deque_base&& __c, const allocator_type& __a);1059 1060 void swap(__deque_base& __c)1061#if _LIBCUDACXX_STD_VER >= 141062 noexcept;1063#else1064 noexcept(!__alloc_traits::propagate_on_container_swap::value ||1065 __is_nothrow_swappable<allocator_type>::value);1066#endif1067protected:1068 void clear() noexcept;1069 1070 bool __invariants() const;1071 1072 _LIBCUDACXX_INLINE_VISIBILITY1073 void __move_assign(__deque_base& __c)1074 noexcept(__alloc_traits::propagate_on_container_move_assignment::value &&1075 is_nothrow_move_assignable<allocator_type>::value)1076 {1077 __map_ = _CUDA_VSTD::move(__c.__map_);1078 __start_ = __c.__start_;1079 size() = __c.size();1080 __move_assign_alloc(__c);1081 __c.__start_ = __c.size() = 0;1082 }1083 1084 _LIBCUDACXX_INLINE_VISIBILITY1085 void __move_assign_alloc(__deque_base& __c)1086 noexcept(!__alloc_traits::propagate_on_container_move_assignment::value ||1087 is_nothrow_move_assignable<allocator_type>::value)1088 {__move_assign_alloc(__c, integral_constant<bool,1089 __alloc_traits::propagate_on_container_move_assignment::value>());}1090 1091private:1092 _LIBCUDACXX_INLINE_VISIBILITY1093 void __move_assign_alloc(__deque_base& __c, true_type)1094 noexcept(is_nothrow_move_assignable<allocator_type>::value)1095 {1096 __alloc() = _CUDA_VSTD::move(__c.__alloc());1097 }1098 1099 _LIBCUDACXX_INLINE_VISIBILITY1100 void __move_assign_alloc(__deque_base&, false_type) noexcept1101 {}1102};1103 1104template <class _Tp, class _Allocator>1105const typename __deque_base<_Tp, _Allocator>::difference_type1106 __deque_base<_Tp, _Allocator>::__block_size =1107 __deque_block_size<value_type, difference_type>::value;1108 1109template <class _Tp, class _Allocator>1110bool1111__deque_base<_Tp, _Allocator>::__invariants() const1112{1113 if (!__map_.__invariants())1114 return false;1115 if (__map_.size() >= size_type(-1) / __block_size)1116 return false;1117 for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end();1118 __i != __e; ++__i)1119 if (*__i == nullptr)1120 return false;1121 if (__map_.size() != 0)1122 {1123 if (size() >= __map_.size() * __block_size)1124 return false;1125 if (__start_ >= __map_.size() * __block_size - size())1126 return false;1127 }1128 else1129 {1130 if (size() != 0)1131 return false;1132 if (__start_ != 0)1133 return false;1134 }1135 return true;1136}1137 1138template <class _Tp, class _Allocator>1139typename __deque_base<_Tp, _Allocator>::iterator1140__deque_base<_Tp, _Allocator>::begin() noexcept1141{1142 __map_pointer __mp = __map_.begin() + __start_ / __block_size;1143 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);1144}1145 1146template <class _Tp, class _Allocator>1147typename __deque_base<_Tp, _Allocator>::const_iterator1148__deque_base<_Tp, _Allocator>::begin() const noexcept1149{1150 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size);1151 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size);1152}1153 1154template <class _Tp, class _Allocator>1155typename __deque_base<_Tp, _Allocator>::iterator1156__deque_base<_Tp, _Allocator>::end() noexcept1157{1158 size_type __p = size() + __start_;1159 __map_pointer __mp = __map_.begin() + __p / __block_size;1160 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);1161}1162 1163template <class _Tp, class _Allocator>1164typename __deque_base<_Tp, _Allocator>::const_iterator1165__deque_base<_Tp, _Allocator>::end() const noexcept1166{1167 size_type __p = size() + __start_;1168 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size);1169 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size);1170}1171 1172template <class _Tp, class _Allocator>1173inline1174__deque_base<_Tp, _Allocator>::__deque_base()1175 noexcept(is_nothrow_default_constructible<allocator_type>::value)1176 : __start_(0), __size_(0) {}1177 1178template <class _Tp, class _Allocator>1179inline1180__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a)1181 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {}1182 1183template <class _Tp, class _Allocator>1184__deque_base<_Tp, _Allocator>::~__deque_base()1185{1186 clear();1187 typename __map::iterator __i = __map_.begin();1188 typename __map::iterator __e = __map_.end();1189 for (; __i != __e; ++__i)1190 __alloc_traits::deallocate(__alloc(), *__i, __block_size);1191}1192 1193template <class _Tp, class _Allocator>1194__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c)1195 noexcept(is_nothrow_move_constructible<allocator_type>::value)1196 : __map_(_CUDA_VSTD::move(__c.__map_)),1197 __start_(_CUDA_VSTD::move(__c.__start_)),1198 __size_(_CUDA_VSTD::move(__c.__size_))1199{1200 __c.__start_ = 0;