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