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