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