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