2 //===------------------------------ vector --------------------------------===//
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
8 //===----------------------------------------------------------------------===//
10 #ifndef _LIBCPP_VECTOR
11 #define _LIBCPP_VECTOR
19 template <class T, class Allocator = allocator<T> >
24 typedef Allocator allocator_type;
25 typedef typename allocator_type::reference reference;
26 typedef typename allocator_type::const_reference const_reference;
27 typedef implementation-defined iterator;
28 typedef implementation-defined const_iterator;
29 typedef typename allocator_type::size_type size_type;
30 typedef typename allocator_type::difference_type difference_type;
31 typedef typename allocator_type::pointer pointer;
32 typedef typename allocator_type::const_pointer const_pointer;
33 typedef std::reverse_iterator<iterator> reverse_iterator;
34 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
37 noexcept(is_nothrow_default_constructible<allocator_type>::value);
38 explicit vector(const allocator_type&);
39 explicit vector(size_type n);
40 explicit vector(size_type n, const allocator_type&); // C++14
41 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
42 template <class InputIterator>
43 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
44 vector(const vector& x);
46 noexcept(is_nothrow_move_constructible<allocator_type>::value);
47 vector(initializer_list<value_type> il);
48 vector(initializer_list<value_type> il, const allocator_type& a);
50 vector& operator=(const vector& x);
51 vector& operator=(vector&& x)
53 allocator_type::propagate_on_container_move_assignment::value ||
54 allocator_type::is_always_equal::value); // C++17
55 vector& operator=(initializer_list<value_type> il);
56 template <class InputIterator>
57 void assign(InputIterator first, InputIterator last);
58 void assign(size_type n, const value_type& u);
59 void assign(initializer_list<value_type> il);
61 allocator_type get_allocator() const noexcept;
63 iterator begin() noexcept;
64 const_iterator begin() const noexcept;
65 iterator end() noexcept;
66 const_iterator end() const noexcept;
68 reverse_iterator rbegin() noexcept;
69 const_reverse_iterator rbegin() const noexcept;
70 reverse_iterator rend() noexcept;
71 const_reverse_iterator rend() const noexcept;
73 const_iterator cbegin() const noexcept;
74 const_iterator cend() const noexcept;
75 const_reverse_iterator crbegin() const noexcept;
76 const_reverse_iterator crend() const noexcept;
78 size_type size() const noexcept;
79 size_type max_size() const noexcept;
80 size_type capacity() const noexcept;
81 bool empty() const noexcept;
82 void reserve(size_type n);
83 void shrink_to_fit() noexcept;
85 reference operator[](size_type n);
86 const_reference operator[](size_type n) const;
87 reference at(size_type n);
88 const_reference at(size_type n) const;
91 const_reference front() const;
93 const_reference back() const;
95 value_type* data() noexcept;
96 const value_type* data() const noexcept;
98 void push_back(const value_type& x);
99 void push_back(value_type&& x);
100 template <class... Args>
101 reference emplace_back(Args&&... args); // reference in C++17
104 template <class... Args> iterator emplace(const_iterator position, Args&&... args);
105 iterator insert(const_iterator position, const value_type& x);
106 iterator insert(const_iterator position, value_type&& x);
107 iterator insert(const_iterator position, size_type n, const value_type& x);
108 template <class InputIterator>
109 iterator insert(const_iterator position, InputIterator first, InputIterator last);
110 iterator insert(const_iterator position, initializer_list<value_type> il);
112 iterator erase(const_iterator position);
113 iterator erase(const_iterator first, const_iterator last);
115 void clear() noexcept;
117 void resize(size_type sz);
118 void resize(size_type sz, const value_type& c);
121 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
122 allocator_traits<allocator_type>::is_always_equal::value); // C++17
124 bool __invariants() const;
127 template <class Allocator = allocator<T> >
128 class vector<bool, Allocator>
131 typedef bool value_type;
132 typedef Allocator allocator_type;
133 typedef implementation-defined iterator;
134 typedef implementation-defined const_iterator;
135 typedef typename allocator_type::size_type size_type;
136 typedef typename allocator_type::difference_type difference_type;
137 typedef iterator pointer;
138 typedef const_iterator const_pointer;
139 typedef std::reverse_iterator<iterator> reverse_iterator;
140 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
145 reference(const reference&) noexcept;
146 operator bool() const noexcept;
147 reference& operator=(const bool x) noexcept;
148 reference& operator=(const reference& x) noexcept;
149 iterator operator&() const noexcept;
150 void flip() noexcept;
153 class const_reference
156 const_reference(const reference&) noexcept;
157 operator bool() const noexcept;
158 const_iterator operator&() const noexcept;
162 noexcept(is_nothrow_default_constructible<allocator_type>::value);
163 explicit vector(const allocator_type&);
164 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
165 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
166 template <class InputIterator>
167 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
168 vector(const vector& x);
170 noexcept(is_nothrow_move_constructible<allocator_type>::value);
171 vector(initializer_list<value_type> il);
172 vector(initializer_list<value_type> il, const allocator_type& a);
174 vector& operator=(const vector& x);
175 vector& operator=(vector&& x)
177 allocator_type::propagate_on_container_move_assignment::value ||
178 allocator_type::is_always_equal::value); // C++17
179 vector& operator=(initializer_list<value_type> il);
180 template <class InputIterator>
181 void assign(InputIterator first, InputIterator last);
182 void assign(size_type n, const value_type& u);
183 void assign(initializer_list<value_type> il);
185 allocator_type get_allocator() const noexcept;
187 iterator begin() noexcept;
188 const_iterator begin() const noexcept;
189 iterator end() noexcept;
190 const_iterator end() const noexcept;
192 reverse_iterator rbegin() noexcept;
193 const_reverse_iterator rbegin() const noexcept;
194 reverse_iterator rend() noexcept;
195 const_reverse_iterator rend() const noexcept;
197 const_iterator cbegin() const noexcept;
198 const_iterator cend() const noexcept;
199 const_reverse_iterator crbegin() const noexcept;
200 const_reverse_iterator crend() const noexcept;
202 size_type size() const noexcept;
203 size_type max_size() const noexcept;
204 size_type capacity() const noexcept;
205 bool empty() const noexcept;
206 void reserve(size_type n);
207 void shrink_to_fit() noexcept;
209 reference operator[](size_type n);
210 const_reference operator[](size_type n) const;
211 reference at(size_type n);
212 const_reference at(size_type n) const;
215 const_reference front() const;
217 const_reference back() const;
219 void push_back(const value_type& x);
220 template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17
223 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
224 iterator insert(const_iterator position, const value_type& x);
225 iterator insert(const_iterator position, size_type n, const value_type& x);
226 template <class InputIterator>
227 iterator insert(const_iterator position, InputIterator first, InputIterator last);
228 iterator insert(const_iterator position, initializer_list<value_type> il);
230 iterator erase(const_iterator position);
231 iterator erase(const_iterator first, const_iterator last);
233 void clear() noexcept;
235 void resize(size_type sz);
236 void resize(size_type sz, value_type x);
239 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
240 allocator_traits<allocator_type>::is_always_equal::value); // C++17
241 void flip() noexcept;
243 bool __invariants() const;
246 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
247 vector(InputIterator, InputIterator, Allocator = Allocator())
248 -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>;
250 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
252 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
253 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
254 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
255 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
256 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
257 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
259 template <class T, class Allocator>
260 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
261 noexcept(noexcept(x.swap(y)));
263 template <class T, class Allocator, class U>
264 void erase(vector<T, Allocator>& c, const U& value); // C++20
265 template <class T, class Allocator, class Predicate>
266 void erase_if(vector<T, Allocator>& c, Predicate pred); // C++20
273 #include <iosfwd> // for forward declaration of vector
274 #include <__bit_reference>
275 #include <type_traits>
278 #include <initializer_list>
284 #include <__split_buffer>
285 #include <__functional_base>
289 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
290 #pragma GCC system_header
294 #include <__undef_macros>
297 _LIBCPP_BEGIN_NAMESPACE_STD
300 class _LIBCPP_TEMPLATE_VIS __vector_base_common
303 _LIBCPP_INLINE_VISIBILITY __vector_base_common() {}
304 _LIBCPP_NORETURN void __throw_length_error() const;
305 _LIBCPP_NORETURN void __throw_out_of_range() const;
310 __vector_base_common<__b>::__throw_length_error() const
312 _VSTD::__throw_length_error("vector");
317 __vector_base_common<__b>::__throw_out_of_range() const
319 _VSTD::__throw_out_of_range("vector");
322 _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>)
324 template <class _Tp, class _Allocator>
326 : protected __vector_base_common<true>
329 typedef _Allocator allocator_type;
330 typedef allocator_traits<allocator_type> __alloc_traits;
331 typedef typename __alloc_traits::size_type size_type;
333 typedef _Tp value_type;
334 typedef value_type& reference;
335 typedef const value_type& const_reference;
336 typedef typename __alloc_traits::difference_type difference_type;
337 typedef typename __alloc_traits::pointer pointer;
338 typedef typename __alloc_traits::const_pointer const_pointer;
339 typedef pointer iterator;
340 typedef const_pointer const_iterator;
344 __compressed_pair<pointer, allocator_type> __end_cap_;
346 _LIBCPP_INLINE_VISIBILITY
347 allocator_type& __alloc() _NOEXCEPT
348 {return __end_cap_.second();}
349 _LIBCPP_INLINE_VISIBILITY
350 const allocator_type& __alloc() const _NOEXCEPT
351 {return __end_cap_.second();}
352 _LIBCPP_INLINE_VISIBILITY
353 pointer& __end_cap() _NOEXCEPT
354 {return __end_cap_.first();}
355 _LIBCPP_INLINE_VISIBILITY
356 const pointer& __end_cap() const _NOEXCEPT
357 {return __end_cap_.first();}
359 _LIBCPP_INLINE_VISIBILITY
361 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
362 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
363 #ifndef _LIBCPP_CXX03_LANG
364 _LIBCPP_INLINE_VISIBILITY __vector_base(allocator_type&& __a) _NOEXCEPT;
368 _LIBCPP_INLINE_VISIBILITY
369 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
370 _LIBCPP_INLINE_VISIBILITY
371 size_type capacity() const _NOEXCEPT
372 {return static_cast<size_type>(__end_cap() - __begin_);}
374 _LIBCPP_INLINE_VISIBILITY
375 void __destruct_at_end(pointer __new_last) _NOEXCEPT;
377 _LIBCPP_INLINE_VISIBILITY
378 void __copy_assign_alloc(const __vector_base& __c)
379 {__copy_assign_alloc(__c, integral_constant<bool,
380 __alloc_traits::propagate_on_container_copy_assignment::value>());}
382 _LIBCPP_INLINE_VISIBILITY
383 void __move_assign_alloc(__vector_base& __c)
385 !__alloc_traits::propagate_on_container_move_assignment::value ||
386 is_nothrow_move_assignable<allocator_type>::value)
387 {__move_assign_alloc(__c, integral_constant<bool,
388 __alloc_traits::propagate_on_container_move_assignment::value>());}
390 _LIBCPP_INLINE_VISIBILITY
391 void __copy_assign_alloc(const __vector_base& __c, true_type)
393 if (__alloc() != __c.__alloc())
396 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
397 __begin_ = __end_ = __end_cap() = nullptr;
399 __alloc() = __c.__alloc();
402 _LIBCPP_INLINE_VISIBILITY
403 void __copy_assign_alloc(const __vector_base&, false_type)
406 _LIBCPP_INLINE_VISIBILITY
407 void __move_assign_alloc(__vector_base& __c, true_type)
408 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
410 __alloc() = _VSTD::move(__c.__alloc());
413 _LIBCPP_INLINE_VISIBILITY
414 void __move_assign_alloc(__vector_base&, false_type)
419 template <class _Tp, class _Allocator>
420 inline _LIBCPP_INLINE_VISIBILITY
422 __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
424 pointer __soon_to_be_end = __end_;
425 while (__new_last != __soon_to_be_end)
426 __alloc_traits::destroy(__alloc(), _VSTD::__to_address(--__soon_to_be_end));
430 template <class _Tp, class _Allocator>
431 inline _LIBCPP_INLINE_VISIBILITY
432 __vector_base<_Tp, _Allocator>::__vector_base()
433 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
436 __end_cap_(nullptr, __default_init_tag())
440 template <class _Tp, class _Allocator>
441 inline _LIBCPP_INLINE_VISIBILITY
442 __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
445 __end_cap_(nullptr, __a)
449 #ifndef _LIBCPP_CXX03_LANG
450 template <class _Tp, class _Allocator>
451 inline _LIBCPP_INLINE_VISIBILITY
452 __vector_base<_Tp, _Allocator>::__vector_base(allocator_type&& __a) _NOEXCEPT
455 __end_cap_(nullptr, std::move(__a)) {}
458 template <class _Tp, class _Allocator>
459 __vector_base<_Tp, _Allocator>::~__vector_base()
461 if (__begin_ != nullptr)
464 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
468 template <class _Tp, class _Allocator /* = allocator<_Tp> */>
469 class _LIBCPP_TEMPLATE_VIS vector
470 : private __vector_base<_Tp, _Allocator>
473 typedef __vector_base<_Tp, _Allocator> __base;
474 typedef allocator<_Tp> __default_allocator_type;
476 typedef vector __self;
477 typedef _Tp value_type;
478 typedef _Allocator allocator_type;
479 typedef typename __base::__alloc_traits __alloc_traits;
480 typedef typename __base::reference reference;
481 typedef typename __base::const_reference const_reference;
482 typedef typename __base::size_type size_type;
483 typedef typename __base::difference_type difference_type;
484 typedef typename __base::pointer pointer;
485 typedef typename __base::const_pointer const_pointer;
486 typedef __wrap_iter<pointer> iterator;
487 typedef __wrap_iter<const_pointer> const_iterator;
488 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
489 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
491 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
492 "Allocator::value_type must be same type as value_type");
494 _LIBCPP_INLINE_VISIBILITY
495 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
497 #if _LIBCPP_DEBUG_LEVEL >= 2
498 __get_db()->__insert_c(this);
501 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
502 #if _LIBCPP_STD_VER <= 14
503 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
509 #if _LIBCPP_DEBUG_LEVEL >= 2
510 __get_db()->__insert_c(this);
513 explicit vector(size_type __n);
514 #if _LIBCPP_STD_VER > 11
515 explicit vector(size_type __n, const allocator_type& __a);
517 vector(size_type __n, const value_type& __x);
518 vector(size_type __n, const value_type& __x, const allocator_type& __a);
519 template <class _InputIterator>
520 vector(_InputIterator __first,
521 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
522 !__is_cpp17_forward_iterator<_InputIterator>::value &&
525 typename iterator_traits<_InputIterator>::reference>::value,
526 _InputIterator>::type __last);
527 template <class _InputIterator>
528 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
529 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
530 !__is_cpp17_forward_iterator<_InputIterator>::value &&
533 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
534 template <class _ForwardIterator>
535 vector(_ForwardIterator __first,
536 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
539 typename iterator_traits<_ForwardIterator>::reference>::value,
540 _ForwardIterator>::type __last);
541 template <class _ForwardIterator>
542 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
543 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
546 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
548 _LIBCPP_INLINE_VISIBILITY
552 #if _LIBCPP_DEBUG_LEVEL >= 2
553 __get_db()->__erase_c(this);
557 vector(const vector& __x);
558 vector(const vector& __x, const allocator_type& __a);
559 _LIBCPP_INLINE_VISIBILITY
560 vector& operator=(const vector& __x);
562 #ifndef _LIBCPP_CXX03_LANG
563 _LIBCPP_INLINE_VISIBILITY
564 vector(initializer_list<value_type> __il);
566 _LIBCPP_INLINE_VISIBILITY
567 vector(initializer_list<value_type> __il, const allocator_type& __a);
569 _LIBCPP_INLINE_VISIBILITY
571 #if _LIBCPP_STD_VER > 14
574 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
577 _LIBCPP_INLINE_VISIBILITY
578 vector(vector&& __x, const allocator_type& __a);
579 _LIBCPP_INLINE_VISIBILITY
580 vector& operator=(vector&& __x)
581 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
583 _LIBCPP_INLINE_VISIBILITY
584 vector& operator=(initializer_list<value_type> __il)
585 {assign(__il.begin(), __il.end()); return *this;}
587 #endif // !_LIBCPP_CXX03_LANG
589 template <class _InputIterator>
592 __is_cpp17_input_iterator <_InputIterator>::value &&
593 !__is_cpp17_forward_iterator<_InputIterator>::value &&
596 typename iterator_traits<_InputIterator>::reference>::value,
599 assign(_InputIterator __first, _InputIterator __last);
600 template <class _ForwardIterator>
603 __is_cpp17_forward_iterator<_ForwardIterator>::value &&
606 typename iterator_traits<_ForwardIterator>::reference>::value,
609 assign(_ForwardIterator __first, _ForwardIterator __last);
611 void assign(size_type __n, const_reference __u);
613 #ifndef _LIBCPP_CXX03_LANG
614 _LIBCPP_INLINE_VISIBILITY
615 void assign(initializer_list<value_type> __il)
616 {assign(__il.begin(), __il.end());}
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_NODISCARD_AFTER_CXX17 _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) _NOEXCEPT;
668 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const _NOEXCEPT;
669 reference at(size_type __n);
670 const_reference at(size_type __n) const;
672 _LIBCPP_INLINE_VISIBILITY reference front() _NOEXCEPT
674 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
675 return *this->__begin_;
677 _LIBCPP_INLINE_VISIBILITY const_reference front() const _NOEXCEPT
679 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
680 return *this->__begin_;
682 _LIBCPP_INLINE_VISIBILITY reference back() _NOEXCEPT
684 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
685 return *(this->__end_ - 1);
687 _LIBCPP_INLINE_VISIBILITY const_reference back() const _NOEXCEPT
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_address(this->__begin_);}
696 _LIBCPP_INLINE_VISIBILITY
697 const value_type* data() const _NOEXCEPT
698 {return _VSTD::__to_address(this->__begin_);}
700 #ifdef _LIBCPP_CXX03_LANG
701 _LIBCPP_INLINE_VISIBILITY
702 void __emplace_back(const value_type& __x) { push_back(__x); }
704 template <class _Arg>
705 _LIBCPP_INLINE_VISIBILITY
706 void __emplace_back(_Arg&& __arg) {
707 emplace_back(_VSTD::forward<_Arg>(__arg));
711 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
713 #ifndef _LIBCPP_CXX03_LANG
714 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
716 template <class... _Args>
717 _LIBCPP_INLINE_VISIBILITY
718 #if _LIBCPP_STD_VER > 14
719 reference emplace_back(_Args&&... __args);
721 void emplace_back(_Args&&... __args);
723 #endif // !_LIBCPP_CXX03_LANG
725 _LIBCPP_INLINE_VISIBILITY
728 iterator insert(const_iterator __position, const_reference __x);
730 #ifndef _LIBCPP_CXX03_LANG
731 iterator insert(const_iterator __position, value_type&& __x);
732 template <class... _Args>
733 iterator emplace(const_iterator __position, _Args&&... __args);
734 #endif // !_LIBCPP_CXX03_LANG
736 iterator insert(const_iterator __position, size_type __n, const_reference __x);
737 template <class _InputIterator>
740 __is_cpp17_input_iterator <_InputIterator>::value &&
741 !__is_cpp17_forward_iterator<_InputIterator>::value &&
744 typename iterator_traits<_InputIterator>::reference>::value,
747 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
748 template <class _ForwardIterator>
751 __is_cpp17_forward_iterator<_ForwardIterator>::value &&
754 typename iterator_traits<_ForwardIterator>::reference>::value,
757 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
759 #ifndef _LIBCPP_CXX03_LANG
760 _LIBCPP_INLINE_VISIBILITY
761 iterator insert(const_iterator __position, initializer_list<value_type> __il)
762 {return insert(__position, __il.begin(), __il.end());}
765 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
766 iterator erase(const_iterator __first, const_iterator __last);
768 _LIBCPP_INLINE_VISIBILITY
769 void clear() _NOEXCEPT
771 size_type __old_size = size();
773 __annotate_shrink(__old_size);
774 __invalidate_all_iterators();
777 void resize(size_type __sz);
778 void resize(size_type __sz, const_reference __x);
781 #if _LIBCPP_STD_VER >= 14
784 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
785 __is_nothrow_swappable<allocator_type>::value);
788 bool __invariants() const;
790 #if _LIBCPP_DEBUG_LEVEL >= 2
792 bool __dereferenceable(const const_iterator* __i) const;
793 bool __decrementable(const const_iterator* __i) const;
794 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
795 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
797 #endif // _LIBCPP_DEBUG_LEVEL >= 2
800 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
801 _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
802 void __vallocate(size_type __n);
803 void __vdeallocate() _NOEXCEPT;
804 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
805 void __construct_at_end(size_type __n);
806 _LIBCPP_INLINE_VISIBILITY
807 void __construct_at_end(size_type __n, const_reference __x);
808 template <class _ForwardIterator>
811 __is_cpp17_forward_iterator<_ForwardIterator>::value,
814 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
815 void __append(size_type __n);
816 void __append(size_type __n, const_reference __x);
817 _LIBCPP_INLINE_VISIBILITY
818 iterator __make_iter(pointer __p) _NOEXCEPT;
819 _LIBCPP_INLINE_VISIBILITY
820 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
821 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
822 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
823 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
824 void __move_assign(vector& __c, true_type)
825 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
826 void __move_assign(vector& __c, false_type)
827 _NOEXCEPT_(__alloc_traits::is_always_equal::value);
828 _LIBCPP_INLINE_VISIBILITY
829 void __destruct_at_end(pointer __new_last) _NOEXCEPT
831 __invalidate_iterators_past(__new_last);
832 size_type __old_size = size();
833 __base::__destruct_at_end(__new_last);
834 __annotate_shrink(__old_size);
837 #ifndef _LIBCPP_CXX03_LANG
839 _LIBCPP_INLINE_VISIBILITY
840 inline void __push_back_slow_path(_Up&& __x);
842 template <class... _Args>
843 _LIBCPP_INLINE_VISIBILITY
844 inline void __emplace_back_slow_path(_Args&&... __args);
847 _LIBCPP_INLINE_VISIBILITY
848 inline void __push_back_slow_path(_Up& __x);
851 // The following functions are no-ops outside of AddressSanitizer mode.
852 // We call annotatations only for the default Allocator because other allocators
853 // may not meet the AddressSanitizer alignment constraints.
854 // See the documentation for __sanitizer_annotate_contiguous_container for more details.
855 #ifndef _LIBCPP_HAS_NO_ASAN
856 void __annotate_contiguous_container(const void *__beg, const void *__end,
857 const void *__old_mid,
858 const void *__new_mid) const
861 if (__beg && is_same<allocator_type, __default_allocator_type>::value)
862 __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
865 _LIBCPP_INLINE_VISIBILITY
866 void __annotate_contiguous_container(const void*, const void*, const void*,
867 const void*) const _NOEXCEPT {}
869 _LIBCPP_INLINE_VISIBILITY
870 void __annotate_new(size_type __current_size) const _NOEXCEPT {
871 __annotate_contiguous_container(data(), data() + capacity(),
872 data() + capacity(), data() + __current_size);
875 _LIBCPP_INLINE_VISIBILITY
876 void __annotate_delete() const _NOEXCEPT {
877 __annotate_contiguous_container(data(), data() + capacity(),
878 data() + size(), data() + capacity());
881 _LIBCPP_INLINE_VISIBILITY
882 void __annotate_increase(size_type __n) const _NOEXCEPT
884 __annotate_contiguous_container(data(), data() + capacity(),
885 data() + size(), data() + size() + __n);
888 _LIBCPP_INLINE_VISIBILITY
889 void __annotate_shrink(size_type __old_size) const _NOEXCEPT
891 __annotate_contiguous_container(data(), data() + capacity(),
892 data() + __old_size, data() + size());
895 struct _ConstructTransaction {
896 explicit _ConstructTransaction(vector &__v, size_type __n)
897 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
898 #ifndef _LIBCPP_HAS_NO_ASAN
899 __v_.__annotate_increase(__n);
902 ~_ConstructTransaction() {
903 __v_.__end_ = __pos_;
904 #ifndef _LIBCPP_HAS_NO_ASAN
905 if (__pos_ != __new_end_) {
906 __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
913 const_pointer const __new_end_;
916 _ConstructTransaction(_ConstructTransaction const&) = delete;
917 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
920 template <class ..._Args>
921 _LIBCPP_INLINE_VISIBILITY
922 void __construct_one_at_end(_Args&& ...__args) {
923 _ConstructTransaction __tx(*this, 1);
924 __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_),
925 _VSTD::forward<_Args>(__args)...);
930 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
931 template<class _InputIterator,
932 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
933 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
935 vector(_InputIterator, _InputIterator)
936 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
938 template<class _InputIterator,
940 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
942 vector(_InputIterator, _InputIterator, _Alloc)
943 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
946 template <class _Tp, class _Allocator>
948 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
952 __alloc_traits::__construct_backward_with_exception_guarantees(
953 this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
954 _VSTD::swap(this->__begin_, __v.__begin_);
955 _VSTD::swap(this->__end_, __v.__end_);
956 _VSTD::swap(this->__end_cap(), __v.__end_cap());
957 __v.__first_ = __v.__begin_;
958 __annotate_new(size());
959 __invalidate_all_iterators();
962 template <class _Tp, class _Allocator>
963 typename vector<_Tp, _Allocator>::pointer
964 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
967 pointer __r = __v.__begin_;
968 __alloc_traits::__construct_backward_with_exception_guarantees(
969 this->__alloc(), this->__begin_, __p, __v.__begin_);
970 __alloc_traits::__construct_forward_with_exception_guarantees(
971 this->__alloc(), __p, this->__end_, __v.__end_);
972 _VSTD::swap(this->__begin_, __v.__begin_);
973 _VSTD::swap(this->__end_, __v.__end_);
974 _VSTD::swap(this->__end_cap(), __v.__end_cap());
975 __v.__first_ = __v.__begin_;
976 __annotate_new(size());
977 __invalidate_all_iterators();
981 // Allocate space for __n objects
982 // throws length_error if __n > max_size()
983 // throws (probably bad_alloc) if memory run out
984 // Precondition: __begin_ == __end_ == __end_cap() == 0
985 // Precondition: __n > 0
986 // Postcondition: capacity() == __n
987 // Postcondition: size() == 0
988 template <class _Tp, class _Allocator>
990 vector<_Tp, _Allocator>::__vallocate(size_type __n)
992 if (__n > max_size())
993 this->__throw_length_error();
994 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
995 this->__end_cap() = this->__begin_ + __n;
999 template <class _Tp, class _Allocator>
1001 vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT
1003 if (this->__begin_ != nullptr)
1006 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
1007 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
1011 template <class _Tp, class _Allocator>
1012 typename vector<_Tp, _Allocator>::size_type
1013 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
1015 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),
1016 numeric_limits<difference_type>::max());
1019 // Precondition: __new_size > capacity()
1020 template <class _Tp, class _Allocator>
1021 inline _LIBCPP_INLINE_VISIBILITY
1022 typename vector<_Tp, _Allocator>::size_type
1023 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
1025 const size_type __ms = max_size();
1026 if (__new_size > __ms)
1027 this->__throw_length_error();
1028 const size_type __cap = capacity();
1029 if (__cap >= __ms / 2)
1031 return _VSTD::max<size_type>(2*__cap, __new_size);
1034 // Default constructs __n objects starting at __end_
1035 // throws if construction throws
1036 // Precondition: __n > 0
1037 // Precondition: size() + __n <= capacity()
1038 // Postcondition: size() == size() + __n
1039 template <class _Tp, class _Allocator>
1041 vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
1043 _ConstructTransaction __tx(*this, __n);
1044 for (; __tx.__pos_ != __tx.__new_end_; ++__tx.__pos_) {
1045 __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_));
1049 // Copy constructs __n objects starting at __end_ from __x
1050 // throws if construction throws
1051 // Precondition: __n > 0
1052 // Precondition: size() + __n <= capacity()
1053 // Postcondition: size() == old size() + __n
1054 // Postcondition: [i] == __x for all i in [size() - __n, __n)
1055 template <class _Tp, class _Allocator>
1058 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
1060 _ConstructTransaction __tx(*this, __n);
1061 for (; __tx.__pos_ != __tx.__new_end_; ++__tx.__pos_) {
1062 __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_), __x);
1066 template <class _Tp, class _Allocator>
1067 template <class _ForwardIterator>
1070 __is_cpp17_forward_iterator<_ForwardIterator>::value,
1073 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
1075 _ConstructTransaction __tx(*this, __n);
1076 __alloc_traits::__construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_);
1079 // Default constructs __n objects starting at __end_
1080 // throws if construction throws
1081 // Postcondition: size() == size() + __n
1082 // Exception safety: strong.
1083 template <class _Tp, class _Allocator>
1085 vector<_Tp, _Allocator>::__append(size_type __n)
1087 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1088 this->__construct_at_end(__n);
1091 allocator_type& __a = this->__alloc();
1092 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1093 __v.__construct_at_end(__n);
1094 __swap_out_circular_buffer(__v);
1098 // Default constructs __n objects starting at __end_
1099 // throws if construction throws
1100 // Postcondition: size() == size() + __n
1101 // Exception safety: strong.
1102 template <class _Tp, class _Allocator>
1104 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
1106 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1107 this->__construct_at_end(__n, __x);
1110 allocator_type& __a = this->__alloc();
1111 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1112 __v.__construct_at_end(__n, __x);
1113 __swap_out_circular_buffer(__v);
1117 template <class _Tp, class _Allocator>
1118 vector<_Tp, _Allocator>::vector(size_type __n)
1120 #if _LIBCPP_DEBUG_LEVEL >= 2
1121 __get_db()->__insert_c(this);
1126 __construct_at_end(__n);
1130 #if _LIBCPP_STD_VER > 11
1131 template <class _Tp, class _Allocator>
1132 vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
1135 #if _LIBCPP_DEBUG_LEVEL >= 2
1136 __get_db()->__insert_c(this);
1141 __construct_at_end(__n);
1146 template <class _Tp, class _Allocator>
1147 vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)
1149 #if _LIBCPP_DEBUG_LEVEL >= 2
1150 __get_db()->__insert_c(this);
1155 __construct_at_end(__n, __x);
1159 template <class _Tp, class _Allocator>
1160 vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
1163 #if _LIBCPP_DEBUG_LEVEL >= 2
1164 __get_db()->__insert_c(this);
1169 __construct_at_end(__n, __x);
1173 template <class _Tp, class _Allocator>
1174 template <class _InputIterator>
1175 vector<_Tp, _Allocator>::vector(_InputIterator __first,
1176 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
1177 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1180 typename iterator_traits<_InputIterator>::reference>::value,
1181 _InputIterator>::type __last)
1183 #if _LIBCPP_DEBUG_LEVEL >= 2
1184 __get_db()->__insert_c(this);
1186 for (; __first != __last; ++__first)
1187 __emplace_back(*__first);
1190 template <class _Tp, class _Allocator>
1191 template <class _InputIterator>
1192 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1193 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
1194 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1197 typename iterator_traits<_InputIterator>::reference>::value>::type*)
1200 #if _LIBCPP_DEBUG_LEVEL >= 2
1201 __get_db()->__insert_c(this);
1203 for (; __first != __last; ++__first)
1204 __emplace_back(*__first);
1207 template <class _Tp, class _Allocator>
1208 template <class _ForwardIterator>
1209 vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
1210 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
1213 typename iterator_traits<_ForwardIterator>::reference>::value,
1214 _ForwardIterator>::type __last)
1216 #if _LIBCPP_DEBUG_LEVEL >= 2
1217 __get_db()->__insert_c(this);
1219 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1223 __construct_at_end(__first, __last, __n);
1227 template <class _Tp, class _Allocator>
1228 template <class _ForwardIterator>
1229 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
1230 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
1233 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
1236 #if _LIBCPP_DEBUG_LEVEL >= 2
1237 __get_db()->__insert_c(this);
1239 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1243 __construct_at_end(__first, __last, __n);
1247 template <class _Tp, class _Allocator>
1248 vector<_Tp, _Allocator>::vector(const vector& __x)
1249 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1251 #if _LIBCPP_DEBUG_LEVEL >= 2
1252 __get_db()->__insert_c(this);
1254 size_type __n = __x.size();
1258 __construct_at_end(__x.__begin_, __x.__end_, __n);
1262 template <class _Tp, class _Allocator>
1263 vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1266 #if _LIBCPP_DEBUG_LEVEL >= 2
1267 __get_db()->__insert_c(this);
1269 size_type __n = __x.size();
1273 __construct_at_end(__x.__begin_, __x.__end_, __n);
1277 #ifndef _LIBCPP_CXX03_LANG
1279 template <class _Tp, class _Allocator>
1280 inline _LIBCPP_INLINE_VISIBILITY
1281 vector<_Tp, _Allocator>::vector(vector&& __x)
1282 #if _LIBCPP_STD_VER > 14
1285 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1287 : __base(_VSTD::move(__x.__alloc()))
1289 #if _LIBCPP_DEBUG_LEVEL >= 2
1290 __get_db()->__insert_c(this);
1291 __get_db()->swap(this, &__x);
1293 this->__begin_ = __x.__begin_;
1294 this->__end_ = __x.__end_;
1295 this->__end_cap() = __x.__end_cap();
1296 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1299 template <class _Tp, class _Allocator>
1300 inline _LIBCPP_INLINE_VISIBILITY
1301 vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1304 #if _LIBCPP_DEBUG_LEVEL >= 2
1305 __get_db()->__insert_c(this);
1307 if (__a == __x.__alloc())
1309 this->__begin_ = __x.__begin_;
1310 this->__end_ = __x.__end_;
1311 this->__end_cap() = __x.__end_cap();
1312 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1313 #if _LIBCPP_DEBUG_LEVEL >= 2
1314 __get_db()->swap(this, &__x);
1319 typedef move_iterator<iterator> _Ip;
1320 assign(_Ip(__x.begin()), _Ip(__x.end()));
1324 template <class _Tp, class _Allocator>
1325 inline _LIBCPP_INLINE_VISIBILITY
1326 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1328 #if _LIBCPP_DEBUG_LEVEL >= 2
1329 __get_db()->__insert_c(this);
1331 if (__il.size() > 0)
1333 __vallocate(__il.size());
1334 __construct_at_end(__il.begin(), __il.end(), __il.size());
1338 template <class _Tp, class _Allocator>
1339 inline _LIBCPP_INLINE_VISIBILITY
1340 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1343 #if _LIBCPP_DEBUG_LEVEL >= 2
1344 __get_db()->__insert_c(this);
1346 if (__il.size() > 0)
1348 __vallocate(__il.size());
1349 __construct_at_end(__il.begin(), __il.end(), __il.size());
1353 template <class _Tp, class _Allocator>
1354 inline _LIBCPP_INLINE_VISIBILITY
1355 vector<_Tp, _Allocator>&
1356 vector<_Tp, _Allocator>::operator=(vector&& __x)
1357 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
1359 __move_assign(__x, integral_constant<bool,
1360 __alloc_traits::propagate_on_container_move_assignment::value>());
1364 template <class _Tp, class _Allocator>
1366 vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1367 _NOEXCEPT_(__alloc_traits::is_always_equal::value)
1369 if (__base::__alloc() != __c.__alloc())
1371 typedef move_iterator<iterator> _Ip;
1372 assign(_Ip(__c.begin()), _Ip(__c.end()));
1375 __move_assign(__c, true_type());
1378 template <class _Tp, class _Allocator>
1380 vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1381 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1384 __base::__move_assign_alloc(__c); // this can throw
1385 this->__begin_ = __c.__begin_;
1386 this->__end_ = __c.__end_;
1387 this->__end_cap() = __c.__end_cap();
1388 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1389 #if _LIBCPP_DEBUG_LEVEL >= 2
1390 __get_db()->swap(this, &__c);
1394 #endif // !_LIBCPP_CXX03_LANG
1396 template <class _Tp, class _Allocator>
1397 inline _LIBCPP_INLINE_VISIBILITY
1398 vector<_Tp, _Allocator>&
1399 vector<_Tp, _Allocator>::operator=(const vector& __x)
1403 __base::__copy_assign_alloc(__x);
1404 assign(__x.__begin_, __x.__end_);
1409 template <class _Tp, class _Allocator>
1410 template <class _InputIterator>
1413 __is_cpp17_input_iterator <_InputIterator>::value &&
1414 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1417 typename iterator_traits<_InputIterator>::reference>::value,
1420 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1423 for (; __first != __last; ++__first)
1424 __emplace_back(*__first);
1427 template <class _Tp, class _Allocator>
1428 template <class _ForwardIterator>
1431 __is_cpp17_forward_iterator<_ForwardIterator>::value &&
1434 typename iterator_traits<_ForwardIterator>::reference>::value,
1437 vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1439 size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
1440 if (__new_size <= capacity())
1442 _ForwardIterator __mid = __last;
1443 bool __growing = false;
1444 if (__new_size > size())
1448 _VSTD::advance(__mid, size());
1450 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
1452 __construct_at_end(__mid, __last, __new_size - size());
1454 this->__destruct_at_end(__m);
1459 __vallocate(__recommend(__new_size));
1460 __construct_at_end(__first, __last, __new_size);
1462 __invalidate_all_iterators();
1465 template <class _Tp, class _Allocator>
1467 vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1469 if (__n <= capacity())
1471 size_type __s = size();
1472 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
1474 __construct_at_end(__n - __s, __u);
1476 this->__destruct_at_end(this->__begin_ + __n);
1481 __vallocate(__recommend(static_cast<size_type>(__n)));
1482 __construct_at_end(__n, __u);
1484 __invalidate_all_iterators();
1487 template <class _Tp, class _Allocator>
1488 inline _LIBCPP_INLINE_VISIBILITY
1489 typename vector<_Tp, _Allocator>::iterator
1490 vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
1492 #if _LIBCPP_DEBUG_LEVEL >= 2
1493 return iterator(this, __p);
1495 return iterator(__p);
1499 template <class _Tp, class _Allocator>
1500 inline _LIBCPP_INLINE_VISIBILITY
1501 typename vector<_Tp, _Allocator>::const_iterator
1502 vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
1504 #if _LIBCPP_DEBUG_LEVEL >= 2
1505 return const_iterator(this, __p);
1507 return const_iterator(__p);
1511 template <class _Tp, class _Allocator>
1512 inline _LIBCPP_INLINE_VISIBILITY
1513 typename vector<_Tp, _Allocator>::iterator
1514 vector<_Tp, _Allocator>::begin() _NOEXCEPT
1516 return __make_iter(this->__begin_);
1519 template <class _Tp, class _Allocator>
1520 inline _LIBCPP_INLINE_VISIBILITY
1521 typename vector<_Tp, _Allocator>::const_iterator
1522 vector<_Tp, _Allocator>::begin() const _NOEXCEPT
1524 return __make_iter(this->__begin_);
1527 template <class _Tp, class _Allocator>
1528 inline _LIBCPP_INLINE_VISIBILITY
1529 typename vector<_Tp, _Allocator>::iterator
1530 vector<_Tp, _Allocator>::end() _NOEXCEPT
1532 return __make_iter(this->__end_);
1535 template <class _Tp, class _Allocator>
1536 inline _LIBCPP_INLINE_VISIBILITY
1537 typename vector<_Tp, _Allocator>::const_iterator
1538 vector<_Tp, _Allocator>::end() const _NOEXCEPT
1540 return __make_iter(this->__end_);
1543 template <class _Tp, class _Allocator>
1544 inline _LIBCPP_INLINE_VISIBILITY
1545 typename vector<_Tp, _Allocator>::reference
1546 vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT
1548 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1549 return this->__begin_[__n];
1552 template <class _Tp, class _Allocator>
1553 inline _LIBCPP_INLINE_VISIBILITY
1554 typename vector<_Tp, _Allocator>::const_reference
1555 vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT
1557 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1558 return this->__begin_[__n];
1561 template <class _Tp, class _Allocator>
1562 typename vector<_Tp, _Allocator>::reference
1563 vector<_Tp, _Allocator>::at(size_type __n)
1566 this->__throw_out_of_range();
1567 return this->__begin_[__n];
1570 template <class _Tp, class _Allocator>
1571 typename vector<_Tp, _Allocator>::const_reference
1572 vector<_Tp, _Allocator>::at(size_type __n) const
1575 this->__throw_out_of_range();
1576 return this->__begin_[__n];
1579 template <class _Tp, class _Allocator>
1581 vector<_Tp, _Allocator>::reserve(size_type __n)
1583 if (__n > capacity())
1585 allocator_type& __a = this->__alloc();
1586 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1587 __swap_out_circular_buffer(__v);
1591 template <class _Tp, class _Allocator>
1593 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1595 if (capacity() > size())
1597 #ifndef _LIBCPP_NO_EXCEPTIONS
1600 #endif // _LIBCPP_NO_EXCEPTIONS
1601 allocator_type& __a = this->__alloc();
1602 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1603 __swap_out_circular_buffer(__v);
1604 #ifndef _LIBCPP_NO_EXCEPTIONS
1609 #endif // _LIBCPP_NO_EXCEPTIONS
1613 template <class _Tp, class _Allocator>
1614 template <class _Up>
1616 #ifndef _LIBCPP_CXX03_LANG
1617 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1619 vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1622 allocator_type& __a = this->__alloc();
1623 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1624 // __v.push_back(_VSTD::forward<_Up>(__x));
1625 __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x));
1627 __swap_out_circular_buffer(__v);
1630 template <class _Tp, class _Allocator>
1631 inline _LIBCPP_INLINE_VISIBILITY
1633 vector<_Tp, _Allocator>::push_back(const_reference __x)
1635 if (this->__end_ != this->__end_cap())
1637 __construct_one_at_end(__x);
1640 __push_back_slow_path(__x);
1643 #ifndef _LIBCPP_CXX03_LANG
1645 template <class _Tp, class _Allocator>
1646 inline _LIBCPP_INLINE_VISIBILITY
1648 vector<_Tp, _Allocator>::push_back(value_type&& __x)
1650 if (this->__end_ < this->__end_cap())
1652 __construct_one_at_end(_VSTD::move(__x));
1655 __push_back_slow_path(_VSTD::move(__x));
1658 template <class _Tp, class _Allocator>
1659 template <class... _Args>
1661 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1663 allocator_type& __a = this->__alloc();
1664 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1665 // __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1666 __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...);
1668 __swap_out_circular_buffer(__v);
1671 template <class _Tp, class _Allocator>
1672 template <class... _Args>
1674 #if _LIBCPP_STD_VER > 14
1675 typename vector<_Tp, _Allocator>::reference
1679 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1681 if (this->__end_ < this->__end_cap())
1683 __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
1686 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
1687 #if _LIBCPP_STD_VER > 14
1688 return this->back();
1692 #endif // !_LIBCPP_CXX03_LANG
1694 template <class _Tp, class _Allocator>
1697 vector<_Tp, _Allocator>::pop_back()
1699 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1700 this->__destruct_at_end(this->__end_ - 1);
1703 template <class _Tp, class _Allocator>
1704 inline _LIBCPP_INLINE_VISIBILITY
1705 typename vector<_Tp, _Allocator>::iterator
1706 vector<_Tp, _Allocator>::erase(const_iterator __position)
1708 #if _LIBCPP_DEBUG_LEVEL >= 2
1709 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1710 "vector::erase(iterator) called with an iterator not"
1711 " referring to this vector");
1713 _LIBCPP_ASSERT(__position != end(),
1714 "vector::erase(iterator) called with a non-dereferenceable iterator");
1715 difference_type __ps = __position - cbegin();
1716 pointer __p = this->__begin_ + __ps;
1717 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1718 this->__invalidate_iterators_past(__p-1);
1719 iterator __r = __make_iter(__p);
1723 template <class _Tp, class _Allocator>
1724 typename vector<_Tp, _Allocator>::iterator
1725 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1727 #if _LIBCPP_DEBUG_LEVEL >= 2
1728 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1729 "vector::erase(iterator, iterator) called with an iterator not"
1730 " referring to this vector");
1731 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
1732 "vector::erase(iterator, iterator) called with an iterator not"
1733 " referring to this vector");
1735 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1736 pointer __p = this->__begin_ + (__first - begin());
1737 if (__first != __last) {
1738 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1739 this->__invalidate_iterators_past(__p - 1);
1741 iterator __r = __make_iter(__p);
1745 template <class _Tp, class _Allocator>
1747 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1749 pointer __old_last = this->__end_;
1750 difference_type __n = __old_last - __to;
1752 pointer __i = __from_s + __n;
1753 _ConstructTransaction __tx(*this, __from_e - __i);
1754 for (; __i < __from_e; ++__i, ++__tx.__pos_) {
1755 __alloc_traits::construct(this->__alloc(),
1756 _VSTD::__to_address(__tx.__pos_),
1760 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1763 template <class _Tp, class _Allocator>
1764 typename vector<_Tp, _Allocator>::iterator
1765 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1767 #if _LIBCPP_DEBUG_LEVEL >= 2
1768 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1769 "vector::insert(iterator, x) called with an iterator not"
1770 " referring to this vector");
1772 pointer __p = this->__begin_ + (__position - begin());
1773 if (this->__end_ < this->__end_cap())
1775 if (__p == this->__end_)
1777 __construct_one_at_end(__x);
1781 __move_range(__p, this->__end_, __p + 1);
1782 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1783 if (__p <= __xr && __xr < this->__end_)
1790 allocator_type& __a = this->__alloc();
1791 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1793 __p = __swap_out_circular_buffer(__v, __p);
1795 return __make_iter(__p);
1798 #ifndef _LIBCPP_CXX03_LANG
1800 template <class _Tp, class _Allocator>
1801 typename vector<_Tp, _Allocator>::iterator
1802 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1804 #if _LIBCPP_DEBUG_LEVEL >= 2
1805 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1806 "vector::insert(iterator, x) called with an iterator not"
1807 " referring to this vector");
1809 pointer __p = this->__begin_ + (__position - begin());
1810 if (this->__end_ < this->__end_cap())
1812 if (__p == this->__end_)
1814 __construct_one_at_end(_VSTD::move(__x));
1818 __move_range(__p, this->__end_, __p + 1);
1819 *__p = _VSTD::move(__x);
1824 allocator_type& __a = this->__alloc();
1825 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1826 __v.push_back(_VSTD::move(__x));
1827 __p = __swap_out_circular_buffer(__v, __p);
1829 return __make_iter(__p);
1832 template <class _Tp, class _Allocator>
1833 template <class... _Args>
1834 typename vector<_Tp, _Allocator>::iterator
1835 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1837 #if _LIBCPP_DEBUG_LEVEL >= 2
1838 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1839 "vector::emplace(iterator, x) called with an iterator not"
1840 " referring to this vector");
1842 pointer __p = this->__begin_ + (__position - begin());
1843 if (this->__end_ < this->__end_cap())
1845 if (__p == this->__end_)
1847 __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
1851 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
1852 __move_range(__p, this->__end_, __p + 1);
1853 *__p = _VSTD::move(__tmp.get());
1858 allocator_type& __a = this->__alloc();
1859 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1860 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1861 __p = __swap_out_circular_buffer(__v, __p);
1863 return __make_iter(__p);
1866 #endif // !_LIBCPP_CXX03_LANG
1868 template <class _Tp, class _Allocator>
1869 typename vector<_Tp, _Allocator>::iterator
1870 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1872 #if _LIBCPP_DEBUG_LEVEL >= 2
1873 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1874 "vector::insert(iterator, n, x) called with an iterator not"
1875 " referring to this vector");
1877 pointer __p = this->__begin_ + (__position - begin());
1880 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1882 size_type __old_n = __n;
1883 pointer __old_last = this->__end_;
1884 if (__n > static_cast<size_type>(this->__end_ - __p))
1886 size_type __cx = __n - (this->__end_ - __p);
1887 __construct_at_end(__cx, __x);
1892 __move_range(__p, __old_last, __p + __old_n);
1893 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1894 if (__p <= __xr && __xr < this->__end_)
1896 _VSTD::fill_n(__p, __n, *__xr);
1901 allocator_type& __a = this->__alloc();
1902 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1903 __v.__construct_at_end(__n, __x);
1904 __p = __swap_out_circular_buffer(__v, __p);
1907 return __make_iter(__p);
1910 template <class _Tp, class _Allocator>
1911 template <class _InputIterator>
1914 __is_cpp17_input_iterator <_InputIterator>::value &&
1915 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1918 typename iterator_traits<_InputIterator>::reference>::value,
1919 typename vector<_Tp, _Allocator>::iterator
1921 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1923 #if _LIBCPP_DEBUG_LEVEL >= 2
1924 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1925 "vector::insert(iterator, range) called with an iterator not"
1926 " referring to this vector");
1928 difference_type __off = __position - begin();
1929 pointer __p = this->__begin_ + __off;
1930 allocator_type& __a = this->__alloc();
1931 pointer __old_last = this->__end_;
1932 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1934 __construct_one_at_end(*__first);
1936 __split_buffer<value_type, allocator_type&> __v(__a);
1937 if (__first != __last)
1939 #ifndef _LIBCPP_NO_EXCEPTIONS
1942 #endif // _LIBCPP_NO_EXCEPTIONS
1943 __v.__construct_at_end(__first, __last);
1944 difference_type __old_size = __old_last - this->__begin_;
1945 difference_type __old_p = __p - this->__begin_;
1946 reserve(__recommend(size() + __v.size()));
1947 __p = this->__begin_ + __old_p;
1948 __old_last = this->__begin_ + __old_size;
1949 #ifndef _LIBCPP_NO_EXCEPTIONS
1953 erase(__make_iter(__old_last), end());
1956 #endif // _LIBCPP_NO_EXCEPTIONS
1958 __p = _VSTD::rotate(__p, __old_last, this->__end_);
1959 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1960 make_move_iterator(__v.end()));
1961 return begin() + __off;
1964 template <class _Tp, class _Allocator>
1965 template <class _ForwardIterator>
1968 __is_cpp17_forward_iterator<_ForwardIterator>::value &&
1971 typename iterator_traits<_ForwardIterator>::reference>::value,
1972 typename vector<_Tp, _Allocator>::iterator
1974 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1976 #if _LIBCPP_DEBUG_LEVEL >= 2
1977 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1978 "vector::insert(iterator, range) called with an iterator not"
1979 " referring to this vector");
1981 pointer __p = this->__begin_ + (__position - begin());
1982 difference_type __n = _VSTD::distance(__first, __last);
1985 if (__n <= this->__end_cap() - this->__end_)
1987 size_type __old_n = __n;
1988 pointer __old_last = this->__end_;
1989 _ForwardIterator __m = __last;
1990 difference_type __dx = this->__end_ - __p;
1994 difference_type __diff = this->__end_ - __p;
1995 _VSTD::advance(__m, __diff);
1996 __construct_at_end(__m, __last, __n - __diff);
2001 __move_range(__p, __old_last, __p + __old_n);
2002 _VSTD::copy(__first, __m, __p);
2007 allocator_type& __a = this->__alloc();
2008 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
2009 __v.__construct_at_end(__first, __last);
2010 __p = __swap_out_circular_buffer(__v, __p);
2013 return __make_iter(__p);
2016 template <class _Tp, class _Allocator>
2018 vector<_Tp, _Allocator>::resize(size_type __sz)
2020 size_type __cs = size();
2022 this->__append(__sz - __cs);
2023 else if (__cs > __sz)
2024 this->__destruct_at_end(this->__begin_ + __sz);
2027 template <class _Tp, class _Allocator>
2029 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
2031 size_type __cs = size();
2033 this->__append(__sz - __cs, __x);
2034 else if (__cs > __sz)
2035 this->__destruct_at_end(this->__begin_ + __sz);
2038 template <class _Tp, class _Allocator>
2040 vector<_Tp, _Allocator>::swap(vector& __x)
2041 #if _LIBCPP_STD_VER >= 14
2044 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2045 __is_nothrow_swappable<allocator_type>::value)
2048 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
2049 this->__alloc() == __x.__alloc(),
2050 "vector::swap: Either propagate_on_container_swap must be true"
2051 " or the allocators must compare equal");
2052 _VSTD::swap(this->__begin_, __x.__begin_);
2053 _VSTD::swap(this->__end_, __x.__end_);
2054 _VSTD::swap(this->__end_cap(), __x.__end_cap());
2055 __swap_allocator(this->__alloc(), __x.__alloc(),
2056 integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
2057 #if _LIBCPP_DEBUG_LEVEL >= 2
2058 __get_db()->swap(this, &__x);
2059 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2062 template <class _Tp, class _Allocator>
2064 vector<_Tp, _Allocator>::__invariants() const
2066 if (this->__begin_ == nullptr)
2068 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
2073 if (this->__begin_ > this->__end_)
2075 if (this->__begin_ == this->__end_cap())
2077 if (this->__end_ > this->__end_cap())
2083 #if _LIBCPP_DEBUG_LEVEL >= 2
2085 template <class _Tp, class _Allocator>
2087 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
2089 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
2092 template <class _Tp, class _Allocator>
2094 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
2096 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
2099 template <class _Tp, class _Allocator>
2101 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2103 const_pointer __p = __i->base() + __n;
2104 return this->__begin_ <= __p && __p <= this->__end_;
2107 template <class _Tp, class _Allocator>
2109 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2111 const_pointer __p = __i->base() + __n;
2112 return this->__begin_ <= __p && __p < this->__end_;
2115 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2117 template <class _Tp, class _Allocator>
2118 inline _LIBCPP_INLINE_VISIBILITY
2120 vector<_Tp, _Allocator>::__invalidate_all_iterators()
2122 #if _LIBCPP_DEBUG_LEVEL >= 2
2123 __get_db()->__invalidate_all(this);
2124 #endif // _LIBCPP_DEBUG_LEVEL >= 2
2128 template <class _Tp, class _Allocator>
2129 inline _LIBCPP_INLINE_VISIBILITY
2131 vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) {
2132 #if _LIBCPP_DEBUG_LEVEL >= 2
2133 __c_node* __c = __get_db()->__find_c_and_lock(this);
2134 for (__i_node** __p = __c->end_; __p != __c->beg_; ) {
2136 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
2137 if (__i->base() > __new_last) {
2138 (*__p)->__c_ = nullptr;
2139 if (--__c->end_ != __p)
2140 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
2143 __get_db()->unlock();
2151 template <class _Allocator> class vector<bool, _Allocator>;
2153 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2155 template <class _Allocator>
2156 struct __has_storage_type<vector<bool, _Allocator> >
2158 static const bool value = true;
2161 template <class _Allocator>
2162 class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
2163 : private __vector_base_common<true>
2166 typedef vector __self;
2167 typedef bool value_type;
2168 typedef _Allocator allocator_type;
2169 typedef allocator_traits<allocator_type> __alloc_traits;
2170 typedef typename __alloc_traits::size_type size_type;
2171 typedef typename __alloc_traits::difference_type difference_type;
2172 typedef size_type __storage_type;
2173 typedef __bit_iterator<vector, false> pointer;
2174 typedef __bit_iterator<vector, true> const_pointer;
2175 typedef pointer iterator;
2176 typedef const_pointer const_iterator;
2177 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2178 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
2181 typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
2182 typedef allocator_traits<__storage_allocator> __storage_traits;
2183 typedef typename __storage_traits::pointer __storage_pointer;
2184 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2186 __storage_pointer __begin_;
2188 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2190 typedef __bit_reference<vector> reference;
2191 typedef __bit_const_reference<vector> const_reference;
2193 _LIBCPP_INLINE_VISIBILITY
2194 size_type& __cap() _NOEXCEPT
2195 {return __cap_alloc_.first();}
2196 _LIBCPP_INLINE_VISIBILITY
2197 const size_type& __cap() const _NOEXCEPT
2198 {return __cap_alloc_.first();}
2199 _LIBCPP_INLINE_VISIBILITY
2200 __storage_allocator& __alloc() _NOEXCEPT
2201 {return __cap_alloc_.second();}
2202 _LIBCPP_INLINE_VISIBILITY
2203 const __storage_allocator& __alloc() const _NOEXCEPT
2204 {return __cap_alloc_.second();}
2206 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2208 _LIBCPP_INLINE_VISIBILITY
2209 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2210 {return __n * __bits_per_word;}
2211 _LIBCPP_INLINE_VISIBILITY
2212 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2213 {return (__n - 1) / __bits_per_word + 1;}
2216 _LIBCPP_INLINE_VISIBILITY
2217 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2219 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
2220 #if _LIBCPP_STD_VER <= 14
2221 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
2226 explicit vector(size_type __n);
2227 #if _LIBCPP_STD_VER > 11
2228 explicit vector(size_type __n, const allocator_type& __a);
2230 vector(size_type __n, const value_type& __v);
2231 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2232 template <class _InputIterator>
2233 vector(_InputIterator __first, _InputIterator __last,
2234 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2235 !__is_cpp17_forward_iterator<_InputIterator>::value>::type* = 0);
2236 template <class _InputIterator>
2237 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2238 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2239 !__is_cpp17_forward_iterator<_InputIterator>::value>::type* = 0);
2240 template <class _ForwardIterator>
2241 vector(_ForwardIterator __first, _ForwardIterator __last,
2242 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
2243 template <class _ForwardIterator>
2244 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2245 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
2247 vector(const vector& __v);
2248 vector(const vector& __v, const allocator_type& __a);
2249 vector& operator=(const vector& __v);
2251 #ifndef _LIBCPP_CXX03_LANG
2252 vector(initializer_list<value_type> __il);
2253 vector(initializer_list<value_type> __il, const allocator_type& __a);
2255 _LIBCPP_INLINE_VISIBILITY
2256 vector(vector&& __v)
2257 #if _LIBCPP_STD_VER > 14
2260 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2262 vector(vector&& __v, const allocator_type& __a);
2263 _LIBCPP_INLINE_VISIBILITY
2264 vector& operator=(vector&& __v)
2265 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
2267 _LIBCPP_INLINE_VISIBILITY
2268 vector& operator=(initializer_list<value_type> __il)
2269 {assign(__il.begin(), __il.end()); return *this;}
2271 #endif // !_LIBCPP_CXX03_LANG
2273 template <class _InputIterator>
2276 __is_cpp17_input_iterator<_InputIterator>::value &&
2277 !__is_cpp17_forward_iterator<_InputIterator>::value,
2280 assign(_InputIterator __first, _InputIterator __last);
2281 template <class _ForwardIterator>
2284 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2287 assign(_ForwardIterator __first, _ForwardIterator __last);
2289 void assign(size_type __n, const value_type& __x);
2291 #ifndef _LIBCPP_CXX03_LANG
2292 _LIBCPP_INLINE_VISIBILITY
2293 void assign(initializer_list<value_type> __il)
2294 {assign(__il.begin(), __il.end());}
2297 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2298 {return allocator_type(this->__alloc());}
2300 size_type max_size() const _NOEXCEPT;
2301 _LIBCPP_INLINE_VISIBILITY
2302 size_type capacity() const _NOEXCEPT
2303 {return __internal_cap_to_external(__cap());}
2304 _LIBCPP_INLINE_VISIBILITY
2305 size_type size() const _NOEXCEPT
2307 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
2308 bool empty() const _NOEXCEPT
2309 {return __size_ == 0;}
2310 void reserve(size_type __n);
2311 void shrink_to_fit() _NOEXCEPT;
2313 _LIBCPP_INLINE_VISIBILITY
2314 iterator begin() _NOEXCEPT
2315 {return __make_iter(0);}
2316 _LIBCPP_INLINE_VISIBILITY
2317 const_iterator begin() const _NOEXCEPT
2318 {return __make_iter(0);}
2319 _LIBCPP_INLINE_VISIBILITY
2320 iterator end() _NOEXCEPT
2321 {return __make_iter(__size_);}
2322 _LIBCPP_INLINE_VISIBILITY
2323 const_iterator end() const _NOEXCEPT
2324 {return __make_iter(__size_);}
2326 _LIBCPP_INLINE_VISIBILITY
2327 reverse_iterator rbegin() _NOEXCEPT
2328 {return reverse_iterator(end());}
2329 _LIBCPP_INLINE_VISIBILITY
2330 const_reverse_iterator rbegin() const _NOEXCEPT
2331 {return const_reverse_iterator(end());}
2332 _LIBCPP_INLINE_VISIBILITY
2333 reverse_iterator rend() _NOEXCEPT
2334 {return reverse_iterator(begin());}
2335 _LIBCPP_INLINE_VISIBILITY
2336 const_reverse_iterator rend() const _NOEXCEPT
2337 {return const_reverse_iterator(begin());}
2339 _LIBCPP_INLINE_VISIBILITY
2340 const_iterator cbegin() const _NOEXCEPT
2341 {return __make_iter(0);}
2342 _LIBCPP_INLINE_VISIBILITY
2343 const_iterator cend() const _NOEXCEPT
2344 {return __make_iter(__size_);}
2345 _LIBCPP_INLINE_VISIBILITY
2346 const_reverse_iterator crbegin() const _NOEXCEPT
2348 _LIBCPP_INLINE_VISIBILITY
2349 const_reverse_iterator crend() const _NOEXCEPT
2352 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2353 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2354 reference at(size_type __n);
2355 const_reference at(size_type __n) const;
2357 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2358 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2359 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2360 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2362 void push_back(const value_type& __x);
2363 #if _LIBCPP_STD_VER > 11
2364 template <class... _Args>
2365 #if _LIBCPP_STD_VER > 14
2366 _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args)
2368 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
2371 push_back ( value_type ( _VSTD::forward<_Args>(__args)... ));
2372 #if _LIBCPP_STD_VER > 14
2373 return this->back();
2378 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2380 #if _LIBCPP_STD_VER > 11
2381 template <class... _Args>
2382 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
2383 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
2386 iterator insert(const_iterator __position, const value_type& __x);
2387 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2388 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2389 template <class _InputIterator>
2392 __is_cpp17_input_iterator <_InputIterator>::value &&
2393 !__is_cpp17_forward_iterator<_InputIterator>::value,
2396 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2397 template <class _ForwardIterator>
2400 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2403 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2405 #ifndef _LIBCPP_CXX03_LANG
2406 _LIBCPP_INLINE_VISIBILITY
2407 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2408 {return insert(__position, __il.begin(), __il.end());}
2411 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2412 iterator erase(const_iterator __first, const_iterator __last);
2414 _LIBCPP_INLINE_VISIBILITY
2415 void clear() _NOEXCEPT {__size_ = 0;}
2418 #if _LIBCPP_STD_VER >= 14
2421 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2422 __is_nothrow_swappable<allocator_type>::value);
2424 static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); }
2426 void resize(size_type __sz, value_type __x = false);
2427 void flip() _NOEXCEPT;
2429 bool __invariants() const;
2432 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2433 void __vallocate(size_type __n);
2434 void __vdeallocate() _NOEXCEPT;
2435 _LIBCPP_INLINE_VISIBILITY
2436 static size_type __align_it(size_type __new_size) _NOEXCEPT
2437 {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}
2438 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2439 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2440 template <class _ForwardIterator>
2443 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2446 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2447 void __append(size_type __n, const_reference __x);
2448 _LIBCPP_INLINE_VISIBILITY
2449 reference __make_ref(size_type __pos) _NOEXCEPT
2450 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2451 _LIBCPP_INLINE_VISIBILITY
2452 const_reference __make_ref(size_type __pos) const _NOEXCEPT
2453 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2454 _LIBCPP_INLINE_VISIBILITY
2455 iterator __make_iter(size_type __pos) _NOEXCEPT
2456 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2457 _LIBCPP_INLINE_VISIBILITY
2458 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2459 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2460 _LIBCPP_INLINE_VISIBILITY
2461 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2462 {return begin() + (__p - cbegin());}
2464 _LIBCPP_INLINE_VISIBILITY
2465 void __copy_assign_alloc(const vector& __v)
2466 {__copy_assign_alloc(__v, integral_constant<bool,
2467 __storage_traits::propagate_on_container_copy_assignment::value>());}
2468 _LIBCPP_INLINE_VISIBILITY
2469 void __copy_assign_alloc(const vector& __c, true_type)
2471 if (__alloc() != __c.__alloc())
2473 __alloc() = __c.__alloc();
2476 _LIBCPP_INLINE_VISIBILITY
2477 void __copy_assign_alloc(const vector&, false_type)
2480 void __move_assign(vector& __c, false_type);
2481 void __move_assign(vector& __c, true_type)
2482 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2483 _LIBCPP_INLINE_VISIBILITY
2484 void __move_assign_alloc(vector& __c)
2486 !__storage_traits::propagate_on_container_move_assignment::value ||
2487 is_nothrow_move_assignable<allocator_type>::value)
2488 {__move_assign_alloc(__c, integral_constant<bool,
2489 __storage_traits::propagate_on_container_move_assignment::value>());}
2490 _LIBCPP_INLINE_VISIBILITY
2491 void __move_assign_alloc(vector& __c, true_type)
2492 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2494 __alloc() = _VSTD::move(__c.__alloc());
2497 _LIBCPP_INLINE_VISIBILITY
2498 void __move_assign_alloc(vector&, false_type)
2502 size_t __hash_code() const _NOEXCEPT;
2504 friend class __bit_reference<vector>;
2505 friend class __bit_const_reference<vector>;
2506 friend class __bit_iterator<vector, false>;
2507 friend class __bit_iterator<vector, true>;
2508 friend struct __bit_array<vector>;
2509 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
2512 template <class _Allocator>
2513 inline _LIBCPP_INLINE_VISIBILITY
2515 vector<bool, _Allocator>::__invalidate_all_iterators()
2519 // Allocate space for __n objects
2520 // throws length_error if __n > max_size()
2521 // throws (probably bad_alloc) if memory run out
2522 // Precondition: __begin_ == __end_ == __cap() == 0
2523 // Precondition: __n > 0
2524 // Postcondition: capacity() == __n
2525 // Postcondition: size() == 0
2526 template <class _Allocator>
2528 vector<bool, _Allocator>::__vallocate(size_type __n)
2530 if (__n > max_size())
2531 this->__throw_length_error();
2532 __n = __external_cap_to_internal(__n);
2533 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2535 this->__cap() = __n;
2538 template <class _Allocator>
2540 vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
2542 if (this->__begin_ != nullptr)
2544 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2545 __invalidate_all_iterators();
2546 this->__begin_ = nullptr;
2547 this->__size_ = this->__cap() = 0;
2551 template <class _Allocator>
2552 typename vector<bool, _Allocator>::size_type
2553 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2555 size_type __amax = __storage_traits::max_size(__alloc());
2556 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2557 if (__nmax / __bits_per_word <= __amax)
2559 return __internal_cap_to_external(__amax);
2562 // Precondition: __new_size > capacity()
2563 template <class _Allocator>
2564 inline _LIBCPP_INLINE_VISIBILITY
2565 typename vector<bool, _Allocator>::size_type
2566 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2568 const size_type __ms = max_size();
2569 if (__new_size > __ms)
2570 this->__throw_length_error();
2571 const size_type __cap = capacity();
2572 if (__cap >= __ms / 2)
2574 return _VSTD::max(2*__cap, __align_it(__new_size));
2577 // Default constructs __n objects starting at __end_
2578 // Precondition: __n > 0
2579 // Precondition: size() + __n <= capacity()
2580 // Postcondition: size() == size() + __n
2581 template <class _Allocator>
2582 inline _LIBCPP_INLINE_VISIBILITY
2584 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2586 size_type __old_size = this->__size_;
2587 this->__size_ += __n;
2588 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2590 if (this->__size_ <= __bits_per_word)
2591 this->__begin_[0] = __storage_type(0);
2593 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2595 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2598 template <class _Allocator>
2599 template <class _ForwardIterator>
2602 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2605 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2607 size_type __old_size = this->__size_;
2608 this->__size_ += _VSTD::distance(__first, __last);
2609 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2611 if (this->__size_ <= __bits_per_word)
2612 this->__begin_[0] = __storage_type(0);
2614 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2616 _VSTD::copy(__first, __last, __make_iter(__old_size));
2619 template <class _Allocator>
2620 inline _LIBCPP_INLINE_VISIBILITY
2621 vector<bool, _Allocator>::vector()
2622 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2623 : __begin_(nullptr),
2625 __cap_alloc_(0, __default_init_tag())
2629 template <class _Allocator>
2630 inline _LIBCPP_INLINE_VISIBILITY
2631 vector<bool, _Allocator>::vector(const allocator_type& __a)
2632 #if _LIBCPP_STD_VER <= 14
2633 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
2637 : __begin_(nullptr),
2639 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2643 template <class _Allocator>
2644 vector<bool, _Allocator>::vector(size_type __n)
2645 : __begin_(nullptr),
2647 __cap_alloc_(0, __default_init_tag())
2652 __construct_at_end(__n, false);
2656 #if _LIBCPP_STD_VER > 11
2657 template <class _Allocator>
2658 vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2659 : __begin_(nullptr),
2661 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2666 __construct_at_end(__n, false);
2671 template <class _Allocator>
2672 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2673 : __begin_(nullptr),
2675 __cap_alloc_(0, __default_init_tag())
2680 __construct_at_end(__n, __x);
2684 template <class _Allocator>
2685 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2686 : __begin_(nullptr),
2688 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2693 __construct_at_end(__n, __x);
2697 template <class _Allocator>
2698 template <class _InputIterator>
2699 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2700 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2701 !__is_cpp17_forward_iterator<_InputIterator>::value>::type*)
2702 : __begin_(nullptr),
2704 __cap_alloc_(0, __default_init_tag())
2706 #ifndef _LIBCPP_NO_EXCEPTIONS
2709 #endif // _LIBCPP_NO_EXCEPTIONS
2710 for (; __first != __last; ++__first)
2711 push_back(*__first);
2712 #ifndef _LIBCPP_NO_EXCEPTIONS
2716 if (__begin_ != nullptr)
2717 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2718 __invalidate_all_iterators();
2721 #endif // _LIBCPP_NO_EXCEPTIONS
2724 template <class _Allocator>
2725 template <class _InputIterator>
2726 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2727 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2728 !__is_cpp17_forward_iterator<_InputIterator>::value>::type*)
2729 : __begin_(nullptr),
2731 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2733 #ifndef _LIBCPP_NO_EXCEPTIONS
2736 #endif // _LIBCPP_NO_EXCEPTIONS
2737 for (; __first != __last; ++__first)
2738 push_back(*__first);
2739 #ifndef _LIBCPP_NO_EXCEPTIONS
2743 if (__begin_ != nullptr)
2744 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2745 __invalidate_all_iterators();
2748 #endif // _LIBCPP_NO_EXCEPTIONS
2751 template <class _Allocator>
2752 template <class _ForwardIterator>
2753 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2754 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
2755 : __begin_(nullptr),
2757 __cap_alloc_(0, __default_init_tag())
2759 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2763 __construct_at_end(__first, __last);
2767 template <class _Allocator>
2768 template <class _ForwardIterator>
2769 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2770 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
2771 : __begin_(nullptr),
2773 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2775 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2779 __construct_at_end(__first, __last);
2783 #ifndef _LIBCPP_CXX03_LANG
2785 template <class _Allocator>
2786 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2787 : __begin_(nullptr),
2789 __cap_alloc_(0, __default_init_tag())
2791 size_type __n = static_cast<size_type>(__il.size());
2795 __construct_at_end(__il.begin(), __il.end());
2799 template <class _Allocator>
2800 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2801 : __begin_(nullptr),
2803 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2805 size_type __n = static_cast<size_type>(__il.size());
2809 __construct_at_end(__il.begin(), __il.end());
2813 #endif // _LIBCPP_CXX03_LANG
2815 template <class _Allocator>
2816 vector<bool, _Allocator>::~vector()
2818 if (__begin_ != nullptr)
2819 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2820 __invalidate_all_iterators();
2823 template <class _Allocator>
2824 vector<bool, _Allocator>::vector(const vector& __v)
2825 : __begin_(nullptr),
2827 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2831 __vallocate(__v.size());
2832 __construct_at_end(__v.begin(), __v.end());
2836 template <class _Allocator>
2837 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2838 : __begin_(nullptr),
2840 __cap_alloc_(0, __a)
2844 __vallocate(__v.size());
2845 __construct_at_end(__v.begin(), __v.end());
2849 template <class _Allocator>
2850 vector<bool, _Allocator>&
2851 vector<bool, _Allocator>::operator=(const vector& __v)
2855 __copy_assign_alloc(__v);
2858 if (__v.__size_ > capacity())
2861 __vallocate(__v.__size_);
2863 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2865 __size_ = __v.__size_;
2870 #ifndef _LIBCPP_CXX03_LANG
2872 template <class _Allocator>
2873 inline _LIBCPP_INLINE_VISIBILITY vector<bool, _Allocator>::vector(vector&& __v)
2874 #if _LIBCPP_STD_VER > 14
2877 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2879 : __begin_(__v.__begin_),
2880 __size_(__v.__size_),
2881 __cap_alloc_(std::move(__v.__cap_alloc_)) {
2882 __v.__begin_ = nullptr;
2887 template <class _Allocator>
2888 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2889 : __begin_(nullptr),
2891 __cap_alloc_(0, __a)
2893 if (__a == allocator_type(__v.__alloc()))
2895 this->__begin_ = __v.__begin_;
2896 this->__size_ = __v.__size_;
2897 this->__cap() = __v.__cap();
2898 __v.__begin_ = nullptr;
2899 __v.__cap() = __v.__size_ = 0;
2901 else if (__v.size() > 0)
2903 __vallocate(__v.size());
2904 __construct_at_end(__v.begin(), __v.end());
2908 template <class _Allocator>
2909 inline _LIBCPP_INLINE_VISIBILITY
2910 vector<bool, _Allocator>&
2911 vector<bool, _Allocator>::operator=(vector&& __v)
2912 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
2914 __move_assign(__v, integral_constant<bool,
2915 __storage_traits::propagate_on_container_move_assignment::value>());
2919 template <class _Allocator>
2921 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2923 if (__alloc() != __c.__alloc())
2924 assign(__c.begin(), __c.end());
2926 __move_assign(__c, true_type());
2929 template <class _Allocator>
2931 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2932 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2935 __move_assign_alloc(__c);
2936 this->__begin_ = __c.__begin_;
2937 this->__size_ = __c.__size_;
2938 this->__cap() = __c.__cap();
2939 __c.__begin_ = nullptr;
2940 __c.__cap() = __c.__size_ = 0;
2943 #endif // !_LIBCPP_CXX03_LANG
2945 template <class _Allocator>
2947 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2952 size_type __c = capacity();
2957 vector __v(__alloc());
2958 __v.reserve(__recommend(__n));
2962 _VSTD::fill_n(begin(), __n, __x);
2964 __invalidate_all_iterators();
2967 template <class _Allocator>
2968 template <class _InputIterator>
2971 __is_cpp17_input_iterator<_InputIterator>::value &&
2972 !__is_cpp17_forward_iterator<_InputIterator>::value,
2975 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2978 for (; __first != __last; ++__first)
2979 push_back(*__first);
2982 template <class _Allocator>
2983 template <class _ForwardIterator>
2986 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2989 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2992 difference_type __ns = _VSTD::distance(__first, __last);
2993 _LIBCPP_ASSERT(__ns >= 0, "invalid range specified");
2994 const size_t __n = static_cast<size_type>(__ns);
2997 if (__n > capacity())
3002 __construct_at_end(__first, __last);
3006 template <class _Allocator>
3008 vector<bool, _Allocator>::reserve(size_type __n)
3010 if (__n > capacity())
3012 vector __v(this->__alloc());
3013 __v.__vallocate(__n);
3014 __v.__construct_at_end(this->begin(), this->end());
3016 __invalidate_all_iterators();
3020 template <class _Allocator>
3022 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
3024 if (__external_cap_to_internal(size()) > __cap())
3026 #ifndef _LIBCPP_NO_EXCEPTIONS
3029 #endif // _LIBCPP_NO_EXCEPTIONS
3030 vector(*this, allocator_type(__alloc())).swap(*this);
3031 #ifndef _LIBCPP_NO_EXCEPTIONS
3036 #endif // _LIBCPP_NO_EXCEPTIONS
3040 template <class _Allocator>
3041 typename vector<bool, _Allocator>::reference
3042 vector<bool, _Allocator>::at(size_type __n)
3045 this->__throw_out_of_range();
3046 return (*this)[__n];
3049 template <class _Allocator>
3050 typename vector<bool, _Allocator>::const_reference
3051 vector<bool, _Allocator>::at(size_type __n) const
3054 this->__throw_out_of_range();
3055 return (*this)[__n];
3058 template <class _Allocator>
3060 vector<bool, _Allocator>::push_back(const value_type& __x)
3062 if (this->__size_ == this->capacity())
3063 reserve(__recommend(this->__size_ + 1));
3068 template <class _Allocator>
3069 typename vector<bool, _Allocator>::iterator
3070 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
3073 if (size() < capacity())
3075 const_iterator __old_end = end();
3077 _VSTD::copy_backward(__position, __old_end, end());
3078 __r = __const_iterator_cast(__position);
3082 vector __v(__alloc());
3083 __v.reserve(__recommend(__size_ + 1));
3084 __v.__size_ = __size_ + 1;
3085 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3086 _VSTD::copy_backward(__position, cend(), __v.end());
3093 template <class _Allocator>
3094 typename vector<bool, _Allocator>::iterator
3095 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
3098 size_type __c = capacity();
3099 if (__n <= __c && size() <= __c - __n)
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_ + __n));
3110 __v.__size_ = __size_ + __n;
3111 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3112 _VSTD::copy_backward(__position, cend(), __v.end());
3115 _VSTD::fill_n(__r, __n, __x);
3119 template <class _Allocator>
3120 template <class _InputIterator>
3123 __is_cpp17_input_iterator <_InputIterator>::value &&
3124 !__is_cpp17_forward_iterator<_InputIterator>::value,
3125 typename vector<bool, _Allocator>::iterator
3127 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
3129 difference_type __off = __position - begin();
3130 iterator __p = __const_iterator_cast(__position);
3131 iterator __old_end = end();
3132 for (; size() != capacity() && __first != __last; ++__first)
3137 vector __v(__alloc());
3138 if (__first != __last)
3140 #ifndef _LIBCPP_NO_EXCEPTIONS
3143 #endif // _LIBCPP_NO_EXCEPTIONS
3144 __v.assign(__first, __last);
3145 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
3146 difference_type __old_p = __p - begin();
3147 reserve(__recommend(size() + __v.size()));
3148 __p = begin() + __old_p;
3149 __old_end = begin() + __old_size;
3150 #ifndef _LIBCPP_NO_EXCEPTIONS
3154 erase(__old_end, end());
3157 #endif // _LIBCPP_NO_EXCEPTIONS
3159 __p = _VSTD::rotate(__p, __old_end, end());
3160 insert(__p, __v.begin(), __v.end());
3161 return begin() + __off;
3164 template <class _Allocator>
3165 template <class _ForwardIterator>
3168 __is_cpp17_forward_iterator<_ForwardIterator>::value,
3169 typename vector<bool, _Allocator>::iterator
3171 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3173 const difference_type __n_signed = _VSTD::distance(__first, __last);
3174 _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified");
3175 const size_type __n = static_cast<size_type>(__n_signed);
3177 size_type __c = capacity();
3178 if (__n <= __c && size() <= __c - __n)
3180 const_iterator __old_end = end();
3182 _VSTD::copy_backward(__position, __old_end, end());
3183 __r = __const_iterator_cast(__position);
3187 vector __v(__alloc());
3188 __v.reserve(__recommend(__size_ + __n));
3189 __v.__size_ = __size_ + __n;
3190 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3191 _VSTD::copy_backward(__position, cend(), __v.end());
3194 _VSTD::copy(__first, __last, __r);
3198 template <class _Allocator>
3199 inline _LIBCPP_INLINE_VISIBILITY
3200 typename vector<bool, _Allocator>::iterator
3201 vector<bool, _Allocator>::erase(const_iterator __position)
3203 iterator __r = __const_iterator_cast(__position);
3204 _VSTD::copy(__position + 1, this->cend(), __r);
3209 template <class _Allocator>
3210 typename vector<bool, _Allocator>::iterator
3211 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3213 iterator __r = __const_iterator_cast(__first);
3214 difference_type __d = __last - __first;
3215 _VSTD::copy(__last, this->cend(), __r);
3220 template <class _Allocator>
3222 vector<bool, _Allocator>::swap(vector& __x)
3223 #if _LIBCPP_STD_VER >= 14
3226 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3227 __is_nothrow_swappable<allocator_type>::value)
3230 _VSTD::swap(this->__begin_, __x.__begin_);
3231 _VSTD::swap(this->__size_, __x.__size_);
3232 _VSTD::swap(this->__cap(), __x.__cap());
3233 __swap_allocator(this->__alloc(), __x.__alloc(),
3234 integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
3237 template <class _Allocator>
3239 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3241 size_type __cs = size();
3245 size_type __c = capacity();
3246 size_type __n = __sz - __cs;
3247 if (__n <= __c && __cs <= __c - __n)
3254 vector __v(__alloc());
3255 __v.reserve(__recommend(__size_ + __n));
3256 __v.__size_ = __size_ + __n;
3257 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3260 _VSTD::fill_n(__r, __n, __x);
3266 template <class _Allocator>
3268 vector<bool, _Allocator>::flip() _NOEXCEPT
3270 // do middle whole words
3271 size_type __n = __size_;
3272 __storage_pointer __p = __begin_;
3273 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3275 // do last partial word
3278 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3279 __storage_type __b = *__p & __m;
3285 template <class _Allocator>
3287 vector<bool, _Allocator>::__invariants() const
3289 if (this->__begin_ == nullptr)
3291 if (this->__size_ != 0 || this->__cap() != 0)
3296 if (this->__cap() == 0)
3298 if (this->__size_ > this->capacity())
3304 template <class _Allocator>
3306 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3309 // do middle whole words
3310 size_type __n = __size_;
3311 __storage_pointer __p = __begin_;
3312 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3314 // do last partial word
3317 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3323 template <class _Allocator>
3324 struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
3325 : public unary_function<vector<bool, _Allocator>, size_t>
3327 _LIBCPP_INLINE_VISIBILITY
3328 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3329 {return __vec.__hash_code();}
3332 template <class _Tp, class _Allocator>
3333 inline _LIBCPP_INLINE_VISIBILITY
3335 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3337 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3338 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3341 template <class _Tp, class _Allocator>
3342 inline _LIBCPP_INLINE_VISIBILITY
3344 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3346 return !(__x == __y);
3349 template <class _Tp, class _Allocator>
3350 inline _LIBCPP_INLINE_VISIBILITY
3352 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3354 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3357 template <class _Tp, class _Allocator>
3358 inline _LIBCPP_INLINE_VISIBILITY
3360 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3365 template <class _Tp, class _Allocator>
3366 inline _LIBCPP_INLINE_VISIBILITY
3368 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3370 return !(__x < __y);
3373 template <class _Tp, class _Allocator>
3374 inline _LIBCPP_INLINE_VISIBILITY
3376 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3378 return !(__y < __x);
3381 template <class _Tp, class _Allocator>
3382 inline _LIBCPP_INLINE_VISIBILITY
3384 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3385 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3390 #if _LIBCPP_STD_VER > 17
3391 template <class _Tp, class _Allocator, class _Up>
3392 inline _LIBCPP_INLINE_VISIBILITY
3393 void erase(vector<_Tp, _Allocator>& __c, const _Up& __v)
3394 { __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); }
3396 template <class _Tp, class _Allocator, class _Predicate>
3397 inline _LIBCPP_INLINE_VISIBILITY
3398 void erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred)
3399 { __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); }
3402 _LIBCPP_END_NAMESPACE_STD
3406 #endif // _LIBCPP_VECTOR