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