llvm-project

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
// clang-format off
14

15
/*
16
    vector synopsis
17

18
namespace std
19
{
20

21
template <class T, class Allocator = allocator<T> >
22
class vector
23
{
24
public:
25
    typedef T                                        value_type;
26
    typedef Allocator                                allocator_type;
27
    typedef typename allocator_type::reference       reference;
28
    typedef typename allocator_type::const_reference const_reference;
29
    typedef implementation-defined                   iterator;
30
    typedef implementation-defined                   const_iterator;
31
    typedef typename allocator_type::size_type       size_type;
32
    typedef typename allocator_type::difference_type difference_type;
33
    typedef typename allocator_type::pointer         pointer;
34
    typedef typename allocator_type::const_pointer   const_pointer;
35
    typedef std::reverse_iterator<iterator>          reverse_iterator;
36
    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
37

38
    vector()
39
        noexcept(is_nothrow_default_constructible<allocator_type>::value);
40
    explicit vector(const allocator_type&);
41
    explicit vector(size_type n);
42
    explicit vector(size_type n, const allocator_type&); // C++14
43
    vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
44
    template <class InputIterator>
45
        vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
46
    template<container-compatible-range<T> R>
47
      constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23
48
    vector(const vector& x);
49
    vector(vector&& x)
50
        noexcept(is_nothrow_move_constructible<allocator_type>::value);
51
    vector(initializer_list<value_type> il);
52
    vector(initializer_list<value_type> il, const allocator_type& a);
53
    ~vector();
54
    vector& operator=(const vector& x);
55
    vector& operator=(vector&& x)
56
        noexcept(
57
             allocator_type::propagate_on_container_move_assignment::value ||
58
             allocator_type::is_always_equal::value); // C++17
59
    vector& operator=(initializer_list<value_type> il);
60
    template <class InputIterator>
61
        void assign(InputIterator first, InputIterator last);
62
    template<container-compatible-range<T> R>
63
      constexpr void assign_range(R&& rg); // C++23
64
    void assign(size_type n, const value_type& u);
65
    void assign(initializer_list<value_type> il);
66

67
    allocator_type get_allocator() const noexcept;
68

69
    iterator               begin() noexcept;
70
    const_iterator         begin()   const noexcept;
71
    iterator               end() noexcept;
72
    const_iterator         end()     const noexcept;
73

74
    reverse_iterator       rbegin() noexcept;
75
    const_reverse_iterator rbegin()  const noexcept;
76
    reverse_iterator       rend() noexcept;
77
    const_reverse_iterator rend()    const noexcept;
78

79
    const_iterator         cbegin()  const noexcept;
80
    const_iterator         cend()    const noexcept;
81
    const_reverse_iterator crbegin() const noexcept;
82
    const_reverse_iterator crend()   const noexcept;
83

84
    size_type size() const noexcept;
85
    size_type max_size() const noexcept;
86
    size_type capacity() const noexcept;
87
    bool empty() const noexcept;
88
    void reserve(size_type n);
89
    void shrink_to_fit() noexcept;
90

91
    reference       operator[](size_type n);
92
    const_reference operator[](size_type n) const;
93
    reference       at(size_type n);
94
    const_reference at(size_type n) const;
95

96
    reference       front();
97
    const_reference front() const;
98
    reference       back();
99
    const_reference back() const;
100

101
    value_type*       data() noexcept;
102
    const value_type* data() const noexcept;
103

104
    void push_back(const value_type& x);
105
    void push_back(value_type&& x);
106
    template <class... Args>
107
        reference emplace_back(Args&&... args); // reference in C++17
108
    template<container-compatible-range<T> R>
109
      constexpr void append_range(R&& rg); // C++23
110
    void pop_back();
111

112
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
113
    iterator insert(const_iterator position, const value_type& x);
114
    iterator insert(const_iterator position, value_type&& x);
115
    iterator insert(const_iterator position, size_type n, const value_type& x);
116
    template <class InputIterator>
117
        iterator insert(const_iterator position, InputIterator first, InputIterator last);
118
    template<container-compatible-range<T> R>
119
      constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
120
    iterator insert(const_iterator position, initializer_list<value_type> il);
121

122
    iterator erase(const_iterator position);
123
    iterator erase(const_iterator first, const_iterator last);
124

125
    void clear() noexcept;
126

127
    void resize(size_type sz);
128
    void resize(size_type sz, const value_type& c);
129

130
    void swap(vector&)
131
        noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
132
                 allocator_traits<allocator_type>::is_always_equal::value);  // C++17
133

134
    bool __invariants() const;
135
};
136

137
template <class Allocator = allocator<T> >
138
class vector<bool, Allocator>
139
{
140
public:
141
    typedef bool                                     value_type;
142
    typedef Allocator                                allocator_type;
143
    typedef implementation-defined                   iterator;
144
    typedef implementation-defined                   const_iterator;
145
    typedef typename allocator_type::size_type       size_type;
146
    typedef typename allocator_type::difference_type difference_type;
147
    typedef iterator                                 pointer;
148
    typedef const_iterator                           const_pointer;
149
    typedef std::reverse_iterator<iterator>          reverse_iterator;
150
    typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
151

152
    class reference
153
    {
154
    public:
155
        reference(const reference&) noexcept;
156
        operator bool() const noexcept;
157
        reference& operator=(bool x) noexcept;
158
        reference& operator=(const reference& x) noexcept;
159
        iterator operator&() const noexcept;
160
        void flip() noexcept;
161
    };
162

163
    class const_reference
164
    {
165
    public:
166
        const_reference(const reference&) noexcept;
167
        operator bool() const noexcept;
168
        const_iterator operator&() const noexcept;
169
    };
170

171
    vector()
172
        noexcept(is_nothrow_default_constructible<allocator_type>::value);
173
    explicit vector(const allocator_type&);
174
    explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
175
    vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
176
    template <class InputIterator>
177
        vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
178
    template<container-compatible-range<bool> R>
179
      constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator());
180
    vector(const vector& x);
181
    vector(vector&& x)
182
        noexcept(is_nothrow_move_constructible<allocator_type>::value);
183
    vector(initializer_list<value_type> il);
184
    vector(initializer_list<value_type> il, const allocator_type& a);
185
    ~vector();
186
    vector& operator=(const vector& x);
187
    vector& operator=(vector&& x)
188
        noexcept(
189
             allocator_type::propagate_on_container_move_assignment::value ||
190
             allocator_type::is_always_equal::value); // C++17
191
    vector& operator=(initializer_list<value_type> il);
192
    template <class InputIterator>
193
        void assign(InputIterator first, InputIterator last);
194
    template<container-compatible-range<T> R>
195
      constexpr void assign_range(R&& rg); // C++23
196
    void assign(size_type n, const value_type& u);
197
    void assign(initializer_list<value_type> il);
198

199
    allocator_type get_allocator() const noexcept;
200

201
    iterator               begin() noexcept;
202
    const_iterator         begin()   const noexcept;
203
    iterator               end() noexcept;
204
    const_iterator         end()     const noexcept;
205

206
    reverse_iterator       rbegin() noexcept;
207
    const_reverse_iterator rbegin()  const noexcept;
208
    reverse_iterator       rend() noexcept;
209
    const_reverse_iterator rend()    const noexcept;
210

211
    const_iterator         cbegin()  const noexcept;
212
    const_iterator         cend()    const noexcept;
213
    const_reverse_iterator crbegin() const noexcept;
214
    const_reverse_iterator crend()   const noexcept;
215

216
    size_type size() const noexcept;
217
    size_type max_size() const noexcept;
218
    size_type capacity() const noexcept;
219
    bool empty() const noexcept;
220
    void reserve(size_type n);
221
    void shrink_to_fit() noexcept;
222

223
    reference       operator[](size_type n);
224
    const_reference operator[](size_type n) const;
225
    reference       at(size_type n);
226
    const_reference at(size_type n) const;
227

228
    reference       front();
229
    const_reference front() const;
230
    reference       back();
231
    const_reference back() const;
232

233
    void push_back(const value_type& x);
234
    template <class... Args> reference emplace_back(Args&&... args);  // C++14; reference in C++17
235
    template<container-compatible-range<T> R>
236
      constexpr void append_range(R&& rg); // C++23
237
    void pop_back();
238

239
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);  // C++14
240
    iterator insert(const_iterator position, const value_type& x);
241
    iterator insert(const_iterator position, size_type n, const value_type& x);
242
    template <class InputIterator>
243
        iterator insert(const_iterator position, InputIterator first, InputIterator last);
244
    template<container-compatible-range<T> R>
245
      constexpr iterator insert_range(const_iterator position, R&& rg); // C++23
246
    iterator insert(const_iterator position, initializer_list<value_type> il);
247

248
    iterator erase(const_iterator position);
249
    iterator erase(const_iterator first, const_iterator last);
250

251
    void clear() noexcept;
252

253
    void resize(size_type sz);
254
    void resize(size_type sz, value_type x);
255

256
    void swap(vector&)
257
        noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
258
                 allocator_traits<allocator_type>::is_always_equal::value);  // C++17
259
    void flip() noexcept;
260

261
    bool __invariants() const;
262
};
263

264
template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
265
   vector(InputIterator, InputIterator, Allocator = Allocator())
266
   -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
267

268
template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>>
269
  vector(from_range_t, R&&, Allocator = Allocator())
270
    -> vector<ranges::range_value_t<R>, Allocator>; // C++23
271

272
template <class Allocator> struct hash<std::vector<bool, Allocator>>;
273

274
template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // constexpr since C++20
275
template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
276
template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
277
template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
278
template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
279
template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
280
template <class T, class Allocator> constexpr
281
  constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
282
                                                  const vector<T, Allocator>& y);                                  // since C++20
283

284
template <class T, class Allocator>
285
void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
286
    noexcept(noexcept(x.swap(y)));
287

288
template <class T, class Allocator, class U>
289
typename vector<T, Allocator>::size_type
290
erase(vector<T, Allocator>& c, const U& value);       // since C++20
291
template <class T, class Allocator, class Predicate>
292
typename vector<T, Allocator>::size_type
293
erase_if(vector<T, Allocator>& c, Predicate pred);    // since C++20
294

295

296
template<class T>
297
 inline constexpr bool is-vector-bool-reference = see below;        // exposition only, since C++23
298

299
template<class T, class charT> requires is-vector-bool-reference<T> // Since C++23
300
 struct formatter<T, charT>;
301

302
}  // std
303

304
*/
305

306
// clang-format on
307

308
#include <__algorithm/copy.h>
309
#include <__algorithm/equal.h>
310
#include <__algorithm/fill_n.h>
311
#include <__algorithm/iterator_operations.h>
312
#include <__algorithm/lexicographical_compare.h>
313
#include <__algorithm/lexicographical_compare_three_way.h>
314
#include <__algorithm/remove.h>
315
#include <__algorithm/remove_if.h>
316
#include <__algorithm/rotate.h>
317
#include <__algorithm/unwrap_iter.h>
318
#include <__assert>
319
#include <__bit_reference>
320
#include <__concepts/same_as.h>
321
#include <__config>
322
#include <__debug_utils/sanitizers.h>
323
#include <__format/enable_insertable.h>
324
#include <__format/formatter.h>
325
#include <__format/formatter_bool.h>
326
#include <__functional/hash.h>
327
#include <__functional/unary_function.h>
328
#include <__fwd/vector.h>
329
#include <__iterator/advance.h>
330
#include <__iterator/distance.h>
331
#include <__iterator/iterator_traits.h>
332
#include <__iterator/reverse_iterator.h>
333
#include <__iterator/wrap_iter.h>
334
#include <__memory/addressof.h>
335
#include <__memory/allocate_at_least.h>
336
#include <__memory/allocator_traits.h>
337
#include <__memory/pointer_traits.h>
338
#include <__memory/swap_allocator.h>
339
#include <__memory/temp_value.h>
340
#include <__memory/uninitialized_algorithms.h>
341
#include <__memory_resource/polymorphic_allocator.h>
342
#include <__ranges/access.h>
343
#include <__ranges/concepts.h>
344
#include <__ranges/container_compatible_range.h>
345
#include <__ranges/from_range.h>
346
#include <__ranges/size.h>
347
#include <__split_buffer>
348
#include <__type_traits/is_allocator.h>
349
#include <__type_traits/is_constructible.h>
350
#include <__type_traits/is_nothrow_assignable.h>
351
#include <__type_traits/noexcept_move_assign_container.h>
352
#include <__type_traits/type_identity.h>
353
#include <__utility/exception_guard.h>
354
#include <__utility/forward.h>
355
#include <__utility/is_pointer_in_range.h>
356
#include <__utility/move.h>
357
#include <__utility/pair.h>
358
#include <__utility/swap.h>
359
#include <climits>
360
#include <cstring>
361
#include <limits>
362
#include <stdexcept>
363
#include <version>
364

