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