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