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