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