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_VISIBLE __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_VISIBLE __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_VISIBLE deque; 414 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp> 415 friend class _LIBCPP_VISIBLE __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_VISIBLE 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 iterator __b = __base::begin(); 1970 iterator __bm1 = _VSTD::prev(__b); 1971 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 1972 --__base::__start_; 1973 ++__base::size(); 1974 if (__pos > 1) 1975 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 1976 *__b = value_type(_VSTD::forward<_Args>(__args)...); 1977 } 1978 } 1979 else 1980 { // insert by shifting things forward 1981 if (__back_spare() == 0) 1982 __add_back_capacity(); 1983 // __back_capacity >= 1 1984 size_type __de = __base::size() - __pos; 1985 if (__de == 0) 1986 { 1987 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 1988 ++__base::size(); 1989 } 1990 else 1991 { 1992 iterator __e = __base::end(); 1993 iterator __em1 = _VSTD::prev(__e); 1994 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 1995 ++__base::size(); 1996 if (__de > 1) 1997 __e = _VSTD::move_backward(__e - __de, __em1, __e); 1998 *--__e = value_type(_VSTD::forward<_Args>(__args)...); 1999 } 2000 } 2001 return __base::begin() + __pos; 2002} 2003 2004#endif // _LIBCPP_HAS_NO_VARIADICS 2005#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2006 2007template <class _Tp, class _Allocator> 2008typename deque<_Tp, _Allocator>::iterator 2009deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) 2010{ 2011 size_type __pos = __p - __base::begin(); 2012 size_type __to_end = __base::size() - __pos; 2013 allocator_type& __a = __base::__alloc(); 2014 if (__pos < __to_end) 2015 { // insert by shifting things backward 2016 if (__n > __front_spare()) 2017 __add_front_capacity(__n - __front_spare()); 2018 // __n <= __front_spare() 2019 size_type __old_n = __n; 2020 iterator __old_begin = __base::begin(); 2021 iterator __i = __old_begin; 2022 if (__n > __pos) 2023 { 2024 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size()) 2025 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v); 2026 __n = __pos; 2027 } 2028 if (__n > 0) 2029 { 2030 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2031 iterator __obn = __old_begin + __n; 2032 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); 2033 if (__n < __pos) 2034 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); 2035 _VSTD::fill_n(__old_begin, __n, *__vt); 2036 } 2037 } 2038 else 2039 { // insert by shifting things forward 2040 size_type __back_capacity = __back_spare(); 2041 if (__n > __back_capacity) 2042 __add_back_capacity(__n - __back_capacity); 2043 // __n <= __back_capacity 2044 size_type __old_n = __n; 2045 iterator __old_end = __base::end(); 2046 iterator __i = __old_end; 2047 size_type __de = __base::size() - __pos; 2048 if (__n > __de) 2049 { 2050 for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size()) 2051 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2052 __n = __de; 2053 } 2054 if (__n > 0) 2055 { 2056 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2057 iterator __oen = __old_end - __n; 2058 __move_construct_and_check(__oen, __old_end, __i, __vt); 2059 if (__n < __de) 2060 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); 2061 _VSTD::fill_n(__old_end - __n, __n, *__vt); 2062 } 2063 } 2064 return __base::begin() + __pos; 2065} 2066 2067template <class _Tp, class _Allocator> 2068template <class _InputIter> 2069typename deque<_Tp, _Allocator>::iterator 2070deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, 2071 typename enable_if<__is_input_iterator<_InputIter>::value 2072 &&!__is_bidirectional_iterator<_InputIter>::value>::type*) 2073{ 2074 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc()); 2075 __buf.__construct_at_end(__f, __l); 2076 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi; 2077 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); 2078} 2079 2080template <class _Tp, class _Allocator> 2081template <class _BiIter> 2082typename deque<_Tp, _Allocator>::iterator 2083deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, 2084 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*) 2085{ 2086 size_type __n = _VSTD::distance(__f, __l); 2087 size_type __pos = __p - __base::begin(); 2088 size_type __to_end = __base::size() - __pos; 2089 allocator_type& __a = __base::__alloc(); 2090 if (__pos < __to_end) 2091 { // insert by shifting things backward 2092 if (__n > __front_spare()) 2093 __add_front_capacity(__n - __front_spare()); 2094 // __n <= __front_spare() 2095 size_type __old_n = __n; 2096 iterator __old_begin = __base::begin(); 2097 iterator __i = __old_begin; 2098 _BiIter __m = __f; 2099 if (__n > __pos) 2100 { 2101 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos); 2102 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size()) 2103 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j); 2104 __n = __pos; 2105 } 2106 if (__n > 0) 2107 { 2108 iterator __obn = __old_begin + __n; 2109 for (iterator __j = __obn; __j != __old_begin;) 2110 { 2111 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j)); 2112 --__base::__start_; 2113 ++__base::size(); 2114 } 2115 if (__n < __pos) 2116 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin); 2117 _VSTD::copy(__m, __l, __old_begin); 2118 } 2119 } 2120 else 2121 { // insert by shifting things forward 2122 size_type __back_capacity = __back_spare(); 2123 if (__n > __back_capacity) 2124 __add_back_capacity(__n - __back_capacity); 2125 // __n <= __back_capacity 2126 size_type __old_n = __n; 2127 iterator __old_end = __base::end(); 2128 iterator __i = __old_end; 2129 _BiIter __m = __l; 2130 size_type __de = __base::size() - __pos; 2131 if (__n > __de) 2132 { 2133 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de); 2134 for (_BiIter __j = __m; __j != __l; ++__i, ++__j, ++__base::size()) 2135 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j); 2136 __n = __de; 2137 } 2138 if (__n > 0) 2139 { 2140 iterator __oen = __old_end - __n; 2141 for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size()) 2142 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j)); 2143 if (__n < __de) 2144 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end); 2145 _VSTD::copy_backward(__f, __m, __old_end); 2146 } 2147 } 2148 return __base::begin() + __pos; 2149} 2150 2151template <class _Tp, class _Allocator> 2152template <class _InpIter> 2153void 2154deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, 2155 typename enable_if<__is_input_iterator<_InpIter>::value && 2156 !__is_forward_iterator<_InpIter>::value>::type*) 2157{ 2158 for (; __f != __l; ++__f) 2159 push_back(*__f); 2160} 2161 2162template <class _Tp, class _Allocator> 2163template <class _ForIter> 2164void 2165deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, 2166 typename enable_if<__is_forward_iterator<_ForIter>::value>::type*) 2167{ 2168 size_type __n = _VSTD::distance(__f, __l); 2169 allocator_type& __a = __base::__alloc(); 2170 size_type __back_capacity = __back_spare(); 2171 if (__n > __back_capacity) 2172 __add_back_capacity(__n - __back_capacity); 2173 // __n <= __back_capacity 2174 for (iterator __i = __base::end(); __f != __l; ++__i, ++__f, ++__base::size()) 2175 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f); 2176} 2177 2178template <class _Tp, class _Allocator> 2179void 2180deque<_Tp, _Allocator>::__append(size_type __n) 2181{ 2182 allocator_type& __a = __base::__alloc(); 2183 size_type __back_capacity = __back_spare(); 2184 if (__n > __back_capacity) 2185 __add_back_capacity(__n - __back_capacity); 2186 // __n <= __back_capacity 2187 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2188 __alloc_traits::construct(__a, _VSTD::addressof(*__i)); 2189} 2190 2191template <class _Tp, class _Allocator> 2192void 2193deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) 2194{ 2195 allocator_type& __a = __base::__alloc(); 2196 size_type __back_capacity = __back_spare(); 2197 if (__n > __back_capacity) 2198 __add_back_capacity(__n - __back_capacity); 2199 // __n <= __back_capacity 2200 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2201 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2202} 2203 2204// Create front capacity for one block of elements. 2205// Strong guarantee. Either do it or don't touch anything. 2206template <class _Tp, class _Allocator> 2207void 2208deque<_Tp, _Allocator>::__add_front_capacity() 2209{ 2210 allocator_type& __a = __base::__alloc(); 2211 if (__back_spare() >= __base::__block_size) 2212 { 2213 __base::__start_ += __base::__block_size; 2214 pointer __pt = __base::__map_.back(); 2215 __base::__map_.pop_back(); 2216 __base::__map_.push_front(__pt); 2217 } 2218 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer 2219 else if (__base::__map_.size() < __base::__map_.capacity()) 2220 { // we can put the new buffer into the map, but don't shift things around 2221 // until all buffers are allocated. If we throw, we don't need to fix 2222 // anything up (any added buffers are undetectible) 2223 if (__base::__map_.__front_spare() > 0) 2224 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2225 else 2226 { 2227 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2228 // Done allocating, reorder capacity 2229 pointer __pt = __base::__map_.back(); 2230 __base::__map_.pop_back(); 2231 __base::__map_.push_front(__pt); 2232 } 2233 __base::__start_ = __base::__map_.size() == 1 ? 2234 __base::__block_size / 2 : 2235 __base::__start_ + __base::__block_size; 2236 } 2237 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2238 else 2239 { 2240 __split_buffer<pointer, typename __base::__pointer_allocator&> 2241 __buf(max<size_type>(2 * __base::__map_.capacity(), 1), 2242 0, __base::__map_.__alloc()); 2243#ifndef _LIBCPP_NO_EXCEPTIONS 2244 try 2245 { 2246#endif // _LIBCPP_NO_EXCEPTIONS 2247 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2248#ifndef _LIBCPP_NO_EXCEPTIONS 2249 } 2250 catch (...) 2251 { 2252 __alloc_traits::deallocate(__a, __buf.front(), __base::__block_size); 2253 throw; 2254 } 2255#endif // _LIBCPP_NO_EXCEPTIONS 2256 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2257 __i != __base::__map_.end(); ++__i) 2258 __buf.push_back(*__i); 2259 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2260 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2261 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2262 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2263 __base::__start_ = __base::__map_.size() == 1 ? 2264 __base::__block_size / 2 : 2265 __base::__start_ + __base::__block_size; 2266 } 2267} 2268 2269// Create front capacity for __n elements. 2270// Strong guarantee. Either do it or don't touch anything. 2271template <class _Tp, class _Allocator> 2272void 2273deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) 2274{ 2275 allocator_type& __a = __base::__alloc(); 2276 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2277 // Number of unused blocks at back: 2278 size_type __back_capacity = __back_spare() / __base::__block_size; 2279 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need 2280 __nb -= __back_capacity; // number of blocks need to allocate 2281 // If __nb == 0, then we have sufficient capacity. 2282 if (__nb == 0) 2283 { 2284 __base::__start_ += __base::__block_size * __back_capacity; 2285 for (; __back_capacity > 0; --__back_capacity) 2286 { 2287 pointer __pt = __base::__map_.back(); 2288 __base::__map_.pop_back(); 2289 __base::__map_.push_front(__pt); 2290 } 2291 } 2292 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2293 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2294 { // we can put the new buffers into the map, but don't shift things around 2295 // until all buffers are allocated. If we throw, we don't need to fix 2296 // anything up (any added buffers are undetectible) 2297 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1)) 2298 { 2299 if (__base::__map_.__front_spare() == 0) 2300 break; 2301 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2302 } 2303 for (; __nb > 0; --__nb, ++__back_capacity) 2304 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2305 // Done allocating, reorder capacity 2306 __base::__start_ += __back_capacity * __base::__block_size; 2307 for (; __back_capacity > 0; --__back_capacity) 2308 { 2309 pointer __pt = __base::__map_.back(); 2310 __base::__map_.pop_back(); 2311 __base::__map_.push_front(__pt); 2312 } 2313 } 2314 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2315 else 2316 { 2317 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty(); 2318 __split_buffer<pointer, typename __base::__pointer_allocator&> 2319 __buf(max<size_type>(2* __base::__map_.capacity(), 2320 __nb + __base::__map_.size()), 2321 0, __base::__map_.__alloc()); 2322#ifndef _LIBCPP_NO_EXCEPTIONS 2323 try 2324 { 2325#endif // _LIBCPP_NO_EXCEPTIONS 2326 for (; __nb > 0; --__nb) 2327 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2328#ifndef _LIBCPP_NO_EXCEPTIONS 2329 } 2330 catch (...) 2331 { 2332 for (typename __base::__map_pointer __i = __buf.begin(); 2333 __i != __buf.end(); ++__i) 2334 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2335 throw; 2336 } 2337#endif // _LIBCPP_NO_EXCEPTIONS 2338 for (; __back_capacity > 0; --__back_capacity) 2339 { 2340 __buf.push_back(__base::__map_.back()); 2341 __base::__map_.pop_back(); 2342 } 2343 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2344 __i != __base::__map_.end(); ++__i) 2345 __buf.push_back(*__i); 2346 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2347 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2348 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2349 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2350 __base::__start_ += __ds; 2351 } 2352} 2353 2354// Create back capacity for one block of elements. 2355// Strong guarantee. Either do it or don't touch anything. 2356template <class _Tp, class _Allocator> 2357void 2358deque<_Tp, _Allocator>::__add_back_capacity() 2359{ 2360 allocator_type& __a = __base::__alloc(); 2361 if (__front_spare() >= __base::__block_size) 2362 { 2363 __base::__start_ -= __base::__block_size; 2364 pointer __pt = __base::__map_.front(); 2365 __base::__map_.pop_front(); 2366 __base::__map_.push_back(__pt); 2367 } 2368 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2369 else if (__base::__map_.size() < __base::__map_.capacity()) 2370 { // we can put the new buffer into the map, but don't shift things around 2371 // until it is allocated. If we throw, we don't need to fix 2372 // anything up (any added buffers are undetectible) 2373 if (__base::__map_.__back_spare() != 0) 2374 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2375 else 2376 { 2377 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2378 // Done allocating, reorder capacity 2379 pointer __pt = __base::__map_.front(); 2380 __base::__map_.pop_front(); 2381 __base::__map_.push_back(__pt); 2382 } 2383 } 2384 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2385 else 2386 { 2387 __split_buffer<pointer, typename __base::__pointer_allocator&> 2388 __buf(max<size_type>(2* __base::__map_.capacity(), 1), 2389 __base::__map_.size(), 2390 __base::__map_.__alloc()); 2391#ifndef _LIBCPP_NO_EXCEPTIONS 2392 try 2393 { 2394#endif // _LIBCPP_NO_EXCEPTIONS 2395 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2396#ifndef _LIBCPP_NO_EXCEPTIONS 2397 } 2398 catch (...) 2399 { 2400 __alloc_traits::deallocate(__a, __buf.back(), __base::__block_size); 2401 throw; 2402 } 2403#endif // _LIBCPP_NO_EXCEPTIONS 2404 for (typename __base::__map_pointer __i = __base::__map_.end(); 2405 __i != __base::__map_.begin();) 2406 __buf.push_front(*--__i); 2407 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2408 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2409 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2410 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2411 } 2412} 2413 2414// Create back capacity for __n elements. 2415// Strong guarantee. Either do it or don't touch anything. 2416template <class _Tp, class _Allocator> 2417void 2418deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) 2419{ 2420 allocator_type& __a = __base::__alloc(); 2421 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2422 // Number of unused blocks at front: 2423 size_type __front_capacity = __front_spare() / __base::__block_size; 2424 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need 2425 __nb -= __front_capacity; // number of blocks need to allocate 2426 // If __nb == 0, then we have sufficient capacity. 2427 if (__nb == 0) 2428 { 2429 __base::__start_ -= __base::__block_size * __front_capacity; 2430 for (; __front_capacity > 0; --__front_capacity) 2431 { 2432 pointer __pt = __base::__map_.front(); 2433 __base::__map_.pop_front(); 2434 __base::__map_.push_back(__pt); 2435 } 2436 } 2437 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2438 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2439 { // we can put the new buffers into the map, but don't shift things around 2440 // until all buffers are allocated. If we throw, we don't need to fix 2441 // anything up (any added buffers are undetectible) 2442 for (; __nb > 0; --__nb) 2443 { 2444 if (__base::__map_.__back_spare() == 0) 2445 break; 2446 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2447 } 2448 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ += 2449 __base::__block_size - (__base::__map_.size() == 1)) 2450 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2451 // Done allocating, reorder capacity 2452 __base::__start_ -= __base::__block_size * __front_capacity; 2453 for (; __front_capacity > 0; --__front_capacity) 2454 { 2455 pointer __pt = __base::__map_.front(); 2456 __base::__map_.pop_front(); 2457 __base::__map_.push_back(__pt); 2458 } 2459 } 2460 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2461 else 2462 { 2463 size_type __ds = __front_capacity * __base::__block_size; 2464 __split_buffer<pointer, typename __base::__pointer_allocator&> 2465 __buf(max<size_type>(2* __base::__map_.capacity(), 2466 __nb + __base::__map_.size()), 2467 __base::__map_.size() - __front_capacity, 2468 __base::__map_.__alloc()); 2469#ifndef _LIBCPP_NO_EXCEPTIONS 2470 try 2471 { 2472#endif // _LIBCPP_NO_EXCEPTIONS 2473 for (; __nb > 0; --__nb) 2474 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2475#ifndef _LIBCPP_NO_EXCEPTIONS 2476 } 2477 catch (...) 2478 { 2479 for (typename __base::__map_pointer __i = __buf.begin(); 2480 __i != __buf.end(); ++__i) 2481 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2482 throw; 2483 } 2484#endif // _LIBCPP_NO_EXCEPTIONS 2485 for (; __front_capacity > 0; --__front_capacity) 2486 { 2487 __buf.push_back(__base::__map_.front()); 2488 __base::__map_.pop_front(); 2489 } 2490 for (typename __base::__map_pointer __i = __base::__map_.end(); 2491 __i != __base::__map_.begin();) 2492 __buf.push_front(*--__i); 2493 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2494 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2495 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2496 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2497 __base::__start_ -= __ds; 2498 } 2499} 2500 2501template <class _Tp, class _Allocator> 2502void 2503deque<_Tp, _Allocator>::pop_front() 2504{ 2505 allocator_type& __a = __base::__alloc(); 2506 __alloc_traits::destroy(__a, *(__base::__map_.begin() + 2507 __base::__start_ / __base::__block_size) + 2508 __base::__start_ % __base::__block_size); 2509 --__base::size(); 2510 if (++__base::__start_ >= 2 * __base::__block_size) 2511 { 2512 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2513 __base::__map_.pop_front(); 2514 __base::__start_ -= __base::__block_size; 2515 } 2516} 2517 2518template <class _Tp, class _Allocator> 2519void 2520deque<_Tp, _Allocator>::pop_back() 2521{ 2522 allocator_type& __a = __base::__alloc(); 2523 size_type __p = __base::size() + __base::__start_ - 1; 2524 __alloc_traits::destroy(__a, *(__base::__map_.begin() + 2525 __p / __base::__block_size) + 2526 __p % __base::__block_size); 2527 --__base::size(); 2528 if (__back_spare() >= 2 * __base::__block_size) 2529 { 2530 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2531 __base::__map_.pop_back(); 2532 } 2533} 2534 2535// move assign [__f, __l) to [__r, __r + (__l-__f)). 2536// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. 2537template <class _Tp, class _Allocator> 2538typename deque<_Tp, _Allocator>::iterator 2539deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, 2540 const_pointer& __vt) 2541{ 2542 // as if 2543 // for (; __f != __l; ++__f, ++__r) 2544 // *__r = _VSTD::move(*__f); 2545 difference_type __n = __l - __f; 2546 while (__n > 0) 2547 { 2548 pointer __fb = __f.__ptr_; 2549 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2550 difference_type __bs = __fe - __fb; 2551 if (__bs > __n) 2552 { 2553 __bs = __n; 2554 __fe = __fb + __bs; 2555 } 2556 if (__fb <= __vt && __vt < __fe) 2557 __vt = (const_iterator(__f.__m_iter_, __vt) -= __f - __r).__ptr_; 2558 __r = _VSTD::move(__fb, __fe, __r); 2559 __n -= __bs; 2560 __f += __bs; 2561 } 2562 return __r; 2563} 2564 2565// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. 2566// If __vt points into [__f, __l), then add (__r - __l) to __vt. 2567template <class _Tp, class _Allocator> 2568typename deque<_Tp, _Allocator>::iterator 2569deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, 2570 const_pointer& __vt) 2571{ 2572 // as if 2573 // while (__f != __l) 2574 // *--__r = _VSTD::move(*--__l); 2575 difference_type __n = __l - __f; 2576 while (__n > 0) 2577 { 2578 --__l; 2579 pointer __lb = *__l.__m_iter_; 2580 pointer __le = __l.__ptr_ + 1; 2581 difference_type __bs = __le - __lb; 2582 if (__bs > __n) 2583 { 2584 __bs = __n; 2585 __lb = __le - __bs; 2586 } 2587 if (__lb <= __vt && __vt < __le) 2588 __vt = (const_iterator(__l.__m_iter_, __vt) += __r - __l - 1).__ptr_; 2589 __r = _VSTD::move_backward(__lb, __le, __r); 2590 __n -= __bs; 2591 __l -= __bs - 1; 2592 } 2593 return __r; 2594} 2595 2596// move construct [__f, __l) to [__r, __r + (__l-__f)). 2597// If __vt points into [__f, __l), then add (__r - __f) to __vt. 2598template <class _Tp, class _Allocator> 2599void 2600deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, 2601 iterator __r, const_pointer& __vt) 2602{ 2603 allocator_type& __a = __base::__alloc(); 2604 // as if 2605 // for (; __f != __l; ++__r, ++__f, ++__base::size()) 2606 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f)); 2607 difference_type __n = __l - __f; 2608 while (__n > 0) 2609 { 2610 pointer __fb = __f.__ptr_; 2611 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2612 difference_type __bs = __fe - __fb; 2613 if (__bs > __n) 2614 { 2615 __bs = __n; 2616 __fe = __fb + __bs; 2617 } 2618 if (__fb <= __vt && __vt < __fe) 2619 __vt = (const_iterator(__f.__m_iter_, __vt) += __r - __f).__ptr_; 2620 for (; __fb != __fe; ++__fb, ++__r, ++__base::size()) 2621 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb)); 2622 __n -= __bs; 2623 __f += __bs; 2624 } 2625} 2626 2627// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. 2628// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. 2629template <class _Tp, class _Allocator> 2630void 2631deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l, 2632 iterator __r, const_pointer& __vt) 2633{ 2634 allocator_type& __a = __base::__alloc(); 2635 // as if 2636 // for (iterator __j = __l; __j != __f;) 2637 // { 2638 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j)); 2639 // --__base::__start_; 2640 // ++__base::size(); 2641 // } 2642 difference_type __n = __l - __f; 2643 while (__n > 0) 2644 { 2645 --__l; 2646 pointer __lb = *__l.__m_iter_; 2647 pointer __le = __l.__ptr_ + 1; 2648 difference_type __bs = __le - __lb; 2649 if (__bs > __n) 2650 { 2651 __bs = __n; 2652 __lb = __le - __bs; 2653 } 2654 if (__lb <= __vt && __vt < __le) 2655 __vt = (const_iterator(__l.__m_iter_, __vt) -= __l - __r + 1).__ptr_; 2656 while (__le != __lb) 2657 { 2658 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le)); 2659 --__base::__start_; 2660 ++__base::size(); 2661 } 2662 __n -= __bs; 2663 __l -= __bs - 1; 2664 } 2665} 2666 2667template <class _Tp, class _Allocator> 2668typename deque<_Tp, _Allocator>::iterator 2669deque<_Tp, _Allocator>::erase(const_iterator __f) 2670{ 2671 difference_type __n = 1; 2672 iterator __b = __base::begin(); 2673 difference_type __pos = __f - __b; 2674 iterator __p = __b + __pos; 2675 allocator_type& __a = __base::__alloc(); 2676 if (__pos < (__base::size() - 1) / 2) 2677 { // erase from front 2678 _VSTD::move_backward(__b, __p, _VSTD::next(__p)); 2679 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2680 --__base::size(); 2681 ++__base::__start_; 2682 if (__front_spare() >= 2 * __base::__block_size) 2683 { 2684 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2685 __base::__map_.pop_front(); 2686 __base::__start_ -= __base::__block_size; 2687 } 2688 } 2689 else 2690 { // erase from back 2691 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p); 2692 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2693 --__base::size(); 2694 if (__back_spare() >= 2 * __base::__block_size) 2695 { 2696 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2697 __base::__map_.pop_back(); 2698 } 2699 } 2700 return __base::begin() + __pos; 2701} 2702 2703template <class _Tp, class _Allocator> 2704typename deque<_Tp, _Allocator>::iterator 2705deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) 2706{ 2707 difference_type __n = __l - __f; 2708 iterator __b = __base::begin(); 2709 difference_type __pos = __f - __b; 2710 iterator __p = __b + __pos; 2711 if (__n > 0) 2712 { 2713 allocator_type& __a = __base::__alloc(); 2714 if (__pos < (__base::size() - __n) / 2) 2715 { // erase from front 2716 iterator __i = _VSTD::move_backward(__b, __p, __p + __n); 2717 for (; __b != __i; ++__b) 2718 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2719 __base::size() -= __n; 2720 __base::__start_ += __n; 2721 while (__front_spare() >= 2 * __base::__block_size) 2722 { 2723 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2724 __base::__map_.pop_front(); 2725 __base::__start_ -= __base::__block_size; 2726 } 2727 } 2728 else 2729 { // erase from back 2730 iterator __i = _VSTD::move(__p + __n, __base::end(), __p); 2731 for (iterator __e = __base::end(); __i != __e; ++__i) 2732 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2733 __base::size() -= __n; 2734 while (__back_spare() >= 2 * __base::__block_size) 2735 { 2736 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2737 __base::__map_.pop_back(); 2738 } 2739 } 2740 } 2741 return __base::begin() + __pos; 2742} 2743 2744template <class _Tp, class _Allocator> 2745void 2746deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) 2747{ 2748 iterator __e = __base::end(); 2749 difference_type __n = __e - __f; 2750 if (__n > 0) 2751 { 2752 allocator_type& __a = __base::__alloc(); 2753 iterator __b = __base::begin(); 2754 difference_type __pos = __f - __b; 2755 for (iterator __p = __b + __pos; __p != __e; ++__p) 2756 __alloc_traits::destroy(__a, _VSTD::addressof(*__p)); 2757 __base::size() -= __n; 2758 while (__back_spare() >= 2 * __base::__block_size) 2759 { 2760 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2761 __base::__map_.pop_back(); 2762 } 2763 } 2764} 2765 2766template <class _Tp, class _Allocator> 2767inline _LIBCPP_INLINE_VISIBILITY 2768void 2769deque<_Tp, _Allocator>::swap(deque& __c) 2770 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2771 __is_nothrow_swappable<allocator_type>::value) 2772{ 2773 __base::swap(__c); 2774} 2775 2776template <class _Tp, class _Allocator> 2777inline _LIBCPP_INLINE_VISIBILITY 2778void 2779deque<_Tp, _Allocator>::clear() _NOEXCEPT 2780{ 2781 __base::clear(); 2782} 2783 2784template <class _Tp, class _Allocator> 2785_LIBCPP_INLINE_VISIBILITY inline 2786bool 2787operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2788{ 2789 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); 2790 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2791} 2792 2793template <class _Tp, class _Allocator> 2794_LIBCPP_INLINE_VISIBILITY inline 2795bool 2796operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2797{ 2798 return !(__x == __y); 2799} 2800 2801template <class _Tp, class _Allocator> 2802_LIBCPP_INLINE_VISIBILITY inline 2803bool 2804operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2805{ 2806 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2807} 2808 2809template <class _Tp, class _Allocator> 2810_LIBCPP_INLINE_VISIBILITY inline 2811bool 2812operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2813{ 2814 return __y < __x; 2815} 2816 2817template <class _Tp, class _Allocator> 2818_LIBCPP_INLINE_VISIBILITY inline 2819bool 2820operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2821{ 2822 return !(__x < __y); 2823} 2824 2825template <class _Tp, class _Allocator> 2826_LIBCPP_INLINE_VISIBILITY inline 2827bool 2828operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2829{ 2830 return !(__y < __x); 2831} 2832 2833template <class _Tp, class _Allocator> 2834_LIBCPP_INLINE_VISIBILITY inline 2835void 2836swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) 2837 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2838{ 2839 __x.swap(__y); 2840} 2841 2842_LIBCPP_END_NAMESPACE_STD 2843 2844#endif // _LIBCPP_DEQUE 2845