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