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