365
// standard-mandated includes
366

367
// [iterator.range]
368
#include <__iterator/access.h>
369
#include <__iterator/data.h>
370
#include <__iterator/empty.h>
371
#include <__iterator/reverse_access.h>
372
#include <__iterator/size.h>
373

374
// [vector.syn]
375
#include <compare>
376
#include <initializer_list>
377

378
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
379
#  pragma GCC system_header
380
#endif
381

382
_LIBCPP_PUSH_MACROS
383
#include <__undef_macros>
384

385
_LIBCPP_BEGIN_NAMESPACE_STD
386

387
template <class _Tp, class _Allocator /* = allocator<_Tp> */>
388
class _LIBCPP_TEMPLATE_VIS vector {
389
private:
390
  typedef allocator<_Tp> __default_allocator_type;
391

392
public:
393
  typedef vector __self;
394
  typedef _Tp value_type;
395
  typedef _Allocator allocator_type;
396
  typedef allocator_traits<allocator_type> __alloc_traits;
397
  typedef value_type& reference;
398
  typedef const value_type& const_reference;
399
  typedef typename __alloc_traits::size_type size_type;
400
  typedef typename __alloc_traits::difference_type difference_type;
401
  typedef typename __alloc_traits::pointer pointer;
402
  typedef typename __alloc_traits::const_pointer const_pointer;
403
  // TODO: Implement iterator bounds checking without requiring the global database.
404
  typedef __wrap_iter<pointer> iterator;
405
  typedef __wrap_iter<const_pointer> const_iterator;
406
  typedef std::reverse_iterator<iterator> reverse_iterator;
407
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
408

409
  // A vector containers the following members which may be trivially relocatable:
410
  // - pointer: may be trivially relocatable, so it's checked
411
  // - allocator_type: may be trivially relocatable, so it's checked
412
  // vector doesn't contain any self-references, so it's trivially relocatable if its members are.
413
  using __trivially_relocatable = __conditional_t<
414
      __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value,
415
      vector,
416
      void>;
417

418
  static_assert(__check_valid_allocator<allocator_type>::value, "");
419
  static_assert(is_same<typename allocator_type::value_type, value_type>::value,
420
                "Allocator::value_type must be same type as value_type");
421

422
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector()
423
      _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) {}
424
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(const allocator_type& __a)
425
#if _LIBCPP_STD_VER <= 14
426
      _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
427
#else
428
      _NOEXCEPT
429
#endif
430
      : __end_cap_(nullptr, __a) {
431
  }
432

433
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n) {
434
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
435
    if (__n > 0) {
436
      __vallocate(__n);
437
      __construct_at_end(__n);
438
    }
439
    __guard.__complete();
440
  }
441

442
#if _LIBCPP_STD_VER >= 14
443
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n, const allocator_type& __a)
444
      : __end_cap_(nullptr, __a) {
445
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
446
    if (__n > 0) {
447
      __vallocate(__n);
448
      __construct_at_end(__n);
449
    }
450
    __guard.__complete();
451
  }
452
#endif
453

454
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __x) {
455
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
456
    if (__n > 0) {
457
      __vallocate(__n);
458
      __construct_at_end(__n, __x);
459
    }
460
    __guard.__complete();
461
  }
462

463
  template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0>
464
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
465
  vector(size_type __n, const value_type& __x, const allocator_type& __a)
466
      : __end_cap_(nullptr, __a) {
467
    if (__n > 0) {
468
      __vallocate(__n);
469
      __construct_at_end(__n, __x);
470
    }
471
  }
472

473
  template <class _InputIterator,
474
            __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
475
                              is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
476
                          int> = 0>
477
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last);
478
  template <class _InputIterator,
479
            __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
480
                              is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
481
                          int> = 0>
482
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
483
  vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
484

485
  template <
486
      class _ForwardIterator,
487
      __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
488
                        is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
489
                    int> = 0>
490
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last);
491

492
  template <
493
      class _ForwardIterator,
494
      __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
495
                        is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
496
                    int> = 0>
497
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
498
  vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);
499

500
#if _LIBCPP_STD_VER >= 23
501
  template <_ContainerCompatibleRange<_Tp> _Range>
502
  _LIBCPP_HIDE_FROM_ABI constexpr vector(
503
      from_range_t, _Range&& __range, const allocator_type& __alloc = allocator_type())
504
      : __end_cap_(nullptr, __alloc) {
505
    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
506
      auto __n = static_cast<size_type>(ranges::distance(__range));
507
      __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
508

509
    } else {
510
      __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
511
    }
512
  }
513
#endif
514

515
private:
516
  class __destroy_vector {
517
  public:
518
    _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
519

520
    _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
521
      if (__vec_.__begin_ != nullptr) {
522
        __vec_.__clear();
523
        __vec_.__annotate_delete();
524
        __alloc_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.capacity());
525
      }
526
    }
527

528
  private:
529
    vector& __vec_;
530
  };
531

532
public:
533
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~vector() { __destroy_vector (*this)(); }
534

535
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(const vector& __x);
536
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
537
  vector(const vector& __x, const __type_identity_t<allocator_type>& __a);
538
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(const vector& __x);
539

540
#ifndef _LIBCPP_CXX03_LANG
541
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(initializer_list<value_type> __il);
542

543
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
544
  vector(initializer_list<value_type> __il, const allocator_type& __a);
545

546
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(initializer_list<value_type> __il) {
547
    assign(__il.begin(), __il.end());
548
    return *this;
549
  }
550
#endif // !_LIBCPP_CXX03_LANG
551

552
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(vector&& __x)
553
#if _LIBCPP_STD_VER >= 17
554
      noexcept;
555
#else
556
      _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
557
#endif
558

559
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
560
  vector(vector&& __x, const __type_identity_t<allocator_type>& __a);
561
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector& operator=(vector&& __x)
562
      _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);
563

564
  template <class _InputIterator,
565
            __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
566
                              is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value,
567
                          int> = 0>
568
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_InputIterator __first, _InputIterator __last);
569
  template <
570
      class _ForwardIterator,
571
      __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
572
                        is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
573
                    int> = 0>
574
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_ForwardIterator __first, _ForwardIterator __last);
575

576
#if _LIBCPP_STD_VER >= 23
577
  template <_ContainerCompatibleRange<_Tp> _Range>
578
  _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
579
    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
580
      auto __n = static_cast<size_type>(ranges::distance(__range));
581
      __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);
582

583
    } else {
584
      __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
585
    }
586
  }
587
#endif
588

589
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const_reference __u);
590

591
#ifndef _LIBCPP_CXX03_LANG
592
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(initializer_list<value_type> __il) {
593
    assign(__il.begin(), __il.end());
594
  }
595
#endif
596

597
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT {
598
    return this->__alloc();
599
  }
600

601
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT;
602
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT;
603
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT;
604
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT;
605

606
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT {
607
    return reverse_iterator(end());
608
  }
609
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT {
610
    return const_reverse_iterator(end());
611
  }
612
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT {
613
    return reverse_iterator(begin());
614
  }
615
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT {
616
    return const_reverse_iterator(begin());
617
  }
618

619
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
620
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
621
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT {
622
    return rbegin();
623
  }
624
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
625

626
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT {
627
    return static_cast<size_type>(this->__end_ - this->__begin_);
628
  }
629
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT {
630
    return static_cast<size_type>(__end_cap() - this->__begin_);
631
  }
632
  _LIBCPP_NODISCARD _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT {
633
    return this->__begin_ == this->__end_;
634
  }
635
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT;
636
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n);
637
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT;
638

639
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) _NOEXCEPT;
640
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __n) const _NOEXCEPT;
641
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n);
642
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const;
643

644
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() _NOEXCEPT {
645
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector");
646
    return *this->__begin_;
647
  }
648
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const _NOEXCEPT {
649
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector");
650
    return *this->__begin_;
651
  }
652
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT {
653
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector");
654
    return *(this->__end_ - 1);
655
  }
656
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT {
657
    _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector");
658
    return *(this->__end_ - 1);
659
  }
660

661
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI value_type* data() _NOEXCEPT {
662
    return std::__to_address(this->__begin_);
663
  }
664

665
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const value_type* data() const _NOEXCEPT {
666
    return std::__to_address(this->__begin_);
667
  }
668

669
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(const_reference __x);
670

671
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x);
672

673
  template <class... _Args>
674
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI
675
#if _LIBCPP_STD_VER >= 17
676
  reference
677
  emplace_back(_Args&&... __args);
678
#else
679
  void
680
  emplace_back(_Args&&... __args);
681
#endif
682

683
#if _LIBCPP_STD_VER >= 23
684
  template <_ContainerCompatibleRange<_Tp> _Range>
685
  _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
686
    insert_range(end(), std::forward<_Range>(__range));
687
  }
688
#endif
689

690
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back();
691

692
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, const_reference __x);
693

694
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, value_type&& __x);
695
  template <class... _Args>
696
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __position, _Args&&... __args);
697

698
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
699
  insert(const_iterator __position, size_type __n, const_reference __x);
700

701
  template <class _InputIterator,
702
            __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
703
                              is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value,
704
                          int> = 0>
705
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
706
  insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
707

708
#if _LIBCPP_STD_VER >= 23
709
  template <_ContainerCompatibleRange<_Tp> _Range>
710
  _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
711
    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
712
      auto __n = static_cast<size_type>(ranges::distance(__range));
713
      return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
714

715
    } else {
716
      return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
717
    }
718
  }
719
#endif
720

721
  template <
722
      class _ForwardIterator,
723
      __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
724
                        is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value,
725
                    int> = 0>
726
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
727
  insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
728

729
#ifndef _LIBCPP_CXX03_LANG
730
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
731
  insert(const_iterator __position, initializer_list<value_type> __il) {
732
    return insert(__position, __il.begin(), __il.end());
733
  }
734
#endif
735

736
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position);
737
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last);
738

739
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT {
740
    size_type __old_size = size();
741
    __clear();
742
    __annotate_shrink(__old_size);
743
  }
744

745
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz);
746
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz, const_reference __x);
747

748
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(vector&)
749
#if _LIBCPP_STD_VER >= 14
750
      _NOEXCEPT;
751
#else
752
      _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
753
#endif
754

755
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const;
756

757
private:
758
  pointer __begin_ = nullptr;
759
  pointer __end_   = nullptr;
760
  __compressed_pair<pointer, allocator_type> __end_cap_ =
761
      __compressed_pair<pointer, allocator_type>(nullptr, __default_init_tag());
762

763
  //  Allocate space for __n objects
764
  //  throws length_error if __n > max_size()
765
  //  throws (probably bad_alloc) if memory run out
766
  //  Precondition:  __begin_ == __end_ == __end_cap() == 0
767
  //  Precondition:  __n > 0
768
  //  Postcondition:  capacity() >= __n
769
  //  Postcondition:  size() == 0
770
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) {
771
    if (__n > max_size())
772
      __throw_length_error();
773
    auto __allocation = std::__allocate_at_least(__alloc(), __n);
774
    __begin_          = __allocation.ptr;
775
    __end_            = __allocation.ptr;
776
    __end_cap()       = __begin_ + __allocation.count;
777
    __annotate_new(0);
778
  }
779

780
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __vdeallocate() _NOEXCEPT;
781
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __recommend(size_type __new_size) const;
782
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n);
783
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x);
784

785
  template <class _InputIterator, class _Sentinel>
786
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
787
  __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
788
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
789

790
    if (__n > 0) {
791
      __vallocate(__n);
792
      __construct_at_end(__first, __last, __n);
793
    }
794

795
    __guard.__complete();
796
  }
797

798
  template <class _InputIterator, class _Sentinel>
799
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
800
  __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
801
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
802

803
    for (; __first != __last; ++__first)
804
      emplace_back(*__first);
805

806
    __guard.__complete();
807
  }
808

809
  template <class _Iterator, class _Sentinel>
810
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
811

812
  template <class _ForwardIterator, class _Sentinel>
813
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
814
  __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n);
815

816
  template <class _InputIterator, class _Sentinel>
817
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
818
  __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
819

820
  template <class _Iterator, class _Sentinel>
821
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
822
  __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
823

824
  template <class _InputIterator, class _Sentinel>
825
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
826
  __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
827

828
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n);
829
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const_reference __x);
830
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator __make_iter(pointer __p) _NOEXCEPT {
831
    return iterator(__p);
832
  }
