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