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