833
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(const_pointer __p) const _NOEXCEPT {
834
    return const_iterator(__p);
835
  }
836
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
837
  __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
838
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer
839
  __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
840
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
841
  __move_range(pointer __from_s, pointer __from_e, pointer __to);
842
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, true_type)
843
      _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
844
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, false_type)
845
      _NOEXCEPT_(__alloc_traits::is_always_equal::value);
846
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT {
847
    size_type __old_size = size();
848
    __base_destruct_at_end(__new_last);
849
    __annotate_shrink(__old_size);
850
  }
851

852
  template <class _Up>
853
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI inline pointer __push_back_slow_path(_Up&& __x);
854

855
  template <class... _Args>
856
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI inline pointer __emplace_back_slow_path(_Args&&... __args);
857

858
  // The following functions are no-ops outside of AddressSanitizer mode.
859
  // We call annotations for every allocator, unless explicitly disabled.
860
  //
861
  // To disable annotations for a particular allocator, change value of
862
  // __asan_annotate_container_with_allocator to false.
863
  // For more details, see the "Using libc++" documentation page or
864
  // the documentation for __sanitizer_annotate_contiguous_container.
865

866
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
867
  __annotate_contiguous_container(const void* __old_mid, const void* __new_mid) const {
868
    std::__annotate_contiguous_container<_Allocator>(data(), data() + capacity(), __old_mid, __new_mid);
869
  }
870

871
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT {
872
    (void)__current_size;
873
#ifndef _LIBCPP_HAS_NO_ASAN
874
    __annotate_contiguous_container(data() + capacity(), data() + __current_size);
875
#endif
876
  }
877

878
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT {
879
#ifndef _LIBCPP_HAS_NO_ASAN
880
    __annotate_contiguous_container(data() + size(), data() + capacity());
881
#endif
882
  }
883

884
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_increase(size_type __n) const _NOEXCEPT {
885
    (void)__n;
886
#ifndef _LIBCPP_HAS_NO_ASAN
887
    __annotate_contiguous_container(data() + size(), data() + size() + __n);
888
#endif
889
  }
890

891
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink(size_type __old_size) const _NOEXCEPT {
892
    (void)__old_size;
893
#ifndef _LIBCPP_HAS_NO_ASAN
894
    __annotate_contiguous_container(data() + __old_size, data() + size());
895
#endif
896
  }
897

898
  struct _ConstructTransaction {
899
    _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(vector& __v, size_type __n)
900
        : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
901
#ifndef _LIBCPP_HAS_NO_ASAN
902
      __v_.__annotate_increase(__n);
903
#endif
904
    }
905

906
    _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() {
907
      __v_.__end_ = __pos_;
908
#ifndef _LIBCPP_HAS_NO_ASAN
909
      if (__pos_ != __new_end_) {
910
        __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
911
      }
912
#endif
913
    }
914

915
    vector& __v_;
916
    pointer __pos_;
917
    const_pointer const __new_end_;
918

919
    _ConstructTransaction(_ConstructTransaction const&)            = delete;
920
    _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
921
  };
922

923
  template <class... _Args>
924
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_one_at_end(_Args&&... __args) {
925
    _ConstructTransaction __tx(*this, 1);
926
    __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), std::forward<_Args>(__args)...);
927
    ++__tx.__pos_;
928
  }
929

930
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT {
931
    return this->__end_cap_.second();
932
  }
933
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT {
934
    return this->__end_cap_.second();
935
  }
936
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer& __end_cap() _NOEXCEPT {
937
    return this->__end_cap_.first();
938
  }
939
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const pointer& __end_cap() const _NOEXCEPT {
940
    return this->__end_cap_.first();
941
  }
942

943
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __clear() _NOEXCEPT {
944
    __base_destruct_at_end(this->__begin_);
945
  }
946

947
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {
948
    pointer __soon_to_be_end = this->__end_;
949
    while (__new_last != __soon_to_be_end)
950
      __alloc_traits::destroy(__alloc(), std::__to_address(--__soon_to_be_end));
951
    this->__end_ = __new_last;
952
  }
953

954
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c) {
955
    __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>());
956
  }
957

958
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c)
959
      _NOEXCEPT_(!__alloc_traits::propagate_on_container_move_assignment::value ||
960
                 is_nothrow_move_assignable<allocator_type>::value) {
961
    __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
962
  }
963

964
  _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { std::__throw_length_error("vector"); }
965

966
  _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { std::__throw_out_of_range("vector"); }
967

968
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c, true_type) {
969
    if (__alloc() != __c.__alloc()) {
970
      __clear();
971
      __annotate_delete();
972
      __alloc_traits::deallocate(__alloc(), this->__begin_, capacity());
973
      this->__begin_ = this->__end_ = __end_cap() = nullptr;
974
    }
975
    __alloc() = __c.__alloc();
976
  }
977

978
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector&, false_type) {}
979

980
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c, true_type)
981
      _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
982
    __alloc() = std::move(__c.__alloc());
983
  }
984

985
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
986
};
987

988
#if _LIBCPP_STD_VER >= 17
989
template <class _InputIterator,
990
          class _Alloc = allocator<__iter_value_type<_InputIterator>>,
991
          class        = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
992
          class        = enable_if_t<__is_allocator<_Alloc>::value> >
993
vector(_InputIterator, _InputIterator) -> vector<__iter_value_type<_InputIterator>, _Alloc>;
994

995
template <class _InputIterator,
996
          class _Alloc,
997
          class = enable_if_t<__has_input_iterator_category<_InputIterator>::value>,
998
          class = enable_if_t<__is_allocator<_Alloc>::value> >
999
vector(_InputIterator, _InputIterator, _Alloc) -> vector<__iter_value_type<_InputIterator>, _Alloc>;
1000
#endif
1001

1002
#if _LIBCPP_STD_VER >= 23
1003
template <ranges::input_range _Range,
1004
          class _Alloc = allocator<ranges::range_value_t<_Range>>,
1005
          class        = enable_if_t<__is_allocator<_Alloc>::value> >
1006
vector(from_range_t, _Range&&, _Alloc = _Alloc()) -> vector<ranges::range_value_t<_Range>, _Alloc>;
1007
#endif
1008

1009
// __swap_out_circular_buffer relocates the objects in [__begin_, __end_) into the front of __v and swaps the buffers of
1010
// *this and __v. It is assumed that __v provides space for exactly (__end_ - __begin_) objects in the front. This
1011
// function has a strong exception guarantee.
1012
template <class _Tp, class _Allocator>
1013
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
1014
vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) {
1015
  __annotate_delete();
1016
  auto __new_begin = __v.__begin_ - (__end_ - __begin_);
1017
  std::__uninitialized_allocator_relocate(
1018
      __alloc(), std::__to_address(__begin_), std::__to_address(__end_), std::__to_address(__new_begin));
1019
  __v.__begin_ = __new_begin;
1020
  __end_       = __begin_; // All the objects have been destroyed by relocating them.
1021
  std::swap(this->__begin_, __v.__begin_);
1022
  std::swap(this->__end_, __v.__end_);
1023
  std::swap(this->__end_cap(), __v.__end_cap());
1024
  __v.__first_ = __v.__begin_;
1025
  __annotate_new(size());
1026
}
1027

1028
// __swap_out_circular_buffer relocates the objects in [__begin_, __p) into the front of __v, the objects in
1029
// [__p, __end_) into the back of __v and swaps the buffers of *this and __v. It is assumed that __v provides space for
1030
// exactly (__p - __begin_) objects in the front and space for at least (__end_ - __p) objects in the back. This
1031
// function has a strong exception guarantee if __begin_ == __p || __end_ == __p.
1032
template <class _Tp, class _Allocator>
1033
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1034
vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) {
1035
  __annotate_delete();
1036
  pointer __ret = __v.__begin_;
1037

1038
  // Relocate [__p, __end_) first to avoid having a hole in [__begin_, __end_)
1039
  // in case something in [__begin_, __p) throws.
1040
  std::__uninitialized_allocator_relocate(
1041
      __alloc(), std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.__end_));
1042
  __v.__end_ += (__end_ - __p);
1043
  __end_           = __p; // The objects in [__p, __end_) have been destroyed by relocating them.
1044
  auto __new_begin = __v.__begin_ - (__p - __begin_);
1045

1046
  std::__uninitialized_allocator_relocate(
1047
      __alloc(), std::__to_address(__begin_), std::__to_address(__p), std::__to_address(__new_begin));
1048
  __v.__begin_ = __new_begin;
1049
  __end_       = __begin_; // All the objects have been destroyed by relocating them.
1050

1051
  std::swap(this->__begin_, __v.__begin_);
1052
  std::swap(this->__end_, __v.__end_);
1053
  std::swap(this->__end_cap(), __v.__end_cap());
1054
  __v.__first_ = __v.__begin_;
1055
  __annotate_new(size());
1056
  return __ret;
1057
}
1058

1059
template <class _Tp, class _Allocator>
1060
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT {
1061
  if (this->__begin_ != nullptr) {
1062
    clear();
1063
    __annotate_delete();
1064
    __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
1065
    this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
1066
  }
1067
}
1068

1069
template <class _Tp, class _Allocator>
1070
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::size_type
1071
vector<_Tp, _Allocator>::max_size() const _NOEXCEPT {
1072
  return std::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<difference_type>::max());
1073
}
1074

1075
//  Precondition:  __new_size > capacity()
1076
template <class _Tp, class _Allocator>
1077
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
1078
vector<_Tp, _Allocator>::__recommend(size_type __new_size) const {
1079
  const size_type __ms = max_size();
1080
  if (__new_size > __ms)
1081
    this->__throw_length_error();
1082
  const size_type __cap = capacity();
1083
  if (__cap >= __ms / 2)
1084
    return __ms;
1085
  return std::max<size_type>(2 * __cap, __new_size);
1086
}
1087

1088
//  Default constructs __n objects starting at __end_
1089
//  throws if construction throws
1090
//  Precondition:  __n > 0
1091
//  Precondition:  size() + __n <= capacity()
1092
//  Postcondition:  size() == size() + __n
1093
template <class _Tp, class _Allocator>
1094
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) {
1095
  _ConstructTransaction __tx(*this, __n);
1096
  const_pointer __new_end = __tx.__new_end_;
1097
  for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
1098
    __alloc_traits::construct(this->__alloc(), std::__to_address(__pos));
1099
  }
1100
}
1101

1102
//  Copy constructs __n objects starting at __end_ from __x
1103
//  throws if construction throws
1104
//  Precondition:  __n > 0
1105
//  Precondition:  size() + __n <= capacity()
1106
//  Postcondition:  size() == old size() + __n
1107
//  Postcondition:  [i] == __x for all i in [size() - __n, __n)
1108
template <class _Tp, class _Allocator>
1109
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void
1110
vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) {
1111
  _ConstructTransaction __tx(*this, __n);
1112
  const_pointer __new_end = __tx.__new_end_;
1113
  for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
1114
    __alloc_traits::construct(this->__alloc(), std::__to_address(__pos), __x);
1115
  }
1116
}
1117

1118
template <class _Tp, class _Allocator>
1119
template <class _InputIterator, class _Sentinel>
1120
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
1121
vector<_Tp, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
1122
  _ConstructTransaction __tx(*this, __n);
1123
  __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_);
1124
}
1125

1126
//  Default constructs __n objects starting at __end_
1127
//  throws if construction throws
1128
//  Postcondition:  size() == size() + __n
1129
//  Exception safety: strong.
1130
template <class _Tp, class _Allocator>
1131
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__append(size_type __n) {
1132
  if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1133
    this->__construct_at_end(__n);
1134
  else {
1135
    allocator_type& __a = this->__alloc();
1136
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1137
    __v.__construct_at_end(__n);
1138
    __swap_out_circular_buffer(__v);
1139
  }
1140
}
1141

1142
//  Default constructs __n objects starting at __end_
1143
//  throws if construction throws
1144
//  Postcondition:  size() == size() + __n
1145
//  Exception safety: strong.
1146
template <class _Tp, class _Allocator>
1147
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) {
1148
  if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1149
    this->__construct_at_end(__n, __x);
1150
  else {
1151
    allocator_type& __a = this->__alloc();
1152
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1153
    __v.__construct_at_end(__n, __x);
1154
    __swap_out_circular_buffer(__v);
1155
  }
1156
}
1157

1158
template <class _Tp, class _Allocator>
1159
template <class _InputIterator,
1160
          __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1161
                            is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1162
                        int> >
1163
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last) {
1164
  __init_with_sentinel(__first, __last);
1165
}
1166

