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