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