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