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

source code of flutter_engine/third_party/libcxx/include/vector