1167
template <class _Tp, class _Allocator>
1168
template <class _InputIterator,
1169
          __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1170
                            is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1171
                        int> >
1172
_LIBCPP_CONSTEXPR_SINCE_CXX20
1173
vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
1174
    : __end_cap_(nullptr, __a) {
1175
  __init_with_sentinel(__first, __last);
1176
}
1177

1178
template <class _Tp, class _Allocator>
1179
template <class _ForwardIterator,
1180
          __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1181
                            is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1182
                        int> >
1183
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last) {
1184
  size_type __n = static_cast<size_type>(std::distance(__first, __last));
1185
  __init_with_size(__first, __last, __n);
1186
}
1187

1188
template <class _Tp, class _Allocator>
1189
template <class _ForwardIterator,
1190
          __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1191
                            is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1192
                        int> >
1193
_LIBCPP_CONSTEXPR_SINCE_CXX20
1194
vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)
1195
    : __end_cap_(nullptr, __a) {
1196
  size_type __n = static_cast<size_type>(std::distance(__first, __last));
1197
  __init_with_size(__first, __last, __n);
1198
}
1199

1200
template <class _Tp, class _Allocator>
1201
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(const vector& __x)
1202
    : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc())) {
1203
  __init_with_size(__x.__begin_, __x.__end_, __x.size());
1204
}
1205

1206
template <class _Tp, class _Allocator>
1207
_LIBCPP_CONSTEXPR_SINCE_CXX20
1208
vector<_Tp, _Allocator>::vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
1209
    : __end_cap_(nullptr, __a) {
1210
  __init_with_size(__x.__begin_, __x.__end_, __x.size());
1211
}
1212

1213
template <class _Tp, class _Allocator>
1214
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>::vector(vector&& __x)
1215
#if _LIBCPP_STD_VER >= 17
1216
    noexcept
1217
#else
1218
    _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1219
#endif
1220
    : __end_cap_(nullptr, std::move(__x.__alloc())) {
1221
  this->__begin_    = __x.__begin_;
1222
  this->__end_      = __x.__end_;
1223
  this->__end_cap() = __x.__end_cap();
1224
  __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1225
}
1226

1227
template <class _Tp, class _Allocator>
1228
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
1229
vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
1230
    : __end_cap_(nullptr, __a) {
1231
  if (__a == __x.__alloc()) {
1232
    this->__begin_    = __x.__begin_;
1233
    this->__end_      = __x.__end_;
1234
    this->__end_cap() = __x.__end_cap();
1235
    __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1236
  } else {
1237
    typedef move_iterator<iterator> _Ip;
1238
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
1239
    assign(_Ip(__x.begin()), _Ip(__x.end()));
1240
    __guard.__complete();
1241
  }
1242
}
1243

1244
#ifndef _LIBCPP_CXX03_LANG
1245

1246
template <class _Tp, class _Allocator>
1247
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
1248
vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) {
1249
  auto __guard = std::__make_exception_guard(__destroy_vector(*this));
1250
  if (__il.size() > 0) {
1251
    __vallocate(__il.size());
1252
    __construct_at_end(__il.begin(), __il.end(), __il.size());
1253
  }
1254
  __guard.__complete();
1255
}
1256

1257
template <class _Tp, class _Allocator>
1258
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI
1259
vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1260
    : __end_cap_(nullptr, __a) {
1261
  auto __guard = std::__make_exception_guard(__destroy_vector(*this));
1262
  if (__il.size() > 0) {
1263
    __vallocate(__il.size());
1264
    __construct_at_end(__il.begin(), __il.end(), __il.size());
1265
  }
1266
  __guard.__complete();
1267
}
1268

1269
#endif // _LIBCPP_CXX03_LANG
1270

1271
template <class _Tp, class _Allocator>
1272
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>&
1273
vector<_Tp, _Allocator>::operator=(vector&& __x)
1274
    _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {
1275
  __move_assign(__x, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>());
1276
  return *this;
1277
}
1278

1279
template <class _Tp, class _Allocator>
1280
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1281
    _NOEXCEPT_(__alloc_traits::is_always_equal::value) {
1282
  if (__alloc() != __c.__alloc()) {
1283
    typedef move_iterator<iterator> _Ip;
1284
    assign(_Ip(__c.begin()), _Ip(__c.end()));
1285
  } else
1286
    __move_assign(__c, true_type());
1287
}
1288

1289
template <class _Tp, class _Allocator>
1290
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1291
    _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
1292
  __vdeallocate();
1293
  __move_assign_alloc(__c); // this can throw
1294
  this->__begin_    = __c.__begin_;
1295
  this->__end_      = __c.__end_;
1296
  this->__end_cap() = __c.__end_cap();
1297
  __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1298
}
1299

1300
template <class _Tp, class _Allocator>
1301
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>&
1302
vector<_Tp, _Allocator>::operator=(const vector& __x) {
1303
  if (this != std::addressof(__x)) {
1304
    __copy_assign_alloc(__x);
1305
    assign(__x.__begin_, __x.__end_);
1306
  }
1307
  return *this;
1308
}
1309

1310
template <class _Tp, class _Allocator>
1311
template <class _InputIterator,
1312
          __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1313
                            is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1314
                        int> >
1315
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) {
1316
  __assign_with_sentinel(__first, __last);
1317
}
1318

1319
template <class _Tp, class _Allocator>
1320
template <class _Iterator, class _Sentinel>
1321
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1322
vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
1323
  clear();
1324
  for (; __first != __last; ++__first)
1325
    emplace_back(*__first);
1326
}
1327

1328
template <class _Tp, class _Allocator>
1329
template <class _ForwardIterator,
1330
          __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1331
                            is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1332
                        int> >
1333
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) {
1334
  __assign_with_size(__first, __last, std::distance(__first, __last));
1335
}
1336

1337
template <class _Tp, class _Allocator>
1338
template <class _ForwardIterator, class _Sentinel>
1339
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
1340
vector<_Tp, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n) {
1341
  size_type __new_size = static_cast<size_type>(__n);
1342
  if (__new_size <= capacity()) {
1343
    if (__new_size > size()) {
1344
      _ForwardIterator __mid = std::next(__first, size());
1345
      std::copy(__first, __mid, this->__begin_);
1346
      __construct_at_end(__mid, __last, __new_size - size());
1347
    } else {
1348
      pointer __m = std::__copy<_ClassicAlgPolicy>(__first, __last, this->__begin_).second;
1349
      this->__destruct_at_end(__m);
1350
    }
1351
  } else {
1352
    __vdeallocate();
1353
    __vallocate(__recommend(__new_size));
1354
    __construct_at_end(__first, __last, __new_size);
1355
  }
1356
}
1357

1358
template <class _Tp, class _Allocator>
1359
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) {
1360
  if (__n <= capacity()) {
1361
    size_type __s = size();
1362
    std::fill_n(this->__begin_, std::min(__n, __s), __u);
1363
    if (__n > __s)
1364
      __construct_at_end(__n - __s, __u);
1365
    else
1366
      this->__destruct_at_end(this->__begin_ + __n);
1367
  } else {
1368
    __vdeallocate();
1369
    __vallocate(__recommend(static_cast<size_type>(__n)));
1370
    __construct_at_end(__n, __u);
1371
  }
1372
}
1373

1374
template <class _Tp, class _Allocator>
1375
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1376
vector<_Tp, _Allocator>::begin() _NOEXCEPT {
1377
  return __make_iter(this->__begin_);
1378
}
1379

1380
template <class _Tp, class _Allocator>
1381
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_iterator
1382
vector<_Tp, _Allocator>::begin() const _NOEXCEPT {
1383
  return __make_iter(this->__begin_);
1384
}
1385

1386
template <class _Tp, class _Allocator>
1387
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1388
vector<_Tp, _Allocator>::end() _NOEXCEPT {
1389
  return __make_iter(this->__end_);
1390
}
1391

1392
template <class _Tp, class _Allocator>
1393
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_iterator
1394
vector<_Tp, _Allocator>::end() const _NOEXCEPT {
1395
  return __make_iter(this->__end_);
1396
}
1397

1398
template <class _Tp, class _Allocator>
1399
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::reference
1400
vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT {
1401
  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
1402
  return this->__begin_[__n];
1403
}
1404

1405
template <class _Tp, class _Allocator>
1406
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_reference
1407
vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT {
1408
  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds");
1409
  return this->__begin_[__n];
1410
}
1411

1412
template <class _Tp, class _Allocator>
1413
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::reference vector<_Tp, _Allocator>::at(size_type __n) {
1414
  if (__n >= size())
1415
    this->__throw_out_of_range();
1416
  return this->__begin_[__n];
1417
}
1418

1419
template <class _Tp, class _Allocator>
1420
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::const_reference
1421
vector<_Tp, _Allocator>::at(size_type __n) const {
1422
  if (__n >= size())
1423
    this->__throw_out_of_range();
1424
  return this->__begin_[__n];
1425
}
1426

1427
template <class _Tp, class _Allocator>
1428
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::reserve(size_type __n) {
1429
  if (__n > capacity()) {
1430
    if (__n > max_size())
1431
      this->__throw_length_error();
1432
    allocator_type& __a = this->__alloc();
1433
    __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1434
    __swap_out_circular_buffer(__v);
1435
  }
1436
}
1437

1438
template <class _Tp, class _Allocator>
1439
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT {
1440
  if (capacity() > size()) {
1441
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1442
    try {
1443
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1444
      allocator_type& __a = this->__alloc();
1445
      __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1446
      __swap_out_circular_buffer(__v);
1447
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1448
    } catch (...) {
1449
    }
1450
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1451
  }
1452
}
1453

1454
template <class _Tp, class _Allocator>
1455
template <class _Up>
1456
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1457
vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) {
1458
  allocator_type& __a = this->__alloc();
1459
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1460
  // __v.push_back(std::forward<_Up>(__x));
1461
  __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Up>(__x));
1462
  __v.__end_++;
1463
  __swap_out_circular_buffer(__v);
1464
  return this->__end_;
1465
}
1466

1467
template <class _Tp, class _Allocator>
1468
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
1469
vector<_Tp, _Allocator>::push_back(const_reference __x) {
1470
  pointer __end = this->__end_;
1471
  if (__end < this->__end_cap()) {
1472
    __construct_one_at_end(__x);
1473
    ++__end;
1474
  } else {
1475
    __end = __push_back_slow_path(__x);
1476
  }
1477
  this->__end_ = __end;
1478
}
1479

1480
template <class _Tp, class _Allocator>
1481
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void vector<_Tp, _Allocator>::push_back(value_type&& __x) {
1482
  pointer __end = this->__end_;
1483
  if (__end < this->__end_cap()) {
1484
    __construct_one_at_end(std::move(__x));
1485
    ++__end;
1486
  } else {
1487
    __end = __push_back_slow_path(std::move(__x));
1488
  }
1489
  this->__end_ = __end;
1490
}
1491

1492
template <class _Tp, class _Allocator>
1493
template <class... _Args>
1494
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer
1495
vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) {
1496
  allocator_type& __a = this->__alloc();
1497
  __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1498
  //    __v.emplace_back(std::forward<_Args>(__args)...);
1499
  __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Args>(__args)...);
1500
  __v.__end_++;
1501
  __swap_out_circular_buffer(__v);
1502
  return this->__end_;
1503
}
1504

1505
template <class _Tp, class _Allocator>
1506
template <class... _Args>
1507
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline
1508
#if _LIBCPP_STD_VER >= 17
1509
    typename vector<_Tp, _Allocator>::reference
1510
#else
1511
    void
1512
#endif
1513
    vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) {
1514
  pointer __end = this->__end_;
1515
  if (__end < this->__end_cap()) {
1516
    __construct_one_at_end(std::forward<_Args>(__args)...);
1517
    ++__end;
1518
  } else {
1519
    __end = __emplace_back_slow_path(std::forward<_Args>(__args)...);
1520
  }
1521
  this->__end_ = __end;
1522
#if _LIBCPP_STD_VER >= 17
1523
  return *(__end - 1);
1524
#endif
1525
}
1526

1527
template <class _Tp, class _Allocator>
1528
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline void vector<_Tp, _Allocator>::pop_back() {
1529
  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector::pop_back called on an empty vector");
1530
  this->__destruct_at_end(this->__end_ - 1);
1531
}
1532

1533
template <class _Tp, class _Allocator>
1534
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1535
vector<_Tp, _Allocator>::erase(const_iterator __position) {
1536
  _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
1537
      __position != end(), "vector::erase(iterator) called with a non-dereferenceable iterator");
1538
  difference_type __ps = __position - cbegin();
