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