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