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