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 pointer __push_back_slow_path(_Up&& __x); 837 838 template <class... _Args> 839 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 840 inline pointer __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 1612typename vector<_Tp, _Allocator>::pointer 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 return this->__end_; 1622} 1623 1624template <class _Tp, class _Allocator> 1625_LIBCPP_CONSTEXPR_SINCE_CXX20 1626inline _LIBCPP_HIDE_FROM_ABI 1627void 1628vector<_Tp, _Allocator>::push_back(const_reference __x) 1629{ 1630 pointer __end = this->__end_; 1631 if (__end < this->__end_cap()) { 1632 __construct_one_at_end(__x); 1633 ++__end; 1634 } else { 1635 __end = __push_back_slow_path(__x); 1636 } 1637 this->__end_ = __end; 1638} 1639 1640template <class _Tp, class _Allocator> 1641_LIBCPP_CONSTEXPR_SINCE_CXX20 1642inline _LIBCPP_HIDE_FROM_ABI 1643void 1644vector<_Tp, _Allocator>::push_back(value_type&& __x) 1645{ 1646 pointer __end = this->__end_; 1647 if (__end < this->__end_cap()) { 1648 __construct_one_at_end(std::move(__x)); 1649 ++__end; 1650 } else { 1651 __end = __push_back_slow_path(std::move(__x)); 1652 } 1653 this->__end_ = __end; 1654} 1655 1656template <class _Tp, class _Allocator> 1657template <class... _Args> 1658_LIBCPP_CONSTEXPR_SINCE_CXX20 1659typename vector<_Tp, _Allocator>::pointer 1660vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) 1661{ 1662 allocator_type& __a = this->__alloc(); 1663 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1664// __v.emplace_back(std::forward<_Args>(__args)...); 1665 __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Args>(__args)...); 1666 __v.__end_++; 1667 __swap_out_circular_buffer(__v); 1668 return this->__end_; 1669} 1670 1671template <class _Tp, class _Allocator> 1672template <class... _Args> 1673_LIBCPP_CONSTEXPR_SINCE_CXX20 1674inline 1675#if _LIBCPP_STD_VER >= 17 1676typename vector<_Tp, _Allocator>::reference 1677#else 1678void 1679#endif 1680vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1681{ 1682 pointer __end = this->__end_; 1683 if (__end < this->__end_cap()) { 1684 __construct_one_at_end(std::forward<_Args>(__args)...); 1685 ++__end; 1686 } else { 1687 __end = __emplace_back_slow_path(std::forward<_Args>(__args)...); 1688 } 1689 this->__end_ = __end; 1690#if _LIBCPP_STD_VER >= 17 1691 return *(__end - 1); 1692#endif 1693} 1694 1695template <class _Tp, class _Allocator> 1696_LIBCPP_CONSTEXPR_SINCE_CXX20 1697inline 1698void 1699vector<_Tp, _Allocator>::pop_back() 1700{ 1701 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector::pop_back called on an empty vector"); 1702 this->__destruct_at_end(this->__end_ - 1); 1703} 1704 1705template <class _Tp, class _Allocator> 1706_LIBCPP_CONSTEXPR_SINCE_CXX20 1707inline _LIBCPP_HIDE_FROM_ABI 1708typename vector<_Tp, _Allocator>::iterator 1709vector<_Tp, _Allocator>::erase(const_iterator __position) 1710{ 1711 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__position != end(), 1712 "vector::erase(iterator) called with a non-dereferenceable iterator"); 1713 difference_type __ps = __position - cbegin(); 1714 pointer __p = this->__begin_ + __ps; 1715 this->__destruct_at_end(std::move(__p + 1, this->__end_, __p)); 1716 return __make_iter(__p); 1717} 1718 1719template <class _Tp, class _Allocator> 1720_LIBCPP_CONSTEXPR_SINCE_CXX20 1721typename vector<_Tp, _Allocator>::iterator 1722vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) 1723{ 1724 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "vector::erase(first, last) called with invalid range"); 1725 pointer __p = this->__begin_ + (__first - begin()); 1726 if (__first != __last) { 1727 this->__destruct_at_end(std::move(__p + (__last - __first), this->__end_, __p)); 1728 } 1729 return __make_iter(__p); 1730} 1731 1732template <class _Tp, class _Allocator> 1733_LIBCPP_CONSTEXPR_SINCE_CXX20 1734void 1735vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) 1736{ 1737 pointer __old_last = this->__end_; 1738 difference_type __n = __old_last - __to; 1739 { 1740 pointer __i = __from_s + __n; 1741 _ConstructTransaction __tx(*this, __from_e - __i); 1742 for (pointer __pos = __tx.__pos_; __i < __from_e; 1743 ++__i, (void) ++__pos, __tx.__pos_ = __pos) { 1744 __alloc_traits::construct(this->__alloc(), 1745 std::__to_address(__pos), 1746 std::move(*__i)); 1747 } 1748 } 1749 std::move_backward(__from_s, __from_s + __n, __old_last); 1750} 1751 1752template <class _Tp, class _Allocator> 1753_LIBCPP_CONSTEXPR_SINCE_CXX20 1754typename vector<_Tp, _Allocator>::iterator 1755vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) 1756{ 1757 pointer __p = this->__begin_ + (__position - begin()); 1758 // We can't compare unrelated pointers inside constant expressions 1759 if (!__libcpp_is_constant_evaluated() && this->__end_ < this->__end_cap()) 1760 { 1761 if (__p == this->__end_) 1762 { 1763 __construct_one_at_end(__x); 1764 } 1765 else 1766 { 1767 __move_range(__p, this->__end_, __p + 1); 1768 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1769 if (__p <= __xr && __xr < this->__end_) 1770 ++__xr; 1771 *__p = *__xr; 1772 } 1773 } 1774 else 1775 { 1776 allocator_type& __a = this->__alloc(); 1777 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1778 __v.push_back(__x); 1779 __p = __swap_out_circular_buffer(__v, __p); 1780 } 1781 return __make_iter(__p); 1782} 1783 1784template <class _Tp, class _Allocator> 1785_LIBCPP_CONSTEXPR_SINCE_CXX20 1786typename vector<_Tp, _Allocator>::iterator 1787vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) 1788{ 1789 pointer __p = this->__begin_ + (__position - begin()); 1790 if (this->__end_ < this->__end_cap()) 1791 { 1792 if (__p == this->__end_) 1793 { 1794 __construct_one_at_end(std::move(__x)); 1795 } 1796 else 1797 { 1798 __move_range(__p, this->__end_, __p + 1); 1799 *__p = std::move(__x); 1800 } 1801 } 1802 else 1803 { 1804 allocator_type& __a = this->__alloc(); 1805 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1806 __v.push_back(std::move(__x)); 1807 __p = __swap_out_circular_buffer(__v, __p); 1808 } 1809 return __make_iter(__p); 1810} 1811 1812template <class _Tp, class _Allocator> 1813template <class... _Args> 1814_LIBCPP_CONSTEXPR_SINCE_CXX20 1815typename vector<_Tp, _Allocator>::iterator 1816vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) 1817{ 1818 pointer __p = this->__begin_ + (__position - begin()); 1819 if (this->__end_ < this->__end_cap()) 1820 { 1821 if (__p == this->__end_) 1822 { 1823 __construct_one_at_end(std::forward<_Args>(__args)...); 1824 } 1825 else 1826 { 1827 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), std::forward<_Args>(__args)...); 1828 __move_range(__p, this->__end_, __p + 1); 1829 *__p = std::move(__tmp.get()); 1830 } 1831 } 1832 else 1833 { 1834 allocator_type& __a = this->__alloc(); 1835 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1836 __v.emplace_back(std::forward<_Args>(__args)...); 1837 __p = __swap_out_circular_buffer(__v, __p); 1838 } 1839 return __make_iter(__p); 1840} 1841 1842template <class _Tp, class _Allocator> 1843_LIBCPP_CONSTEXPR_SINCE_CXX20 1844typename vector<_Tp, _Allocator>::iterator 1845vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) 1846{ 1847 pointer __p = this->__begin_ + (__position - begin()); 1848 if (__n > 0) 1849 { 1850 // We can't compare unrelated pointers inside constant expressions 1851 if (!__libcpp_is_constant_evaluated() && __n <= static_cast<size_type>(this->__end_cap() - this->__end_)) 1852 { 1853 size_type __old_n = __n; 1854 pointer __old_last = this->__end_; 1855 if (__n > static_cast<size_type>(this->__end_ - __p)) 1856 { 1857 size_type __cx = __n - (this->__end_ - __p); 1858 __construct_at_end(__cx, __x); 1859 __n -= __cx; 1860 } 1861 if (__n > 0) 1862 { 1863 __move_range(__p, __old_last, __p + __old_n); 1864 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1865 if (__p <= __xr && __xr < this->__end_) 1866 __xr += __old_n; 1867 std::fill_n(__p, __n, *__xr); 1868 } 1869 } 1870 else 1871 { 1872 allocator_type& __a = this->__alloc(); 1873 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1874 __v.__construct_at_end(__n, __x); 1875 __p = __swap_out_circular_buffer(__v, __p); 1876 } 1877 } 1878 return __make_iter(__p); 1879} 1880template <class _Tp, class _Allocator> 1881template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 1882 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, 1883 int> > 1884_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator 1885vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 1886{ 1887 return __insert_with_sentinel(__position, __first, __last); 1888} 1889 1890template <class _Tp, class _Allocator> 1891template <class _InputIterator, class _Sentinel> 1892_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 1893typename vector<_Tp, _Allocator>::iterator 1894vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { 1895 difference_type __off = __position - begin(); 1896 pointer __p = this->__begin_ + __off; 1897 allocator_type& __a = this->__alloc(); 1898 pointer __old_last = this->__end_; 1899 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) 1900 { 1901 __construct_one_at_end(*__first); 1902 } 1903 __split_buffer<value_type, allocator_type&> __v(__a); 1904 if (__first != __last) 1905 { 1906#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1907 try 1908 { 1909#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1910 __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last)); 1911 difference_type __old_size = __old_last - this->__begin_; 1912 difference_type __old_p = __p - this->__begin_; 1913 reserve(__recommend(size() + __v.size())); 1914 __p = this->__begin_ + __old_p; 1915 __old_last = this->__begin_ + __old_size; 1916#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1917 } 1918 catch (...) 1919 { 1920 erase(__make_iter(__old_last), end()); 1921 throw; 1922 } 1923#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1924 } 1925 __p = std::rotate(__p, __old_last, this->__end_); 1926 insert(__make_iter(__p), std::make_move_iterator(__v.begin()), 1927 std::make_move_iterator(__v.end())); 1928 return begin() + __off; 1929} 1930 1931template <class _Tp, class _Allocator> 1932template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 1933 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value, 1934 int> > 1935_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator 1936vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 1937{ 1938 return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); 1939} 1940 1941template <class _Tp, class _Allocator> 1942template <class _Iterator, class _Sentinel> 1943_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 1944typename vector<_Tp, _Allocator>::iterator 1945vector<_Tp, _Allocator>::__insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, 1946 difference_type __n) { 1947 auto __insertion_size = __n; 1948 pointer __p = this->__begin_ + (__position - begin()); 1949 if (__n > 0) 1950 { 1951 if (__n <= this->__end_cap() - this->__end_) 1952 { 1953 size_type __old_n = __n; 1954 pointer __old_last = this->__end_; 1955 _Iterator __m = std::next(__first, __n); 1956 difference_type __dx = this->__end_ - __p; 1957 if (__n > __dx) 1958 { 1959 __m = __first; 1960 difference_type __diff = this->__end_ - __p; 1961 std::advance(__m, __diff); 1962 __construct_at_end(__m, __last, __n - __diff); 1963 __n = __dx; 1964 } 1965 if (__n > 0) 1966 { 1967 __move_range(__p, __old_last, __p + __old_n); 1968 std::copy(__first, __m, __p); 1969 } 1970 } 1971 else 1972 { 1973 allocator_type& __a = this->__alloc(); 1974 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1975 __v.__construct_at_end_with_size(__first, __insertion_size); 1976 __p = __swap_out_circular_buffer(__v, __p); 1977 } 1978 } 1979 return __make_iter(__p); 1980} 1981 1982template <class _Tp, class _Allocator> 1983_LIBCPP_CONSTEXPR_SINCE_CXX20 1984void 1985vector<_Tp, _Allocator>::resize(size_type __sz) 1986{ 1987 size_type __cs = size(); 1988 if (__cs < __sz) 1989 this->__append(__sz - __cs); 1990 else if (__cs > __sz) 1991 this->__destruct_at_end(this->__begin_ + __sz); 1992} 1993 1994template <class _Tp, class _Allocator> 1995_LIBCPP_CONSTEXPR_SINCE_CXX20 1996void 1997vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) 1998{ 1999 size_type __cs = size(); 2000 if (__cs < __sz) 2001 this->__append(__sz - __cs, __x); 2002 else if (__cs > __sz) 2003 this->__destruct_at_end(this->__begin_ + __sz); 2004} 2005 2006template <class _Tp, class _Allocator> 2007_LIBCPP_CONSTEXPR_SINCE_CXX20 2008void 2009vector<_Tp, _Allocator>::swap(vector& __x) 2010#if _LIBCPP_STD_VER >= 14 2011 _NOEXCEPT 2012#else 2013 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2014 __is_nothrow_swappable<allocator_type>::value) 2015#endif 2016{ 2017 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(__alloc_traits::propagate_on_container_swap::value || 2018 this->__alloc() == __x.__alloc(), 2019 "vector::swap: Either propagate_on_container_swap must be true" 2020 " or the allocators must compare equal"); 2021 std::swap(this->__begin_, __x.__begin_); 2022 std::swap(this->__end_, __x.__end_); 2023 std::swap(this->__end_cap(), __x.__end_cap()); 2024 std::__swap_allocator(this->__alloc(), __x.__alloc(), 2025 integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>()); 2026} 2027 2028template <class _Tp, class _Allocator> 2029_LIBCPP_CONSTEXPR_SINCE_CXX20 2030bool 2031vector<_Tp, _Allocator>::__invariants() const 2032{ 2033 if (this->__begin_ == nullptr) 2034 { 2035 if (this->__end_ != nullptr || this->__end_cap() != nullptr) 2036 return false; 2037 } 2038 else 2039 { 2040 if (this->__begin_ > this->__end_) 2041 return false; 2042 if (this->__begin_ == this->__end_cap()) 2043 return false; 2044 if (this->__end_ > this->__end_cap()) 2045 return false; 2046 } 2047 return true; 2048} 2049 2050// vector<bool> 2051 2052template <class _Allocator> class vector<bool, _Allocator>; 2053 2054template <class _Allocator> struct hash<vector<bool, _Allocator> >; 2055 2056template <class _Allocator> 2057struct __has_storage_type<vector<bool, _Allocator> > 2058{ 2059 static const bool value = true; 2060}; 2061 2062template <class _Allocator> 2063class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> 2064{ 2065public: 2066 typedef vector __self; 2067 typedef bool value_type; 2068 typedef _Allocator allocator_type; 2069 typedef allocator_traits<allocator_type> __alloc_traits; 2070 typedef typename __alloc_traits::size_type size_type; 2071 typedef typename __alloc_traits::difference_type difference_type; 2072 typedef size_type __storage_type; 2073 typedef __bit_iterator<vector, false> pointer; 2074 typedef __bit_iterator<vector, true> const_pointer; 2075 typedef pointer iterator; 2076 typedef const_pointer const_iterator; 2077 typedef std::reverse_iterator<iterator> reverse_iterator; 2078 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 2079 2080private: 2081 typedef __rebind_alloc<__alloc_traits, __storage_type> __storage_allocator; 2082 typedef allocator_traits<__storage_allocator> __storage_traits; 2083 typedef typename __storage_traits::pointer __storage_pointer; 2084 typedef typename __storage_traits::const_pointer __const_storage_pointer; 2085 2086 __storage_pointer __begin_; 2087 size_type __size_; 2088 __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 2089public: 2090 typedef __bit_reference<vector> reference; 2091#ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL 2092 using const_reference = bool; 2093#else 2094 typedef __bit_const_reference<vector> const_reference; 2095#endif 2096private: 2097 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2098 size_type& __cap() _NOEXCEPT 2099 {return __cap_alloc_.first();} 2100 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2101 const size_type& __cap() const _NOEXCEPT 2102 {return __cap_alloc_.first();} 2103 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2104 __storage_allocator& __alloc() _NOEXCEPT 2105 {return __cap_alloc_.second();} 2106 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2107 const __storage_allocator& __alloc() const _NOEXCEPT 2108 {return __cap_alloc_.second();} 2109 2110 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 2111 2112 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2113 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT 2114 {return __n * __bits_per_word;} 2115 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2116 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT 2117 {return (__n - 1) / __bits_per_word + 1;} 2118 2119public: 2120 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2121 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 2122 2123 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(const allocator_type& __a) 2124#if _LIBCPP_STD_VER <= 14 2125 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value); 2126#else 2127 _NOEXCEPT; 2128#endif 2129 2130private: 2131 class __destroy_vector { 2132 public: 2133 _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {} 2134 2135 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() { 2136 if (__vec_.__begin_ != nullptr) 2137 __storage_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.__cap()); 2138 } 2139 2140 private: 2141 vector& __vec_; 2142 }; 2143 2144public: 2145 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 ~vector() { __destroy_vector(*this)(); } 2146 2147 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n); 2148#if _LIBCPP_STD_VER >= 14 2149 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n, const allocator_type& __a); 2150#endif 2151 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v); 2152 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v, const allocator_type& __a); 2153 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 2154 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last); 2155 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 2156 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a); 2157 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 2158 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last); 2159 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 2160 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a); 2161 2162#if _LIBCPP_STD_VER >= 23 2163 template <_ContainerCompatibleRange<bool> _Range> 2164 _LIBCPP_HIDE_FROM_ABI constexpr 2165 vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) 2166 : __begin_(nullptr), 2167 __size_(0), 2168 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { 2169 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { 2170 auto __n = static_cast<size_type>(ranges::distance(__range)); 2171 __init_with_size(ranges::begin(__range), ranges::end(__range), __n); 2172 2173 } else { 2174 __init_with_sentinel(ranges::begin(__range), ranges::end(__range)); 2175 } 2176 } 2177#endif 2178 2179 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v); 2180 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a); 2181 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v); 2182 2183#ifndef _LIBCPP_CXX03_LANG 2184 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il); 2185 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il, const allocator_type& __a); 2186 2187 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2188 vector& operator=(initializer_list<value_type> __il) 2189 {assign(__il.begin(), __il.end()); return *this;} 2190 2191#endif // !_LIBCPP_CXX03_LANG 2192 2193 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2194 vector(vector&& __v) 2195#if _LIBCPP_STD_VER >= 17 2196 noexcept; 2197#else 2198 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 2199#endif 2200 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(vector&& __v, const __type_identity_t<allocator_type>& __a); 2201 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2202 vector& operator=(vector&& __v) 2203 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); 2204 2205 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 2206 void 2207 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_InputIterator __first, _InputIterator __last); 2208 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 2209 void 2210 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last); 2211 2212#if _LIBCPP_STD_VER >= 23 2213 template <_ContainerCompatibleRange<bool> _Range> 2214 _LIBCPP_HIDE_FROM_ABI 2215 constexpr void assign_range(_Range&& __range) { 2216 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { 2217 auto __n = static_cast<size_type>(ranges::distance(__range)); 2218 __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); 2219 2220 } else { 2221 __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); 2222 } 2223 } 2224#endif 2225 2226 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x); 2227 2228#ifndef _LIBCPP_CXX03_LANG 2229 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2230 void assign(initializer_list<value_type> __il) 2231 {assign(__il.begin(), __il.end());} 2232#endif 2233 2234 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 allocator_type get_allocator() const _NOEXCEPT 2235 {return allocator_type(this->__alloc());} 2236 2237 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT; 2238 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2239 size_type capacity() const _NOEXCEPT 2240 {return __internal_cap_to_external(__cap());} 2241 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2242 size_type size() const _NOEXCEPT 2243 {return __size_;} 2244 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2245 bool empty() const _NOEXCEPT 2246 {return __size_ == 0;} 2247 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __n); 2248 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT; 2249 2250 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2251 iterator begin() _NOEXCEPT 2252 {return __make_iter(0);} 2253 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2254 const_iterator begin() const _NOEXCEPT 2255 {return __make_iter(0);} 2256 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2257 iterator end() _NOEXCEPT 2258 {return __make_iter(__size_);} 2259 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2260 const_iterator end() const _NOEXCEPT 2261 {return __make_iter(__size_);} 2262 2263 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2264 reverse_iterator rbegin() _NOEXCEPT 2265 {return reverse_iterator(end());} 2266 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2267 const_reverse_iterator rbegin() const _NOEXCEPT 2268 {return const_reverse_iterator(end());} 2269 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2270 reverse_iterator rend() _NOEXCEPT 2271 {return reverse_iterator(begin());} 2272 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2273 const_reverse_iterator rend() const _NOEXCEPT 2274 {return const_reverse_iterator(begin());} 2275 2276 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2277 const_iterator cbegin() const _NOEXCEPT 2278 {return __make_iter(0);} 2279 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2280 const_iterator cend() const _NOEXCEPT 2281 {return __make_iter(__size_);} 2282 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2283 const_reverse_iterator crbegin() const _NOEXCEPT 2284 {return rbegin();} 2285 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2286 const_reverse_iterator crend() const _NOEXCEPT 2287 {return rend();} 2288 2289 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __n) {return __make_ref(__n);} 2290 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference operator[](size_type __n) const {return __make_ref(__n);} 2291 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n); 2292 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const; 2293 2294 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() {return __make_ref(0);} 2295 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const {return __make_ref(0);} 2296 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() {return __make_ref(__size_ - 1);} 2297 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const {return __make_ref(__size_ - 1);} 2298 2299 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(const value_type& __x); 2300#if _LIBCPP_STD_VER >= 14 2301 template <class... _Args> 2302#if _LIBCPP_STD_VER >= 17 2303 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference emplace_back(_Args&&... __args) 2304#else 2305 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args) 2306#endif 2307 { 2308 push_back ( value_type ( std::forward<_Args>(__args)... )); 2309#if _LIBCPP_STD_VER >= 17 2310 return this->back(); 2311#endif 2312 } 2313#endif 2314 2315#if _LIBCPP_STD_VER >= 23 2316 template <_ContainerCompatibleRange<bool> _Range> 2317 _LIBCPP_HIDE_FROM_ABI 2318 constexpr void append_range(_Range&& __range) { 2319 insert_range(end(), std::forward<_Range>(__range)); 2320 } 2321#endif 2322 2323 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() {--__size_;} 2324 2325#if _LIBCPP_STD_VER >= 14 2326 template <class... _Args> 2327 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator emplace(const_iterator __position, _Args&&... __args) 2328 { return insert ( __position, value_type ( std::forward<_Args>(__args)... )); } 2329#endif 2330 2331 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, const value_type& __x); 2332 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, size_type __n, const value_type& __x); 2333 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 2334 iterator 2335 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 2336 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 2337 iterator 2338 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 2339 2340#if _LIBCPP_STD_VER >= 23 2341 template <_ContainerCompatibleRange<bool> _Range> 2342 _LIBCPP_HIDE_FROM_ABI 2343 constexpr iterator insert_range(const_iterator __position, _Range&& __range) { 2344 if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { 2345 auto __n = static_cast<size_type>(ranges::distance(__range)); 2346 return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n); 2347 2348 } else { 2349 return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); 2350 } 2351 } 2352#endif 2353 2354#ifndef _LIBCPP_CXX03_LANG 2355 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2356 iterator insert(const_iterator __position, initializer_list<value_type> __il) 2357 {return insert(__position, __il.begin(), __il.end());} 2358#endif 2359 2360 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __position); 2361 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __first, const_iterator __last); 2362 2363 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2364 void clear() _NOEXCEPT {__size_ = 0;} 2365 2366 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(vector&) 2367#if _LIBCPP_STD_VER >= 14 2368 _NOEXCEPT; 2369#else 2370 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2371 __is_nothrow_swappable<allocator_type>::value); 2372#endif 2373 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void swap(reference __x, reference __y) _NOEXCEPT { std::swap(__x, __y); } 2374 2375 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __sz, value_type __x = false); 2376 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT; 2377 2378 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const; 2379 2380private: 2381 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI 2382 void __throw_length_error() const { 2383 std::__throw_length_error("vector"); 2384 } 2385 2386 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI 2387 void __throw_out_of_range() const { 2388 std::__throw_out_of_range("vector"); 2389 } 2390 2391 template <class _InputIterator, class _Sentinel> 2392 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2393 void __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) { 2394 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 2395 2396 if (__n > 0) { 2397 __vallocate(__n); 2398 __construct_at_end(std::move(__first), std::move(__last), __n); 2399 } 2400 2401 __guard.__complete(); 2402 } 2403 2404 template <class _InputIterator, class _Sentinel> 2405 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2406 void __init_with_sentinel(_InputIterator __first, _Sentinel __last) { 2407#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2408 try { 2409#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2410 for (; __first != __last; ++__first) 2411 push_back(*__first); 2412#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2413 } catch (...) { 2414 if (__begin_ != nullptr) 2415 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2416 throw; 2417 } 2418#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2419 } 2420 2421 template <class _Iterator, class _Sentinel> 2422 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 2423 void __assign_with_sentinel(_Iterator __first, _Sentinel __last); 2424 2425 template <class _ForwardIterator, class _Sentinel> 2426 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 2427 void __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns); 2428 2429 template <class _InputIterator, class _Sentinel> 2430 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 2431 iterator __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); 2432 2433 template <class _Iterator, class _Sentinel> 2434 _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 2435 iterator __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); 2436 2437 // Allocate space for __n objects 2438 // throws length_error if __n > max_size() 2439 // throws (probably bad_alloc) if memory run out 2440 // Precondition: __begin_ == __end_ == __cap() == 0 2441 // Precondition: __n > 0 2442 // Postcondition: capacity() >= __n 2443 // Postcondition: size() == 0 2444 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vallocate(size_type __n) { 2445 if (__n > max_size()) 2446 __throw_length_error(); 2447 auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n)); 2448 __begin_ = __allocation.ptr; 2449 __size_ = 0; 2450 __cap() = __allocation.count; 2451 if (__libcpp_is_constant_evaluated()) { 2452 for (size_type __i = 0; __i != __cap(); ++__i) 2453 std::__construct_at(std::__to_address(__begin_) + __i); 2454 } 2455 } 2456 2457 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vdeallocate() _NOEXCEPT; 2458 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2459 static size_type __align_it(size_type __new_size) _NOEXCEPT 2460 {return (__new_size + (__bits_per_word-1)) & ~((size_type)__bits_per_word-1);} 2461 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const; 2462 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __construct_at_end(size_type __n, bool __x); 2463 template <class _InputIterator, class _Sentinel> 2464 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2465 void __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n); 2466 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __append(size_type __n, const_reference __x); 2467 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2468 reference __make_ref(size_type __pos) _NOEXCEPT 2469 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2470 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2471 const_reference __make_ref(size_type __pos) const _NOEXCEPT { 2472 return __bit_const_reference<vector>(__begin_ + __pos / __bits_per_word, 2473 __storage_type(1) << __pos % __bits_per_word); 2474 } 2475 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2476 iterator __make_iter(size_type __pos) _NOEXCEPT 2477 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2478 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2479 const_iterator __make_iter(size_type __pos) const _NOEXCEPT 2480 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2481 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2482 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT 2483 {return begin() + (__p - cbegin());} 2484 2485 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2486 void __copy_assign_alloc(const vector& __v) 2487 {__copy_assign_alloc(__v, integral_constant<bool, 2488 __storage_traits::propagate_on_container_copy_assignment::value>());} 2489 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2490 void __copy_assign_alloc(const vector& __c, true_type) 2491 { 2492 if (__alloc() != __c.__alloc()) 2493 __vdeallocate(); 2494 __alloc() = __c.__alloc(); 2495 } 2496 2497 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2498 void __copy_assign_alloc(const vector&, false_type) 2499 {} 2500 2501 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, false_type); 2502 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, true_type) 2503 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 2504 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2505 void __move_assign_alloc(vector& __c) 2506 _NOEXCEPT_( 2507 !__storage_traits::propagate_on_container_move_assignment::value || 2508 is_nothrow_move_assignable<allocator_type>::value) 2509 {__move_assign_alloc(__c, integral_constant<bool, 2510 __storage_traits::propagate_on_container_move_assignment::value>());} 2511 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2512 void __move_assign_alloc(vector& __c, true_type) 2513 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2514 { 2515 __alloc() = std::move(__c.__alloc()); 2516 } 2517 2518 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2519 void __move_assign_alloc(vector&, false_type) 2520 _NOEXCEPT 2521 {} 2522 2523 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t __hash_code() const _NOEXCEPT; 2524 2525 friend class __bit_reference<vector>; 2526 friend class __bit_const_reference<vector>; 2527 friend class __bit_iterator<vector, false>; 2528 friend class __bit_iterator<vector, true>; 2529 friend struct __bit_array<vector>; 2530 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>; 2531}; 2532 2533template <class _Allocator> 2534_LIBCPP_CONSTEXPR_SINCE_CXX20 void 2535vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT 2536{ 2537 if (this->__begin_ != nullptr) 2538 { 2539 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 2540 this->__begin_ = nullptr; 2541 this->__size_ = this->__cap() = 0; 2542 } 2543} 2544 2545template <class _Allocator> 2546_LIBCPP_CONSTEXPR_SINCE_CXX20 2547typename vector<bool, _Allocator>::size_type 2548vector<bool, _Allocator>::max_size() const _NOEXCEPT 2549{ 2550 size_type __amax = __storage_traits::max_size(__alloc()); 2551 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 2552 if (__nmax / __bits_per_word <= __amax) 2553 return __nmax; 2554 return __internal_cap_to_external(__amax); 2555} 2556 2557// Precondition: __new_size > capacity() 2558template <class _Allocator> 2559inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2560typename vector<bool, _Allocator>::size_type 2561vector<bool, _Allocator>::__recommend(size_type __new_size) const 2562{ 2563 const size_type __ms = max_size(); 2564 if (__new_size > __ms) 2565 this->__throw_length_error(); 2566 const size_type __cap = capacity(); 2567 if (__cap >= __ms / 2) 2568 return __ms; 2569 return std::max(2 * __cap, __align_it(__new_size)); 2570} 2571 2572// Default constructs __n objects starting at __end_ 2573// Precondition: __n > 0 2574// Precondition: size() + __n <= capacity() 2575// Postcondition: size() == size() + __n 2576template <class _Allocator> 2577inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2578void 2579vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) 2580{ 2581 size_type __old_size = this->__size_; 2582 this->__size_ += __n; 2583 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) 2584 { 2585 if (this->__size_ <= __bits_per_word) 2586 this->__begin_[0] = __storage_type(0); 2587 else 2588 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); 2589 } 2590 std::fill_n(__make_iter(__old_size), __n, __x); 2591} 2592 2593template <class _Allocator> 2594template <class _InputIterator, class _Sentinel> 2595_LIBCPP_CONSTEXPR_SINCE_CXX20 2596void vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) { 2597 size_type __old_size = this->__size_; 2598 this->__size_ += __n; 2599 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) 2600 { 2601 if (this->__size_ <= __bits_per_word) 2602 this->__begin_[0] = __storage_type(0); 2603 else 2604 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); 2605 } 2606 std::__copy<_ClassicAlgPolicy>(__first, __last, __make_iter(__old_size)); 2607} 2608 2609template <class _Allocator> 2610inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2611vector<bool, _Allocator>::vector() 2612 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 2613 : __begin_(nullptr), 2614 __size_(0), 2615 __cap_alloc_(0, __default_init_tag()) 2616{ 2617} 2618 2619template <class _Allocator> 2620inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2621vector<bool, _Allocator>::vector(const allocator_type& __a) 2622#if _LIBCPP_STD_VER <= 14 2623 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) 2624#else 2625 _NOEXCEPT 2626#endif 2627 : __begin_(nullptr), 2628 __size_(0), 2629 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2630{ 2631} 2632 2633template <class _Allocator> 2634_LIBCPP_CONSTEXPR_SINCE_CXX20 2635vector<bool, _Allocator>::vector(size_type __n) 2636 : __begin_(nullptr), 2637 __size_(0), 2638 __cap_alloc_(0, __default_init_tag()) 2639{ 2640 if (__n > 0) 2641 { 2642 __vallocate(__n); 2643 __construct_at_end(__n, false); 2644 } 2645} 2646 2647#if _LIBCPP_STD_VER >= 14 2648template <class _Allocator> 2649_LIBCPP_CONSTEXPR_SINCE_CXX20 2650vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a) 2651 : __begin_(nullptr), 2652 __size_(0), 2653 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2654{ 2655 if (__n > 0) 2656 { 2657 __vallocate(__n); 2658 __construct_at_end(__n, false); 2659 } 2660} 2661#endif 2662 2663template <class _Allocator> 2664_LIBCPP_CONSTEXPR_SINCE_CXX20 2665vector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 2666 : __begin_(nullptr), 2667 __size_(0), 2668 __cap_alloc_(0, __default_init_tag()) 2669{ 2670 if (__n > 0) 2671 { 2672 __vallocate(__n); 2673 __construct_at_end(__n, __x); 2674 } 2675} 2676 2677template <class _Allocator> 2678_LIBCPP_CONSTEXPR_SINCE_CXX20 2679vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 2680 : __begin_(nullptr), 2681 __size_(0), 2682 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2683{ 2684 if (__n > 0) 2685 { 2686 __vallocate(__n); 2687 __construct_at_end(__n, __x); 2688 } 2689} 2690 2691template <class _Allocator> 2692template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 2693_LIBCPP_CONSTEXPR_SINCE_CXX20 2694vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last) 2695 : __begin_(nullptr), 2696 __size_(0), 2697 __cap_alloc_(0, __default_init_tag()) 2698{ 2699 __init_with_sentinel(__first, __last); 2700} 2701 2702template <class _Allocator> 2703template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 2704_LIBCPP_CONSTEXPR_SINCE_CXX20 2705vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a) 2706 : __begin_(nullptr), 2707 __size_(0), 2708 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2709{ 2710 __init_with_sentinel(__first, __last); 2711} 2712 2713template <class _Allocator> 2714template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 2715_LIBCPP_CONSTEXPR_SINCE_CXX20 2716vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last) 2717 : __begin_(nullptr), 2718 __size_(0), 2719 __cap_alloc_(0, __default_init_tag()) 2720{ 2721 auto __n = static_cast<size_type>(std::distance(__first, __last)); 2722 __init_with_size(__first, __last, __n); 2723} 2724 2725template <class _Allocator> 2726template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 2727_LIBCPP_CONSTEXPR_SINCE_CXX20 2728vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a) 2729 : __begin_(nullptr), 2730 __size_(0), 2731 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2732{ 2733 auto __n = static_cast<size_type>(std::distance(__first, __last)); 2734 __init_with_size(__first, __last, __n); 2735} 2736 2737#ifndef _LIBCPP_CXX03_LANG 2738 2739template <class _Allocator> 2740_LIBCPP_CONSTEXPR_SINCE_CXX20 2741vector<bool, _Allocator>::vector(initializer_list<value_type> __il) 2742 : __begin_(nullptr), 2743 __size_(0), 2744 __cap_alloc_(0, __default_init_tag()) 2745{ 2746 size_type __n = static_cast<size_type>(__il.size()); 2747 if (__n > 0) 2748 { 2749 __vallocate(__n); 2750 __construct_at_end(__il.begin(), __il.end(), __n); 2751 } 2752} 2753 2754template <class _Allocator> 2755_LIBCPP_CONSTEXPR_SINCE_CXX20 2756vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 2757 : __begin_(nullptr), 2758 __size_(0), 2759 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2760{ 2761 size_type __n = static_cast<size_type>(__il.size()); 2762 if (__n > 0) 2763 { 2764 __vallocate(__n); 2765 __construct_at_end(__il.begin(), __il.end(), __n); 2766 } 2767} 2768 2769#endif // _LIBCPP_CXX03_LANG 2770 2771template <class _Allocator> 2772_LIBCPP_CONSTEXPR_SINCE_CXX20 2773vector<bool, _Allocator>::vector(const vector& __v) 2774 : __begin_(nullptr), 2775 __size_(0), 2776 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) 2777{ 2778 if (__v.size() > 0) 2779 { 2780 __vallocate(__v.size()); 2781 __construct_at_end(__v.begin(), __v.end(), __v.size()); 2782 } 2783} 2784 2785template <class _Allocator> 2786_LIBCPP_CONSTEXPR_SINCE_CXX20 2787vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2788 : __begin_(nullptr), 2789 __size_(0), 2790 __cap_alloc_(0, __a) 2791{ 2792 if (__v.size() > 0) 2793 { 2794 __vallocate(__v.size()); 2795 __construct_at_end(__v.begin(), __v.end(), __v.size()); 2796 } 2797} 2798 2799template <class _Allocator> 2800_LIBCPP_CONSTEXPR_SINCE_CXX20 2801vector<bool, _Allocator>& 2802vector<bool, _Allocator>::operator=(const vector& __v) 2803{ 2804 if (this != std::addressof(__v)) 2805 { 2806 __copy_assign_alloc(__v); 2807 if (__v.__size_) 2808 { 2809 if (__v.__size_ > capacity()) 2810 { 2811 __vdeallocate(); 2812 __vallocate(__v.__size_); 2813 } 2814 std::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2815 } 2816 __size_ = __v.__size_; 2817 } 2818 return *this; 2819} 2820 2821template <class _Allocator> 2822inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(vector&& __v) 2823#if _LIBCPP_STD_VER >= 17 2824 _NOEXCEPT 2825#else 2826 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 2827#endif 2828 : __begin_(__v.__begin_), 2829 __size_(__v.__size_), 2830 __cap_alloc_(std::move(__v.__cap_alloc_)) { 2831 __v.__begin_ = nullptr; 2832 __v.__size_ = 0; 2833 __v.__cap() = 0; 2834} 2835 2836template <class _Allocator> 2837_LIBCPP_CONSTEXPR_SINCE_CXX20 2838vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a) 2839 : __begin_(nullptr), 2840 __size_(0), 2841 __cap_alloc_(0, __a) 2842{ 2843 if (__a == allocator_type(__v.__alloc())) 2844 { 2845 this->__begin_ = __v.__begin_; 2846 this->__size_ = __v.__size_; 2847 this->__cap() = __v.__cap(); 2848 __v.__begin_ = nullptr; 2849 __v.__cap() = __v.__size_ = 0; 2850 } 2851 else if (__v.size() > 0) 2852 { 2853 __vallocate(__v.size()); 2854 __construct_at_end(__v.begin(), __v.end(), __v.size()); 2855 } 2856} 2857 2858template <class _Allocator> 2859inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 2860vector<bool, _Allocator>& 2861vector<bool, _Allocator>::operator=(vector&& __v) 2862 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) 2863{ 2864 __move_assign(__v, integral_constant<bool, 2865 __storage_traits::propagate_on_container_move_assignment::value>()); 2866 return *this; 2867} 2868 2869template <class _Allocator> 2870_LIBCPP_CONSTEXPR_SINCE_CXX20 void 2871vector<bool, _Allocator>::__move_assign(vector& __c, false_type) 2872{ 2873 if (__alloc() != __c.__alloc()) 2874 assign(__c.begin(), __c.end()); 2875 else 2876 __move_assign(__c, true_type()); 2877} 2878 2879template <class _Allocator> 2880_LIBCPP_CONSTEXPR_SINCE_CXX20 void 2881vector<bool, _Allocator>::__move_assign(vector& __c, true_type) 2882 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2883{ 2884 __vdeallocate(); 2885 __move_assign_alloc(__c); 2886 this->__begin_ = __c.__begin_; 2887 this->__size_ = __c.__size_; 2888 this->__cap() = __c.__cap(); 2889 __c.__begin_ = nullptr; 2890 __c.__cap() = __c.__size_ = 0; 2891} 2892 2893template <class _Allocator> 2894_LIBCPP_CONSTEXPR_SINCE_CXX20 void 2895vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) 2896{ 2897 __size_ = 0; 2898 if (__n > 0) 2899 { 2900 size_type __c = capacity(); 2901 if (__n <= __c) 2902 __size_ = __n; 2903 else 2904 { 2905 vector __v(get_allocator()); 2906 __v.reserve(__recommend(__n)); 2907 __v.__size_ = __n; 2908 swap(__v); 2909 } 2910 std::fill_n(begin(), __n, __x); 2911 } 2912} 2913 2914template <class _Allocator> 2915template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 2916_LIBCPP_CONSTEXPR_SINCE_CXX20 2917void 2918vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2919{ 2920 __assign_with_sentinel(__first, __last); 2921} 2922 2923template <class _Allocator> 2924template <class _Iterator, class _Sentinel> 2925_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 2926void vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { 2927 clear(); 2928 for (; __first != __last; ++__first) 2929 push_back(*__first); 2930} 2931 2932template <class _Allocator> 2933template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 2934_LIBCPP_CONSTEXPR_SINCE_CXX20 2935void 2936vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2937{ 2938 __assign_with_size(__first, __last, std::distance(__first, __last)); 2939} 2940 2941template <class _Allocator> 2942template <class _ForwardIterator, class _Sentinel> 2943_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 2944void vector<bool, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns) { 2945 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__ns >= 0, "invalid range specified"); 2946 2947 clear(); 2948 2949 const size_t __n = static_cast<size_type>(__ns); 2950 if (__n) 2951 { 2952 if (__n > capacity()) 2953 { 2954 __vdeallocate(); 2955 __vallocate(__n); 2956 } 2957 __construct_at_end(__first, __last, __n); 2958 } 2959} 2960 2961template <class _Allocator> 2962_LIBCPP_CONSTEXPR_SINCE_CXX20 void 2963vector<bool, _Allocator>::reserve(size_type __n) 2964{ 2965 if (__n > capacity()) 2966 { 2967 if (__n > max_size()) 2968 this->__throw_length_error(); 2969 vector __v(this->get_allocator()); 2970 __v.__vallocate(__n); 2971 __v.__construct_at_end(this->begin(), this->end(), this->size()); 2972 swap(__v); 2973 } 2974} 2975 2976template <class _Allocator> 2977_LIBCPP_CONSTEXPR_SINCE_CXX20 void 2978vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT 2979{ 2980 if (__external_cap_to_internal(size()) > __cap()) 2981 { 2982#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2983 try 2984 { 2985#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2986 vector(*this, allocator_type(__alloc())).swap(*this); 2987#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2988 } 2989 catch (...) 2990 { 2991 } 2992#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2993 } 2994} 2995 2996template <class _Allocator> 2997typename vector<bool, _Allocator>::reference 2998vector<bool, _Allocator>::at(size_type __n) 2999{ 3000 if (__n >= size()) 3001 this->__throw_out_of_range(); 3002 return (*this)[__n]; 3003} 3004 3005template <class _Allocator> 3006typename vector<bool, _Allocator>::const_reference 3007vector<bool, _Allocator>::at(size_type __n) const 3008{ 3009 if (__n >= size()) 3010 this->__throw_out_of_range(); 3011 return (*this)[__n]; 3012} 3013 3014template <class _Allocator> 3015_LIBCPP_CONSTEXPR_SINCE_CXX20 void 3016vector<bool, _Allocator>::push_back(const value_type& __x) 3017{ 3018 if (this->__size_ == this->capacity()) 3019 reserve(__recommend(this->__size_ + 1)); 3020 ++this->__size_; 3021 back() = __x; 3022} 3023 3024template <class _Allocator> 3025_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator 3026vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) 3027{ 3028 iterator __r; 3029 if (size() < capacity()) 3030 { 3031 const_iterator __old_end = end(); 3032 ++__size_; 3033 std::copy_backward(__position, __old_end, end()); 3034 __r = __const_iterator_cast(__position); 3035 } 3036 else 3037 { 3038 vector __v(get_allocator()); 3039 __v.reserve(__recommend(__size_ + 1)); 3040 __v.__size_ = __size_ + 1; 3041 __r = std::copy(cbegin(), __position, __v.begin()); 3042 std::copy_backward(__position, cend(), __v.end()); 3043 swap(__v); 3044 } 3045 *__r = __x; 3046 return __r; 3047} 3048 3049template <class _Allocator> 3050_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator 3051vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) 3052{ 3053 iterator __r; 3054 size_type __c = capacity(); 3055 if (__n <= __c && size() <= __c - __n) 3056 { 3057 const_iterator __old_end = end(); 3058 __size_ += __n; 3059 std::copy_backward(__position, __old_end, end()); 3060 __r = __const_iterator_cast(__position); 3061 } 3062 else 3063 { 3064 vector __v(get_allocator()); 3065 __v.reserve(__recommend(__size_ + __n)); 3066 __v.__size_ = __size_ + __n; 3067 __r = std::copy(cbegin(), __position, __v.begin()); 3068 std::copy_backward(__position, cend(), __v.end()); 3069 swap(__v); 3070 } 3071 std::fill_n(__r, __n, __x); 3072 return __r; 3073} 3074 3075template <class _Allocator> 3076template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 3077_LIBCPP_CONSTEXPR_SINCE_CXX20 3078typename vector<bool, _Allocator>::iterator 3079vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 3080{ 3081 return __insert_with_sentinel(__position, __first, __last); 3082} 3083 3084template <class _Allocator> 3085template <class _InputIterator, class _Sentinel> 3086_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 3087typename vector<bool, _Allocator>::iterator 3088vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { 3089 difference_type __off = __position - begin(); 3090 iterator __p = __const_iterator_cast(__position); 3091 iterator __old_end = end(); 3092 for (; size() != capacity() && __first != __last; ++__first) 3093 { 3094 ++this->__size_; 3095 back() = *__first; 3096 } 3097 vector __v(get_allocator()); 3098 if (__first != __last) 3099 { 3100#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 3101 try 3102 { 3103#endif // _LIBCPP_HAS_NO_EXCEPTIONS 3104 __v.__assign_with_sentinel(std::move(__first), std::move(__last)); 3105 difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 3106 difference_type __old_p = __p - begin(); 3107 reserve(__recommend(size() + __v.size())); 3108 __p = begin() + __old_p; 3109 __old_end = begin() + __old_size; 3110#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 3111 } 3112 catch (...) 3113 { 3114 erase(__old_end, end()); 3115 throw; 3116 } 3117#endif // _LIBCPP_HAS_NO_EXCEPTIONS 3118 } 3119 __p = std::rotate(__p, __old_end, end()); 3120 insert(__p, __v.begin(), __v.end()); 3121 return begin() + __off; 3122} 3123 3124template <class _Allocator> 3125template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 3126_LIBCPP_CONSTEXPR_SINCE_CXX20 3127typename vector<bool, _Allocator>::iterator 3128vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 3129{ 3130 return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); 3131} 3132 3133template <class _Allocator> 3134template <class _ForwardIterator, class _Sentinel> 3135_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI 3136typename vector<bool, _Allocator>::iterator 3137vector<bool, _Allocator>::__insert_with_size(const_iterator __position, _ForwardIterator __first, _Sentinel __last, 3138 difference_type __n_signed) { 3139 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__n_signed >= 0, "invalid range specified"); 3140 const size_type __n = static_cast<size_type>(__n_signed); 3141 iterator __r; 3142 size_type __c = capacity(); 3143 if (__n <= __c && size() <= __c - __n) 3144 { 3145 const_iterator __old_end = end(); 3146 __size_ += __n; 3147 std::copy_backward(__position, __old_end, end()); 3148 __r = __const_iterator_cast(__position); 3149 } 3150 else 3151 { 3152 vector __v(get_allocator()); 3153 __v.reserve(__recommend(__size_ + __n)); 3154 __v.__size_ = __size_ + __n; 3155 __r = std::copy(cbegin(), __position, __v.begin()); 3156 std::copy_backward(__position, cend(), __v.end()); 3157 swap(__v); 3158 } 3159 std::__copy<_ClassicAlgPolicy>(__first, __last, __r); 3160 return __r; 3161} 3162 3163template <class _Allocator> 3164inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 3165typename vector<bool, _Allocator>::iterator 3166vector<bool, _Allocator>::erase(const_iterator __position) 3167{ 3168 iterator __r = __const_iterator_cast(__position); 3169 std::copy(__position + 1, this->cend(), __r); 3170 --__size_; 3171 return __r; 3172} 3173 3174template <class _Allocator> 3175_LIBCPP_CONSTEXPR_SINCE_CXX20 3176typename vector<bool, _Allocator>::iterator 3177vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) 3178{ 3179 iterator __r = __const_iterator_cast(__first); 3180 difference_type __d = __last - __first; 3181 std::copy(__last, this->cend(), __r); 3182 __size_ -= __d; 3183 return __r; 3184} 3185 3186template <class _Allocator> 3187_LIBCPP_CONSTEXPR_SINCE_CXX20 void 3188vector<bool, _Allocator>::swap(vector& __x) 3189#if _LIBCPP_STD_VER >= 14 3190 _NOEXCEPT 3191#else 3192 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3193 __is_nothrow_swappable<allocator_type>::value) 3194#endif 3195{ 3196 std::swap(this->__begin_, __x.__begin_); 3197 std::swap(this->__size_, __x.__size_); 3198 std::swap(this->__cap(), __x.__cap()); 3199 std::__swap_allocator(this->__alloc(), __x.__alloc(), 3200 integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>()); 3201} 3202 3203template <class _Allocator> 3204_LIBCPP_CONSTEXPR_SINCE_CXX20 void 3205vector<bool, _Allocator>::resize(size_type __sz, value_type __x) 3206{ 3207 size_type __cs = size(); 3208 if (__cs < __sz) 3209 { 3210 iterator __r; 3211 size_type __c = capacity(); 3212 size_type __n = __sz - __cs; 3213 if (__n <= __c && __cs <= __c - __n) 3214 { 3215 __r = end(); 3216 __size_ += __n; 3217 } 3218 else 3219 { 3220 vector __v(get_allocator()); 3221 __v.reserve(__recommend(__size_ + __n)); 3222 __v.__size_ = __size_ + __n; 3223 __r = std::copy(cbegin(), cend(), __v.begin()); 3224 swap(__v); 3225 } 3226 std::fill_n(__r, __n, __x); 3227 } 3228 else 3229 __size_ = __sz; 3230} 3231 3232template <class _Allocator> 3233_LIBCPP_CONSTEXPR_SINCE_CXX20 void 3234vector<bool, _Allocator>::flip() _NOEXCEPT 3235{ 3236 // do middle whole words 3237 size_type __n = __size_; 3238 __storage_pointer __p = __begin_; 3239 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3240 *__p = ~*__p; 3241 // do last partial word 3242 if (__n > 0) 3243 { 3244 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3245 __storage_type __b = *__p & __m; 3246 *__p &= ~__m; 3247 *__p |= ~__b & __m; 3248 } 3249} 3250 3251template <class _Allocator> 3252_LIBCPP_CONSTEXPR_SINCE_CXX20 bool 3253vector<bool, _Allocator>::__invariants() const 3254{ 3255 if (this->__begin_ == nullptr) 3256 { 3257 if (this->__size_ != 0 || this->__cap() != 0) 3258 return false; 3259 } 3260 else 3261 { 3262 if (this->__cap() == 0) 3263 return false; 3264 if (this->__size_ > this->capacity()) 3265 return false; 3266 } 3267 return true; 3268} 3269 3270template <class _Allocator> 3271_LIBCPP_CONSTEXPR_SINCE_CXX20 size_t 3272vector<bool, _Allocator>::__hash_code() const _NOEXCEPT 3273{ 3274 size_t __h = 0; 3275 // do middle whole words 3276 size_type __n = __size_; 3277 __storage_pointer __p = __begin_; 3278 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3279 __h ^= *__p; 3280 // do last partial word 3281 if (__n > 0) 3282 { 3283 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3284 __h ^= *__p & __m; 3285 } 3286 return __h; 3287} 3288 3289template <class _Allocator> 3290struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> > 3291 : public __unary_function<vector<bool, _Allocator>, size_t> 3292{ 3293 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 3294 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT 3295 {return __vec.__hash_code();} 3296}; 3297 3298template <class _Tp, class _Allocator> 3299_LIBCPP_CONSTEXPR_SINCE_CXX20 3300inline _LIBCPP_HIDE_FROM_ABI 3301bool 3302operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3303{ 3304 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 3305 return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 3306} 3307 3308#if _LIBCPP_STD_VER <= 17 3309 3310template <class _Tp, class _Allocator> 3311inline _LIBCPP_HIDE_FROM_ABI 3312bool 3313operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3314{ 3315 return !(__x == __y); 3316} 3317 3318template <class _Tp, class _Allocator> 3319inline _LIBCPP_HIDE_FROM_ABI 3320bool 3321operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3322{ 3323 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 3324} 3325 3326template <class _Tp, class _Allocator> 3327inline _LIBCPP_HIDE_FROM_ABI 3328bool 3329operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3330{ 3331 return __y < __x; 3332} 3333 3334template <class _Tp, class _Allocator> 3335inline _LIBCPP_HIDE_FROM_ABI 3336bool 3337operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3338{ 3339 return !(__x < __y); 3340} 3341 3342template <class _Tp, class _Allocator> 3343inline _LIBCPP_HIDE_FROM_ABI 3344bool 3345operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3346{ 3347 return !(__y < __x); 3348} 3349 3350#else // _LIBCPP_STD_VER <= 17 3351 3352template <class _Tp, class _Allocator> 3353_LIBCPP_HIDE_FROM_ABI constexpr __synth_three_way_result<_Tp> 3354operator<=>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 3355 return std::lexicographical_compare_three_way( 3356 __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Tp, _Tp>); 3357} 3358 3359#endif // _LIBCPP_STD_VER <= 17 3360 3361template <class _Tp, class _Allocator> 3362_LIBCPP_CONSTEXPR_SINCE_CXX20 3363inline _LIBCPP_HIDE_FROM_ABI 3364void 3365swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) 3366 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3367{ 3368 __x.swap(__y); 3369} 3370 3371#if _LIBCPP_STD_VER >= 20 3372template <class _Tp, class _Allocator, class _Up> 3373_LIBCPP_CONSTEXPR_SINCE_CXX20 3374inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type 3375erase(vector<_Tp, _Allocator>& __c, const _Up& __v) { 3376 auto __old_size = __c.size(); 3377 __c.erase(std::remove(__c.begin(), __c.end(), __v), __c.end()); 3378 return __old_size - __c.size(); 3379} 3380 3381template <class _Tp, class _Allocator, class _Predicate> 3382_LIBCPP_CONSTEXPR_SINCE_CXX20 3383inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type 3384erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred) { 3385 auto __old_size = __c.size(); 3386 __c.erase(std::remove_if(__c.begin(), __c.end(), __pred), __c.end()); 3387 return __old_size - __c.size(); 3388} 3389 3390template <> 3391inline constexpr bool __format::__enable_insertable<vector<char>> = true; 3392#ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS 3393template <> 3394inline constexpr bool __format::__enable_insertable<vector<wchar_t>> = true; 3395#endif 3396 3397#endif // _LIBCPP_STD_VER >= 20 3398 3399#if _LIBCPP_STD_VER >= 23 3400template <class _Tp, class _CharT> 3401// Since is-vector-bool-reference is only used once it's inlined here. 3402 requires same_as<typename _Tp::__container, vector<bool, typename _Tp::__container::allocator_type>> 3403struct _LIBCPP_TEMPLATE_VIS formatter<_Tp, _CharT> { 3404private: 3405 formatter<bool, _CharT> __underlying_; 3406 3407public: 3408 template <class _ParseContext> 3409 _LIBCPP_HIDE_FROM_ABI constexpr typename _ParseContext::iterator parse(_ParseContext& __ctx) { 3410 return __underlying_.parse(__ctx); 3411 } 3412 3413 template <class _FormatContext> 3414 _LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator format(const _Tp& __ref, _FormatContext& __ctx) const { 3415 return __underlying_.format(__ref, __ctx); 3416 } 3417}; 3418#endif // _LIBCPP_STD_VER >= 23 3419 3420_LIBCPP_END_NAMESPACE_STD 3421 3422#if _LIBCPP_STD_VER >= 17 3423_LIBCPP_BEGIN_NAMESPACE_STD 3424namespace pmr { 3425template <class _ValueT> 3426using vector _LIBCPP_AVAILABILITY_PMR = std::vector<_ValueT, polymorphic_allocator<_ValueT>>; 3427} // namespace pmr 3428_LIBCPP_END_NAMESPACE_STD 3429#endif 3430 3431_LIBCPP_POP_MACROS 3432 3433#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20 3434# include <algorithm> 3435# include <atomic> 3436# include <concepts> 3437# include <cstdlib> 3438# include <type_traits> 3439# include <typeinfo> 3440# include <utility> 3441#endif 3442 3443#endif // _LIBCPP_VECTOR 3444