1 // -*- C++ -*- 2 //===------------------------------ vector --------------------------------===// 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_VECTOR 12 #define _LIBCPP_VECTOR 13 14 /* 15 vector synopsis 16 17 namespace std 18 { 19 20 template <class T, class Allocator = allocator<T> > 21 class vector 22 { 23 public: 24 typedef T value_type; 25 typedef Allocator allocator_type; 26 typedef typename allocator_type::reference reference; 27 typedef typename allocator_type::const_reference const_reference; 28 typedef implementation-defined iterator; 29 typedef implementation-defined const_iterator; 30 typedef typename allocator_type::size_type size_type; 31 typedef typename allocator_type::difference_type difference_type; 32 typedef typename allocator_type::pointer pointer; 33 typedef typename allocator_type::const_pointer const_pointer; 34 typedef std::reverse_iterator<iterator> reverse_iterator; 35 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 36 37 vector() 38 noexcept(is_nothrow_default_constructible<allocator_type>::value); 39 explicit vector(const allocator_type&); 40 explicit vector(size_type n); 41 explicit vector(size_type n, const allocator_type&); // C++14 42 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 43 template <class InputIterator> 44 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 45 vector(const vector& x); 46 vector(vector&& x) 47 noexcept(is_nothrow_move_constructible<allocator_type>::value); 48 vector(initializer_list<value_type> il); 49 vector(initializer_list<value_type> il, const allocator_type& a); 50 ~vector(); 51 vector& operator=(const vector& x); 52 vector& operator=(vector&& x) 53 noexcept( 54 allocator_type::propagate_on_container_move_assignment::value || 55 allocator_type::is_always_equal::value); // C++17 56 vector& operator=(initializer_list<value_type> il); 57 template <class InputIterator> 58 void assign(InputIterator first, InputIterator last); 59 void assign(size_type n, const value_type& u); 60 void assign(initializer_list<value_type> il); 61 62 allocator_type get_allocator() const noexcept; 63 64 iterator begin() noexcept; 65 const_iterator begin() const noexcept; 66 iterator end() noexcept; 67 const_iterator end() const noexcept; 68 69 reverse_iterator rbegin() noexcept; 70 const_reverse_iterator rbegin() const noexcept; 71 reverse_iterator rend() noexcept; 72 const_reverse_iterator rend() const noexcept; 73 74 const_iterator cbegin() const noexcept; 75 const_iterator cend() const noexcept; 76 const_reverse_iterator crbegin() const noexcept; 77 const_reverse_iterator crend() const noexcept; 78 79 size_type size() const noexcept; 80 size_type max_size() const noexcept; 81 size_type capacity() const noexcept; 82 bool empty() const noexcept; 83 void reserve(size_type n); 84 void shrink_to_fit() noexcept; 85 86 reference operator[](size_type n); 87 const_reference operator[](size_type n) const; 88 reference at(size_type n); 89 const_reference at(size_type n) const; 90 91 reference front(); 92 const_reference front() const; 93 reference back(); 94 const_reference back() const; 95 96 value_type* data() noexcept; 97 const value_type* data() const noexcept; 98 99 void push_back(const value_type& x); 100 void push_back(value_type&& x); 101 template <class... Args> 102 reference emplace_back(Args&&... args); // reference in C++17 103 void pop_back(); 104 105 template <class... Args> iterator emplace(const_iterator position, Args&&... args); 106 iterator insert(const_iterator position, const value_type& x); 107 iterator insert(const_iterator position, value_type&& x); 108 iterator insert(const_iterator position, size_type n, const value_type& x); 109 template <class InputIterator> 110 iterator insert(const_iterator position, InputIterator first, InputIterator last); 111 iterator insert(const_iterator position, initializer_list<value_type> il); 112 113 iterator erase(const_iterator position); 114 iterator erase(const_iterator first, const_iterator last); 115 116 void clear() noexcept; 117 118 void resize(size_type sz); 119 void resize(size_type sz, const value_type& c); 120 121 void swap(vector&) 122 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value || 123 allocator_traits<allocator_type>::is_always_equal::value); // C++17 124 125 bool __invariants() const; 126 }; 127 128 template <class Allocator = allocator<T> > 129 class vector<bool, Allocator> 130 { 131 public: 132 typedef bool value_type; 133 typedef Allocator allocator_type; 134 typedef implementation-defined iterator; 135 typedef implementation-defined const_iterator; 136 typedef typename allocator_type::size_type size_type; 137 typedef typename allocator_type::difference_type difference_type; 138 typedef iterator pointer; 139 typedef const_iterator const_pointer; 140 typedef std::reverse_iterator<iterator> reverse_iterator; 141 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 142 143 class reference 144 { 145 public: 146 reference(const reference&) noexcept; 147 operator bool() const noexcept; 148 reference& operator=(const bool x) noexcept; 149 reference& operator=(const reference& x) noexcept; 150 iterator operator&() const noexcept; 151 void flip() noexcept; 152 }; 153 154 class const_reference 155 { 156 public: 157 const_reference(const reference&) noexcept; 158 operator bool() const noexcept; 159 const_iterator operator&() const noexcept; 160 }; 161 162 vector() 163 noexcept(is_nothrow_default_constructible<allocator_type>::value); 164 explicit vector(const allocator_type&); 165 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14 166 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 167 template <class InputIterator> 168 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 169 vector(const vector& x); 170 vector(vector&& x) 171 noexcept(is_nothrow_move_constructible<allocator_type>::value); 172 vector(initializer_list<value_type> il); 173 vector(initializer_list<value_type> il, const allocator_type& a); 174 ~vector(); 175 vector& operator=(const vector& x); 176 vector& operator=(vector&& x) 177 noexcept( 178 allocator_type::propagate_on_container_move_assignment::value || 179 allocator_type::is_always_equal::value); // C++17 180 vector& operator=(initializer_list<value_type> il); 181 template <class InputIterator> 182 void assign(InputIterator first, InputIterator last); 183 void assign(size_type n, const value_type& u); 184 void assign(initializer_list<value_type> il); 185 186 allocator_type get_allocator() const noexcept; 187 188 iterator begin() noexcept; 189 const_iterator begin() const noexcept; 190 iterator end() noexcept; 191 const_iterator end() const noexcept; 192 193 reverse_iterator rbegin() noexcept; 194 const_reverse_iterator rbegin() const noexcept; 195 reverse_iterator rend() noexcept; 196 const_reverse_iterator rend() const noexcept; 197 198 const_iterator cbegin() const noexcept; 199 const_iterator cend() const noexcept; 200 const_reverse_iterator crbegin() const noexcept; 201 const_reverse_iterator crend() const noexcept; 202 203 size_type size() const noexcept; 204 size_type max_size() const noexcept; 205 size_type capacity() const noexcept; 206 bool empty() const noexcept; 207 void reserve(size_type n); 208 void shrink_to_fit() noexcept; 209 210 reference operator[](size_type n); 211 const_reference operator[](size_type n) const; 212 reference at(size_type n); 213 const_reference at(size_type n) const; 214 215 reference front(); 216 const_reference front() const; 217 reference back(); 218 const_reference back() const; 219 220 void push_back(const value_type& x); 221 template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17 222 void pop_back(); 223 224 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14 225 iterator insert(const_iterator position, const value_type& x); 226 iterator insert(const_iterator position, size_type n, const value_type& x); 227 template <class InputIterator> 228 iterator insert(const_iterator position, InputIterator first, InputIterator last); 229 iterator insert(const_iterator position, initializer_list<value_type> il); 230 231 iterator erase(const_iterator position); 232 iterator erase(const_iterator first, const_iterator last); 233 234 void clear() noexcept; 235 236 void resize(size_type sz); 237 void resize(size_type sz, value_type x); 238 239 void swap(vector&) 240 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value || 241 allocator_traits<allocator_type>::is_always_equal::value); // C++17 242 void flip() noexcept; 243 244 bool __invariants() const; 245 }; 246 247 template <class Allocator> struct hash<std::vector<bool, Allocator>>; 248 249 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 250 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 251 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 252 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 253 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 254 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 255 256 template <class T, class Allocator> 257 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y) 258 noexcept(noexcept(x.swap(y))); 259 260 } // std 261 262 */ 263 264 #include <__config> 265 #include <iosfwd> // for forward declaration of vector 266 #include <__bit_reference> 267 #include <type_traits> 268 #include <climits> 269 #include <limits> 270 #include <initializer_list> 271 #include <memory> 272 #include <stdexcept> 273 #include <algorithm> 274 #include <cstring> 275 #include <__split_buffer> 276 #include <__functional_base> 277 278 #include <__debug> 279 280 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 281 #pragma GCC system_header 282 #endif 283 284 _LIBCPP_PUSH_MACROS 285 #include <__undef_macros> 286 287 288 _LIBCPP_BEGIN_NAMESPACE_STD 289 290 template <bool> 291 class __vector_base_common 292 { 293 protected: 294 _LIBCPP_ALWAYS_INLINE __vector_base_common() {} 295 _LIBCPP_NORETURN void __throw_length_error() const; 296 _LIBCPP_NORETURN void __throw_out_of_range() const; 297 }; 298 299 template <bool __b> 300 void 301 __vector_base_common<__b>::__throw_length_error() const 302 { 303 _VSTD::__throw_length_error("vector"); 304 } 305 306 template <bool __b> 307 void 308 __vector_base_common<__b>::__throw_out_of_range() const 309 { 310 _VSTD::__throw_out_of_range("vector"); 311 } 312 313 #ifdef _LIBCPP_MSVC 314 #pragma warning( push ) 315 #pragma warning( disable: 4231 ) 316 #endif // _LIBCPP_MSVC 317 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>) 318 #ifdef _LIBCPP_MSVC 319 #pragma warning( pop ) 320 #endif // _LIBCPP_MSVC 321 322 template <class _Tp, class _Allocator> 323 class __vector_base 324 : protected __vector_base_common<true> 325 { 326 protected: 327 typedef _Tp value_type; 328 typedef _Allocator allocator_type; 329 typedef allocator_traits<allocator_type> __alloc_traits; 330 typedef value_type& reference; 331 typedef const value_type& const_reference; 332 typedef typename __alloc_traits::size_type size_type; 333 typedef typename __alloc_traits::difference_type difference_type; 334 typedef typename __alloc_traits::pointer pointer; 335 typedef typename __alloc_traits::const_pointer const_pointer; 336 typedef pointer iterator; 337 typedef const_pointer const_iterator; 338 339 pointer __begin_; 340 pointer __end_; 341 __compressed_pair<pointer, allocator_type> __end_cap_; 342 343 _LIBCPP_INLINE_VISIBILITY 344 allocator_type& __alloc() _NOEXCEPT 345 {return __end_cap_.second();} 346 _LIBCPP_INLINE_VISIBILITY 347 const allocator_type& __alloc() const _NOEXCEPT 348 {return __end_cap_.second();} 349 _LIBCPP_INLINE_VISIBILITY 350 pointer& __end_cap() _NOEXCEPT 351 {return __end_cap_.first();} 352 _LIBCPP_INLINE_VISIBILITY 353 const pointer& __end_cap() const _NOEXCEPT 354 {return __end_cap_.first();} 355 356 _LIBCPP_INLINE_VISIBILITY 357 __vector_base() 358 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 359 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a); 360 ~__vector_base(); 361 362 _LIBCPP_INLINE_VISIBILITY 363 void clear() _NOEXCEPT {__destruct_at_end(__begin_);} 364 _LIBCPP_INLINE_VISIBILITY 365 size_type capacity() const _NOEXCEPT 366 {return static_cast<size_type>(__end_cap() - __begin_);} 367 368 _LIBCPP_INLINE_VISIBILITY 369 void __destruct_at_end(pointer __new_last) _NOEXCEPT; 370 371 _LIBCPP_INLINE_VISIBILITY 372 void __copy_assign_alloc(const __vector_base& __c) 373 {__copy_assign_alloc(__c, integral_constant<bool, 374 __alloc_traits::propagate_on_container_copy_assignment::value>());} 375 376 _LIBCPP_INLINE_VISIBILITY 377 void __move_assign_alloc(__vector_base& __c) 378 _NOEXCEPT_( 379 !__alloc_traits::propagate_on_container_move_assignment::value || 380 is_nothrow_move_assignable<allocator_type>::value) 381 {__move_assign_alloc(__c, integral_constant<bool, 382 __alloc_traits::propagate_on_container_move_assignment::value>());} 383 private: 384 _LIBCPP_INLINE_VISIBILITY 385 void __copy_assign_alloc(const __vector_base& __c, true_type) 386 { 387 if (__alloc() != __c.__alloc()) 388 { 389 clear(); 390 __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 391 __begin_ = __end_ = __end_cap() = nullptr; 392 } 393 __alloc() = __c.__alloc(); 394 } 395 396 _LIBCPP_INLINE_VISIBILITY 397 void __copy_assign_alloc(const __vector_base&, false_type) 398 {} 399 400 _LIBCPP_INLINE_VISIBILITY 401 void __move_assign_alloc(__vector_base& __c, true_type) 402 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 403 { 404 __alloc() = _VSTD::move(__c.__alloc()); 405 } 406 407 _LIBCPP_INLINE_VISIBILITY 408 void __move_assign_alloc(__vector_base&, false_type) 409 _NOEXCEPT 410 {} 411 }; 412 413 template <class _Tp, class _Allocator> 414 inline _LIBCPP_INLINE_VISIBILITY 415 void 416 __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT 417 { 418 pointer __soon_to_be_end = __end_; 419 while (__new_last != __soon_to_be_end) 420 __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__soon_to_be_end)); 421 __end_ = __new_last; 422 } 423 424 template <class _Tp, class _Allocator> 425 inline _LIBCPP_INLINE_VISIBILITY 426 __vector_base<_Tp, _Allocator>::__vector_base() 427 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 428 : __begin_(nullptr), 429 __end_(nullptr), 430 __end_cap_(nullptr) 431 { 432 } 433 434 template <class _Tp, class _Allocator> 435 inline _LIBCPP_INLINE_VISIBILITY 436 __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a) 437 : __begin_(nullptr), 438 __end_(nullptr), 439 __end_cap_(nullptr, __a) 440 { 441 } 442 443 template <class _Tp, class _Allocator> 444 __vector_base<_Tp, _Allocator>::~__vector_base() 445 { 446 if (__begin_ != nullptr) 447 { 448 clear(); 449 __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 450 } 451 } 452 453 template <class _Tp, class _Allocator /* = allocator<_Tp> */> 454 class _LIBCPP_TEMPLATE_VIS vector 455 : private __vector_base<_Tp, _Allocator> 456 { 457 private: 458 typedef __vector_base<_Tp, _Allocator> __base; 459 typedef allocator<_Tp> __default_allocator_type; 460 public: 461 typedef vector __self; 462 typedef _Tp value_type; 463 typedef _Allocator allocator_type; 464 typedef typename __base::__alloc_traits __alloc_traits; 465 typedef typename __base::reference reference; 466 typedef typename __base::const_reference const_reference; 467 typedef typename __base::size_type size_type; 468 typedef typename __base::difference_type difference_type; 469 typedef typename __base::pointer pointer; 470 typedef typename __base::const_pointer const_pointer; 471 typedef __wrap_iter<pointer> iterator; 472 typedef __wrap_iter<const_pointer> const_iterator; 473 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 474 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 475 476 static_assert((is_same<typename allocator_type::value_type, value_type>::value), 477 "Allocator::value_type must be same type as value_type"); 478 479 _LIBCPP_INLINE_VISIBILITY 480 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 481 { 482 #if _LIBCPP_DEBUG_LEVEL >= 2 483 __get_db()->__insert_c(this); 484 #endif 485 } 486 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) 487 #if _LIBCPP_STD_VER <= 14 488 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 489 #else 490 _NOEXCEPT 491 #endif 492 : __base(__a) 493 { 494 #if _LIBCPP_DEBUG_LEVEL >= 2 495 __get_db()->__insert_c(this); 496 #endif 497 } 498 explicit vector(size_type __n); 499 #if _LIBCPP_STD_VER > 11 500 explicit vector(size_type __n, const allocator_type& __a); 501 #endif 502 vector(size_type __n, const_reference __x); 503 vector(size_type __n, const_reference __x, const allocator_type& __a); 504 template <class _InputIterator> 505 vector(_InputIterator __first, 506 typename enable_if<__is_input_iterator <_InputIterator>::value && 507 !__is_forward_iterator<_InputIterator>::value && 508 is_constructible< 509 value_type, 510 typename iterator_traits<_InputIterator>::reference>::value, 511 _InputIterator>::type __last); 512 template <class _InputIterator> 513 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 514 typename enable_if<__is_input_iterator <_InputIterator>::value && 515 !__is_forward_iterator<_InputIterator>::value && 516 is_constructible< 517 value_type, 518 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0); 519 template <class _ForwardIterator> 520 vector(_ForwardIterator __first, 521 typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 522 is_constructible< 523 value_type, 524 typename iterator_traits<_ForwardIterator>::reference>::value, 525 _ForwardIterator>::type __last); 526 template <class _ForwardIterator> 527 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 528 typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 529 is_constructible< 530 value_type, 531 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0); 532 533 #if _LIBCPP_DEBUG_LEVEL >= 2 534 _LIBCPP_INLINE_VISIBILITY 535 ~vector() 536 { 537 __get_db()->__erase_c(this); 538 } 539 #endif 540 541 vector(const vector& __x); 542 vector(const vector& __x, const allocator_type& __a); 543 _LIBCPP_INLINE_VISIBILITY 544 vector& operator=(const vector& __x); 545 546 #ifndef _LIBCPP_CXX03_LANG 547 _LIBCPP_INLINE_VISIBILITY 548 vector(initializer_list<value_type> __il); 549 550 _LIBCPP_INLINE_VISIBILITY 551 vector(initializer_list<value_type> __il, const allocator_type& __a); 552 553 _LIBCPP_INLINE_VISIBILITY 554 vector(vector&& __x) 555 #if _LIBCPP_STD_VER > 14 556 _NOEXCEPT; 557 #else 558 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 559 #endif 560 561 _LIBCPP_INLINE_VISIBILITY 562 vector(vector&& __x, const allocator_type& __a); 563 _LIBCPP_INLINE_VISIBILITY 564 vector& operator=(vector&& __x) 565 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); 566 567 _LIBCPP_INLINE_VISIBILITY 568 vector& operator=(initializer_list<value_type> __il) 569 {assign(__il.begin(), __il.end()); return *this;} 570 571 #endif // !_LIBCPP_CXX03_LANG 572 573 template <class _InputIterator> 574 typename enable_if 575 < 576 __is_input_iterator <_InputIterator>::value && 577 !__is_forward_iterator<_InputIterator>::value && 578 is_constructible< 579 value_type, 580 typename iterator_traits<_InputIterator>::reference>::value, 581 void 582 >::type 583 assign(_InputIterator __first, _InputIterator __last); 584 template <class _ForwardIterator> 585 typename enable_if 586 < 587 __is_forward_iterator<_ForwardIterator>::value && 588 is_constructible< 589 value_type, 590 typename iterator_traits<_ForwardIterator>::reference>::value, 591 void 592 >::type 593 assign(_ForwardIterator __first, _ForwardIterator __last); 594 595 void assign(size_type __n, const_reference __u); 596 597 #ifndef _LIBCPP_CXX03_LANG 598 _LIBCPP_INLINE_VISIBILITY 599 void assign(initializer_list<value_type> __il) 600 {assign(__il.begin(), __il.end());} 601 #endif 602 603 _LIBCPP_INLINE_VISIBILITY 604 allocator_type get_allocator() const _NOEXCEPT 605 {return this->__alloc();} 606 607 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT; 608 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT; 609 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT; 610 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT; 611 612 _LIBCPP_INLINE_VISIBILITY 613 reverse_iterator rbegin() _NOEXCEPT 614 {return reverse_iterator(end());} 615 _LIBCPP_INLINE_VISIBILITY 616 const_reverse_iterator rbegin() const _NOEXCEPT 617 {return const_reverse_iterator(end());} 618 _LIBCPP_INLINE_VISIBILITY 619 reverse_iterator rend() _NOEXCEPT 620 {return reverse_iterator(begin());} 621 _LIBCPP_INLINE_VISIBILITY 622 const_reverse_iterator rend() const _NOEXCEPT 623 {return const_reverse_iterator(begin());} 624 625 _LIBCPP_INLINE_VISIBILITY 626 const_iterator cbegin() const _NOEXCEPT 627 {return begin();} 628 _LIBCPP_INLINE_VISIBILITY 629 const_iterator cend() const _NOEXCEPT 630 {return end();} 631 _LIBCPP_INLINE_VISIBILITY 632 const_reverse_iterator crbegin() const _NOEXCEPT 633 {return rbegin();} 634 _LIBCPP_INLINE_VISIBILITY 635 const_reverse_iterator crend() const _NOEXCEPT 636 {return rend();} 637 638 _LIBCPP_INLINE_VISIBILITY 639 size_type size() const _NOEXCEPT 640 {return static_cast<size_type>(this->__end_ - this->__begin_);} 641 _LIBCPP_INLINE_VISIBILITY 642 size_type capacity() const _NOEXCEPT 643 {return __base::capacity();} 644 _LIBCPP_INLINE_VISIBILITY 645 bool empty() const _NOEXCEPT 646 {return this->__begin_ == this->__end_;} 647 size_type max_size() const _NOEXCEPT; 648 void reserve(size_type __n); 649 void shrink_to_fit() _NOEXCEPT; 650 651 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); 652 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; 653 reference at(size_type __n); 654 const_reference at(size_type __n) const; 655 656 _LIBCPP_INLINE_VISIBILITY reference front() 657 { 658 _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 659 return *this->__begin_; 660 } 661 _LIBCPP_INLINE_VISIBILITY const_reference front() const 662 { 663 _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 664 return *this->__begin_; 665 } 666 _LIBCPP_INLINE_VISIBILITY reference back() 667 { 668 _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 669 return *(this->__end_ - 1); 670 } 671 _LIBCPP_INLINE_VISIBILITY const_reference back() const 672 { 673 _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 674 return *(this->__end_ - 1); 675 } 676 677 _LIBCPP_INLINE_VISIBILITY 678 value_type* data() _NOEXCEPT 679 {return _VSTD::__to_raw_pointer(this->__begin_);} 680 _LIBCPP_INLINE_VISIBILITY 681 const value_type* data() const _NOEXCEPT 682 {return _VSTD::__to_raw_pointer(this->__begin_);} 683 684 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 685 686 #ifndef _LIBCPP_CXX03_LANG 687 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x); 688 689 template <class... _Args> 690 _LIBCPP_INLINE_VISIBILITY 691 #if _LIBCPP_STD_VER > 14 692 reference emplace_back(_Args&&... __args); 693 #else 694 void emplace_back(_Args&&... __args); 695 #endif 696 #endif // !_LIBCPP_CXX03_LANG 697 698 _LIBCPP_INLINE_VISIBILITY 699 void pop_back(); 700 701 iterator insert(const_iterator __position, const_reference __x); 702 703 #ifndef _LIBCPP_CXX03_LANG 704 iterator insert(const_iterator __position, value_type&& __x); 705 template <class... _Args> 706 iterator emplace(const_iterator __position, _Args&&... __args); 707 #endif // !_LIBCPP_CXX03_LANG 708 709 iterator insert(const_iterator __position, size_type __n, const_reference __x); 710 template <class _InputIterator> 711 typename enable_if 712 < 713 __is_input_iterator <_InputIterator>::value && 714 !__is_forward_iterator<_InputIterator>::value && 715 is_constructible< 716 value_type, 717 typename iterator_traits<_InputIterator>::reference>::value, 718 iterator 719 >::type 720 insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 721 template <class _ForwardIterator> 722 typename enable_if 723 < 724 __is_forward_iterator<_ForwardIterator>::value && 725 is_constructible< 726 value_type, 727 typename iterator_traits<_ForwardIterator>::reference>::value, 728 iterator 729 >::type 730 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 731 732 #ifndef _LIBCPP_CXX03_LANG 733 _LIBCPP_INLINE_VISIBILITY 734 iterator insert(const_iterator __position, initializer_list<value_type> __il) 735 {return insert(__position, __il.begin(), __il.end());} 736 #endif 737 738 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 739 iterator erase(const_iterator __first, const_iterator __last); 740 741 _LIBCPP_INLINE_VISIBILITY 742 void clear() _NOEXCEPT 743 { 744 size_type __old_size = size(); 745 __base::clear(); 746 __annotate_shrink(__old_size); 747 __invalidate_all_iterators(); 748 } 749 750 void resize(size_type __sz); 751 void resize(size_type __sz, const_reference __x); 752 753 void swap(vector&) 754 #if _LIBCPP_STD_VER >= 14 755 _NOEXCEPT_DEBUG; 756 #else 757 _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value || 758 __is_nothrow_swappable<allocator_type>::value); 759 #endif 760 761 bool __invariants() const; 762 763 #if _LIBCPP_DEBUG_LEVEL >= 2 764 765 bool __dereferenceable(const const_iterator* __i) const; 766 bool __decrementable(const const_iterator* __i) const; 767 bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 768 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 769 770 #endif // _LIBCPP_DEBUG_LEVEL >= 2 771 772 private: 773 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 774 _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last); 775 void allocate(size_type __n); 776 void deallocate() _NOEXCEPT; 777 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 778 void __construct_at_end(size_type __n); 779 _LIBCPP_INLINE_VISIBILITY 780 void __construct_at_end(size_type __n, const_reference __x); 781 template <class _ForwardIterator> 782 typename enable_if 783 < 784 __is_forward_iterator<_ForwardIterator>::value, 785 void 786 >::type 787 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n); 788 void __append(size_type __n); 789 void __append(size_type __n, const_reference __x); 790 _LIBCPP_INLINE_VISIBILITY 791 iterator __make_iter(pointer __p) _NOEXCEPT; 792 _LIBCPP_INLINE_VISIBILITY 793 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT; 794 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); 795 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); 796 void __move_range(pointer __from_s, pointer __from_e, pointer __to); 797 void __move_assign(vector& __c, true_type) 798 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 799 void __move_assign(vector& __c, false_type) 800 _NOEXCEPT_(__alloc_traits::is_always_equal::value); 801 _LIBCPP_INLINE_VISIBILITY 802 void __destruct_at_end(pointer __new_last) _NOEXCEPT 803 { 804 __invalidate_iterators_past(__new_last); 805 size_type __old_size = size(); 806 __base::__destruct_at_end(__new_last); 807 __annotate_shrink(__old_size); 808 } 809 810 #ifndef _LIBCPP_CXX03_LANG 811 template <class _Up> void __push_back_slow_path(_Up&& __x); 812 813 template <class... _Args> 814 void __emplace_back_slow_path(_Args&&... __args); 815 #else 816 template <class _Up> void __push_back_slow_path(_Up& __x); 817 #endif 818 819 // The following functions are no-ops outside of AddressSanitizer mode. 820 // We call annotatations only for the default Allocator because other allocators 821 // may not meet the AddressSanitizer alignment constraints. 822 // See the documentation for __sanitizer_annotate_contiguous_container for more details. 823 #ifndef _LIBCPP_HAS_NO_ASAN 824 void __annotate_contiguous_container(const void *__beg, const void *__end, 825 const void *__old_mid, 826 const void *__new_mid) const 827 { 828 829 if (__beg && is_same<allocator_type, __default_allocator_type>::value) 830 __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid); 831 } 832 #else 833 _LIBCPP_INLINE_VISIBILITY 834 void __annotate_contiguous_container(const void*, const void*, const void*, 835 const void*) const {} 836 #endif 837 _LIBCPP_INLINE_VISIBILITY 838 void __annotate_new(size_type __current_size) const { 839 __annotate_contiguous_container(data(), data() + capacity(), 840 data() + capacity(), data() + __current_size); 841 } 842 843 _LIBCPP_INLINE_VISIBILITY 844 void __annotate_delete() const { 845 __annotate_contiguous_container(data(), data() + capacity(), 846 data() + size(), data() + capacity()); 847 } 848 849 _LIBCPP_INLINE_VISIBILITY 850 void __annotate_increase(size_type __n) const 851 { 852 __annotate_contiguous_container(data(), data() + capacity(), 853 data() + size(), data() + size() + __n); 854 } 855 856 _LIBCPP_INLINE_VISIBILITY 857 void __annotate_shrink(size_type __old_size) const 858 { 859 __annotate_contiguous_container(data(), data() + capacity(), 860 data() + __old_size, data() + size()); 861 } 862 #ifndef _LIBCPP_HAS_NO_ASAN 863 // The annotation for size increase should happen before the actual increase, 864 // but if an exception is thrown after that the annotation has to be undone. 865 struct __RAII_IncreaseAnnotator { 866 __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1) 867 : __commit(false), __v(__v), __old_size(__v.size() + __n) { 868 __v.__annotate_increase(__n); 869 } 870 void __done() { __commit = true; } 871 ~__RAII_IncreaseAnnotator() { 872 if (__commit) return; 873 __v.__annotate_shrink(__old_size); 874 } 875 bool __commit; 876 const vector &__v; 877 size_type __old_size; 878 }; 879 #else 880 struct __RAII_IncreaseAnnotator { 881 _LIBCPP_INLINE_VISIBILITY 882 __RAII_IncreaseAnnotator(const vector &, size_type = 1) {} 883 _LIBCPP_INLINE_VISIBILITY void __done() {} 884 }; 885 #endif 886 887 }; 888 889 template <class _Tp, class _Allocator> 890 void 891 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) 892 { 893 __annotate_delete(); 894 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_); 895 _VSTD::swap(this->__begin_, __v.__begin_); 896 _VSTD::swap(this->__end_, __v.__end_); 897 _VSTD::swap(this->__end_cap(), __v.__end_cap()); 898 __v.__first_ = __v.__begin_; 899 __annotate_new(size()); 900 __invalidate_all_iterators(); 901 } 902 903 template <class _Tp, class _Allocator> 904 typename vector<_Tp, _Allocator>::pointer 905 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) 906 { 907 __annotate_delete(); 908 pointer __r = __v.__begin_; 909 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_); 910 __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_); 911 _VSTD::swap(this->__begin_, __v.__begin_); 912 _VSTD::swap(this->__end_, __v.__end_); 913 _VSTD::swap(this->__end_cap(), __v.__end_cap()); 914 __v.__first_ = __v.__begin_; 915 __annotate_new(size()); 916 __invalidate_all_iterators(); 917 return __r; 918 } 919 920 // Allocate space for __n objects 921 // throws length_error if __n > max_size() 922 // throws (probably bad_alloc) if memory run out 923 // Precondition: __begin_ == __end_ == __end_cap() == 0 924 // Precondition: __n > 0 925 // Postcondition: capacity() == __n 926 // Postcondition: size() == 0 927 template <class _Tp, class _Allocator> 928 void 929 vector<_Tp, _Allocator>::allocate(size_type __n) 930 { 931 if (__n > max_size()) 932 this->__throw_length_error(); 933 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); 934 this->__end_cap() = this->__begin_ + __n; 935 __annotate_new(0); 936 } 937 938 template <class _Tp, class _Allocator> 939 void 940 vector<_Tp, _Allocator>::deallocate() _NOEXCEPT 941 { 942 if (this->__begin_ != nullptr) 943 { 944 clear(); 945 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); 946 this->__begin_ = this->__end_ = this->__end_cap() = nullptr; 947 } 948 } 949 950 template <class _Tp, class _Allocator> 951 typename vector<_Tp, _Allocator>::size_type 952 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT 953 { 954 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), 955 numeric_limits<difference_type>::max()); 956 } 957 958 // Precondition: __new_size > capacity() 959 template <class _Tp, class _Allocator> 960 inline _LIBCPP_INLINE_VISIBILITY 961 typename vector<_Tp, _Allocator>::size_type 962 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const 963 { 964 const size_type __ms = max_size(); 965 if (__new_size > __ms) 966 this->__throw_length_error(); 967 const size_type __cap = capacity(); 968 if (__cap >= __ms / 2) 969 return __ms; 970 return _VSTD::max<size_type>(2*__cap, __new_size); 971 } 972 973 // Default constructs __n objects starting at __end_ 974 // throws if construction throws 975 // Precondition: __n > 0 976 // Precondition: size() + __n <= capacity() 977 // Postcondition: size() == size() + __n 978 template <class _Tp, class _Allocator> 979 void 980 vector<_Tp, _Allocator>::__construct_at_end(size_type __n) 981 { 982 allocator_type& __a = this->__alloc(); 983 do 984 { 985 __RAII_IncreaseAnnotator __annotator(*this); 986 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 987 ++this->__end_; 988 --__n; 989 __annotator.__done(); 990 } while (__n > 0); 991 } 992 993 // Copy constructs __n objects starting at __end_ from __x 994 // throws if construction throws 995 // Precondition: __n > 0 996 // Precondition: size() + __n <= capacity() 997 // Postcondition: size() == old size() + __n 998 // Postcondition: [i] == __x for all i in [size() - __n, __n) 999 template <class _Tp, class _Allocator> 1000 inline 1001 void 1002 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 1003 { 1004 allocator_type& __a = this->__alloc(); 1005 do 1006 { 1007 __RAII_IncreaseAnnotator __annotator(*this); 1008 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 1009 ++this->__end_; 1010 --__n; 1011 __annotator.__done(); 1012 } while (__n > 0); 1013 } 1014 1015 template <class _Tp, class _Allocator> 1016 template <class _ForwardIterator> 1017 typename enable_if 1018 < 1019 __is_forward_iterator<_ForwardIterator>::value, 1020 void 1021 >::type 1022 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n) 1023 { 1024 allocator_type& __a = this->__alloc(); 1025 __RAII_IncreaseAnnotator __annotator(*this, __n); 1026 __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_); 1027 __annotator.__done(); 1028 } 1029 1030 // Default constructs __n objects starting at __end_ 1031 // throws if construction throws 1032 // Postcondition: size() == size() + __n 1033 // Exception safety: strong. 1034 template <class _Tp, class _Allocator> 1035 void 1036 vector<_Tp, _Allocator>::__append(size_type __n) 1037 { 1038 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 1039 this->__construct_at_end(__n); 1040 else 1041 { 1042 allocator_type& __a = this->__alloc(); 1043 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 1044 __v.__construct_at_end(__n); 1045 __swap_out_circular_buffer(__v); 1046 } 1047 } 1048 1049 // Default constructs __n objects starting at __end_ 1050 // throws if construction throws 1051 // Postcondition: size() == size() + __n 1052 // Exception safety: strong. 1053 template <class _Tp, class _Allocator> 1054 void 1055 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) 1056 { 1057 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 1058 this->__construct_at_end(__n, __x); 1059 else 1060 { 1061 allocator_type& __a = this->__alloc(); 1062 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 1063 __v.__construct_at_end(__n, __x); 1064 __swap_out_circular_buffer(__v); 1065 } 1066 } 1067 1068 template <class _Tp, class _Allocator> 1069 vector<_Tp, _Allocator>::vector(size_type __n) 1070 { 1071 #if _LIBCPP_DEBUG_LEVEL >= 2 1072 __get_db()->__insert_c(this); 1073 #endif 1074 if (__n > 0) 1075 { 1076 allocate(__n); 1077 __construct_at_end(__n); 1078 } 1079 } 1080 1081 #if _LIBCPP_STD_VER > 11 1082 template <class _Tp, class _Allocator> 1083 vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a) 1084 : __base(__a) 1085 { 1086 #if _LIBCPP_DEBUG_LEVEL >= 2 1087 __get_db()->__insert_c(this); 1088 #endif 1089 if (__n > 0) 1090 { 1091 allocate(__n); 1092 __construct_at_end(__n); 1093 } 1094 } 1095 #endif 1096 1097 template <class _Tp, class _Allocator> 1098 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) 1099 { 1100 #if _LIBCPP_DEBUG_LEVEL >= 2 1101 __get_db()->__insert_c(this); 1102 #endif 1103 if (__n > 0) 1104 { 1105 allocate(__n); 1106 __construct_at_end(__n, __x); 1107 } 1108 } 1109 1110 template <class _Tp, class _Allocator> 1111 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) 1112 : __base(__a) 1113 { 1114 #if _LIBCPP_DEBUG_LEVEL >= 2 1115 __get_db()->__insert_c(this); 1116 #endif 1117 if (__n > 0) 1118 { 1119 allocate(__n); 1120 __construct_at_end(__n, __x); 1121 } 1122 } 1123 1124 template <class _Tp, class _Allocator> 1125 template <class _InputIterator> 1126 vector<_Tp, _Allocator>::vector(_InputIterator __first, 1127 typename enable_if<__is_input_iterator <_InputIterator>::value && 1128 !__is_forward_iterator<_InputIterator>::value && 1129 is_constructible< 1130 value_type, 1131 typename iterator_traits<_InputIterator>::reference>::value, 1132 _InputIterator>::type __last) 1133 { 1134 #if _LIBCPP_DEBUG_LEVEL >= 2 1135 __get_db()->__insert_c(this); 1136 #endif 1137 for (; __first != __last; ++__first) 1138 push_back(*__first); 1139 } 1140 1141 template <class _Tp, class _Allocator> 1142 template <class _InputIterator> 1143 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 1144 typename enable_if<__is_input_iterator <_InputIterator>::value && 1145 !__is_forward_iterator<_InputIterator>::value && 1146 is_constructible< 1147 value_type, 1148 typename iterator_traits<_InputIterator>::reference>::value>::type*) 1149 : __base(__a) 1150 { 1151 #if _LIBCPP_DEBUG_LEVEL >= 2 1152 __get_db()->__insert_c(this); 1153 #endif 1154 for (; __first != __last; ++__first) 1155 push_back(*__first); 1156 } 1157 1158 template <class _Tp, class _Allocator> 1159 template <class _ForwardIterator> 1160 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, 1161 typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 1162 is_constructible< 1163 value_type, 1164 typename iterator_traits<_ForwardIterator>::reference>::value, 1165 _ForwardIterator>::type __last) 1166 { 1167 #if _LIBCPP_DEBUG_LEVEL >= 2 1168 __get_db()->__insert_c(this); 1169 #endif 1170 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1171 if (__n > 0) 1172 { 1173 allocate(__n); 1174 __construct_at_end(__first, __last, __n); 1175 } 1176 } 1177 1178 template <class _Tp, class _Allocator> 1179 template <class _ForwardIterator> 1180 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 1181 typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 1182 is_constructible< 1183 value_type, 1184 typename iterator_traits<_ForwardIterator>::reference>::value>::type*) 1185 : __base(__a) 1186 { 1187 #if _LIBCPP_DEBUG_LEVEL >= 2 1188 __get_db()->__insert_c(this); 1189 #endif 1190 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1191 if (__n > 0) 1192 { 1193 allocate(__n); 1194 __construct_at_end(__first, __last, __n); 1195 } 1196 } 1197 1198 template <class _Tp, class _Allocator> 1199 vector<_Tp, _Allocator>::vector(const vector& __x) 1200 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) 1201 { 1202 #if _LIBCPP_DEBUG_LEVEL >= 2 1203 __get_db()->__insert_c(this); 1204 #endif 1205 size_type __n = __x.size(); 1206 if (__n > 0) 1207 { 1208 allocate(__n); 1209 __construct_at_end(__x.__begin_, __x.__end_, __n); 1210 } 1211 } 1212 1213 template <class _Tp, class _Allocator> 1214 vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) 1215 : __base(__a) 1216 { 1217 #if _LIBCPP_DEBUG_LEVEL >= 2 1218 __get_db()->__insert_c(this); 1219 #endif 1220 size_type __n = __x.size(); 1221 if (__n > 0) 1222 { 1223 allocate(__n); 1224 __construct_at_end(__x.__begin_, __x.__end_, __n); 1225 } 1226 } 1227 1228 #ifndef _LIBCPP_CXX03_LANG 1229 1230 template <class _Tp, class _Allocator> 1231 inline _LIBCPP_INLINE_VISIBILITY 1232 vector<_Tp, _Allocator>::vector(vector&& __x) 1233 #if _LIBCPP_STD_VER > 14 1234 _NOEXCEPT 1235 #else 1236 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1237 #endif 1238 : __base(_VSTD::move(__x.__alloc())) 1239 { 1240 #if _LIBCPP_DEBUG_LEVEL >= 2 1241 __get_db()->__insert_c(this); 1242 __get_db()->swap(this, &__x); 1243 #endif 1244 this->__begin_ = __x.__begin_; 1245 this->__end_ = __x.__end_; 1246 this->__end_cap() = __x.__end_cap(); 1247 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1248 } 1249 1250 template <class _Tp, class _Allocator> 1251 inline _LIBCPP_INLINE_VISIBILITY 1252 vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) 1253 : __base(__a) 1254 { 1255 #if _LIBCPP_DEBUG_LEVEL >= 2 1256 __get_db()->__insert_c(this); 1257 #endif 1258 if (__a == __x.__alloc()) 1259 { 1260 this->__begin_ = __x.__begin_; 1261 this->__end_ = __x.__end_; 1262 this->__end_cap() = __x.__end_cap(); 1263 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1264 #if _LIBCPP_DEBUG_LEVEL >= 2 1265 __get_db()->swap(this, &__x); 1266 #endif 1267 } 1268 else 1269 { 1270 typedef move_iterator<iterator> _Ip; 1271 assign(_Ip(__x.begin()), _Ip(__x.end())); 1272 } 1273 } 1274 1275 template <class _Tp, class _Allocator> 1276 inline _LIBCPP_INLINE_VISIBILITY 1277 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) 1278 { 1279 #if _LIBCPP_DEBUG_LEVEL >= 2 1280 __get_db()->__insert_c(this); 1281 #endif 1282 if (__il.size() > 0) 1283 { 1284 allocate(__il.size()); 1285 __construct_at_end(__il.begin(), __il.end(), __il.size()); 1286 } 1287 } 1288 1289 template <class _Tp, class _Allocator> 1290 inline _LIBCPP_INLINE_VISIBILITY 1291 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 1292 : __base(__a) 1293 { 1294 #if _LIBCPP_DEBUG_LEVEL >= 2 1295 __get_db()->__insert_c(this); 1296 #endif 1297 if (__il.size() > 0) 1298 { 1299 allocate(__il.size()); 1300 __construct_at_end(__il.begin(), __il.end(), __il.size()); 1301 } 1302 } 1303 1304 template <class _Tp, class _Allocator> 1305 inline _LIBCPP_INLINE_VISIBILITY 1306 vector<_Tp, _Allocator>& 1307 vector<_Tp, _Allocator>::operator=(vector&& __x) 1308 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) 1309 { 1310 __move_assign(__x, integral_constant<bool, 1311 __alloc_traits::propagate_on_container_move_assignment::value>()); 1312 return *this; 1313 } 1314 1315 template <class _Tp, class _Allocator> 1316 void 1317 vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) 1318 _NOEXCEPT_(__alloc_traits::is_always_equal::value) 1319 { 1320 if (__base::__alloc() != __c.__alloc()) 1321 { 1322 typedef move_iterator<iterator> _Ip; 1323 assign(_Ip(__c.begin()), _Ip(__c.end())); 1324 } 1325 else 1326 __move_assign(__c, true_type()); 1327 } 1328 1329 template <class _Tp, class _Allocator> 1330 void 1331 vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) 1332 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1333 { 1334 deallocate(); 1335 __base::__move_assign_alloc(__c); // this can throw 1336 this->__begin_ = __c.__begin_; 1337 this->__end_ = __c.__end_; 1338 this->__end_cap() = __c.__end_cap(); 1339 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 1340 #if _LIBCPP_DEBUG_LEVEL >= 2 1341 __get_db()->swap(this, &__c); 1342 #endif 1343 } 1344 1345 #endif // !_LIBCPP_CXX03_LANG 1346 1347 template <class _Tp, class _Allocator> 1348 inline _LIBCPP_INLINE_VISIBILITY 1349 vector<_Tp, _Allocator>& 1350 vector<_Tp, _Allocator>::operator=(const vector& __x) 1351 { 1352 if (this != &__x) 1353 { 1354 __base::__copy_assign_alloc(__x); 1355 assign(__x.__begin_, __x.__end_); 1356 } 1357 return *this; 1358 } 1359 1360 template <class _Tp, class _Allocator> 1361 template <class _InputIterator> 1362 typename enable_if 1363 < 1364 __is_input_iterator <_InputIterator>::value && 1365 !__is_forward_iterator<_InputIterator>::value && 1366 is_constructible< 1367 _Tp, 1368 typename iterator_traits<_InputIterator>::reference>::value, 1369 void 1370 >::type 1371 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 1372 { 1373 clear(); 1374 for (; __first != __last; ++__first) 1375 push_back(*__first); 1376 } 1377 1378 template <class _Tp, class _Allocator> 1379 template <class _ForwardIterator> 1380 typename enable_if 1381 < 1382 __is_forward_iterator<_ForwardIterator>::value && 1383 is_constructible< 1384 _Tp, 1385 typename iterator_traits<_ForwardIterator>::reference>::value, 1386 void 1387 >::type 1388 vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 1389 { 1390 size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last)); 1391 if (__new_size <= capacity()) 1392 { 1393 _ForwardIterator __mid = __last; 1394 bool __growing = false; 1395 if (__new_size > size()) 1396 { 1397 __growing = true; 1398 __mid = __first; 1399 _VSTD::advance(__mid, size()); 1400 } 1401 pointer __m = _VSTD::copy(__first, __mid, this->__begin_); 1402 if (__growing) 1403 __construct_at_end(__mid, __last, __new_size - size()); 1404 else 1405 this->__destruct_at_end(__m); 1406 } 1407 else 1408 { 1409 deallocate(); 1410 allocate(__recommend(__new_size)); 1411 __construct_at_end(__first, __last, __new_size); 1412 } 1413 __invalidate_all_iterators(); 1414 } 1415 1416 template <class _Tp, class _Allocator> 1417 void 1418 vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) 1419 { 1420 if (__n <= capacity()) 1421 { 1422 size_type __s = size(); 1423 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u); 1424 if (__n > __s) 1425 __construct_at_end(__n - __s, __u); 1426 else 1427 this->__destruct_at_end(this->__begin_ + __n); 1428 } 1429 else 1430 { 1431 deallocate(); 1432 allocate(__recommend(static_cast<size_type>(__n))); 1433 __construct_at_end(__n, __u); 1434 } 1435 __invalidate_all_iterators(); 1436 } 1437 1438 template <class _Tp, class _Allocator> 1439 inline _LIBCPP_INLINE_VISIBILITY 1440 typename vector<_Tp, _Allocator>::iterator 1441 vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT 1442 { 1443 #if _LIBCPP_DEBUG_LEVEL >= 2 1444 return iterator(this, __p); 1445 #else 1446 return iterator(__p); 1447 #endif 1448 } 1449 1450 template <class _Tp, class _Allocator> 1451 inline _LIBCPP_INLINE_VISIBILITY 1452 typename vector<_Tp, _Allocator>::const_iterator 1453 vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT 1454 { 1455 #if _LIBCPP_DEBUG_LEVEL >= 2 1456 return const_iterator(this, __p); 1457 #else 1458 return const_iterator(__p); 1459 #endif 1460 } 1461 1462 template <class _Tp, class _Allocator> 1463 inline _LIBCPP_INLINE_VISIBILITY 1464 typename vector<_Tp, _Allocator>::iterator 1465 vector<_Tp, _Allocator>::begin() _NOEXCEPT 1466 { 1467 return __make_iter(this->__begin_); 1468 } 1469 1470 template <class _Tp, class _Allocator> 1471 inline _LIBCPP_INLINE_VISIBILITY 1472 typename vector<_Tp, _Allocator>::const_iterator 1473 vector<_Tp, _Allocator>::begin() const _NOEXCEPT 1474 { 1475 return __make_iter(this->__begin_); 1476 } 1477 1478 template <class _Tp, class _Allocator> 1479 inline _LIBCPP_INLINE_VISIBILITY 1480 typename vector<_Tp, _Allocator>::iterator 1481 vector<_Tp, _Allocator>::end() _NOEXCEPT 1482 { 1483 return __make_iter(this->__end_); 1484 } 1485 1486 template <class _Tp, class _Allocator> 1487 inline _LIBCPP_INLINE_VISIBILITY 1488 typename vector<_Tp, _Allocator>::const_iterator 1489 vector<_Tp, _Allocator>::end() const _NOEXCEPT 1490 { 1491 return __make_iter(this->__end_); 1492 } 1493 1494 template <class _Tp, class _Allocator> 1495 inline _LIBCPP_INLINE_VISIBILITY 1496 typename vector<_Tp, _Allocator>::reference 1497 vector<_Tp, _Allocator>::operator[](size_type __n) 1498 { 1499 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1500 return this->__begin_[__n]; 1501 } 1502 1503 template <class _Tp, class _Allocator> 1504 inline _LIBCPP_INLINE_VISIBILITY 1505 typename vector<_Tp, _Allocator>::const_reference 1506 vector<_Tp, _Allocator>::operator[](size_type __n) const 1507 { 1508 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1509 return this->__begin_[__n]; 1510 } 1511 1512 template <class _Tp, class _Allocator> 1513 typename vector<_Tp, _Allocator>::reference 1514 vector<_Tp, _Allocator>::at(size_type __n) 1515 { 1516 if (__n >= size()) 1517 this->__throw_out_of_range(); 1518 return this->__begin_[__n]; 1519 } 1520 1521 template <class _Tp, class _Allocator> 1522 typename vector<_Tp, _Allocator>::const_reference 1523 vector<_Tp, _Allocator>::at(size_type __n) const 1524 { 1525 if (__n >= size()) 1526 this->__throw_out_of_range(); 1527 return this->__begin_[__n]; 1528 } 1529 1530 template <class _Tp, class _Allocator> 1531 void 1532 vector<_Tp, _Allocator>::reserve(size_type __n) 1533 { 1534 if (__n > capacity()) 1535 { 1536 allocator_type& __a = this->__alloc(); 1537 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); 1538 __swap_out_circular_buffer(__v); 1539 } 1540 } 1541 1542 template <class _Tp, class _Allocator> 1543 void 1544 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1545 { 1546 if (capacity() > size()) 1547 { 1548 #ifndef _LIBCPP_NO_EXCEPTIONS 1549 try 1550 { 1551 #endif // _LIBCPP_NO_EXCEPTIONS 1552 allocator_type& __a = this->__alloc(); 1553 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a); 1554 __swap_out_circular_buffer(__v); 1555 #ifndef _LIBCPP_NO_EXCEPTIONS 1556 } 1557 catch (...) 1558 { 1559 } 1560 #endif // _LIBCPP_NO_EXCEPTIONS 1561 } 1562 } 1563 1564 template <class _Tp, class _Allocator> 1565 template <class _Up> 1566 void 1567 #ifndef _LIBCPP_CXX03_LANG 1568 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) 1569 #else 1570 vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x) 1571 #endif 1572 { 1573 allocator_type& __a = this->__alloc(); 1574 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1575 // __v.push_back(_VSTD::forward<_Up>(__x)); 1576 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x)); 1577 __v.__end_++; 1578 __swap_out_circular_buffer(__v); 1579 } 1580 1581 template <class _Tp, class _Allocator> 1582 inline _LIBCPP_INLINE_VISIBILITY 1583 void 1584 vector<_Tp, _Allocator>::push_back(const_reference __x) 1585 { 1586 if (this->__end_ != this->__end_cap()) 1587 { 1588 __RAII_IncreaseAnnotator __annotator(*this); 1589 __alloc_traits::construct(this->__alloc(), 1590 _VSTD::__to_raw_pointer(this->__end_), __x); 1591 __annotator.__done(); 1592 ++this->__end_; 1593 } 1594 else 1595 __push_back_slow_path(__x); 1596 } 1597 1598 #ifndef _LIBCPP_CXX03_LANG 1599 1600 template <class _Tp, class _Allocator> 1601 inline _LIBCPP_INLINE_VISIBILITY 1602 void 1603 vector<_Tp, _Allocator>::push_back(value_type&& __x) 1604 { 1605 if (this->__end_ < this->__end_cap()) 1606 { 1607 __RAII_IncreaseAnnotator __annotator(*this); 1608 __alloc_traits::construct(this->__alloc(), 1609 _VSTD::__to_raw_pointer(this->__end_), 1610 _VSTD::move(__x)); 1611 __annotator.__done(); 1612 ++this->__end_; 1613 } 1614 else 1615 __push_back_slow_path(_VSTD::move(__x)); 1616 } 1617 1618 template <class _Tp, class _Allocator> 1619 template <class... _Args> 1620 void 1621 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) 1622 { 1623 allocator_type& __a = this->__alloc(); 1624 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1625 // __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1626 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...); 1627 __v.__end_++; 1628 __swap_out_circular_buffer(__v); 1629 } 1630 1631 template <class _Tp, class _Allocator> 1632 template <class... _Args> 1633 inline 1634 #if _LIBCPP_STD_VER > 14 1635 typename vector<_Tp, _Allocator>::reference 1636 #else 1637 void 1638 #endif 1639 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1640 { 1641 if (this->__end_ < this->__end_cap()) 1642 { 1643 __RAII_IncreaseAnnotator __annotator(*this); 1644 __alloc_traits::construct(this->__alloc(), 1645 _VSTD::__to_raw_pointer(this->__end_), 1646 _VSTD::forward<_Args>(__args)...); 1647 __annotator.__done(); 1648 ++this->__end_; 1649 } 1650 else 1651 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); 1652 #if _LIBCPP_STD_VER > 14 1653 return this->back(); 1654 #endif 1655 } 1656 1657 #endif // !_LIBCPP_CXX03_LANG 1658 1659 template <class _Tp, class _Allocator> 1660 inline 1661 void 1662 vector<_Tp, _Allocator>::pop_back() 1663 { 1664 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector"); 1665 this->__destruct_at_end(this->__end_ - 1); 1666 } 1667 1668 template <class _Tp, class _Allocator> 1669 inline _LIBCPP_INLINE_VISIBILITY 1670 typename vector<_Tp, _Allocator>::iterator 1671 vector<_Tp, _Allocator>::erase(const_iterator __position) 1672 { 1673 #if _LIBCPP_DEBUG_LEVEL >= 2 1674 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1675 "vector::erase(iterator) called with an iterator not" 1676 " referring to this vector"); 1677 #endif 1678 _LIBCPP_ASSERT(__position != end(), 1679 "vector::erase(iterator) called with a non-dereferenceable iterator"); 1680 difference_type __ps = __position - cbegin(); 1681 pointer __p = this->__begin_ + __ps; 1682 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); 1683 this->__invalidate_iterators_past(__p-1); 1684 iterator __r = __make_iter(__p); 1685 return __r; 1686 } 1687 1688 template <class _Tp, class _Allocator> 1689 typename vector<_Tp, _Allocator>::iterator 1690 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) 1691 { 1692 #if _LIBCPP_DEBUG_LEVEL >= 2 1693 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 1694 "vector::erase(iterator, iterator) called with an iterator not" 1695 " referring to this vector"); 1696 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this, 1697 "vector::erase(iterator, iterator) called with an iterator not" 1698 " referring to this vector"); 1699 #endif 1700 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range"); 1701 pointer __p = this->__begin_ + (__first - begin()); 1702 if (__first != __last) { 1703 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p)); 1704 this->__invalidate_iterators_past(__p - 1); 1705 } 1706 iterator __r = __make_iter(__p); 1707 return __r; 1708 } 1709 1710 template <class _Tp, class _Allocator> 1711 void 1712 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) 1713 { 1714 pointer __old_last = this->__end_; 1715 difference_type __n = __old_last - __to; 1716 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_) 1717 __alloc_traits::construct(this->__alloc(), 1718 _VSTD::__to_raw_pointer(this->__end_), 1719 _VSTD::move(*__i)); 1720 _VSTD::move_backward(__from_s, __from_s + __n, __old_last); 1721 } 1722 1723 template <class _Tp, class _Allocator> 1724 typename vector<_Tp, _Allocator>::iterator 1725 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) 1726 { 1727 #if _LIBCPP_DEBUG_LEVEL >= 2 1728 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1729 "vector::insert(iterator, x) called with an iterator not" 1730 " referring to this vector"); 1731 #endif 1732 pointer __p = this->__begin_ + (__position - begin()); 1733 if (this->__end_ < this->__end_cap()) 1734 { 1735 __RAII_IncreaseAnnotator __annotator(*this); 1736 if (__p == this->__end_) 1737 { 1738 __alloc_traits::construct(this->__alloc(), 1739 _VSTD::__to_raw_pointer(this->__end_), __x); 1740 ++this->__end_; 1741 } 1742 else 1743 { 1744 __move_range(__p, this->__end_, __p + 1); 1745 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1746 if (__p <= __xr && __xr < this->__end_) 1747 ++__xr; 1748 *__p = *__xr; 1749 } 1750 __annotator.__done(); 1751 } 1752 else 1753 { 1754 allocator_type& __a = this->__alloc(); 1755 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1756 __v.push_back(__x); 1757 __p = __swap_out_circular_buffer(__v, __p); 1758 } 1759 return __make_iter(__p); 1760 } 1761 1762 #ifndef _LIBCPP_CXX03_LANG 1763 1764 template <class _Tp, class _Allocator> 1765 typename vector<_Tp, _Allocator>::iterator 1766 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) 1767 { 1768 #if _LIBCPP_DEBUG_LEVEL >= 2 1769 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1770 "vector::insert(iterator, x) called with an iterator not" 1771 " referring to this vector"); 1772 #endif 1773 pointer __p = this->__begin_ + (__position - begin()); 1774 if (this->__end_ < this->__end_cap()) 1775 { 1776 __RAII_IncreaseAnnotator __annotator(*this); 1777 if (__p == this->__end_) 1778 { 1779 __alloc_traits::construct(this->__alloc(), 1780 _VSTD::__to_raw_pointer(this->__end_), 1781 _VSTD::move(__x)); 1782 ++this->__end_; 1783 } 1784 else 1785 { 1786 __move_range(__p, this->__end_, __p + 1); 1787 *__p = _VSTD::move(__x); 1788 } 1789 __annotator.__done(); 1790 } 1791 else 1792 { 1793 allocator_type& __a = this->__alloc(); 1794 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1795 __v.push_back(_VSTD::move(__x)); 1796 __p = __swap_out_circular_buffer(__v, __p); 1797 } 1798 return __make_iter(__p); 1799 } 1800 1801 template <class _Tp, class _Allocator> 1802 template <class... _Args> 1803 typename vector<_Tp, _Allocator>::iterator 1804 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) 1805 { 1806 #if _LIBCPP_DEBUG_LEVEL >= 2 1807 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1808 "vector::emplace(iterator, x) called with an iterator not" 1809 " referring to this vector"); 1810 #endif 1811 pointer __p = this->__begin_ + (__position - begin()); 1812 if (this->__end_ < this->__end_cap()) 1813 { 1814 __RAII_IncreaseAnnotator __annotator(*this); 1815 if (__p == this->__end_) 1816 { 1817 __alloc_traits::construct(this->__alloc(), 1818 _VSTD::__to_raw_pointer(this->__end_), 1819 _VSTD::forward<_Args>(__args)...); 1820 ++this->__end_; 1821 } 1822 else 1823 { 1824 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...); 1825 __move_range(__p, this->__end_, __p + 1); 1826 *__p = _VSTD::move(__tmp.get()); 1827 } 1828 __annotator.__done(); 1829 } 1830 else 1831 { 1832 allocator_type& __a = this->__alloc(); 1833 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1834 __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1835 __p = __swap_out_circular_buffer(__v, __p); 1836 } 1837 return __make_iter(__p); 1838 } 1839 1840 #endif // !_LIBCPP_CXX03_LANG 1841 1842 template <class _Tp, class _Allocator> 1843 typename vector<_Tp, _Allocator>::iterator 1844 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) 1845 { 1846 #if _LIBCPP_DEBUG_LEVEL >= 2 1847 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1848 "vector::insert(iterator, n, x) called with an iterator not" 1849 " referring to this vector"); 1850 #endif 1851 pointer __p = this->__begin_ + (__position - begin()); 1852 if (__n > 0) 1853 { 1854 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_)) 1855 { 1856 size_type __old_n = __n; 1857 pointer __old_last = this->__end_; 1858 if (__n > static_cast<size_type>(this->__end_ - __p)) 1859 { 1860 size_type __cx = __n - (this->__end_ - __p); 1861 __construct_at_end(__cx, __x); 1862 __n -= __cx; 1863 } 1864 if (__n > 0) 1865 { 1866 __RAII_IncreaseAnnotator __annotator(*this, __n); 1867 __move_range(__p, __old_last, __p + __old_n); 1868 __annotator.__done(); 1869 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1870 if (__p <= __xr && __xr < this->__end_) 1871 __xr += __old_n; 1872 _VSTD::fill_n(__p, __n, *__xr); 1873 } 1874 } 1875 else 1876 { 1877 allocator_type& __a = this->__alloc(); 1878 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1879 __v.__construct_at_end(__n, __x); 1880 __p = __swap_out_circular_buffer(__v, __p); 1881 } 1882 } 1883 return __make_iter(__p); 1884 } 1885 1886 template <class _Tp, class _Allocator> 1887 template <class _InputIterator> 1888 typename enable_if 1889 < 1890 __is_input_iterator <_InputIterator>::value && 1891 !__is_forward_iterator<_InputIterator>::value && 1892 is_constructible< 1893 _Tp, 1894 typename iterator_traits<_InputIterator>::reference>::value, 1895 typename vector<_Tp, _Allocator>::iterator 1896 >::type 1897 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 1898 { 1899 #if _LIBCPP_DEBUG_LEVEL >= 2 1900 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1901 "vector::insert(iterator, range) called with an iterator not" 1902 " referring to this vector"); 1903 #endif 1904 difference_type __off = __position - begin(); 1905 pointer __p = this->__begin_ + __off; 1906 allocator_type& __a = this->__alloc(); 1907 pointer __old_last = this->__end_; 1908 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) 1909 { 1910 __RAII_IncreaseAnnotator __annotator(*this); 1911 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), 1912 *__first); 1913 ++this->__end_; 1914 __annotator.__done(); 1915 } 1916 __split_buffer<value_type, allocator_type&> __v(__a); 1917 if (__first != __last) 1918 { 1919 #ifndef _LIBCPP_NO_EXCEPTIONS 1920 try 1921 { 1922 #endif // _LIBCPP_NO_EXCEPTIONS 1923 __v.__construct_at_end(__first, __last); 1924 difference_type __old_size = __old_last - this->__begin_; 1925 difference_type __old_p = __p - this->__begin_; 1926 reserve(__recommend(size() + __v.size())); 1927 __p = this->__begin_ + __old_p; 1928 __old_last = this->__begin_ + __old_size; 1929 #ifndef _LIBCPP_NO_EXCEPTIONS 1930 } 1931 catch (...) 1932 { 1933 erase(__make_iter(__old_last), end()); 1934 throw; 1935 } 1936 #endif // _LIBCPP_NO_EXCEPTIONS 1937 } 1938 __p = _VSTD::rotate(__p, __old_last, this->__end_); 1939 insert(__make_iter(__p), make_move_iterator(__v.begin()), 1940 make_move_iterator(__v.end())); 1941 return begin() + __off; 1942 } 1943 1944 template <class _Tp, class _Allocator> 1945 template <class _ForwardIterator> 1946 typename enable_if 1947 < 1948 __is_forward_iterator<_ForwardIterator>::value && 1949 is_constructible< 1950 _Tp, 1951 typename iterator_traits<_ForwardIterator>::reference>::value, 1952 typename vector<_Tp, _Allocator>::iterator 1953 >::type 1954 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 1955 { 1956 #if _LIBCPP_DEBUG_LEVEL >= 2 1957 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1958 "vector::insert(iterator, range) called with an iterator not" 1959 " referring to this vector"); 1960 #endif 1961 pointer __p = this->__begin_ + (__position - begin()); 1962 difference_type __n = _VSTD::distance(__first, __last); 1963 if (__n > 0) 1964 { 1965 if (__n <= this->__end_cap() - this->__end_) 1966 { 1967 size_type __old_n = __n; 1968 pointer __old_last = this->__end_; 1969 _ForwardIterator __m = __last; 1970 difference_type __dx = this->__end_ - __p; 1971 if (__n > __dx) 1972 { 1973 __m = __first; 1974 difference_type __diff = this->__end_ - __p; 1975 _VSTD::advance(__m, __diff); 1976 __construct_at_end(__m, __last, __n - __diff); 1977 __n = __dx; 1978 } 1979 if (__n > 0) 1980 { 1981 __RAII_IncreaseAnnotator __annotator(*this, __n); 1982 __move_range(__p, __old_last, __p + __old_n); 1983 __annotator.__done(); 1984 _VSTD::copy(__first, __m, __p); 1985 } 1986 } 1987 else 1988 { 1989 allocator_type& __a = this->__alloc(); 1990 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1991 __v.__construct_at_end(__first, __last); 1992 __p = __swap_out_circular_buffer(__v, __p); 1993 } 1994 } 1995 return __make_iter(__p); 1996 } 1997 1998 template <class _Tp, class _Allocator> 1999 void 2000 vector<_Tp, _Allocator>::resize(size_type __sz) 2001 { 2002 size_type __cs = size(); 2003 if (__cs < __sz) 2004 this->__append(__sz - __cs); 2005 else if (__cs > __sz) 2006 this->__destruct_at_end(this->__begin_ + __sz); 2007 } 2008 2009 template <class _Tp, class _Allocator> 2010 void 2011 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) 2012 { 2013 size_type __cs = size(); 2014 if (__cs < __sz) 2015 this->__append(__sz - __cs, __x); 2016 else if (__cs > __sz) 2017 this->__destruct_at_end(this->__begin_ + __sz); 2018 } 2019 2020 template <class _Tp, class _Allocator> 2021 void 2022 vector<_Tp, _Allocator>::swap(vector& __x) 2023 #if _LIBCPP_STD_VER >= 14 2024 _NOEXCEPT_DEBUG 2025 #else 2026 _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value || 2027 __is_nothrow_swappable<allocator_type>::value) 2028 #endif 2029 { 2030 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 2031 this->__alloc() == __x.__alloc(), 2032 "vector::swap: Either propagate_on_container_swap must be true" 2033 " or the allocators must compare equal"); 2034 _VSTD::swap(this->__begin_, __x.__begin_); 2035 _VSTD::swap(this->__end_, __x.__end_); 2036 _VSTD::swap(this->__end_cap(), __x.__end_cap()); 2037 __swap_allocator(this->__alloc(), __x.__alloc(), 2038 integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>()); 2039 #if _LIBCPP_DEBUG_LEVEL >= 2 2040 __get_db()->swap(this, &__x); 2041 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2042 } 2043 2044 template <class _Tp, class _Allocator> 2045 bool 2046 vector<_Tp, _Allocator>::__invariants() const 2047 { 2048 if (this->__begin_ == nullptr) 2049 { 2050 if (this->__end_ != nullptr || this->__end_cap() != nullptr) 2051 return false; 2052 } 2053 else 2054 { 2055 if (this->__begin_ > this->__end_) 2056 return false; 2057 if (this->__begin_ == this->__end_cap()) 2058 return false; 2059 if (this->__end_ > this->__end_cap()) 2060 return false; 2061 } 2062 return true; 2063 } 2064 2065 #if _LIBCPP_DEBUG_LEVEL >= 2 2066 2067 template <class _Tp, class _Allocator> 2068 bool 2069 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const 2070 { 2071 return this->__begin_ <= __i->base() && __i->base() < this->__end_; 2072 } 2073 2074 template <class _Tp, class _Allocator> 2075 bool 2076 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const 2077 { 2078 return this->__begin_ < __i->base() && __i->base() <= this->__end_; 2079 } 2080 2081 template <class _Tp, class _Allocator> 2082 bool 2083 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2084 { 2085 const_pointer __p = __i->base() + __n; 2086 return this->__begin_ <= __p && __p <= this->__end_; 2087 } 2088 2089 template <class _Tp, class _Allocator> 2090 bool 2091 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2092 { 2093 const_pointer __p = __i->base() + __n; 2094 return this->__begin_ <= __p && __p < this->__end_; 2095 } 2096 2097 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2098 2099 template <class _Tp, class _Allocator> 2100 inline _LIBCPP_INLINE_VISIBILITY 2101 void 2102 vector<_Tp, _Allocator>::__invalidate_all_iterators() 2103 { 2104 #if _LIBCPP_DEBUG_LEVEL >= 2 2105 __get_db()->__invalidate_all(this); 2106 #endif // _LIBCPP_DEBUG_LEVEL >= 2 2107 } 2108 2109 2110 template <class _Tp, class _Allocator> 2111 inline _LIBCPP_INLINE_VISIBILITY 2112 void 2113 vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) { 2114 #if _LIBCPP_DEBUG_LEVEL >= 2 2115 __c_node* __c = __get_db()->__find_c_and_lock(this); 2116 for (__i_node** __p = __c->end_; __p != __c->beg_; ) { 2117 --__p; 2118 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 2119 if (__i->base() > __new_last) { 2120 (*__p)->__c_ = nullptr; 2121 if (--__c->end_ != __p) 2122 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 2123 } 2124 } 2125 __get_db()->unlock(); 2126 #else 2127 ((void)__new_last); 2128 #endif 2129 } 2130 2131 // vector<bool> 2132 2133 template <class _Allocator> class vector<bool, _Allocator>; 2134 2135 template <class _Allocator> struct hash<vector<bool, _Allocator> >; 2136 2137 template <class _Allocator> 2138 struct __has_storage_type<vector<bool, _Allocator> > 2139 { 2140 static const bool value = true; 2141 }; 2142 2143 template <class _Allocator> 2144 class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> 2145 : private __vector_base_common<true> 2146 { 2147 public: 2148 typedef vector __self; 2149 typedef bool value_type; 2150 typedef _Allocator allocator_type; 2151 typedef allocator_traits<allocator_type> __alloc_traits; 2152 typedef typename __alloc_traits::size_type size_type; 2153 typedef typename __alloc_traits::difference_type difference_type; 2154 typedef size_type __storage_type; 2155 typedef __bit_iterator<vector, false> pointer; 2156 typedef __bit_iterator<vector, true> const_pointer; 2157 typedef pointer iterator; 2158 typedef const_pointer const_iterator; 2159 typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 2160 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 2161 2162 private: 2163 typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator; 2164 typedef allocator_traits<__storage_allocator> __storage_traits; 2165 typedef typename __storage_traits::pointer __storage_pointer; 2166 typedef typename __storage_traits::const_pointer __const_storage_pointer; 2167 2168 __storage_pointer __begin_; 2169 size_type __size_; 2170 __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 2171 public: 2172 typedef __bit_reference<vector> reference; 2173 typedef __bit_const_reference<vector> const_reference; 2174 private: 2175 _LIBCPP_INLINE_VISIBILITY 2176 size_type& __cap() _NOEXCEPT 2177 {return __cap_alloc_.first();} 2178 _LIBCPP_INLINE_VISIBILITY 2179 const size_type& __cap() const _NOEXCEPT 2180 {return __cap_alloc_.first();} 2181 _LIBCPP_INLINE_VISIBILITY 2182 __storage_allocator& __alloc() _NOEXCEPT 2183 {return __cap_alloc_.second();} 2184 _LIBCPP_INLINE_VISIBILITY 2185 const __storage_allocator& __alloc() const _NOEXCEPT 2186 {return __cap_alloc_.second();} 2187 2188 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 2189 2190 _LIBCPP_INLINE_VISIBILITY 2191 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT 2192 {return __n * __bits_per_word;} 2193 _LIBCPP_INLINE_VISIBILITY 2194 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT 2195 {return (__n - 1) / __bits_per_word + 1;} 2196 2197 public: 2198 _LIBCPP_INLINE_VISIBILITY 2199 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 2200 2201 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) 2202 #if _LIBCPP_STD_VER <= 14 2203 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value); 2204 #else 2205 _NOEXCEPT; 2206 #endif 2207 ~vector(); 2208 explicit vector(size_type __n); 2209 #if _LIBCPP_STD_VER > 11 2210 explicit vector(size_type __n, const allocator_type& __a); 2211 #endif 2212 vector(size_type __n, const value_type& __v); 2213 vector(size_type __n, const value_type& __v, const allocator_type& __a); 2214 template <class _InputIterator> 2215 vector(_InputIterator __first, _InputIterator __last, 2216 typename enable_if<__is_input_iterator <_InputIterator>::value && 2217 !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2218 template <class _InputIterator> 2219 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2220 typename enable_if<__is_input_iterator <_InputIterator>::value && 2221 !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2222 template <class _ForwardIterator> 2223 vector(_ForwardIterator __first, _ForwardIterator __last, 2224 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2225 template <class _ForwardIterator> 2226 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2227 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2228 2229 vector(const vector& __v); 2230 vector(const vector& __v, const allocator_type& __a); 2231 vector& operator=(const vector& __v); 2232 2233 #ifndef _LIBCPP_CXX03_LANG 2234 vector(initializer_list<value_type> __il); 2235 vector(initializer_list<value_type> __il, const allocator_type& __a); 2236 2237 _LIBCPP_INLINE_VISIBILITY 2238 vector(vector&& __v) 2239 #if _LIBCPP_STD_VER > 14 2240 _NOEXCEPT; 2241 #else 2242 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 2243 #endif 2244 vector(vector&& __v, const allocator_type& __a); 2245 _LIBCPP_INLINE_VISIBILITY 2246 vector& operator=(vector&& __v) 2247 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); 2248 2249 _LIBCPP_INLINE_VISIBILITY 2250 vector& operator=(initializer_list<value_type> __il) 2251 {assign(__il.begin(), __il.end()); return *this;} 2252 2253 #endif // !_LIBCPP_CXX03_LANG 2254 2255 template <class _InputIterator> 2256 typename enable_if 2257 < 2258 __is_input_iterator<_InputIterator>::value && 2259 !__is_forward_iterator<_InputIterator>::value, 2260 void 2261 >::type 2262 assign(_InputIterator __first, _InputIterator __last); 2263 template <class _ForwardIterator> 2264 typename enable_if 2265 < 2266 __is_forward_iterator<_ForwardIterator>::value, 2267 void 2268 >::type 2269 assign(_ForwardIterator __first, _ForwardIterator __last); 2270 2271 void assign(size_type __n, const value_type& __x); 2272 2273 #ifndef _LIBCPP_CXX03_LANG 2274 _LIBCPP_INLINE_VISIBILITY 2275 void assign(initializer_list<value_type> __il) 2276 {assign(__il.begin(), __il.end());} 2277 #endif 2278 2279 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT 2280 {return allocator_type(this->__alloc());} 2281 2282 size_type max_size() const _NOEXCEPT; 2283 _LIBCPP_INLINE_VISIBILITY 2284 size_type capacity() const _NOEXCEPT 2285 {return __internal_cap_to_external(__cap());} 2286 _LIBCPP_INLINE_VISIBILITY 2287 size_type size() const _NOEXCEPT 2288 {return __size_;} 2289 _LIBCPP_INLINE_VISIBILITY 2290 bool empty() const _NOEXCEPT 2291 {return __size_ == 0;} 2292 void reserve(size_type __n); 2293 void shrink_to_fit() _NOEXCEPT; 2294 2295 _LIBCPP_INLINE_VISIBILITY 2296 iterator begin() _NOEXCEPT 2297 {return __make_iter(0);} 2298 _LIBCPP_INLINE_VISIBILITY 2299 const_iterator begin() const _NOEXCEPT 2300 {return __make_iter(0);} 2301 _LIBCPP_INLINE_VISIBILITY 2302 iterator end() _NOEXCEPT 2303 {return __make_iter(__size_);} 2304 _LIBCPP_INLINE_VISIBILITY 2305 const_iterator end() const _NOEXCEPT 2306 {return __make_iter(__size_);} 2307 2308 _LIBCPP_INLINE_VISIBILITY 2309 reverse_iterator rbegin() _NOEXCEPT 2310 {return reverse_iterator(end());} 2311 _LIBCPP_INLINE_VISIBILITY 2312 const_reverse_iterator rbegin() const _NOEXCEPT 2313 {return const_reverse_iterator(end());} 2314 _LIBCPP_INLINE_VISIBILITY 2315 reverse_iterator rend() _NOEXCEPT 2316 {return reverse_iterator(begin());} 2317 _LIBCPP_INLINE_VISIBILITY 2318 const_reverse_iterator rend() const _NOEXCEPT 2319 {return const_reverse_iterator(begin());} 2320 2321 _LIBCPP_INLINE_VISIBILITY 2322 const_iterator cbegin() const _NOEXCEPT 2323 {return __make_iter(0);} 2324 _LIBCPP_INLINE_VISIBILITY 2325 const_iterator cend() const _NOEXCEPT 2326 {return __make_iter(__size_);} 2327 _LIBCPP_INLINE_VISIBILITY 2328 const_reverse_iterator crbegin() const _NOEXCEPT 2329 {return rbegin();} 2330 _LIBCPP_INLINE_VISIBILITY 2331 const_reverse_iterator crend() const _NOEXCEPT 2332 {return rend();} 2333 2334 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);} 2335 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);} 2336 reference at(size_type __n); 2337 const_reference at(size_type __n) const; 2338 2339 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);} 2340 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);} 2341 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);} 2342 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);} 2343 2344 void push_back(const value_type& __x); 2345 #if _LIBCPP_STD_VER > 11 2346 template <class... _Args> 2347 #if _LIBCPP_STD_VER > 14 2348 _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args) 2349 #else 2350 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args) 2351 #endif 2352 { 2353 push_back ( value_type ( _VSTD::forward<_Args>(__args)... )); 2354 #if _LIBCPP_STD_VER > 14 2355 return this->back(); 2356 #endif 2357 } 2358 #endif 2359 2360 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;} 2361 2362 #if _LIBCPP_STD_VER > 11 2363 template <class... _Args> 2364 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args) 2365 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); } 2366 #endif 2367 2368 iterator insert(const_iterator __position, const value_type& __x); 2369 iterator insert(const_iterator __position, size_type __n, const value_type& __x); 2370 iterator insert(const_iterator __position, size_type __n, const_reference __x); 2371 template <class _InputIterator> 2372 typename enable_if 2373 < 2374 __is_input_iterator <_InputIterator>::value && 2375 !__is_forward_iterator<_InputIterator>::value, 2376 iterator 2377 >::type 2378 insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 2379 template <class _ForwardIterator> 2380 typename enable_if 2381 < 2382 __is_forward_iterator<_ForwardIterator>::value, 2383 iterator 2384 >::type 2385 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 2386 2387 #ifndef _LIBCPP_CXX03_LANG 2388 _LIBCPP_INLINE_VISIBILITY 2389 iterator insert(const_iterator __position, initializer_list<value_type> __il) 2390 {return insert(__position, __il.begin(), __il.end());} 2391 #endif 2392 2393 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 2394 iterator erase(const_iterator __first, const_iterator __last); 2395 2396 _LIBCPP_INLINE_VISIBILITY 2397 void clear() _NOEXCEPT {__size_ = 0;} 2398 2399 void swap(vector&) 2400 #if _LIBCPP_STD_VER >= 14 2401 _NOEXCEPT; 2402 #else 2403 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2404 __is_nothrow_swappable<allocator_type>::value); 2405 #endif 2406 static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); } 2407 2408 void resize(size_type __sz, value_type __x = false); 2409 void flip() _NOEXCEPT; 2410 2411 bool __invariants() const; 2412 2413 private: 2414 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 2415 void allocate(size_type __n); 2416 void deallocate() _NOEXCEPT; 2417 _LIBCPP_INLINE_VISIBILITY 2418 static size_type __align_it(size_type __new_size) _NOEXCEPT 2419 {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}; 2420 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 2421 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x); 2422 template <class _ForwardIterator> 2423 typename enable_if 2424 < 2425 __is_forward_iterator<_ForwardIterator>::value, 2426 void 2427 >::type 2428 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 2429 void __append(size_type __n, const_reference __x); 2430 _LIBCPP_INLINE_VISIBILITY 2431 reference __make_ref(size_type __pos) _NOEXCEPT 2432 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2433 _LIBCPP_INLINE_VISIBILITY 2434 const_reference __make_ref(size_type __pos) const _NOEXCEPT 2435 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2436 _LIBCPP_INLINE_VISIBILITY 2437 iterator __make_iter(size_type __pos) _NOEXCEPT 2438 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2439 _LIBCPP_INLINE_VISIBILITY 2440 const_iterator __make_iter(size_type __pos) const _NOEXCEPT 2441 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2442 _LIBCPP_INLINE_VISIBILITY 2443 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT 2444 {return begin() + (__p - cbegin());} 2445 2446 _LIBCPP_INLINE_VISIBILITY 2447 void __copy_assign_alloc(const vector& __v) 2448 {__copy_assign_alloc(__v, integral_constant<bool, 2449 __storage_traits::propagate_on_container_copy_assignment::value>());} 2450 _LIBCPP_INLINE_VISIBILITY 2451 void __copy_assign_alloc(const vector& __c, true_type) 2452 { 2453 if (__alloc() != __c.__alloc()) 2454 deallocate(); 2455 __alloc() = __c.__alloc(); 2456 } 2457 2458 _LIBCPP_INLINE_VISIBILITY 2459 void __copy_assign_alloc(const vector&, false_type) 2460 {} 2461 2462 void __move_assign(vector& __c, false_type); 2463 void __move_assign(vector& __c, true_type) 2464 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 2465 _LIBCPP_INLINE_VISIBILITY 2466 void __move_assign_alloc(vector& __c) 2467 _NOEXCEPT_( 2468 !__storage_traits::propagate_on_container_move_assignment::value || 2469 is_nothrow_move_assignable<allocator_type>::value) 2470 {__move_assign_alloc(__c, integral_constant<bool, 2471 __storage_traits::propagate_on_container_move_assignment::value>());} 2472 _LIBCPP_INLINE_VISIBILITY 2473 void __move_assign_alloc(vector& __c, true_type) 2474 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2475 { 2476 __alloc() = _VSTD::move(__c.__alloc()); 2477 } 2478 2479 _LIBCPP_INLINE_VISIBILITY 2480 void __move_assign_alloc(vector&, false_type) 2481 _NOEXCEPT 2482 {} 2483 2484 size_t __hash_code() const _NOEXCEPT; 2485 2486 friend class __bit_reference<vector>; 2487 friend class __bit_const_reference<vector>; 2488 friend class __bit_iterator<vector, false>; 2489 friend class __bit_iterator<vector, true>; 2490 friend struct __bit_array<vector>; 2491 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>; 2492 }; 2493 2494 template <class _Allocator> 2495 inline _LIBCPP_INLINE_VISIBILITY 2496 void 2497 vector<bool, _Allocator>::__invalidate_all_iterators() 2498 { 2499 } 2500 2501 // Allocate space for __n objects 2502 // throws length_error if __n > max_size() 2503 // throws (probably bad_alloc) if memory run out 2504 // Precondition: __begin_ == __end_ == __cap() == 0 2505 // Precondition: __n > 0 2506 // Postcondition: capacity() == __n 2507 // Postcondition: size() == 0 2508 template <class _Allocator> 2509 void 2510 vector<bool, _Allocator>::allocate(size_type __n) 2511 { 2512 if (__n > max_size()) 2513 this->__throw_length_error(); 2514 __n = __external_cap_to_internal(__n); 2515 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n); 2516 this->__size_ = 0; 2517 this->__cap() = __n; 2518 } 2519 2520 template <class _Allocator> 2521 void 2522 vector<bool, _Allocator>::deallocate() _NOEXCEPT 2523 { 2524 if (this->__begin_ != nullptr) 2525 { 2526 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 2527 __invalidate_all_iterators(); 2528 this->__begin_ = nullptr; 2529 this->__size_ = this->__cap() = 0; 2530 } 2531 } 2532 2533 template <class _Allocator> 2534 typename vector<bool, _Allocator>::size_type 2535 vector<bool, _Allocator>::max_size() const _NOEXCEPT 2536 { 2537 size_type __amax = __storage_traits::max_size(__alloc()); 2538 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 2539 if (__nmax / __bits_per_word <= __amax) 2540 return __nmax; 2541 return __internal_cap_to_external(__amax); 2542 } 2543 2544 // Precondition: __new_size > capacity() 2545 template <class _Allocator> 2546 inline _LIBCPP_INLINE_VISIBILITY 2547 typename vector<bool, _Allocator>::size_type 2548 vector<bool, _Allocator>::__recommend(size_type __new_size) const 2549 { 2550 const size_type __ms = max_size(); 2551 if (__new_size > __ms) 2552 this->__throw_length_error(); 2553 const size_type __cap = capacity(); 2554 if (__cap >= __ms / 2) 2555 return __ms; 2556 return _VSTD::max(2*__cap, __align_it(__new_size)); 2557 } 2558 2559 // Default constructs __n objects starting at __end_ 2560 // Precondition: __n > 0 2561 // Precondition: size() + __n <= capacity() 2562 // Postcondition: size() == size() + __n 2563 template <class _Allocator> 2564 inline _LIBCPP_INLINE_VISIBILITY 2565 void 2566 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) 2567 { 2568 size_type __old_size = this->__size_; 2569 this->__size_ += __n; 2570 _VSTD::fill_n(__make_iter(__old_size), __n, __x); 2571 } 2572 2573 template <class _Allocator> 2574 template <class _ForwardIterator> 2575 typename enable_if 2576 < 2577 __is_forward_iterator<_ForwardIterator>::value, 2578 void 2579 >::type 2580 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 2581 { 2582 size_type __old_size = this->__size_; 2583 this->__size_ += _VSTD::distance(__first, __last); 2584 _VSTD::copy(__first, __last, __make_iter(__old_size)); 2585 } 2586 2587 template <class _Allocator> 2588 inline _LIBCPP_INLINE_VISIBILITY 2589 vector<bool, _Allocator>::vector() 2590 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 2591 : __begin_(nullptr), 2592 __size_(0), 2593 __cap_alloc_(0) 2594 { 2595 } 2596 2597 template <class _Allocator> 2598 inline _LIBCPP_INLINE_VISIBILITY 2599 vector<bool, _Allocator>::vector(const allocator_type& __a) 2600 #if _LIBCPP_STD_VER <= 14 2601 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 2602 #else 2603 _NOEXCEPT 2604 #endif 2605 : __begin_(nullptr), 2606 __size_(0), 2607 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2608 { 2609 } 2610 2611 template <class _Allocator> 2612 vector<bool, _Allocator>::vector(size_type __n) 2613 : __begin_(nullptr), 2614 __size_(0), 2615 __cap_alloc_(0) 2616 { 2617 if (__n > 0) 2618 { 2619 allocate(__n); 2620 __construct_at_end(__n, false); 2621 } 2622 } 2623 2624 #if _LIBCPP_STD_VER > 11 2625 template <class _Allocator> 2626 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a) 2627 : __begin_(nullptr), 2628 __size_(0), 2629 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2630 { 2631 if (__n > 0) 2632 { 2633 allocate(__n); 2634 __construct_at_end(__n, false); 2635 } 2636 } 2637 #endif 2638 2639 template <class _Allocator> 2640 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 2641 : __begin_(nullptr), 2642 __size_(0), 2643 __cap_alloc_(0) 2644 { 2645 if (__n > 0) 2646 { 2647 allocate(__n); 2648 __construct_at_end(__n, __x); 2649 } 2650 } 2651 2652 template <class _Allocator> 2653 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 2654 : __begin_(nullptr), 2655 __size_(0), 2656 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2657 { 2658 if (__n > 0) 2659 { 2660 allocate(__n); 2661 __construct_at_end(__n, __x); 2662 } 2663 } 2664 2665 template <class _Allocator> 2666 template <class _InputIterator> 2667 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 2668 typename enable_if<__is_input_iterator <_InputIterator>::value && 2669 !__is_forward_iterator<_InputIterator>::value>::type*) 2670 : __begin_(nullptr), 2671 __size_(0), 2672 __cap_alloc_(0) 2673 { 2674 #ifndef _LIBCPP_NO_EXCEPTIONS 2675 try 2676 { 2677 #endif // _LIBCPP_NO_EXCEPTIONS 2678 for (; __first != __last; ++__first) 2679 push_back(*__first); 2680 #ifndef _LIBCPP_NO_EXCEPTIONS 2681 } 2682 catch (...) 2683 { 2684 if (__begin_ != nullptr) 2685 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2686 __invalidate_all_iterators(); 2687 throw; 2688 } 2689 #endif // _LIBCPP_NO_EXCEPTIONS 2690 } 2691 2692 template <class _Allocator> 2693 template <class _InputIterator> 2694 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2695 typename enable_if<__is_input_iterator <_InputIterator>::value && 2696 !__is_forward_iterator<_InputIterator>::value>::type*) 2697 : __begin_(nullptr), 2698 __size_(0), 2699 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2700 { 2701 #ifndef _LIBCPP_NO_EXCEPTIONS 2702 try 2703 { 2704 #endif // _LIBCPP_NO_EXCEPTIONS 2705 for (; __first != __last; ++__first) 2706 push_back(*__first); 2707 #ifndef _LIBCPP_NO_EXCEPTIONS 2708 } 2709 catch (...) 2710 { 2711 if (__begin_ != nullptr) 2712 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2713 __invalidate_all_iterators(); 2714 throw; 2715 } 2716 #endif // _LIBCPP_NO_EXCEPTIONS 2717 } 2718 2719 template <class _Allocator> 2720 template <class _ForwardIterator> 2721 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 2722 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2723 : __begin_(nullptr), 2724 __size_(0), 2725 __cap_alloc_(0) 2726 { 2727 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2728 if (__n > 0) 2729 { 2730 allocate(__n); 2731 __construct_at_end(__first, __last); 2732 } 2733 } 2734 2735 template <class _Allocator> 2736 template <class _ForwardIterator> 2737 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2738 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2739 : __begin_(nullptr), 2740 __size_(0), 2741 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2742 { 2743 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2744 if (__n > 0) 2745 { 2746 allocate(__n); 2747 __construct_at_end(__first, __last); 2748 } 2749 } 2750 2751 #ifndef _LIBCPP_CXX03_LANG 2752 2753 template <class _Allocator> 2754 vector<bool, _Allocator>::vector(initializer_list<value_type> __il) 2755 : __begin_(nullptr), 2756 __size_(0), 2757 __cap_alloc_(0) 2758 { 2759 size_type __n = static_cast<size_type>(__il.size()); 2760 if (__n > 0) 2761 { 2762 allocate(__n); 2763 __construct_at_end(__il.begin(), __il.end()); 2764 } 2765 } 2766 2767 template <class _Allocator> 2768 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 2769 : __begin_(nullptr), 2770 __size_(0), 2771 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2772 { 2773 size_type __n = static_cast<size_type>(__il.size()); 2774 if (__n > 0) 2775 { 2776 allocate(__n); 2777 __construct_at_end(__il.begin(), __il.end()); 2778 } 2779 } 2780 2781 #endif // _LIBCPP_CXX03_LANG 2782 2783 template <class _Allocator> 2784 vector<bool, _Allocator>::~vector() 2785 { 2786 if (__begin_ != nullptr) 2787 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2788 __invalidate_all_iterators(); 2789 } 2790 2791 template <class _Allocator> 2792 vector<bool, _Allocator>::vector(const vector& __v) 2793 : __begin_(nullptr), 2794 __size_(0), 2795 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) 2796 { 2797 if (__v.size() > 0) 2798 { 2799 allocate(__v.size()); 2800 __construct_at_end(__v.begin(), __v.end()); 2801 } 2802 } 2803 2804 template <class _Allocator> 2805 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2806 : __begin_(nullptr), 2807 __size_(0), 2808 __cap_alloc_(0, __a) 2809 { 2810 if (__v.size() > 0) 2811 { 2812 allocate(__v.size()); 2813 __construct_at_end(__v.begin(), __v.end()); 2814 } 2815 } 2816 2817 template <class _Allocator> 2818 vector<bool, _Allocator>& 2819 vector<bool, _Allocator>::operator=(const vector& __v) 2820 { 2821 if (this != &__v) 2822 { 2823 __copy_assign_alloc(__v); 2824 if (__v.__size_) 2825 { 2826 if (__v.__size_ > capacity()) 2827 { 2828 deallocate(); 2829 allocate(__v.__size_); 2830 } 2831 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2832 } 2833 __size_ = __v.__size_; 2834 } 2835 return *this; 2836 } 2837 2838 #ifndef _LIBCPP_CXX03_LANG 2839 2840 template <class _Allocator> 2841 inline _LIBCPP_INLINE_VISIBILITY 2842 vector<bool, _Allocator>::vector(vector&& __v) 2843 #if _LIBCPP_STD_VER > 14 2844 _NOEXCEPT 2845 #else 2846 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 2847 #endif 2848 : __begin_(__v.__begin_), 2849 __size_(__v.__size_), 2850 __cap_alloc_(__v.__cap_alloc_) 2851 { 2852 __v.__begin_ = nullptr; 2853 __v.__size_ = 0; 2854 __v.__cap() = 0; 2855 } 2856 2857 template <class _Allocator> 2858 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a) 2859 : __begin_(nullptr), 2860 __size_(0), 2861 __cap_alloc_(0, __a) 2862 { 2863 if (__a == allocator_type(__v.__alloc())) 2864 { 2865 this->__begin_ = __v.__begin_; 2866 this->__size_ = __v.__size_; 2867 this->__cap() = __v.__cap(); 2868 __v.__begin_ = nullptr; 2869 __v.__cap() = __v.__size_ = 0; 2870 } 2871 else if (__v.size() > 0) 2872 { 2873 allocate(__v.size()); 2874 __construct_at_end(__v.begin(), __v.end()); 2875 } 2876 } 2877 2878 template <class _Allocator> 2879 inline _LIBCPP_INLINE_VISIBILITY 2880 vector<bool, _Allocator>& 2881 vector<bool, _Allocator>::operator=(vector&& __v) 2882 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) 2883 { 2884 __move_assign(__v, integral_constant<bool, 2885 __storage_traits::propagate_on_container_move_assignment::value>()); 2886 return *this; 2887 } 2888 2889 template <class _Allocator> 2890 void 2891 vector<bool, _Allocator>::__move_assign(vector& __c, false_type) 2892 { 2893 if (__alloc() != __c.__alloc()) 2894 assign(__c.begin(), __c.end()); 2895 else 2896 __move_assign(__c, true_type()); 2897 } 2898 2899 template <class _Allocator> 2900 void 2901 vector<bool, _Allocator>::__move_assign(vector& __c, true_type) 2902 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2903 { 2904 deallocate(); 2905 __move_assign_alloc(__c); 2906 this->__begin_ = __c.__begin_; 2907 this->__size_ = __c.__size_; 2908 this->__cap() = __c.__cap(); 2909 __c.__begin_ = nullptr; 2910 __c.__cap() = __c.__size_ = 0; 2911 } 2912 2913 #endif // !_LIBCPP_CXX03_LANG 2914 2915 template <class _Allocator> 2916 void 2917 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) 2918 { 2919 __size_ = 0; 2920 if (__n > 0) 2921 { 2922 size_type __c = capacity(); 2923 if (__n <= __c) 2924 __size_ = __n; 2925 else 2926 { 2927 vector __v(__alloc()); 2928 __v.reserve(__recommend(__n)); 2929 __v.__size_ = __n; 2930 swap(__v); 2931 } 2932 _VSTD::fill_n(begin(), __n, __x); 2933 } 2934 __invalidate_all_iterators(); 2935 } 2936 2937 template <class _Allocator> 2938 template <class _InputIterator> 2939 typename enable_if 2940 < 2941 __is_input_iterator<_InputIterator>::value && 2942 !__is_forward_iterator<_InputIterator>::value, 2943 void 2944 >::type 2945 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2946 { 2947 clear(); 2948 for (; __first != __last; ++__first) 2949 push_back(*__first); 2950 } 2951 2952 template <class _Allocator> 2953 template <class _ForwardIterator> 2954 typename enable_if 2955 < 2956 __is_forward_iterator<_ForwardIterator>::value, 2957 void 2958 >::type 2959 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2960 { 2961 clear(); 2962 difference_type __ns = _VSTD::distance(__first, __last); 2963 _LIBCPP_ASSERT(__ns >= 0, "invalid range specified"); 2964 const size_t __n = static_cast<size_type>(__ns); 2965 if (__n) 2966 { 2967 if (__n > capacity()) 2968 { 2969 deallocate(); 2970 allocate(__n); 2971 } 2972 __construct_at_end(__first, __last); 2973 } 2974 } 2975 2976 template <class _Allocator> 2977 void 2978 vector<bool, _Allocator>::reserve(size_type __n) 2979 { 2980 if (__n > capacity()) 2981 { 2982 vector __v(this->__alloc()); 2983 __v.allocate(__n); 2984 __v.__construct_at_end(this->begin(), this->end()); 2985 swap(__v); 2986 __invalidate_all_iterators(); 2987 } 2988 } 2989 2990 template <class _Allocator> 2991 void 2992 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT 2993 { 2994 if (__external_cap_to_internal(size()) > __cap()) 2995 { 2996 #ifndef _LIBCPP_NO_EXCEPTIONS 2997 try 2998 { 2999 #endif // _LIBCPP_NO_EXCEPTIONS 3000 vector(*this, allocator_type(__alloc())).swap(*this); 3001 #ifndef _LIBCPP_NO_EXCEPTIONS 3002 } 3003 catch (...) 3004 { 3005 } 3006 #endif // _LIBCPP_NO_EXCEPTIONS 3007 } 3008 } 3009 3010 template <class _Allocator> 3011 typename vector<bool, _Allocator>::reference 3012 vector<bool, _Allocator>::at(size_type __n) 3013 { 3014 if (__n >= size()) 3015 this->__throw_out_of_range(); 3016 return (*this)[__n]; 3017 } 3018 3019 template <class _Allocator> 3020 typename vector<bool, _Allocator>::const_reference 3021 vector<bool, _Allocator>::at(size_type __n) const 3022 { 3023 if (__n >= size()) 3024 this->__throw_out_of_range(); 3025 return (*this)[__n]; 3026 } 3027 3028 template <class _Allocator> 3029 void 3030 vector<bool, _Allocator>::push_back(const value_type& __x) 3031 { 3032 if (this->__size_ == this->capacity()) 3033 reserve(__recommend(this->__size_ + 1)); 3034 ++this->__size_; 3035 back() = __x; 3036 } 3037 3038 template <class _Allocator> 3039 typename vector<bool, _Allocator>::iterator 3040 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) 3041 { 3042 iterator __r; 3043 if (size() < capacity()) 3044 { 3045 const_iterator __old_end = end(); 3046 ++__size_; 3047 _VSTD::copy_backward(__position, __old_end, end()); 3048 __r = __const_iterator_cast(__position); 3049 } 3050 else 3051 { 3052 vector __v(__alloc()); 3053 __v.reserve(__recommend(__size_ + 1)); 3054 __v.__size_ = __size_ + 1; 3055 __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3056 _VSTD::copy_backward(__position, cend(), __v.end()); 3057 swap(__v); 3058 } 3059 *__r = __x; 3060 return __r; 3061 } 3062 3063 template <class _Allocator> 3064 typename vector<bool, _Allocator>::iterator 3065 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) 3066 { 3067 iterator __r; 3068 size_type __c = capacity(); 3069 if (__n <= __c && size() <= __c - __n) 3070 { 3071 const_iterator __old_end = end(); 3072 __size_ += __n; 3073 _VSTD::copy_backward(__position, __old_end, end()); 3074 __r = __const_iterator_cast(__position); 3075 } 3076 else 3077 { 3078 vector __v(__alloc()); 3079 __v.reserve(__recommend(__size_ + __n)); 3080 __v.__size_ = __size_ + __n; 3081 __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3082 _VSTD::copy_backward(__position, cend(), __v.end()); 3083 swap(__v); 3084 } 3085 _VSTD::fill_n(__r, __n, __x); 3086 return __r; 3087 } 3088 3089 template <class _Allocator> 3090 template <class _InputIterator> 3091 typename enable_if 3092 < 3093 __is_input_iterator <_InputIterator>::value && 3094 !__is_forward_iterator<_InputIterator>::value, 3095 typename vector<bool, _Allocator>::iterator 3096 >::type 3097 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 3098 { 3099 difference_type __off = __position - begin(); 3100 iterator __p = __const_iterator_cast(__position); 3101 iterator __old_end = end(); 3102 for (; size() != capacity() && __first != __last; ++__first) 3103 { 3104 ++this->__size_; 3105 back() = *__first; 3106 } 3107 vector __v(__alloc()); 3108 if (__first != __last) 3109 { 3110 #ifndef _LIBCPP_NO_EXCEPTIONS 3111 try 3112 { 3113 #endif // _LIBCPP_NO_EXCEPTIONS 3114 __v.assign(__first, __last); 3115 difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 3116 difference_type __old_p = __p - begin(); 3117 reserve(__recommend(size() + __v.size())); 3118 __p = begin() + __old_p; 3119 __old_end = begin() + __old_size; 3120 #ifndef _LIBCPP_NO_EXCEPTIONS 3121 } 3122 catch (...) 3123 { 3124 erase(__old_end, end()); 3125 throw; 3126 } 3127 #endif // _LIBCPP_NO_EXCEPTIONS 3128 } 3129 __p = _VSTD::rotate(__p, __old_end, end()); 3130 insert(__p, __v.begin(), __v.end()); 3131 return begin() + __off; 3132 } 3133 3134 template <class _Allocator> 3135 template <class _ForwardIterator> 3136 typename enable_if 3137 < 3138 __is_forward_iterator<_ForwardIterator>::value, 3139 typename vector<bool, _Allocator>::iterator 3140 >::type 3141 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 3142 { 3143 const difference_type __n_signed = _VSTD::distance(__first, __last); 3144 _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified"); 3145 const size_type __n = static_cast<size_type>(__n_signed); 3146 iterator __r; 3147 size_type __c = capacity(); 3148 if (__n <= __c && size() <= __c - __n) 3149 { 3150 const_iterator __old_end = end(); 3151 __size_ += __n; 3152 _VSTD::copy_backward(__position, __old_end, end()); 3153 __r = __const_iterator_cast(__position); 3154 } 3155 else 3156 { 3157 vector __v(__alloc()); 3158 __v.reserve(__recommend(__size_ + __n)); 3159 __v.__size_ = __size_ + __n; 3160 __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3161 _VSTD::copy_backward(__position, cend(), __v.end()); 3162 swap(__v); 3163 } 3164 _VSTD::copy(__first, __last, __r); 3165 return __r; 3166 } 3167 3168 template <class _Allocator> 3169 inline _LIBCPP_INLINE_VISIBILITY 3170 typename vector<bool, _Allocator>::iterator 3171 vector<bool, _Allocator>::erase(const_iterator __position) 3172 { 3173 iterator __r = __const_iterator_cast(__position); 3174 _VSTD::copy(__position + 1, this->cend(), __r); 3175 --__size_; 3176 return __r; 3177 } 3178 3179 template <class _Allocator> 3180 typename vector<bool, _Allocator>::iterator 3181 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) 3182 { 3183 iterator __r = __const_iterator_cast(__first); 3184 difference_type __d = __last - __first; 3185 _VSTD::copy(__last, this->cend(), __r); 3186 __size_ -= __d; 3187 return __r; 3188 } 3189 3190 template <class _Allocator> 3191 void 3192 vector<bool, _Allocator>::swap(vector& __x) 3193 #if _LIBCPP_STD_VER >= 14 3194 _NOEXCEPT 3195 #else 3196 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3197 __is_nothrow_swappable<allocator_type>::value) 3198 #endif 3199 { 3200 _VSTD::swap(this->__begin_, __x.__begin_); 3201 _VSTD::swap(this->__size_, __x.__size_); 3202 _VSTD::swap(this->__cap(), __x.__cap()); 3203 __swap_allocator(this->__alloc(), __x.__alloc(), 3204 integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>()); 3205 } 3206 3207 template <class _Allocator> 3208 void 3209 vector<bool, _Allocator>::resize(size_type __sz, value_type __x) 3210 { 3211 size_type __cs = size(); 3212 if (__cs < __sz) 3213 { 3214 iterator __r; 3215 size_type __c = capacity(); 3216 size_type __n = __sz - __cs; 3217 if (__n <= __c && __cs <= __c - __n) 3218 { 3219 __r = end(); 3220 __size_ += __n; 3221 } 3222 else 3223 { 3224 vector __v(__alloc()); 3225 __v.reserve(__recommend(__size_ + __n)); 3226 __v.__size_ = __size_ + __n; 3227 __r = _VSTD::copy(cbegin(), cend(), __v.begin()); 3228 swap(__v); 3229 } 3230 _VSTD::fill_n(__r, __n, __x); 3231 } 3232 else 3233 __size_ = __sz; 3234 } 3235 3236 template <class _Allocator> 3237 void 3238 vector<bool, _Allocator>::flip() _NOEXCEPT 3239 { 3240 // do middle whole words 3241 size_type __n = __size_; 3242 __storage_pointer __p = __begin_; 3243 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3244 *__p = ~*__p; 3245 // do last partial word 3246 if (__n > 0) 3247 { 3248 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3249 __storage_type __b = *__p & __m; 3250 *__p &= ~__m; 3251 *__p |= ~__b & __m; 3252 } 3253 } 3254 3255 template <class _Allocator> 3256 bool 3257 vector<bool, _Allocator>::__invariants() const 3258 { 3259 if (this->__begin_ == nullptr) 3260 { 3261 if (this->__size_ != 0 || this->__cap() != 0) 3262 return false; 3263 } 3264 else 3265 { 3266 if (this->__cap() == 0) 3267 return false; 3268 if (this->__size_ > this->capacity()) 3269 return false; 3270 } 3271 return true; 3272 } 3273 3274 template <class _Allocator> 3275 size_t 3276 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT 3277 { 3278 size_t __h = 0; 3279 // do middle whole words 3280 size_type __n = __size_; 3281 __storage_pointer __p = __begin_; 3282 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3283 __h ^= *__p; 3284 // do last partial word 3285 if (__n > 0) 3286 { 3287 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3288 __h ^= *__p & __m; 3289 } 3290 return __h; 3291 } 3292 3293 template <class _Allocator> 3294 struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> > 3295 : public unary_function<vector<bool, _Allocator>, size_t> 3296 { 3297 _LIBCPP_INLINE_VISIBILITY 3298 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT 3299 {return __vec.__hash_code();} 3300 }; 3301 3302 template <class _Tp, class _Allocator> 3303 inline _LIBCPP_INLINE_VISIBILITY 3304 bool 3305 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3306 { 3307 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 3308 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 3309 } 3310 3311 template <class _Tp, class _Allocator> 3312 inline _LIBCPP_INLINE_VISIBILITY 3313 bool 3314 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3315 { 3316 return !(__x == __y); 3317 } 3318 3319 template <class _Tp, class _Allocator> 3320 inline _LIBCPP_INLINE_VISIBILITY 3321 bool 3322 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3323 { 3324 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 3325 } 3326 3327 template <class _Tp, class _Allocator> 3328 inline _LIBCPP_INLINE_VISIBILITY 3329 bool 3330 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3331 { 3332 return __y < __x; 3333 } 3334 3335 template <class _Tp, class _Allocator> 3336 inline _LIBCPP_INLINE_VISIBILITY 3337 bool 3338 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3339 { 3340 return !(__x < __y); 3341 } 3342 3343 template <class _Tp, class _Allocator> 3344 inline _LIBCPP_INLINE_VISIBILITY 3345 bool 3346 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3347 { 3348 return !(__y < __x); 3349 } 3350 3351 template <class _Tp, class _Allocator> 3352 inline _LIBCPP_INLINE_VISIBILITY 3353 void 3354 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) 3355 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3356 { 3357 __x.swap(__y); 3358 } 3359 3360 _LIBCPP_END_NAMESPACE_STD 3361 3362 _LIBCPP_POP_MACROS 3363 3364 #endif // _LIBCPP_VECTOR 3365