1539
  pointer __p          = this->__begin_ + __ps;
1540
  this->__destruct_at_end(std::move(__p + 1, this->__end_, __p));
1541
  return __make_iter(__p);
1542
}
1543

1544
template <class _Tp, class _Allocator>
1545
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1546
vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) {
1547
  _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "vector::erase(first, last) called with invalid range");
1548
  pointer __p = this->__begin_ + (__first - begin());
1549
  if (__first != __last) {
1550
    this->__destruct_at_end(std::move(__p + (__last - __first), this->__end_, __p));
1551
  }
1552
  return __make_iter(__p);
1553
}
1554

1555
template <class _Tp, class _Allocator>
1556
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
1557
vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) {
1558
  pointer __old_last  = this->__end_;
1559
  difference_type __n = __old_last - __to;
1560
  {
1561
    pointer __i = __from_s + __n;
1562
    _ConstructTransaction __tx(*this, __from_e - __i);
1563
    for (pointer __pos = __tx.__pos_; __i < __from_e; ++__i, (void)++__pos, __tx.__pos_ = __pos) {
1564
      __alloc_traits::construct(this->__alloc(), std::__to_address(__pos), std::move(*__i));
1565
    }
1566
  }
1567
  std::move_backward(__from_s, __from_s + __n, __old_last);
1568
}
1569

1570
template <class _Tp, class _Allocator>
1571
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1572
vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) {
1573
  pointer __p = this->__begin_ + (__position - begin());
1574
  if (this->__end_ < this->__end_cap()) {
1575
    if (__p == this->__end_) {
1576
      __construct_one_at_end(__x);
1577
    } else {
1578
      __move_range(__p, this->__end_, __p + 1);
1579
      const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1580
      if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x)))
1581
        ++__xr;
1582
      *__p = *__xr;
1583
    }
1584
  } else {
1585
    allocator_type& __a = this->__alloc();
1586
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1587
    __v.push_back(__x);
1588
    __p = __swap_out_circular_buffer(__v, __p);
1589
  }
1590
  return __make_iter(__p);
1591
}
1592

1593
template <class _Tp, class _Allocator>
1594
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1595
vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) {
1596
  pointer __p = this->__begin_ + (__position - begin());
1597
  if (this->__end_ < this->__end_cap()) {
1598
    if (__p == this->__end_) {
1599
      __construct_one_at_end(std::move(__x));
1600
    } else {
1601
      __move_range(__p, this->__end_, __p + 1);
1602
      *__p = std::move(__x);
1603
    }
1604
  } else {
1605
    allocator_type& __a = this->__alloc();
1606
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1607
    __v.push_back(std::move(__x));
1608
    __p = __swap_out_circular_buffer(__v, __p);
1609
  }
1610
  return __make_iter(__p);
1611
}
1612

1613
template <class _Tp, class _Allocator>
1614
template <class... _Args>
1615
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1616
vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) {
1617
  pointer __p = this->__begin_ + (__position - begin());
1618
  if (this->__end_ < this->__end_cap()) {
1619
    if (__p == this->__end_) {
1620
      __construct_one_at_end(std::forward<_Args>(__args)...);
1621
    } else {
1622
      __temp_value<value_type, _Allocator> __tmp(this->__alloc(), std::forward<_Args>(__args)...);
1623
      __move_range(__p, this->__end_, __p + 1);
1624
      *__p = std::move(__tmp.get());
1625
    }
1626
  } else {
1627
    allocator_type& __a = this->__alloc();
1628
    __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1629
    __v.emplace_back(std::forward<_Args>(__args)...);
1630
    __p = __swap_out_circular_buffer(__v, __p);
1631
  }
1632
  return __make_iter(__p);
1633
}
1634

1635
template <class _Tp, class _Allocator>
1636
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1637
vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) {
1638
  pointer __p = this->__begin_ + (__position - begin());
1639
  if (__n > 0) {
1640
    // We can't compare unrelated pointers inside constant expressions
1641
    if (!__libcpp_is_constant_evaluated() && __n <= static_cast<size_type>(this->__end_cap() - this->__end_)) {
1642
      size_type __old_n  = __n;
1643
      pointer __old_last = this->__end_;
1644
      if (__n > static_cast<size_type>(this->__end_ - __p)) {
1645
        size_type __cx = __n - (this->__end_ - __p);
1646
        __construct_at_end(__cx, __x);
1647
        __n -= __cx;
1648
      }
1649
      if (__n > 0) {
1650
        __move_range(__p, __old_last, __p + __old_n);
1651
        const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1652
        if (__p <= __xr && __xr < this->__end_)
1653
          __xr += __old_n;
1654
        std::fill_n(__p, __n, *__xr);
1655
      }
1656
    } else {
1657
      allocator_type& __a = this->__alloc();
1658
      __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1659
      __v.__construct_at_end(__n, __x);
1660
      __p = __swap_out_circular_buffer(__v, __p);
1661
    }
1662
  }
1663
  return __make_iter(__p);
1664
}
1665
template <class _Tp, class _Allocator>
1666
template <class _InputIterator,
1667
          __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value &&
1668
                            is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value,
1669
                        int> >
1670
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1671
vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
1672
  return __insert_with_sentinel(__position, __first, __last);
1673
}
1674

1675
template <class _Tp, class _Allocator>
1676
template <class _InputIterator, class _Sentinel>
1677
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1678
vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
1679
  difference_type __off = __position - begin();
1680
  pointer __p           = this->__begin_ + __off;
1681
  allocator_type& __a   = this->__alloc();
1682
  pointer __old_last    = this->__end_;
1683
  for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) {
1684
    __construct_one_at_end(*__first);
1685
  }
1686
  __split_buffer<value_type, allocator_type&> __v(__a);
1687
  if (__first != __last) {
1688
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1689
    try {
1690
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1691
      __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last));
1692
      difference_type __old_size = __old_last - this->__begin_;
1693
      difference_type __old_p    = __p - this->__begin_;
1694
      reserve(__recommend(size() + __v.size()));
1695
      __p        = this->__begin_ + __old_p;
1696
      __old_last = this->__begin_ + __old_size;
1697
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
1698
    } catch (...) {
1699
      erase(__make_iter(__old_last), end());
1700
      throw;
1701
    }
1702
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
1703
  }
1704
  __p = std::rotate(__p, __old_last, this->__end_);
1705
  insert(__make_iter(__p), std::make_move_iterator(__v.begin()), std::make_move_iterator(__v.end()));
1706
  return begin() + __off;
1707
}
1708

1709
template <class _Tp, class _Allocator>
1710
template <class _ForwardIterator,
1711
          __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value &&
1712
                            is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value,
1713
                        int> >
1714
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator
1715
vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
1716
  return __insert_with_size(__position, __first, __last, std::distance(__first, __last));
1717
}
1718

1719
template <class _Tp, class _Allocator>
1720
template <class _Iterator, class _Sentinel>
1721
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator
1722
vector<_Tp, _Allocator>::__insert_with_size(
1723
    const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n) {
1724
  auto __insertion_size = __n;
1725
  pointer __p           = this->__begin_ + (__position - begin());
1726
  if (__n > 0) {
1727
    if (__n <= this->__end_cap() - this->__end_) {
1728
      size_type __old_n    = __n;
1729
      pointer __old_last   = this->__end_;
1730
      _Iterator __m        = std::next(__first, __n);
1731
      difference_type __dx = this->__end_ - __p;
1732
      if (__n > __dx) {
1733
        __m                    = __first;
1734
        difference_type __diff = this->__end_ - __p;
1735
        std::advance(__m, __diff);
1736
        __construct_at_end(__m, __last, __n - __diff);
1737
        __n = __dx;
1738
      }
1739
      if (__n > 0) {
1740
        __move_range(__p, __old_last, __p + __old_n);
1741
        std::copy(__first, __m, __p);
1742
      }
1743
    } else {
1744
      allocator_type& __a = this->__alloc();
1745
      __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1746
      __v.__construct_at_end_with_size(__first, __insertion_size);
1747
      __p = __swap_out_circular_buffer(__v, __p);
1748
    }
1749
  }
1750
  return __make_iter(__p);
1751
}
1752

1753
template <class _Tp, class _Allocator>
1754
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __sz) {
1755
  size_type __cs = size();
1756
  if (__cs < __sz)
1757
    this->__append(__sz - __cs);
1758
  else if (__cs > __sz)
1759
    this->__destruct_at_end(this->__begin_ + __sz);
1760
}
1761

1762
template <class _Tp, class _Allocator>
1763
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) {
1764
  size_type __cs = size();
1765
  if (__cs < __sz)
1766
    this->__append(__sz - __cs, __x);
1767
  else if (__cs > __sz)
1768
    this->__destruct_at_end(this->__begin_ + __sz);
1769
}
1770

1771
template <class _Tp, class _Allocator>
1772
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::swap(vector& __x)
1773
#if _LIBCPP_STD_VER >= 14
1774
    _NOEXCEPT
1775
#else
1776
    _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
1777
#endif
1778
{
1779
  _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR(
1780
      __alloc_traits::propagate_on_container_swap::value || this->__alloc() == __x.__alloc(),
1781
      "vector::swap: Either propagate_on_container_swap must be true"
1782
      " or the allocators must compare equal");
1783
  std::swap(this->__begin_, __x.__begin_);
1784
  std::swap(this->__end_, __x.__end_);
1785
  std::swap(this->__end_cap(), __x.__end_cap());
1786
  std::__swap_allocator(
1787
      this->__alloc(), __x.__alloc(), integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
1788
}
1789

1790
template <class _Tp, class _Allocator>
1791
_LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<_Tp, _Allocator>::__invariants() const {
1792
  if (this->__begin_ == nullptr) {
1793
    if (this->__end_ != nullptr || this->__end_cap() != nullptr)
1794
      return false;
1795
  } else {
1796
    if (this->__begin_ > this->__end_)
1797
      return false;
1798
    if (this->__begin_ == this->__end_cap())
1799
      return false;
1800
    if (this->__end_ > this->__end_cap())
1801
      return false;
1802
  }
1803
  return true;
1804
}
1805

1806
// vector<bool>
1807

1808
template <class _Allocator>
1809
class vector<bool, _Allocator>;
1810

1811
template <class _Allocator>
1812
struct hash<vector<bool, _Allocator> >;
1813

1814
template <class _Allocator>
1815
struct __has_storage_type<vector<bool, _Allocator> > {
1816
  static const bool value = true;
1817
};
1818

1819
template <class _Allocator>
1820
class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> {
1821
public:
1822
  typedef vector __self;
1823
  typedef bool value_type;
1824
  typedef _Allocator allocator_type;
1825
  typedef allocator_traits<allocator_type> __alloc_traits;
1826
  typedef typename __alloc_traits::size_type size_type;
1827
  typedef typename __alloc_traits::difference_type difference_type;
1828
  typedef size_type __storage_type;
1829
  typedef __bit_iterator<vector, false> pointer;
1830
  typedef __bit_iterator<vector, true> const_pointer;
1831
  typedef pointer iterator;
1832
  typedef const_pointer const_iterator;
1833
  typedef std::reverse_iterator<iterator> reverse_iterator;
1834
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1835

1836
private:
1837
  typedef __rebind_alloc<__alloc_traits, __storage_type> __storage_allocator;
1838
  typedef allocator_traits<__storage_allocator> __storage_traits;
1839
  typedef typename __storage_traits::pointer __storage_pointer;
1840
  typedef typename __storage_traits::const_pointer __const_storage_pointer;
1841

1842
  __storage_pointer __begin_;
1843
  size_type __size_;
1844
  __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
1845

1846
public:
1847
  typedef __bit_reference<vector> reference;
1848
#ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
1849
  using const_reference = bool;
1850
#else
1851
  typedef __bit_const_reference<vector> const_reference;
1852
#endif
1853

1854
private:
1855
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type& __cap() _NOEXCEPT { return __cap_alloc_.first(); }
1856
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const size_type& __cap() const _NOEXCEPT {
1857
    return __cap_alloc_.first();
1858
  }
1859
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __storage_allocator& __alloc() _NOEXCEPT {
1860
    return __cap_alloc_.second();
1861
  }
1862
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const __storage_allocator& __alloc() const _NOEXCEPT {
1863
    return __cap_alloc_.second();
1864
  }
1865

1866
  static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
1867

1868
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
1869
  __internal_cap_to_external(size_type __n) _NOEXCEPT {
1870
    return __n * __bits_per_word;
1871
  }
1872
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type
1873
  __external_cap_to_internal(size_type __n) _NOEXCEPT {
1874
    return (__n - 1) / __bits_per_word + 1;
1875
  }
1876

1877
public:
1878
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector()
1879
      _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
1880

1881
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(const allocator_type& __a)
1882
#if _LIBCPP_STD_VER <= 14
1883
      _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
1884
#else
1885
      _NOEXCEPT;
1886
#endif
1887

1888
private:
1889
  class __destroy_vector {
1890
  public:
1891
    _LIBCPP_CONSTEXPR _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {}
1892

1893
    _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void operator()() {
1894
      if (__vec_.__begin_ != nullptr)
1895
        __storage_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.__cap());
1896
    }
1897

1898
  private:
1899
    vector& __vec_;
1900
  };
1901

1902
public:
1903
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 ~vector() { __destroy_vector (*this)(); }
1904

1905
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n);
1906
#if _LIBCPP_STD_VER >= 14
1907
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 explicit vector(size_type __n, const allocator_type& __a);
1908
#endif
1909
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(size_type __n, const value_type& __v);
1910
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1911
  vector(size_type __n, const value_type& __v, const allocator_type& __a);
