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