1// -*- C++ -*- 2//===---------------------------- deque -----------------------------------===// 3// 4// The LLVM Compiler Infrastructure 5// 6// This file is dual licensed under the MIT and the University of Illinois Open 7// Source Licenses. See LICENSE.TXT for details. 8// 9//===----------------------------------------------------------------------===// 10 11#ifndef _LIBCPP_DEQUE 12#define _LIBCPP_DEQUE 13 14/* 15 deque synopsis 16 17namespace std 18{ 19 20template <class T, class Allocator = allocator<T> > 21class deque 22{ 23public: 24 // types: 25 typedef T value_type; 26 typedef Allocator allocator_type; 27 28 typedef typename allocator_type::reference reference; 29 typedef typename allocator_type::const_reference const_reference; 30 typedef implementation-defined iterator; 31 typedef implementation-defined const_iterator; 32 typedef typename allocator_type::size_type size_type; 33 typedef typename allocator_type::difference_type difference_type; 34 35 typedef typename allocator_type::pointer pointer; 36 typedef typename allocator_type::const_pointer const_pointer; 37 typedef std::reverse_iterator<iterator> reverse_iterator; 38 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 39 40 // construct/copy/destroy: 41 deque() noexcept(is_nothrow_default_constructible<allocator_type>::value); 42 explicit deque(const allocator_type& a); 43 explicit deque(size_type n); 44 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> void emplace_front(Args&&... args); 114 template <class... Args> void emplace_back(Args&&... args); 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 131template <class T, class Allocator> 132 bool operator==(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 133template <class T, class Allocator> 134 bool operator< (const deque<T,Allocator>& x, const deque<T,Allocator>& y); 135template <class T, class Allocator> 136 bool operator!=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 137template <class T, class Allocator> 138 bool operator> (const deque<T,Allocator>& x, const deque<T,Allocator>& y); 139template <class T, class Allocator> 140 bool operator>=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 141template <class T, class Allocator> 142 bool operator<=(const deque<T,Allocator>& x, const deque<T,Allocator>& y); 143 144// specialized algorithms: 145template <class T, class Allocator> 146 void swap(deque<T,Allocator>& x, deque<T,Allocator>& y) 147 noexcept(noexcept(x.swap(y))); 148 149} // std 150 151*/ 152 153#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 154#pragma GCC system_header 155#endif 156 157#include <__config> 158#include <__split_buffer> 159#include <type_traits> 160#include <initializer_list> 161#include <iterator> 162#include <algorithm> 163#include <stdexcept> 164 165#include <__undef_min_max> 166 167_LIBCPP_BEGIN_NAMESPACE_STD 168 169template <class _Tp, class _Allocator> class __deque_base; 170template <class _Tp, class _Allocator = allocator<_Tp> > class _LIBCPP_TYPE_VIS_ONLY deque; 171 172template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 173 class _DiffType, _DiffType _BlockSize> 174class _LIBCPP_TYPE_VIS_ONLY __deque_iterator; 175 176template <class _RAIter, 177 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 178__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 179copy(_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 184template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 185 class _OutputIterator> 186_OutputIterator 187copy(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 188 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 189 _OutputIterator __r); 190 191template <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> 194copy(__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 198template <class _RAIter, 199 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 200__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 201copy_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 206template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 207 class _OutputIterator> 208_OutputIterator 209copy_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 210 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 211 _OutputIterator __r); 212 213template <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> 216copy_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 220template <class _RAIter, 221 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 222__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 223move(_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 228template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 229 class _OutputIterator> 230_OutputIterator 231move(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 232 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 233 _OutputIterator __r); 234 235template <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> 238move(__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 242template <class _RAIter, 243 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 244__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 245move_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 250template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 251 class _OutputIterator> 252_OutputIterator 253move_backward(__deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __f, 254 __deque_iterator<_V1, _P1, _R1, _M1, _D1, _B1> __l, 255 _OutputIterator __r); 256 257template <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> 260move_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 264template <class _ValueType, class _DiffType> 265struct __deque_block_size { 266 static const _DiffType value = sizeof(_ValueType) < 256 ? 4096 / sizeof(_ValueType) : 16; 267}; 268 269template <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 > 279class _LIBCPP_TYPE_VIS_ONLY __deque_iterator 280{ 281 typedef _MapPointer __map_iterator; 282public: 283 typedef _Pointer pointer; 284 typedef _DiffType difference_type; 285private: 286 __map_iterator __m_iter_; 287 pointer __ptr_; 288 289 static const difference_type __block_size; 290public: 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 426private: 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_TYPE_VIS_ONLY deque; 432 template <class _Vp, class _Pp, class _Rp, class _MP, class _Dp, _Dp> 433 friend class _LIBCPP_TYPE_VIS_ONLY __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 536template <class _ValueType, class _Pointer, class _Reference, class _MapPointer, 537 class _DiffType, _DiffType _BlockSize> 538const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, 539 _DiffType, _BlockSize>::__block_size = 540 __deque_block_size<_ValueType, _DiffType>::value; 541 542// copy 543 544template <class _RAIter, 545 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 546__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 547copy(_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 574template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 575 class _OutputIterator> 576_OutputIterator 577copy(__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 602template <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> 605copy(__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 632template <class _RAIter, 633 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 634__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 635copy_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 662template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 663 class _OutputIterator> 664_OutputIterator 665copy_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 690template <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> 693copy_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 720template <class _RAIter, 721 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 722__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 723move(_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 750template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 751 class _OutputIterator> 752_OutputIterator 753move(__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 778template <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> 781move(__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 808template <class _RAIter, 809 class _V2, class _P2, class _R2, class _M2, class _D2, _D2 _B2> 810__deque_iterator<_V2, _P2, _R2, _M2, _D2, _B2> 811move_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 838template <class _V1, class _P1, class _R1, class _M1, class _D1, _D1 _B1, 839 class _OutputIterator> 840_OutputIterator 841move_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 866template <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> 869move_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 894template <bool> 895class __deque_base_common 896{ 897protected: 898 void __throw_length_error() const; 899 void __throw_out_of_range() const; 900}; 901 902template <bool __b> 903void 904__deque_base_common<__b>::__throw_length_error() const 905{ 906#ifndef _LIBCPP_NO_EXCEPTIONS 907 throw length_error("deque"); 908#endif 909} 910 911template <bool __b> 912void 913__deque_base_common<__b>::__throw_out_of_range() const 914{ 915#ifndef _LIBCPP_NO_EXCEPTIONS 916 throw out_of_range("deque"); 917#endif 918} 919 920template <class _Tp, class _Allocator> 921class __deque_base 922 : protected __deque_base_common<true> 923{ 924 __deque_base(const __deque_base& __c); 925 __deque_base& operator=(const __deque_base& __c); 926protected: 927 typedef _Tp value_type; 928 typedef _Allocator allocator_type; 929 typedef allocator_traits<allocator_type> __alloc_traits; 930 typedef value_type& reference; 931 typedef const value_type& const_reference; 932 typedef typename __alloc_traits::size_type size_type; 933 typedef typename __alloc_traits::difference_type difference_type; 934 typedef typename __alloc_traits::pointer pointer; 935 typedef typename __alloc_traits::const_pointer const_pointer; 936 937 static const difference_type __block_size; 938 939 typedef typename __rebind_alloc_helper<__alloc_traits, pointer>::type __pointer_allocator; 940 typedef allocator_traits<__pointer_allocator> __map_traits; 941 typedef typename __map_traits::pointer __map_pointer; 942 typedef typename __rebind_alloc_helper<__alloc_traits, const_pointer>::type __const_pointer_allocator; 943 typedef typename allocator_traits<__const_pointer_allocator>::const_pointer __map_const_pointer; 944 typedef __split_buffer<pointer, __pointer_allocator> __map; 945 946 typedef __deque_iterator<value_type, pointer, reference, __map_pointer, 947 difference_type> iterator; 948 typedef __deque_iterator<value_type, const_pointer, const_reference, __map_const_pointer, 949 difference_type> const_iterator; 950 951 __map __map_; 952 size_type __start_; 953 __compressed_pair<size_type, allocator_type> __size_; 954 955 iterator begin() _NOEXCEPT; 956 const_iterator begin() const _NOEXCEPT; 957 iterator end() _NOEXCEPT; 958 const_iterator end() const _NOEXCEPT; 959 960 _LIBCPP_INLINE_VISIBILITY size_type& size() {return __size_.first();} 961 _LIBCPP_INLINE_VISIBILITY 962 const size_type& size() const _NOEXCEPT {return __size_.first();} 963 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __size_.second();} 964 _LIBCPP_INLINE_VISIBILITY 965 const allocator_type& __alloc() const _NOEXCEPT {return __size_.second();} 966 967 _LIBCPP_INLINE_VISIBILITY 968 __deque_base() 969 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 970 _LIBCPP_INLINE_VISIBILITY 971 explicit __deque_base(const allocator_type& __a); 972public: 973 ~__deque_base(); 974 975#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 976 977 __deque_base(__deque_base&& __c) 978 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 979 __deque_base(__deque_base&& __c, const allocator_type& __a); 980 981#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 982 void swap(__deque_base& __c) 983#if _LIBCPP_STD_VER >= 14 984 _NOEXCEPT; 985#else 986 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 987 __is_nothrow_swappable<allocator_type>::value); 988#endif 989protected: 990 void clear() _NOEXCEPT; 991 992 bool __invariants() const; 993 994 _LIBCPP_INLINE_VISIBILITY 995 void __move_assign(__deque_base& __c) 996 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 997 is_nothrow_move_assignable<allocator_type>::value) 998 { 999 __map_ = _VSTD::move(__c.__map_); 1000 __start_ = __c.__start_; 1001 size() = __c.size(); 1002 __move_assign_alloc(__c); 1003 __c.__start_ = __c.size() = 0; 1004 } 1005 1006 _LIBCPP_INLINE_VISIBILITY 1007 void __move_assign_alloc(__deque_base& __c) 1008 _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value || 1009 is_nothrow_move_assignable<allocator_type>::value) 1010 {__move_assign_alloc(__c, integral_constant<bool, 1011 __alloc_traits::propagate_on_container_move_assignment::value>());} 1012 1013private: 1014 _LIBCPP_INLINE_VISIBILITY 1015 void __move_assign_alloc(__deque_base& __c, true_type) 1016 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1017 { 1018 __alloc() = _VSTD::move(__c.__alloc()); 1019 } 1020 1021 _LIBCPP_INLINE_VISIBILITY 1022 void __move_assign_alloc(__deque_base&, false_type) _NOEXCEPT 1023 {} 1024}; 1025 1026template <class _Tp, class _Allocator> 1027const typename __deque_base<_Tp, _Allocator>::difference_type 1028 __deque_base<_Tp, _Allocator>::__block_size = 1029 __deque_block_size<value_type, difference_type>::value; 1030 1031template <class _Tp, class _Allocator> 1032bool 1033__deque_base<_Tp, _Allocator>::__invariants() const 1034{ 1035 if (!__map_.__invariants()) 1036 return false; 1037 if (__map_.size() >= size_type(-1) / __block_size) 1038 return false; 1039 for (typename __map::const_iterator __i = __map_.begin(), __e = __map_.end(); 1040 __i != __e; ++__i) 1041 if (*__i == nullptr) 1042 return false; 1043 if (__map_.size() != 0) 1044 { 1045 if (size() >= __map_.size() * __block_size) 1046 return false; 1047 if (__start_ >= __map_.size() * __block_size - size()) 1048 return false; 1049 } 1050 else 1051 { 1052 if (size() != 0) 1053 return false; 1054 if (__start_ != 0) 1055 return false; 1056 } 1057 return true; 1058} 1059 1060template <class _Tp, class _Allocator> 1061typename __deque_base<_Tp, _Allocator>::iterator 1062__deque_base<_Tp, _Allocator>::begin() _NOEXCEPT 1063{ 1064 __map_pointer __mp = __map_.begin() + __start_ / __block_size; 1065 return iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); 1066} 1067 1068template <class _Tp, class _Allocator> 1069typename __deque_base<_Tp, _Allocator>::const_iterator 1070__deque_base<_Tp, _Allocator>::begin() const _NOEXCEPT 1071{ 1072 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __start_ / __block_size); 1073 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __start_ % __block_size); 1074} 1075 1076template <class _Tp, class _Allocator> 1077typename __deque_base<_Tp, _Allocator>::iterator 1078__deque_base<_Tp, _Allocator>::end() _NOEXCEPT 1079{ 1080 size_type __p = size() + __start_; 1081 __map_pointer __mp = __map_.begin() + __p / __block_size; 1082 return iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); 1083} 1084 1085template <class _Tp, class _Allocator> 1086typename __deque_base<_Tp, _Allocator>::const_iterator 1087__deque_base<_Tp, _Allocator>::end() const _NOEXCEPT 1088{ 1089 size_type __p = size() + __start_; 1090 __map_const_pointer __mp = static_cast<__map_const_pointer>(__map_.begin() + __p / __block_size); 1091 return const_iterator(__mp, __map_.empty() ? 0 : *__mp + __p % __block_size); 1092} 1093 1094template <class _Tp, class _Allocator> 1095inline 1096__deque_base<_Tp, _Allocator>::__deque_base() 1097 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1098 : __start_(0), __size_(0) {} 1099 1100template <class _Tp, class _Allocator> 1101inline 1102__deque_base<_Tp, _Allocator>::__deque_base(const allocator_type& __a) 1103 : __map_(__pointer_allocator(__a)), __start_(0), __size_(0, __a) {} 1104 1105template <class _Tp, class _Allocator> 1106__deque_base<_Tp, _Allocator>::~__deque_base() 1107{ 1108 clear(); 1109 typename __map::iterator __i = __map_.begin(); 1110 typename __map::iterator __e = __map_.end(); 1111 for (; __i != __e; ++__i) 1112 __alloc_traits::deallocate(__alloc(), *__i, __block_size); 1113} 1114 1115#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1116 1117template <class _Tp, class _Allocator> 1118__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c) 1119 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1120 : __map_(_VSTD::move(__c.__map_)), 1121 __start_(_VSTD::move(__c.__start_)), 1122 __size_(_VSTD::move(__c.__size_)) 1123{ 1124 __c.__start_ = 0; 1125 __c.size() = 0; 1126} 1127 1128template <class _Tp, class _Allocator> 1129__deque_base<_Tp, _Allocator>::__deque_base(__deque_base&& __c, const allocator_type& __a) 1130 : __map_(_VSTD::move(__c.__map_), __pointer_allocator(__a)), 1131 __start_(_VSTD::move(__c.__start_)), 1132 __size_(_VSTD::move(__c.size()), __a) 1133{ 1134 if (__a == __c.__alloc()) 1135 { 1136 __c.__start_ = 0; 1137 __c.size() = 0; 1138 } 1139 else 1140 { 1141 __map_.clear(); 1142 __start_ = 0; 1143 size() = 0; 1144 } 1145} 1146 1147#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1148 1149template <class _Tp, class _Allocator> 1150void 1151__deque_base<_Tp, _Allocator>::swap(__deque_base& __c) 1152#if _LIBCPP_STD_VER >= 14 1153 _NOEXCEPT 1154#else 1155 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1156 __is_nothrow_swappable<allocator_type>::value) 1157#endif 1158{ 1159 __map_.swap(__c.__map_); 1160 _VSTD::swap(__start_, __c.__start_); 1161 _VSTD::swap(size(), __c.size()); 1162 __swap_allocator(__alloc(), __c.__alloc()); 1163} 1164 1165template <class _Tp, class _Allocator> 1166void 1167__deque_base<_Tp, _Allocator>::clear() _NOEXCEPT 1168{ 1169 allocator_type& __a = __alloc(); 1170 for (iterator __i = begin(), __e = end(); __i != __e; ++__i) 1171 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 1172 size() = 0; 1173 while (__map_.size() > 2) 1174 { 1175 __alloc_traits::deallocate(__a, __map_.front(), __block_size); 1176 __map_.pop_front(); 1177 } 1178 switch (__map_.size()) 1179 { 1180 case 1: 1181 __start_ = __block_size / 2; 1182 break; 1183 case 2: 1184 __start_ = __block_size; 1185 break; 1186 } 1187} 1188 1189template <class _Tp, class _Allocator /*= allocator<_Tp>*/> 1190class _LIBCPP_TYPE_VIS_ONLY deque 1191 : private __deque_base<_Tp, _Allocator> 1192{ 1193public: 1194 // types: 1195 1196 typedef _Tp value_type; 1197 typedef _Allocator allocator_type; 1198 1199 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 1200 "Allocator::value_type must be same type as value_type"); 1201 1202 typedef __deque_base<value_type, allocator_type> __base; 1203 1204 typedef typename __base::__alloc_traits __alloc_traits; 1205 typedef typename __base::reference reference; 1206 typedef typename __base::const_reference const_reference; 1207 typedef typename __base::iterator iterator; 1208 typedef typename __base::const_iterator const_iterator; 1209 typedef typename __base::size_type size_type; 1210 typedef typename __base::difference_type difference_type; 1211 1212 typedef typename __base::pointer pointer; 1213 typedef typename __base::const_pointer const_pointer; 1214 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1215 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1216 1217 // construct/copy/destroy: 1218 _LIBCPP_INLINE_VISIBILITY 1219 deque() 1220 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 1221 {} 1222 _LIBCPP_INLINE_VISIBILITY explicit deque(const allocator_type& __a) : __base(__a) {} 1223 explicit deque(size_type __n); 1224#if _LIBCPP_STD_VER > 11 1225 explicit deque(size_type __n, const _Allocator& __a); 1226#endif 1227 deque(size_type __n, const value_type& __v); 1228 deque(size_type __n, const value_type& __v, const allocator_type& __a); 1229 template <class _InputIter> 1230 deque(_InputIter __f, _InputIter __l, 1231 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0); 1232 template <class _InputIter> 1233 deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1234 typename enable_if<__is_input_iterator<_InputIter>::value>::type* = 0); 1235 deque(const deque& __c); 1236 deque(const deque& __c, const allocator_type& __a); 1237#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1238 deque(initializer_list<value_type> __il); 1239 deque(initializer_list<value_type> __il, const allocator_type& __a); 1240#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1241 1242 deque& operator=(const deque& __c); 1243#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1244 _LIBCPP_INLINE_VISIBILITY 1245 deque& operator=(initializer_list<value_type> __il) {assign(__il); return *this;} 1246#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1247 1248#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1249 _LIBCPP_INLINE_VISIBILITY 1250 deque(deque&& __c) _NOEXCEPT_(is_nothrow_move_constructible<__base>::value); 1251 _LIBCPP_INLINE_VISIBILITY 1252 deque(deque&& __c, const allocator_type& __a); 1253 _LIBCPP_INLINE_VISIBILITY 1254 deque& operator=(deque&& __c) 1255 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1256 is_nothrow_move_assignable<allocator_type>::value); 1257#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1258 1259 template <class _InputIter> 1260 void assign(_InputIter __f, _InputIter __l, 1261 typename enable_if<__is_input_iterator<_InputIter>::value && 1262 !__is_random_access_iterator<_InputIter>::value>::type* = 0); 1263 template <class _RAIter> 1264 void assign(_RAIter __f, _RAIter __l, 1265 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type* = 0); 1266 void assign(size_type __n, const value_type& __v); 1267#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1268 _LIBCPP_INLINE_VISIBILITY 1269 void assign(initializer_list<value_type> __il) {assign(__il.begin(), __il.end());} 1270#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1271 1272 _LIBCPP_INLINE_VISIBILITY 1273 allocator_type get_allocator() const _NOEXCEPT; 1274 1275 // iterators: 1276 1277 _LIBCPP_INLINE_VISIBILITY 1278 iterator begin() _NOEXCEPT {return __base::begin();} 1279 _LIBCPP_INLINE_VISIBILITY 1280 const_iterator begin() const _NOEXCEPT {return __base::begin();} 1281 _LIBCPP_INLINE_VISIBILITY 1282 iterator end() _NOEXCEPT {return __base::end();} 1283 _LIBCPP_INLINE_VISIBILITY 1284 const_iterator end() const _NOEXCEPT {return __base::end();} 1285 1286 _LIBCPP_INLINE_VISIBILITY 1287 reverse_iterator rbegin() _NOEXCEPT 1288 {return reverse_iterator(__base::end());} 1289 _LIBCPP_INLINE_VISIBILITY 1290 const_reverse_iterator rbegin() const _NOEXCEPT 1291 {return const_reverse_iterator(__base::end());} 1292 _LIBCPP_INLINE_VISIBILITY 1293 reverse_iterator rend() _NOEXCEPT 1294 {return reverse_iterator(__base::begin());} 1295 _LIBCPP_INLINE_VISIBILITY 1296 const_reverse_iterator rend() const _NOEXCEPT 1297 {return const_reverse_iterator(__base::begin());} 1298 1299 _LIBCPP_INLINE_VISIBILITY 1300 const_iterator cbegin() const _NOEXCEPT 1301 {return __base::begin();} 1302 _LIBCPP_INLINE_VISIBILITY 1303 const_iterator cend() const _NOEXCEPT 1304 {return __base::end();} 1305 _LIBCPP_INLINE_VISIBILITY 1306 const_reverse_iterator crbegin() const _NOEXCEPT 1307 {return const_reverse_iterator(__base::end());} 1308 _LIBCPP_INLINE_VISIBILITY 1309 const_reverse_iterator crend() const _NOEXCEPT 1310 {return const_reverse_iterator(__base::begin());} 1311 1312 // capacity: 1313 _LIBCPP_INLINE_VISIBILITY 1314 size_type size() const _NOEXCEPT {return __base::size();} 1315 _LIBCPP_INLINE_VISIBILITY 1316 size_type max_size() const _NOEXCEPT 1317 {return __alloc_traits::max_size(__base::__alloc());} 1318 void resize(size_type __n); 1319 void resize(size_type __n, const value_type& __v); 1320 void shrink_to_fit() _NOEXCEPT; 1321 _LIBCPP_INLINE_VISIBILITY 1322 bool empty() const _NOEXCEPT {return __base::size() == 0;} 1323 1324 // element access: 1325 _LIBCPP_INLINE_VISIBILITY 1326 reference operator[](size_type __i); 1327 _LIBCPP_INLINE_VISIBILITY 1328 const_reference operator[](size_type __i) const; 1329 _LIBCPP_INLINE_VISIBILITY 1330 reference at(size_type __i); 1331 _LIBCPP_INLINE_VISIBILITY 1332 const_reference at(size_type __i) const; 1333 _LIBCPP_INLINE_VISIBILITY 1334 reference front(); 1335 _LIBCPP_INLINE_VISIBILITY 1336 const_reference front() const; 1337 _LIBCPP_INLINE_VISIBILITY 1338 reference back(); 1339 _LIBCPP_INLINE_VISIBILITY 1340 const_reference back() const; 1341 1342 // 23.2.2.3 modifiers: 1343 void push_front(const value_type& __v); 1344 void push_back(const value_type& __v); 1345#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1346#ifndef _LIBCPP_HAS_NO_VARIADICS 1347 template <class... _Args> void emplace_front(_Args&&... __args); 1348 template <class... _Args> void emplace_back(_Args&&... __args); 1349 template <class... _Args> iterator emplace(const_iterator __p, _Args&&... __args); 1350#endif // _LIBCPP_HAS_NO_VARIADICS 1351 void push_front(value_type&& __v); 1352 void push_back(value_type&& __v); 1353 iterator insert(const_iterator __p, value_type&& __v); 1354#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1355 iterator insert(const_iterator __p, const value_type& __v); 1356 iterator insert(const_iterator __p, size_type __n, const value_type& __v); 1357 template <class _InputIter> 1358 iterator insert(const_iterator __p, _InputIter __f, _InputIter __l, 1359 typename enable_if<__is_input_iterator<_InputIter>::value 1360 &&!__is_forward_iterator<_InputIter>::value>::type* = 0); 1361 template <class _ForwardIterator> 1362 iterator insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 1363 typename enable_if<__is_forward_iterator<_ForwardIterator>::value 1364 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type* = 0); 1365 template <class _BiIter> 1366 iterator insert(const_iterator __p, _BiIter __f, _BiIter __l, 1367 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type* = 0); 1368#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1369 _LIBCPP_INLINE_VISIBILITY 1370 iterator insert(const_iterator __p, initializer_list<value_type> __il) 1371 {return insert(__p, __il.begin(), __il.end());} 1372#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1373 void pop_front(); 1374 void pop_back(); 1375 iterator erase(const_iterator __p); 1376 iterator erase(const_iterator __f, const_iterator __l); 1377 1378 _LIBCPP_INLINE_VISIBILITY 1379 void swap(deque& __c) 1380#if _LIBCPP_STD_VER >= 14 1381 _NOEXCEPT; 1382#else 1383 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1384 __is_nothrow_swappable<allocator_type>::value); 1385#endif 1386 _LIBCPP_INLINE_VISIBILITY 1387 void clear() _NOEXCEPT; 1388 1389 _LIBCPP_INLINE_VISIBILITY 1390 bool __invariants() const {return __base::__invariants();} 1391private: 1392 typedef typename __base::__map_const_pointer __map_const_pointer; 1393 1394 _LIBCPP_INLINE_VISIBILITY 1395 static size_type __recommend_blocks(size_type __n) 1396 { 1397 return __n / __base::__block_size + (__n % __base::__block_size != 0); 1398 } 1399 _LIBCPP_INLINE_VISIBILITY 1400 size_type __capacity() const 1401 { 1402 return __base::__map_.size() == 0 ? 0 : __base::__map_.size() * __base::__block_size - 1; 1403 } 1404 _LIBCPP_INLINE_VISIBILITY 1405 size_type __front_spare() const 1406 { 1407 return __base::__start_; 1408 } 1409 _LIBCPP_INLINE_VISIBILITY 1410 size_type __back_spare() const 1411 { 1412 return __capacity() - (__base::__start_ + __base::size()); 1413 } 1414 1415 template <class _InpIter> 1416 void __append(_InpIter __f, _InpIter __l, 1417 typename enable_if<__is_input_iterator<_InpIter>::value && 1418 !__is_forward_iterator<_InpIter>::value>::type* = 0); 1419 template <class _ForIter> 1420 void __append(_ForIter __f, _ForIter __l, 1421 typename enable_if<__is_forward_iterator<_ForIter>::value>::type* = 0); 1422 void __append(size_type __n); 1423 void __append(size_type __n, const value_type& __v); 1424 void __erase_to_end(const_iterator __f); 1425 void __add_front_capacity(); 1426 void __add_front_capacity(size_type __n); 1427 void __add_back_capacity(); 1428 void __add_back_capacity(size_type __n); 1429 iterator __move_and_check(iterator __f, iterator __l, iterator __r, 1430 const_pointer& __vt); 1431 iterator __move_backward_and_check(iterator __f, iterator __l, iterator __r, 1432 const_pointer& __vt); 1433 void __move_construct_and_check(iterator __f, iterator __l, 1434 iterator __r, const_pointer& __vt); 1435 void __move_construct_backward_and_check(iterator __f, iterator __l, 1436 iterator __r, const_pointer& __vt); 1437 1438 _LIBCPP_INLINE_VISIBILITY 1439 void __copy_assign_alloc(const deque& __c) 1440 {__copy_assign_alloc(__c, integral_constant<bool, 1441 __alloc_traits::propagate_on_container_copy_assignment::value>());} 1442 1443 _LIBCPP_INLINE_VISIBILITY 1444 void __copy_assign_alloc(const deque& __c, true_type) 1445 { 1446 if (__base::__alloc() != __c.__alloc()) 1447 { 1448 clear(); 1449 shrink_to_fit(); 1450 } 1451 __base::__alloc() = __c.__alloc(); 1452 __base::__map_.__alloc() = __c.__map_.__alloc(); 1453 } 1454 1455 _LIBCPP_INLINE_VISIBILITY 1456 void __copy_assign_alloc(const deque&, false_type) 1457 {} 1458 1459 void __move_assign(deque& __c, true_type) 1460 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 1461 void __move_assign(deque& __c, false_type); 1462}; 1463 1464template <class _Tp, class _Allocator> 1465deque<_Tp, _Allocator>::deque(size_type __n) 1466{ 1467 if (__n > 0) 1468 __append(__n); 1469} 1470 1471#if _LIBCPP_STD_VER > 11 1472template <class _Tp, class _Allocator> 1473deque<_Tp, _Allocator>::deque(size_type __n, const _Allocator& __a) 1474 : __base(__a) 1475{ 1476 if (__n > 0) 1477 __append(__n); 1478} 1479#endif 1480 1481template <class _Tp, class _Allocator> 1482deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v) 1483{ 1484 if (__n > 0) 1485 __append(__n, __v); 1486} 1487 1488template <class _Tp, class _Allocator> 1489deque<_Tp, _Allocator>::deque(size_type __n, const value_type& __v, const allocator_type& __a) 1490 : __base(__a) 1491{ 1492 if (__n > 0) 1493 __append(__n, __v); 1494} 1495 1496template <class _Tp, class _Allocator> 1497template <class _InputIter> 1498deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, 1499 typename enable_if<__is_input_iterator<_InputIter>::value>::type*) 1500{ 1501 __append(__f, __l); 1502} 1503 1504template <class _Tp, class _Allocator> 1505template <class _InputIter> 1506deque<_Tp, _Allocator>::deque(_InputIter __f, _InputIter __l, const allocator_type& __a, 1507 typename enable_if<__is_input_iterator<_InputIter>::value>::type*) 1508 : __base(__a) 1509{ 1510 __append(__f, __l); 1511} 1512 1513template <class _Tp, class _Allocator> 1514deque<_Tp, _Allocator>::deque(const deque& __c) 1515 : __base(__alloc_traits::select_on_container_copy_construction(__c.__alloc())) 1516{ 1517 __append(__c.begin(), __c.end()); 1518} 1519 1520template <class _Tp, class _Allocator> 1521deque<_Tp, _Allocator>::deque(const deque& __c, const allocator_type& __a) 1522 : __base(__a) 1523{ 1524 __append(__c.begin(), __c.end()); 1525} 1526 1527#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1528 1529template <class _Tp, class _Allocator> 1530deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il) 1531{ 1532 __append(__il.begin(), __il.end()); 1533} 1534 1535template <class _Tp, class _Allocator> 1536deque<_Tp, _Allocator>::deque(initializer_list<value_type> __il, const allocator_type& __a) 1537 : __base(__a) 1538{ 1539 __append(__il.begin(), __il.end()); 1540} 1541 1542#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1543 1544template <class _Tp, class _Allocator> 1545deque<_Tp, _Allocator>& 1546deque<_Tp, _Allocator>::operator=(const deque& __c) 1547{ 1548 if (this != &__c) 1549 { 1550 __copy_assign_alloc(__c); 1551 assign(__c.begin(), __c.end()); 1552 } 1553 return *this; 1554} 1555 1556#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1557 1558template <class _Tp, class _Allocator> 1559inline 1560deque<_Tp, _Allocator>::deque(deque&& __c) 1561 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value) 1562 : __base(_VSTD::move(__c)) 1563{ 1564} 1565 1566template <class _Tp, class _Allocator> 1567inline 1568deque<_Tp, _Allocator>::deque(deque&& __c, const allocator_type& __a) 1569 : __base(_VSTD::move(__c), __a) 1570{ 1571 if (__a != __c.__alloc()) 1572 { 1573 typedef move_iterator<iterator> _Ip; 1574 assign(_Ip(__c.begin()), _Ip(__c.end())); 1575 } 1576} 1577 1578template <class _Tp, class _Allocator> 1579inline 1580deque<_Tp, _Allocator>& 1581deque<_Tp, _Allocator>::operator=(deque&& __c) 1582 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value && 1583 is_nothrow_move_assignable<allocator_type>::value) 1584{ 1585 __move_assign(__c, integral_constant<bool, 1586 __alloc_traits::propagate_on_container_move_assignment::value>()); 1587 return *this; 1588} 1589 1590template <class _Tp, class _Allocator> 1591void 1592deque<_Tp, _Allocator>::__move_assign(deque& __c, false_type) 1593{ 1594 if (__base::__alloc() != __c.__alloc()) 1595 { 1596 typedef move_iterator<iterator> _Ip; 1597 assign(_Ip(__c.begin()), _Ip(__c.end())); 1598 } 1599 else 1600 __move_assign(__c, true_type()); 1601} 1602 1603template <class _Tp, class _Allocator> 1604void 1605deque<_Tp, _Allocator>::__move_assign(deque& __c, true_type) 1606 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1607{ 1608 clear(); 1609 shrink_to_fit(); 1610 __base::__move_assign(__c); 1611} 1612 1613#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1614 1615template <class _Tp, class _Allocator> 1616template <class _InputIter> 1617void 1618deque<_Tp, _Allocator>::assign(_InputIter __f, _InputIter __l, 1619 typename enable_if<__is_input_iterator<_InputIter>::value && 1620 !__is_random_access_iterator<_InputIter>::value>::type*) 1621{ 1622 iterator __i = __base::begin(); 1623 iterator __e = __base::end(); 1624 for (; __f != __l && __i != __e; ++__f, (void) ++__i) 1625 *__i = *__f; 1626 if (__f != __l) 1627 __append(__f, __l); 1628 else 1629 __erase_to_end(__i); 1630} 1631 1632template <class _Tp, class _Allocator> 1633template <class _RAIter> 1634void 1635deque<_Tp, _Allocator>::assign(_RAIter __f, _RAIter __l, 1636 typename enable_if<__is_random_access_iterator<_RAIter>::value>::type*) 1637{ 1638 if (static_cast<size_type>(__l - __f) > __base::size()) 1639 { 1640 _RAIter __m = __f + __base::size(); 1641 _VSTD::copy(__f, __m, __base::begin()); 1642 __append(__m, __l); 1643 } 1644 else 1645 __erase_to_end(_VSTD::copy(__f, __l, __base::begin())); 1646} 1647 1648template <class _Tp, class _Allocator> 1649void 1650deque<_Tp, _Allocator>::assign(size_type __n, const value_type& __v) 1651{ 1652 if (__n > __base::size()) 1653 { 1654 _VSTD::fill_n(__base::begin(), __base::size(), __v); 1655 __n -= __base::size(); 1656 __append(__n, __v); 1657 } 1658 else 1659 __erase_to_end(_VSTD::fill_n(__base::begin(), __n, __v)); 1660} 1661 1662template <class _Tp, class _Allocator> 1663inline 1664_Allocator 1665deque<_Tp, _Allocator>::get_allocator() const _NOEXCEPT 1666{ 1667 return __base::__alloc(); 1668} 1669 1670template <class _Tp, class _Allocator> 1671void 1672deque<_Tp, _Allocator>::resize(size_type __n) 1673{ 1674 if (__n > __base::size()) 1675 __append(__n - __base::size()); 1676 else if (__n < __base::size()) 1677 __erase_to_end(__base::begin() + __n); 1678} 1679 1680template <class _Tp, class _Allocator> 1681void 1682deque<_Tp, _Allocator>::resize(size_type __n, const value_type& __v) 1683{ 1684 if (__n > __base::size()) 1685 __append(__n - __base::size(), __v); 1686 else if (__n < __base::size()) 1687 __erase_to_end(__base::begin() + __n); 1688} 1689 1690template <class _Tp, class _Allocator> 1691void 1692deque<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1693{ 1694 allocator_type& __a = __base::__alloc(); 1695 if (empty()) 1696 { 1697 while (__base::__map_.size() > 0) 1698 { 1699 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 1700 __base::__map_.pop_back(); 1701 } 1702 __base::__start_ = 0; 1703 } 1704 else 1705 { 1706 if (__front_spare() >= __base::__block_size) 1707 { 1708 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 1709 __base::__map_.pop_front(); 1710 __base::__start_ -= __base::__block_size; 1711 } 1712 if (__back_spare() >= __base::__block_size) 1713 { 1714 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 1715 __base::__map_.pop_back(); 1716 } 1717 } 1718 __base::__map_.shrink_to_fit(); 1719} 1720 1721template <class _Tp, class _Allocator> 1722inline 1723typename deque<_Tp, _Allocator>::reference 1724deque<_Tp, _Allocator>::operator[](size_type __i) 1725{ 1726 size_type __p = __base::__start_ + __i; 1727 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1728} 1729 1730template <class _Tp, class _Allocator> 1731inline 1732typename deque<_Tp, _Allocator>::const_reference 1733deque<_Tp, _Allocator>::operator[](size_type __i) const 1734{ 1735 size_type __p = __base::__start_ + __i; 1736 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1737} 1738 1739template <class _Tp, class _Allocator> 1740inline 1741typename deque<_Tp, _Allocator>::reference 1742deque<_Tp, _Allocator>::at(size_type __i) 1743{ 1744 if (__i >= __base::size()) 1745 __base::__throw_out_of_range(); 1746 size_type __p = __base::__start_ + __i; 1747 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1748} 1749 1750template <class _Tp, class _Allocator> 1751inline 1752typename deque<_Tp, _Allocator>::const_reference 1753deque<_Tp, _Allocator>::at(size_type __i) const 1754{ 1755 if (__i >= __base::size()) 1756 __base::__throw_out_of_range(); 1757 size_type __p = __base::__start_ + __i; 1758 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1759} 1760 1761template <class _Tp, class _Allocator> 1762inline 1763typename deque<_Tp, _Allocator>::reference 1764deque<_Tp, _Allocator>::front() 1765{ 1766 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1767 + __base::__start_ % __base::__block_size); 1768} 1769 1770template <class _Tp, class _Allocator> 1771inline 1772typename deque<_Tp, _Allocator>::const_reference 1773deque<_Tp, _Allocator>::front() const 1774{ 1775 return *(*(__base::__map_.begin() + __base::__start_ / __base::__block_size) 1776 + __base::__start_ % __base::__block_size); 1777} 1778 1779template <class _Tp, class _Allocator> 1780inline 1781typename deque<_Tp, _Allocator>::reference 1782deque<_Tp, _Allocator>::back() 1783{ 1784 size_type __p = __base::size() + __base::__start_ - 1; 1785 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1786} 1787 1788template <class _Tp, class _Allocator> 1789inline 1790typename deque<_Tp, _Allocator>::const_reference 1791deque<_Tp, _Allocator>::back() const 1792{ 1793 size_type __p = __base::size() + __base::__start_ - 1; 1794 return *(*(__base::__map_.begin() + __p / __base::__block_size) + __p % __base::__block_size); 1795} 1796 1797template <class _Tp, class _Allocator> 1798void 1799deque<_Tp, _Allocator>::push_back(const value_type& __v) 1800{ 1801 allocator_type& __a = __base::__alloc(); 1802 if (__back_spare() == 0) 1803 __add_back_capacity(); 1804 // __back_spare() >= 1 1805 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 1806 ++__base::size(); 1807} 1808 1809#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1810 1811template <class _Tp, class _Allocator> 1812void 1813deque<_Tp, _Allocator>::push_back(value_type&& __v) 1814{ 1815 allocator_type& __a = __base::__alloc(); 1816 if (__back_spare() == 0) 1817 __add_back_capacity(); 1818 // __back_spare() >= 1 1819 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 1820 ++__base::size(); 1821} 1822 1823#ifndef _LIBCPP_HAS_NO_VARIADICS 1824 1825template <class _Tp, class _Allocator> 1826template <class... _Args> 1827void 1828deque<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1829{ 1830 allocator_type& __a = __base::__alloc(); 1831 if (__back_spare() == 0) 1832 __add_back_capacity(); 1833 // __back_spare() >= 1 1834 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 1835 ++__base::size(); 1836} 1837 1838#endif // _LIBCPP_HAS_NO_VARIADICS 1839#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1840 1841template <class _Tp, class _Allocator> 1842void 1843deque<_Tp, _Allocator>::push_front(const value_type& __v) 1844{ 1845 allocator_type& __a = __base::__alloc(); 1846 if (__front_spare() == 0) 1847 __add_front_capacity(); 1848 // __front_spare() >= 1 1849 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 1850 --__base::__start_; 1851 ++__base::size(); 1852} 1853 1854#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1855 1856template <class _Tp, class _Allocator> 1857void 1858deque<_Tp, _Allocator>::push_front(value_type&& __v) 1859{ 1860 allocator_type& __a = __base::__alloc(); 1861 if (__front_spare() == 0) 1862 __add_front_capacity(); 1863 // __front_spare() >= 1 1864 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 1865 --__base::__start_; 1866 ++__base::size(); 1867} 1868 1869#ifndef _LIBCPP_HAS_NO_VARIADICS 1870 1871template <class _Tp, class _Allocator> 1872template <class... _Args> 1873void 1874deque<_Tp, _Allocator>::emplace_front(_Args&&... __args) 1875{ 1876 allocator_type& __a = __base::__alloc(); 1877 if (__front_spare() == 0) 1878 __add_front_capacity(); 1879 // __front_spare() >= 1 1880 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 1881 --__base::__start_; 1882 ++__base::size(); 1883} 1884 1885#endif // _LIBCPP_HAS_NO_VARIADICS 1886#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1887 1888template <class _Tp, class _Allocator> 1889typename deque<_Tp, _Allocator>::iterator 1890deque<_Tp, _Allocator>::insert(const_iterator __p, const value_type& __v) 1891{ 1892 size_type __pos = __p - __base::begin(); 1893 size_type __to_end = __base::size() - __pos; 1894 allocator_type& __a = __base::__alloc(); 1895 if (__pos < __to_end) 1896 { // insert by shifting things backward 1897 if (__front_spare() == 0) 1898 __add_front_capacity(); 1899 // __front_spare() >= 1 1900 if (__pos == 0) 1901 { 1902 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), __v); 1903 --__base::__start_; 1904 ++__base::size(); 1905 } 1906 else 1907 { 1908 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 1909 iterator __b = __base::begin(); 1910 iterator __bm1 = _VSTD::prev(__b); 1911 if (__vt == pointer_traits<const_pointer>::pointer_to(*__b)) 1912 __vt = pointer_traits<const_pointer>::pointer_to(*__bm1); 1913 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 1914 --__base::__start_; 1915 ++__base::size(); 1916 if (__pos > 1) 1917 __b = __move_and_check(_VSTD::next(__b), __b + __pos, __b, __vt); 1918 *__b = *__vt; 1919 } 1920 } 1921 else 1922 { // insert by shifting things forward 1923 if (__back_spare() == 0) 1924 __add_back_capacity(); 1925 // __back_capacity >= 1 1926 size_type __de = __base::size() - __pos; 1927 if (__de == 0) 1928 { 1929 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), __v); 1930 ++__base::size(); 1931 } 1932 else 1933 { 1934 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 1935 iterator __e = __base::end(); 1936 iterator __em1 = _VSTD::prev(__e); 1937 if (__vt == pointer_traits<const_pointer>::pointer_to(*__em1)) 1938 __vt = pointer_traits<const_pointer>::pointer_to(*__e); 1939 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 1940 ++__base::size(); 1941 if (__de > 1) 1942 __e = __move_backward_and_check(__e - __de, __em1, __e, __vt); 1943 *--__e = *__vt; 1944 } 1945 } 1946 return __base::begin() + __pos; 1947} 1948 1949#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1950 1951template <class _Tp, class _Allocator> 1952typename deque<_Tp, _Allocator>::iterator 1953deque<_Tp, _Allocator>::insert(const_iterator __p, value_type&& __v) 1954{ 1955 size_type __pos = __p - __base::begin(); 1956 size_type __to_end = __base::size() - __pos; 1957 allocator_type& __a = __base::__alloc(); 1958 if (__pos < __to_end) 1959 { // insert by shifting things backward 1960 if (__front_spare() == 0) 1961 __add_front_capacity(); 1962 // __front_spare() >= 1 1963 if (__pos == 0) 1964 { 1965 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::move(__v)); 1966 --__base::__start_; 1967 ++__base::size(); 1968 } 1969 else 1970 { 1971 iterator __b = __base::begin(); 1972 iterator __bm1 = _VSTD::prev(__b); 1973 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 1974 --__base::__start_; 1975 ++__base::size(); 1976 if (__pos > 1) 1977 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 1978 *__b = _VSTD::move(__v); 1979 } 1980 } 1981 else 1982 { // insert by shifting things forward 1983 if (__back_spare() == 0) 1984 __add_back_capacity(); 1985 // __back_capacity >= 1 1986 size_type __de = __base::size() - __pos; 1987 if (__de == 0) 1988 { 1989 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::move(__v)); 1990 ++__base::size(); 1991 } 1992 else 1993 { 1994 iterator __e = __base::end(); 1995 iterator __em1 = _VSTD::prev(__e); 1996 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 1997 ++__base::size(); 1998 if (__de > 1) 1999 __e = _VSTD::move_backward(__e - __de, __em1, __e); 2000 *--__e = _VSTD::move(__v); 2001 } 2002 } 2003 return __base::begin() + __pos; 2004} 2005 2006#ifndef _LIBCPP_HAS_NO_VARIADICS 2007 2008template <class _Tp, class _Allocator> 2009template <class... _Args> 2010typename deque<_Tp, _Allocator>::iterator 2011deque<_Tp, _Allocator>::emplace(const_iterator __p, _Args&&... __args) 2012{ 2013 size_type __pos = __p - __base::begin(); 2014 size_type __to_end = __base::size() - __pos; 2015 allocator_type& __a = __base::__alloc(); 2016 if (__pos < __to_end) 2017 { // insert by shifting things backward 2018 if (__front_spare() == 0) 2019 __add_front_capacity(); 2020 // __front_spare() >= 1 2021 if (__pos == 0) 2022 { 2023 __alloc_traits::construct(__a, _VSTD::addressof(*--__base::begin()), _VSTD::forward<_Args>(__args)...); 2024 --__base::__start_; 2025 ++__base::size(); 2026 } 2027 else 2028 { 2029 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 2030 iterator __b = __base::begin(); 2031 iterator __bm1 = _VSTD::prev(__b); 2032 __alloc_traits::construct(__a, _VSTD::addressof(*__bm1), _VSTD::move(*__b)); 2033 --__base::__start_; 2034 ++__base::size(); 2035 if (__pos > 1) 2036 __b = _VSTD::move(_VSTD::next(__b), __b + __pos, __b); 2037 *__b = _VSTD::move(__tmp.get()); 2038 } 2039 } 2040 else 2041 { // insert by shifting things forward 2042 if (__back_spare() == 0) 2043 __add_back_capacity(); 2044 // __back_capacity >= 1 2045 size_type __de = __base::size() - __pos; 2046 if (__de == 0) 2047 { 2048 __alloc_traits::construct(__a, _VSTD::addressof(*__base::end()), _VSTD::forward<_Args>(__args)...); 2049 ++__base::size(); 2050 } 2051 else 2052 { 2053 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 2054 iterator __e = __base::end(); 2055 iterator __em1 = _VSTD::prev(__e); 2056 __alloc_traits::construct(__a, _VSTD::addressof(*__e), _VSTD::move(*__em1)); 2057 ++__base::size(); 2058 if (__de > 1) 2059 __e = _VSTD::move_backward(__e - __de, __em1, __e); 2060 *--__e = _VSTD::move(__tmp.get()); 2061 } 2062 } 2063 return __base::begin() + __pos; 2064} 2065 2066#endif // _LIBCPP_HAS_NO_VARIADICS 2067#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2068 2069template <class _Tp, class _Allocator> 2070typename deque<_Tp, _Allocator>::iterator 2071deque<_Tp, _Allocator>::insert(const_iterator __p, size_type __n, const value_type& __v) 2072{ 2073 size_type __pos = __p - __base::begin(); 2074 size_type __to_end = __base::size() - __pos; 2075 allocator_type& __a = __base::__alloc(); 2076 if (__pos < __to_end) 2077 { // insert by shifting things backward 2078 if (__n > __front_spare()) 2079 __add_front_capacity(__n - __front_spare()); 2080 // __n <= __front_spare() 2081 iterator __old_begin = __base::begin(); 2082 iterator __i = __old_begin; 2083 if (__n > __pos) 2084 { 2085 for (size_type __m = __n - __pos; __m; --__m, --__base::__start_, ++__base::size()) 2086 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), __v); 2087 __n = __pos; 2088 } 2089 if (__n > 0) 2090 { 2091 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2092 iterator __obn = __old_begin + __n; 2093 __move_construct_backward_and_check(__old_begin, __obn, __i, __vt); 2094 if (__n < __pos) 2095 __old_begin = __move_and_check(__obn, __old_begin + __pos, __old_begin, __vt); 2096 _VSTD::fill_n(__old_begin, __n, *__vt); 2097 } 2098 } 2099 else 2100 { // insert by shifting things forward 2101 size_type __back_capacity = __back_spare(); 2102 if (__n > __back_capacity) 2103 __add_back_capacity(__n - __back_capacity); 2104 // __n <= __back_capacity 2105 iterator __old_end = __base::end(); 2106 iterator __i = __old_end; 2107 size_type __de = __base::size() - __pos; 2108 if (__n > __de) 2109 { 2110 for (size_type __m = __n - __de; __m; --__m, ++__i, ++__base::size()) 2111 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2112 __n = __de; 2113 } 2114 if (__n > 0) 2115 { 2116 const_pointer __vt = pointer_traits<const_pointer>::pointer_to(__v); 2117 iterator __oen = __old_end - __n; 2118 __move_construct_and_check(__oen, __old_end, __i, __vt); 2119 if (__n < __de) 2120 __old_end = __move_backward_and_check(__old_end - __de, __oen, __old_end, __vt); 2121 _VSTD::fill_n(__old_end - __n, __n, *__vt); 2122 } 2123 } 2124 return __base::begin() + __pos; 2125} 2126 2127template <class _Tp, class _Allocator> 2128template <class _InputIter> 2129typename deque<_Tp, _Allocator>::iterator 2130deque<_Tp, _Allocator>::insert(const_iterator __p, _InputIter __f, _InputIter __l, 2131 typename enable_if<__is_input_iterator<_InputIter>::value 2132 &&!__is_forward_iterator<_InputIter>::value>::type*) 2133{ 2134 __split_buffer<value_type, allocator_type&> __buf(__base::__alloc()); 2135 __buf.__construct_at_end(__f, __l); 2136 typedef typename __split_buffer<value_type, allocator_type&>::iterator __bi; 2137 return insert(__p, move_iterator<__bi>(__buf.begin()), move_iterator<__bi>(__buf.end())); 2138} 2139 2140template <class _Tp, class _Allocator> 2141template <class _ForwardIterator> 2142typename deque<_Tp, _Allocator>::iterator 2143deque<_Tp, _Allocator>::insert(const_iterator __p, _ForwardIterator __f, _ForwardIterator __l, 2144 typename enable_if<__is_forward_iterator<_ForwardIterator>::value 2145 &&!__is_bidirectional_iterator<_ForwardIterator>::value>::type*) 2146{ 2147 size_type __n = _VSTD::distance(__f, __l); 2148 __split_buffer<value_type, allocator_type&> __buf(__n, 0, __base::__alloc()); 2149 __buf.__construct_at_end(__f, __l); 2150 typedef typename __split_buffer<value_type, allocator_type&>::iterator __fwd; 2151 return insert(__p, move_iterator<__fwd>(__buf.begin()), move_iterator<__fwd>(__buf.end())); 2152} 2153 2154template <class _Tp, class _Allocator> 2155template <class _BiIter> 2156typename deque<_Tp, _Allocator>::iterator 2157deque<_Tp, _Allocator>::insert(const_iterator __p, _BiIter __f, _BiIter __l, 2158 typename enable_if<__is_bidirectional_iterator<_BiIter>::value>::type*) 2159{ 2160 size_type __n = _VSTD::distance(__f, __l); 2161 size_type __pos = __p - __base::begin(); 2162 size_type __to_end = __base::size() - __pos; 2163 allocator_type& __a = __base::__alloc(); 2164 if (__pos < __to_end) 2165 { // insert by shifting things backward 2166 if (__n > __front_spare()) 2167 __add_front_capacity(__n - __front_spare()); 2168 // __n <= __front_spare() 2169 iterator __old_begin = __base::begin(); 2170 iterator __i = __old_begin; 2171 _BiIter __m = __f; 2172 if (__n > __pos) 2173 { 2174 __m = __pos < __n / 2 ? _VSTD::prev(__l, __pos) : _VSTD::next(__f, __n - __pos); 2175 for (_BiIter __j = __m; __j != __f; --__base::__start_, ++__base::size()) 2176 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), *--__j); 2177 __n = __pos; 2178 } 2179 if (__n > 0) 2180 { 2181 iterator __obn = __old_begin + __n; 2182 for (iterator __j = __obn; __j != __old_begin;) 2183 { 2184 __alloc_traits::construct(__a, _VSTD::addressof(*--__i), _VSTD::move(*--__j)); 2185 --__base::__start_; 2186 ++__base::size(); 2187 } 2188 if (__n < __pos) 2189 __old_begin = _VSTD::move(__obn, __old_begin + __pos, __old_begin); 2190 _VSTD::copy(__m, __l, __old_begin); 2191 } 2192 } 2193 else 2194 { // insert by shifting things forward 2195 size_type __back_capacity = __back_spare(); 2196 if (__n > __back_capacity) 2197 __add_back_capacity(__n - __back_capacity); 2198 // __n <= __back_capacity 2199 iterator __old_end = __base::end(); 2200 iterator __i = __old_end; 2201 _BiIter __m = __l; 2202 size_type __de = __base::size() - __pos; 2203 if (__n > __de) 2204 { 2205 __m = __de < __n / 2 ? _VSTD::next(__f, __de) : _VSTD::prev(__l, __n - __de); 2206 for (_BiIter __j = __m; __j != __l; ++__i, (void) ++__j, ++__base::size()) 2207 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__j); 2208 __n = __de; 2209 } 2210 if (__n > 0) 2211 { 2212 iterator __oen = __old_end - __n; 2213 for (iterator __j = __oen; __j != __old_end; ++__i, ++__j, ++__base::size()) 2214 __alloc_traits::construct(__a, _VSTD::addressof(*__i), _VSTD::move(*__j)); 2215 if (__n < __de) 2216 __old_end = _VSTD::move_backward(__old_end - __de, __oen, __old_end); 2217 _VSTD::copy_backward(__f, __m, __old_end); 2218 } 2219 } 2220 return __base::begin() + __pos; 2221} 2222 2223template <class _Tp, class _Allocator> 2224template <class _InpIter> 2225void 2226deque<_Tp, _Allocator>::__append(_InpIter __f, _InpIter __l, 2227 typename enable_if<__is_input_iterator<_InpIter>::value && 2228 !__is_forward_iterator<_InpIter>::value>::type*) 2229{ 2230 for (; __f != __l; ++__f) 2231 push_back(*__f); 2232} 2233 2234template <class _Tp, class _Allocator> 2235template <class _ForIter> 2236void 2237deque<_Tp, _Allocator>::__append(_ForIter __f, _ForIter __l, 2238 typename enable_if<__is_forward_iterator<_ForIter>::value>::type*) 2239{ 2240 size_type __n = _VSTD::distance(__f, __l); 2241 allocator_type& __a = __base::__alloc(); 2242 size_type __back_capacity = __back_spare(); 2243 if (__n > __back_capacity) 2244 __add_back_capacity(__n - __back_capacity); 2245 // __n <= __back_capacity 2246 for (iterator __i = __base::end(); __f != __l; ++__i, (void) ++__f, ++__base::size()) 2247 __alloc_traits::construct(__a, _VSTD::addressof(*__i), *__f); 2248} 2249 2250template <class _Tp, class _Allocator> 2251void 2252deque<_Tp, _Allocator>::__append(size_type __n) 2253{ 2254 allocator_type& __a = __base::__alloc(); 2255 size_type __back_capacity = __back_spare(); 2256 if (__n > __back_capacity) 2257 __add_back_capacity(__n - __back_capacity); 2258 // __n <= __back_capacity 2259 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2260 __alloc_traits::construct(__a, _VSTD::addressof(*__i)); 2261} 2262 2263template <class _Tp, class _Allocator> 2264void 2265deque<_Tp, _Allocator>::__append(size_type __n, const value_type& __v) 2266{ 2267 allocator_type& __a = __base::__alloc(); 2268 size_type __back_capacity = __back_spare(); 2269 if (__n > __back_capacity) 2270 __add_back_capacity(__n - __back_capacity); 2271 // __n <= __back_capacity 2272 for (iterator __i = __base::end(); __n; --__n, ++__i, ++__base::size()) 2273 __alloc_traits::construct(__a, _VSTD::addressof(*__i), __v); 2274} 2275 2276// Create front capacity for one block of elements. 2277// Strong guarantee. Either do it or don't touch anything. 2278template <class _Tp, class _Allocator> 2279void 2280deque<_Tp, _Allocator>::__add_front_capacity() 2281{ 2282 allocator_type& __a = __base::__alloc(); 2283 if (__back_spare() >= __base::__block_size) 2284 { 2285 __base::__start_ += __base::__block_size; 2286 pointer __pt = __base::__map_.back(); 2287 __base::__map_.pop_back(); 2288 __base::__map_.push_front(__pt); 2289 } 2290 // Else if __base::__map_.size() < __base::__map_.capacity() then we need to allocate 1 buffer 2291 else if (__base::__map_.size() < __base::__map_.capacity()) 2292 { // we can put the new buffer into the map, but don't shift things around 2293 // until all buffers are allocated. If we throw, we don't need to fix 2294 // anything up (any added buffers are undetectible) 2295 if (__base::__map_.__front_spare() > 0) 2296 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2297 else 2298 { 2299 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2300 // Done allocating, reorder capacity 2301 pointer __pt = __base::__map_.back(); 2302 __base::__map_.pop_back(); 2303 __base::__map_.push_front(__pt); 2304 } 2305 __base::__start_ = __base::__map_.size() == 1 ? 2306 __base::__block_size / 2 : 2307 __base::__start_ + __base::__block_size; 2308 } 2309 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2310 else 2311 { 2312 __split_buffer<pointer, typename __base::__pointer_allocator&> 2313 __buf(max<size_type>(2 * __base::__map_.capacity(), 1), 2314 0, __base::__map_.__alloc()); 2315 2316 typedef __allocator_destructor<_Allocator> _Dp; 2317 unique_ptr<pointer, _Dp> __hold( 2318 __alloc_traits::allocate(__a, __base::__block_size), 2319 _Dp(__a, __base::__block_size)); 2320 __buf.push_back(__hold.get()); 2321 __hold.release(); 2322 2323 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2324 __i != __base::__map_.end(); ++__i) 2325 __buf.push_back(*__i); 2326 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2327 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2328 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2329 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2330 __base::__start_ = __base::__map_.size() == 1 ? 2331 __base::__block_size / 2 : 2332 __base::__start_ + __base::__block_size; 2333 } 2334} 2335 2336// Create front capacity for __n elements. 2337// Strong guarantee. Either do it or don't touch anything. 2338template <class _Tp, class _Allocator> 2339void 2340deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) 2341{ 2342 allocator_type& __a = __base::__alloc(); 2343 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2344 // Number of unused blocks at back: 2345 size_type __back_capacity = __back_spare() / __base::__block_size; 2346 __back_capacity = _VSTD::min(__back_capacity, __nb); // don't take more than you need 2347 __nb -= __back_capacity; // number of blocks need to allocate 2348 // If __nb == 0, then we have sufficient capacity. 2349 if (__nb == 0) 2350 { 2351 __base::__start_ += __base::__block_size * __back_capacity; 2352 for (; __back_capacity > 0; --__back_capacity) 2353 { 2354 pointer __pt = __base::__map_.back(); 2355 __base::__map_.pop_back(); 2356 __base::__map_.push_front(__pt); 2357 } 2358 } 2359 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2360 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2361 { // we can put the new buffers into the map, but don't shift things around 2362 // until all buffers are allocated. If we throw, we don't need to fix 2363 // anything up (any added buffers are undetectible) 2364 for (; __nb > 0; --__nb, __base::__start_ += __base::__block_size - (__base::__map_.size() == 1)) 2365 { 2366 if (__base::__map_.__front_spare() == 0) 2367 break; 2368 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2369 } 2370 for (; __nb > 0; --__nb, ++__back_capacity) 2371 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2372 // Done allocating, reorder capacity 2373 __base::__start_ += __back_capacity * __base::__block_size; 2374 for (; __back_capacity > 0; --__back_capacity) 2375 { 2376 pointer __pt = __base::__map_.back(); 2377 __base::__map_.pop_back(); 2378 __base::__map_.push_front(__pt); 2379 } 2380 } 2381 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2382 else 2383 { 2384 size_type __ds = (__nb + __back_capacity) * __base::__block_size - __base::__map_.empty(); 2385 __split_buffer<pointer, typename __base::__pointer_allocator&> 2386 __buf(max<size_type>(2* __base::__map_.capacity(), 2387 __nb + __base::__map_.size()), 2388 0, __base::__map_.__alloc()); 2389#ifndef _LIBCPP_NO_EXCEPTIONS 2390 try 2391 { 2392#endif // _LIBCPP_NO_EXCEPTIONS 2393 for (; __nb > 0; --__nb) 2394 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2395#ifndef _LIBCPP_NO_EXCEPTIONS 2396 } 2397 catch (...) 2398 { 2399 for (typename __base::__map_pointer __i = __buf.begin(); 2400 __i != __buf.end(); ++__i) 2401 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2402 throw; 2403 } 2404#endif // _LIBCPP_NO_EXCEPTIONS 2405 for (; __back_capacity > 0; --__back_capacity) 2406 { 2407 __buf.push_back(__base::__map_.back()); 2408 __base::__map_.pop_back(); 2409 } 2410 for (typename __base::__map_pointer __i = __base::__map_.begin(); 2411 __i != __base::__map_.end(); ++__i) 2412 __buf.push_back(*__i); 2413 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2414 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2415 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2416 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2417 __base::__start_ += __ds; 2418 } 2419} 2420 2421// Create back capacity for one block of elements. 2422// Strong guarantee. Either do it or don't touch anything. 2423template <class _Tp, class _Allocator> 2424void 2425deque<_Tp, _Allocator>::__add_back_capacity() 2426{ 2427 allocator_type& __a = __base::__alloc(); 2428 if (__front_spare() >= __base::__block_size) 2429 { 2430 __base::__start_ -= __base::__block_size; 2431 pointer __pt = __base::__map_.front(); 2432 __base::__map_.pop_front(); 2433 __base::__map_.push_back(__pt); 2434 } 2435 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2436 else if (__base::__map_.size() < __base::__map_.capacity()) 2437 { // we can put the new buffer into the map, but don't shift things around 2438 // until it is allocated. If we throw, we don't need to fix 2439 // anything up (any added buffers are undetectible) 2440 if (__base::__map_.__back_spare() != 0) 2441 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2442 else 2443 { 2444 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2445 // Done allocating, reorder capacity 2446 pointer __pt = __base::__map_.front(); 2447 __base::__map_.pop_front(); 2448 __base::__map_.push_back(__pt); 2449 } 2450 } 2451 // Else need to allocate 1 buffer, *and* we need to reallocate __map_. 2452 else 2453 { 2454 __split_buffer<pointer, typename __base::__pointer_allocator&> 2455 __buf(max<size_type>(2* __base::__map_.capacity(), 1), 2456 __base::__map_.size(), 2457 __base::__map_.__alloc()); 2458 2459 typedef __allocator_destructor<_Allocator> _Dp; 2460 unique_ptr<pointer, _Dp> __hold( 2461 __alloc_traits::allocate(__a, __base::__block_size), 2462 _Dp(__a, __base::__block_size)); 2463 __buf.push_back(__hold.get()); 2464 __hold.release(); 2465 2466 for (typename __base::__map_pointer __i = __base::__map_.end(); 2467 __i != __base::__map_.begin();) 2468 __buf.push_front(*--__i); 2469 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2470 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2471 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2472 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2473 } 2474} 2475 2476// Create back capacity for __n elements. 2477// Strong guarantee. Either do it or don't touch anything. 2478template <class _Tp, class _Allocator> 2479void 2480deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) 2481{ 2482 allocator_type& __a = __base::__alloc(); 2483 size_type __nb = __recommend_blocks(__n + __base::__map_.empty()); 2484 // Number of unused blocks at front: 2485 size_type __front_capacity = __front_spare() / __base::__block_size; 2486 __front_capacity = _VSTD::min(__front_capacity, __nb); // don't take more than you need 2487 __nb -= __front_capacity; // number of blocks need to allocate 2488 // If __nb == 0, then we have sufficient capacity. 2489 if (__nb == 0) 2490 { 2491 __base::__start_ -= __base::__block_size * __front_capacity; 2492 for (; __front_capacity > 0; --__front_capacity) 2493 { 2494 pointer __pt = __base::__map_.front(); 2495 __base::__map_.pop_front(); 2496 __base::__map_.push_back(__pt); 2497 } 2498 } 2499 // Else if __nb <= __map_.capacity() - __map_.size() then we need to allocate __nb buffers 2500 else if (__nb <= __base::__map_.capacity() - __base::__map_.size()) 2501 { // we can put the new buffers into the map, but don't shift things around 2502 // until all buffers are allocated. If we throw, we don't need to fix 2503 // anything up (any added buffers are undetectible) 2504 for (; __nb > 0; --__nb) 2505 { 2506 if (__base::__map_.__back_spare() == 0) 2507 break; 2508 __base::__map_.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2509 } 2510 for (; __nb > 0; --__nb, ++__front_capacity, __base::__start_ += 2511 __base::__block_size - (__base::__map_.size() == 1)) 2512 __base::__map_.push_front(__alloc_traits::allocate(__a, __base::__block_size)); 2513 // Done allocating, reorder capacity 2514 __base::__start_ -= __base::__block_size * __front_capacity; 2515 for (; __front_capacity > 0; --__front_capacity) 2516 { 2517 pointer __pt = __base::__map_.front(); 2518 __base::__map_.pop_front(); 2519 __base::__map_.push_back(__pt); 2520 } 2521 } 2522 // Else need to allocate __nb buffers, *and* we need to reallocate __map_. 2523 else 2524 { 2525 size_type __ds = __front_capacity * __base::__block_size; 2526 __split_buffer<pointer, typename __base::__pointer_allocator&> 2527 __buf(max<size_type>(2* __base::__map_.capacity(), 2528 __nb + __base::__map_.size()), 2529 __base::__map_.size() - __front_capacity, 2530 __base::__map_.__alloc()); 2531#ifndef _LIBCPP_NO_EXCEPTIONS 2532 try 2533 { 2534#endif // _LIBCPP_NO_EXCEPTIONS 2535 for (; __nb > 0; --__nb) 2536 __buf.push_back(__alloc_traits::allocate(__a, __base::__block_size)); 2537#ifndef _LIBCPP_NO_EXCEPTIONS 2538 } 2539 catch (...) 2540 { 2541 for (typename __base::__map_pointer __i = __buf.begin(); 2542 __i != __buf.end(); ++__i) 2543 __alloc_traits::deallocate(__a, *__i, __base::__block_size); 2544 throw; 2545 } 2546#endif // _LIBCPP_NO_EXCEPTIONS 2547 for (; __front_capacity > 0; --__front_capacity) 2548 { 2549 __buf.push_back(__base::__map_.front()); 2550 __base::__map_.pop_front(); 2551 } 2552 for (typename __base::__map_pointer __i = __base::__map_.end(); 2553 __i != __base::__map_.begin();) 2554 __buf.push_front(*--__i); 2555 _VSTD::swap(__base::__map_.__first_, __buf.__first_); 2556 _VSTD::swap(__base::__map_.__begin_, __buf.__begin_); 2557 _VSTD::swap(__base::__map_.__end_, __buf.__end_); 2558 _VSTD::swap(__base::__map_.__end_cap(), __buf.__end_cap()); 2559 __base::__start_ -= __ds; 2560 } 2561} 2562 2563template <class _Tp, class _Allocator> 2564void 2565deque<_Tp, _Allocator>::pop_front() 2566{ 2567 allocator_type& __a = __base::__alloc(); 2568 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() + 2569 __base::__start_ / __base::__block_size) + 2570 __base::__start_ % __base::__block_size)); 2571 --__base::size(); 2572 if (++__base::__start_ >= 2 * __base::__block_size) 2573 { 2574 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2575 __base::__map_.pop_front(); 2576 __base::__start_ -= __base::__block_size; 2577 } 2578} 2579 2580template <class _Tp, class _Allocator> 2581void 2582deque<_Tp, _Allocator>::pop_back() 2583{ 2584 allocator_type& __a = __base::__alloc(); 2585 size_type __p = __base::size() + __base::__start_ - 1; 2586 __alloc_traits::destroy(__a, __to_raw_pointer(*(__base::__map_.begin() + 2587 __p / __base::__block_size) + 2588 __p % __base::__block_size)); 2589 --__base::size(); 2590 if (__back_spare() >= 2 * __base::__block_size) 2591 { 2592 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2593 __base::__map_.pop_back(); 2594 } 2595} 2596 2597// move assign [__f, __l) to [__r, __r + (__l-__f)). 2598// If __vt points into [__f, __l), then subtract (__f - __r) from __vt. 2599template <class _Tp, class _Allocator> 2600typename deque<_Tp, _Allocator>::iterator 2601deque<_Tp, _Allocator>::__move_and_check(iterator __f, iterator __l, iterator __r, 2602 const_pointer& __vt) 2603{ 2604 // as if 2605 // for (; __f != __l; ++__f, ++__r) 2606 // *__r = _VSTD::move(*__f); 2607 difference_type __n = __l - __f; 2608 while (__n > 0) 2609 { 2610 pointer __fb = __f.__ptr_; 2611 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2612 difference_type __bs = __fe - __fb; 2613 if (__bs > __n) 2614 { 2615 __bs = __n; 2616 __fe = __fb + __bs; 2617 } 2618 if (__fb <= __vt && __vt < __fe) 2619 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) -= __f - __r).__ptr_; 2620 __r = _VSTD::move(__fb, __fe, __r); 2621 __n -= __bs; 2622 __f += __bs; 2623 } 2624 return __r; 2625} 2626 2627// move assign [__f, __l) to [__r - (__l-__f), __r) backwards. 2628// If __vt points into [__f, __l), then add (__r - __l) to __vt. 2629template <class _Tp, class _Allocator> 2630typename deque<_Tp, _Allocator>::iterator 2631deque<_Tp, _Allocator>::__move_backward_and_check(iterator __f, iterator __l, iterator __r, 2632 const_pointer& __vt) 2633{ 2634 // as if 2635 // while (__f != __l) 2636 // *--__r = _VSTD::move(*--__l); 2637 difference_type __n = __l - __f; 2638 while (__n > 0) 2639 { 2640 --__l; 2641 pointer __lb = *__l.__m_iter_; 2642 pointer __le = __l.__ptr_ + 1; 2643 difference_type __bs = __le - __lb; 2644 if (__bs > __n) 2645 { 2646 __bs = __n; 2647 __lb = __le - __bs; 2648 } 2649 if (__lb <= __vt && __vt < __le) 2650 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) += __r - __l - 1).__ptr_; 2651 __r = _VSTD::move_backward(__lb, __le, __r); 2652 __n -= __bs; 2653 __l -= __bs - 1; 2654 } 2655 return __r; 2656} 2657 2658// move construct [__f, __l) to [__r, __r + (__l-__f)). 2659// If __vt points into [__f, __l), then add (__r - __f) to __vt. 2660template <class _Tp, class _Allocator> 2661void 2662deque<_Tp, _Allocator>::__move_construct_and_check(iterator __f, iterator __l, 2663 iterator __r, const_pointer& __vt) 2664{ 2665 allocator_type& __a = __base::__alloc(); 2666 // as if 2667 // for (; __f != __l; ++__r, ++__f, ++__base::size()) 2668 // __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__f)); 2669 difference_type __n = __l - __f; 2670 while (__n > 0) 2671 { 2672 pointer __fb = __f.__ptr_; 2673 pointer __fe = *__f.__m_iter_ + __base::__block_size; 2674 difference_type __bs = __fe - __fb; 2675 if (__bs > __n) 2676 { 2677 __bs = __n; 2678 __fe = __fb + __bs; 2679 } 2680 if (__fb <= __vt && __vt < __fe) 2681 __vt = (const_iterator(static_cast<__map_const_pointer>(__f.__m_iter_), __vt) += __r - __f).__ptr_; 2682 for (; __fb != __fe; ++__fb, ++__r, ++__base::size()) 2683 __alloc_traits::construct(__a, _VSTD::addressof(*__r), _VSTD::move(*__fb)); 2684 __n -= __bs; 2685 __f += __bs; 2686 } 2687} 2688 2689// move construct [__f, __l) to [__r - (__l-__f), __r) backwards. 2690// If __vt points into [__f, __l), then subtract (__l - __r) from __vt. 2691template <class _Tp, class _Allocator> 2692void 2693deque<_Tp, _Allocator>::__move_construct_backward_and_check(iterator __f, iterator __l, 2694 iterator __r, const_pointer& __vt) 2695{ 2696 allocator_type& __a = __base::__alloc(); 2697 // as if 2698 // for (iterator __j = __l; __j != __f;) 2699 // { 2700 // __alloc_traitsconstruct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__j)); 2701 // --__base::__start_; 2702 // ++__base::size(); 2703 // } 2704 difference_type __n = __l - __f; 2705 while (__n > 0) 2706 { 2707 --__l; 2708 pointer __lb = *__l.__m_iter_; 2709 pointer __le = __l.__ptr_ + 1; 2710 difference_type __bs = __le - __lb; 2711 if (__bs > __n) 2712 { 2713 __bs = __n; 2714 __lb = __le - __bs; 2715 } 2716 if (__lb <= __vt && __vt < __le) 2717 __vt = (const_iterator(static_cast<__map_const_pointer>(__l.__m_iter_), __vt) -= __l - __r + 1).__ptr_; 2718 while (__le != __lb) 2719 { 2720 __alloc_traits::construct(__a, _VSTD::addressof(*--__r), _VSTD::move(*--__le)); 2721 --__base::__start_; 2722 ++__base::size(); 2723 } 2724 __n -= __bs; 2725 __l -= __bs - 1; 2726 } 2727} 2728 2729template <class _Tp, class _Allocator> 2730typename deque<_Tp, _Allocator>::iterator 2731deque<_Tp, _Allocator>::erase(const_iterator __f) 2732{ 2733 iterator __b = __base::begin(); 2734 difference_type __pos = __f - __b; 2735 iterator __p = __b + __pos; 2736 allocator_type& __a = __base::__alloc(); 2737 if (__pos <= (__base::size() - 1) / 2) 2738 { // erase from front 2739 _VSTD::move_backward(__b, __p, _VSTD::next(__p)); 2740 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2741 --__base::size(); 2742 ++__base::__start_; 2743 if (__front_spare() >= 2 * __base::__block_size) 2744 { 2745 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2746 __base::__map_.pop_front(); 2747 __base::__start_ -= __base::__block_size; 2748 } 2749 } 2750 else 2751 { // erase from back 2752 iterator __i = _VSTD::move(_VSTD::next(__p), __base::end(), __p); 2753 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2754 --__base::size(); 2755 if (__back_spare() >= 2 * __base::__block_size) 2756 { 2757 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2758 __base::__map_.pop_back(); 2759 } 2760 } 2761 return __base::begin() + __pos; 2762} 2763 2764template <class _Tp, class _Allocator> 2765typename deque<_Tp, _Allocator>::iterator 2766deque<_Tp, _Allocator>::erase(const_iterator __f, const_iterator __l) 2767{ 2768 difference_type __n = __l - __f; 2769 iterator __b = __base::begin(); 2770 difference_type __pos = __f - __b; 2771 iterator __p = __b + __pos; 2772 if (__n > 0) 2773 { 2774 allocator_type& __a = __base::__alloc(); 2775 if (__pos <= (__base::size() - __n) / 2) 2776 { // erase from front 2777 iterator __i = _VSTD::move_backward(__b, __p, __p + __n); 2778 for (; __b != __i; ++__b) 2779 __alloc_traits::destroy(__a, _VSTD::addressof(*__b)); 2780 __base::size() -= __n; 2781 __base::__start_ += __n; 2782 while (__front_spare() >= 2 * __base::__block_size) 2783 { 2784 __alloc_traits::deallocate(__a, __base::__map_.front(), __base::__block_size); 2785 __base::__map_.pop_front(); 2786 __base::__start_ -= __base::__block_size; 2787 } 2788 } 2789 else 2790 { // erase from back 2791 iterator __i = _VSTD::move(__p + __n, __base::end(), __p); 2792 for (iterator __e = __base::end(); __i != __e; ++__i) 2793 __alloc_traits::destroy(__a, _VSTD::addressof(*__i)); 2794 __base::size() -= __n; 2795 while (__back_spare() >= 2 * __base::__block_size) 2796 { 2797 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2798 __base::__map_.pop_back(); 2799 } 2800 } 2801 } 2802 return __base::begin() + __pos; 2803} 2804 2805template <class _Tp, class _Allocator> 2806void 2807deque<_Tp, _Allocator>::__erase_to_end(const_iterator __f) 2808{ 2809 iterator __e = __base::end(); 2810 difference_type __n = __e - __f; 2811 if (__n > 0) 2812 { 2813 allocator_type& __a = __base::__alloc(); 2814 iterator __b = __base::begin(); 2815 difference_type __pos = __f - __b; 2816 for (iterator __p = __b + __pos; __p != __e; ++__p) 2817 __alloc_traits::destroy(__a, _VSTD::addressof(*__p)); 2818 __base::size() -= __n; 2819 while (__back_spare() >= 2 * __base::__block_size) 2820 { 2821 __alloc_traits::deallocate(__a, __base::__map_.back(), __base::__block_size); 2822 __base::__map_.pop_back(); 2823 } 2824 } 2825} 2826 2827template <class _Tp, class _Allocator> 2828inline 2829void 2830deque<_Tp, _Allocator>::swap(deque& __c) 2831#if _LIBCPP_STD_VER >= 14 2832 _NOEXCEPT 2833#else 2834 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2835 __is_nothrow_swappable<allocator_type>::value) 2836#endif 2837{ 2838 __base::swap(__c); 2839} 2840 2841template <class _Tp, class _Allocator> 2842inline 2843void 2844deque<_Tp, _Allocator>::clear() _NOEXCEPT 2845{ 2846 __base::clear(); 2847} 2848 2849template <class _Tp, class _Allocator> 2850inline _LIBCPP_INLINE_VISIBILITY 2851bool 2852operator==(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2853{ 2854 const typename deque<_Tp, _Allocator>::size_type __sz = __x.size(); 2855 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 2856} 2857 2858template <class _Tp, class _Allocator> 2859inline _LIBCPP_INLINE_VISIBILITY 2860bool 2861operator!=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2862{ 2863 return !(__x == __y); 2864} 2865 2866template <class _Tp, class _Allocator> 2867inline _LIBCPP_INLINE_VISIBILITY 2868bool 2869operator< (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2870{ 2871 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2872} 2873 2874template <class _Tp, class _Allocator> 2875inline _LIBCPP_INLINE_VISIBILITY 2876bool 2877operator> (const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2878{ 2879 return __y < __x; 2880} 2881 2882template <class _Tp, class _Allocator> 2883inline _LIBCPP_INLINE_VISIBILITY 2884bool 2885operator>=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2886{ 2887 return !(__x < __y); 2888} 2889 2890template <class _Tp, class _Allocator> 2891inline _LIBCPP_INLINE_VISIBILITY 2892bool 2893operator<=(const deque<_Tp, _Allocator>& __x, const deque<_Tp, _Allocator>& __y) 2894{ 2895 return !(__y < __x); 2896} 2897 2898template <class _Tp, class _Allocator> 2899inline _LIBCPP_INLINE_VISIBILITY 2900void 2901swap(deque<_Tp, _Allocator>& __x, deque<_Tp, _Allocator>& __y) 2902 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 2903{ 2904 __x.swap(__y); 2905} 2906 2907_LIBCPP_END_NAMESPACE_STD 2908 2909#endif // _LIBCPP_DEQUE 2910