1912
  template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1913
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_InputIterator __first, _InputIterator __last);
1914
  template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1915
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1916
  vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
1917
  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1918
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last);
1919
  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1920
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1921
  vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a);
1922

1923
#if _LIBCPP_STD_VER >= 23
1924
  template <_ContainerCompatibleRange<bool> _Range>
1925
  _LIBCPP_HIDE_FROM_ABI constexpr vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type())
1926
      : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
1927
    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
1928
      auto __n = static_cast<size_type>(ranges::distance(__range));
1929
      __init_with_size(ranges::begin(__range), ranges::end(__range), __n);
1930

1931
    } else {
1932
      __init_with_sentinel(ranges::begin(__range), ranges::end(__range));
1933
    }
1934
  }
1935
#endif
1936

1937
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v);
1938
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a);
1939
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v);
1940

1941
#ifndef _LIBCPP_CXX03_LANG
1942
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(initializer_list<value_type> __il);
1943
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1944
  vector(initializer_list<value_type> __il, const allocator_type& __a);
1945

1946
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(initializer_list<value_type> __il) {
1947
    assign(__il.begin(), __il.end());
1948
    return *this;
1949
  }
1950

1951
#endif // !_LIBCPP_CXX03_LANG
1952

1953
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(vector&& __v)
1954
#if _LIBCPP_STD_VER >= 17
1955
      noexcept;
1956
#else
1957
      _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
1958
#endif
1959
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
1960
  vector(vector&& __v, const __type_identity_t<allocator_type>& __a);
1961
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(vector&& __v)
1962
      _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value);
1963

1964
  template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
1965
  void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_InputIterator __first, _InputIterator __last);
1966
  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
1967
  void _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last);
1968

1969
#if _LIBCPP_STD_VER >= 23
1970
  template <_ContainerCompatibleRange<bool> _Range>
1971
  _LIBCPP_HIDE_FROM_ABI constexpr void assign_range(_Range&& __range) {
1972
    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
1973
      auto __n = static_cast<size_type>(ranges::distance(__range));
1974
      __assign_with_size(ranges::begin(__range), ranges::end(__range), __n);
1975

1976
    } else {
1977
      __assign_with_sentinel(ranges::begin(__range), ranges::end(__range));
1978
    }
1979
  }
1980
#endif
1981

1982
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x);
1983

1984
#ifndef _LIBCPP_CXX03_LANG
1985
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(initializer_list<value_type> __il) {
1986
    assign(__il.begin(), __il.end());
1987
  }
1988
#endif
1989

1990
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 allocator_type get_allocator() const _NOEXCEPT {
1991
    return allocator_type(this->__alloc());
1992
  }
1993

1994
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type max_size() const _NOEXCEPT;
1995
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type capacity() const _NOEXCEPT {
1996
    return __internal_cap_to_external(__cap());
1997
  }
1998
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type size() const _NOEXCEPT { return __size_; }
1999
  _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool empty() const _NOEXCEPT {
2000
    return __size_ == 0;
2001
  }
2002
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void reserve(size_type __n);
2003
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void shrink_to_fit() _NOEXCEPT;
2004

2005
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator begin() _NOEXCEPT { return __make_iter(0); }
2006
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator begin() const _NOEXCEPT { return __make_iter(0); }
2007
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator end() _NOEXCEPT { return __make_iter(__size_); }
2008
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator end() const _NOEXCEPT {
2009
    return __make_iter(__size_);
2010
  }
2011

2012
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rbegin() _NOEXCEPT {
2013
    return reverse_iterator(end());
2014
  }
2015
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rbegin() const _NOEXCEPT {
2016
    return const_reverse_iterator(end());
2017
  }
2018
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reverse_iterator rend() _NOEXCEPT {
2019
    return reverse_iterator(begin());
2020
  }
2021
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator rend() const _NOEXCEPT {
2022
    return const_reverse_iterator(begin());
2023
  }
2024

2025
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cbegin() const _NOEXCEPT { return __make_iter(0); }
2026
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator cend() const _NOEXCEPT {
2027
    return __make_iter(__size_);
2028
  }
2029
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crbegin() const _NOEXCEPT {
2030
    return rbegin();
2031
  }
2032
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
2033

2034
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference operator[](size_type __n) { return __make_ref(__n); }
2035
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference operator[](size_type __n) const {
2036
    return __make_ref(__n);
2037
  }
2038
  _LIBCPP_HIDE_FROM_ABI reference at(size_type __n);
2039
  _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const;
2040

2041
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference front() { return __make_ref(0); }
2042
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference front() const { return __make_ref(0); }
2043
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference back() { return __make_ref(__size_ - 1); }
2044
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference back() const { return __make_ref(__size_ - 1); }
2045

2046
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void push_back(const value_type& __x);
2047
#if _LIBCPP_STD_VER >= 14
2048
  template <class... _Args>
2049
#  if _LIBCPP_STD_VER >= 17
2050
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference emplace_back(_Args&&... __args)
2051
#  else
2052
  _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args)
2053
#  endif
2054
  {
2055
    push_back(value_type(std::forward<_Args>(__args)...));
2056
#  if _LIBCPP_STD_VER >= 17
2057
    return this->back();
2058
#  endif
2059
  }
2060
#endif
2061

2062
#if _LIBCPP_STD_VER >= 23
2063
  template <_ContainerCompatibleRange<bool> _Range>
2064
  _LIBCPP_HIDE_FROM_ABI constexpr void append_range(_Range&& __range) {
2065
    insert_range(end(), std::forward<_Range>(__range));
2066
  }
2067
#endif
2068

2069
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() { --__size_; }
2070

2071
#if _LIBCPP_STD_VER >= 14
2072
  template <class... _Args>
2073
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator emplace(const_iterator __position, _Args&&... __args) {
2074
    return insert(__position, value_type(std::forward<_Args>(__args)...));
2075
  }
2076
#endif
2077

2078
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, const value_type& __x);
2079
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
2080
  insert(const_iterator __position, size_type __n, const value_type& __x);
2081
  template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0>
2082
  iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2083
  insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2084
  template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0>
2085
  iterator _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20
2086
  insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2087

2088
#if _LIBCPP_STD_VER >= 23
2089
  template <_ContainerCompatibleRange<bool> _Range>
2090
  _LIBCPP_HIDE_FROM_ABI constexpr iterator insert_range(const_iterator __position, _Range&& __range) {
2091
    if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) {
2092
      auto __n = static_cast<size_type>(ranges::distance(__range));
2093
      return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n);
2094

2095
    } else {
2096
      return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range));
2097
    }
2098
  }
2099
#endif
2100

2101
#ifndef _LIBCPP_CXX03_LANG
2102
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator
2103
  insert(const_iterator __position, initializer_list<value_type> __il) {
2104
    return insert(__position, __il.begin(), __il.end());
2105
  }
2106
#endif
2107

2108
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __position);
2109
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator erase(const_iterator __first, const_iterator __last);
2110

2111
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void clear() _NOEXCEPT { __size_ = 0; }
2112

2113
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void swap(vector&)
2114
#if _LIBCPP_STD_VER >= 14
2115
      _NOEXCEPT;
2116
#else
2117
      _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>);
2118
#endif
2119
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static void swap(reference __x, reference __y) _NOEXCEPT {
2120
    std::swap(__x, __y);
2121
  }
2122

2123
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void resize(size_type __sz, value_type __x = false);
2124
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void flip() _NOEXCEPT;
2125

2126
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 bool __invariants() const;
2127

2128
private:
2129
  _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { std::__throw_length_error("vector"); }
2130

2131
  _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { std::__throw_out_of_range("vector"); }
2132

2133
  template <class _InputIterator, class _Sentinel>
2134
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2135
  __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) {
2136
    auto __guard = std::__make_exception_guard(__destroy_vector(*this));
2137

2138
    if (__n > 0) {
2139
      __vallocate(__n);
2140
      __construct_at_end(std::move(__first), std::move(__last), __n);
2141
    }
2142

2143
    __guard.__complete();
2144
  }
2145

2146
  template <class _InputIterator, class _Sentinel>
2147
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2148
  __init_with_sentinel(_InputIterator __first, _Sentinel __last) {
2149
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2150
    try {
2151
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
2152
      for (; __first != __last; ++__first)
2153
        push_back(*__first);
2154
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2155
    } catch (...) {
2156
      if (__begin_ != nullptr)
2157
        __storage_traits::deallocate(__alloc(), __begin_, __cap());
2158
      throw;
2159
    }
2160
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
2161
  }
2162

2163
  template <class _Iterator, class _Sentinel>
2164
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last);
2165

2166
  template <class _ForwardIterator, class _Sentinel>
2167
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
2168
  __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns);
2169

2170
  template <class _InputIterator, class _Sentinel>
2171
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
2172
  __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last);
2173

2174
  template <class _Iterator, class _Sentinel>
2175
  _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator
2176
  __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n);
2177

2178
  //  Allocate space for __n objects
2179
  //  throws length_error if __n > max_size()
2180
  //  throws (probably bad_alloc) if memory run out
2181
  //  Precondition:  __begin_ == __end_ == __cap() == 0
2182
  //  Precondition:  __n > 0
2183
  //  Postcondition:  capacity() >= __n
2184
  //  Postcondition:  size() == 0
2185
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vallocate(size_type __n) {
2186
    if (__n > max_size())
2187
      __throw_length_error();
2188
    auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n));
2189
    __begin_          = __allocation.ptr;
2190
    __size_           = 0;
2191
    __cap()           = __allocation.count;
2192
    if (__libcpp_is_constant_evaluated()) {
2193
      for (size_type __i = 0; __i != __cap(); ++__i)
2194
        std::__construct_at(std::__to_address(__begin_) + __i);
2195
    }
2196
  }
2197

2198
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __vdeallocate() _NOEXCEPT;
2199
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 static size_type __align_it(size_type __new_size) _NOEXCEPT {
2200
    return (__new_size + (__bits_per_word - 1)) & ~((size_type)__bits_per_word - 1);
2201
  }
2202
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const;
2203
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __construct_at_end(size_type __n, bool __x);
2204
  template <class _InputIterator, class _Sentinel>
2205
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2206
  __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n);
2207
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __append(size_type __n, const_reference __x);
2208
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference __make_ref(size_type __pos) _NOEXCEPT {
2209
    return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
2210
  }
2211
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_reference __make_ref(size_type __pos) const _NOEXCEPT {
2212
    return __bit_const_reference<vector>(
2213
        __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);
2214
  }
2215
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __make_iter(size_type __pos) _NOEXCEPT {
2216
    return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
2217
  }
2218
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 const_iterator __make_iter(size_type __pos) const _NOEXCEPT {
2219
    return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));
2220
  }
2221
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT {
2222
    return begin() + (__p - cbegin());
2223
  }
2224

2225
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __v) {
2226
    __copy_assign_alloc(
2227
        __v, integral_constant<bool, __storage_traits::propagate_on_container_copy_assignment::value>());
2228
  }
2229
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector& __c, true_type) {
2230
    if (__alloc() != __c.__alloc())
2231
      __vdeallocate();
2232
    __alloc() = __c.__alloc();
2233
  }
2234

2235
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __copy_assign_alloc(const vector&, false_type) {}
2236

2237
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, false_type);
2238
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign(vector& __c, true_type)
2239
      _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2240
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c)
2241
      _NOEXCEPT_(!__storage_traits::propagate_on_container_move_assignment::value ||
2242
                 is_nothrow_move_assignable<allocator_type>::value) {
2243
    __move_assign_alloc(
2244
        __c, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
2245
  }
2246
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector& __c, true_type)
2247
      _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
