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