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