2248
    __alloc() = std::move(__c.__alloc());
2249
  }
2250

2251
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __move_assign_alloc(vector&, false_type) _NOEXCEPT {}
2252

2253
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t __hash_code() const _NOEXCEPT;
2254

2255
  friend class __bit_reference<vector>;
2256
  friend class __bit_const_reference<vector>;
2257
  friend class __bit_iterator<vector, false>;
2258
  friend class __bit_iterator<vector, true>;
2259
  friend struct __bit_array<vector>;
2260
  friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
2261
};
2262

2263
template <class _Allocator>
2264
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT {
2265
  if (this->__begin_ != nullptr) {
2266
    __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2267
    this->__begin_ = nullptr;
2268
    this->__size_ = this->__cap() = 0;
2269
  }
2270
}
2271

2272
template <class _Allocator>
2273
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
2274
vector<bool, _Allocator>::max_size() const _NOEXCEPT {
2275
  size_type __amax = __storage_traits::max_size(__alloc());
2276
  size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2277
  if (__nmax / __bits_per_word <= __amax)
2278
    return __nmax;
2279
  return __internal_cap_to_external(__amax);
2280
}
2281

2282
//  Precondition:  __new_size > capacity()
2283
template <class _Allocator>
2284
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::size_type
2285
vector<bool, _Allocator>::__recommend(size_type __new_size) const {
2286
  const size_type __ms = max_size();
2287
  if (__new_size > __ms)
2288
    this->__throw_length_error();
2289
  const size_type __cap = capacity();
2290
  if (__cap >= __ms / 2)
2291
    return __ms;
2292
  return std::max(2 * __cap, __align_it(__new_size));
2293
}
2294

2295
//  Default constructs __n objects starting at __end_
2296
//  Precondition:  __n > 0
2297
//  Precondition:  size() + __n <= capacity()
2298
//  Postcondition:  size() == size() + __n
2299
template <class _Allocator>
2300
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void
2301
vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) {
2302
  size_type __old_size = this->__size_;
2303
  this->__size_ += __n;
2304
  if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) {
2305
    if (this->__size_ <= __bits_per_word)
2306
      this->__begin_[0] = __storage_type(0);
2307
    else
2308
      this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2309
  }
2310
  std::fill_n(__make_iter(__old_size), __n, __x);
2311
}
2312

2313
template <class _Allocator>
2314
template <class _InputIterator, class _Sentinel>
2315
_LIBCPP_CONSTEXPR_SINCE_CXX20 void
2316
vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) {
2317
  size_type __old_size = this->__size_;
2318
  this->__size_ += __n;
2319
  if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) {
2320
    if (this->__size_ <= __bits_per_word)
2321
      this->__begin_[0] = __storage_type(0);
2322
    else
2323
      this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2324
  }
2325
  std::__copy<_ClassicAlgPolicy>(__first, __last, __make_iter(__old_size));
2326
}
2327

2328
template <class _Allocator>
2329
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector()
2330
    _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2331
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {}
2332

2333
template <class _Allocator>
2334
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const allocator_type& __a)
2335
#if _LIBCPP_STD_VER <= 14
2336
    _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
2337
#else
2338
        _NOEXCEPT
2339
#endif
2340
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2341
}
2342

2343
template <class _Allocator>
2344
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n)
2345
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2346
  if (__n > 0) {
2347
    __vallocate(__n);
2348
    __construct_at_end(__n, false);
2349
  }
2350
}
2351

2352
#if _LIBCPP_STD_VER >= 14
2353
template <class _Allocator>
2354
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2355
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2356
  if (__n > 0) {
2357
    __vallocate(__n);
2358
    __construct_at_end(__n, false);
2359
  }
2360
}
2361
#endif
2362

2363
template <class _Allocator>
2364
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2365
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2366
  if (__n > 0) {
2367
    __vallocate(__n);
2368
    __construct_at_end(__n, __x);
2369
  }
2370
}
2371

2372
template <class _Allocator>
2373
_LIBCPP_CONSTEXPR_SINCE_CXX20
2374
vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2375
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2376
  if (__n > 0) {
2377
    __vallocate(__n);
2378
    __construct_at_end(__n, __x);
2379
  }
2380
}
2381

2382
template <class _Allocator>
2383
template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2384
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last)
2385
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2386
  __init_with_sentinel(__first, __last);
2387
}
2388

2389
template <class _Allocator>
2390
template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2391
_LIBCPP_CONSTEXPR_SINCE_CXX20
2392
vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a)
2393
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2394
  __init_with_sentinel(__first, __last);
2395
}
2396

2397
template <class _Allocator>
2398
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2399
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last)
2400
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2401
  auto __n = static_cast<size_type>(std::distance(__first, __last));
2402
  __init_with_size(__first, __last, __n);
2403
}
2404

2405
template <class _Allocator>
2406
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2407
_LIBCPP_CONSTEXPR_SINCE_CXX20
2408
vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a)
2409
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2410
  auto __n = static_cast<size_type>(std::distance(__first, __last));
2411
  __init_with_size(__first, __last, __n);
2412
}
2413

2414
#ifndef _LIBCPP_CXX03_LANG
2415

2416
template <class _Allocator>
2417
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2418
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {
2419
  size_type __n = static_cast<size_type>(__il.size());
2420
  if (__n > 0) {
2421
    __vallocate(__n);
2422
    __construct_at_end(__il.begin(), __il.end(), __n);
2423
  }
2424
}
2425

2426
template <class _Allocator>
2427
_LIBCPP_CONSTEXPR_SINCE_CXX20
2428
vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2429
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {
2430
  size_type __n = static_cast<size_type>(__il.size());
2431
  if (__n > 0) {
2432
    __vallocate(__n);
2433
    __construct_at_end(__il.begin(), __il.end(), __n);
2434
  }
2435
}
2436

2437
#endif // _LIBCPP_CXX03_LANG
2438

2439
template <class _Allocator>
2440
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v)
2441
    : __begin_(nullptr),
2442
      __size_(0),
2443
      __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) {
2444
  if (__v.size() > 0) {
2445
    __vallocate(__v.size());
2446
    __construct_at_end(__v.begin(), __v.end(), __v.size());
2447
  }
2448
}
2449

2450
template <class _Allocator>
2451
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2452
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) {
2453
  if (__v.size() > 0) {
2454
    __vallocate(__v.size());
2455
    __construct_at_end(__v.begin(), __v.end(), __v.size());
2456
  }
2457
}
2458

2459
template <class _Allocator>
2460
_LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>& vector<bool, _Allocator>::operator=(const vector& __v) {
2461
  if (this != std::addressof(__v)) {
2462
    __copy_assign_alloc(__v);
2463
    if (__v.__size_) {
2464
      if (__v.__size_ > capacity()) {
2465
        __vdeallocate();
2466
        __vallocate(__v.__size_);
2467
      }
2468
      std::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2469
    }
2470
    __size_ = __v.__size_;
2471
  }
2472
  return *this;
2473
}
2474

2475
template <class _Allocator>
2476
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>::vector(vector&& __v)
2477
#if _LIBCPP_STD_VER >= 17
2478
    _NOEXCEPT
2479
#else
2480
    _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2481
#endif
2482
    : __begin_(__v.__begin_),
2483
      __size_(__v.__size_),
2484
      __cap_alloc_(std::move(__v.__cap_alloc_)) {
2485
  __v.__begin_ = nullptr;
2486
  __v.__size_  = 0;
2487
  __v.__cap()  = 0;
2488
}
2489

2490
template <class _Allocator>
2491
_LIBCPP_CONSTEXPR_SINCE_CXX20
2492
vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a)
2493
    : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) {
2494
  if (__a == allocator_type(__v.__alloc())) {
2495
    this->__begin_ = __v.__begin_;
2496
    this->__size_  = __v.__size_;
2497
    this->__cap()  = __v.__cap();
2498
    __v.__begin_   = nullptr;
2499
    __v.__cap() = __v.__size_ = 0;
2500
  } else if (__v.size() > 0) {
2501
    __vallocate(__v.size());
2502
    __construct_at_end(__v.begin(), __v.end(), __v.size());
2503
  }
2504
}
2505

2506
template <class _Allocator>
2507
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<bool, _Allocator>&
2508
vector<bool, _Allocator>::operator=(vector&& __v)
2509
    _NOEXCEPT_(__noexcept_move_assign_container<_Allocator, __alloc_traits>::value) {
2510
  __move_assign(__v, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>());
2511
  return *this;
2512
}
2513

2514
template <class _Allocator>
2515
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, false_type) {
2516
  if (__alloc() != __c.__alloc())
2517
    assign(__c.begin(), __c.end());
2518
  else
2519
    __move_assign(__c, true_type());
2520
}
2521

2522
template <class _Allocator>
2523
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2524
    _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) {
2525
  __vdeallocate();
2526
  __move_assign_alloc(__c);
2527
  this->__begin_ = __c.__begin_;
2528
  this->__size_  = __c.__size_;
2529
  this->__cap()  = __c.__cap();
2530
  __c.__begin_   = nullptr;
2531
  __c.__cap() = __c.__size_ = 0;
2532
}
2533

2534
template <class _Allocator>
2535
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) {
2536
  __size_ = 0;
2537
  if (__n > 0) {
2538
    size_type __c = capacity();
2539
    if (__n <= __c)
2540
      __size_ = __n;
2541
    else {
2542
      vector __v(get_allocator());
2543
      __v.reserve(__recommend(__n));
2544
      __v.__size_ = __n;
2545
      swap(__v);
2546
    }
2547
    std::fill_n(begin(), __n, __x);
2548
  }
2549
}
2550

2551
template <class _Allocator>
2552
template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2553
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) {
2554
  __assign_with_sentinel(__first, __last);
2555
}
2556

2557
template <class _Allocator>
2558
template <class _Iterator, class _Sentinel>
2559
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
2560
vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) {
2561
  clear();
2562
  for (; __first != __last; ++__first)
2563
    push_back(*__first);
2564
}
2565

2566
template <class _Allocator>
2567
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2568
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) {
2569
  __assign_with_size(__first, __last, std::distance(__first, __last));
2570
}
2571

2572
template <class _Allocator>
2573
template <class _ForwardIterator, class _Sentinel>
2574
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void
2575
vector<bool, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns) {
2576
  _LIBCPP_ASSERT_VALID_INPUT_RANGE(__ns >= 0, "invalid range specified");
2577

2578
  clear();
2579

2580
  const size_t __n = static_cast<size_type>(__ns);
2581
  if (__n) {
2582
    if (__n > capacity()) {
2583
      __vdeallocate();
2584
      __vallocate(__n);
2585
    }
2586
    __construct_at_end(__first, __last, __n);
2587
  }
2588
}
2589

2590
template <class _Allocator>
2591
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::reserve(size_type __n) {
2592
  if (__n > capacity()) {
2593
    if (__n > max_size())
2594
      this->__throw_length_error();
2595
    vector __v(this->get_allocator());
2596
    __v.__vallocate(__n);
2597
    __v.__construct_at_end(this->begin(), this->end(), this->size());
2598
    swap(__v);
2599
  }
2600
}
2601

2602
template <class _Allocator>
2603
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT {
2604
  if (__external_cap_to_internal(size()) > __cap()) {
2605
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2606
    try {
2607
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
2608
      vector(*this, allocator_type(__alloc())).swap(*this);
2609
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2610
    } catch (...) {
2611
    }
2612
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
2613
  }
2614
}
2615

2616
template <class _Allocator>
2617
typename vector<bool, _Allocator>::reference vector<bool, _Allocator>::at(size_type __n) {
2618
  if (__n >= size())
2619
    this->__throw_out_of_range();
2620
  return (*this)[__n];
2621
}
2622

2623
template <class _Allocator>
2624
typename vector<bool, _Allocator>::const_reference vector<bool, _Allocator>::at(size_type __n) const {
2625
  if (__n >= size())
2626
    this->__throw_out_of_range();
2627
  return (*this)[__n];
2628
}
2629

2630
template <class _Allocator>
2631
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::push_back(const value_type& __x) {
2632
  if (this->__size_ == this->capacity())
2633
    reserve(__recommend(this->__size_ + 1));
2634
  ++this->__size_;
2635
  back() = __x;
2636
}
2637

