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