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