2638
template <class _Allocator>
2639
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2640
vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) {
2641
  iterator __r;
2642
  if (size() < capacity()) {
2643
    const_iterator __old_end = end();
2644
    ++__size_;
2645
    std::copy_backward(__position, __old_end, end());
2646
    __r = __const_iterator_cast(__position);
2647
  } else {
2648
    vector __v(get_allocator());
2649
    __v.reserve(__recommend(__size_ + 1));
2650
    __v.__size_ = __size_ + 1;
2651
    __r         = std::copy(cbegin(), __position, __v.begin());
2652
    std::copy_backward(__position, cend(), __v.end());
2653
    swap(__v);
2654
  }
2655
  *__r = __x;
2656
  return __r;
2657
}
2658

2659
template <class _Allocator>
2660
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2661
vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) {
2662
  iterator __r;
2663
  size_type __c = capacity();
2664
  if (__n <= __c && size() <= __c - __n) {
2665
    const_iterator __old_end = end();
2666
    __size_ += __n;
2667
    std::copy_backward(__position, __old_end, end());
2668
    __r = __const_iterator_cast(__position);
2669
  } else {
2670
    vector __v(get_allocator());
2671
    __v.reserve(__recommend(__size_ + __n));
2672
    __v.__size_ = __size_ + __n;
2673
    __r         = std::copy(cbegin(), __position, __v.begin());
2674
    std::copy_backward(__position, cend(), __v.end());
2675
    swap(__v);
2676
  }
2677
  std::fill_n(__r, __n, __x);
2678
  return __r;
2679
}
2680

2681
template <class _Allocator>
2682
template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> >
2683
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2684
vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) {
2685
  return __insert_with_sentinel(__position, __first, __last);
2686
}
2687

2688
template <class _Allocator>
2689
template <class _InputIterator, class _Sentinel>
2690
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
2691
vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) {
2692
  difference_type __off = __position - begin();
2693
  iterator __p          = __const_iterator_cast(__position);
2694
  iterator __old_end    = end();
2695
  for (; size() != capacity() && __first != __last; ++__first) {
2696
    ++this->__size_;
2697
    back() = *__first;
2698
  }
2699
  vector __v(get_allocator());
2700
  if (__first != __last) {
2701
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2702
    try {
2703
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
2704
      __v.__assign_with_sentinel(std::move(__first), std::move(__last));
2705
      difference_type __old_size = static_cast<difference_type>(__old_end - begin());
2706
      difference_type __old_p    = __p - begin();
2707
      reserve(__recommend(size() + __v.size()));
2708
      __p       = begin() + __old_p;
2709
      __old_end = begin() + __old_size;
2710
#ifndef _LIBCPP_HAS_NO_EXCEPTIONS
2711
    } catch (...) {
2712
      erase(__old_end, end());
2713
      throw;
2714
    }
2715
#endif // _LIBCPP_HAS_NO_EXCEPTIONS
2716
  }
2717
  __p = std::rotate(__p, __old_end, end());
2718
  insert(__p, __v.begin(), __v.end());
2719
  return begin() + __off;
2720
}
2721

2722
template <class _Allocator>
2723
template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> >
2724
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2725
vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) {
2726
  return __insert_with_size(__position, __first, __last, std::distance(__first, __last));
2727
}
2728

2729
template <class _Allocator>
2730
template <class _ForwardIterator, class _Sentinel>
2731
_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator
2732
vector<bool, _Allocator>::__insert_with_size(
2733
    const_iterator __position, _ForwardIterator __first, _Sentinel __last, difference_type __n_signed) {
2734
  _LIBCPP_ASSERT_VALID_INPUT_RANGE(__n_signed >= 0, "invalid range specified");
2735
  const size_type __n = static_cast<size_type>(__n_signed);
2736
  iterator __r;
2737
  size_type __c = capacity();
2738
  if (__n <= __c && size() <= __c - __n) {
2739
    const_iterator __old_end = end();
2740
    __size_ += __n;
2741
    std::copy_backward(__position, __old_end, end());
2742
    __r = __const_iterator_cast(__position);
2743
  } else {
2744
    vector __v(get_allocator());
2745
    __v.reserve(__recommend(__size_ + __n));
2746
    __v.__size_ = __size_ + __n;
2747
    __r         = std::copy(cbegin(), __position, __v.begin());
2748
    std::copy_backward(__position, cend(), __v.end());
2749
    swap(__v);
2750
  }
2751
  std::__copy<_ClassicAlgPolicy>(__first, __last, __r);
2752
  return __r;
2753
}
2754

2755
template <class _Allocator>
2756
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2757
vector<bool, _Allocator>::erase(const_iterator __position) {
2758
  iterator __r = __const_iterator_cast(__position);
2759
  std::copy(__position + 1, this->cend(), __r);
2760
  --__size_;
2761
  return __r;
2762
}
2763

2764
template <class _Allocator>
2765
_LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<bool, _Allocator>::iterator
2766
vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) {
2767
  iterator __r        = __const_iterator_cast(__first);
2768
  difference_type __d = __last - __first;
2769
  std::copy(__last, this->cend(), __r);
2770
  __size_ -= __d;
2771
  return __r;
2772
}
2773

2774
template <class _Allocator>
2775
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::swap(vector& __x)
2776
#if _LIBCPP_STD_VER >= 14
2777
    _NOEXCEPT
2778
#else
2779
    _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<allocator_type>)
2780
#endif
2781
{
2782
  std::swap(this->__begin_, __x.__begin_);
2783
  std::swap(this->__size_, __x.__size_);
2784
  std::swap(this->__cap(), __x.__cap());
2785
  std::__swap_allocator(
2786
      this->__alloc(), __x.__alloc(), integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
2787
}
2788

2789
template <class _Allocator>
2790
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::resize(size_type __sz, value_type __x) {
2791
  size_type __cs = size();
2792
  if (__cs < __sz) {
2793
    iterator __r;
2794
    size_type __c = capacity();
2795
    size_type __n = __sz - __cs;
2796
    if (__n <= __c && __cs <= __c - __n) {
2797
      __r = end();
2798
      __size_ += __n;
2799
    } else {
2800
      vector __v(get_allocator());
2801
      __v.reserve(__recommend(__size_ + __n));
2802
      __v.__size_ = __size_ + __n;
2803
      __r         = std::copy(cbegin(), cend(), __v.begin());
2804
      swap(__v);
2805
    }
2806
    std::fill_n(__r, __n, __x);
2807
  } else
2808
    __size_ = __sz;
2809
}
2810

2811
template <class _Allocator>
2812
_LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<bool, _Allocator>::flip() _NOEXCEPT {
2813
  // do middle whole words
2814
  size_type __n         = __size_;
2815
  __storage_pointer __p = __begin_;
2816
  for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
2817
    *__p = ~*__p;
2818
  // do last partial word
2819
  if (__n > 0) {
2820
    __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2821
    __storage_type __b = *__p & __m;
2822
    *__p &= ~__m;
2823
    *__p |= ~__b & __m;
2824
  }
2825
}
2826

2827
template <class _Allocator>
2828
_LIBCPP_CONSTEXPR_SINCE_CXX20 bool vector<bool, _Allocator>::__invariants() const {
2829
  if (this->__begin_ == nullptr) {
2830
    if (this->__size_ != 0 || this->__cap() != 0)
2831
      return false;
2832
  } else {
2833
    if (this->__cap() == 0)
2834
      return false;
2835
    if (this->__size_ > this->capacity())
2836
      return false;
2837
  }
2838
  return true;
2839
}
2840

2841
template <class _Allocator>
2842
_LIBCPP_CONSTEXPR_SINCE_CXX20 size_t vector<bool, _Allocator>::__hash_code() const _NOEXCEPT {
2843
  size_t __h = 0;
2844
  // do middle whole words
2845
  size_type __n         = __size_;
2846
  __storage_pointer __p = __begin_;
2847
  for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
2848
    __h ^= *__p;
2849
  // do last partial word
2850
  if (__n > 0) {
2851
    const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
2852
    __h ^= *__p & __m;
2853
  }
2854
  return __h;
2855
}
2856

2857
template <class _Allocator>
2858
struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
2859
    : public __unary_function<vector<bool, _Allocator>, size_t> {
2860
  _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_t
2861
  operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT {
2862
    return __vec.__hash_code();
2863
  }
2864
};
2865

2866
template <class _Tp, class _Allocator>
2867
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI bool
2868
operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2869
  const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
2870
  return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
2871
}
2872

2873
#if _LIBCPP_STD_VER <= 17
2874

2875
template <class _Tp, class _Allocator>
2876
inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2877
  return !(__x == __y);
2878
}
2879

2880
template <class _Tp, class _Allocator>
2881
inline _LIBCPP_HIDE_FROM_ABI bool operator<(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2882
  return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2883
}
2884

2885
template <class _Tp, class _Allocator>
2886
inline _LIBCPP_HIDE_FROM_ABI bool operator>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2887
  return __y < __x;
2888
}
2889

2890
template <class _Tp, class _Allocator>
2891
inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2892
  return !(__x < __y);
2893
}
2894

2895
template <class _Tp, class _Allocator>
2896
inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2897
  return !(__y < __x);
2898
}
2899

2900
#else // _LIBCPP_STD_VER <= 17
2901

2902
template <class _Tp, class _Allocator>
2903
_LIBCPP_HIDE_FROM_ABI constexpr __synth_three_way_result<_Tp>
2904
operator<=>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
2905
  return std::lexicographical_compare_three_way(
2906
      __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way);
2907
}
2908

2909
#endif // _LIBCPP_STD_VER <= 17
2910

2911
template <class _Tp, class _Allocator>
2912
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void
2913
swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) {
2914
  __x.swap(__y);
2915
}
2916

2917
#if _LIBCPP_STD_VER >= 20
2918
template <class _Tp, class _Allocator, class _Up>
2919
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
2920
erase(vector<_Tp, _Allocator>& __c, const _Up& __v) {
2921
  auto __old_size = __c.size();
2922
  __c.erase(std::remove(__c.begin(), __c.end(), __v), __c.end());
2923
  return __old_size - __c.size();
2924
}
2925

2926
template <class _Tp, class _Allocator, class _Predicate>
2927
_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type
2928
erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred) {
2929
  auto __old_size = __c.size();
2930
  __c.erase(std::remove_if(__c.begin(), __c.end(), __pred), __c.end());
2931
  return __old_size - __c.size();
2932
}
2933

2934
template <>
2935
inline constexpr bool __format::__enable_insertable<vector<char>> = true;
2936
#  ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
2937
template <>
2938
inline constexpr bool __format::__enable_insertable<vector<wchar_t>> = true;
2939
#  endif
2940

2941
#endif // _LIBCPP_STD_VER >= 20
2942

2943
#if _LIBCPP_STD_VER >= 23
2944
template <class _Tp, class _CharT>
2945
// Since is-vector-bool-reference is only used once it's inlined here.
2946
  requires same_as<typename _Tp::__container, vector<bool, typename _Tp::__container::allocator_type>>
2947
struct _LIBCPP_TEMPLATE_VIS formatter<_Tp, _CharT> {
2948
private:
2949
  formatter<bool, _CharT> __underlying_;
2950

2951
public:
2952
  template <class _ParseContext>
2953
  _LIBCPP_HIDE_FROM_ABI constexpr typename _ParseContext::iterator parse(_ParseContext& __ctx) {
2954
    return __underlying_.parse(__ctx);
2955
  }
2956

2957
  template <class _FormatContext>
2958
  _LIBCPP_HIDE_FROM_ABI typename _FormatContext::iterator format(const _Tp& __ref, _FormatContext& __ctx) const {
2959
    return __underlying_.format(__ref, __ctx);
2960
  }
2961
};
2962
#endif // _LIBCPP_STD_VER >= 23
2963

2964
_LIBCPP_END_NAMESPACE_STD
2965

2966
#if _LIBCPP_STD_VER >= 17
2967
_LIBCPP_BEGIN_NAMESPACE_STD
2968
namespace pmr {
2969
template <class _ValueT>
2970
using vector _LIBCPP_AVAILABILITY_PMR = std::vector<_ValueT, polymorphic_allocator<_ValueT>>;
2971
} // namespace pmr
2972
_LIBCPP_END_NAMESPACE_STD
2973
#endif
2974

2975
_LIBCPP_POP_MACROS
2976

2977
#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
2978
#  include <algorithm>
2979
#  include <atomic>
2980
#  include <concepts>
2981
#  include <cstdlib>
2982
#  include <iosfwd>
2983
#  if !defined(_LIBCPP_HAS_NO_LOCALIZATION)
2984
#    include <locale>
2985
#  endif
2986
#  include <tuple>
2987
#  include <type_traits>
2988
#  include <typeinfo>
2989
#  include <utility>
2990
#endif
2991

2992
#endif // _LIBCPP_VECTOR
2993