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