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