1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 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-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP_DEQUE 11#define _LIBCPP_DEQUE 12 13/* 14 deque synopsis 15 16namespace std 17{ 18 19template <class T, class Allocator = allocator<T> > 20class deque 21{ 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++14 44 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++17 113 template <class... Args> reference emplace_back(Args&&... args); // reference in C++17 114 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++17 127 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>; // C++17 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 typename deque<T, Allocator>::size_type 154 erase(deque<T, Allocator>& c, const U& value); // C++20 155template <class T, class Allocator, class Predicate> 156 typename deque<T, Allocator>::size_type 157 erase_if(deque<T, Allocator>& c, Predicate pred); // C++20 158 159} // std 160 161*/ 162 163#include <__algorithm/copy.h> 164#include <__algorithm/copy_backward.h> 165#include <__algorithm/equal.h> 166#include <__algorithm/fill_n.h> 167#include <__algorithm/lexicographical_compare.h> 168#include <__algorithm/min.h> 169#include <__algorithm/remove.h> 170#include <__algorithm/remove_if.h> 171#include <__algorithm/unwrap_iter.h> 172#include <__assert> // all public C++ headers provide the assertion handler 173#include <__config> 174#include <__format/enable_insertable.h> 175#include <__iterator/iterator_traits.h> 176#include <__split_buffer> 177#include <__utility/forward.h> 178#include <__utility/move.h> 179#include <__utility/swap.h> 180#include <compare> 181#include <initializer_list> 182#include <iterator> 183#include <limits> 184#include <stdexcept> 185#include <type_traits> 186#include <version> 187 188#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 189# pragma GCC system_header 190#endif 191 192_LIBCPP_PUSH_MACROS 193#include <__undef_macros> 194 195 196_LIBCPP_BEGIN_NAMESPACE_STD 197 198template <class _Tp, class _Allocator> class __deque_base; 199template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TEMPLATE_VIS deque; 200 201template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 202 class _DiffType, _DiffType _BlockSize> 203class _LIBCPP_TEMPLATE_VIS __deque_iterator; 204 205template <class _RAIter, 206 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 207__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 208copy(_RAIter __f, 209 _RAIter __l, 210 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 211 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); 212 213template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 214 class _OutputIterator> 215_OutputIterator 216copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 217 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 218 _OutputIterator __r); 219 220template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 221 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 222__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 223copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 224 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 225 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 226 227template <class _RAIter, 228 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 229__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 230copy_backward(_RAIter __f, 231 _RAIter __l, 232 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 233 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); 234 235template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 236 class _OutputIterator> 237_OutputIterator 238copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 239 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 240 _OutputIterator __r); 241 242template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 243 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 244__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 245copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 246 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 247 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 248 249template <class _RAIter, 250 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 251__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 252move(_RAIter __f, 253 _RAIter __l, 254 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 255 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); 256 257template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 258 class _OutputIterator> 259_OutputIterator 260move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 261 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 262 _OutputIterator __r); 263 264template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 265 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 266__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 267move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 268 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 269 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 270 271template <class _RAIter, 272 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 273__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 274move_backward(_RAIter __f, 275 _RAIter __l, 276 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 277 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); 278 279template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 280 class _OutputIterator> 281_OutputIterator 282move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 283 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 284 _OutputIterator __r); 285 286template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 287 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 288__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 289move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 290 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 291 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 292 293template <class _ValueType, class _DiffType> 294struct __deque_block_size { 295 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16; 296}; 297 298template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 299 class _DiffType, _DiffType _BS = 300#ifdef _LIBCPP_ABI_INCOMPLETE_TYPES_IN_DEQUE 301// Keep template parameter to avoid changing all template declarations thoughout 302// this file. 303 0 304#else 305 __deque_block_size<_ValueType, _DiffType>::value 306#endif 307 > 308class _LIBCPP_TEMPLATE_VIS __deque_iterator 309{ 310 typedef _MapPointer __map_iterator; 311public: 312 typedef _Pointer pointer; 313 typedef _DiffType difference_type; 314private: 315 __map_iterator __m_iter_; 316 pointer __ptr_; 317 318 static const difference_type __block_size; 319public: 320 typedef _ValueType value_type; 321 typedef random_access_iterator_tag iterator_category; 322 typedef _Reference reference; 323 324 _LIBCPP_INLINE_VISIBILITY __deque_iterator() _NOEXCEPT 325#if _LIBCPP_STD_VER > 11 326 : __m_iter_(nullptr), __ptr_(nullptr) 327#endif 328 {} 329 330 template <class _Pp, class _Rp, class _MP> 331 _LIBCPP_INLINE_VISIBILITY 332 __deque_iterator(const __deque_iterator<value_type, _Pp, _Rp, _MP, difference_type, _BS>& __it, 333 typename enable_if<is_convertible<_Pp, pointer>::value>::type* = 0) _NOEXCEPT 334 : __m_iter_(__it.__m_iter_), __ptr_(__it.__ptr_) {} 335 336 _LIBCPP_INLINE_VISIBILITY reference operator*() const {return *__ptr_;} 337 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return __ptr_;} 338 339 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator++() 340 { 341 if (++__ptr_ - *__m_iter_ == __block_size) 342 { 343 ++__m_iter_; 344 __ptr_ = *__m_iter_; 345 } 346 return *this; 347 } 348 349 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator++(int) 350 { 351 __deque_iterator __tmp = *this; 352 ++(*this); 353 return __tmp; 354 } 355 356 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator--() 357 { 358 if (__ptr_ == *__m_iter_) 359 { 360 --__m_iter_; 361 __ptr_ = *__m_iter_ + __block_size; 362 } 363 --__ptr_; 364 return *this; 365 } 366 367 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator--(int) 368 { 369 __deque_iterator __tmp = *this; 370 --(*this); 371 return __tmp; 372 } 373 374 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator+=(difference_type __n) 375 { 376 if (__n != 0) 377 { 378 __n += __ptr_ - *__m_iter_; 379 if (__n > 0) 380 { 381 __m_iter_ += __n / __block_size; 382 __ptr_ = *__m_iter_ + __n % __block_size; 383 } 384 else // (__n < 0) 385 { 386 difference_type __z = __block_size - 1 - __n; 387 __m_iter_ -= __z / __block_size; 388 __ptr_ = *__m_iter_ + (__block_size - 1 - __z % __block_size); 389 } 390 } 391 return *this; 392 } 393 394 _LIBCPP_INLINE_VISIBILITY __deque_iterator& operator-=(difference_type __n) 395 { 396 return *this += -__n; 397 } 398 399 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator+(difference_type __n) const 400 { 401 __deque_iterator __t(*this); 402 __t += __n; 403 return __t; 404 } 405 406 _LIBCPP_INLINE_VISIBILITY __deque_iterator operator-(difference_type __n) const 407 { 408 __deque_iterator __t(*this); 409 __t -= __n; 410 return __t; 411 } 412 413 _LIBCPP_INLINE_VISIBILITY 414 friend __deque_iterator operator+(difference_type __n, const __deque_iterator& __it) 415 {return __it + __n;} 416 417 _LIBCPP_INLINE_VISIBILITY 418 friend difference_type operator-(const __deque_iterator& __x, const __deque_iterator& __y) 419 { 420 if (__x != __y) 421 return (__x.__m_iter_ - __y.__m_iter_) * __block_size 422 + (__x.__ptr_ - *__x.__m_iter_) 423 - (__y.__ptr_ - *__y.__m_iter_); 424 return 0; 425 } 426 427 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const 428 {return *(*this + __n);} 429 430 _LIBCPP_INLINE_VISIBILITY friend 431 bool operator==(const __deque_iterator& __x, const __deque_iterator& __y) 432 {return __x.__ptr_ == __y.__ptr_;} 433 434 _LIBCPP_INLINE_VISIBILITY friend 435 bool operator!=(const __deque_iterator& __x, const __deque_iterator& __y) 436 {return !(__x == __y);} 437 438 _LIBCPP_INLINE_VISIBILITY friend 439 bool operator<(const __deque_iterator& __x, const __deque_iterator& __y) 440 {return __x.__m_iter_ < __y.__m_iter_ || 441 (__x.__m_iter_ == __y.__m_iter_ && __x.__ptr_ < __y.__ptr_);} 442 443 _LIBCPP_INLINE_VISIBILITY friend 444 bool operator>(const __deque_iterator& __x, const __deque_iterator& __y) 445 {return __y < __x;} 446 447 _LIBCPP_INLINE_VISIBILITY friend 448 bool operator<=(const __deque_iterator& __x, const __deque_iterator& __y) 449 {return !(__y < __x);} 450 451 _LIBCPP_INLINE_VISIBILITY friend 452 bool operator>=(const __deque_iterator& __x, const __deque_iterator& __y) 453 {return !(__x < __y);} 454 455private: 456 _LIBCPP_INLINE_VISIBILITY explicit __deque_iterator(__map_iterator __m, pointer __p) _NOEXCEPT 457 : __m_iter_(__m), __ptr_(__p) {} 458 459 template <class _Tp, class _Ap> friend class __deque_base; 460 template <class _Tp, class _Ap> friend class _LIBCPP_TEMPLATE_VIS deque; 461 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp> 462 friend class _LIBCPP_TEMPLATE_VIS __deque_iterator; 463 464 template <class _RAIter, 465 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 466 friend 467 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 468 copy(_RAIter __f, 469 _RAIter __l, 470 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 471 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*); 472 473 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 474 class _OutputIterator> 475 friend 476 _OutputIterator 477 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 478 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 479 _OutputIterator __r); 480 481 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 482 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 483 friend 484 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 485 copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 486 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 487 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 488 489 template <class _RAIter, 490 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 491 friend 492 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 493 copy_backward(_RAIter __f, 494 _RAIter __l, 495 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 496 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*); 497 498 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 499 class _OutputIterator> 500 friend 501 _OutputIterator 502 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 503 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 504 _OutputIterator __r); 505 506 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 507 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 508 friend 509 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 510 copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 511 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 512 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 513 514 template <class _RAIter, 515 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 516 friend 517 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 518 move(_RAIter __f, 519 _RAIter __l, 520 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 521 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*); 522 523 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 524 class _OutputIterator> 525 friend 526 _OutputIterator 527 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 528 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 529 _OutputIterator __r); 530 531 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 532 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 533 friend 534 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 535 move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 536 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 537 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 538 539 template <class _RAIter, 540 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 541 friend 542 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 543 move_backward(_RAIter __f, 544 _RAIter __l, 545 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 546 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*); 547 548 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 549 class _OutputIterator> 550 friend 551 _OutputIterator 552 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 553 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 554 _OutputIterator __r); 555 556 template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 557 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 558 friend 559 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 560 move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 561 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 562 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r); 563}; 564 565template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 566 class _DiffType, _DiffType _BlockSize> 567const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, 568 _DiffType, _BlockSize>::__block_size = 569 __deque_block_size<_ValueType, _DiffType>::value; 570 571// copy 572 573template <class _RAIter, 574 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 575__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 576copy(_RAIter __f, 577 _RAIter __l, 578 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 579 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) 580{ 581 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 582 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 583 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size; 584 while (__f != __l) 585 { 586 pointer __rb = __r.__ptr_; 587 pointer __re = *__r.__m_iter_ + __block_size; 588 difference_type __bs = __re - __rb; 589 difference_type __n = __l - __f; 590 _RAIter __m = __l; 591 if (__n > __bs) 592 { 593 __n = __bs; 594 __m = __f + __n; 595 } 596 _VSTD::copy(__f, __m, __rb); 597 __f = __m; 598 __r += __n; 599 } 600 return __r; 601} 602 603template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 604 class _OutputIterator> 605_OutputIterator 606copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 607 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 608 _OutputIterator __r) 609{ 610 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 611 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 612 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size; 613 difference_type __n = __l - __f; 614 while (__n > 0) 615 { 616 pointer __fb = __f.__ptr_; 617 pointer __fe = *__f.__m_iter_ + __block_size; 618 difference_type __bs = __fe - __fb; 619 if (__bs > __n) 620 { 621 __bs = __n; 622 __fe = __fb + __bs; 623 } 624 __r = _VSTD::copy(__fb, __fe, __r); 625 __n -= __bs; 626 __f += __bs; 627 } 628 return __r; 629} 630 631template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 632 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 633__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 634copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 635 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 636 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 637{ 638 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 639 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 640 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size; 641 difference_type __n = __l - __f; 642 while (__n > 0) 643 { 644 pointer __fb = __f.__ptr_; 645 pointer __fe = *__f.__m_iter_ + __block_size; 646 difference_type __bs = __fe - __fb; 647 if (__bs > __n) 648 { 649 __bs = __n; 650 __fe = __fb + __bs; 651 } 652 __r = _VSTD::copy(__fb, __fe, __r); 653 __n -= __bs; 654 __f += __bs; 655 } 656 return __r; 657} 658 659// copy_backward 660 661template <class _RAIter, 662 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 663__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 664copy_backward(_RAIter __f, 665 _RAIter __l, 666 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 667 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) 668{ 669 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 670 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 671 while (__f != __l) 672 { 673 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r); 674 pointer __rb = *__rp.__m_iter_; 675 pointer __re = __rp.__ptr_ + 1; 676 difference_type __bs = __re - __rb; 677 difference_type __n = __l - __f; 678 _RAIter __m = __f; 679 if (__n > __bs) 680 { 681 __n = __bs; 682 __m = __l - __n; 683 } 684 _VSTD::copy_backward(__m, __l, __re); 685 __l = __m; 686 __r -= __n; 687 } 688 return __r; 689} 690 691template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 692 class _OutputIterator> 693_OutputIterator 694copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 695 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 696 _OutputIterator __r) 697{ 698 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 699 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 700 difference_type __n = __l - __f; 701 while (__n > 0) 702 { 703 --__l; 704 pointer __lb = *__l.__m_iter_; 705 pointer __le = __l.__ptr_ + 1; 706 difference_type __bs = __le - __lb; 707 if (__bs > __n) 708 { 709 __bs = __n; 710 __lb = __le - __bs; 711 } 712 __r = _VSTD::copy_backward(__lb, __le, __r); 713 __n -= __bs; 714 __l -= __bs - 1; 715 } 716 return __r; 717} 718 719template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 720 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 721__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 722copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 723 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 724 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 725{ 726 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 727 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 728 difference_type __n = __l - __f; 729 while (__n > 0) 730 { 731 --__l; 732 pointer __lb = *__l.__m_iter_; 733 pointer __le = __l.__ptr_ + 1; 734 difference_type __bs = __le - __lb; 735 if (__bs > __n) 736 { 737 __bs = __n; 738 __lb = __le - __bs; 739 } 740 __r = _VSTD::copy_backward(__lb, __le, __r); 741 __n -= __bs; 742 __l -= __bs - 1; 743 } 744 return __r; 745} 746 747// move 748 749template <class _RAIter, 750 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 751__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 752move(_RAIter __f, 753 _RAIter __l, 754 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 755 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) 756{ 757 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 758 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 759 const difference_type __block_size = __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::__block_size; 760 while (__f != __l) 761 { 762 pointer __rb = __r.__ptr_; 763 pointer __re = *__r.__m_iter_ + __block_size; 764 difference_type __bs = __re - __rb; 765 difference_type __n = __l - __f; 766 _RAIter __m = __l; 767 if (__n > __bs) 768 { 769 __n = __bs; 770 __m = __f + __n; 771 } 772 _VSTD::move(__f, __m, __rb); 773 __f = __m; 774 __r += __n; 775 } 776 return __r; 777} 778 779template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 780 class _OutputIterator> 781_OutputIterator 782move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 783 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 784 _OutputIterator __r) 785{ 786 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 787 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 788 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size; 789 difference_type __n = __l - __f; 790 while (__n > 0) 791 { 792 pointer __fb = __f.__ptr_; 793 pointer __fe = *__f.__m_iter_ + __block_size; 794 difference_type __bs = __fe - __fb; 795 if (__bs > __n) 796 { 797 __bs = __n; 798 __fe = __fb + __bs; 799 } 800 __r = _VSTD::move(__fb, __fe, __r); 801 __n -= __bs; 802 __f += __bs; 803 } 804 return __r; 805} 806 807template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 808 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 809__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 810move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 811 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 812 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 813{ 814 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 815 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 816 const difference_type __block_size = __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::__block_size; 817 difference_type __n = __l - __f; 818 while (__n > 0) 819 { 820 pointer __fb = __f.__ptr_; 821 pointer __fe = *__f.__m_iter_ + __block_size; 822 difference_type __bs = __fe - __fb; 823 if (__bs > __n) 824 { 825 __bs = __n; 826 __fe = __fb + __bs; 827 } 828 __r = _VSTD::move(__fb, __fe, __r); 829 __n -= __bs; 830 __f += __bs; 831 } 832 return __r; 833} 834 835// move_backward 836 837template <class _RAIter, 838 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 839__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 840move_backward(_RAIter __f, 841 _RAIter __l, 842 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r, 843 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) 844{ 845 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::difference_type difference_type; 846 typedef typename __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2>::pointer pointer; 847 while (__f != __l) 848 { 849 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __rp = _VSTD::prev(__r); 850 pointer __rb = *__rp.__m_iter_; 851 pointer __re = __rp.__ptr_ + 1; 852 difference_type __bs = __re - __rb; 853 difference_type __n = __l - __f; 854 _RAIter __m = __f; 855 if (__n > __bs) 856 { 857 __n = __bs; 858 __m = __l - __n; 859 } 860 _VSTD::move_backward(__m, __l, __re); 861 __l = __m; 862 __r -= __n; 863 } 864 return __r; 865} 866 867template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 868 class _OutputIterator> 869_OutputIterator 870move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 871 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 872 _OutputIterator __r) 873{ 874 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 875 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 876 difference_type __n = __l - __f; 877 while (__n > 0) 878 { 879 --__l; 880 pointer __lb = *__l.__m_iter_; 881 pointer __le = __l.__ptr_ + 1; 882 difference_type __bs = __le - __lb; 883 if (__bs > __n) 884 { 885 __bs = __n; 886 __lb = __le - __bs; 887 } 888 __r = _VSTD::move_backward(__lb, __le, __r); 889 __n -= __bs; 890 __l -= __bs - 1; 891 } 892 return __r; 893} 894 895template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 896 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 897__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 898move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 899 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 900 __deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> __r) 901{ 902 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::difference_type difference_type; 903 typedef typename __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1>::pointer pointer; 904 difference_type __n = __l - __f; 905 while (__n > 0) 906 { 907 --__l; 908 pointer __lb = *__l.__m_iter_; 909 pointer __le = __l.__ptr_ + 1; 910 difference_type __bs = __le - __lb; 911 if (__bs > __n) 912 { 913 __bs = __n; 914 __lb = __le - __bs; 915 } 916 __r = _VSTD::move_backward(__lb, __le, __r); 917 __n -= __bs; 918 __l -= __bs - 1; 919 } 920 return __r; 921} 922 923template <class _Tp, class _Allocator> 924class __deque_base 925{ 926 __deque_base(const __deque_base& __c); 927 __deque_base& operator=(const __deque_base& __c); 928public: 929 typedef _Allocator allocator_type; 930 typedef allocator_traits<allocator_type> __alloc_traits; 931 typedef typename __alloc_traits::size_type size_type; 932 933 typedef _Tp value_type; 934 typedef value_type& reference; 935 typedef const value_type& const_reference; 936 typedef typename __alloc_traits::difference_type difference_type; 937 typedef typename __alloc_traits::pointer pointer; 938 typedef typename __alloc_traits::const_pointer const_pointer; 939 940 static const difference_type __block_size; 941 942 typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator; 943 typedef allocator_traits<__pointer_allocator> __map_traits; 944 typedef typename __map_traits::pointer __map_pointer; 945 typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator; 946 typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer; 947 typedef __split_buffer<pointer, __pointer_allocator> __map; 948 949 typedef __deque_iterator<value_type, pointer, reference, __map_pointer, 950 difference_type> iterator; 951 typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, 952 difference_type> const_iterator; 953 954 struct __deque_block_range { 955 explicit __deque_block_range(pointer __b, pointer __e) _NOEXCEPT : __begin_(__b), __end_(__e) {} 956 const pointer __begin_; 957 const pointer __end_; 958 }; 959 960 struct __deque_range { 961 iterator __pos_; 962 const iterator __end_; 963 964 __deque_range(iterator __pos, iterator __e) _NOEXCEPT 965 : __pos_(__pos), __end_(__e) {} 966 967 explicit operator bool() const _NOEXCEPT { 968 return __pos_ != __end_; 969 } 970 971 __deque_range begin() const { 972 return *this; 973 } 974 975 __deque_range end() const { 976 return __deque_range(__end_, __end_); 977 } 978 __deque_block_range operator*() const _NOEXCEPT { 979 if (__pos_.__m_iter_ == __end_.__m_iter_) { 980 return __deque_block_range(__pos_.__ptr_, __end_.__ptr_); 981 } 982 return __deque_block_range(__pos_.__ptr_, *__pos_.__m_iter_ + __block_size); 983 } 984 985 __deque_range& operator++() _NOEXCEPT { 986 if (__pos_.__m_iter_ == __end_.__m_iter_) { 987 __pos_ = __end_; 988 } else { 989 ++__pos_.__m_iter_; 990 __pos_.__ptr_ = *__pos_.__m_iter_; 991 } 992 return *this; 993 } 994 995 996 friend bool operator==(__deque_range const& __lhs, __deque_range const& __rhs) { 997 return __lhs.__pos_ == __rhs.__pos_; 998 } 999 friend bool operator!=(__deque_range const& __lhs, __deque_range const& __rhs) { 1000 return !(__lhs == __rhs); 1001 } 1002 }; 1003 1004 1005 1006 struct _ConstructTransaction { 1007 _ConstructTransaction(__deque_base* __db, __deque_block_range& __r) 1008 : __pos_(__r.__begin_), __end_(__r.__end_), __begin_(__r.__begin_), __base_(__db) {} 1009 1010 1011 ~_ConstructTransaction() { 1012 __base_->size() += (__pos_ - __begin_); 1013 } 1014 1015 pointer __pos_; 1016 const pointer __end_; 1017 private: 1018 const pointer __begin_; 1019 __deque_base * const __base_; 1020 }; 1021 1022protected: 1023 __map __map_; 1024 size_type __start_; 1025 __compressed_pair<size_type, allocator_type> __size_; 1026 1027 iterator begin() _NOEXCEPT; 1028 const_iterator begin() const _NOEXCEPT; 1029 iterator end() _NOEXCEPT; 1030 const_iterator end() const _NOEXCEPT; 1031 1032 _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();} 1033 _LIBCPP_INLINE_VISIBILITY 1034 const size_type& size() const _NOEXCEPT {return __size_.first();} 1035 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();} 1036 _LIBCPP_INLINE_VISIBILITY 1037 const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();} 1038 1039 _LIBCPP_INLINE_VISIBILITY 1040 __deque_base() 1041 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 1042 _LIBCPP_INLINE_VISIBILITY 1043 explicit __deque_base(const allocator_type& __a); 1044public: 1045 ~__deque_base(); 1046 1047#ifndef _LIBCPP_CXX03_LANG 1048 __deque_base(__deque_base&& __c) 1049 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 1050 __deque_base(__deque_base&& __c, const allocator_type& __a); 1051#endif // _LIBCPP_CXX03_LANG 1052 1053 void swap(__deque_base& __c) 1054#if _LIBCPP_STD_VER >= 14 1055 _NOEXCEPT; 1056#else 1057 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1058 __is_nothrow_swappable<allocator_type>::value); 1059#endif 1060protected: 1061 void clear() _NOEXCEPT; 1062 1063 bool __invariants() const; 1064 1065 _LIBCPP_INLINE_VISIBILITY 1066 void __move_assign(__deque_base& __c) 1067 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1068 is_nothrow_move_assignable<allocator_type>::value) 1069 { 1070 __map_ = _VSTD::move(__c.__map_); 1071 __start_ = __c.__start_; 1072 size() = __c.size(); 1073 __move_assign_alloc(__c); 1074 __c.__start_ = __c.size() = 0; 1075 } 1076 1077 _LIBCPP_INLINE_VISIBILITY 1078 void __move_assign_alloc(__deque_base& __c) 1079 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value || 1080 is_nothrow_move_assignable<allocator_type>::value) 1081 {__move_assign_alloc(__c, integral_constant<bool, 1082 __alloc_traits::propagate_on_container_move_assignment::value>());} 1083 1084private: 1085 _LIBCPP_INLINE_VISIBILITY 1086 void __move_assign_alloc(__deque_base& __c, true_type) 1087 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1088 { 1089 __alloc() = _VSTD::move(__c.__alloc()); 1090 } 1091 1092 _LIBCPP_INLINE_VISIBILITY 1093 void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT 1094 {} 1095}; 1096 1097template <class _Tp, class _Allocator> 1098const typename __deque_base<_Tp, _Allocator>::difference_type 1099 __deque_base<_Tp, _Allocator>::__block_size = 1100 __deque_block_size<value_type, difference_type>::value; 1101 1102template <class _Tp, class _Allocator> 1103bool 1104__deque_base<_Tp, _Allocator>::__invariants() const 1105{ 1106 if (!__map_.__invariants()) 1107 return false; 1108 if (__map_.size() >= size_type(-1) / __block_size) 1109 return false; 1110 for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end(); 1111 __i != __e; ++__i) 1112 if (*__i == nullptr) 1113 return false; 1114 if (__map_.size() != 0) 1115 { 1116 if (size() >= __map_.size() * __block_size) 1117 return false; 1118 if (__start_ >= __map_.size() * __block_size - size()) 1119 return false; 1120 } 1121 else 1122 { 1123 if (size() != 0) 1124 return false; 1125 if (__start_ != 0) 1126 return false; 1127 } 1128 return true; 1129} 1130 1131template <class _Tp, class _Allocator> 1132typename __deque_base<_Tp, _Allocator>::iterator 1133__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT 1134{ 1135 __map_pointer __mp = __map_.begin() + __start_ / __block_size; 1136 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); 1137} 1138 1139template <class _Tp, class _Allocator> 1140typename __deque_base<_Tp, _Allocator>::const_iterator 1141__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT 1142{ 1143 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size); 1144 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); 1145} 1146 1147template <class _Tp, class _Allocator> 1148typename __deque_base<_Tp, _Allocator>::iterator 1149__deque_base<_Tp, _Allocator>::end() _NOEXCEPT 1150{ 1151 size_type __p = size() + __start_; 1152 __map_pointer __mp = __map_.begin() + __p / __block_size; 1153 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); 1154} 1155 1156template <class _Tp, class _Allocator> 1157typename __deque_base<_Tp, _Allocator>::const_iterator 1158__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT 1159{ 1160 size_type __p = size() + __start_; 1161 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size); 1162 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); 1163} 1164 1165template <class _Tp, class _Allocator> 1166inline 1167__deque_base<_Tp, _Allocator>::__deque_base() 1168 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1169 : __start_(0), __size_(0, __default_init_tag()) {} 1170 1171template <class _Tp, class _Allocator> 1172inline 1173__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a) 1174 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {} 1175 1176template <class _Tp, class _Allocator> 1177__deque_base<_Tp, _Allocator>::~__deque_base() 1178{ 1179 clear(); 1180 typename __map::iterator __i = __map_.begin(); 1181 typename __map::iterator __e = __map_.end(); 1182 for (; __i != __e; ++__i) 1183 __alloc_traits::deallocate(__alloc(), *__i, __block_size); 1184} 1185 1186#ifndef _LIBCPP_CXX03_LANG 1187 1188template <class _Tp, class _Allocator> 1189__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c) 1190 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1191 : __map_(_VSTD::move(__c.__map_)), 1192 __start_(_VSTD::move(__c.__start_)), 1193 __size_(_VSTD::move(__c.__size_)) 1194{ 1195 __c.__start_ = 0; 1196 __c.size() = 0; 1197} 1198 1199template <class _Tp, class _Allocator> 1200__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a) 1201 : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)), 1202 __start_(_VSTD::move(__c.__start_)), 1203 __size_(_VSTD::move(__c.size()), __a) 1204{ 1205 if (__a == __c.__alloc()) 1206 { 1207 __c.__start_ = 0; 1208 __c.size() = 0; 1209 } 1210 else 1211 { 1212 __map_.clear(); 1213 __start_ = 0; 1214 size() = 0; 1215 } 1216} 1217 1218#endif // _LIBCPP_CXX03_LANG 1219 1220template <class _Tp, class _Allocator> 1221void 1222__deque_base<_Tp, _Allocator>::swap(__deque_base& __c) 1223#if _LIBCPP_STD_VER >= 14 1224 _NOEXCEPT 1225#else 1226 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1227 __is_nothrow_swappable<allocator_type>::value) 1228#endif 1229{ 1230 __map_.swap(__c.__map_); 1231 _VSTD::swap(__start_, __c.__start_); 1232 _VSTD::swap(size(), __c.size()); 1233 _VSTD::__swap_allocator(__alloc(), __c.__alloc()); 1234} 1235 1236template <class _Tp, class _Allocator> 1237void 1238__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT 1239{ 1240 allocator_type& __a = __alloc(); 1241 for (iterator __i = begin(), __e = end(); __i != __e; ++__i) 1242 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 1243 size() = 0; 1244 while (__map_.size() > 2) 1245 { 1246 __alloc_traits::deallocate(__a, __map_.front(), __block_size); 1247 __map_.pop_front(); 1248 } 1249 switch (__map_.size()) 1250 { 1251 case 1: 1252 __start_ = __block_size / 2; 1253 break; 1254 case 2: 1255 __start_ = __block_size; 1256 break; 1257 } 1258} 1259 1260template <class _Tp, class _Allocator /*= allocator<_Tp>*/> 1261class _LIBCPP_TEMPLATE_VIS deque 1262 : private __deque_base<_Tp, _Allocator> 1263{ 1264public: 1265 // types: 1266 1267 typedef _Tp value_type; 1268 typedef _Allocator allocator_type; 1269 1270 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1271 "Allocator::value_type must be same type as value_type"); 1272 1273 typedef __deque_base<value_type, allocator_type> __base; 1274 1275 typedef typename __base::__alloc_traits __alloc_traits; 1276 typedef typename __base::reference reference; 1277 typedef typename __base::const_reference const_reference; 1278 typedef typename __base::iterator iterator; 1279 typedef typename __base::const_iterator const_iterator; 1280 typedef typename __base::size_type size_type; 1281 typedef typename __base::difference_type difference_type; 1282 1283 typedef typename __base::pointer pointer; 1284 typedef typename __base::const_pointer const_pointer; 1285 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1286 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1287 1288 using typename __base::__deque_range; 1289 using typename __base::__deque_block_range; 1290 using typename __base::_ConstructTransaction; 1291 1292 // construct/copy/destroy: 1293 _LIBCPP_INLINE_VISIBILITY 1294 deque() 1295 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1296 {} 1297 _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {} 1298 explicit deque(size_type __n); 1299#if _LIBCPP_STD_VER > 11 1300 explicit deque(size_type __n, const _Allocator& __a); 1301#endif 1302 deque(size_type __n, const value_type& __v); 1303 1304 template <class = __enable_if_t<__is_allocator<_Allocator>::value> > 1305 deque(size_type __n, const value_type& __v, const allocator_type& __a) : __base(__a) 1306 { 1307 if (__n > 0) 1308 __append(__n, __v); 1309 } 1310 1311 template <class _InputIter> 1312 deque(_InputIter __f, _InputIter __l, 1313 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0); 1314 template <class _InputIter> 1315 deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1316 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type* = 0); 1317 deque(const deque& __c); 1318 deque(const deque& __c, const __type_identity_t<allocator_type>& __a); 1319 1320 deque& operator=(const deque& __c); 1321 1322#ifndef _LIBCPP_CXX03_LANG 1323 deque(initializer_list<value_type> __il); 1324 deque(initializer_list<value_type> __il, const allocator_type& __a); 1325 1326 _LIBCPP_INLINE_VISIBILITY 1327 deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;} 1328 1329 _LIBCPP_INLINE_VISIBILITY 1330 deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value); 1331 _LIBCPP_INLINE_VISIBILITY 1332 deque(deque&& __c, const __type_identity_t<allocator_type>& __a); 1333 _LIBCPP_INLINE_VISIBILITY 1334 deque& operator=(deque&& __c) 1335 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1336 is_nothrow_move_assignable<allocator_type>::value); 1337 1338 _LIBCPP_INLINE_VISIBILITY 1339 void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());} 1340#endif // _LIBCPP_CXX03_LANG 1341 1342 template <class _InputIter> 1343 void assign(_InputIter __f, _InputIter __l, 1344 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value && 1345 !__is_cpp17_random_access_iterator<_InputIter>::value>::type* = 0); 1346 template <class _RAIter> 1347 void assign(_RAIter __f, _RAIter __l, 1348 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type* = 0); 1349 void assign(size_type __n, const value_type& __v); 1350 1351 _LIBCPP_INLINE_VISIBILITY 1352 allocator_type get_allocator() const _NOEXCEPT; 1353 1354 // iterators: 1355 1356 _LIBCPP_INLINE_VISIBILITY 1357 iterator begin() _NOEXCEPT {return __base::begin();} 1358 _LIBCPP_INLINE_VISIBILITY 1359 const_iterator begin() const _NOEXCEPT {return __base::begin();} 1360 _LIBCPP_INLINE_VISIBILITY 1361 iterator end() _NOEXCEPT {return __base::end();} 1362 _LIBCPP_INLINE_VISIBILITY 1363 const_iterator end() const _NOEXCEPT {return __base::end();} 1364 1365 _LIBCPP_INLINE_VISIBILITY 1366 reverse_iterator rbegin() _NOEXCEPT 1367 {return reverse_iterator(__base::end());} 1368 _LIBCPP_INLINE_VISIBILITY 1369 const_reverse_iterator rbegin() const _NOEXCEPT 1370 {return const_reverse_iterator(__base::end());} 1371 _LIBCPP_INLINE_VISIBILITY 1372 reverse_iterator rend() _NOEXCEPT 1373 {return reverse_iterator(__base::begin());} 1374 _LIBCPP_INLINE_VISIBILITY 1375 const_reverse_iterator rend() const _NOEXCEPT 1376 {return const_reverse_iterator(__base::begin());} 1377 1378 _LIBCPP_INLINE_VISIBILITY 1379 const_iterator cbegin() const _NOEXCEPT 1380 {return __base::begin();} 1381 _LIBCPP_INLINE_VISIBILITY 1382 const_iterator cend() const _NOEXCEPT 1383 {return __base::end();} 1384 _LIBCPP_INLINE_VISIBILITY 1385 const_reverse_iterator crbegin() const _NOEXCEPT 1386 {return const_reverse_iterator(__base::end());} 1387 _LIBCPP_INLINE_VISIBILITY 1388 const_reverse_iterator crend() const _NOEXCEPT 1389 {return const_reverse_iterator(__base::begin());} 1390 1391 // capacity: 1392 _LIBCPP_INLINE_VISIBILITY 1393 size_type size() const _NOEXCEPT {return __base::size();} 1394 _LIBCPP_INLINE_VISIBILITY 1395 size_type max_size() const _NOEXCEPT 1396 {return _VSTD::min<size_type>( 1397 __alloc_traits::max_size(__base::__alloc()), 1398 numeric_limits<difference_type>::max());} 1399 void resize(size_type __n); 1400 void resize(size_type __n, const value_type& __v); 1401 void shrink_to_fit() _NOEXCEPT; 1402 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY 1403 bool empty() const _NOEXCEPT {return __base::size() == 0;} 1404 1405 // element access: 1406 _LIBCPP_INLINE_VISIBILITY 1407 reference operator[](size_type __i) _NOEXCEPT; 1408 _LIBCPP_INLINE_VISIBILITY 1409 const_reference operator[](size_type __i) const _NOEXCEPT; 1410 _LIBCPP_INLINE_VISIBILITY 1411 reference at(size_type __i); 1412 _LIBCPP_INLINE_VISIBILITY 1413 const_reference at(size_type __i) const; 1414 _LIBCPP_INLINE_VISIBILITY 1415 reference front() _NOEXCEPT; 1416 _LIBCPP_INLINE_VISIBILITY 1417 const_reference front() const _NOEXCEPT; 1418 _LIBCPP_INLINE_VISIBILITY 1419 reference back() _NOEXCEPT; 1420 _LIBCPP_INLINE_VISIBILITY 1421 const_reference back() const _NOEXCEPT; 1422 1423 // 23.2.2.3 modifiers: 1424 void push_front(const value_type& __v); 1425 void push_back(const value_type& __v); 1426#ifndef _LIBCPP_CXX03_LANG 1427#if _LIBCPP_STD_VER > 14 1428 template <class... _Args> reference emplace_front(_Args&&... __args); 1429 template <class... _Args> reference emplace_back (_Args&&... __args); 1430#else 1431 template <class... _Args> void emplace_front(_Args&&... __args); 1432 template <class... _Args> void emplace_back (_Args&&... __args); 1433#endif 1434 template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args); 1435 1436 void push_front(value_type&& __v); 1437 void push_back(value_type&& __v); 1438 iterator insert(const_iterator __p, value_type&& __v); 1439 1440 _LIBCPP_INLINE_VISIBILITY 1441 iterator insert(const_iterator __p, initializer_list<value_type> __il) 1442 {return insert(__p, __il.begin(), __il.end());} 1443#endif // _LIBCPP_CXX03_LANG 1444 iterator insert(const_iterator __p, const value_type& __v); 1445 iterator insert(const_iterator __p, size_type __n, const value_type& __v); 1446 template <class _InputIter> 1447 iterator insert(const_iterator __p, _InputIter __f, _InputIter __l, 1448 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value 1449 &&!__is_cpp17_forward_iterator<_InputIter>::value>::type* = 0); 1450 template <class _ForwardIterator> 1451 iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 1452 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value 1453 &&!__is_cpp17_bidirectional_iterator<_ForwardIterator>::value>::type* = 0); 1454 template <class _BiIter> 1455 iterator insert(const_iterator __p, _BiIter __f, _BiIter __l, 1456 typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type* = 0); 1457 1458 void pop_front(); 1459 void pop_back(); 1460 iterator erase(const_iterator __p); 1461 iterator erase(const_iterator __f, const_iterator __l); 1462 1463 _LIBCPP_INLINE_VISIBILITY 1464 void swap(deque& __c) 1465#if _LIBCPP_STD_VER >= 14 1466 _NOEXCEPT; 1467#else 1468 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1469 __is_nothrow_swappable<allocator_type>::value); 1470#endif 1471 _LIBCPP_INLINE_VISIBILITY 1472 void clear() _NOEXCEPT; 1473 1474 _LIBCPP_INLINE_VISIBILITY 1475 bool __invariants() const {return __base::__invariants();} 1476 1477 typedef typename __base::__map_const_pointer __map_const_pointer; 1478 1479 _LIBCPP_INLINE_VISIBILITY 1480 static size_type __recommend_blocks(size_type __n) 1481 { 1482 return __n / __base::__block_size + (__n % __base::__block_size != 0); 1483 } 1484 _LIBCPP_INLINE_VISIBILITY 1485 size_type __capacity() const 1486 { 1487 return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1; 1488 } 1489 _LIBCPP_INLINE_VISIBILITY 1490 size_type __block_count() const 1491 { 1492 return __base::__map_.size(); 1493 } 1494 1495 _LIBCPP_INLINE_VISIBILITY 1496 size_type __front_spare() const 1497 { 1498 return __base::__start_; 1499 } 1500 _LIBCPP_INLINE_VISIBILITY 1501 size_type __front_spare_blocks() const { 1502 return __front_spare() / __base::__block_size; 1503 } 1504 _LIBCPP_INLINE_VISIBILITY 1505 size_type __back_spare() const 1506 { 1507 return __capacity() - (__base::__start_ + __base::size()); 1508 } 1509 _LIBCPP_INLINE_VISIBILITY 1510 size_type __back_spare_blocks() const { 1511 return __back_spare() / __base::__block_size; 1512 } 1513 1514 private: 1515 _LIBCPP_INLINE_VISIBILITY 1516 bool __maybe_remove_front_spare(bool __keep_one = true) { 1517 if (__front_spare_blocks() >= 2 || (!__keep_one && __front_spare_blocks())) { 1518 __alloc_traits::deallocate(__base::__alloc(), __base::__map_.front(), 1519 __base::__block_size); 1520 __base::__map_.pop_front(); 1521 __base::__start_ -= __base::__block_size; 1522 return true; 1523 } 1524 return false; 1525 } 1526 1527 _LIBCPP_INLINE_VISIBILITY 1528 bool __maybe_remove_back_spare(bool __keep_one = true) { 1529 if (__back_spare_blocks() >= 2 || (!__keep_one && __back_spare_blocks())) { 1530 __alloc_traits::deallocate(__base::__alloc(), __base::__map_.back(), 1531 __base::__block_size); 1532 __base::__map_.pop_back(); 1533 return true; 1534 } 1535 return false; 1536 } 1537 1538 template <class _InpIter> 1539 void __append(_InpIter __f, _InpIter __l, 1540 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value && 1541 !__is_cpp17_forward_iterator<_InpIter>::value>::type* = 0); 1542 template <class _ForIter> 1543 void __append(_ForIter __f, _ForIter __l, 1544 typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type* = 0); 1545 void __append(size_type __n); 1546 void __append(size_type __n, const value_type& __v); 1547 void __erase_to_end(const_iterator __f); 1548 void __add_front_capacity(); 1549 void __add_front_capacity(size_type __n); 1550 void __add_back_capacity(); 1551 void __add_back_capacity(size_type __n); 1552 iterator __move_and_check(iterator __f, iterator __l, iterator __r, 1553 const_pointer& __vt); 1554 iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r, 1555 const_pointer& __vt); 1556 void __move_construct_and_check(iterator __f, iterator __l, 1557 iterator __r, const_pointer& __vt); 1558 void __move_construct_backward_and_check(iterator __f, iterator __l, 1559 iterator __r, const_pointer& __vt); 1560 1561 _LIBCPP_INLINE_VISIBILITY 1562 void __copy_assign_alloc(const deque& __c) 1563 {__copy_assign_alloc(__c, integral_constant<bool, 1564 __alloc_traits::propagate_on_container_copy_assignment::value>());} 1565 1566 _LIBCPP_INLINE_VISIBILITY 1567 void __copy_assign_alloc(const deque& __c, true_type) 1568 { 1569 if (__base::__alloc() != __c.__alloc()) 1570 { 1571 clear(); 1572 shrink_to_fit(); 1573 } 1574 __base::__alloc() = __c.__alloc(); 1575 __base::__map_.__alloc() = __c.__map_.__alloc(); 1576 } 1577 1578 _LIBCPP_INLINE_VISIBILITY 1579 void __copy_assign_alloc(const deque&, false_type) 1580 {} 1581 1582 void __move_assign(deque& __c, true_type) 1583 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 1584 void __move_assign(deque& __c, false_type); 1585}; 1586 1587#if _LIBCPP_STD_VER >= 17 1588template<class _InputIterator, 1589 class _Alloc = allocator<__iter_value_type<_InputIterator>>, 1590 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1591 class = enable_if_t<__is_allocator<_Alloc>::value> 1592 > 1593deque(_InputIterator, _InputIterator) 1594 -> deque<__iter_value_type<_InputIterator>, _Alloc>; 1595 1596template<class _InputIterator, 1597 class _Alloc, 1598 class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>, 1599 class = enable_if_t<__is_allocator<_Alloc>::value> 1600 > 1601deque(_InputIterator, _InputIterator, _Alloc) 1602 -> deque<__iter_value_type<_InputIterator>, _Alloc>; 1603#endif 1604 1605template <class _Tp, class _Allocator> 1606deque<_Tp, _Allocator>::deque(size_type __n) 1607{ 1608 if (__n > 0) 1609 __append(__n); 1610} 1611 1612#if _LIBCPP_STD_VER > 11 1613template <class _Tp, class _Allocator> 1614deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a) 1615 : __base(__a) 1616{ 1617 if (__n > 0) 1618 __append(__n); 1619} 1620#endif 1621 1622template <class _Tp, class _Allocator> 1623deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v) 1624{ 1625 if (__n > 0) 1626 __append(__n, __v); 1627} 1628 1629template <class _Tp, class _Allocator> 1630template <class _InputIter> 1631deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, 1632 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*) 1633{ 1634 __append(__f, __l); 1635} 1636 1637template <class _Tp, class _Allocator> 1638template <class _InputIter> 1639deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1640 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value>::type*) 1641 : __base(__a) 1642{ 1643 __append(__f, __l); 1644} 1645 1646template <class _Tp, class _Allocator> 1647deque<_Tp, _Allocator>::deque(const deque& __c) 1648 : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc())) 1649{ 1650 __append(__c.begin(), __c.end()); 1651} 1652 1653template <class _Tp, class _Allocator> 1654deque<_Tp, _Allocator>::deque(const deque& __c, const __type_identity_t<allocator_type>& __a) 1655 : __base(__a) 1656{ 1657 __append(__c.begin(), __c.end()); 1658} 1659 1660template <class _Tp, class _Allocator> 1661deque<_Tp, _Allocator>& 1662deque<_Tp, _Allocator>::operator=(const deque& __c) 1663{ 1664 if (this != _VSTD::addressof(__c)) 1665 { 1666 __copy_assign_alloc(__c); 1667 assign(__c.begin(), __c.end()); 1668 } 1669 return *this; 1670} 1671 1672#ifndef _LIBCPP_CXX03_LANG 1673 1674template <class _Tp, class _Allocator> 1675deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il) 1676{ 1677 __append(__il.begin(), __il.end()); 1678} 1679 1680template <class _Tp, class _Allocator> 1681deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a) 1682 : __base(__a) 1683{ 1684 __append(__il.begin(), __il.end()); 1685} 1686 1687template <class _Tp, class _Allocator> 1688inline 1689deque<_Tp, _Allocator>::deque(deque&& __c) 1690 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1691 : __base(_VSTD::move(__c)) 1692{ 1693} 1694 1695template <class _Tp, class _Allocator> 1696inline 1697deque<_Tp, _Allocator>::deque(deque&& __c, const __type_identity_t<allocator_type>& __a) 1698 : __base(_VSTD::move(__c), __a) 1699{ 1700 if (__a != __c.__alloc()) 1701 { 1702 typedef move_iterator<iterator> _Ip; 1703 assign(_Ip(__c.begin()), _Ip(__c.end())); 1704 } 1705} 1706 1707template <class _Tp, class _Allocator> 1708inline 1709deque<_Tp, _Allocator>& 1710deque<_Tp, _Allocator>::operator=(deque&& __c) 1711 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1712 is_nothrow_move_assignable<allocator_type>::value) 1713{ 1714 __move_assign(__c, integral_constant<bool, 1715 __alloc_traits::propagate_on_container_move_assignment::value>()); 1716 return *this; 1717} 1718 1719template <class _Tp, class _Allocator> 1720void 1721deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type) 1722{ 1723 if (__base::__alloc() != __c.__alloc()) 1724 { 1725 typedef move_iterator<iterator> _Ip; 1726 assign(_Ip(__c.begin()), _Ip(__c.end())); 1727 } 1728 else 1729 __move_assign(__c, true_type()); 1730} 1731 1732template <class _Tp, class _Allocator> 1733void 1734deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type) 1735 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1736{ 1737 clear(); 1738 shrink_to_fit(); 1739 __base::__move_assign(__c); 1740} 1741 1742#endif // _LIBCPP_CXX03_LANG 1743 1744template <class _Tp, class _Allocator> 1745template <class _InputIter> 1746void 1747deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l, 1748 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value && 1749 !__is_cpp17_random_access_iterator<_InputIter>::value>::type*) 1750{ 1751 iterator __i = __base::begin(); 1752 iterator __e = __base::end(); 1753 for (; __f != __l && __i != __e; ++__f, (void) ++__i) 1754 *__i = *__f; 1755 if (__f != __l) 1756 __append(__f, __l); 1757 else 1758 __erase_to_end(__i); 1759} 1760 1761template <class _Tp, class _Allocator> 1762template <class _RAIter> 1763void 1764deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l, 1765 typename enable_if<__is_cpp17_random_access_iterator<_RAIter>::value>::type*) 1766{ 1767 if (static_cast<size_type>(__l - __f) > __base::size()) 1768 { 1769 _RAIter __m = __f + __base::size(); 1770 _VSTD::copy(__f, __m, __base::begin()); 1771 __append(__m, __l); 1772 } 1773 else 1774 __erase_to_end(_VSTD::copy(__f, __l, __base::begin())); 1775} 1776 1777template <class _Tp, class _Allocator> 1778void 1779deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v) 1780{ 1781 if (__n > __base::size()) 1782 { 1783 _VSTD::fill_n(__base::begin(), __base::size(), __v); 1784 __n -= __base::size(); 1785 __append(__n, __v); 1786 } 1787 else 1788 __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v)); 1789} 1790 1791template <class _Tp, class _Allocator> 1792inline 1793_Allocator 1794deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT 1795{ 1796 return __base::__alloc(); 1797} 1798 1799template <class _Tp, class _Allocator> 1800void 1801deque<_Tp, _Allocator>::resize(size_type __n) 1802{ 1803 if (__n > __base::size()) 1804 __append(__n - __base::size()); 1805 else if (__n < __base::size()) 1806 __erase_to_end(__base::begin() + __n); 1807} 1808 1809template <class _Tp, class _Allocator> 1810void 1811deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v) 1812{ 1813 if (__n > __base::size()) 1814 __append(__n - __base::size(), __v); 1815 else if (__n < __base::size()) 1816 __erase_to_end(__base::begin() + __n); 1817} 1818 1819template <class _Tp, class _Allocator> 1820void 1821deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1822{ 1823 allocator_type& __a = __base::__alloc(); 1824 if (empty()) 1825 { 1826 while (__base::__map_.size() > 0) 1827 { 1828 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 1829 __base::__map_.pop_back(); 1830 } 1831 __base::__start_ = 0; 1832 } 1833 else 1834 { 1835 __maybe_remove_front_spare(/*__keep_one=*/false); 1836 __maybe_remove_back_spare(/*__keep_one=*/false); 1837 } 1838 __base::__map_.shrink_to_fit(); 1839} 1840 1841template <class _Tp, class _Allocator> 1842inline 1843typename deque<_Tp, _Allocator>::reference 1844deque<_Tp, _Allocator>::operator[](size_type __i) _NOEXCEPT 1845{ 1846 size_type __p = __base::__start_ + __i; 1847 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1848} 1849 1850template <class _Tp, class _Allocator> 1851inline 1852typename deque<_Tp, _Allocator>::const_reference 1853deque<_Tp, _Allocator>::operator[](size_type __i) const _NOEXCEPT 1854{ 1855 size_type __p = __base::__start_ + __i; 1856 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1857} 1858 1859template <class _Tp, class _Allocator> 1860inline 1861typename deque<_Tp, _Allocator>::reference 1862deque<_Tp, _Allocator>::at(size_type __i) 1863{ 1864 if (__i >= __base::size()) 1865 _VSTD::__throw_out_of_range("deque"); 1866 size_type __p = __base::__start_ + __i; 1867 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1868} 1869 1870template <class _Tp, class _Allocator> 1871inline 1872typename deque<_Tp, _Allocator>::const_reference 1873deque<_Tp, _Allocator>::at(size_type __i) const 1874{ 1875 if (__i >= __base::size()) 1876 _VSTD::__throw_out_of_range("deque"); 1877 size_type __p = __base::__start_ + __i; 1878 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1879} 1880 1881template <class _Tp, class _Allocator> 1882inline 1883typename deque<_Tp, _Allocator>::reference 1884deque<_Tp, _Allocator>::front() _NOEXCEPT 1885{ 1886 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1887 + __base::__start_ % __base::__block_size); 1888} 1889 1890template <class _Tp, class _Allocator> 1891inline 1892typename deque<_Tp, _Allocator>::const_reference 1893deque<_Tp, _Allocator>::front() const _NOEXCEPT 1894{ 1895 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1896 + __base::__start_ % __base::__block_size); 1897} 1898 1899template <class _Tp, class _Allocator> 1900inline 1901typename deque<_Tp, _Allocator>::reference 1902deque<_Tp, _Allocator>::back() _NOEXCEPT 1903{ 1904 size_type __p = __base::size() + __base::__start_ - 1; 1905 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1906} 1907 1908template <class _Tp, class _Allocator> 1909inline 1910typename deque<_Tp, _Allocator>::const_reference 1911deque<_Tp, _Allocator>::back() const _NOEXCEPT 1912{ 1913 size_type __p = __base::size() + __base::__start_ - 1; 1914 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1915} 1916 1917template <class _Tp, class _Allocator> 1918void 1919deque<_Tp, _Allocator>::push_back(const value_type& __v) 1920{ 1921 allocator_type& __a = __base::__alloc(); 1922 if (__back_spare() == 0) 1923 __add_back_capacity(); 1924 // __back_spare() >= 1 1925 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 1926 ++__base::size(); 1927} 1928 1929template <class _Tp, class _Allocator> 1930void 1931deque<_Tp, _Allocator>::push_front(const value_type& __v) 1932{ 1933 allocator_type& __a = __base::__alloc(); 1934 if (__front_spare() == 0) 1935 __add_front_capacity(); 1936 // __front_spare() >= 1 1937 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 1938 --__base::__start_; 1939 ++__base::size(); 1940} 1941 1942#ifndef _LIBCPP_CXX03_LANG 1943template <class _Tp, class _Allocator> 1944void 1945deque<_Tp, _Allocator>::push_back(value_type&& __v) 1946{ 1947 allocator_type& __a = __base::__alloc(); 1948 if (__back_spare() == 0) 1949 __add_back_capacity(); 1950 // __back_spare() >= 1 1951 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 1952 ++__base::size(); 1953} 1954 1955template <class _Tp, class _Allocator> 1956template <class... _Args> 1957#if _LIBCPP_STD_VER > 14 1958typename deque<_Tp, _Allocator>::reference 1959#else 1960void 1961#endif 1962deque<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1963{ 1964 allocator_type& __a = __base::__alloc(); 1965 if (__back_spare() == 0) 1966 __add_back_capacity(); 1967 // __back_spare() >= 1 1968 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), 1969 _VSTD::forward<_Args>(__args)...); 1970 ++__base::size(); 1971#if _LIBCPP_STD_VER > 14 1972 return *--__base::end(); 1973#endif 1974} 1975 1976template <class _Tp, class _Allocator> 1977void 1978deque<_Tp, _Allocator>::push_front(value_type&& __v) 1979{ 1980 allocator_type& __a = __base::__alloc(); 1981 if (__front_spare() == 0) 1982 __add_front_capacity(); 1983 // __front_spare() >= 1 1984 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 1985 --__base::__start_; 1986 ++__base::size(); 1987} 1988 1989 1990template <class _Tp, class _Allocator> 1991template <class... _Args> 1992#if _LIBCPP_STD_VER > 14 1993typename deque<_Tp, _Allocator>::reference 1994#else 1995void 1996#endif 1997deque<_Tp, _Allocator>::emplace_front(_Args&&... __args) 1998{ 1999 allocator_type& __a = __base::__alloc(); 2000 if (__front_spare() == 0) 2001 __add_front_capacity(); 2002 // __front_spare() >= 1 2003 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 2004 --__base::__start_; 2005 ++__base::size(); 2006#if _LIBCPP_STD_VER > 14 2007 return *__base::begin(); 2008#endif 2009} 2010 2011template <class _Tp, class _Allocator> 2012typename deque<_Tp, _Allocator>::iterator 2013deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v) 2014{ 2015 size_type __pos = __p - __base::begin(); 2016 size_type __to_end = __base::size() - __pos; 2017 allocator_type& __a = __base::__alloc(); 2018 if (__pos < __to_end) 2019 { // insert by shifting things backward 2020 if (__front_spare() == 0) 2021 __add_front_capacity(); 2022 // __front_spare() >= 1 2023 if (__pos == 0) 2024 { 2025 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 2026 --__base::__start_; 2027 ++__base::size(); 2028 } 2029 else 2030 { 2031 iterator __b = __base::begin(); 2032 iterator __bm1 = _VSTD::prev(__b); 2033 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2034 --__base::__start_; 2035 ++__base::size(); 2036 if (__pos > 1) 2037 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 2038 *__b = _VSTD::move(__v); 2039 } 2040 } 2041 else 2042 { // insert by shifting things forward 2043 if (__back_spare() == 0) 2044 __add_back_capacity(); 2045 // __back_capacity >= 1 2046 size_type __de = __base::size() - __pos; 2047 if (__de == 0) 2048 { 2049 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 2050 ++__base::size(); 2051 } 2052 else 2053 { 2054 iterator __e = __base::end(); 2055 iterator __em1 = _VSTD::prev(__e); 2056 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2057 ++__base::size(); 2058 if (__de > 1) 2059 __e = _VSTD::move_backward(__e - __de, __em1, __e); 2060 *--__e = _VSTD::move(__v); 2061 } 2062 } 2063 return __base::begin() + __pos; 2064} 2065 2066template <class _Tp, class _Allocator> 2067template <class... _Args> 2068typename deque<_Tp, _Allocator>::iterator 2069deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args) 2070{ 2071 size_type __pos = __p - __base::begin(); 2072 size_type __to_end = __base::size() - __pos; 2073 allocator_type& __a = __base::__alloc(); 2074 if (__pos < __to_end) 2075 { // insert by shifting things backward 2076 if (__front_spare() == 0) 2077 __add_front_capacity(); 2078 // __front_spare() >= 1 2079 if (__pos == 0) 2080 { 2081 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 2082 --__base::__start_; 2083 ++__base::size(); 2084 } 2085 else 2086 { 2087 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 2088 iterator __b = __base::begin(); 2089 iterator __bm1 = _VSTD::prev(__b); 2090 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2091 --__base::__start_; 2092 ++__base::size(); 2093 if (__pos > 1) 2094 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 2095 *__b = _VSTD::move(__tmp.get()); 2096 } 2097 } 2098 else 2099 { // insert by shifting things forward 2100 if (__back_spare() == 0) 2101 __add_back_capacity(); 2102 // __back_capacity >= 1 2103 size_type __de = __base::size() - __pos; 2104 if (__de == 0) 2105 { 2106 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 2107 ++__base::size(); 2108 } 2109 else 2110 { 2111 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 2112 iterator __e = __base::end(); 2113 iterator __em1 = _VSTD::prev(__e); 2114 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2115 ++__base::size(); 2116 if (__de > 1) 2117 __e = _VSTD::move_backward(__e - __de, __em1, __e); 2118 *--__e = _VSTD::move(__tmp.get()); 2119 } 2120 } 2121 return __base::begin() + __pos; 2122} 2123 2124#endif // _LIBCPP_CXX03_LANG 2125 2126 2127template <class _Tp, class _Allocator> 2128typename deque<_Tp, _Allocator>::iterator 2129deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v) 2130{ 2131 size_type __pos = __p - __base::begin(); 2132 size_type __to_end = __base::size() - __pos; 2133 allocator_type& __a = __base::__alloc(); 2134 if (__pos < __to_end) 2135 { // insert by shifting things backward 2136 if (__front_spare() == 0) 2137 __add_front_capacity(); 2138 // __front_spare() >= 1 2139 if (__pos == 0) 2140 { 2141 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 2142 --__base::__start_; 2143 ++__base::size(); 2144 } 2145 else 2146 { 2147 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2148 iterator __b = __base::begin(); 2149 iterator __bm1 = _VSTD::prev(__b); 2150 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b)) 2151 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1); 2152 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2153 --__base::__start_; 2154 ++__base::size(); 2155 if (__pos > 1) 2156 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt); 2157 *__b = *__vt; 2158 } 2159 } 2160 else 2161 { // insert by shifting things forward 2162 if (__back_spare() == 0) 2163 __add_back_capacity(); 2164 // __back_capacity >= 1 2165 size_type __de = __base::size() - __pos; 2166 if (__de == 0) 2167 { 2168 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 2169 ++__base::size(); 2170 } 2171 else 2172 { 2173 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2174 iterator __e = __base::end(); 2175 iterator __em1 = _VSTD::prev(__e); 2176 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1)) 2177 __vt = pointer_traits<const_pointer>::pointer_to(*__e); 2178 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2179 ++__base::size(); 2180 if (__de > 1) 2181 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt); 2182 *--__e = *__vt; 2183 } 2184 } 2185 return __base::begin() + __pos; 2186} 2187 2188template <class _Tp, class _Allocator> 2189typename deque<_Tp, _Allocator>::iterator 2190deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) 2191{ 2192 size_type __pos = __p - __base::begin(); 2193 size_type __to_end = __base::size() - __pos; 2194 allocator_type& __a = __base::__alloc(); 2195 if (__pos < __to_end) 2196 { // insert by shifting things backward 2197 if (__n > __front_spare()) 2198 __add_front_capacity(__n - __front_spare()); 2199 // __n <= __front_spare() 2200 iterator __old_begin = __base::begin(); 2201 iterator __i = __old_begin; 2202 if (__n > __pos) 2203 { 2204 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size()) 2205 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v); 2206 __n = __pos; 2207 } 2208 if (__n > 0) 2209 { 2210 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2211 iterator __obn = __old_begin + __n; 2212 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); 2213 if (__n < __pos) 2214 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); 2215 _VSTD::fill_n(__old_begin, __n, *__vt); 2216 } 2217 } 2218 else 2219 { // insert by shifting things forward 2220 size_type __back_capacity = __back_spare(); 2221 if (__n > __back_capacity) 2222 __add_back_capacity(__n - __back_capacity); 2223 // __n <= __back_capacity 2224 iterator __old_end = __base::end(); 2225 iterator __i = __old_end; 2226 size_type __de = __base::size() - __pos; 2227 if (__n > __de) 2228 { 2229 for (size_type __m = __n - __de; __m; --__m, (void) ++__i, ++__base::size()) 2230 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2231 __n = __de; 2232 } 2233 if (__n > 0) 2234 { 2235 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2236 iterator __oen = __old_end - __n; 2237 __move_construct_and_check(__oen, __old_end, __i, __vt); 2238 if (__n < __de) 2239 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); 2240 _VSTD::fill_n(__old_end - __n, __n, *__vt); 2241 } 2242 } 2243 return __base::begin() + __pos; 2244} 2245 2246template <class _Tp, class _Allocator> 2247template <class _InputIter> 2248typename deque<_Tp, _Allocator>::iterator 2249deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, 2250 typename enable_if<__is_cpp17_input_iterator<_InputIter>::value 2251 &&!__is_cpp17_forward_iterator<_InputIter>::value>::type*) 2252{ 2253 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc()); 2254 __buf.__construct_at_end(__f, __l); 2255 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi; 2256 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); 2257} 2258 2259template <class _Tp, class _Allocator> 2260template <class _ForwardIterator> 2261typename deque<_Tp, _Allocator>::iterator 2262deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 2263 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value 2264 &&!__is_cpp17_bidirectional_iterator<_ForwardIterator>::value>::type*) 2265{ 2266 size_type __n = _VSTD::distance(__f, __l); 2267 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc()); 2268 __buf.__construct_at_end(__f, __l); 2269 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd; 2270 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end())); 2271} 2272 2273template <class _Tp, class _Allocator> 2274template <class _BiIter> 2275typename deque<_Tp, _Allocator>::iterator 2276deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, 2277 typename enable_if<__is_cpp17_bidirectional_iterator<_BiIter>::value>::type*) 2278{ 2279 size_type __n = _VSTD::distance(__f, __l); 2280 size_type __pos = __p - __base::begin(); 2281 size_type __to_end = __base::size() - __pos; 2282 allocator_type& __a = __base::__alloc(); 2283 if (__pos < __to_end) 2284 { // insert by shifting things backward 2285 if (__n > __front_spare()) 2286 __add_front_capacity(__n - __front_spare()); 2287 // __n <= __front_spare() 2288 iterator __old_begin = __base::begin(); 2289 iterator __i = __old_begin; 2290 _BiIter __m = __f; 2291 if (__n > __pos) 2292 { 2293 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos); 2294 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size()) 2295 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j); 2296 __n = __pos; 2297 } 2298 if (__n > 0) 2299 { 2300 iterator __obn = __old_begin + __n; 2301 for (iterator __j = __obn; __j != __old_begin;) 2302 { 2303 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j)); 2304 --__base::__start_; 2305 ++__base::size(); 2306 } 2307 if (__n < __pos) 2308 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin); 2309 _VSTD::copy(__m, __l, __old_begin); 2310 } 2311 } 2312 else 2313 { // insert by shifting things forward 2314 size_type __back_capacity = __back_spare(); 2315 if (__n > __back_capacity) 2316 __add_back_capacity(__n - __back_capacity); 2317 // __n <= __back_capacity 2318 iterator __old_end = __base::end(); 2319 iterator __i = __old_end; 2320 _BiIter __m = __l; 2321 size_type __de = __base::size() - __pos; 2322 if (__n > __de) 2323 { 2324 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de); 2325 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size()) 2326 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j); 2327 __n = __de; 2328 } 2329 if (__n > 0) 2330 { 2331 iterator __oen = __old_end - __n; 2332 for (iterator __j = __oen; __j != __old_end; ++__i, (void) ++__j, ++__base::size()) 2333 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j)); 2334 if (__n < __de) 2335 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end); 2336 _VSTD::copy_backward(__f, __m, __old_end); 2337 } 2338 } 2339 return __base::begin() + __pos; 2340} 2341 2342template <class _Tp, class _Allocator> 2343template <class _InpIter> 2344void 2345deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, 2346 typename enable_if<__is_cpp17_input_iterator<_InpIter>::value && 2347 !__is_cpp17_forward_iterator<_InpIter>::value>::type*) 2348{ 2349 for (; __f != __l; ++__f) 2350#ifdef _LIBCPP_CXX03_LANG 2351 push_back(*__f); 2352#else 2353 emplace_back(*__f); 2354#endif 2355} 2356 2357template <class _Tp, class _Allocator> 2358template <class _ForIter> 2359void 2360deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, 2361 typename enable_if<__is_cpp17_forward_iterator<_ForIter>::value>::type*) 2362{ 2363 size_type __n = _VSTD::distance(__f, __l); 2364 allocator_type& __a = __base::__alloc(); 2365 size_type __back_capacity = __back_spare(); 2366 if (__n > __back_capacity) 2367 __add_back_capacity(__n - __back_capacity); 2368 // __n <= __back_capacity 2369 for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) { 2370 _ConstructTransaction __tx(this, __br); 2371 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__f) { 2372 __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), *__f); 2373 } 2374 } 2375} 2376 2377template <class _Tp, class _Allocator> 2378void 2379deque<_Tp, _Allocator>::__append(size_type __n) 2380{ 2381 allocator_type& __a = __base::__alloc(); 2382 size_type __back_capacity = __back_spare(); 2383 if (__n > __back_capacity) 2384 __add_back_capacity(__n - __back_capacity); 2385 // __n <= __back_capacity 2386 for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) { 2387 _ConstructTransaction __tx(this, __br); 2388 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { 2389 __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_)); 2390 } 2391 } 2392} 2393 2394template <class _Tp, class _Allocator> 2395void 2396deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) 2397{ 2398 allocator_type& __a = __base::__alloc(); 2399 size_type __back_capacity = __back_spare(); 2400 if (__n > __back_capacity) 2401 __add_back_capacity(__n - __back_capacity); 2402 // __n <= __back_capacity 2403 for (__deque_block_range __br : __deque_range(__base::end(), __base::end() + __n)) { 2404 _ConstructTransaction __tx(this, __br); 2405 for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { 2406 __alloc_traits::construct(__a, _VSTD::__to_address(__tx.__pos_), __v); 2407 } 2408 } 2409 2410} 2411 2412// Create front capacity for one block of elements. 2413// Strong guarantee. Either do it or don't touch anything. 2414template <class _Tp, class _Allocator> 2415void 2416deque<_Tp, _Allocator>::__add_front_capacity() 2417{ 2418 allocator_type& __a = __base::__alloc(); 2419 if (__back_spare() >= __base::__block_size) 2420 { 2421 __base::__start_ += __base::__block_size; 2422 pointer __pt = __base::__map_.back(); 2423 __base::__map_.pop_back(); 2424 __base::__map_.push_front(__pt); 2425 } 2426 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer 2427 else if (__base::__map_.size() < __base::__map_.capacity()) 2428 { // we can put the new buffer into the map, but don't shift things around 2429 // until all buffers are allocated. If we throw, we don't need to fix 2430 // anything up (any added buffers are undetectible) 2431 if (__base::__map_.__front_spare() > 0) 2432 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2433 else 2434 { 2435 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2436 // Done allocating, reorder capacity 2437 pointer __pt = __base::__map_.back(); 2438 __base::__map_.pop_back(); 2439 __base::__map_.push_front(__pt); 2440 } 2441 __base::__start_ = __base::__map_.size() == 1 ? 2442 __base::__block_size / 2 : 2443 __base::__start_ + __base::__block_size; 2444 } 2445 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2446 else 2447 { 2448 __split_buffer<pointer, typename __base::__pointer_allocator&> 2449 __buf(max<size_type>(2 * __base::__map_.capacity(), 1), 2450 0, __base::__map_.__alloc()); 2451 2452 typedef __allocator_destructor<_Allocator> _Dp; 2453 unique_ptr<pointer, _Dp> __hold( 2454 __alloc_traits::allocate(__a, __base::__block_size), 2455 _Dp(__a, __base::__block_size)); 2456 __buf.push_back(__hold.get()); 2457 __hold.release(); 2458 2459 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2460 __i != __base::__map_.end(); ++__i) 2461 __buf.push_back(*__i); 2462 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2463 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2464 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2465 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2466 __base::__start_ = __base::__map_.size() == 1 ? 2467 __base::__block_size / 2 : 2468 __base::__start_ + __base::__block_size; 2469 } 2470} 2471 2472// Create front capacity for __n elements. 2473// Strong guarantee. Either do it or don't touch anything. 2474template <class _Tp, class _Allocator> 2475void 2476deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) 2477{ 2478 allocator_type& __a = __base::__alloc(); 2479 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2480 // Number of unused blocks at back: 2481 size_type __back_capacity = __back_spare() / __base::__block_size; 2482 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need 2483 __nb -= __back_capacity; // number of blocks need to allocate 2484 // If __nb == 0, then we have sufficient capacity. 2485 if (__nb == 0) 2486 { 2487 __base::__start_ += __base::__block_size * __back_capacity; 2488 for (; __back_capacity > 0; --__back_capacity) 2489 { 2490 pointer __pt = __base::__map_.back(); 2491 __base::__map_.pop_back(); 2492 __base::__map_.push_front(__pt); 2493 } 2494 } 2495 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2496 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2497 { // we can put the new buffers into the map, but don't shift things around 2498 // until all buffers are allocated. If we throw, we don't need to fix 2499 // anything up (any added buffers are undetectible) 2500 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1)) 2501 { 2502 if (__base::__map_.__front_spare() == 0) 2503 break; 2504 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2505 } 2506 for (; __nb > 0; --__nb, ++__back_capacity) 2507 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2508 // Done allocating, reorder capacity 2509 __base::__start_ += __back_capacity * __base::__block_size; 2510 for (; __back_capacity > 0; --__back_capacity) 2511 { 2512 pointer __pt = __base::__map_.back(); 2513 __base::__map_.pop_back(); 2514 __base::__map_.push_front(__pt); 2515 } 2516 } 2517 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2518 else 2519 { 2520 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty(); 2521 __split_buffer<pointer, typename __base::__pointer_allocator&> 2522 __buf(max<size_type>(2* __base::__map_.capacity(), 2523 __nb + __base::__map_.size()), 2524 0, __base::__map_.__alloc()); 2525#ifndef _LIBCPP_NO_EXCEPTIONS 2526 try 2527 { 2528#endif // _LIBCPP_NO_EXCEPTIONS 2529 for (; __nb > 0; --__nb) 2530 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2531#ifndef _LIBCPP_NO_EXCEPTIONS 2532 } 2533 catch (...) 2534 { 2535 for (typename __base::__map_pointer __i = __buf.begin(); 2536 __i != __buf.end(); ++__i) 2537 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2538 throw; 2539 } 2540#endif // _LIBCPP_NO_EXCEPTIONS 2541 for (; __back_capacity > 0; --__back_capacity) 2542 { 2543 __buf.push_back(__base::__map_.back()); 2544 __base::__map_.pop_back(); 2545 } 2546 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2547 __i != __base::__map_.end(); ++__i) 2548 __buf.push_back(*__i); 2549 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2550 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2551 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2552 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2553 __base::__start_ += __ds; 2554 } 2555} 2556 2557// Create back capacity for one block of elements. 2558// Strong guarantee. Either do it or don't touch anything. 2559template <class _Tp, class _Allocator> 2560void 2561deque<_Tp, _Allocator>::__add_back_capacity() 2562{ 2563 allocator_type& __a = __base::__alloc(); 2564 if (__front_spare() >= __base::__block_size) 2565 { 2566 __base::__start_ -= __base::__block_size; 2567 pointer __pt = __base::__map_.front(); 2568 __base::__map_.pop_front(); 2569 __base::__map_.push_back(__pt); 2570 } 2571 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2572 else if (__base::__map_.size() < __base::__map_.capacity()) 2573 { // we can put the new buffer into the map, but don't shift things around 2574 // until it is allocated. If we throw, we don't need to fix 2575 // anything up (any added buffers are undetectible) 2576 if (__base::__map_.__back_spare() != 0) 2577 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2578 else 2579 { 2580 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2581 // Done allocating, reorder capacity 2582 pointer __pt = __base::__map_.front(); 2583 __base::__map_.pop_front(); 2584 __base::__map_.push_back(__pt); 2585 } 2586 } 2587 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2588 else 2589 { 2590 __split_buffer<pointer, typename __base::__pointer_allocator&> 2591 __buf(max<size_type>(2* __base::__map_.capacity(), 1), 2592 __base::__map_.size(), 2593 __base::__map_.__alloc()); 2594 2595 typedef __allocator_destructor<_Allocator> _Dp; 2596 unique_ptr<pointer, _Dp> __hold( 2597 __alloc_traits::allocate(__a, __base::__block_size), 2598 _Dp(__a, __base::__block_size)); 2599 __buf.push_back(__hold.get()); 2600 __hold.release(); 2601 2602 for (typename __base::__map_pointer __i = __base::__map_.end(); 2603 __i != __base::__map_.begin();) 2604 __buf.push_front(*--__i); 2605 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2606 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2607 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2608 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2609 } 2610} 2611 2612// Create back capacity for __n elements. 2613// Strong guarantee. Either do it or don't touch anything. 2614template <class _Tp, class _Allocator> 2615void 2616deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) 2617{ 2618 allocator_type& __a = __base::__alloc(); 2619 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2620 // Number of unused blocks at front: 2621 size_type __front_capacity = __front_spare() / __base::__block_size; 2622 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need 2623 __nb -= __front_capacity; // number of blocks need to allocate 2624 // If __nb == 0, then we have sufficient capacity. 2625 if (__nb == 0) 2626 { 2627 __base::__start_ -= __base::__block_size * __front_capacity; 2628 for (; __front_capacity > 0; --__front_capacity) 2629 { 2630 pointer __pt = __base::__map_.front(); 2631 __base::__map_.pop_front(); 2632 __base::__map_.push_back(__pt); 2633 } 2634 } 2635 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2636 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2637 { // we can put the new buffers into the map, but don't shift things around 2638 // until all buffers are allocated. If we throw, we don't need to fix 2639 // anything up (any added buffers are undetectible) 2640 for (; __nb > 0; --__nb) 2641 { 2642 if (__base::__map_.__back_spare() == 0) 2643 break; 2644 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2645 } 2646 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ += 2647 __base::__block_size - (__base::__map_.size() == 1)) 2648 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2649 // Done allocating, reorder capacity 2650 __base::__start_ -= __base::__block_size * __front_capacity; 2651 for (; __front_capacity > 0; --__front_capacity) 2652 { 2653 pointer __pt = __base::__map_.front(); 2654 __base::__map_.pop_front(); 2655 __base::__map_.push_back(__pt); 2656 } 2657 } 2658 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2659 else 2660 { 2661 size_type __ds = __front_capacity * __base::__block_size; 2662 __split_buffer<pointer, typename __base::__pointer_allocator&> 2663 __buf(max<size_type>(2* __base::__map_.capacity(), 2664 __nb + __base::__map_.size()), 2665 __base::__map_.size() - __front_capacity, 2666 __base::__map_.__alloc()); 2667#ifndef _LIBCPP_NO_EXCEPTIONS 2668 try 2669 { 2670#endif // _LIBCPP_NO_EXCEPTIONS 2671 for (; __nb > 0; --__nb) 2672 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2673#ifndef _LIBCPP_NO_EXCEPTIONS 2674 } 2675 catch (...) 2676 { 2677 for (typename __base::__map_pointer __i = __buf.begin(); 2678 __i != __buf.end(); ++__i) 2679 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2680 throw; 2681 } 2682#endif // _LIBCPP_NO_EXCEPTIONS 2683 for (; __front_capacity > 0; --__front_capacity) 2684 { 2685 __buf.push_back(__base::__map_.front()); 2686 __base::__map_.pop_front(); 2687 } 2688 for (typename __base::__map_pointer __i = __base::__map_.end(); 2689 __i != __base::__map_.begin();) 2690 __buf.push_front(*--__i); 2691 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2692 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2693 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2694 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2695 __base::__start_ -= __ds; 2696 } 2697} 2698 2699template <class _Tp, class _Allocator> 2700void 2701deque<_Tp, _Allocator>::pop_front() 2702{ 2703 allocator_type& __a = __base::__alloc(); 2704 __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() + 2705 __base::__start_ / __base::__block_size) + 2706 __base::__start_ % __base::__block_size)); 2707 --__base::size(); 2708 ++__base::__start_; 2709 __maybe_remove_front_spare(); 2710} 2711 2712template <class _Tp, class _Allocator> 2713void 2714deque<_Tp, _Allocator>::pop_back() 2715{ 2716 _LIBCPP_ASSERT(!empty(), "deque::pop_back called on an empty deque"); 2717 allocator_type& __a = __base::__alloc(); 2718 size_type __p = __base::size() + __base::__start_ - 1; 2719 __alloc_traits::destroy(__a, _VSTD::__to_address(*(__base::__map_.begin() + 2720 __p / __base::__block_size) + 2721 __p % __base::__block_size)); 2722 --__base::size(); 2723 __maybe_remove_back_spare(); 2724} 2725 2726// move assign [__f, __l) to [__r, __r + (__l-__f)). 2727// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. 2728template <class _Tp, class _Allocator> 2729typename deque<_Tp, _Allocator>::iterator 2730deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, 2731 const_pointer& __vt) 2732{ 2733 // as if 2734 // for (; __f != __l; ++__f, ++__r) 2735 // *__r = _VSTD::move(*__f); 2736 difference_type __n = __l - __f; 2737 while (__n > 0) 2738 { 2739 pointer __fb = __f.__ptr_; 2740 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2741 difference_type __bs = __fe - __fb; 2742 if (__bs > __n) 2743 { 2744 __bs = __n; 2745 __fe = __fb + __bs; 2746 } 2747 if (__fb <= __vt && __vt < __fe) 2748 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_; 2749 __r = _VSTD::move(__fb, __fe, __r); 2750 __n -= __bs; 2751 __f += __bs; 2752 } 2753 return __r; 2754} 2755 2756// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. 2757// If __vt points into [__f, __l), then add (__r - __l) to __vt. 2758template <class _Tp, class _Allocator> 2759typename deque<_Tp, _Allocator>::iterator 2760deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, 2761 const_pointer& __vt) 2762{ 2763 // as if 2764 // while (__f != __l) 2765 // *--__r = _VSTD::move(*--__l); 2766 difference_type __n = __l - __f; 2767 while (__n > 0) 2768 { 2769 --__l; 2770 pointer __lb = *__l.__m_iter_; 2771 pointer __le = __l.__ptr_ + 1; 2772 difference_type __bs = __le - __lb; 2773 if (__bs > __n) 2774 { 2775 __bs = __n; 2776 __lb = __le - __bs; 2777 } 2778 if (__lb <= __vt && __vt < __le) 2779 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_; 2780 __r = _VSTD::move_backward(__lb, __le, __r); 2781 __n -= __bs; 2782 __l -= __bs - 1; 2783 } 2784 return __r; 2785} 2786 2787// move construct [__f, __l) to [__r, __r + (__l-__f)). 2788// If __vt points into [__f, __l), then add (__r - __f) to __vt. 2789template <class _Tp, class _Allocator> 2790void 2791deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, 2792 iterator __r, const_pointer& __vt) 2793{ 2794 allocator_type& __a = __base::__alloc(); 2795 // as if 2796 // for (; __f != __l; ++__r, ++__f, ++__base::size()) 2797 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f)); 2798 difference_type __n = __l - __f; 2799 while (__n > 0) 2800 { 2801 pointer __fb = __f.__ptr_; 2802 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2803 difference_type __bs = __fe - __fb; 2804 if (__bs > __n) 2805 { 2806 __bs = __n; 2807 __fe = __fb + __bs; 2808 } 2809 if (__fb <= __vt && __vt < __fe) 2810 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_; 2811 for (; __fb != __fe; ++__fb, ++__r, ++__base::size()) 2812 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb)); 2813 __n -= __bs; 2814 __f += __bs; 2815 } 2816} 2817 2818// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. 2819// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. 2820template <class _Tp, class _Allocator> 2821void 2822deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l, 2823 iterator __r, const_pointer& __vt) 2824{ 2825 allocator_type& __a = __base::__alloc(); 2826 // as if 2827 // for (iterator __j = __l; __j != __f;) 2828 // { 2829 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j)); 2830 // --__base::__start_; 2831 // ++__base::size(); 2832 // } 2833 difference_type __n = __l - __f; 2834 while (__n > 0) 2835 { 2836 --__l; 2837 pointer __lb = *__l.__m_iter_; 2838 pointer __le = __l.__ptr_ + 1; 2839 difference_type __bs = __le - __lb; 2840 if (__bs > __n) 2841 { 2842 __bs = __n; 2843 __lb = __le - __bs; 2844 } 2845 if (__lb <= __vt && __vt < __le) 2846 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_; 2847 while (__le != __lb) 2848 { 2849 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le)); 2850 --__base::__start_; 2851 ++__base::size(); 2852 } 2853 __n -= __bs; 2854 __l -= __bs - 1; 2855 } 2856} 2857 2858template <class _Tp, class _Allocator> 2859typename deque<_Tp, _Allocator>::iterator 2860deque<_Tp, _Allocator>::erase(const_iterator __f) 2861{ 2862 iterator __b = __base::begin(); 2863 difference_type __pos = __f - __b; 2864 iterator __p = __b + __pos; 2865 allocator_type& __a = __base::__alloc(); 2866 if (static_cast<size_t>(__pos) <= (__base::size() - 1) / 2) 2867 { // erase from front 2868 _VSTD::move_backward(__b, __p, _VSTD::next(__p)); 2869 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2870 --__base::size(); 2871 ++__base::__start_; 2872 __maybe_remove_front_spare(); 2873 } 2874 else 2875 { // erase from back 2876 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p); 2877 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2878 --__base::size(); 2879 __maybe_remove_back_spare(); 2880 } 2881 return __base::begin() + __pos; 2882} 2883 2884template <class _Tp, class _Allocator> 2885typename deque<_Tp, _Allocator>::iterator 2886deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) 2887{ 2888 difference_type __n = __l - __f; 2889 iterator __b = __base::begin(); 2890 difference_type __pos = __f - __b; 2891 iterator __p = __b + __pos; 2892 if (__n > 0) 2893 { 2894 allocator_type& __a = __base::__alloc(); 2895 if (static_cast<size_t>(__pos) <= (__base::size() - __n) / 2) 2896 { // erase from front 2897 iterator __i = _VSTD::move_backward(__b, __p, __p + __n); 2898 for (; __b != __i; ++__b) 2899 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2900 __base::size() -= __n; 2901 __base::__start_ += __n; 2902 while (__maybe_remove_front_spare()) { 2903 } 2904 } 2905 else 2906 { // erase from back 2907 iterator __i = _VSTD::move(__p + __n, __base::end(), __p); 2908 for (iterator __e = __base::end(); __i != __e; ++__i) 2909 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2910 __base::size() -= __n; 2911 while (__maybe_remove_back_spare()) { 2912 } 2913 } 2914 } 2915 return __base::begin() + __pos; 2916} 2917 2918template <class _Tp, class _Allocator> 2919void 2920deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) 2921{ 2922 iterator __e = __base::end(); 2923 difference_type __n = __e - __f; 2924 if (__n > 0) 2925 { 2926 allocator_type& __a = __base::__alloc(); 2927 iterator __b = __base::begin(); 2928 difference_type __pos = __f - __b; 2929 for (iterator __p = __b + __pos; __p != __e; ++__p) 2930 __alloc_traits::destroy(__a, _VSTD::addressof(*__p)); 2931 __base::size() -= __n; 2932 while (__maybe_remove_back_spare()) { 2933 } 2934 } 2935} 2936 2937template <class _Tp, class _Allocator> 2938inline 2939void 2940deque<_Tp, _Allocator>::swap(deque& __c) 2941#if _LIBCPP_STD_VER >= 14 2942 _NOEXCEPT 2943#else 2944 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2945 __is_nothrow_swappable<allocator_type>::value) 2946#endif 2947{ 2948 __base::swap(__c); 2949} 2950 2951template <class _Tp, class _Allocator> 2952inline 2953void 2954deque<_Tp, _Allocator>::clear() _NOEXCEPT 2955{ 2956 __base::clear(); 2957} 2958 2959template <class _Tp, class _Allocator> 2960inline _LIBCPP_INLINE_VISIBILITY 2961bool 2962operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2963{ 2964 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); 2965 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2966} 2967 2968template <class _Tp, class _Allocator> 2969inline _LIBCPP_INLINE_VISIBILITY 2970bool 2971operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2972{ 2973 return !(__x == __y); 2974} 2975 2976template <class _Tp, class _Allocator> 2977inline _LIBCPP_INLINE_VISIBILITY 2978bool 2979operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2980{ 2981 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2982} 2983 2984template <class _Tp, class _Allocator> 2985inline _LIBCPP_INLINE_VISIBILITY 2986bool 2987operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2988{ 2989 return __y < __x; 2990} 2991 2992template <class _Tp, class _Allocator> 2993inline _LIBCPP_INLINE_VISIBILITY 2994bool 2995operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2996{ 2997 return !(__x < __y); 2998} 2999 3000template <class _Tp, class _Allocator> 3001inline _LIBCPP_INLINE_VISIBILITY 3002bool 3003operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 3004{ 3005 return !(__y < __x); 3006} 3007 3008template <class _Tp, class _Allocator> 3009inline _LIBCPP_INLINE_VISIBILITY 3010void 3011swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) 3012 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3013{ 3014 __x.swap(__y); 3015} 3016 3017#if _LIBCPP_STD_VER > 17 3018template <class _Tp, class _Allocator, class _Up> 3019inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type 3020erase(deque<_Tp, _Allocator>& __c, const _Up& __v) { 3021 auto __old_size = __c.size(); 3022 __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); 3023 return __old_size - __c.size(); 3024} 3025 3026template <class _Tp, class _Allocator, class _Predicate> 3027inline _LIBCPP_INLINE_VISIBILITY typename deque<_Tp, _Allocator>::size_type 3028erase_if(deque<_Tp, _Allocator>& __c, _Predicate __pred) { 3029 auto __old_size = __c.size(); 3030 __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); 3031 return __old_size - __c.size(); 3032} 3033 3034template <> 3035inline constexpr bool __format::__enable_insertable<std::deque<char>> = true; 3036#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 3037template <> 3038inline constexpr bool __format::__enable_insertable<std::deque<wchar_t>> = true; 3039#endif 3040 3041#endif // _LIBCPP_STD_VER > 17 3042 3043_LIBCPP_END_NAMESPACE_STD 3044 3045_LIBCPP_POP_MACROS 3046 3047#endif // _LIBCPP_DEQUE 3048