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