2 //===------------------------------ vector --------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_VECTOR
12 #define _LIBCPP_VECTOR
20 template <class T, class Allocator = allocator<T> >
25 typedef Allocator allocator_type;
26 typedef typename allocator_type::reference reference;
27 typedef typename allocator_type::const_reference const_reference;
28 typedef implementation-defined iterator;
29 typedef implementation-defined const_iterator;
30 typedef typename allocator_type::size_type size_type;
31 typedef typename allocator_type::difference_type difference_type;
32 typedef typename allocator_type::pointer pointer;
33 typedef typename allocator_type::const_pointer const_pointer;
34 typedef std::reverse_iterator<iterator> reverse_iterator;
35 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
38 noexcept(is_nothrow_default_constructible<allocator_type>::value);
39 explicit vector(const allocator_type&);
40 explicit vector(size_type n);
41 explicit vector(size_type n, const allocator_type&); // C++14
42 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
43 template <class InputIterator>
44 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
45 vector(const vector& x);
47 noexcept(is_nothrow_move_constructible<allocator_type>::value);
48 vector(initializer_list<value_type> il);
49 vector(initializer_list<value_type> il, const allocator_type& a);
51 vector& operator=(const vector& x);
52 vector& operator=(vector&& x)
54 allocator_type::propagate_on_container_move_assignment::value ||
55 allocator_type::is_always_equal::value); // C++17
56 vector& operator=(initializer_list<value_type> il);
57 template <class InputIterator>
58 void assign(InputIterator first, InputIterator last);
59 void assign(size_type n, const value_type& u);
60 void assign(initializer_list<value_type> il);
62 allocator_type get_allocator() const noexcept;
64 iterator begin() noexcept;
65 const_iterator begin() const noexcept;
66 iterator end() noexcept;
67 const_iterator end() const noexcept;
69 reverse_iterator rbegin() noexcept;
70 const_reverse_iterator rbegin() const noexcept;
71 reverse_iterator rend() noexcept;
72 const_reverse_iterator rend() const noexcept;
74 const_iterator cbegin() const noexcept;
75 const_iterator cend() const noexcept;
76 const_reverse_iterator crbegin() const noexcept;
77 const_reverse_iterator crend() const noexcept;
79 size_type size() const noexcept;
80 size_type max_size() const noexcept;
81 size_type capacity() const noexcept;
82 bool empty() const noexcept;
83 void reserve(size_type n);
84 void shrink_to_fit() noexcept;
86 reference operator[](size_type n);
87 const_reference operator[](size_type n) const;
88 reference at(size_type n);
89 const_reference at(size_type n) const;
92 const_reference front() const;
94 const_reference back() const;
96 value_type* data() noexcept;
97 const value_type* data() const noexcept;
99 void push_back(const value_type& x);
100 void push_back(value_type&& x);
101 template <class... Args>
102 reference emplace_back(Args&&... args); // reference in C++17
105 template <class... Args> iterator emplace(const_iterator position, Args&&... args);
106 iterator insert(const_iterator position, const value_type& x);
107 iterator insert(const_iterator position, value_type&& x);
108 iterator insert(const_iterator position, size_type n, const value_type& x);
109 template <class InputIterator>
110 iterator insert(const_iterator position, InputIterator first, InputIterator last);
111 iterator insert(const_iterator position, initializer_list<value_type> il);
113 iterator erase(const_iterator position);
114 iterator erase(const_iterator first, const_iterator last);
116 void clear() noexcept;
118 void resize(size_type sz);
119 void resize(size_type sz, const value_type& c);
122 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
123 allocator_traits<allocator_type>::is_always_equal::value); // C++17
125 bool __invariants() const;
128 template <class Allocator = allocator<T> >
129 class vector<bool, Allocator>
132 typedef bool value_type;
133 typedef Allocator allocator_type;
134 typedef implementation-defined iterator;
135 typedef implementation-defined const_iterator;
136 typedef typename allocator_type::size_type size_type;
137 typedef typename allocator_type::difference_type difference_type;
138 typedef iterator pointer;
139 typedef const_iterator const_pointer;
140 typedef std::reverse_iterator<iterator> reverse_iterator;
141 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
146 reference(const reference&) noexcept;
147 operator bool() const noexcept;
148 reference& operator=(const bool x) noexcept;
149 reference& operator=(const reference& x) noexcept;
150 iterator operator&() const noexcept;
151 void flip() noexcept;
154 class const_reference
157 const_reference(const reference&) noexcept;
158 operator bool() const noexcept;
159 const_iterator operator&() const noexcept;
163 noexcept(is_nothrow_default_constructible<allocator_type>::value);
164 explicit vector(const allocator_type&);
165 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
166 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
167 template <class InputIterator>
168 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
169 vector(const vector& x);
171 noexcept(is_nothrow_move_constructible<allocator_type>::value);
172 vector(initializer_list<value_type> il);
173 vector(initializer_list<value_type> il, const allocator_type& a);
175 vector& operator=(const vector& x);
176 vector& operator=(vector&& x)
178 allocator_type::propagate_on_container_move_assignment::value ||
179 allocator_type::is_always_equal::value); // C++17
180 vector& operator=(initializer_list<value_type> il);
181 template <class InputIterator>
182 void assign(InputIterator first, InputIterator last);
183 void assign(size_type n, const value_type& u);
184 void assign(initializer_list<value_type> il);
186 allocator_type get_allocator() const noexcept;
188 iterator begin() noexcept;
189 const_iterator begin() const noexcept;
190 iterator end() noexcept;
191 const_iterator end() const noexcept;
193 reverse_iterator rbegin() noexcept;
194 const_reverse_iterator rbegin() const noexcept;
195 reverse_iterator rend() noexcept;
196 const_reverse_iterator rend() const noexcept;
198 const_iterator cbegin() const noexcept;
199 const_iterator cend() const noexcept;
200 const_reverse_iterator crbegin() const noexcept;
201 const_reverse_iterator crend() const noexcept;
203 size_type size() const noexcept;
204 size_type max_size() const noexcept;
205 size_type capacity() const noexcept;
206 bool empty() const noexcept;
207 void reserve(size_type n);
208 void shrink_to_fit() noexcept;
210 reference operator[](size_type n);
211 const_reference operator[](size_type n) const;
212 reference at(size_type n);
213 const_reference at(size_type n) const;
216 const_reference front() const;
218 const_reference back() const;
220 void push_back(const value_type& x);
221 template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17
224 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
225 iterator insert(const_iterator position, const value_type& x);
226 iterator insert(const_iterator position, size_type n, const value_type& x);
227 template <class InputIterator>
228 iterator insert(const_iterator position, InputIterator first, InputIterator last);
229 iterator insert(const_iterator position, initializer_list<value_type> il);
231 iterator erase(const_iterator position);
232 iterator erase(const_iterator first, const_iterator last);
234 void clear() noexcept;
236 void resize(size_type sz);
237 void resize(size_type sz, value_type x);
240 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
241 allocator_traits<allocator_type>::is_always_equal::value); // C++17
242 void flip() noexcept;
244 bool __invariants() const;
247 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
248 vector(InputIterator, InputIterator, Allocator = Allocator())
249 -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>;
251 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
253 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
254 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
255 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
256 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
257 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
258 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
260 template <class T, class Allocator>
261 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
262 noexcept(noexcept(x.swap(y)));
264 template <class T, class Allocator, class U>
265 void erase(vector<T, Allocator>& c, const U& value); // C++20
266 template <class T, class Allocator, class Predicate>
267 void erase_if(vector<T, Allocator>& c, Predicate pred); // C++20
274 #include <iosfwd> // for forward declaration of vector
275 #include <__bit_reference>
276 #include <type_traits>
279 #include <initializer_list>
285 #include <__split_buffer>
286 #include <__functional_base>
290 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
291 #pragma GCC system_header
295 #include <__undef_macros>
298 _LIBCPP_BEGIN_NAMESPACE_STD
301 class __vector_base_common
304 _LIBCPP_INLINE_VISIBILITY __vector_base_common() {}
305 _LIBCPP_NORETURN void __throw_length_error() const;
306 _LIBCPP_NORETURN void __throw_out_of_range() const;
311 __vector_base_common<__b>::__throw_length_error() const
313 _VSTD::__throw_length_error("vector");
318 __vector_base_common<__b>::__throw_out_of_range() const
320 _VSTD::__throw_out_of_range("vector");
323 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>)
325 template <class _Tp, class _Allocator>
327 : protected __vector_base_common<true>
330 typedef _Allocator allocator_type;
331 typedef allocator_traits<allocator_type> __alloc_traits;
332 typedef typename __alloc_traits::size_type size_type;
334 typedef _Tp value_type;
335 typedef value_type& reference;
336 typedef const value_type& const_reference;
337 typedef typename __alloc_traits::difference_type difference_type;
338 typedef typename __alloc_traits::pointer pointer;
339 typedef typename __alloc_traits::const_pointer const_pointer;
340 typedef pointer iterator;
341 typedef const_pointer const_iterator;
345 __compressed_pair<pointer, allocator_type> __end_cap_;
347 _LIBCPP_INLINE_VISIBILITY
348 allocator_type& __alloc() _NOEXCEPT
349 {return __end_cap_.second();}
350 _LIBCPP_INLINE_VISIBILITY
351 const allocator_type& __alloc() const _NOEXCEPT
352 {return __end_cap_.second();}
353 _LIBCPP_INLINE_VISIBILITY
354 pointer& __end_cap() _NOEXCEPT
355 {return __end_cap_.first();}
356 _LIBCPP_INLINE_VISIBILITY
357 const pointer& __end_cap() const _NOEXCEPT
358 {return __end_cap_.first();}
360 _LIBCPP_INLINE_VISIBILITY
362 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
363 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
364 #ifndef _LIBCPP_CXX03_LANG
365 _LIBCPP_INLINE_VISIBILITY __vector_base(allocator_type&& __a) _NOEXCEPT;
369 _LIBCPP_INLINE_VISIBILITY
370 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
371 _LIBCPP_INLINE_VISIBILITY
372 size_type capacity() const _NOEXCEPT
373 {return static_cast<size_type>(__end_cap() - __begin_);}
375 _LIBCPP_INLINE_VISIBILITY
376 void __destruct_at_end(pointer __new_last) _NOEXCEPT;
378 _LIBCPP_INLINE_VISIBILITY
379 void __copy_assign_alloc(const __vector_base& __c)
380 {__copy_assign_alloc(__c, integral_constant<bool,
381 __alloc_traits::propagate_on_container_copy_assignment::value>());}
383 _LIBCPP_INLINE_VISIBILITY
384 void __move_assign_alloc(__vector_base& __c)
386 !__alloc_traits::propagate_on_container_move_assignment::value ||
387 is_nothrow_move_assignable<allocator_type>::value)
388 {__move_assign_alloc(__c, integral_constant<bool,
389 __alloc_traits::propagate_on_container_move_assignment::value>());}
391 _LIBCPP_INLINE_VISIBILITY
392 void __copy_assign_alloc(const __vector_base& __c, true_type)
394 if (__alloc() != __c.__alloc())
397 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
398 __begin_ = __end_ = __end_cap() = nullptr;
400 __alloc() = __c.__alloc();
403 _LIBCPP_INLINE_VISIBILITY
404 void __copy_assign_alloc(const __vector_base&, false_type)
407 _LIBCPP_INLINE_VISIBILITY
408 void __move_assign_alloc(__vector_base& __c, true_type)
409 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
411 __alloc() = _VSTD::move(__c.__alloc());
414 _LIBCPP_INLINE_VISIBILITY
415 void __move_assign_alloc(__vector_base&, false_type)
420 template <class _Tp, class _Allocator>
421 inline _LIBCPP_INLINE_VISIBILITY
423 __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
425 pointer __soon_to_be_end = __end_;
426 while (__new_last != __soon_to_be_end)
427 __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__soon_to_be_end));
431 template <class _Tp, class _Allocator>
432 inline _LIBCPP_INLINE_VISIBILITY
433 __vector_base<_Tp, _Allocator>::__vector_base()
434 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
441 template <class _Tp, class _Allocator>
442 inline _LIBCPP_INLINE_VISIBILITY
443 __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
446 __end_cap_(nullptr, __a)
450 #ifndef _LIBCPP_CXX03_LANG
451 template <class _Tp, class _Allocator>
452 inline _LIBCPP_INLINE_VISIBILITY
453 __vector_base<_Tp, _Allocator>::__vector_base(allocator_type&& __a) _NOEXCEPT
456 __end_cap_(nullptr, std::move(__a)) {}
459 template <class _Tp, class _Allocator>
460 __vector_base<_Tp, _Allocator>::~__vector_base()
462 if (__begin_ != nullptr)
465 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
469 template <class _Tp, class _Allocator /* = allocator<_Tp> */>
470 class _LIBCPP_TEMPLATE_VIS vector
471 : private __vector_base<_Tp, _Allocator>
474 typedef __vector_base<_Tp, _Allocator> __base;
475 typedef allocator<_Tp> __default_allocator_type;
477 typedef vector __self;
478 typedef _Tp value_type;
479 typedef _Allocator allocator_type;
480 typedef typename __base::__alloc_traits __alloc_traits;
481 typedef typename __base::reference reference;
482 typedef typename __base::const_reference const_reference;
483 typedef typename __base::size_type size_type;
484 typedef typename __base::difference_type difference_type;
485 typedef typename __base::pointer pointer;
486 typedef typename __base::const_pointer const_pointer;
487 typedef __wrap_iter<pointer> iterator;
488 typedef __wrap_iter<const_pointer> const_iterator;
489 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
490 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
492 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
493 "Allocator::value_type must be same type as value_type");
495 _LIBCPP_INLINE_VISIBILITY
496 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
498 #if _LIBCPP_DEBUG_LEVEL >= 2
499 __get_db()->__insert_c(this);
502 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
503 #if _LIBCPP_STD_VER <= 14
504 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
510 #if _LIBCPP_DEBUG_LEVEL >= 2
511 __get_db()->__insert_c(this);
514 explicit vector(size_type __n);
515 #if _LIBCPP_STD_VER > 11
516 explicit vector(size_type __n, const allocator_type& __a);
518 vector(size_type __n, const value_type& __x);
519 vector(size_type __n, const value_type& __x, const allocator_type& __a);
520 template <class _InputIterator>
521 vector(_InputIterator __first,
522 typename enable_if<__is_input_iterator <_InputIterator>::value &&
523 !__is_forward_iterator<_InputIterator>::value &&
526 typename iterator_traits<_InputIterator>::reference>::value,
527 _InputIterator>::type __last);
528 template <class _InputIterator>
529 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
530 typename enable_if<__is_input_iterator <_InputIterator>::value &&
531 !__is_forward_iterator<_InputIterator>::value &&
534 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
535 template <class _ForwardIterator>
536 vector(_ForwardIterator __first,
537 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
540 typename iterator_traits<_ForwardIterator>::reference>::value,
541 _ForwardIterator>::type __last);
542 template <class _ForwardIterator>
543 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
544 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
547 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
549 _LIBCPP_INLINE_VISIBILITY
553 #if _LIBCPP_DEBUG_LEVEL >= 2
554 __get_db()->__erase_c(this);
558 vector(const vector& __x);
559 vector(const vector& __x, const allocator_type& __a);
560 _LIBCPP_INLINE_VISIBILITY
561 vector& operator=(const vector& __x);
563 #ifndef _LIBCPP_CXX03_LANG
564 _LIBCPP_INLINE_VISIBILITY
565 vector(initializer_list<value_type> __il);
567 _LIBCPP_INLINE_VISIBILITY
568 vector(initializer_list<value_type> __il, const allocator_type& __a);
570 _LIBCPP_INLINE_VISIBILITY
572 #if _LIBCPP_STD_VER > 14
575 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
578 _LIBCPP_INLINE_VISIBILITY
579 vector(vector&& __x, const allocator_type& __a);
580 _LIBCPP_INLINE_VISIBILITY
581 vector& operator=(vector&& __x)
582 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
584 _LIBCPP_INLINE_VISIBILITY
585 vector& operator=(initializer_list<value_type> __il)
586 {assign(__il.begin(), __il.end()); return *this;}
588 #endif // !_LIBCPP_CXX03_LANG
590 template <class _InputIterator>
593 __is_input_iterator <_InputIterator>::value &&
594 !__is_forward_iterator<_InputIterator>::value &&
597 typename iterator_traits<_InputIterator>::reference>::value,
600 assign(_InputIterator __first, _InputIterator __last);
601 template <class _ForwardIterator>
604 __is_forward_iterator<_ForwardIterator>::value &&
607 typename iterator_traits<_ForwardIterator>::reference>::value,
610 assign(_ForwardIterator __first, _ForwardIterator __last);
612 void assign(size_type __n, const_reference __u);
614 #ifndef _LIBCPP_CXX03_LANG
615 _LIBCPP_INLINE_VISIBILITY
616 void assign(initializer_list<value_type> __il)
617 {assign(__il.begin(), __il.end());}
620 _LIBCPP_INLINE_VISIBILITY
621 allocator_type get_allocator() const _NOEXCEPT
622 {return this->__alloc();}
624 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
625 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
626 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
627 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
629 _LIBCPP_INLINE_VISIBILITY
630 reverse_iterator rbegin() _NOEXCEPT
631 {return reverse_iterator(end());}
632 _LIBCPP_INLINE_VISIBILITY
633 const_reverse_iterator rbegin() const _NOEXCEPT
634 {return const_reverse_iterator(end());}
635 _LIBCPP_INLINE_VISIBILITY
636 reverse_iterator rend() _NOEXCEPT
637 {return reverse_iterator(begin());}
638 _LIBCPP_INLINE_VISIBILITY
639 const_reverse_iterator rend() const _NOEXCEPT
640 {return const_reverse_iterator(begin());}
642 _LIBCPP_INLINE_VISIBILITY
643 const_iterator cbegin() const _NOEXCEPT
645 _LIBCPP_INLINE_VISIBILITY
646 const_iterator cend() const _NOEXCEPT
648 _LIBCPP_INLINE_VISIBILITY
649 const_reverse_iterator crbegin() const _NOEXCEPT
651 _LIBCPP_INLINE_VISIBILITY
652 const_reverse_iterator crend() const _NOEXCEPT
655 _LIBCPP_INLINE_VISIBILITY
656 size_type size() const _NOEXCEPT
657 {return static_cast<size_type>(this->__end_ - this->__begin_);}
658 _LIBCPP_INLINE_VISIBILITY
659 size_type capacity() const _NOEXCEPT
660 {return __base::capacity();}
661 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
662 bool empty() const _NOEXCEPT
663 {return this->__begin_ == this->__end_;}
664 size_type max_size() const _NOEXCEPT;
665 void reserve(size_type __n);
666 void shrink_to_fit() _NOEXCEPT;
668 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n);
669 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const;
670 reference at(size_type __n);
671 const_reference at(size_type __n) const;
673 _LIBCPP_INLINE_VISIBILITY reference front()
675 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
676 return *this->__begin_;
678 _LIBCPP_INLINE_VISIBILITY const_reference front() const
680 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
681 return *this->__begin_;
683 _LIBCPP_INLINE_VISIBILITY reference back()
685 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
686 return *(this->__end_ - 1);
688 _LIBCPP_INLINE_VISIBILITY const_reference back() const
690 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
691 return *(this->__end_ - 1);
694 _LIBCPP_INLINE_VISIBILITY
695 value_type* data() _NOEXCEPT
696 {return _VSTD::__to_raw_pointer(this->__begin_);}
697 _LIBCPP_INLINE_VISIBILITY
698 const value_type* data() const _NOEXCEPT
699 {return _VSTD::__to_raw_pointer(this->__begin_);}
701 #ifdef _LIBCPP_CXX03_LANG
702 _LIBCPP_INLINE_VISIBILITY
703 void __emplace_back(const value_type& __x) { push_back(__x); }
705 template <class _Arg>
706 _LIBCPP_INLINE_VISIBILITY
707 void __emplace_back(_Arg&& __arg) {
708 emplace_back(_VSTD::forward<_Arg>(__arg));
712 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
714 #ifndef _LIBCPP_CXX03_LANG
715 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
717 template <class... _Args>
718 _LIBCPP_INLINE_VISIBILITY
719 #if _LIBCPP_STD_VER > 14
720 reference emplace_back(_Args&&... __args);
722 void emplace_back(_Args&&... __args);
724 #endif // !_LIBCPP_CXX03_LANG
726 _LIBCPP_INLINE_VISIBILITY
729 iterator insert(const_iterator __position, const_reference __x);
731 #ifndef _LIBCPP_CXX03_LANG
732 iterator insert(const_iterator __position, value_type&& __x);
733 template <class... _Args>
734 iterator emplace(const_iterator __position, _Args&&... __args);
735 #endif // !_LIBCPP_CXX03_LANG
737 iterator insert(const_iterator __position, size_type __n, const_reference __x);
738 template <class _InputIterator>
741 __is_input_iterator <_InputIterator>::value &&
742 !__is_forward_iterator<_InputIterator>::value &&
745 typename iterator_traits<_InputIterator>::reference>::value,
748 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
749 template <class _ForwardIterator>
752 __is_forward_iterator<_ForwardIterator>::value &&
755 typename iterator_traits<_ForwardIterator>::reference>::value,
758 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
760 #ifndef _LIBCPP_CXX03_LANG
761 _LIBCPP_INLINE_VISIBILITY
762 iterator insert(const_iterator __position, initializer_list<value_type> __il)
763 {return insert(__position, __il.begin(), __il.end());}
766 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
767 iterator erase(const_iterator __first, const_iterator __last);
769 _LIBCPP_INLINE_VISIBILITY
770 void clear() _NOEXCEPT
772 size_type __old_size = size();
774 __annotate_shrink(__old_size);
775 __invalidate_all_iterators();
778 void resize(size_type __sz);
779 void resize(size_type __sz, const_reference __x);
782 #if _LIBCPP_STD_VER >= 14
785 _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value ||
786 __is_nothrow_swappable<allocator_type>::value);
789 bool __invariants() const;
791 #if _LIBCPP_DEBUG_LEVEL >= 2
793 bool __dereferenceable(const const_iterator* __i) const;
794 bool __decrementable(const const_iterator* __i) const;
795 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
796 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
798 #endif // _LIBCPP_DEBUG_LEVEL >= 2
801 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
802 _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
803 void __vallocate(size_type __n);
804 void __vdeallocate() _NOEXCEPT;
805 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
806 void __construct_at_end(size_type __n);
807 _LIBCPP_INLINE_VISIBILITY
808 void __construct_at_end(size_type __n, const_reference __x);
809 template <class _ForwardIterator>
812 __is_forward_iterator<_ForwardIterator>::value,
815 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
816 void __append(size_type __n);
817 void __append(size_type __n, const_reference __x);
818 _LIBCPP_INLINE_VISIBILITY
819 iterator __make_iter(pointer __p) _NOEXCEPT;
820 _LIBCPP_INLINE_VISIBILITY
821 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
822 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
823 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
824 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
825 void __move_assign(vector& __c, true_type)
826 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
827 void __move_assign(vector& __c, false_type)
828 _NOEXCEPT_(__alloc_traits::is_always_equal::value);
829 _LIBCPP_INLINE_VISIBILITY
830 void __destruct_at_end(pointer __new_last) _NOEXCEPT
832 __invalidate_iterators_past(__new_last);
833 size_type __old_size = size();
834 __base::__destruct_at_end(__new_last);
835 __annotate_shrink(__old_size);
838 #ifndef _LIBCPP_CXX03_LANG
839 template <class _Up> void __push_back_slow_path(_Up&& __x);
841 template <class... _Args>
842 void __emplace_back_slow_path(_Args&&... __args);
844 template <class _Up> void __push_back_slow_path(_Up& __x);
847 // The following functions are no-ops outside of AddressSanitizer mode.
848 // We call annotatations only for the default Allocator because other allocators
849 // may not meet the AddressSanitizer alignment constraints.
850 // See the documentation for __sanitizer_annotate_contiguous_container for more details.
851 #ifndef _LIBCPP_HAS_NO_ASAN
852 void __annotate_contiguous_container(const void *__beg, const void *__end,
853 const void *__old_mid,
854 const void *__new_mid) const
857 if (__beg && is_same<allocator_type, __default_allocator_type>::value)
858 __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
861 _LIBCPP_INLINE_VISIBILITY
862 void __annotate_contiguous_container(const void*, const void*, const void*,
863 const void*) const {}
865 _LIBCPP_INLINE_VISIBILITY
866 void __annotate_new(size_type __current_size) const {
867 __annotate_contiguous_container(data(), data() + capacity(),
868 data() + capacity(), data() + __current_size);
871 _LIBCPP_INLINE_VISIBILITY
872 void __annotate_delete() const {
873 __annotate_contiguous_container(data(), data() + capacity(),
874 data() + size(), data() + capacity());
877 _LIBCPP_INLINE_VISIBILITY
878 void __annotate_increase(size_type __n) const
880 __annotate_contiguous_container(data(), data() + capacity(),
881 data() + size(), data() + size() + __n);
884 _LIBCPP_INLINE_VISIBILITY
885 void __annotate_shrink(size_type __old_size) const
887 __annotate_contiguous_container(data(), data() + capacity(),
888 data() + __old_size, data() + size());
890 #ifndef _LIBCPP_HAS_NO_ASAN
891 // The annotation for size increase should happen before the actual increase,
892 // but if an exception is thrown after that the annotation has to be undone.
893 struct __RAII_IncreaseAnnotator {
894 __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1)
895 : __commit(false), __v(__v), __old_size(__v.size() + __n) {
896 __v.__annotate_increase(__n);
898 void __done() { __commit = true; }
899 ~__RAII_IncreaseAnnotator() {
900 if (__commit) return;
901 __v.__annotate_shrink(__old_size);
905 size_type __old_size;
908 struct __RAII_IncreaseAnnotator {
909 _LIBCPP_INLINE_VISIBILITY
910 __RAII_IncreaseAnnotator(const vector &, size_type = 1) {}
911 _LIBCPP_INLINE_VISIBILITY void __done() {}
917 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
918 template<class _InputIterator,
919 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
920 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
922 vector(_InputIterator, _InputIterator)
923 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
925 template<class _InputIterator,
927 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
929 vector(_InputIterator, _InputIterator, _Alloc)
930 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
933 template <class _Tp, class _Allocator>
935 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
938 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
939 _VSTD::swap(this->__begin_, __v.__begin_);
940 _VSTD::swap(this->__end_, __v.__end_);
941 _VSTD::swap(this->__end_cap(), __v.__end_cap());
942 __v.__first_ = __v.__begin_;
943 __annotate_new(size());
944 __invalidate_all_iterators();
947 template <class _Tp, class _Allocator>
948 typename vector<_Tp, _Allocator>::pointer
949 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
952 pointer __r = __v.__begin_;
953 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
954 __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
955 _VSTD::swap(this->__begin_, __v.__begin_);
956 _VSTD::swap(this->__end_, __v.__end_);
957 _VSTD::swap(this->__end_cap(), __v.__end_cap());
958 __v.__first_ = __v.__begin_;
959 __annotate_new(size());
960 __invalidate_all_iterators();
964 // Allocate space for __n objects
965 // throws length_error if __n > max_size()
966 // throws (probably bad_alloc) if memory run out
967 // Precondition: __begin_ == __end_ == __end_cap() == 0
968 // Precondition: __n > 0
969 // Postcondition: capacity() == __n
970 // Postcondition: size() == 0
971 template <class _Tp, class _Allocator>
973 vector<_Tp, _Allocator>::__vallocate(size_type __n)
975 if (__n > max_size())
976 this->__throw_length_error();
977 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
978 this->__end_cap() = this->__begin_ + __n;
982 template <class _Tp, class _Allocator>
984 vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT
986 if (this->__begin_ != nullptr)
989 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
990 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
994 template <class _Tp, class _Allocator>
995 typename vector<_Tp, _Allocator>::size_type
996 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
998 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),
999 numeric_limits<difference_type>::max());
1002 // Precondition: __new_size > capacity()
1003 template <class _Tp, class _Allocator>
1004 inline _LIBCPP_INLINE_VISIBILITY
1005 typename vector<_Tp, _Allocator>::size_type
1006 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
1008 const size_type __ms = max_size();
1009 if (__new_size > __ms)
1010 this->__throw_length_error();
1011 const size_type __cap = capacity();
1012 if (__cap >= __ms / 2)
1014 return _VSTD::max<size_type>(2*__cap, __new_size);
1017 // Default constructs __n objects starting at __end_
1018 // throws if construction throws
1019 // Precondition: __n > 0
1020 // Precondition: size() + __n <= capacity()
1021 // Postcondition: size() == size() + __n
1022 template <class _Tp, class _Allocator>
1024 vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
1026 allocator_type& __a = this->__alloc();
1029 __RAII_IncreaseAnnotator __annotator(*this);
1030 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
1033 __annotator.__done();
1037 // Copy constructs __n objects starting at __end_ from __x
1038 // throws if construction throws
1039 // Precondition: __n > 0
1040 // Precondition: size() + __n <= capacity()
1041 // Postcondition: size() == old size() + __n
1042 // Postcondition: [i] == __x for all i in [size() - __n, __n)
1043 template <class _Tp, class _Allocator>
1046 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
1048 allocator_type& __a = this->__alloc();
1051 __RAII_IncreaseAnnotator __annotator(*this);
1052 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
1055 __annotator.__done();
1059 template <class _Tp, class _Allocator>
1060 template <class _ForwardIterator>
1063 __is_forward_iterator<_ForwardIterator>::value,
1066 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
1068 allocator_type& __a = this->__alloc();
1069 __RAII_IncreaseAnnotator __annotator(*this, __n);
1070 __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_);
1071 __annotator.__done();
1074 // Default constructs __n objects starting at __end_
1075 // throws if construction throws
1076 // Postcondition: size() == size() + __n
1077 // Exception safety: strong.
1078 template <class _Tp, class _Allocator>
1080 vector<_Tp, _Allocator>::__append(size_type __n)
1082 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1083 this->__construct_at_end(__n);
1086 allocator_type& __a = this->__alloc();
1087 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1088 __v.__construct_at_end(__n);
1089 __swap_out_circular_buffer(__v);
1093 // Default constructs __n objects starting at __end_
1094 // throws if construction throws
1095 // Postcondition: size() == size() + __n
1096 // Exception safety: strong.
1097 template <class _Tp, class _Allocator>
1099 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
1101 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1102 this->__construct_at_end(__n, __x);
1105 allocator_type& __a = this->__alloc();
1106 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1107 __v.__construct_at_end(__n, __x);
1108 __swap_out_circular_buffer(__v);
1112 template <class _Tp, class _Allocator>
1113 vector<_Tp, _Allocator>::vector(size_type __n)
1115 #if _LIBCPP_DEBUG_LEVEL >= 2
1116 __get_db()->__insert_c(this);
1121 __construct_at_end(__n);
1125 #if _LIBCPP_STD_VER > 11
1126 template <class _Tp, class _Allocator>
1127 vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
1130 #if _LIBCPP_DEBUG_LEVEL >= 2
1131 __get_db()->__insert_c(this);
1136 __construct_at_end(__n);
1141 template <class _Tp, class _Allocator>
1142 vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)
1144 #if _LIBCPP_DEBUG_LEVEL >= 2
1145 __get_db()->__insert_c(this);
1150 __construct_at_end(__n, __x);
1154 template <class _Tp, class _Allocator>
1155 vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
1158 #if _LIBCPP_DEBUG_LEVEL >= 2
1159 __get_db()->__insert_c(this);
1164 __construct_at_end(__n, __x);
1168 template <class _Tp, class _Allocator>
1169 template <class _InputIterator>
1170 vector<_Tp, _Allocator>::vector(_InputIterator __first,
1171 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1172 !__is_forward_iterator<_InputIterator>::value &&
1175 typename iterator_traits<_InputIterator>::reference>::value,
1176 _InputIterator>::type __last)
1178 #if _LIBCPP_DEBUG_LEVEL >= 2
1179 __get_db()->__insert_c(this);
1181 for (; __first != __last; ++__first)
1182 __emplace_back(*__first);
1185 template <class _Tp, class _Allocator>
1186 template <class _InputIterator>
1187 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1188 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1189 !__is_forward_iterator<_InputIterator>::value &&
1192 typename iterator_traits<_InputIterator>::reference>::value>::type*)
1195 #if _LIBCPP_DEBUG_LEVEL >= 2
1196 __get_db()->__insert_c(this);
1198 for (; __first != __last; ++__first)
1199 __emplace_back(*__first);
1202 template <class _Tp, class _Allocator>
1203 template <class _ForwardIterator>
1204 vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
1205 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1208 typename iterator_traits<_ForwardIterator>::reference>::value,
1209 _ForwardIterator>::type __last)
1211 #if _LIBCPP_DEBUG_LEVEL >= 2
1212 __get_db()->__insert_c(this);
1214 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1218 __construct_at_end(__first, __last, __n);
1222 template <class _Tp, class _Allocator>
1223 template <class _ForwardIterator>
1224 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
1225 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1228 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
1231 #if _LIBCPP_DEBUG_LEVEL >= 2
1232 __get_db()->__insert_c(this);
1234 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1238 __construct_at_end(__first, __last, __n);
1242 template <class _Tp, class _Allocator>
1243 vector<_Tp, _Allocator>::vector(const vector& __x)
1244 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1246 #if _LIBCPP_DEBUG_LEVEL >= 2
1247 __get_db()->__insert_c(this);
1249 size_type __n = __x.size();
1253 __construct_at_end(__x.__begin_, __x.__end_, __n);
1257 template <class _Tp, class _Allocator>
1258 vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1261 #if _LIBCPP_DEBUG_LEVEL >= 2
1262 __get_db()->__insert_c(this);
1264 size_type __n = __x.size();
1268 __construct_at_end(__x.__begin_, __x.__end_, __n);
1272 #ifndef _LIBCPP_CXX03_LANG
1274 template <class _Tp, class _Allocator>
1275 inline _LIBCPP_INLINE_VISIBILITY
1276 vector<_Tp, _Allocator>::vector(vector&& __x)
1277 #if _LIBCPP_STD_VER > 14
1280 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1282 : __base(_VSTD::move(__x.__alloc()))
1284 #if _LIBCPP_DEBUG_LEVEL >= 2
1285 __get_db()->__insert_c(this);
1286 __get_db()->swap(this, &__x);
1288 this->__begin_ = __x.__begin_;
1289 this->__end_ = __x.__end_;
1290 this->__end_cap() = __x.__end_cap();
1291 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1294 template <class _Tp, class _Allocator>
1295 inline _LIBCPP_INLINE_VISIBILITY
1296 vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1299 #if _LIBCPP_DEBUG_LEVEL >= 2
1300 __get_db()->__insert_c(this);
1302 if (__a == __x.__alloc())
1304 this->__begin_ = __x.__begin_;
1305 this->__end_ = __x.__end_;
1306 this->__end_cap() = __x.__end_cap();
1307 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1308 #if _LIBCPP_DEBUG_LEVEL >= 2
1309 __get_db()->swap(this, &__x);
1314 typedef move_iterator<iterator> _Ip;
1315 assign(_Ip(__x.begin()), _Ip(__x.end()));
1319 template <class _Tp, class _Allocator>
1320 inline _LIBCPP_INLINE_VISIBILITY
1321 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1323 #if _LIBCPP_DEBUG_LEVEL >= 2
1324 __get_db()->__insert_c(this);
1326 if (__il.size() > 0)
1328 __vallocate(__il.size());
1329 __construct_at_end(__il.begin(), __il.end(), __il.size());
1333 template <class _Tp, class _Allocator>
1334 inline _LIBCPP_INLINE_VISIBILITY
1335 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1338 #if _LIBCPP_DEBUG_LEVEL >= 2
1339 __get_db()->__insert_c(this);
1341 if (__il.size() > 0)
1343 __vallocate(__il.size());
1344 __construct_at_end(__il.begin(), __il.end(), __il.size());
1348 template <class _Tp, class _Allocator>
1349 inline _LIBCPP_INLINE_VISIBILITY
1350 vector<_Tp, _Allocator>&
1351 vector<_Tp, _Allocator>::operator=(vector&& __x)
1352 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
1354 __move_assign(__x, integral_constant<bool,
1355 __alloc_traits::propagate_on_container_move_assignment::value>());
1359 template <class _Tp, class _Allocator>
1361 vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1362 _NOEXCEPT_(__alloc_traits::is_always_equal::value)
1364 if (__base::__alloc() != __c.__alloc())
1366 typedef move_iterator<iterator> _Ip;
1367 assign(_Ip(__c.begin()), _Ip(__c.end()));
1370 __move_assign(__c, true_type());
1373 template <class _Tp, class _Allocator>
1375 vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1376 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1379 __base::__move_assign_alloc(__c); // this can throw
1380 this->__begin_ = __c.__begin_;
1381 this->__end_ = __c.__end_;
1382 this->__end_cap() = __c.__end_cap();
1383 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1384 #if _LIBCPP_DEBUG_LEVEL >= 2
1385 __get_db()->swap(this, &__c);
1389 #endif // !_LIBCPP_CXX03_LANG
1391 template <class _Tp, class _Allocator>
1392 inline _LIBCPP_INLINE_VISIBILITY
1393 vector<_Tp, _Allocator>&
1394 vector<_Tp, _Allocator>::operator=(const vector& __x)
1398 __base::__copy_assign_alloc(__x);
1399 assign(__x.__begin_, __x.__end_);
1404 template <class _Tp, class _Allocator>
1405 template <class _InputIterator>
1408 __is_input_iterator <_InputIterator>::value &&
1409 !__is_forward_iterator<_InputIterator>::value &&
1412 typename iterator_traits<_InputIterator>::reference>::value,
1415 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1418 for (; __first != __last; ++__first)
1419 __emplace_back(*__first);
1422 template <class _Tp, class _Allocator>
1423 template <class _ForwardIterator>
1426 __is_forward_iterator<_ForwardIterator>::value &&
1429 typename iterator_traits<_ForwardIterator>::reference>::value,
1432 vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1434 size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
1435 if (__new_size <= capacity())
1437 _ForwardIterator __mid = __last;
1438 bool __growing = false;
1439 if (__new_size > size())
1443 _VSTD::advance(__mid, size());
1445 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
1447 __construct_at_end(__mid, __last, __new_size - size());
1449 this->__destruct_at_end(__m);
1454 __vallocate(__recommend(__new_size));
1455 __construct_at_end(__first, __last, __new_size);
1457 __invalidate_all_iterators();
1460 template <class _Tp, class _Allocator>
1462 vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1464 if (__n <= capacity())
1466 size_type __s = size();
1467 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
1469 __construct_at_end(__n - __s, __u);
1471 this->__destruct_at_end(this->__begin_ + __n);
1476 __vallocate(__recommend(static_cast<size_type>(__n)));
1477 __construct_at_end(__n, __u);
1479 __invalidate_all_iterators();
1482 template <class _Tp, class _Allocator>
1483 inline _LIBCPP_INLINE_VISIBILITY
1484 typename vector<_Tp, _Allocator>::iterator
1485 vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
1487 #if _LIBCPP_DEBUG_LEVEL >= 2
1488 return iterator(this, __p);
1490 return iterator(__p);
1494 template <class _Tp, class _Allocator>
1495 inline _LIBCPP_INLINE_VISIBILITY
1496 typename vector<_Tp, _Allocator>::const_iterator
1497 vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
1499 #if _LIBCPP_DEBUG_LEVEL >= 2
1500 return const_iterator(this, __p);
1502 return const_iterator(__p);
1506 template <class _Tp, class _Allocator>
1507 inline _LIBCPP_INLINE_VISIBILITY
1508 typename vector<_Tp, _Allocator>::iterator
1509 vector<_Tp, _Allocator>::begin() _NOEXCEPT
1511 return __make_iter(this->__begin_);
1514 template <class _Tp, class _Allocator>
1515 inline _LIBCPP_INLINE_VISIBILITY
1516 typename vector<_Tp, _Allocator>::const_iterator
1517 vector<_Tp, _Allocator>::begin() const _NOEXCEPT
1519 return __make_iter(this->__begin_);
1522 template <class _Tp, class _Allocator>
1523 inline _LIBCPP_INLINE_VISIBILITY
1524 typename vector<_Tp, _Allocator>::iterator
1525 vector<_Tp, _Allocator>::end() _NOEXCEPT
1527 return __make_iter(this->__end_);
1530 template <class _Tp, class _Allocator>
1531 inline _LIBCPP_INLINE_VISIBILITY
1532 typename vector<_Tp, _Allocator>::const_iterator
1533 vector<_Tp, _Allocator>::end() const _NOEXCEPT
1535 return __make_iter(this->__end_);
1538 template <class _Tp, class _Allocator>
1539 inline _LIBCPP_INLINE_VISIBILITY
1540 typename vector<_Tp, _Allocator>::reference
1541 vector<_Tp, _Allocator>::operator[](size_type __n)
1543 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1544 return this->__begin_[__n];
1547 template <class _Tp, class _Allocator>
1548 inline _LIBCPP_INLINE_VISIBILITY
1549 typename vector<_Tp, _Allocator>::const_reference
1550 vector<_Tp, _Allocator>::operator[](size_type __n) const
1552 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1553 return this->__begin_[__n];
1556 template <class _Tp, class _Allocator>
1557 typename vector<_Tp, _Allocator>::reference
1558 vector<_Tp, _Allocator>::at(size_type __n)
1561 this->__throw_out_of_range();
1562 return this->__begin_[__n];
1565 template <class _Tp, class _Allocator>
1566 typename vector<_Tp, _Allocator>::const_reference
1567 vector<_Tp, _Allocator>::at(size_type __n) const
1570 this->__throw_out_of_range();
1571 return this->__begin_[__n];
1574 template <class _Tp, class _Allocator>
1576 vector<_Tp, _Allocator>::reserve(size_type __n)
1578 if (__n > capacity())
1580 allocator_type& __a = this->__alloc();
1581 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1582 __swap_out_circular_buffer(__v);
1586 template <class _Tp, class _Allocator>
1588 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1590 if (capacity() > size())
1592 #ifndef _LIBCPP_NO_EXCEPTIONS
1595 #endif // _LIBCPP_NO_EXCEPTIONS
1596 allocator_type& __a = this->__alloc();
1597 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1598 __swap_out_circular_buffer(__v);
1599 #ifndef _LIBCPP_NO_EXCEPTIONS
1604 #endif // _LIBCPP_NO_EXCEPTIONS
1608 template <class _Tp, class _Allocator>
1609 template <class _Up>
1611 #ifndef _LIBCPP_CXX03_LANG
1612 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1614 vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1617 allocator_type& __a = this->__alloc();
1618 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1619 // __v.push_back(_VSTD::forward<_Up>(__x));
1620 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
1622 __swap_out_circular_buffer(__v);
1625 template <class _Tp, class _Allocator>
1626 inline _LIBCPP_INLINE_VISIBILITY
1628 vector<_Tp, _Allocator>::push_back(const_reference __x)
1630 if (this->__end_ != this->__end_cap())
1632 __RAII_IncreaseAnnotator __annotator(*this);
1633 __alloc_traits::construct(this->__alloc(),
1634 _VSTD::__to_raw_pointer(this->__end_), __x);
1635 __annotator.__done();
1639 __push_back_slow_path(__x);
1642 #ifndef _LIBCPP_CXX03_LANG
1644 template <class _Tp, class _Allocator>
1645 inline _LIBCPP_INLINE_VISIBILITY
1647 vector<_Tp, _Allocator>::push_back(value_type&& __x)
1649 if (this->__end_ < this->__end_cap())
1651 __RAII_IncreaseAnnotator __annotator(*this);
1652 __alloc_traits::construct(this->__alloc(),
1653 _VSTD::__to_raw_pointer(this->__end_),
1655 __annotator.__done();
1659 __push_back_slow_path(_VSTD::move(__x));
1662 template <class _Tp, class _Allocator>
1663 template <class... _Args>
1665 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1667 allocator_type& __a = this->__alloc();
1668 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1669 // __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1670 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
1672 __swap_out_circular_buffer(__v);
1675 template <class _Tp, class _Allocator>
1676 template <class... _Args>
1678 #if _LIBCPP_STD_VER > 14
1679 typename vector<_Tp, _Allocator>::reference
1683 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1685 if (this->__end_ < this->__end_cap())
1687 __RAII_IncreaseAnnotator __annotator(*this);
1688 __alloc_traits::construct(this->__alloc(),
1689 _VSTD::__to_raw_pointer(this->__end_),
1690 _VSTD::forward<_Args>(__args)...);
1691 __annotator.__done();
1695 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
1696 #if _LIBCPP_STD_VER > 14
1697 return this->back();
1701 #endif // !_LIBCPP_CXX03_LANG
1703 template <class _Tp, class _Allocator>
1706 vector<_Tp, _Allocator>::pop_back()
1708 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1709 this->__destruct_at_end(this->__end_ - 1);
1712 template <class _Tp, class _Allocator>
1713 inline _LIBCPP_INLINE_VISIBILITY
1714 typename vector<_Tp, _Allocator>::iterator
1715 vector<_Tp, _Allocator>::erase(const_iterator __position)
1717 #if _LIBCPP_DEBUG_LEVEL >= 2
1718 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1719 "vector::erase(iterator) called with an iterator not"
1720 " referring to this vector");
1722 _LIBCPP_ASSERT(__position != end(),
1723 "vector::erase(iterator) called with a non-dereferenceable iterator");
1724 difference_type __ps = __position - cbegin();
1725 pointer __p = this->__begin_ + __ps;
1726 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1727 this->__invalidate_iterators_past(__p-1);
1728 iterator __r = __make_iter(__p);
1732 template <class _Tp, class _Allocator>
1733 typename vector<_Tp, _Allocator>::iterator
1734 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1736 #if _LIBCPP_DEBUG_LEVEL >= 2
1737 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1738 "vector::erase(iterator, iterator) called with an iterator not"
1739 " referring to this vector");
1740 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
1741 "vector::erase(iterator, iterator) called with an iterator not"
1742 " referring to this vector");
1744 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1745 pointer __p = this->__begin_ + (__first - begin());
1746 if (__first != __last) {
1747 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1748 this->__invalidate_iterators_past(__p - 1);
1750 iterator __r = __make_iter(__p);
1754 template <class _Tp, class _Allocator>
1756 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1758 pointer __old_last = this->__end_;
1759 difference_type __n = __old_last - __to;
1760 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1761 __alloc_traits::construct(this->__alloc(),
1762 _VSTD::__to_raw_pointer(this->__end_),
1764 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1767 template <class _Tp, class _Allocator>
1768 typename vector<_Tp, _Allocator>::iterator
1769 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1771 #if _LIBCPP_DEBUG_LEVEL >= 2
1772 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1773 "vector::insert(iterator, x) called with an iterator not"
1774 " referring to this vector");
1776 pointer __p = this->__begin_ + (__position - begin());
1777 if (this->__end_ < this->__end_cap())
1779 __RAII_IncreaseAnnotator __annotator(*this);
1780 if (__p == this->__end_)
1782 __alloc_traits::construct(this->__alloc(),
1783 _VSTD::__to_raw_pointer(this->__end_), __x);
1788 __move_range(__p, this->__end_, __p + 1);
1789 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1790 if (__p <= __xr && __xr < this->__end_)
1794 __annotator.__done();
1798 allocator_type& __a = this->__alloc();
1799 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1801 __p = __swap_out_circular_buffer(__v, __p);
1803 return __make_iter(__p);
1806 #ifndef _LIBCPP_CXX03_LANG
1808 template <class _Tp, class _Allocator>
1809 typename vector<_Tp, _Allocator>::iterator
1810 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1812 #if _LIBCPP_DEBUG_LEVEL >= 2
1813 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1814 "vector::insert(iterator, x) called with an iterator not"
1815 " referring to this vector");
1817 pointer __p = this->__begin_ + (__position - begin());
1818 if (this->__end_ < this->__end_cap())
1820 __RAII_IncreaseAnnotator __annotator(*this);
1821 if (__p == this->__end_)
1823 __alloc_traits::construct(this->__alloc(),
1824 _VSTD::__to_raw_pointer(this->__end_),
1830 __move_range(__p, this->__end_, __p + 1);
1831 *__p = _VSTD::move(__x);
1833 __annotator.__done();
1837 allocator_type& __a = this->__alloc();
1838 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1839 __v.push_back(_VSTD::move(__x));
1840 __p = __swap_out_circular_buffer(__v, __p);
1842 return __make_iter(__p);
1845 template <class _Tp, class _Allocator>
1846 template <class... _Args>
1847 typename vector<_Tp, _Allocator>::iterator
1848 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1850 #if _LIBCPP_DEBUG_LEVEL >= 2
1851 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1852 "vector::emplace(iterator, x) called with an iterator not"
1853 " referring to this vector");
1855 pointer __p = this->__begin_ + (__position - begin());
1856 if (this->__end_ < this->__end_cap())
1858 __RAII_IncreaseAnnotator __annotator(*this);
1859 if (__p == this->__end_)
1861 __alloc_traits::construct(this->__alloc(),
1862 _VSTD::__to_raw_pointer(this->__end_),
1863 _VSTD::forward<_Args>(__args)...);
1868 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
1869 __move_range(__p, this->__end_, __p + 1);
1870 *__p = _VSTD::move(__tmp.get());
1872 __annotator.__done();
1876 allocator_type& __a = this->__alloc();
1877 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1878 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1879 __p = __swap_out_circular_buffer(__v, __p);
1881 return __make_iter(__p);
1884 #endif // !_LIBCPP_CXX03_LANG
1886 template <class _Tp, class _Allocator>
1887 typename vector<_Tp, _Allocator>::iterator
1888 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1890 #if _LIBCPP_DEBUG_LEVEL >= 2
1891 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1892 "vector::insert(iterator, n, x) called with an iterator not"
1893 " referring to this vector");
1895 pointer __p = this->__begin_ + (__position - begin());
1898 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1900 size_type __old_n = __n;
1901 pointer __old_last = this->__end_;
1902 if (__n > static_cast<size_type>(this->__end_ - __p))
1904 size_type __cx = __n - (this->__end_ - __p);
1905 __construct_at_end(__cx, __x);
1910 __RAII_IncreaseAnnotator __annotator(*this, __n);
1911 __move_range(__p, __old_last, __p + __old_n);
1912 __annotator.__done();
1913 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1914 if (__p <= __xr && __xr < this->__end_)
1916 _VSTD::fill_n(__p, __n, *__xr);
1921 allocator_type& __a = this->__alloc();
1922 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1923 __v.__construct_at_end(__n, __x);
1924 __p = __swap_out_circular_buffer(__v, __p);
1927 return __make_iter(__p);
1930 template <class _Tp, class _Allocator>
1931 template <class _InputIterator>
1934 __is_input_iterator <_InputIterator>::value &&
1935 !__is_forward_iterator<_InputIterator>::value &&
1938 typename iterator_traits<_InputIterator>::reference>::value,
1939 typename vector<_Tp, _Allocator>::iterator
1941 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1943 #if _LIBCPP_DEBUG_LEVEL >= 2
1944 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1945 "vector::insert(iterator, range) called with an iterator not"
1946 " referring to this vector");
1948 difference_type __off = __position - begin();
1949 pointer __p = this->__begin_ + __off;
1950 allocator_type& __a = this->__alloc();
1951 pointer __old_last = this->__end_;
1952 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1954 __RAII_IncreaseAnnotator __annotator(*this);
1955 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
1958 __annotator.__done();
1960 __split_buffer<value_type, allocator_type&> __v(__a);
1961 if (__first != __last)
1963 #ifndef _LIBCPP_NO_EXCEPTIONS
1966 #endif // _LIBCPP_NO_EXCEPTIONS
1967 __v.__construct_at_end(__first, __last);
1968 difference_type __old_size = __old_last - this->__begin_;
1969 difference_type __old_p = __p - this->__begin_;
1970 reserve(__recommend(size() + __v.size()));
1971 __p = this->__begin_ + __old_p;
1972 __old_last = this->__begin_ + __old_size;
1973 #ifndef _LIBCPP_NO_EXCEPTIONS
1977 erase(__make_iter(__old_last), end());
1980 #endif // _LIBCPP_NO_EXCEPTIONS
1982 __p = _VSTD::rotate(__p, __old_last, this->__end_);
1983 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1984 make_move_iterator(__v.end()));
1985 return begin() + __off;
1988 template <class _Tp, class _Allocator>
1989 template <class _ForwardIterator>
1992 __is_forward_iterator<_ForwardIterator>::value &&
1995 typename iterator_traits<_ForwardIterator>::reference>::value,
1996 typename vector<_Tp, _Allocator>::iterator
1998 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
2000 #if _LIBCPP_DEBUG_LEVEL >= 2
2001 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
2002 "vector::insert(iterator, range) called with an iterator not"
2003 " referring to this vector");
2005 pointer __p = this->__begin_ + (__position - begin());
2006 difference_type __n = _VSTD::distance(__first, __last);
2009 if (__n <= this->__end_cap() - this->__end_)
2011 size_type __old_n = __n;
2012 pointer __old_last = this->__end_;
2013 _ForwardIterator __m = __last;
2014 difference_type __dx = this->__end_ - __p;
2018 difference_type __diff = this->__end_ - __p;
2019 _VSTD::advance(__m, __diff);
2020 __construct_at_end(__m, __last, __n - __diff);
2025 __RAII_IncreaseAnnotator __annotator(*this, __n);
2026 __move_range(__p, __old_last, __p + __old_n);
2027 __annotator.__done();
2028 _VSTD::copy(__first, __m, __p);
2033 allocator_type& __a = this->__alloc();
2034 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
2035 __v.__construct_at_end(__first, __last);
2036 __p = __swap_out_circular_buffer(__v, __p);
2039 return __make_iter(__p);
2042 template <class _Tp, class _Allocator>
2044 vector<_Tp, _Allocator>::resize(size_type __sz)
2046 size_type __cs = size();
2048 this->__append(__sz - __cs);
2049 else if (__cs > __sz)
2050 this->__destruct_at_end(this->__begin_ + __sz);
2053 template <class _Tp, class _Allocator>
2055 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
2057 size_type __cs = size();
2059 this->__append(__sz - __cs, __x);
2060 else if (__cs > __sz)
2061 this->__destruct_at_end(this->__begin_ + __sz);
2064 template <class _Tp, class _Allocator>
2066 vector<_Tp, _Allocator>::swap(vector& __x)
2067 #if _LIBCPP_STD_VER >= 14
2070 _NOEXCEPT_DEBUG_(!__alloc_traits::propagate_on_container_swap::value ||
2071 __is_nothrow_swappable<allocator_type>::value)
2074 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
2075 this->__alloc() == __x.__alloc(),
2076 "vector::swap: Either propagate_on_container_swap must be true"
2077 " or the allocators must compare equal");
2078 _VSTD::swap(this->__begin_, __x.__begin_);
2079 _VSTD::swap(this->__end_, __x.__end_);
2080 _VSTD::swap(this->__end_cap(), __x.__end_cap());
2081 __swap_allocator(this->__alloc(), __x.__alloc(),
2082 integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
2083 #if _LIBCPP_DEBUG_LEVEL >= 2
2084 __get_db()->swap(this, &__x);
2085 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2088 template <class _Tp, class _Allocator>
2090 vector<_Tp, _Allocator>::__invariants() const
2092 if (this->__begin_ == nullptr)
2094 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
2099 if (this->__begin_ > this->__end_)
2101 if (this->__begin_ == this->__end_cap())
2103 if (this->__end_ > this->__end_cap())
2109 #if _LIBCPP_DEBUG_LEVEL >= 2
2111 template <class _Tp, class _Allocator>
2113 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
2115 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
2118 template <class _Tp, class _Allocator>
2120 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
2122 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
2125 template <class _Tp, class _Allocator>
2127 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2129 const_pointer __p = __i->base() + __n;
2130 return this->__begin_ <= __p && __p <= this->__end_;
2133 template <class _Tp, class _Allocator>
2135 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2137 const_pointer __p = __i->base() + __n;
2138 return this->__begin_ <= __p && __p < this->__end_;
2141 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2143 template <class _Tp, class _Allocator>
2144 inline _LIBCPP_INLINE_VISIBILITY
2146 vector<_Tp, _Allocator>::__invalidate_all_iterators()
2148 #if _LIBCPP_DEBUG_LEVEL >= 2
2149 __get_db()->__invalidate_all(this);
2150 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2154 template <class _Tp, class _Allocator>
2155 inline _LIBCPP_INLINE_VISIBILITY
2157 vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) {
2158 #if _LIBCPP_DEBUG_LEVEL >= 2
2159 __c_node* __c = __get_db()->__find_c_and_lock(this);
2160 for (__i_node** __p = __c->end_; __p != __c->beg_; ) {
2162 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
2163 if (__i->base() > __new_last) {
2164 (*__p)->__c_ = nullptr;
2165 if (--__c->end_ != __p)
2166 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
2169 __get_db()->unlock();
2177 template <class _Allocator> class vector<bool, _Allocator>;
2179 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2181 template <class _Allocator>
2182 struct __has_storage_type<vector<bool, _Allocator> >
2184 static const bool value = true;
2187 template <class _Allocator>
2188 class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
2189 : private __vector_base_common<true>
2192 typedef vector __self;
2193 typedef bool value_type;
2194 typedef _Allocator allocator_type;
2195 typedef allocator_traits<allocator_type> __alloc_traits;
2196 typedef typename __alloc_traits::size_type size_type;
2197 typedef typename __alloc_traits::difference_type difference_type;
2198 typedef size_type __storage_type;
2199 typedef __bit_iterator<vector, false> pointer;
2200 typedef __bit_iterator<vector, true> const_pointer;
2201 typedef pointer iterator;
2202 typedef const_pointer const_iterator;
2203 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2204 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
2207 typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
2208 typedef allocator_traits<__storage_allocator> __storage_traits;
2209 typedef typename __storage_traits::pointer __storage_pointer;
2210 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2212 __storage_pointer __begin_;
2214 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2216 typedef __bit_reference<vector> reference;
2217 typedef __bit_const_reference<vector> const_reference;
2219 _LIBCPP_INLINE_VISIBILITY
2220 size_type& __cap() _NOEXCEPT
2221 {return __cap_alloc_.first();}
2222 _LIBCPP_INLINE_VISIBILITY
2223 const size_type& __cap() const _NOEXCEPT
2224 {return __cap_alloc_.first();}
2225 _LIBCPP_INLINE_VISIBILITY
2226 __storage_allocator& __alloc() _NOEXCEPT
2227 {return __cap_alloc_.second();}
2228 _LIBCPP_INLINE_VISIBILITY
2229 const __storage_allocator& __alloc() const _NOEXCEPT
2230 {return __cap_alloc_.second();}
2232 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2234 _LIBCPP_INLINE_VISIBILITY
2235 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2236 {return __n * __bits_per_word;}
2237 _LIBCPP_INLINE_VISIBILITY
2238 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2239 {return (__n - 1) / __bits_per_word + 1;}
2242 _LIBCPP_INLINE_VISIBILITY
2243 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2245 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
2246 #if _LIBCPP_STD_VER <= 14
2247 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
2252 explicit vector(size_type __n);
2253 #if _LIBCPP_STD_VER > 11
2254 explicit vector(size_type __n, const allocator_type& __a);
2256 vector(size_type __n, const value_type& __v);
2257 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2258 template <class _InputIterator>
2259 vector(_InputIterator __first, _InputIterator __last,
2260 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2261 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2262 template <class _InputIterator>
2263 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2264 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2265 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2266 template <class _ForwardIterator>
2267 vector(_ForwardIterator __first, _ForwardIterator __last,
2268 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2269 template <class _ForwardIterator>
2270 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2271 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2273 vector(const vector& __v);
2274 vector(const vector& __v, const allocator_type& __a);
2275 vector& operator=(const vector& __v);
2277 #ifndef _LIBCPP_CXX03_LANG
2278 vector(initializer_list<value_type> __il);
2279 vector(initializer_list<value_type> __il, const allocator_type& __a);
2281 _LIBCPP_INLINE_VISIBILITY
2282 vector(vector&& __v)
2283 #if _LIBCPP_STD_VER > 14
2286 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2288 vector(vector&& __v, const allocator_type& __a);
2289 _LIBCPP_INLINE_VISIBILITY
2290 vector& operator=(vector&& __v)
2291 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
2293 _LIBCPP_INLINE_VISIBILITY
2294 vector& operator=(initializer_list<value_type> __il)
2295 {assign(__il.begin(), __il.end()); return *this;}
2297 #endif // !_LIBCPP_CXX03_LANG
2299 template <class _InputIterator>
2302 __is_input_iterator<_InputIterator>::value &&
2303 !__is_forward_iterator<_InputIterator>::value,
2306 assign(_InputIterator __first, _InputIterator __last);
2307 template <class _ForwardIterator>
2310 __is_forward_iterator<_ForwardIterator>::value,
2313 assign(_ForwardIterator __first, _ForwardIterator __last);
2315 void assign(size_type __n, const value_type& __x);
2317 #ifndef _LIBCPP_CXX03_LANG
2318 _LIBCPP_INLINE_VISIBILITY
2319 void assign(initializer_list<value_type> __il)
2320 {assign(__il.begin(), __il.end());}
2323 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2324 {return allocator_type(this->__alloc());}
2326 size_type max_size() const _NOEXCEPT;
2327 _LIBCPP_INLINE_VISIBILITY
2328 size_type capacity() const _NOEXCEPT
2329 {return __internal_cap_to_external(__cap());}
2330 _LIBCPP_INLINE_VISIBILITY
2331 size_type size() const _NOEXCEPT
2333 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
2334 bool empty() const _NOEXCEPT
2335 {return __size_ == 0;}
2336 void reserve(size_type __n);
2337 void shrink_to_fit() _NOEXCEPT;
2339 _LIBCPP_INLINE_VISIBILITY
2340 iterator begin() _NOEXCEPT
2341 {return __make_iter(0);}
2342 _LIBCPP_INLINE_VISIBILITY
2343 const_iterator begin() const _NOEXCEPT
2344 {return __make_iter(0);}
2345 _LIBCPP_INLINE_VISIBILITY
2346 iterator end() _NOEXCEPT
2347 {return __make_iter(__size_);}
2348 _LIBCPP_INLINE_VISIBILITY
2349 const_iterator end() const _NOEXCEPT
2350 {return __make_iter(__size_);}
2352 _LIBCPP_INLINE_VISIBILITY
2353 reverse_iterator rbegin() _NOEXCEPT
2354 {return reverse_iterator(end());}
2355 _LIBCPP_INLINE_VISIBILITY
2356 const_reverse_iterator rbegin() const _NOEXCEPT
2357 {return const_reverse_iterator(end());}
2358 _LIBCPP_INLINE_VISIBILITY
2359 reverse_iterator rend() _NOEXCEPT
2360 {return reverse_iterator(begin());}
2361 _LIBCPP_INLINE_VISIBILITY
2362 const_reverse_iterator rend() const _NOEXCEPT
2363 {return const_reverse_iterator(begin());}
2365 _LIBCPP_INLINE_VISIBILITY
2366 const_iterator cbegin() const _NOEXCEPT
2367 {return __make_iter(0);}
2368 _LIBCPP_INLINE_VISIBILITY
2369 const_iterator cend() const _NOEXCEPT
2370 {return __make_iter(__size_);}
2371 _LIBCPP_INLINE_VISIBILITY
2372 const_reverse_iterator crbegin() const _NOEXCEPT
2374 _LIBCPP_INLINE_VISIBILITY
2375 const_reverse_iterator crend() const _NOEXCEPT
2378 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2379 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2380 reference at(size_type __n);
2381 const_reference at(size_type __n) const;
2383 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2384 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2385 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2386 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2388 void push_back(const value_type& __x);
2389 #if _LIBCPP_STD_VER > 11
2390 template <class... _Args>
2391 #if _LIBCPP_STD_VER > 14
2392 _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args)
2394 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
2397 push_back ( value_type ( _VSTD::forward<_Args>(__args)... ));
2398 #if _LIBCPP_STD_VER > 14
2399 return this->back();
2404 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2406 #if _LIBCPP_STD_VER > 11
2407 template <class... _Args>
2408 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
2409 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
2412 iterator insert(const_iterator __position, const value_type& __x);
2413 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2414 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2415 template <class _InputIterator>
2418 __is_input_iterator <_InputIterator>::value &&
2419 !__is_forward_iterator<_InputIterator>::value,
2422 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2423 template <class _ForwardIterator>
2426 __is_forward_iterator<_ForwardIterator>::value,
2429 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2431 #ifndef _LIBCPP_CXX03_LANG
2432 _LIBCPP_INLINE_VISIBILITY
2433 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2434 {return insert(__position, __il.begin(), __il.end());}
2437 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2438 iterator erase(const_iterator __first, const_iterator __last);
2440 _LIBCPP_INLINE_VISIBILITY
2441 void clear() _NOEXCEPT {__size_ = 0;}
2444 #if _LIBCPP_STD_VER >= 14
2447 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2448 __is_nothrow_swappable<allocator_type>::value);
2450 static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); }
2452 void resize(size_type __sz, value_type __x = false);
2453 void flip() _NOEXCEPT;
2455 bool __invariants() const;
2458 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2459 void __vallocate(size_type __n);
2460 void __vdeallocate() _NOEXCEPT;
2461 _LIBCPP_INLINE_VISIBILITY
2462 static size_type __align_it(size_type __new_size) _NOEXCEPT
2463 {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}
2464 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2465 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2466 template <class _ForwardIterator>
2469 __is_forward_iterator<_ForwardIterator>::value,
2472 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2473 void __append(size_type __n, const_reference __x);
2474 _LIBCPP_INLINE_VISIBILITY
2475 reference __make_ref(size_type __pos) _NOEXCEPT
2476 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2477 _LIBCPP_INLINE_VISIBILITY
2478 const_reference __make_ref(size_type __pos) const _NOEXCEPT
2479 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2480 _LIBCPP_INLINE_VISIBILITY
2481 iterator __make_iter(size_type __pos) _NOEXCEPT
2482 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2483 _LIBCPP_INLINE_VISIBILITY
2484 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2485 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2486 _LIBCPP_INLINE_VISIBILITY
2487 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2488 {return begin() + (__p - cbegin());}
2490 _LIBCPP_INLINE_VISIBILITY
2491 void __copy_assign_alloc(const vector& __v)
2492 {__copy_assign_alloc(__v, integral_constant<bool,
2493 __storage_traits::propagate_on_container_copy_assignment::value>());}
2494 _LIBCPP_INLINE_VISIBILITY
2495 void __copy_assign_alloc(const vector& __c, true_type)
2497 if (__alloc() != __c.__alloc())
2499 __alloc() = __c.__alloc();
2502 _LIBCPP_INLINE_VISIBILITY
2503 void __copy_assign_alloc(const vector&, false_type)
2506 void __move_assign(vector& __c, false_type);
2507 void __move_assign(vector& __c, true_type)
2508 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2509 _LIBCPP_INLINE_VISIBILITY
2510 void __move_assign_alloc(vector& __c)
2512 !__storage_traits::propagate_on_container_move_assignment::value ||
2513 is_nothrow_move_assignable<allocator_type>::value)
2514 {__move_assign_alloc(__c, integral_constant<bool,
2515 __storage_traits::propagate_on_container_move_assignment::value>());}
2516 _LIBCPP_INLINE_VISIBILITY
2517 void __move_assign_alloc(vector& __c, true_type)
2518 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2520 __alloc() = _VSTD::move(__c.__alloc());
2523 _LIBCPP_INLINE_VISIBILITY
2524 void __move_assign_alloc(vector&, false_type)
2528 size_t __hash_code() const _NOEXCEPT;
2530 friend class __bit_reference<vector>;
2531 friend class __bit_const_reference<vector>;
2532 friend class __bit_iterator<vector, false>;
2533 friend class __bit_iterator<vector, true>;
2534 friend struct __bit_array<vector>;
2535 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
2538 template <class _Allocator>
2539 inline _LIBCPP_INLINE_VISIBILITY
2541 vector<bool, _Allocator>::__invalidate_all_iterators()
2545 // Allocate space for __n objects
2546 // throws length_error if __n > max_size()
2547 // throws (probably bad_alloc) if memory run out
2548 // Precondition: __begin_ == __end_ == __cap() == 0
2549 // Precondition: __n > 0
2550 // Postcondition: capacity() == __n
2551 // Postcondition: size() == 0
2552 template <class _Allocator>
2554 vector<bool, _Allocator>::__vallocate(size_type __n)
2556 if (__n > max_size())
2557 this->__throw_length_error();
2558 __n = __external_cap_to_internal(__n);
2559 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2561 this->__cap() = __n;
2564 template <class _Allocator>
2566 vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
2568 if (this->__begin_ != nullptr)
2570 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2571 __invalidate_all_iterators();
2572 this->__begin_ = nullptr;
2573 this->__size_ = this->__cap() = 0;
2577 template <class _Allocator>
2578 typename vector<bool, _Allocator>::size_type
2579 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2581 size_type __amax = __storage_traits::max_size(__alloc());
2582 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2583 if (__nmax / __bits_per_word <= __amax)
2585 return __internal_cap_to_external(__amax);
2588 // Precondition: __new_size > capacity()
2589 template <class _Allocator>
2590 inline _LIBCPP_INLINE_VISIBILITY
2591 typename vector<bool, _Allocator>::size_type
2592 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2594 const size_type __ms = max_size();
2595 if (__new_size > __ms)
2596 this->__throw_length_error();
2597 const size_type __cap = capacity();
2598 if (__cap >= __ms / 2)
2600 return _VSTD::max(2*__cap, __align_it(__new_size));
2603 // Default constructs __n objects starting at __end_
2604 // Precondition: __n > 0
2605 // Precondition: size() + __n <= capacity()
2606 // Postcondition: size() == size() + __n
2607 template <class _Allocator>
2608 inline _LIBCPP_INLINE_VISIBILITY
2610 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2612 size_type __old_size = this->__size_;
2613 this->__size_ += __n;
2614 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2616 if (this->__size_ <= __bits_per_word)
2617 this->__begin_[0] = __storage_type(0);
2619 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2621 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2624 template <class _Allocator>
2625 template <class _ForwardIterator>
2628 __is_forward_iterator<_ForwardIterator>::value,
2631 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2633 size_type __old_size = this->__size_;
2634 this->__size_ += _VSTD::distance(__first, __last);
2635 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2637 if (this->__size_ <= __bits_per_word)
2638 this->__begin_[0] = __storage_type(0);
2640 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2642 _VSTD::copy(__first, __last, __make_iter(__old_size));
2645 template <class _Allocator>
2646 inline _LIBCPP_INLINE_VISIBILITY
2647 vector<bool, _Allocator>::vector()
2648 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2649 : __begin_(nullptr),
2655 template <class _Allocator>
2656 inline _LIBCPP_INLINE_VISIBILITY
2657 vector<bool, _Allocator>::vector(const allocator_type& __a)
2658 #if _LIBCPP_STD_VER <= 14
2659 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
2663 : __begin_(nullptr),
2665 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2669 template <class _Allocator>
2670 vector<bool, _Allocator>::vector(size_type __n)
2671 : __begin_(nullptr),
2678 __construct_at_end(__n, false);
2682 #if _LIBCPP_STD_VER > 11
2683 template <class _Allocator>
2684 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2685 : __begin_(nullptr),
2687 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2692 __construct_at_end(__n, false);
2697 template <class _Allocator>
2698 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2699 : __begin_(nullptr),
2706 __construct_at_end(__n, __x);
2710 template <class _Allocator>
2711 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2712 : __begin_(nullptr),
2714 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2719 __construct_at_end(__n, __x);
2723 template <class _Allocator>
2724 template <class _InputIterator>
2725 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2726 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2727 !__is_forward_iterator<_InputIterator>::value>::type*)
2728 : __begin_(nullptr),
2732 #ifndef _LIBCPP_NO_EXCEPTIONS
2735 #endif // _LIBCPP_NO_EXCEPTIONS
2736 for (; __first != __last; ++__first)
2737 push_back(*__first);
2738 #ifndef _LIBCPP_NO_EXCEPTIONS
2742 if (__begin_ != nullptr)
2743 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2744 __invalidate_all_iterators();
2747 #endif // _LIBCPP_NO_EXCEPTIONS
2750 template <class _Allocator>
2751 template <class _InputIterator>
2752 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2753 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2754 !__is_forward_iterator<_InputIterator>::value>::type*)
2755 : __begin_(nullptr),
2757 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2759 #ifndef _LIBCPP_NO_EXCEPTIONS
2762 #endif // _LIBCPP_NO_EXCEPTIONS
2763 for (; __first != __last; ++__first)
2764 push_back(*__first);
2765 #ifndef _LIBCPP_NO_EXCEPTIONS
2769 if (__begin_ != nullptr)
2770 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2771 __invalidate_all_iterators();
2774 #endif // _LIBCPP_NO_EXCEPTIONS
2777 template <class _Allocator>
2778 template <class _ForwardIterator>
2779 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2780 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2781 : __begin_(nullptr),
2785 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2789 __construct_at_end(__first, __last);
2793 template <class _Allocator>
2794 template <class _ForwardIterator>
2795 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2796 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2797 : __begin_(nullptr),
2799 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2801 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2805 __construct_at_end(__first, __last);
2809 #ifndef _LIBCPP_CXX03_LANG
2811 template <class _Allocator>
2812 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2813 : __begin_(nullptr),
2817 size_type __n = static_cast<size_type>(__il.size());
2821 __construct_at_end(__il.begin(), __il.end());
2825 template <class _Allocator>
2826 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2827 : __begin_(nullptr),
2829 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2831 size_type __n = static_cast<size_type>(__il.size());
2835 __construct_at_end(__il.begin(), __il.end());
2839 #endif // _LIBCPP_CXX03_LANG
2841 template <class _Allocator>
2842 vector<bool, _Allocator>::~vector()
2844 if (__begin_ != nullptr)
2845 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2846 __invalidate_all_iterators();
2849 template <class _Allocator>
2850 vector<bool, _Allocator>::vector(const vector& __v)
2851 : __begin_(nullptr),
2853 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2857 __vallocate(__v.size());
2858 __construct_at_end(__v.begin(), __v.end());
2862 template <class _Allocator>
2863 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2864 : __begin_(nullptr),
2866 __cap_alloc_(0, __a)
2870 __vallocate(__v.size());
2871 __construct_at_end(__v.begin(), __v.end());
2875 template <class _Allocator>
2876 vector<bool, _Allocator>&
2877 vector<bool, _Allocator>::operator=(const vector& __v)
2881 __copy_assign_alloc(__v);
2884 if (__v.__size_ > capacity())
2887 __vallocate(__v.__size_);
2889 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2891 __size_ = __v.__size_;
2896 #ifndef _LIBCPP_CXX03_LANG
2898 template <class _Allocator>
2899 inline _LIBCPP_INLINE_VISIBILITY vector<bool, _Allocator>::vector(vector&& __v)
2900 #if _LIBCPP_STD_VER > 14
2903 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2905 : __begin_(__v.__begin_),
2906 __size_(__v.__size_),
2907 __cap_alloc_(std::move(__v.__cap_alloc_)) {
2908 __v.__begin_ = nullptr;
2913 template <class _Allocator>
2914 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2915 : __begin_(nullptr),
2917 __cap_alloc_(0, __a)
2919 if (__a == allocator_type(__v.__alloc()))
2921 this->__begin_ = __v.__begin_;
2922 this->__size_ = __v.__size_;
2923 this->__cap() = __v.__cap();
2924 __v.__begin_ = nullptr;
2925 __v.__cap() = __v.__size_ = 0;
2927 else if (__v.size() > 0)
2929 __vallocate(__v.size());
2930 __construct_at_end(__v.begin(), __v.end());
2934 template <class _Allocator>
2935 inline _LIBCPP_INLINE_VISIBILITY
2936 vector<bool, _Allocator>&
2937 vector<bool, _Allocator>::operator=(vector&& __v)
2938 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
2940 __move_assign(__v, integral_constant<bool,
2941 __storage_traits::propagate_on_container_move_assignment::value>());
2945 template <class _Allocator>
2947 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2949 if (__alloc() != __c.__alloc())
2950 assign(__c.begin(), __c.end());
2952 __move_assign(__c, true_type());
2955 template <class _Allocator>
2957 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2958 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2961 __move_assign_alloc(__c);
2962 this->__begin_ = __c.__begin_;
2963 this->__size_ = __c.__size_;
2964 this->__cap() = __c.__cap();
2965 __c.__begin_ = nullptr;
2966 __c.__cap() = __c.__size_ = 0;
2969 #endif // !_LIBCPP_CXX03_LANG
2971 template <class _Allocator>
2973 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2978 size_type __c = capacity();
2983 vector __v(__alloc());
2984 __v.reserve(__recommend(__n));
2988 _VSTD::fill_n(begin(), __n, __x);
2990 __invalidate_all_iterators();
2993 template <class _Allocator>
2994 template <class _InputIterator>
2997 __is_input_iterator<_InputIterator>::value &&
2998 !__is_forward_iterator<_InputIterator>::value,
3001 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
3004 for (; __first != __last; ++__first)
3005 push_back(*__first);
3008 template <class _Allocator>
3009 template <class _ForwardIterator>
3012 __is_forward_iterator<_ForwardIterator>::value,
3015 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
3018 difference_type __ns = _VSTD::distance(__first, __last);
3019 _LIBCPP_ASSERT(__ns >= 0, "invalid range specified");
3020 const size_t __n = static_cast<size_type>(__ns);
3023 if (__n > capacity())
3028 __construct_at_end(__first, __last);
3032 template <class _Allocator>
3034 vector<bool, _Allocator>::reserve(size_type __n)
3036 if (__n > capacity())
3038 vector __v(this->__alloc());
3039 __v.__vallocate(__n);
3040 __v.__construct_at_end(this->begin(), this->end());
3042 __invalidate_all_iterators();
3046 template <class _Allocator>
3048 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
3050 if (__external_cap_to_internal(size()) > __cap())
3052 #ifndef _LIBCPP_NO_EXCEPTIONS
3055 #endif // _LIBCPP_NO_EXCEPTIONS
3056 vector(*this, allocator_type(__alloc())).swap(*this);
3057 #ifndef _LIBCPP_NO_EXCEPTIONS
3062 #endif // _LIBCPP_NO_EXCEPTIONS
3066 template <class _Allocator>
3067 typename vector<bool, _Allocator>::reference
3068 vector<bool, _Allocator>::at(size_type __n)
3071 this->__throw_out_of_range();
3072 return (*this)[__n];
3075 template <class _Allocator>
3076 typename vector<bool, _Allocator>::const_reference
3077 vector<bool, _Allocator>::at(size_type __n) const
3080 this->__throw_out_of_range();
3081 return (*this)[__n];
3084 template <class _Allocator>
3086 vector<bool, _Allocator>::push_back(const value_type& __x)
3088 if (this->__size_ == this->capacity())
3089 reserve(__recommend(this->__size_ + 1));
3094 template <class _Allocator>
3095 typename vector<bool, _Allocator>::iterator
3096 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
3099 if (size() < capacity())
3101 const_iterator __old_end = end();
3103 _VSTD::copy_backward(__position, __old_end, end());
3104 __r = __const_iterator_cast(__position);
3108 vector __v(__alloc());
3109 __v.reserve(__recommend(__size_ + 1));
3110 __v.__size_ = __size_ + 1;
3111 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3112 _VSTD::copy_backward(__position, cend(), __v.end());
3119 template <class _Allocator>
3120 typename vector<bool, _Allocator>::iterator
3121 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
3124 size_type __c = capacity();
3125 if (__n <= __c && size() <= __c - __n)
3127 const_iterator __old_end = end();
3129 _VSTD::copy_backward(__position, __old_end, end());
3130 __r = __const_iterator_cast(__position);
3134 vector __v(__alloc());
3135 __v.reserve(__recommend(__size_ + __n));
3136 __v.__size_ = __size_ + __n;
3137 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3138 _VSTD::copy_backward(__position, cend(), __v.end());
3141 _VSTD::fill_n(__r, __n, __x);
3145 template <class _Allocator>
3146 template <class _InputIterator>
3149 __is_input_iterator <_InputIterator>::value &&
3150 !__is_forward_iterator<_InputIterator>::value,
3151 typename vector<bool, _Allocator>::iterator
3153 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
3155 difference_type __off = __position - begin();
3156 iterator __p = __const_iterator_cast(__position);
3157 iterator __old_end = end();
3158 for (; size() != capacity() && __first != __last; ++__first)
3163 vector __v(__alloc());
3164 if (__first != __last)
3166 #ifndef _LIBCPP_NO_EXCEPTIONS
3169 #endif // _LIBCPP_NO_EXCEPTIONS
3170 __v.assign(__first, __last);
3171 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
3172 difference_type __old_p = __p - begin();
3173 reserve(__recommend(size() + __v.size()));
3174 __p = begin() + __old_p;
3175 __old_end = begin() + __old_size;
3176 #ifndef _LIBCPP_NO_EXCEPTIONS
3180 erase(__old_end, end());
3183 #endif // _LIBCPP_NO_EXCEPTIONS
3185 __p = _VSTD::rotate(__p, __old_end, end());
3186 insert(__p, __v.begin(), __v.end());
3187 return begin() + __off;
3190 template <class _Allocator>
3191 template <class _ForwardIterator>
3194 __is_forward_iterator<_ForwardIterator>::value,
3195 typename vector<bool, _Allocator>::iterator
3197 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3199 const difference_type __n_signed = _VSTD::distance(__first, __last);
3200 _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified");
3201 const size_type __n = static_cast<size_type>(__n_signed);
3203 size_type __c = capacity();
3204 if (__n <= __c && size() <= __c - __n)
3206 const_iterator __old_end = end();
3208 _VSTD::copy_backward(__position, __old_end, end());
3209 __r = __const_iterator_cast(__position);
3213 vector __v(__alloc());
3214 __v.reserve(__recommend(__size_ + __n));
3215 __v.__size_ = __size_ + __n;
3216 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3217 _VSTD::copy_backward(__position, cend(), __v.end());
3220 _VSTD::copy(__first, __last, __r);
3224 template <class _Allocator>
3225 inline _LIBCPP_INLINE_VISIBILITY
3226 typename vector<bool, _Allocator>::iterator
3227 vector<bool, _Allocator>::erase(const_iterator __position)
3229 iterator __r = __const_iterator_cast(__position);
3230 _VSTD::copy(__position + 1, this->cend(), __r);
3235 template <class _Allocator>
3236 typename vector<bool, _Allocator>::iterator
3237 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3239 iterator __r = __const_iterator_cast(__first);
3240 difference_type __d = __last - __first;
3241 _VSTD::copy(__last, this->cend(), __r);
3246 template <class _Allocator>
3248 vector<bool, _Allocator>::swap(vector& __x)
3249 #if _LIBCPP_STD_VER >= 14
3252 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3253 __is_nothrow_swappable<allocator_type>::value)
3256 _VSTD::swap(this->__begin_, __x.__begin_);
3257 _VSTD::swap(this->__size_, __x.__size_);
3258 _VSTD::swap(this->__cap(), __x.__cap());
3259 __swap_allocator(this->__alloc(), __x.__alloc(),
3260 integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
3263 template <class _Allocator>
3265 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3267 size_type __cs = size();
3271 size_type __c = capacity();
3272 size_type __n = __sz - __cs;
3273 if (__n <= __c && __cs <= __c - __n)
3280 vector __v(__alloc());
3281 __v.reserve(__recommend(__size_ + __n));
3282 __v.__size_ = __size_ + __n;
3283 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3286 _VSTD::fill_n(__r, __n, __x);
3292 template <class _Allocator>
3294 vector<bool, _Allocator>::flip() _NOEXCEPT
3296 // do middle whole words
3297 size_type __n = __size_;
3298 __storage_pointer __p = __begin_;
3299 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3301 // do last partial word
3304 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3305 __storage_type __b = *__p & __m;
3311 template <class _Allocator>
3313 vector<bool, _Allocator>::__invariants() const
3315 if (this->__begin_ == nullptr)
3317 if (this->__size_ != 0 || this->__cap() != 0)
3322 if (this->__cap() == 0)
3324 if (this->__size_ > this->capacity())
3330 template <class _Allocator>
3332 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3335 // do middle whole words
3336 size_type __n = __size_;
3337 __storage_pointer __p = __begin_;
3338 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3340 // do last partial word
3343 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3349 template <class _Allocator>
3350 struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
3351 : public unary_function<vector<bool, _Allocator>, size_t>
3353 _LIBCPP_INLINE_VISIBILITY
3354 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3355 {return __vec.__hash_code();}
3358 template <class _Tp, class _Allocator>
3359 inline _LIBCPP_INLINE_VISIBILITY
3361 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3363 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3364 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3367 template <class _Tp, class _Allocator>
3368 inline _LIBCPP_INLINE_VISIBILITY
3370 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3372 return !(__x == __y);
3375 template <class _Tp, class _Allocator>
3376 inline _LIBCPP_INLINE_VISIBILITY
3378 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3380 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3383 template <class _Tp, class _Allocator>
3384 inline _LIBCPP_INLINE_VISIBILITY
3386 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3391 template <class _Tp, class _Allocator>
3392 inline _LIBCPP_INLINE_VISIBILITY
3394 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3396 return !(__x < __y);
3399 template <class _Tp, class _Allocator>
3400 inline _LIBCPP_INLINE_VISIBILITY
3402 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3404 return !(__y < __x);
3407 template <class _Tp, class _Allocator>
3408 inline _LIBCPP_INLINE_VISIBILITY
3410 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3411 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3416 #if _LIBCPP_STD_VER > 17
3417 template <class _Tp, class _Allocator, class _Up>
3418 inline _LIBCPP_INLINE_VISIBILITY
3419 void erase(vector<_Tp, _Allocator>& __c, const _Up& __v)
3420 { __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); }
3422 template <class _Tp, class _Allocator, class _Predicate>
3423 inline _LIBCPP_INLINE_VISIBILITY
3424 void erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred)
3425 { __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); }
3428 _LIBCPP_END_NAMESPACE_STD
3432 #endif // _LIBCPP_VECTOR