libcxx/include/__cxx03/vector

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