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 is_nothrow_move_assignable<allocator_type>::value);
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 void emplace_back(Args&&... args);
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_type::propagate_on_container_swap::value ||
123 __is_nothrow_swappable<allocator_type>::value);
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 is_nothrow_move_assignable<allocator_type>::value);
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> void emplace_back(Args&&... args); // C++14
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_type::propagate_on_container_swap::value ||
241 __is_nothrow_swappable<allocator_type>::value);
242 void flip() noexcept;
244 bool __invariants() const;
247 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
249 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
250 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
251 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
252 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
253 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
254 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
256 template <class T, class Allocator>
257 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
258 noexcept(noexcept(x.swap(y)));
265 #include <__bit_reference>
266 #include <type_traits>
269 #include <initializer_list>
274 #include <__split_buffer>
275 #include <__functional_base>
277 #include <__undef_min_max>
282 # define _LIBCPP_ASSERT(x, m) ((void)0)
285 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
286 #pragma GCC system_header
289 _LIBCPP_BEGIN_NAMESPACE_STD
292 class __vector_base_common
295 _LIBCPP_ALWAYS_INLINE __vector_base_common() {}
296 void __throw_length_error() const;
297 void __throw_out_of_range() const;
302 __vector_base_common<__b>::__throw_length_error() const
304 #ifndef _LIBCPP_NO_EXCEPTIONS
305 throw length_error("vector");
307 assert(!"vector length_error");
313 __vector_base_common<__b>::__throw_out_of_range() const
315 #ifndef _LIBCPP_NO_EXCEPTIONS
316 throw out_of_range("vector");
318 assert(!"vector out_of_range");
323 #pragma warning( push )
324 #pragma warning( disable: 4231 )
325 #endif // _LIBCPP_MSVC
326 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS __vector_base_common<true>)
328 #pragma warning( pop )
329 #endif // _LIBCPP_MSVC
331 template <class _Tp, class _Allocator>
333 : protected __vector_base_common<true>
336 typedef _Tp value_type;
337 typedef _Allocator allocator_type;
338 typedef allocator_traits<allocator_type> __alloc_traits;
339 typedef value_type& reference;
340 typedef const value_type& const_reference;
341 typedef typename __alloc_traits::size_type size_type;
342 typedef typename __alloc_traits::difference_type difference_type;
343 typedef typename __alloc_traits::pointer pointer;
344 typedef typename __alloc_traits::const_pointer const_pointer;
345 typedef pointer iterator;
346 typedef const_pointer const_iterator;
350 __compressed_pair<pointer, allocator_type> __end_cap_;
352 _LIBCPP_INLINE_VISIBILITY
353 allocator_type& __alloc() _NOEXCEPT
354 {return __end_cap_.second();}
355 _LIBCPP_INLINE_VISIBILITY
356 const allocator_type& __alloc() const _NOEXCEPT
357 {return __end_cap_.second();}
358 _LIBCPP_INLINE_VISIBILITY
359 pointer& __end_cap() _NOEXCEPT
360 {return __end_cap_.first();}
361 _LIBCPP_INLINE_VISIBILITY
362 const pointer& __end_cap() const _NOEXCEPT
363 {return __end_cap_.first();}
365 _LIBCPP_INLINE_VISIBILITY
367 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
368 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
371 _LIBCPP_INLINE_VISIBILITY
372 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
373 _LIBCPP_INLINE_VISIBILITY
374 size_type capacity() const _NOEXCEPT
375 {return static_cast<size_type>(__end_cap() - __begin_);}
377 _LIBCPP_INLINE_VISIBILITY
378 void __destruct_at_end(pointer __new_last) _NOEXCEPT;
380 _LIBCPP_INLINE_VISIBILITY
381 void __copy_assign_alloc(const __vector_base& __c)
382 {__copy_assign_alloc(__c, integral_constant<bool,
383 __alloc_traits::propagate_on_container_copy_assignment::value>());}
385 _LIBCPP_INLINE_VISIBILITY
386 void __move_assign_alloc(__vector_base& __c)
388 !__alloc_traits::propagate_on_container_move_assignment::value ||
389 is_nothrow_move_assignable<allocator_type>::value)
390 {__move_assign_alloc(__c, integral_constant<bool,
391 __alloc_traits::propagate_on_container_move_assignment::value>());}
393 _LIBCPP_INLINE_VISIBILITY
394 static void __swap_alloc(allocator_type& __x, allocator_type& __y)
396 !__alloc_traits::propagate_on_container_swap::value ||
397 __is_nothrow_swappable<allocator_type>::value)
398 {__swap_alloc(__x, __y, integral_constant<bool,
399 __alloc_traits::propagate_on_container_swap::value>());}
401 _LIBCPP_INLINE_VISIBILITY
402 void __copy_assign_alloc(const __vector_base& __c, true_type)
404 if (__alloc() != __c.__alloc())
407 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
408 __begin_ = __end_ = __end_cap() = nullptr;
410 __alloc() = __c.__alloc();
413 _LIBCPP_INLINE_VISIBILITY
414 void __copy_assign_alloc(const __vector_base&, false_type)
417 _LIBCPP_INLINE_VISIBILITY
418 void __move_assign_alloc(__vector_base& __c, true_type)
419 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
421 __alloc() = _VSTD::move(__c.__alloc());
424 _LIBCPP_INLINE_VISIBILITY
425 void __move_assign_alloc(__vector_base&, false_type)
429 _LIBCPP_INLINE_VISIBILITY
430 static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type)
431 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
436 _LIBCPP_INLINE_VISIBILITY
437 static void __swap_alloc(allocator_type&, allocator_type&, false_type)
442 template <class _Tp, class _Allocator>
443 inline _LIBCPP_INLINE_VISIBILITY
445 __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
447 while (__new_last != __end_)
448 __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_));
451 template <class _Tp, class _Allocator>
452 inline _LIBCPP_INLINE_VISIBILITY
453 __vector_base<_Tp, _Allocator>::__vector_base()
454 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
461 template <class _Tp, class _Allocator>
462 inline _LIBCPP_INLINE_VISIBILITY
463 __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
466 __end_cap_(nullptr, __a)
470 template <class _Tp, class _Allocator>
471 __vector_base<_Tp, _Allocator>::~__vector_base()
473 if (__begin_ != nullptr)
476 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
480 template <class _Tp, class _Allocator = allocator<_Tp> >
481 class _LIBCPP_TYPE_VIS_ONLY vector
482 : private __vector_base<_Tp, _Allocator>
485 typedef __vector_base<_Tp, _Allocator> __base;
487 typedef vector __self;
488 typedef _Tp value_type;
489 typedef _Allocator allocator_type;
490 typedef typename __base::__alloc_traits __alloc_traits;
491 typedef typename __base::reference reference;
492 typedef typename __base::const_reference const_reference;
493 typedef typename __base::size_type size_type;
494 typedef typename __base::difference_type difference_type;
495 typedef typename __base::pointer pointer;
496 typedef typename __base::const_pointer const_pointer;
497 typedef __wrap_iter<pointer> iterator;
498 typedef __wrap_iter<const_pointer> const_iterator;
499 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
500 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
502 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
503 "Allocator::value_type must be same type as value_type");
505 _LIBCPP_INLINE_VISIBILITY
507 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
509 #if _LIBCPP_DEBUG_LEVEL >= 2
510 __get_db()->__insert_c(this);
513 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
516 #if _LIBCPP_DEBUG_LEVEL >= 2
517 __get_db()->__insert_c(this);
520 explicit vector(size_type __n);
521 #if _LIBCPP_STD_VER > 11
522 explicit vector(size_type __n, const allocator_type& __a);
524 vector(size_type __n, const_reference __x);
525 vector(size_type __n, const_reference __x, const allocator_type& __a);
526 template <class _InputIterator>
527 vector(_InputIterator __first,
528 typename enable_if<__is_input_iterator <_InputIterator>::value &&
529 !__is_forward_iterator<_InputIterator>::value &&
532 typename iterator_traits<_InputIterator>::reference>::value,
533 _InputIterator>::type __last);
534 template <class _InputIterator>
535 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
536 typename enable_if<__is_input_iterator <_InputIterator>::value &&
537 !__is_forward_iterator<_InputIterator>::value &&
540 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
541 template <class _ForwardIterator>
542 vector(_ForwardIterator __first,
543 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
546 typename iterator_traits<_ForwardIterator>::reference>::value,
547 _ForwardIterator>::type __last);
548 template <class _ForwardIterator>
549 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
550 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
553 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
554 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
555 _LIBCPP_INLINE_VISIBILITY
556 vector(initializer_list<value_type> __il);
557 _LIBCPP_INLINE_VISIBILITY
558 vector(initializer_list<value_type> __il, const allocator_type& __a);
559 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
560 #if _LIBCPP_DEBUG_LEVEL >= 2
561 _LIBCPP_INLINE_VISIBILITY
564 __get_db()->__erase_c(this);
568 vector(const vector& __x);
569 vector(const vector& __x, const allocator_type& __a);
570 _LIBCPP_INLINE_VISIBILITY
571 vector& operator=(const vector& __x);
572 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
573 _LIBCPP_INLINE_VISIBILITY
575 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
576 _LIBCPP_INLINE_VISIBILITY
577 vector(vector&& __x, const allocator_type& __a);
578 _LIBCPP_INLINE_VISIBILITY
579 vector& operator=(vector&& __x)
581 __alloc_traits::propagate_on_container_move_assignment::value &&
582 is_nothrow_move_assignable<allocator_type>::value);
583 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
584 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
585 _LIBCPP_INLINE_VISIBILITY
586 vector& operator=(initializer_list<value_type> __il)
587 {assign(__il.begin(), __il.end()); return *this;}
588 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
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);
613 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
614 _LIBCPP_INLINE_VISIBILITY
615 void assign(initializer_list<value_type> __il)
616 {assign(__il.begin(), __il.end());}
617 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
619 _LIBCPP_INLINE_VISIBILITY
620 allocator_type get_allocator() const _NOEXCEPT
621 {return this->__alloc();}
623 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
624 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
625 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
626 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
628 _LIBCPP_INLINE_VISIBILITY
629 reverse_iterator rbegin() _NOEXCEPT
630 {return reverse_iterator(end());}
631 _LIBCPP_INLINE_VISIBILITY
632 const_reverse_iterator rbegin() const _NOEXCEPT
633 {return const_reverse_iterator(end());}
634 _LIBCPP_INLINE_VISIBILITY
635 reverse_iterator rend() _NOEXCEPT
636 {return reverse_iterator(begin());}
637 _LIBCPP_INLINE_VISIBILITY
638 const_reverse_iterator rend() const _NOEXCEPT
639 {return const_reverse_iterator(begin());}
641 _LIBCPP_INLINE_VISIBILITY
642 const_iterator cbegin() const _NOEXCEPT
644 _LIBCPP_INLINE_VISIBILITY
645 const_iterator cend() const _NOEXCEPT
647 _LIBCPP_INLINE_VISIBILITY
648 const_reverse_iterator crbegin() const _NOEXCEPT
650 _LIBCPP_INLINE_VISIBILITY
651 const_reverse_iterator crend() const _NOEXCEPT
654 _LIBCPP_INLINE_VISIBILITY
655 size_type size() const _NOEXCEPT
656 {return static_cast<size_type>(this->__end_ - this->__begin_);}
657 _LIBCPP_INLINE_VISIBILITY
658 size_type capacity() const _NOEXCEPT
659 {return __base::capacity();}
660 _LIBCPP_INLINE_VISIBILITY
661 bool empty() const _NOEXCEPT
662 {return this->__begin_ == this->__end_;}
663 size_type max_size() const _NOEXCEPT;
664 void reserve(size_type __n);
665 void shrink_to_fit() _NOEXCEPT;
667 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n);
668 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const;
669 reference at(size_type __n);
670 const_reference at(size_type __n) const;
672 _LIBCPP_INLINE_VISIBILITY reference front()
674 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
675 return *this->__begin_;
677 _LIBCPP_INLINE_VISIBILITY const_reference front() const
679 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
680 return *this->__begin_;
682 _LIBCPP_INLINE_VISIBILITY reference back()
684 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
685 return *(this->__end_ - 1);
687 _LIBCPP_INLINE_VISIBILITY const_reference back() const
689 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
690 return *(this->__end_ - 1);
693 _LIBCPP_INLINE_VISIBILITY
694 value_type* data() _NOEXCEPT
695 {return _VSTD::__to_raw_pointer(this->__begin_);}
696 _LIBCPP_INLINE_VISIBILITY
697 const value_type* data() const _NOEXCEPT
698 {return _VSTD::__to_raw_pointer(this->__begin_);}
700 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
701 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
702 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
703 #ifndef _LIBCPP_HAS_NO_VARIADICS
704 template <class... _Args>
705 void emplace_back(_Args&&... __args);
706 #endif // _LIBCPP_HAS_NO_VARIADICS
707 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
710 iterator insert(const_iterator __position, const_reference __x);
711 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
712 iterator insert(const_iterator __position, value_type&& __x);
713 #ifndef _LIBCPP_HAS_NO_VARIADICS
714 template <class... _Args>
715 iterator emplace(const_iterator __position, _Args&&... __args);
716 #endif // _LIBCPP_HAS_NO_VARIADICS
717 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
718 iterator insert(const_iterator __position, size_type __n, const_reference __x);
719 template <class _InputIterator>
722 __is_input_iterator <_InputIterator>::value &&
723 !__is_forward_iterator<_InputIterator>::value &&
726 typename iterator_traits<_InputIterator>::reference>::value,
729 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
730 template <class _ForwardIterator>
733 __is_forward_iterator<_ForwardIterator>::value &&
736 typename iterator_traits<_ForwardIterator>::reference>::value,
739 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
740 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
741 _LIBCPP_INLINE_VISIBILITY
742 iterator insert(const_iterator __position, initializer_list<value_type> __il)
743 {return insert(__position, __il.begin(), __il.end());}
744 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
746 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
747 iterator erase(const_iterator __first, const_iterator __last);
749 _LIBCPP_INLINE_VISIBILITY
750 void clear() _NOEXCEPT
753 __invalidate_all_iterators();
756 void resize(size_type __sz);
757 void resize(size_type __sz, const_reference __x);
760 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
761 __is_nothrow_swappable<allocator_type>::value);
763 bool __invariants() const;
765 #if _LIBCPP_DEBUG_LEVEL >= 2
767 bool __dereferenceable(const const_iterator* __i) const;
768 bool __decrementable(const const_iterator* __i) const;
769 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
770 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
772 #endif // _LIBCPP_DEBUG_LEVEL >= 2
775 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
776 void allocate(size_type __n);
777 void deallocate() _NOEXCEPT;
778 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
779 void __construct_at_end(size_type __n);
780 void __construct_at_end(size_type __n, const_reference __x);
781 template <class _ForwardIterator>
784 __is_forward_iterator<_ForwardIterator>::value,
787 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
788 void __move_construct_at_end(pointer __first, pointer __last);
789 void __append(size_type __n);
790 void __append(size_type __n, const_reference __x);
791 _LIBCPP_INLINE_VISIBILITY
792 iterator __make_iter(pointer __p) _NOEXCEPT;
793 _LIBCPP_INLINE_VISIBILITY
794 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
795 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
796 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
797 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
798 void __move_assign(vector& __c, true_type)
799 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
800 void __move_assign(vector& __c, false_type);
801 _LIBCPP_INLINE_VISIBILITY
802 void __destruct_at_end(pointer __new_last) _NOEXCEPT
804 #if _LIBCPP_DEBUG_LEVEL >= 2
805 __c_node* __c = __get_db()->__find_c_and_lock(this);
806 for (__i_node** __p = __c->end_; __p != __c->beg_; )
809 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
810 if (__i->base() > __new_last)
812 (*__p)->__c_ = nullptr;
813 if (--__c->end_ != __p)
814 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
817 __get_db()->unlock();
819 __base::__destruct_at_end(__new_last);
823 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
824 __push_back_slow_path(_Up&& __x);
826 __push_back_slow_path(_Up& __x);
828 #if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
829 template <class... _Args>
831 __emplace_back_slow_path(_Args&&... __args);
835 template <class _Tp, class _Allocator>
837 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
839 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
840 _VSTD::swap(this->__begin_, __v.__begin_);
841 _VSTD::swap(this->__end_, __v.__end_);
842 _VSTD::swap(this->__end_cap(), __v.__end_cap());
843 __v.__first_ = __v.__begin_;
844 __invalidate_all_iterators();
847 template <class _Tp, class _Allocator>
848 typename vector<_Tp, _Allocator>::pointer
849 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
851 pointer __r = __v.__begin_;
852 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
853 __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
854 _VSTD::swap(this->__begin_, __v.__begin_);
855 _VSTD::swap(this->__end_, __v.__end_);
856 _VSTD::swap(this->__end_cap(), __v.__end_cap());
857 __v.__first_ = __v.__begin_;
858 __invalidate_all_iterators();
862 // Allocate space for __n objects
863 // throws length_error if __n > max_size()
864 // throws (probably bad_alloc) if memory run out
865 // Precondition: __begin_ == __end_ == __end_cap() == 0
866 // Precondition: __n > 0
867 // Postcondition: capacity() == __n
868 // Postcondition: size() == 0
869 template <class _Tp, class _Allocator>
871 vector<_Tp, _Allocator>::allocate(size_type __n)
873 if (__n > max_size())
874 this->__throw_length_error();
875 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
876 this->__end_cap() = this->__begin_ + __n;
879 template <class _Tp, class _Allocator>
881 vector<_Tp, _Allocator>::deallocate() _NOEXCEPT
883 if (this->__begin_ != nullptr)
886 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
887 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
891 template <class _Tp, class _Allocator>
892 typename vector<_Tp, _Allocator>::size_type
893 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
895 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always
898 // Precondition: __new_size > capacity()
899 template <class _Tp, class _Allocator>
900 inline _LIBCPP_INLINE_VISIBILITY
901 typename vector<_Tp, _Allocator>::size_type
902 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
904 const size_type __ms = max_size();
905 if (__new_size > __ms)
906 this->__throw_length_error();
907 const size_type __cap = capacity();
908 if (__cap >= __ms / 2)
910 return _VSTD::max<size_type>(2*__cap, __new_size);
913 // Default constructs __n objects starting at __end_
914 // throws if construction throws
915 // Precondition: __n > 0
916 // Precondition: size() + __n <= capacity()
917 // Postcondition: size() == size() + __n
918 template <class _Tp, class _Allocator>
920 vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
922 allocator_type& __a = this->__alloc();
925 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
931 // Copy constructs __n objects starting at __end_ from __x
932 // throws if construction throws
933 // Precondition: __n > 0
934 // Precondition: size() + __n <= capacity()
935 // Postcondition: size() == old size() + __n
936 // Postcondition: [i] == __x for all i in [size() - __n, __n)
937 template <class _Tp, class _Allocator>
938 inline _LIBCPP_INLINE_VISIBILITY
940 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
942 allocator_type& __a = this->__alloc();
945 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
951 template <class _Tp, class _Allocator>
952 template <class _ForwardIterator>
955 __is_forward_iterator<_ForwardIterator>::value,
958 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
960 allocator_type& __a = this->__alloc();
961 for (; __first != __last; ++__first)
963 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
968 template <class _Tp, class _Allocator>
970 vector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last)
972 allocator_type& __a = this->__alloc();
973 for (; __first != __last; ++__first)
975 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
976 _VSTD::move(*__first));
981 // Default constructs __n objects starting at __end_
982 // throws if construction throws
983 // Postcondition: size() == size() + __n
984 // Exception safety: strong.
985 template <class _Tp, class _Allocator>
987 vector<_Tp, _Allocator>::__append(size_type __n)
989 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
990 this->__construct_at_end(__n);
993 allocator_type& __a = this->__alloc();
994 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
995 __v.__construct_at_end(__n);
996 __swap_out_circular_buffer(__v);
1000 // Default constructs __n objects starting at __end_
1001 // throws if construction throws
1002 // Postcondition: size() == size() + __n
1003 // Exception safety: strong.
1004 template <class _Tp, class _Allocator>
1006 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
1008 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1009 this->__construct_at_end(__n, __x);
1012 allocator_type& __a = this->__alloc();
1013 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1014 __v.__construct_at_end(__n, __x);
1015 __swap_out_circular_buffer(__v);
1019 template <class _Tp, class _Allocator>
1020 vector<_Tp, _Allocator>::vector(size_type __n)
1022 #if _LIBCPP_DEBUG_LEVEL >= 2
1023 __get_db()->__insert_c(this);
1028 __construct_at_end(__n);
1032 #if _LIBCPP_STD_VER > 11
1033 template <class _Tp, class _Allocator>
1034 vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
1037 #if _LIBCPP_DEBUG_LEVEL >= 2
1038 __get_db()->__insert_c(this);
1043 __construct_at_end(__n);
1048 template <class _Tp, class _Allocator>
1049 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x)
1051 #if _LIBCPP_DEBUG_LEVEL >= 2
1052 __get_db()->__insert_c(this);
1057 __construct_at_end(__n, __x);
1061 template <class _Tp, class _Allocator>
1062 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a)
1065 #if _LIBCPP_DEBUG_LEVEL >= 2
1066 __get_db()->__insert_c(this);
1071 __construct_at_end(__n, __x);
1075 template <class _Tp, class _Allocator>
1076 template <class _InputIterator>
1077 vector<_Tp, _Allocator>::vector(_InputIterator __first,
1078 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1079 !__is_forward_iterator<_InputIterator>::value &&
1082 typename iterator_traits<_InputIterator>::reference>::value,
1083 _InputIterator>::type __last)
1085 #if _LIBCPP_DEBUG_LEVEL >= 2
1086 __get_db()->__insert_c(this);
1088 for (; __first != __last; ++__first)
1089 push_back(*__first);
1092 template <class _Tp, class _Allocator>
1093 template <class _InputIterator>
1094 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1095 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1096 !__is_forward_iterator<_InputIterator>::value &&
1099 typename iterator_traits<_InputIterator>::reference>::value>::type*)
1102 #if _LIBCPP_DEBUG_LEVEL >= 2
1103 __get_db()->__insert_c(this);
1105 for (; __first != __last; ++__first)
1106 push_back(*__first);
1109 template <class _Tp, class _Allocator>
1110 template <class _ForwardIterator>
1111 vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
1112 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1115 typename iterator_traits<_ForwardIterator>::reference>::value,
1116 _ForwardIterator>::type __last)
1118 #if _LIBCPP_DEBUG_LEVEL >= 2
1119 __get_db()->__insert_c(this);
1121 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1125 __construct_at_end(__first, __last);
1129 template <class _Tp, class _Allocator>
1130 template <class _ForwardIterator>
1131 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
1132 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1135 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
1138 #if _LIBCPP_DEBUG_LEVEL >= 2
1139 __get_db()->__insert_c(this);
1141 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1145 __construct_at_end(__first, __last);
1149 template <class _Tp, class _Allocator>
1150 vector<_Tp, _Allocator>::vector(const vector& __x)
1151 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1153 #if _LIBCPP_DEBUG_LEVEL >= 2
1154 __get_db()->__insert_c(this);
1156 size_type __n = __x.size();
1160 __construct_at_end(__x.__begin_, __x.__end_);
1164 template <class _Tp, class _Allocator>
1165 vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1168 #if _LIBCPP_DEBUG_LEVEL >= 2
1169 __get_db()->__insert_c(this);
1171 size_type __n = __x.size();
1175 __construct_at_end(__x.__begin_, __x.__end_);
1179 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1181 template <class _Tp, class _Allocator>
1182 inline _LIBCPP_INLINE_VISIBILITY
1183 vector<_Tp, _Allocator>::vector(vector&& __x)
1184 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1185 : __base(_VSTD::move(__x.__alloc()))
1187 #if _LIBCPP_DEBUG_LEVEL >= 2
1188 __get_db()->__insert_c(this);
1189 __get_db()->swap(this, &__x);
1191 this->__begin_ = __x.__begin_;
1192 this->__end_ = __x.__end_;
1193 this->__end_cap() = __x.__end_cap();
1194 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1197 template <class _Tp, class _Allocator>
1198 inline _LIBCPP_INLINE_VISIBILITY
1199 vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1202 #if _LIBCPP_DEBUG_LEVEL >= 2
1203 __get_db()->__insert_c(this);
1205 if (__a == __x.__alloc())
1207 this->__begin_ = __x.__begin_;
1208 this->__end_ = __x.__end_;
1209 this->__end_cap() = __x.__end_cap();
1210 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1211 #if _LIBCPP_DEBUG_LEVEL >= 2
1212 __get_db()->swap(this, &__x);
1217 typedef move_iterator<iterator> _Ip;
1218 assign(_Ip(__x.begin()), _Ip(__x.end()));
1222 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1224 template <class _Tp, class _Allocator>
1225 inline _LIBCPP_INLINE_VISIBILITY
1226 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1228 #if _LIBCPP_DEBUG_LEVEL >= 2
1229 __get_db()->__insert_c(this);
1231 if (__il.size() > 0)
1233 allocate(__il.size());
1234 __construct_at_end(__il.begin(), __il.end());
1238 template <class _Tp, class _Allocator>
1239 inline _LIBCPP_INLINE_VISIBILITY
1240 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1243 #if _LIBCPP_DEBUG_LEVEL >= 2
1244 __get_db()->__insert_c(this);
1246 if (__il.size() > 0)
1248 allocate(__il.size());
1249 __construct_at_end(__il.begin(), __il.end());
1253 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1255 template <class _Tp, class _Allocator>
1256 inline _LIBCPP_INLINE_VISIBILITY
1257 vector<_Tp, _Allocator>&
1258 vector<_Tp, _Allocator>::operator=(vector&& __x)
1260 __alloc_traits::propagate_on_container_move_assignment::value &&
1261 is_nothrow_move_assignable<allocator_type>::value)
1263 __move_assign(__x, integral_constant<bool,
1264 __alloc_traits::propagate_on_container_move_assignment::value>());
1268 template <class _Tp, class _Allocator>
1270 vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1272 if (__base::__alloc() != __c.__alloc())
1274 typedef move_iterator<iterator> _Ip;
1275 assign(_Ip(__c.begin()), _Ip(__c.end()));
1278 __move_assign(__c, true_type());
1281 template <class _Tp, class _Allocator>
1283 vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1284 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1287 this->__begin_ = __c.__begin_;
1288 this->__end_ = __c.__end_;
1289 this->__end_cap() = __c.__end_cap();
1290 __base::__move_assign_alloc(__c);
1291 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1292 #if _LIBCPP_DEBUG_LEVEL >= 2
1293 __get_db()->swap(this, &__c);
1297 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1299 template <class _Tp, class _Allocator>
1300 inline _LIBCPP_INLINE_VISIBILITY
1301 vector<_Tp, _Allocator>&
1302 vector<_Tp, _Allocator>::operator=(const vector& __x)
1306 __base::__copy_assign_alloc(__x);
1307 assign(__x.__begin_, __x.__end_);
1312 template <class _Tp, class _Allocator>
1313 template <class _InputIterator>
1316 __is_input_iterator <_InputIterator>::value &&
1317 !__is_forward_iterator<_InputIterator>::value &&
1320 typename iterator_traits<_InputIterator>::reference>::value,
1323 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1326 for (; __first != __last; ++__first)
1327 push_back(*__first);
1330 template <class _Tp, class _Allocator>
1331 template <class _ForwardIterator>
1334 __is_forward_iterator<_ForwardIterator>::value &&
1337 typename iterator_traits<_ForwardIterator>::reference>::value,
1340 vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1342 typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last);
1343 if (static_cast<size_type>(__new_size) <= capacity())
1345 _ForwardIterator __mid = __last;
1346 bool __growing = false;
1347 if (static_cast<size_type>(__new_size) > size())
1351 _VSTD::advance(__mid, size());
1353 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
1355 __construct_at_end(__mid, __last);
1357 this->__destruct_at_end(__m);
1362 allocate(__recommend(static_cast<size_type>(__new_size)));
1363 __construct_at_end(__first, __last);
1367 template <class _Tp, class _Allocator>
1369 vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1371 if (__n <= capacity())
1373 size_type __s = size();
1374 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
1376 __construct_at_end(__n - __s, __u);
1378 this->__destruct_at_end(this->__begin_ + __n);
1383 allocate(__recommend(static_cast<size_type>(__n)));
1384 __construct_at_end(__n, __u);
1388 template <class _Tp, class _Allocator>
1389 inline _LIBCPP_INLINE_VISIBILITY
1390 typename vector<_Tp, _Allocator>::iterator
1391 vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
1393 #if _LIBCPP_DEBUG_LEVEL >= 2
1394 return iterator(this, __p);
1396 return iterator(__p);
1400 template <class _Tp, class _Allocator>
1401 inline _LIBCPP_INLINE_VISIBILITY
1402 typename vector<_Tp, _Allocator>::const_iterator
1403 vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
1405 #if _LIBCPP_DEBUG_LEVEL >= 2
1406 return const_iterator(this, __p);
1408 return const_iterator(__p);
1412 template <class _Tp, class _Allocator>
1413 inline _LIBCPP_INLINE_VISIBILITY
1414 typename vector<_Tp, _Allocator>::iterator
1415 vector<_Tp, _Allocator>::begin() _NOEXCEPT
1417 return __make_iter(this->__begin_);
1420 template <class _Tp, class _Allocator>
1421 inline _LIBCPP_INLINE_VISIBILITY
1422 typename vector<_Tp, _Allocator>::const_iterator
1423 vector<_Tp, _Allocator>::begin() const _NOEXCEPT
1425 return __make_iter(this->__begin_);
1428 template <class _Tp, class _Allocator>
1429 inline _LIBCPP_INLINE_VISIBILITY
1430 typename vector<_Tp, _Allocator>::iterator
1431 vector<_Tp, _Allocator>::end() _NOEXCEPT
1433 return __make_iter(this->__end_);
1436 template <class _Tp, class _Allocator>
1437 inline _LIBCPP_INLINE_VISIBILITY
1438 typename vector<_Tp, _Allocator>::const_iterator
1439 vector<_Tp, _Allocator>::end() const _NOEXCEPT
1441 return __make_iter(this->__end_);
1444 template <class _Tp, class _Allocator>
1445 inline _LIBCPP_INLINE_VISIBILITY
1446 typename vector<_Tp, _Allocator>::reference
1447 vector<_Tp, _Allocator>::operator[](size_type __n)
1449 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1450 return this->__begin_[__n];
1453 template <class _Tp, class _Allocator>
1454 inline _LIBCPP_INLINE_VISIBILITY
1455 typename vector<_Tp, _Allocator>::const_reference
1456 vector<_Tp, _Allocator>::operator[](size_type __n) const
1458 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1459 return this->__begin_[__n];
1462 template <class _Tp, class _Allocator>
1463 typename vector<_Tp, _Allocator>::reference
1464 vector<_Tp, _Allocator>::at(size_type __n)
1467 this->__throw_out_of_range();
1468 return this->__begin_[__n];
1471 template <class _Tp, class _Allocator>
1472 typename vector<_Tp, _Allocator>::const_reference
1473 vector<_Tp, _Allocator>::at(size_type __n) const
1476 this->__throw_out_of_range();
1477 return this->__begin_[__n];
1480 template <class _Tp, class _Allocator>
1482 vector<_Tp, _Allocator>::reserve(size_type __n)
1484 if (__n > capacity())
1486 allocator_type& __a = this->__alloc();
1487 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1488 __swap_out_circular_buffer(__v);
1492 template <class _Tp, class _Allocator>
1494 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1496 if (capacity() > size())
1498 #ifndef _LIBCPP_NO_EXCEPTIONS
1501 #endif // _LIBCPP_NO_EXCEPTIONS
1502 allocator_type& __a = this->__alloc();
1503 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1504 __swap_out_circular_buffer(__v);
1505 #ifndef _LIBCPP_NO_EXCEPTIONS
1510 #endif // _LIBCPP_NO_EXCEPTIONS
1514 template <class _Tp, class _Allocator>
1515 template <class _Up>
1517 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1518 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1520 vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1523 allocator_type& __a = this->__alloc();
1524 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1525 // __v.push_back(_VSTD::forward<_Up>(__x));
1526 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
1528 __swap_out_circular_buffer(__v);
1531 template <class _Tp, class _Allocator>
1532 inline _LIBCPP_INLINE_VISIBILITY
1534 vector<_Tp, _Allocator>::push_back(const_reference __x)
1536 if (this->__end_ != this->__end_cap())
1538 __alloc_traits::construct(this->__alloc(),
1539 _VSTD::__to_raw_pointer(this->__end_), __x);
1543 __push_back_slow_path(__x);
1546 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1548 template <class _Tp, class _Allocator>
1549 inline _LIBCPP_INLINE_VISIBILITY
1551 vector<_Tp, _Allocator>::push_back(value_type&& __x)
1553 if (this->__end_ < this->__end_cap())
1555 __alloc_traits::construct(this->__alloc(),
1556 _VSTD::__to_raw_pointer(this->__end_),
1561 __push_back_slow_path(_VSTD::move(__x));
1564 #ifndef _LIBCPP_HAS_NO_VARIADICS
1566 template <class _Tp, class _Allocator>
1567 template <class... _Args>
1569 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1571 allocator_type& __a = this->__alloc();
1572 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1573 // __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1574 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
1576 __swap_out_circular_buffer(__v);
1579 template <class _Tp, class _Allocator>
1580 template <class... _Args>
1581 inline _LIBCPP_INLINE_VISIBILITY
1583 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1585 if (this->__end_ < this->__end_cap())
1587 __alloc_traits::construct(this->__alloc(),
1588 _VSTD::__to_raw_pointer(this->__end_),
1589 _VSTD::forward<_Args>(__args)...);
1593 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
1596 #endif // _LIBCPP_HAS_NO_VARIADICS
1597 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1599 template <class _Tp, class _Allocator>
1600 inline _LIBCPP_INLINE_VISIBILITY
1602 vector<_Tp, _Allocator>::pop_back()
1604 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1605 this->__destruct_at_end(this->__end_ - 1);
1608 template <class _Tp, class _Allocator>
1609 inline _LIBCPP_INLINE_VISIBILITY
1610 typename vector<_Tp, _Allocator>::iterator
1611 vector<_Tp, _Allocator>::erase(const_iterator __position)
1613 #if _LIBCPP_DEBUG_LEVEL >= 2
1614 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1615 "vector::erase(iterator) called with an iterator not"
1616 " referring to this vector");
1618 _LIBCPP_ASSERT(__position != end(),
1619 "vector::erase(iterator) called with a non-dereferenceable iterator");
1620 difference_type __ps = __position - cbegin();
1621 pointer __p = this->__begin_ + __ps;
1622 iterator __r = __make_iter(__p);
1623 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1627 template <class _Tp, class _Allocator>
1628 typename vector<_Tp, _Allocator>::iterator
1629 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1631 #if _LIBCPP_DEBUG_LEVEL >= 2
1632 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1633 "vector::erase(iterator, iterator) called with an iterator not"
1634 " referring to this vector");
1636 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1637 pointer __p = this->__begin_ + (__first - begin());
1638 iterator __r = __make_iter(__p);
1639 if (__first != __last)
1640 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1644 template <class _Tp, class _Allocator>
1646 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1648 pointer __old_last = this->__end_;
1649 difference_type __n = __old_last - __to;
1650 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1651 __alloc_traits::construct(this->__alloc(),
1652 _VSTD::__to_raw_pointer(this->__end_),
1654 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1657 template <class _Tp, class _Allocator>
1658 typename vector<_Tp, _Allocator>::iterator
1659 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1661 #if _LIBCPP_DEBUG_LEVEL >= 2
1662 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1663 "vector::insert(iterator, x) called with an iterator not"
1664 " referring to this vector");
1666 pointer __p = this->__begin_ + (__position - begin());
1667 if (this->__end_ < this->__end_cap())
1669 if (__p == this->__end_)
1671 __alloc_traits::construct(this->__alloc(),
1672 _VSTD::__to_raw_pointer(this->__end_), __x);
1677 __move_range(__p, this->__end_, __p + 1);
1678 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1679 if (__p <= __xr && __xr < this->__end_)
1686 allocator_type& __a = this->__alloc();
1687 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1689 __p = __swap_out_circular_buffer(__v, __p);
1691 return __make_iter(__p);
1694 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1696 template <class _Tp, class _Allocator>
1697 typename vector<_Tp, _Allocator>::iterator
1698 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1700 #if _LIBCPP_DEBUG_LEVEL >= 2
1701 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1702 "vector::insert(iterator, x) called with an iterator not"
1703 " referring to this vector");
1705 pointer __p = this->__begin_ + (__position - begin());
1706 if (this->__end_ < this->__end_cap())
1708 if (__p == this->__end_)
1710 __alloc_traits::construct(this->__alloc(),
1711 _VSTD::__to_raw_pointer(this->__end_),
1717 __move_range(__p, this->__end_, __p + 1);
1718 *__p = _VSTD::move(__x);
1723 allocator_type& __a = this->__alloc();
1724 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1725 __v.push_back(_VSTD::move(__x));
1726 __p = __swap_out_circular_buffer(__v, __p);
1728 return __make_iter(__p);
1731 #ifndef _LIBCPP_HAS_NO_VARIADICS
1733 template <class _Tp, class _Allocator>
1734 template <class... _Args>
1735 typename vector<_Tp, _Allocator>::iterator
1736 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1738 #if _LIBCPP_DEBUG_LEVEL >= 2
1739 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1740 "vector::emplace(iterator, x) called with an iterator not"
1741 " referring to this vector");
1743 pointer __p = this->__begin_ + (__position - begin());
1744 if (this->__end_ < this->__end_cap())
1746 if (__p == this->__end_)
1748 __alloc_traits::construct(this->__alloc(),
1749 _VSTD::__to_raw_pointer(this->__end_),
1750 _VSTD::forward<_Args>(__args)...);
1755 value_type __tmp(_VSTD::forward<_Args>(__args)...);
1756 __move_range(__p, this->__end_, __p + 1);
1757 *__p = _VSTD::move(__tmp);
1762 allocator_type& __a = this->__alloc();
1763 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1764 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1765 __p = __swap_out_circular_buffer(__v, __p);
1767 return __make_iter(__p);
1770 #endif // _LIBCPP_HAS_NO_VARIADICS
1771 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1773 template <class _Tp, class _Allocator>
1774 typename vector<_Tp, _Allocator>::iterator
1775 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1777 #if _LIBCPP_DEBUG_LEVEL >= 2
1778 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1779 "vector::insert(iterator, n, x) called with an iterator not"
1780 " referring to this vector");
1782 pointer __p = this->__begin_ + (__position - begin());
1785 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1787 size_type __old_n = __n;
1788 pointer __old_last = this->__end_;
1789 if (__n > static_cast<size_type>(this->__end_ - __p))
1791 size_type __cx = __n - (this->__end_ - __p);
1792 __construct_at_end(__cx, __x);
1797 __move_range(__p, __old_last, __p + __old_n);
1798 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1799 if (__p <= __xr && __xr < this->__end_)
1801 _VSTD::fill_n(__p, __n, *__xr);
1806 allocator_type& __a = this->__alloc();
1807 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1808 __v.__construct_at_end(__n, __x);
1809 __p = __swap_out_circular_buffer(__v, __p);
1812 return __make_iter(__p);
1815 template <class _Tp, class _Allocator>
1816 template <class _InputIterator>
1819 __is_input_iterator <_InputIterator>::value &&
1820 !__is_forward_iterator<_InputIterator>::value &&
1823 typename iterator_traits<_InputIterator>::reference>::value,
1824 typename vector<_Tp, _Allocator>::iterator
1826 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1828 #if _LIBCPP_DEBUG_LEVEL >= 2
1829 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1830 "vector::insert(iterator, range) called with an iterator not"
1831 " referring to this vector");
1833 difference_type __off = __position - begin();
1834 pointer __p = this->__begin_ + __off;
1835 allocator_type& __a = this->__alloc();
1836 pointer __old_last = this->__end_;
1837 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1839 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
1843 __split_buffer<value_type, allocator_type&> __v(__a);
1844 if (__first != __last)
1846 #ifndef _LIBCPP_NO_EXCEPTIONS
1849 #endif // _LIBCPP_NO_EXCEPTIONS
1850 __v.__construct_at_end(__first, __last);
1851 difference_type __old_size = __old_last - this->__begin_;
1852 difference_type __old_p = __p - this->__begin_;
1853 reserve(__recommend(size() + __v.size()));
1854 __p = this->__begin_ + __old_p;
1855 __old_last = this->__begin_ + __old_size;
1856 #ifndef _LIBCPP_NO_EXCEPTIONS
1860 erase(__make_iter(__old_last), end());
1863 #endif // _LIBCPP_NO_EXCEPTIONS
1865 __p = _VSTD::rotate(__p, __old_last, this->__end_);
1866 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1867 make_move_iterator(__v.end()));
1868 return begin() + __off;
1871 template <class _Tp, class _Allocator>
1872 template <class _ForwardIterator>
1875 __is_forward_iterator<_ForwardIterator>::value &&
1878 typename iterator_traits<_ForwardIterator>::reference>::value,
1879 typename vector<_Tp, _Allocator>::iterator
1881 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1883 #if _LIBCPP_DEBUG_LEVEL >= 2
1884 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1885 "vector::insert(iterator, range) called with an iterator not"
1886 " referring to this vector");
1888 pointer __p = this->__begin_ + (__position - begin());
1889 difference_type __n = _VSTD::distance(__first, __last);
1892 if (__n <= this->__end_cap() - this->__end_)
1894 size_type __old_n = __n;
1895 pointer __old_last = this->__end_;
1896 _ForwardIterator __m = __last;
1897 difference_type __dx = this->__end_ - __p;
1901 _VSTD::advance(__m, this->__end_ - __p);
1902 __construct_at_end(__m, __last);
1907 __move_range(__p, __old_last, __p + __old_n);
1908 _VSTD::copy(__first, __m, __p);
1913 allocator_type& __a = this->__alloc();
1914 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1915 __v.__construct_at_end(__first, __last);
1916 __p = __swap_out_circular_buffer(__v, __p);
1919 return __make_iter(__p);
1922 template <class _Tp, class _Allocator>
1924 vector<_Tp, _Allocator>::resize(size_type __sz)
1926 size_type __cs = size();
1928 this->__append(__sz - __cs);
1929 else if (__cs > __sz)
1930 this->__destruct_at_end(this->__begin_ + __sz);
1933 template <class _Tp, class _Allocator>
1935 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
1937 size_type __cs = size();
1939 this->__append(__sz - __cs, __x);
1940 else if (__cs > __sz)
1941 this->__destruct_at_end(this->__begin_ + __sz);
1944 template <class _Tp, class _Allocator>
1946 vector<_Tp, _Allocator>::swap(vector& __x)
1947 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1948 __is_nothrow_swappable<allocator_type>::value)
1950 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
1951 this->__alloc() == __x.__alloc(),
1952 "vector::swap: Either propagate_on_container_swap must be true"
1953 " or the allocators must compare equal");
1954 _VSTD::swap(this->__begin_, __x.__begin_);
1955 _VSTD::swap(this->__end_, __x.__end_);
1956 _VSTD::swap(this->__end_cap(), __x.__end_cap());
1957 __base::__swap_alloc(this->__alloc(), __x.__alloc());
1958 #if _LIBCPP_DEBUG_LEVEL >= 2
1959 __get_db()->swap(this, &__x);
1960 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1963 template <class _Tp, class _Allocator>
1965 vector<_Tp, _Allocator>::__invariants() const
1967 if (this->__begin_ == nullptr)
1969 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
1974 if (this->__begin_ > this->__end_)
1976 if (this->__begin_ == this->__end_cap())
1978 if (this->__end_ > this->__end_cap())
1984 #if _LIBCPP_DEBUG_LEVEL >= 2
1986 template <class _Tp, class _Allocator>
1988 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
1990 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
1993 template <class _Tp, class _Allocator>
1995 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
1997 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
2000 template <class _Tp, class _Allocator>
2002 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2004 const_pointer __p = __i->base() + __n;
2005 return this->__begin_ <= __p && __p <= this->__end_;
2008 template <class _Tp, class _Allocator>
2010 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2012 const_pointer __p = __i->base() + __n;
2013 return this->__begin_ <= __p && __p < this->__end_;
2016 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2018 template <class _Tp, class _Allocator>
2019 inline _LIBCPP_INLINE_VISIBILITY
2021 vector<_Tp, _Allocator>::__invalidate_all_iterators()
2023 #if _LIBCPP_DEBUG_LEVEL >= 2
2024 __get_db()->__invalidate_all(this);
2025 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2030 template <class _Allocator> class vector<bool, _Allocator>;
2032 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2034 template <class _Allocator>
2035 struct __has_storage_type<vector<bool, _Allocator> >
2037 static const bool value = true;
2040 template <class _Allocator>
2041 class _LIBCPP_TYPE_VIS_ONLY vector<bool, _Allocator>
2042 : private __vector_base_common<true>
2045 typedef vector __self;
2046 typedef bool value_type;
2047 typedef _Allocator allocator_type;
2048 typedef allocator_traits<allocator_type> __alloc_traits;
2049 typedef typename __alloc_traits::size_type size_type;
2050 typedef typename __alloc_traits::difference_type difference_type;
2051 typedef size_type __storage_type;
2052 typedef __bit_iterator<vector, false> pointer;
2053 typedef __bit_iterator<vector, true> const_pointer;
2054 typedef pointer iterator;
2055 typedef const_pointer const_iterator;
2056 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2057 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
2060 typedef typename __alloc_traits::template
2061 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
2062 rebind_alloc<__storage_type>
2064 rebind_alloc<__storage_type>::other
2066 __storage_allocator;
2067 typedef allocator_traits<__storage_allocator> __storage_traits;
2068 typedef typename __storage_traits::pointer __storage_pointer;
2069 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2071 __storage_pointer __begin_;
2073 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2075 typedef __bit_reference<vector> reference;
2076 typedef __bit_const_reference<vector> const_reference;
2078 _LIBCPP_INLINE_VISIBILITY
2079 size_type& __cap() _NOEXCEPT
2080 {return __cap_alloc_.first();}
2081 _LIBCPP_INLINE_VISIBILITY
2082 const size_type& __cap() const _NOEXCEPT
2083 {return __cap_alloc_.first();}
2084 _LIBCPP_INLINE_VISIBILITY
2085 __storage_allocator& __alloc() _NOEXCEPT
2086 {return __cap_alloc_.second();}
2087 _LIBCPP_INLINE_VISIBILITY
2088 const __storage_allocator& __alloc() const _NOEXCEPT
2089 {return __cap_alloc_.second();}
2091 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2093 _LIBCPP_INLINE_VISIBILITY
2094 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2095 {return __n * __bits_per_word;}
2096 _LIBCPP_INLINE_VISIBILITY
2097 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2098 {return (__n - 1) / __bits_per_word + 1;}
2101 _LIBCPP_INLINE_VISIBILITY
2103 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2104 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a);
2106 explicit vector(size_type __n);
2107 #if _LIBCPP_STD_VER > 11
2108 explicit vector(size_type __n, const allocator_type& __a);
2110 vector(size_type __n, const value_type& __v);
2111 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2112 template <class _InputIterator>
2113 vector(_InputIterator __first, _InputIterator __last,
2114 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2115 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2116 template <class _InputIterator>
2117 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2118 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2119 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2120 template <class _ForwardIterator>
2121 vector(_ForwardIterator __first, _ForwardIterator __last,
2122 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2123 template <class _ForwardIterator>
2124 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2125 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2127 vector(const vector& __v);
2128 vector(const vector& __v, const allocator_type& __a);
2129 vector& operator=(const vector& __v);
2130 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2131 vector(initializer_list<value_type> __il);
2132 vector(initializer_list<value_type> __il, const allocator_type& __a);
2133 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2135 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2136 _LIBCPP_INLINE_VISIBILITY
2137 vector(vector&& __v)
2138 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2139 vector(vector&& __v, const allocator_type& __a);
2140 _LIBCPP_INLINE_VISIBILITY
2141 vector& operator=(vector&& __v)
2143 __alloc_traits::propagate_on_container_move_assignment::value &&
2144 is_nothrow_move_assignable<allocator_type>::value);
2145 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2146 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2147 _LIBCPP_INLINE_VISIBILITY
2148 vector& operator=(initializer_list<value_type> __il)
2149 {assign(__il.begin(), __il.end()); return *this;}
2150 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2152 template <class _InputIterator>
2155 __is_input_iterator<_InputIterator>::value &&
2156 !__is_forward_iterator<_InputIterator>::value,
2159 assign(_InputIterator __first, _InputIterator __last);
2160 template <class _ForwardIterator>
2163 __is_forward_iterator<_ForwardIterator>::value,
2166 assign(_ForwardIterator __first, _ForwardIterator __last);
2168 void assign(size_type __n, const value_type& __x);
2169 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2170 _LIBCPP_INLINE_VISIBILITY
2171 void assign(initializer_list<value_type> __il)
2172 {assign(__il.begin(), __il.end());}
2173 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2175 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2176 {return allocator_type(this->__alloc());}
2178 size_type max_size() const _NOEXCEPT;
2179 _LIBCPP_INLINE_VISIBILITY
2180 size_type capacity() const _NOEXCEPT
2181 {return __internal_cap_to_external(__cap());}
2182 _LIBCPP_INLINE_VISIBILITY
2183 size_type size() const _NOEXCEPT
2185 _LIBCPP_INLINE_VISIBILITY
2186 bool empty() const _NOEXCEPT
2187 {return __size_ == 0;}
2188 void reserve(size_type __n);
2189 void shrink_to_fit() _NOEXCEPT;
2191 _LIBCPP_INLINE_VISIBILITY
2192 iterator begin() _NOEXCEPT
2193 {return __make_iter(0);}
2194 _LIBCPP_INLINE_VISIBILITY
2195 const_iterator begin() const _NOEXCEPT
2196 {return __make_iter(0);}
2197 _LIBCPP_INLINE_VISIBILITY
2198 iterator end() _NOEXCEPT
2199 {return __make_iter(__size_);}
2200 _LIBCPP_INLINE_VISIBILITY
2201 const_iterator end() const _NOEXCEPT
2202 {return __make_iter(__size_);}
2204 _LIBCPP_INLINE_VISIBILITY
2205 reverse_iterator rbegin() _NOEXCEPT
2206 {return reverse_iterator(end());}
2207 _LIBCPP_INLINE_VISIBILITY
2208 const_reverse_iterator rbegin() const _NOEXCEPT
2209 {return const_reverse_iterator(end());}
2210 _LIBCPP_INLINE_VISIBILITY
2211 reverse_iterator rend() _NOEXCEPT
2212 {return reverse_iterator(begin());}
2213 _LIBCPP_INLINE_VISIBILITY
2214 const_reverse_iterator rend() const _NOEXCEPT
2215 {return const_reverse_iterator(begin());}
2217 _LIBCPP_INLINE_VISIBILITY
2218 const_iterator cbegin() const _NOEXCEPT
2219 {return __make_iter(0);}
2220 _LIBCPP_INLINE_VISIBILITY
2221 const_iterator cend() const _NOEXCEPT
2222 {return __make_iter(__size_);}
2223 _LIBCPP_INLINE_VISIBILITY
2224 const_reverse_iterator crbegin() const _NOEXCEPT
2226 _LIBCPP_INLINE_VISIBILITY
2227 const_reverse_iterator crend() const _NOEXCEPT
2230 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2231 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2232 reference at(size_type __n);
2233 const_reference at(size_type __n) const;
2235 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2236 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2237 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2238 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2240 void push_back(const value_type& __x);
2241 #if _LIBCPP_STD_VER > 11
2242 template <class... _Args>
2243 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
2244 { push_back ( value_type ( _VSTD::forward<_Args>(__args)... )); }
2247 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2249 #if _LIBCPP_STD_VER > 11
2250 template <class... _Args>
2251 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
2252 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
2255 iterator insert(const_iterator __position, const value_type& __x);
2256 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2257 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2258 template <class _InputIterator>
2261 __is_input_iterator <_InputIterator>::value &&
2262 !__is_forward_iterator<_InputIterator>::value,
2265 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2266 template <class _ForwardIterator>
2269 __is_forward_iterator<_ForwardIterator>::value,
2272 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2273 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2274 _LIBCPP_INLINE_VISIBILITY
2275 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2276 {return insert(__position, __il.begin(), __il.end());}
2277 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2279 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2280 iterator erase(const_iterator __first, const_iterator __last);
2282 _LIBCPP_INLINE_VISIBILITY
2283 void clear() _NOEXCEPT {__size_ = 0;}
2286 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2287 __is_nothrow_swappable<allocator_type>::value);
2289 void resize(size_type __sz, value_type __x = false);
2290 void flip() _NOEXCEPT;
2292 bool __invariants() const;
2295 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2296 void allocate(size_type __n);
2297 void deallocate() _NOEXCEPT;
2298 _LIBCPP_INLINE_VISIBILITY
2299 static size_type __align_it(size_type __new_size) _NOEXCEPT
2300 {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);};
2301 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2302 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2303 template <class _ForwardIterator>
2306 __is_forward_iterator<_ForwardIterator>::value,
2309 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2310 void __append(size_type __n, const_reference __x);
2311 _LIBCPP_INLINE_VISIBILITY
2312 reference __make_ref(size_type __pos) _NOEXCEPT
2313 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2314 _LIBCPP_INLINE_VISIBILITY
2315 const_reference __make_ref(size_type __pos) const _NOEXCEPT
2316 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2317 _LIBCPP_INLINE_VISIBILITY
2318 iterator __make_iter(size_type __pos) _NOEXCEPT
2319 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2320 _LIBCPP_INLINE_VISIBILITY
2321 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2322 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2323 _LIBCPP_INLINE_VISIBILITY
2324 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2325 {return begin() + (__p - cbegin());}
2327 _LIBCPP_INLINE_VISIBILITY
2328 void __copy_assign_alloc(const vector& __v)
2329 {__copy_assign_alloc(__v, integral_constant<bool,
2330 __storage_traits::propagate_on_container_copy_assignment::value>());}
2331 _LIBCPP_INLINE_VISIBILITY
2332 void __copy_assign_alloc(const vector& __c, true_type)
2334 if (__alloc() != __c.__alloc())
2336 __alloc() = __c.__alloc();
2339 _LIBCPP_INLINE_VISIBILITY
2340 void __copy_assign_alloc(const vector&, false_type)
2343 void __move_assign(vector& __c, false_type);
2344 void __move_assign(vector& __c, true_type)
2345 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2346 _LIBCPP_INLINE_VISIBILITY
2347 void __move_assign_alloc(vector& __c)
2349 !__storage_traits::propagate_on_container_move_assignment::value ||
2350 is_nothrow_move_assignable<allocator_type>::value)
2351 {__move_assign_alloc(__c, integral_constant<bool,
2352 __storage_traits::propagate_on_container_move_assignment::value>());}
2353 _LIBCPP_INLINE_VISIBILITY
2354 void __move_assign_alloc(vector& __c, true_type)
2355 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2357 __alloc() = _VSTD::move(__c.__alloc());
2360 _LIBCPP_INLINE_VISIBILITY
2361 void __move_assign_alloc(vector&, false_type)
2365 _LIBCPP_INLINE_VISIBILITY
2366 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y)
2368 !__storage_traits::propagate_on_container_swap::value ||
2369 __is_nothrow_swappable<allocator_type>::value)
2370 {__swap_alloc(__x, __y, integral_constant<bool,
2371 __storage_traits::propagate_on_container_swap::value>());}
2373 _LIBCPP_INLINE_VISIBILITY
2374 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type)
2375 _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
2380 _LIBCPP_INLINE_VISIBILITY
2381 static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type)
2385 size_t __hash_code() const _NOEXCEPT;
2387 friend class __bit_reference<vector>;
2388 friend class __bit_const_reference<vector>;
2389 friend class __bit_iterator<vector, false>;
2390 friend class __bit_iterator<vector, true>;
2391 friend struct __bit_array<vector>;
2392 friend struct _LIBCPP_TYPE_VIS_ONLY hash<vector>;
2395 template <class _Allocator>
2396 inline _LIBCPP_INLINE_VISIBILITY
2398 vector<bool, _Allocator>::__invalidate_all_iterators()
2402 // Allocate space for __n objects
2403 // throws length_error if __n > max_size()
2404 // throws (probably bad_alloc) if memory run out
2405 // Precondition: __begin_ == __end_ == __cap() == 0
2406 // Precondition: __n > 0
2407 // Postcondition: capacity() == __n
2408 // Postcondition: size() == 0
2409 template <class _Allocator>
2411 vector<bool, _Allocator>::allocate(size_type __n)
2413 if (__n > max_size())
2414 this->__throw_length_error();
2415 __n = __external_cap_to_internal(__n);
2416 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2418 this->__cap() = __n;
2421 template <class _Allocator>
2423 vector<bool, _Allocator>::deallocate() _NOEXCEPT
2425 if (this->__begin_ != nullptr)
2427 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2428 __invalidate_all_iterators();
2429 this->__begin_ = nullptr;
2430 this->__size_ = this->__cap() = 0;
2434 template <class _Allocator>
2435 typename vector<bool, _Allocator>::size_type
2436 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2438 size_type __amax = __storage_traits::max_size(__alloc());
2439 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2440 if (__nmax / __bits_per_word <= __amax)
2442 return __internal_cap_to_external(__amax);
2445 // Precondition: __new_size > capacity()
2446 template <class _Allocator>
2447 inline _LIBCPP_INLINE_VISIBILITY
2448 typename vector<bool, _Allocator>::size_type
2449 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2451 const size_type __ms = max_size();
2452 if (__new_size > __ms)
2453 this->__throw_length_error();
2454 const size_type __cap = capacity();
2455 if (__cap >= __ms / 2)
2457 return _VSTD::max(2*__cap, __align_it(__new_size));
2460 // Default constructs __n objects starting at __end_
2461 // Precondition: __n > 0
2462 // Precondition: size() + __n <= capacity()
2463 // Postcondition: size() == size() + __n
2464 template <class _Allocator>
2465 inline _LIBCPP_INLINE_VISIBILITY
2467 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2469 size_type __old_size = this->__size_;
2470 this->__size_ += __n;
2471 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2474 template <class _Allocator>
2475 template <class _ForwardIterator>
2478 __is_forward_iterator<_ForwardIterator>::value,
2481 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2483 size_type __old_size = this->__size_;
2484 this->__size_ += _VSTD::distance(__first, __last);
2485 _VSTD::copy(__first, __last, __make_iter(__old_size));
2488 template <class _Allocator>
2489 inline _LIBCPP_INLINE_VISIBILITY
2490 vector<bool, _Allocator>::vector()
2491 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2492 : __begin_(nullptr),
2498 template <class _Allocator>
2499 inline _LIBCPP_INLINE_VISIBILITY
2500 vector<bool, _Allocator>::vector(const allocator_type& __a)
2501 : __begin_(nullptr),
2503 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2507 template <class _Allocator>
2508 vector<bool, _Allocator>::vector(size_type __n)
2509 : __begin_(nullptr),
2516 __construct_at_end(__n, false);
2520 #if _LIBCPP_STD_VER > 11
2521 template <class _Allocator>
2522 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2523 : __begin_(nullptr),
2525 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2530 __construct_at_end(__n, false);
2535 template <class _Allocator>
2536 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2537 : __begin_(nullptr),
2544 __construct_at_end(__n, __x);
2548 template <class _Allocator>
2549 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2550 : __begin_(nullptr),
2552 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2557 __construct_at_end(__n, __x);
2561 template <class _Allocator>
2562 template <class _InputIterator>
2563 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2564 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2565 !__is_forward_iterator<_InputIterator>::value>::type*)
2566 : __begin_(nullptr),
2570 #ifndef _LIBCPP_NO_EXCEPTIONS
2573 #endif // _LIBCPP_NO_EXCEPTIONS
2574 for (; __first != __last; ++__first)
2575 push_back(*__first);
2576 #ifndef _LIBCPP_NO_EXCEPTIONS
2580 if (__begin_ != nullptr)
2581 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2582 __invalidate_all_iterators();
2585 #endif // _LIBCPP_NO_EXCEPTIONS
2588 template <class _Allocator>
2589 template <class _InputIterator>
2590 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2591 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2592 !__is_forward_iterator<_InputIterator>::value>::type*)
2593 : __begin_(nullptr),
2595 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2597 #ifndef _LIBCPP_NO_EXCEPTIONS
2600 #endif // _LIBCPP_NO_EXCEPTIONS
2601 for (; __first != __last; ++__first)
2602 push_back(*__first);
2603 #ifndef _LIBCPP_NO_EXCEPTIONS
2607 if (__begin_ != nullptr)
2608 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2609 __invalidate_all_iterators();
2612 #endif // _LIBCPP_NO_EXCEPTIONS
2615 template <class _Allocator>
2616 template <class _ForwardIterator>
2617 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2618 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2619 : __begin_(nullptr),
2623 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2627 __construct_at_end(__first, __last);
2631 template <class _Allocator>
2632 template <class _ForwardIterator>
2633 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2634 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2635 : __begin_(nullptr),
2637 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2639 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2643 __construct_at_end(__first, __last);
2647 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2649 template <class _Allocator>
2650 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2651 : __begin_(nullptr),
2655 size_type __n = static_cast<size_type>(__il.size());
2659 __construct_at_end(__il.begin(), __il.end());
2663 template <class _Allocator>
2664 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2665 : __begin_(nullptr),
2667 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2669 size_type __n = static_cast<size_type>(__il.size());
2673 __construct_at_end(__il.begin(), __il.end());
2677 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2679 template <class _Allocator>
2680 vector<bool, _Allocator>::~vector()
2682 if (__begin_ != nullptr)
2683 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2684 __invalidate_all_iterators();
2687 template <class _Allocator>
2688 vector<bool, _Allocator>::vector(const vector& __v)
2689 : __begin_(nullptr),
2691 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2695 allocate(__v.size());
2696 __construct_at_end(__v.begin(), __v.end());
2700 template <class _Allocator>
2701 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2702 : __begin_(nullptr),
2704 __cap_alloc_(0, __a)
2708 allocate(__v.size());
2709 __construct_at_end(__v.begin(), __v.end());
2713 template <class _Allocator>
2714 vector<bool, _Allocator>&
2715 vector<bool, _Allocator>::operator=(const vector& __v)
2719 __copy_assign_alloc(__v);
2722 if (__v.__size_ > capacity())
2725 allocate(__v.__size_);
2727 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2729 __size_ = __v.__size_;
2734 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2736 template <class _Allocator>
2737 inline _LIBCPP_INLINE_VISIBILITY
2738 vector<bool, _Allocator>::vector(vector&& __v)
2739 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2740 : __begin_(__v.__begin_),
2741 __size_(__v.__size_),
2742 __cap_alloc_(__v.__cap_alloc_)
2744 __v.__begin_ = nullptr;
2749 template <class _Allocator>
2750 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2751 : __begin_(nullptr),
2753 __cap_alloc_(0, __a)
2755 if (__a == allocator_type(__v.__alloc()))
2757 this->__begin_ = __v.__begin_;
2758 this->__size_ = __v.__size_;
2759 this->__cap() = __v.__cap();
2760 __v.__begin_ = nullptr;
2761 __v.__cap() = __v.__size_ = 0;
2763 else if (__v.size() > 0)
2765 allocate(__v.size());
2766 __construct_at_end(__v.begin(), __v.end());
2770 template <class _Allocator>
2771 inline _LIBCPP_INLINE_VISIBILITY
2772 vector<bool, _Allocator>&
2773 vector<bool, _Allocator>::operator=(vector&& __v)
2775 __alloc_traits::propagate_on_container_move_assignment::value &&
2776 is_nothrow_move_assignable<allocator_type>::value)
2778 __move_assign(__v, integral_constant<bool,
2779 __storage_traits::propagate_on_container_move_assignment::value>());
2783 template <class _Allocator>
2785 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2787 if (__alloc() != __c.__alloc())
2788 assign(__c.begin(), __c.end());
2790 __move_assign(__c, true_type());
2793 template <class _Allocator>
2795 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2796 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2799 this->__begin_ = __c.__begin_;
2800 this->__size_ = __c.__size_;
2801 this->__cap() = __c.__cap();
2802 __move_assign_alloc(__c);
2803 __c.__begin_ = nullptr;
2804 __c.__cap() = __c.__size_ = 0;
2807 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2809 template <class _Allocator>
2811 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2816 size_type __c = capacity();
2821 vector __v(__alloc());
2822 __v.reserve(__recommend(__n));
2826 _VSTD::fill_n(begin(), __n, __x);
2830 template <class _Allocator>
2831 template <class _InputIterator>
2834 __is_input_iterator<_InputIterator>::value &&
2835 !__is_forward_iterator<_InputIterator>::value,
2838 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2841 for (; __first != __last; ++__first)
2842 push_back(*__first);
2845 template <class _Allocator>
2846 template <class _ForwardIterator>
2849 __is_forward_iterator<_ForwardIterator>::value,
2852 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2855 difference_type __n = _VSTD::distance(__first, __last);
2858 if (__n > capacity())
2863 __construct_at_end(__first, __last);
2867 template <class _Allocator>
2869 vector<bool, _Allocator>::reserve(size_type __n)
2871 if (__n > capacity())
2873 vector __v(this->__alloc());
2875 __v.__construct_at_end(this->begin(), this->end());
2877 __invalidate_all_iterators();
2881 template <class _Allocator>
2883 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
2885 if (__external_cap_to_internal(size()) > __cap())
2887 #ifndef _LIBCPP_NO_EXCEPTIONS
2890 #endif // _LIBCPP_NO_EXCEPTIONS
2891 vector(*this, allocator_type(__alloc())).swap(*this);
2892 #ifndef _LIBCPP_NO_EXCEPTIONS
2897 #endif // _LIBCPP_NO_EXCEPTIONS
2901 template <class _Allocator>
2902 typename vector<bool, _Allocator>::reference
2903 vector<bool, _Allocator>::at(size_type __n)
2906 this->__throw_out_of_range();
2907 return (*this)[__n];
2910 template <class _Allocator>
2911 typename vector<bool, _Allocator>::const_reference
2912 vector<bool, _Allocator>::at(size_type __n) const
2915 this->__throw_out_of_range();
2916 return (*this)[__n];
2919 template <class _Allocator>
2921 vector<bool, _Allocator>::push_back(const value_type& __x)
2923 if (this->__size_ == this->capacity())
2924 reserve(__recommend(this->__size_ + 1));
2929 template <class _Allocator>
2930 typename vector<bool, _Allocator>::iterator
2931 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
2934 if (size() < capacity())
2936 const_iterator __old_end = end();
2938 _VSTD::copy_backward(__position, __old_end, end());
2939 __r = __const_iterator_cast(__position);
2943 vector __v(__alloc());
2944 __v.reserve(__recommend(__size_ + 1));
2945 __v.__size_ = __size_ + 1;
2946 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2947 _VSTD::copy_backward(__position, cend(), __v.end());
2954 template <class _Allocator>
2955 typename vector<bool, _Allocator>::iterator
2956 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
2959 size_type __c = capacity();
2960 if (__n <= __c && size() <= __c - __n)
2962 const_iterator __old_end = end();
2964 _VSTD::copy_backward(__position, __old_end, end());
2965 __r = __const_iterator_cast(__position);
2969 vector __v(__alloc());
2970 __v.reserve(__recommend(__size_ + __n));
2971 __v.__size_ = __size_ + __n;
2972 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2973 _VSTD::copy_backward(__position, cend(), __v.end());
2976 _VSTD::fill_n(__r, __n, __x);
2980 template <class _Allocator>
2981 template <class _InputIterator>
2984 __is_input_iterator <_InputIterator>::value &&
2985 !__is_forward_iterator<_InputIterator>::value,
2986 typename vector<bool, _Allocator>::iterator
2988 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
2990 difference_type __off = __position - begin();
2991 iterator __p = __const_iterator_cast(__position);
2992 iterator __old_end = end();
2993 for (; size() != capacity() && __first != __last; ++__first)
2998 vector __v(__alloc());
2999 if (__first != __last)
3001 #ifndef _LIBCPP_NO_EXCEPTIONS
3004 #endif // _LIBCPP_NO_EXCEPTIONS
3005 __v.assign(__first, __last);
3006 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
3007 difference_type __old_p = __p - begin();
3008 reserve(__recommend(size() + __v.size()));
3009 __p = begin() + __old_p;
3010 __old_end = begin() + __old_size;
3011 #ifndef _LIBCPP_NO_EXCEPTIONS
3015 erase(__old_end, end());
3018 #endif // _LIBCPP_NO_EXCEPTIONS
3020 __p = _VSTD::rotate(__p, __old_end, end());
3021 insert(__p, __v.begin(), __v.end());
3022 return begin() + __off;
3025 template <class _Allocator>
3026 template <class _ForwardIterator>
3029 __is_forward_iterator<_ForwardIterator>::value,
3030 typename vector<bool, _Allocator>::iterator
3032 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3034 difference_type __n = _VSTD::distance(__first, __last);
3036 size_type __c = capacity();
3037 if (__n <= __c && size() <= __c - __n)
3039 const_iterator __old_end = end();
3041 _VSTD::copy_backward(__position, __old_end, end());
3042 __r = __const_iterator_cast(__position);
3046 vector __v(__alloc());
3047 __v.reserve(__recommend(__size_ + __n));
3048 __v.__size_ = __size_ + __n;
3049 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3050 _VSTD::copy_backward(__position, cend(), __v.end());
3053 _VSTD::copy(__first, __last, __r);
3057 template <class _Allocator>
3058 inline _LIBCPP_INLINE_VISIBILITY
3059 typename vector<bool, _Allocator>::iterator
3060 vector<bool, _Allocator>::erase(const_iterator __position)
3062 iterator __r = __const_iterator_cast(__position);
3063 _VSTD::copy(__position + 1, this->cend(), __r);
3068 template <class _Allocator>
3069 typename vector<bool, _Allocator>::iterator
3070 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3072 iterator __r = __const_iterator_cast(__first);
3073 difference_type __d = __last - __first;
3074 _VSTD::copy(__last, this->cend(), __r);
3079 template <class _Allocator>
3081 vector<bool, _Allocator>::swap(vector& __x)
3082 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3083 __is_nothrow_swappable<allocator_type>::value)
3085 _VSTD::swap(this->__begin_, __x.__begin_);
3086 _VSTD::swap(this->__size_, __x.__size_);
3087 _VSTD::swap(this->__cap(), __x.__cap());
3088 __swap_alloc(this->__alloc(), __x.__alloc());
3091 template <class _Allocator>
3093 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3095 size_type __cs = size();
3099 size_type __c = capacity();
3100 size_type __n = __sz - __cs;
3101 if (__n <= __c && __cs <= __c - __n)
3108 vector __v(__alloc());
3109 __v.reserve(__recommend(__size_ + __n));
3110 __v.__size_ = __size_ + __n;
3111 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3114 _VSTD::fill_n(__r, __n, __x);
3120 template <class _Allocator>
3122 vector<bool, _Allocator>::flip() _NOEXCEPT
3124 // do middle whole words
3125 size_type __n = __size_;
3126 __storage_pointer __p = __begin_;
3127 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3129 // do last partial word
3132 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3133 __storage_type __b = *__p & __m;
3139 template <class _Allocator>
3141 vector<bool, _Allocator>::__invariants() const
3143 if (this->__begin_ == nullptr)
3145 if (this->__size_ != 0 || this->__cap() != 0)
3150 if (this->__cap() == 0)
3152 if (this->__size_ > this->capacity())
3158 template <class _Allocator>
3160 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3163 // do middle whole words
3164 size_type __n = __size_;
3165 __storage_pointer __p = __begin_;
3166 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3168 // do last partial word
3171 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3177 template <class _Allocator>
3178 struct _LIBCPP_TYPE_VIS_ONLY hash<vector<bool, _Allocator> >
3179 : public unary_function<vector<bool, _Allocator>, size_t>
3181 _LIBCPP_INLINE_VISIBILITY
3182 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3183 {return __vec.__hash_code();}
3186 template <class _Tp, class _Allocator>
3187 inline _LIBCPP_INLINE_VISIBILITY
3189 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3191 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3192 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3195 template <class _Tp, class _Allocator>
3196 inline _LIBCPP_INLINE_VISIBILITY
3198 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3200 return !(__x == __y);
3203 template <class _Tp, class _Allocator>
3204 inline _LIBCPP_INLINE_VISIBILITY
3206 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3208 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3211 template <class _Tp, class _Allocator>
3212 inline _LIBCPP_INLINE_VISIBILITY
3214 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3219 template <class _Tp, class _Allocator>
3220 inline _LIBCPP_INLINE_VISIBILITY
3222 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3224 return !(__x < __y);
3227 template <class _Tp, class _Allocator>
3228 inline _LIBCPP_INLINE_VISIBILITY
3230 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3232 return !(__y < __x);
3235 template <class _Tp, class _Allocator>
3236 inline _LIBCPP_INLINE_VISIBILITY
3238 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3239 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3244 _LIBCPP_END_NAMESPACE_STD
3246 #endif // _LIBCPP_VECTOR