2 //===------------------------------ vector --------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_VECTOR
12 #define _LIBCPP_VECTOR
20 template <class T, class Allocator = allocator<T> >
25 typedef Allocator allocator_type;
26 typedef typename allocator_type::reference reference;
27 typedef typename allocator_type::const_reference const_reference;
28 typedef implementation-defined iterator;
29 typedef implementation-defined const_iterator;
30 typedef typename allocator_type::size_type size_type;
31 typedef typename allocator_type::difference_type difference_type;
32 typedef typename allocator_type::pointer pointer;
33 typedef typename allocator_type::const_pointer const_pointer;
34 typedef std::reverse_iterator<iterator> reverse_iterator;
35 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
38 noexcept(is_nothrow_default_constructible<allocator_type>::value);
39 explicit vector(const allocator_type&);
40 explicit vector(size_type n);
41 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 is_nothrow_move_assignable<allocator_type>::value);
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 void emplace_back(Args&&... args);
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_type::propagate_on_container_swap::value ||
122 __is_nothrow_swappable<allocator_type>::value);
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 value_type& value = value_type(), const allocator_type& = allocator_type());
165 template <class InputIterator>
166 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
167 vector(const vector& x);
169 noexcept(is_nothrow_move_constructible<allocator_type>::value);
170 vector(initializer_list<value_type> il);
171 vector(initializer_list<value_type> il, const allocator_type& a);
173 vector& operator=(const vector& x);
174 vector& operator=(vector&& x)
176 allocator_type::propagate_on_container_move_assignment::value &&
177 is_nothrow_move_assignable<allocator_type>::value);
178 vector& operator=(initializer_list<value_type> il);
179 template <class InputIterator>
180 void assign(InputIterator first, InputIterator last);
181 void assign(size_type n, const value_type& u);
182 void assign(initializer_list<value_type> il);
184 allocator_type get_allocator() const noexcept;
186 iterator begin() noexcept;
187 const_iterator begin() const noexcept;
188 iterator end() noexcept;
189 const_iterator end() const noexcept;
191 reverse_iterator rbegin() noexcept;
192 const_reverse_iterator rbegin() const noexcept;
193 reverse_iterator rend() noexcept;
194 const_reverse_iterator rend() const noexcept;
196 const_iterator cbegin() const noexcept;
197 const_iterator cend() const noexcept;
198 const_reverse_iterator crbegin() const noexcept;
199 const_reverse_iterator crend() const noexcept;
201 size_type size() const noexcept;
202 size_type max_size() const noexcept;
203 size_type capacity() const noexcept;
204 bool empty() const noexcept;
205 void reserve(size_type n);
206 void shrink_to_fit() noexcept;
208 reference operator[](size_type n);
209 const_reference operator[](size_type n) const;
210 reference at(size_type n);
211 const_reference at(size_type n) const;
214 const_reference front() const;
216 const_reference back() const;
218 void push_back(const value_type& x);
221 iterator insert(const_iterator position, const value_type& x);
222 iterator insert(const_iterator position, size_type n, const value_type& x);
223 template <class InputIterator>
224 iterator insert(const_iterator position, InputIterator first, InputIterator last);
225 iterator insert(const_iterator position, initializer_list<value_type> il);
227 iterator erase(const_iterator position);
228 iterator erase(const_iterator first, const_iterator last);
230 void clear() noexcept;
232 void resize(size_type sz);
233 void resize(size_type sz, value_type x);
236 noexcept(!allocator_type::propagate_on_container_swap::value ||
237 __is_nothrow_swappable<allocator_type>::value);
238 void flip() noexcept;
240 bool __invariants() const;
243 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
245 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
246 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
247 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
248 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
249 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
250 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
252 template <class T, class Allocator>
253 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
254 noexcept(noexcept(x.swap(y)));
261 #include <__bit_reference>
262 #include <type_traits>
265 #include <initializer_list>
270 #include <__split_buffer>
271 #include <__functional_base>
273 #include <__undef_min_max>
275 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
276 #pragma GCC system_header
279 _LIBCPP_BEGIN_NAMESPACE_STD
282 class __vector_base_common
285 _LIBCPP_ALWAYS_INLINE __vector_base_common() {}
286 void __throw_length_error() const;
287 void __throw_out_of_range() const;
292 __vector_base_common<__b>::__throw_length_error() const
294 #ifndef _LIBCPP_NO_EXCEPTIONS
295 throw length_error("vector");
297 assert(!"vector length_error");
303 __vector_base_common<__b>::__throw_out_of_range() const
305 #ifndef _LIBCPP_NO_EXCEPTIONS
306 throw out_of_range("vector");
308 assert(!"vector out_of_range");
313 #pragma warning( push )
314 #pragma warning( disable: 4231 )
316 _LIBCPP_EXTERN_TEMPLATE(class __vector_base_common<true>)
318 #pragma warning( pop )
321 template <class _Tp, class _Allocator>
323 : protected __vector_base_common<true>
326 typedef _Tp value_type;
327 typedef _Allocator allocator_type;
328 typedef allocator_traits<allocator_type> __alloc_traits;
329 typedef value_type& reference;
330 typedef const value_type& const_reference;
331 typedef typename __alloc_traits::size_type size_type;
332 typedef typename __alloc_traits::difference_type difference_type;
333 typedef typename __alloc_traits::pointer pointer;
334 typedef typename __alloc_traits::const_pointer const_pointer;
335 typedef pointer iterator;
336 typedef const_pointer const_iterator;
340 __compressed_pair<pointer, allocator_type> __end_cap_;
342 _LIBCPP_INLINE_VISIBILITY
343 allocator_type& __alloc() _NOEXCEPT
344 {return __end_cap_.second();}
345 _LIBCPP_INLINE_VISIBILITY
346 const allocator_type& __alloc() const _NOEXCEPT
347 {return __end_cap_.second();}
348 _LIBCPP_INLINE_VISIBILITY
349 pointer& __end_cap() _NOEXCEPT
350 {return __end_cap_.first();}
351 _LIBCPP_INLINE_VISIBILITY
352 const pointer& __end_cap() const _NOEXCEPT
353 {return __end_cap_.first();}
355 _LIBCPP_INLINE_VISIBILITY
357 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
358 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
361 _LIBCPP_INLINE_VISIBILITY
362 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
363 _LIBCPP_INLINE_VISIBILITY
364 size_type capacity() const _NOEXCEPT
365 {return static_cast<size_type>(__end_cap() - __begin_);}
367 _LIBCPP_INLINE_VISIBILITY
368 void __destruct_at_end(pointer __new_last) _NOEXCEPT;
370 _LIBCPP_INLINE_VISIBILITY
371 void __copy_assign_alloc(const __vector_base& __c)
372 {__copy_assign_alloc(__c, integral_constant<bool,
373 __alloc_traits::propagate_on_container_copy_assignment::value>());}
375 _LIBCPP_INLINE_VISIBILITY
376 void __move_assign_alloc(__vector_base& __c)
378 !__alloc_traits::propagate_on_container_move_assignment::value ||
379 is_nothrow_move_assignable<allocator_type>::value)
380 {__move_assign_alloc(__c, integral_constant<bool,
381 __alloc_traits::propagate_on_container_move_assignment::value>());}
383 _LIBCPP_INLINE_VISIBILITY
384 static void __swap_alloc(allocator_type& __x, allocator_type& __y)
386 !__alloc_traits::propagate_on_container_swap::value ||
387 __is_nothrow_swappable<allocator_type>::value)
388 {__swap_alloc(__x, __y, integral_constant<bool,
389 __alloc_traits::propagate_on_container_swap::value>());}
391 _LIBCPP_INLINE_VISIBILITY
392 void __copy_assign_alloc(const __vector_base& __c, true_type)
394 if (__alloc() != __c.__alloc())
397 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
398 __begin_ = __end_ = __end_cap() = nullptr;
400 __alloc() = __c.__alloc();
403 _LIBCPP_INLINE_VISIBILITY
404 void __copy_assign_alloc(const __vector_base&, false_type)
407 _LIBCPP_INLINE_VISIBILITY
408 void __move_assign_alloc(__vector_base& __c, true_type)
409 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
411 __alloc() = _VSTD::move(__c.__alloc());
414 _LIBCPP_INLINE_VISIBILITY
415 void __move_assign_alloc(__vector_base&, false_type)
419 _LIBCPP_INLINE_VISIBILITY
420 static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type)
421 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
426 _LIBCPP_INLINE_VISIBILITY
427 static void __swap_alloc(allocator_type&, allocator_type&, false_type)
432 template <class _Tp, class _Allocator>
433 _LIBCPP_INLINE_VISIBILITY inline
435 __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
437 while (__new_last != __end_)
438 __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_));
441 template <class _Tp, class _Allocator>
442 _LIBCPP_INLINE_VISIBILITY inline
443 __vector_base<_Tp, _Allocator>::__vector_base()
444 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
451 template <class _Tp, class _Allocator>
452 _LIBCPP_INLINE_VISIBILITY inline
453 __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
456 __end_cap_(nullptr, __a)
460 template <class _Tp, class _Allocator>
461 __vector_base<_Tp, _Allocator>::~__vector_base()
463 if (__begin_ != nullptr)
466 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
470 template <class _Tp, class _Allocator = allocator<_Tp> >
471 class _LIBCPP_TYPE_VIS vector
472 : private __vector_base<_Tp, _Allocator>
475 typedef __vector_base<_Tp, _Allocator> __base;
477 typedef vector __self;
478 typedef _Tp value_type;
479 typedef _Allocator allocator_type;
480 typedef typename __base::__alloc_traits __alloc_traits;
481 typedef typename __base::reference reference;
482 typedef typename __base::const_reference const_reference;
483 typedef typename __base::size_type size_type;
484 typedef typename __base::difference_type difference_type;
485 typedef typename __base::pointer pointer;
486 typedef typename __base::const_pointer const_pointer;
487 typedef __wrap_iter<pointer> iterator;
488 typedef __wrap_iter<const_pointer> const_iterator;
489 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
490 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
492 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
493 "Allocator::value_type must be same type as value_type");
495 _LIBCPP_INLINE_VISIBILITY
497 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
499 #if _LIBCPP_DEBUG_LEVEL >= 2
500 __get_db()->__insert_c(this);
503 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
506 #if _LIBCPP_DEBUG_LEVEL >= 2
507 __get_db()->__insert_c(this);
510 explicit vector(size_type __n);
511 vector(size_type __n, const_reference __x);
512 vector(size_type __n, const_reference __x, const allocator_type& __a);
513 template <class _InputIterator>
514 vector(_InputIterator __first, _InputIterator __last,
515 typename enable_if<__is_input_iterator <_InputIterator>::value &&
516 !__is_forward_iterator<_InputIterator>::value &&
519 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
520 template <class _InputIterator>
521 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
522 typename enable_if<__is_input_iterator <_InputIterator>::value &&
523 !__is_forward_iterator<_InputIterator>::value &&
526 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
527 template <class _ForwardIterator>
528 vector(_ForwardIterator __first, _ForwardIterator __last,
529 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
532 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
533 template <class _ForwardIterator>
534 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
535 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
538 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
539 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
540 _LIBCPP_INLINE_VISIBILITY
541 vector(initializer_list<value_type> __il);
542 _LIBCPP_INLINE_VISIBILITY
543 vector(initializer_list<value_type> __il, const allocator_type& __a);
544 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
545 #if _LIBCPP_DEBUG_LEVEL >= 2
546 _LIBCPP_INLINE_VISIBILITY
549 __get_db()->__erase_c(this);
553 vector(const vector& __x);
554 vector(const vector& __x, const allocator_type& __a);
555 _LIBCPP_INLINE_VISIBILITY
556 vector& operator=(const vector& __x);
557 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
558 _LIBCPP_INLINE_VISIBILITY
560 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
561 _LIBCPP_INLINE_VISIBILITY
562 vector(vector&& __x, const allocator_type& __a);
563 _LIBCPP_INLINE_VISIBILITY
564 vector& operator=(vector&& __x)
566 __alloc_traits::propagate_on_container_move_assignment::value &&
567 is_nothrow_move_assignable<allocator_type>::value);
568 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
569 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
570 _LIBCPP_INLINE_VISIBILITY
571 vector& operator=(initializer_list<value_type> __il)
572 {assign(__il.begin(), __il.end()); return *this;}
573 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
575 template <class _InputIterator>
578 __is_input_iterator <_InputIterator>::value &&
579 !__is_forward_iterator<_InputIterator>::value &&
582 typename iterator_traits<_InputIterator>::reference>::value,
585 assign(_InputIterator __first, _InputIterator __last);
586 template <class _ForwardIterator>
589 __is_forward_iterator<_ForwardIterator>::value &&
592 typename iterator_traits<_ForwardIterator>::reference>::value,
595 assign(_ForwardIterator __first, _ForwardIterator __last);
597 void assign(size_type __n, const_reference __u);
598 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
599 _LIBCPP_INLINE_VISIBILITY
600 void assign(initializer_list<value_type> __il)
601 {assign(__il.begin(), __il.end());}
602 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
604 _LIBCPP_INLINE_VISIBILITY
605 allocator_type get_allocator() const _NOEXCEPT
606 {return this->__alloc();}
608 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
609 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
610 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
611 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
613 _LIBCPP_INLINE_VISIBILITY
614 reverse_iterator rbegin() _NOEXCEPT
615 {return reverse_iterator(end());}
616 _LIBCPP_INLINE_VISIBILITY
617 const_reverse_iterator rbegin() const _NOEXCEPT
618 {return const_reverse_iterator(end());}
619 _LIBCPP_INLINE_VISIBILITY
620 reverse_iterator rend() _NOEXCEPT
621 {return reverse_iterator(begin());}
622 _LIBCPP_INLINE_VISIBILITY
623 const_reverse_iterator rend() const _NOEXCEPT
624 {return const_reverse_iterator(begin());}
626 _LIBCPP_INLINE_VISIBILITY
627 const_iterator cbegin() const _NOEXCEPT
629 _LIBCPP_INLINE_VISIBILITY
630 const_iterator cend() const _NOEXCEPT
632 _LIBCPP_INLINE_VISIBILITY
633 const_reverse_iterator crbegin() const _NOEXCEPT
635 _LIBCPP_INLINE_VISIBILITY
636 const_reverse_iterator crend() const _NOEXCEPT
639 _LIBCPP_INLINE_VISIBILITY
640 size_type size() const _NOEXCEPT
641 {return static_cast<size_type>(this->__end_ - this->__begin_);}
642 _LIBCPP_INLINE_VISIBILITY
643 size_type capacity() const _NOEXCEPT
644 {return __base::capacity();}
645 _LIBCPP_INLINE_VISIBILITY
646 bool empty() const _NOEXCEPT
647 {return this->__begin_ == this->__end_;}
648 size_type max_size() const _NOEXCEPT;
649 void reserve(size_type __n);
650 void shrink_to_fit() _NOEXCEPT;
652 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n);
653 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const;
654 reference at(size_type __n);
655 const_reference at(size_type __n) const;
657 _LIBCPP_INLINE_VISIBILITY reference front()
659 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
660 return *this->__begin_;
662 _LIBCPP_INLINE_VISIBILITY const_reference front() const
664 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
665 return *this->__begin_;
667 _LIBCPP_INLINE_VISIBILITY reference back()
669 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
670 return *(this->__end_ - 1);
672 _LIBCPP_INLINE_VISIBILITY const_reference back() const
674 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
675 return *(this->__end_ - 1);
678 _LIBCPP_INLINE_VISIBILITY
679 value_type* data() _NOEXCEPT
680 {return _VSTD::__to_raw_pointer(this->__begin_);}
681 _LIBCPP_INLINE_VISIBILITY
682 const value_type* data() const _NOEXCEPT
683 {return _VSTD::__to_raw_pointer(this->__begin_);}
685 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
686 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
687 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
688 #ifndef _LIBCPP_HAS_NO_VARIADICS
689 template <class... _Args>
690 void emplace_back(_Args&&... __args);
691 #endif // _LIBCPP_HAS_NO_VARIADICS
692 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
695 iterator insert(const_iterator __position, const_reference __x);
696 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
697 iterator insert(const_iterator __position, value_type&& __x);
698 #ifndef _LIBCPP_HAS_NO_VARIADICS
699 template <class... _Args>
700 iterator emplace(const_iterator __position, _Args&&... __args);
701 #endif // _LIBCPP_HAS_NO_VARIADICS
702 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
703 iterator insert(const_iterator __position, size_type __n, const_reference __x);
704 template <class _InputIterator>
707 __is_input_iterator <_InputIterator>::value &&
708 !__is_forward_iterator<_InputIterator>::value &&
711 typename iterator_traits<_InputIterator>::reference>::value,
714 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
715 template <class _ForwardIterator>
718 __is_forward_iterator<_ForwardIterator>::value &&
721 typename iterator_traits<_ForwardIterator>::reference>::value,
724 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
725 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
726 _LIBCPP_INLINE_VISIBILITY
727 iterator insert(const_iterator __position, initializer_list<value_type> __il)
728 {return insert(__position, __il.begin(), __il.end());}
729 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
731 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
732 iterator erase(const_iterator __first, const_iterator __last);
734 _LIBCPP_INLINE_VISIBILITY
735 void clear() _NOEXCEPT
738 __invalidate_all_iterators();
741 void resize(size_type __sz);
742 void resize(size_type __sz, const_reference __x);
745 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
746 __is_nothrow_swappable<allocator_type>::value);
748 bool __invariants() const;
750 #if _LIBCPP_DEBUG_LEVEL >= 2
752 bool __dereferenceable(const const_iterator* __i) const;
753 bool __decrementable(const const_iterator* __i) const;
754 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
755 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
757 #endif // _LIBCPP_DEBUG_LEVEL >= 2
760 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
761 void allocate(size_type __n);
762 void deallocate() _NOEXCEPT;
763 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
764 void __construct_at_end(size_type __n);
765 void __construct_at_end(size_type __n, const_reference __x);
766 template <class _ForwardIterator>
769 __is_forward_iterator<_ForwardIterator>::value,
772 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
773 void __move_construct_at_end(pointer __first, pointer __last);
774 void __append(size_type __n);
775 void __append(size_type __n, const_reference __x);
776 _LIBCPP_INLINE_VISIBILITY
777 iterator __make_iter(pointer __p) _NOEXCEPT;
778 _LIBCPP_INLINE_VISIBILITY
779 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
780 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
781 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
782 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
783 void __move_assign(vector& __c, true_type)
784 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
785 void __move_assign(vector& __c, false_type);
786 _LIBCPP_INLINE_VISIBILITY
787 void __destruct_at_end(pointer __new_last) _NOEXCEPT
789 #if _LIBCPP_DEBUG_LEVEL >= 2
790 __c_node* __c = __get_db()->__find_c_and_lock(this);
791 for (__i_node** __p = __c->end_; __p != __c->beg_; )
794 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
795 if (__i->base() > __new_last)
797 (*__p)->__c_ = nullptr;
798 if (--__c->end_ != __p)
799 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
802 __get_db()->unlock();
804 __base::__destruct_at_end(__new_last);
808 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
809 __push_back_slow_path(_Up&& __x);
811 __push_back_slow_path(_Up& __x);
813 #if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
814 template <class... _Args>
816 __emplace_back_slow_path(_Args&&... __args);
820 template <class _Tp, class _Allocator>
822 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
824 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
825 _VSTD::swap(this->__begin_, __v.__begin_);
826 _VSTD::swap(this->__end_, __v.__end_);
827 _VSTD::swap(this->__end_cap(), __v.__end_cap());
828 __v.__first_ = __v.__begin_;
829 __invalidate_all_iterators();
832 template <class _Tp, class _Allocator>
833 typename vector<_Tp, _Allocator>::pointer
834 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
836 pointer __r = __v.__begin_;
837 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
838 __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
839 _VSTD::swap(this->__begin_, __v.__begin_);
840 _VSTD::swap(this->__end_, __v.__end_);
841 _VSTD::swap(this->__end_cap(), __v.__end_cap());
842 __v.__first_ = __v.__begin_;
843 __invalidate_all_iterators();
847 // Allocate space for __n objects
848 // throws length_error if __n > max_size()
849 // throws (probably bad_alloc) if memory run out
850 // Precondition: __begin_ == __end_ == __end_cap() == 0
851 // Precondition: __n > 0
852 // Postcondition: capacity() == __n
853 // Postcondition: size() == 0
854 template <class _Tp, class _Allocator>
856 vector<_Tp, _Allocator>::allocate(size_type __n)
858 if (__n > max_size())
859 this->__throw_length_error();
860 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
861 this->__end_cap() = this->__begin_ + __n;
864 template <class _Tp, class _Allocator>
866 vector<_Tp, _Allocator>::deallocate() _NOEXCEPT
868 if (this->__begin_ != nullptr)
871 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
872 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
876 template <class _Tp, class _Allocator>
877 typename vector<_Tp, _Allocator>::size_type
878 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
880 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always
883 // Precondition: __new_size > capacity()
884 template <class _Tp, class _Allocator>
885 _LIBCPP_INLINE_VISIBILITY inline
886 typename vector<_Tp, _Allocator>::size_type
887 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
889 const size_type __ms = max_size();
890 if (__new_size > __ms)
891 this->__throw_length_error();
892 const size_type __cap = capacity();
893 if (__cap >= __ms / 2)
895 return _VSTD::max<size_type>(2*__cap, __new_size);
898 // Default constructs __n objects starting at __end_
899 // throws if construction throws
900 // Precondition: __n > 0
901 // Precondition: size() + __n <= capacity()
902 // Postcondition: size() == size() + __n
903 template <class _Tp, class _Allocator>
905 vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
907 allocator_type& __a = this->__alloc();
910 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
916 // Copy constructs __n objects starting at __end_ from __x
917 // throws if construction throws
918 // Precondition: __n > 0
919 // Precondition: size() + __n <= capacity()
920 // Postcondition: size() == old size() + __n
921 // Postcondition: [i] == __x for all i in [size() - __n, __n)
922 template <class _Tp, class _Allocator>
923 _LIBCPP_INLINE_VISIBILITY inline
925 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
927 allocator_type& __a = this->__alloc();
930 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
936 template <class _Tp, class _Allocator>
937 template <class _ForwardIterator>
940 __is_forward_iterator<_ForwardIterator>::value,
943 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
945 allocator_type& __a = this->__alloc();
946 for (; __first != __last; ++__first)
948 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
953 template <class _Tp, class _Allocator>
955 vector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last)
957 allocator_type& __a = this->__alloc();
958 for (; __first != __last; ++__first)
960 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
961 _VSTD::move(*__first));
966 // Default constructs __n objects starting at __end_
967 // throws if construction throws
968 // Postcondition: size() == size() + __n
969 // Exception safety: strong.
970 template <class _Tp, class _Allocator>
972 vector<_Tp, _Allocator>::__append(size_type __n)
974 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
975 this->__construct_at_end(__n);
978 allocator_type& __a = this->__alloc();
979 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
980 __v.__construct_at_end(__n);
981 __swap_out_circular_buffer(__v);
985 // Default constructs __n objects starting at __end_
986 // throws if construction throws
987 // Postcondition: size() == size() + __n
988 // Exception safety: strong.
989 template <class _Tp, class _Allocator>
991 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
993 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
994 this->__construct_at_end(__n, __x);
997 allocator_type& __a = this->__alloc();
998 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
999 __v.__construct_at_end(__n, __x);
1000 __swap_out_circular_buffer(__v);
1004 template <class _Tp, class _Allocator>
1005 vector<_Tp, _Allocator>::vector(size_type __n)
1007 #if _LIBCPP_DEBUG_LEVEL >= 2
1008 __get_db()->__insert_c(this);
1013 __construct_at_end(__n);
1017 template <class _Tp, class _Allocator>
1018 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x)
1020 #if _LIBCPP_DEBUG_LEVEL >= 2
1021 __get_db()->__insert_c(this);
1026 __construct_at_end(__n, __x);
1030 template <class _Tp, class _Allocator>
1031 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a)
1034 #if _LIBCPP_DEBUG_LEVEL >= 2
1035 __get_db()->__insert_c(this);
1040 __construct_at_end(__n, __x);
1044 template <class _Tp, class _Allocator>
1045 template <class _InputIterator>
1046 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
1047 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1048 !__is_forward_iterator<_InputIterator>::value &&
1051 typename iterator_traits<_InputIterator>::reference>::value>::type*)
1053 #if _LIBCPP_DEBUG_LEVEL >= 2
1054 __get_db()->__insert_c(this);
1056 for (; __first != __last; ++__first)
1057 push_back(*__first);
1060 template <class _Tp, class _Allocator>
1061 template <class _InputIterator>
1062 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1063 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1064 !__is_forward_iterator<_InputIterator>::value &&
1067 typename iterator_traits<_InputIterator>::reference>::value>::type*)
1070 #if _LIBCPP_DEBUG_LEVEL >= 2
1071 __get_db()->__insert_c(this);
1073 for (; __first != __last; ++__first)
1074 push_back(*__first);
1077 template <class _Tp, class _Allocator>
1078 template <class _ForwardIterator>
1079 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
1080 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1083 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
1085 #if _LIBCPP_DEBUG_LEVEL >= 2
1086 __get_db()->__insert_c(this);
1088 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1092 __construct_at_end(__first, __last);
1096 template <class _Tp, class _Allocator>
1097 template <class _ForwardIterator>
1098 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
1099 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1102 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
1105 #if _LIBCPP_DEBUG_LEVEL >= 2
1106 __get_db()->__insert_c(this);
1108 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1112 __construct_at_end(__first, __last);
1116 template <class _Tp, class _Allocator>
1117 vector<_Tp, _Allocator>::vector(const vector& __x)
1118 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1120 #if _LIBCPP_DEBUG_LEVEL >= 2
1121 __get_db()->__insert_c(this);
1123 size_type __n = __x.size();
1127 __construct_at_end(__x.__begin_, __x.__end_);
1131 template <class _Tp, class _Allocator>
1132 vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1135 #if _LIBCPP_DEBUG_LEVEL >= 2
1136 __get_db()->__insert_c(this);
1138 size_type __n = __x.size();
1142 __construct_at_end(__x.__begin_, __x.__end_);
1146 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1148 template <class _Tp, class _Allocator>
1149 _LIBCPP_INLINE_VISIBILITY inline
1150 vector<_Tp, _Allocator>::vector(vector&& __x)
1151 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1152 : __base(_VSTD::move(__x.__alloc()))
1154 #if _LIBCPP_DEBUG_LEVEL >= 2
1155 __get_db()->__insert_c(this);
1156 __get_db()->swap(this, &__x);
1158 this->__begin_ = __x.__begin_;
1159 this->__end_ = __x.__end_;
1160 this->__end_cap() = __x.__end_cap();
1161 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1164 template <class _Tp, class _Allocator>
1165 _LIBCPP_INLINE_VISIBILITY inline
1166 vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1169 #if _LIBCPP_DEBUG_LEVEL >= 2
1170 __get_db()->__insert_c(this);
1172 if (__a == __x.__alloc())
1174 this->__begin_ = __x.__begin_;
1175 this->__end_ = __x.__end_;
1176 this->__end_cap() = __x.__end_cap();
1177 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1178 #if _LIBCPP_DEBUG_LEVEL >= 2
1179 __get_db()->swap(this, &__x);
1184 typedef move_iterator<iterator> _Ip;
1185 assign(_Ip(__x.begin()), _Ip(__x.end()));
1189 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1191 template <class _Tp, class _Allocator>
1192 _LIBCPP_INLINE_VISIBILITY inline
1193 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1195 #if _LIBCPP_DEBUG_LEVEL >= 2
1196 __get_db()->__insert_c(this);
1198 if (__il.size() > 0)
1200 allocate(__il.size());
1201 __construct_at_end(__il.begin(), __il.end());
1205 template <class _Tp, class _Allocator>
1206 _LIBCPP_INLINE_VISIBILITY inline
1207 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1210 #if _LIBCPP_DEBUG_LEVEL >= 2
1211 __get_db()->__insert_c(this);
1213 if (__il.size() > 0)
1215 allocate(__il.size());
1216 __construct_at_end(__il.begin(), __il.end());
1220 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1222 template <class _Tp, class _Allocator>
1223 _LIBCPP_INLINE_VISIBILITY inline
1224 vector<_Tp, _Allocator>&
1225 vector<_Tp, _Allocator>::operator=(vector&& __x)
1227 __alloc_traits::propagate_on_container_move_assignment::value &&
1228 is_nothrow_move_assignable<allocator_type>::value)
1230 __move_assign(__x, integral_constant<bool,
1231 __alloc_traits::propagate_on_container_move_assignment::value>());
1235 template <class _Tp, class _Allocator>
1237 vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1239 if (__base::__alloc() != __c.__alloc())
1241 typedef move_iterator<iterator> _Ip;
1242 assign(_Ip(__c.begin()), _Ip(__c.end()));
1245 __move_assign(__c, true_type());
1248 template <class _Tp, class _Allocator>
1250 vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1251 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1254 this->__begin_ = __c.__begin_;
1255 this->__end_ = __c.__end_;
1256 this->__end_cap() = __c.__end_cap();
1257 __base::__move_assign_alloc(__c);
1258 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1259 #if _LIBCPP_DEBUG_LEVEL >= 2
1260 __get_db()->swap(this, &__c);
1264 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1266 template <class _Tp, class _Allocator>
1267 _LIBCPP_INLINE_VISIBILITY inline
1268 vector<_Tp, _Allocator>&
1269 vector<_Tp, _Allocator>::operator=(const vector& __x)
1273 __base::__copy_assign_alloc(__x);
1274 assign(__x.__begin_, __x.__end_);
1279 template <class _Tp, class _Allocator>
1280 template <class _InputIterator>
1283 __is_input_iterator <_InputIterator>::value &&
1284 !__is_forward_iterator<_InputIterator>::value &&
1287 typename iterator_traits<_InputIterator>::reference>::value,
1290 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1293 for (; __first != __last; ++__first)
1294 push_back(*__first);
1297 template <class _Tp, class _Allocator>
1298 template <class _ForwardIterator>
1301 __is_forward_iterator<_ForwardIterator>::value &&
1304 typename iterator_traits<_ForwardIterator>::reference>::value,
1307 vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1309 typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last);
1310 if (static_cast<size_type>(__new_size) <= capacity())
1312 _ForwardIterator __mid = __last;
1313 bool __growing = false;
1314 if (static_cast<size_type>(__new_size) > size())
1318 _VSTD::advance(__mid, size());
1320 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
1322 __construct_at_end(__mid, __last);
1324 this->__destruct_at_end(__m);
1329 allocate(__recommend(static_cast<size_type>(__new_size)));
1330 __construct_at_end(__first, __last);
1334 template <class _Tp, class _Allocator>
1336 vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1338 if (__n <= capacity())
1340 size_type __s = size();
1341 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
1343 __construct_at_end(__n - __s, __u);
1345 this->__destruct_at_end(this->__begin_ + __n);
1350 allocate(__recommend(static_cast<size_type>(__n)));
1351 __construct_at_end(__n, __u);
1355 template <class _Tp, class _Allocator>
1356 _LIBCPP_INLINE_VISIBILITY inline
1357 typename vector<_Tp, _Allocator>::iterator
1358 vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
1360 #if _LIBCPP_DEBUG_LEVEL >= 2
1361 return iterator(this, __p);
1363 return iterator(__p);
1367 template <class _Tp, class _Allocator>
1368 _LIBCPP_INLINE_VISIBILITY inline
1369 typename vector<_Tp, _Allocator>::const_iterator
1370 vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
1372 #if _LIBCPP_DEBUG_LEVEL >= 2
1373 return const_iterator(this, __p);
1375 return const_iterator(__p);
1379 template <class _Tp, class _Allocator>
1380 _LIBCPP_INLINE_VISIBILITY inline
1381 typename vector<_Tp, _Allocator>::iterator
1382 vector<_Tp, _Allocator>::begin() _NOEXCEPT
1384 return __make_iter(this->__begin_);
1387 template <class _Tp, class _Allocator>
1388 _LIBCPP_INLINE_VISIBILITY inline
1389 typename vector<_Tp, _Allocator>::const_iterator
1390 vector<_Tp, _Allocator>::begin() const _NOEXCEPT
1392 return __make_iter(this->__begin_);
1395 template <class _Tp, class _Allocator>
1396 _LIBCPP_INLINE_VISIBILITY inline
1397 typename vector<_Tp, _Allocator>::iterator
1398 vector<_Tp, _Allocator>::end() _NOEXCEPT
1400 return __make_iter(this->__end_);
1403 template <class _Tp, class _Allocator>
1404 _LIBCPP_INLINE_VISIBILITY inline
1405 typename vector<_Tp, _Allocator>::const_iterator
1406 vector<_Tp, _Allocator>::end() const _NOEXCEPT
1408 return __make_iter(this->__end_);
1411 template <class _Tp, class _Allocator>
1412 _LIBCPP_INLINE_VISIBILITY inline
1413 typename vector<_Tp, _Allocator>::reference
1414 vector<_Tp, _Allocator>::operator[](size_type __n)
1416 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1417 return this->__begin_[__n];
1420 template <class _Tp, class _Allocator>
1421 _LIBCPP_INLINE_VISIBILITY inline
1422 typename vector<_Tp, _Allocator>::const_reference
1423 vector<_Tp, _Allocator>::operator[](size_type __n) const
1425 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1426 return this->__begin_[__n];
1429 template <class _Tp, class _Allocator>
1430 typename vector<_Tp, _Allocator>::reference
1431 vector<_Tp, _Allocator>::at(size_type __n)
1434 this->__throw_out_of_range();
1435 return this->__begin_[__n];
1438 template <class _Tp, class _Allocator>
1439 typename vector<_Tp, _Allocator>::const_reference
1440 vector<_Tp, _Allocator>::at(size_type __n) const
1443 this->__throw_out_of_range();
1444 return this->__begin_[__n];
1447 template <class _Tp, class _Allocator>
1449 vector<_Tp, _Allocator>::reserve(size_type __n)
1451 if (__n > capacity())
1453 allocator_type& __a = this->__alloc();
1454 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1455 __swap_out_circular_buffer(__v);
1459 template <class _Tp, class _Allocator>
1461 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1463 if (capacity() > size())
1465 #ifndef _LIBCPP_NO_EXCEPTIONS
1468 #endif // _LIBCPP_NO_EXCEPTIONS
1469 allocator_type& __a = this->__alloc();
1470 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1471 __swap_out_circular_buffer(__v);
1472 #ifndef _LIBCPP_NO_EXCEPTIONS
1477 #endif // _LIBCPP_NO_EXCEPTIONS
1481 template <class _Tp, class _Allocator>
1482 template <class _Up>
1484 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1485 vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1487 vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1490 allocator_type& __a = this->__alloc();
1491 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1492 // __v.push_back(_VSTD::forward<_Up>(__x));
1493 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
1495 __swap_out_circular_buffer(__v);
1498 template <class _Tp, class _Allocator>
1499 _LIBCPP_INLINE_VISIBILITY inline
1501 vector<_Tp, _Allocator>::push_back(const_reference __x)
1503 if (this->__end_ != this->__end_cap())
1505 __alloc_traits::construct(this->__alloc(),
1506 _VSTD::__to_raw_pointer(this->__end_), __x);
1510 __push_back_slow_path(__x);
1513 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1515 template <class _Tp, class _Allocator>
1516 _LIBCPP_INLINE_VISIBILITY inline
1518 vector<_Tp, _Allocator>::push_back(value_type&& __x)
1520 if (this->__end_ < this->__end_cap())
1522 __alloc_traits::construct(this->__alloc(),
1523 _VSTD::__to_raw_pointer(this->__end_),
1528 __push_back_slow_path(_VSTD::move(__x));
1531 #ifndef _LIBCPP_HAS_NO_VARIADICS
1533 template <class _Tp, class _Allocator>
1534 template <class... _Args>
1536 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1538 allocator_type& __a = this->__alloc();
1539 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1540 // __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1541 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
1543 __swap_out_circular_buffer(__v);
1546 template <class _Tp, class _Allocator>
1547 template <class... _Args>
1548 _LIBCPP_INLINE_VISIBILITY inline
1550 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1552 if (this->__end_ < this->__end_cap())
1554 __alloc_traits::construct(this->__alloc(),
1555 _VSTD::__to_raw_pointer(this->__end_),
1556 _VSTD::forward<_Args>(__args)...);
1560 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
1563 #endif // _LIBCPP_HAS_NO_VARIADICS
1564 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1566 template <class _Tp, class _Allocator>
1567 _LIBCPP_INLINE_VISIBILITY inline
1569 vector<_Tp, _Allocator>::pop_back()
1571 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1572 this->__destruct_at_end(this->__end_ - 1);
1575 template <class _Tp, class _Allocator>
1576 _LIBCPP_INLINE_VISIBILITY inline
1577 typename vector<_Tp, _Allocator>::iterator
1578 vector<_Tp, _Allocator>::erase(const_iterator __position)
1580 #if _LIBCPP_DEBUG_LEVEL >= 2
1581 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1582 "vector::erase(iterator) called with an iterator not"
1583 " referring to this vector");
1585 _LIBCPP_ASSERT(__position != end(),
1586 "vector::erase(iterator) called with a non-dereferenceable iterator");
1587 difference_type __ps = __position - cbegin();
1588 pointer __p = this->__begin_ + __ps;
1589 iterator __r = __make_iter(__p);
1590 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1594 template <class _Tp, class _Allocator>
1595 typename vector<_Tp, _Allocator>::iterator
1596 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1598 #if _LIBCPP_DEBUG_LEVEL >= 2
1599 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1600 "vector::erase(iterator, iterator) called with an iterator not"
1601 " referring to this vector");
1603 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1604 pointer __p = this->__begin_ + (__first - begin());
1605 iterator __r = __make_iter(__p);
1606 if (__first != __last)
1607 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1611 template <class _Tp, class _Allocator>
1613 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1615 pointer __old_last = this->__end_;
1616 difference_type __n = __old_last - __to;
1617 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1618 __alloc_traits::construct(this->__alloc(),
1619 _VSTD::__to_raw_pointer(this->__end_),
1621 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1624 template <class _Tp, class _Allocator>
1625 typename vector<_Tp, _Allocator>::iterator
1626 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1628 #if _LIBCPP_DEBUG_LEVEL >= 2
1629 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1630 "vector::insert(iterator, x) called with an iterator not"
1631 " referring to this vector");
1633 pointer __p = this->__begin_ + (__position - begin());
1634 if (this->__end_ < this->__end_cap())
1636 if (__p == this->__end_)
1638 __alloc_traits::construct(this->__alloc(),
1639 _VSTD::__to_raw_pointer(this->__end_), __x);
1644 __move_range(__p, this->__end_, __p + 1);
1645 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1646 if (__p <= __xr && __xr < this->__end_)
1653 allocator_type& __a = this->__alloc();
1654 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1656 __p = __swap_out_circular_buffer(__v, __p);
1658 return __make_iter(__p);
1661 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1663 template <class _Tp, class _Allocator>
1664 typename vector<_Tp, _Allocator>::iterator
1665 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1667 #if _LIBCPP_DEBUG_LEVEL >= 2
1668 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1669 "vector::insert(iterator, x) called with an iterator not"
1670 " referring to this vector");
1672 pointer __p = this->__begin_ + (__position - begin());
1673 if (this->__end_ < this->__end_cap())
1675 if (__p == this->__end_)
1677 __alloc_traits::construct(this->__alloc(),
1678 _VSTD::__to_raw_pointer(this->__end_),
1684 __move_range(__p, this->__end_, __p + 1);
1685 *__p = _VSTD::move(__x);
1690 allocator_type& __a = this->__alloc();
1691 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1692 __v.push_back(_VSTD::move(__x));
1693 __p = __swap_out_circular_buffer(__v, __p);
1695 return __make_iter(__p);
1698 #ifndef _LIBCPP_HAS_NO_VARIADICS
1700 template <class _Tp, class _Allocator>
1701 template <class... _Args>
1702 typename vector<_Tp, _Allocator>::iterator
1703 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1705 #if _LIBCPP_DEBUG_LEVEL >= 2
1706 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1707 "vector::emplace(iterator, x) called with an iterator not"
1708 " referring to this vector");
1710 pointer __p = this->__begin_ + (__position - begin());
1711 if (this->__end_ < this->__end_cap())
1713 if (__p == this->__end_)
1715 __alloc_traits::construct(this->__alloc(),
1716 _VSTD::__to_raw_pointer(this->__end_),
1717 _VSTD::forward<_Args>(__args)...);
1722 value_type __tmp(_VSTD::forward<_Args>(__args)...);
1723 __move_range(__p, this->__end_, __p + 1);
1724 *__p = _VSTD::move(__tmp);
1729 allocator_type& __a = this->__alloc();
1730 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1731 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1732 __p = __swap_out_circular_buffer(__v, __p);
1734 return __make_iter(__p);
1737 #endif // _LIBCPP_HAS_NO_VARIADICS
1738 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1740 template <class _Tp, class _Allocator>
1741 typename vector<_Tp, _Allocator>::iterator
1742 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1744 #if _LIBCPP_DEBUG_LEVEL >= 2
1745 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1746 "vector::insert(iterator, n, x) called with an iterator not"
1747 " referring to this vector");
1749 pointer __p = this->__begin_ + (__position - begin());
1752 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1754 size_type __old_n = __n;
1755 pointer __old_last = this->__end_;
1756 if (__n > static_cast<size_type>(this->__end_ - __p))
1758 size_type __cx = __n - (this->__end_ - __p);
1759 __construct_at_end(__cx, __x);
1764 __move_range(__p, __old_last, __p + __old_n);
1765 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1766 if (__p <= __xr && __xr < this->__end_)
1768 _VSTD::fill_n(__p, __n, *__xr);
1773 allocator_type& __a = this->__alloc();
1774 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1775 __v.__construct_at_end(__n, __x);
1776 __p = __swap_out_circular_buffer(__v, __p);
1779 return __make_iter(__p);
1782 template <class _Tp, class _Allocator>
1783 template <class _InputIterator>
1786 __is_input_iterator <_InputIterator>::value &&
1787 !__is_forward_iterator<_InputIterator>::value &&
1790 typename iterator_traits<_InputIterator>::reference>::value,
1791 typename vector<_Tp, _Allocator>::iterator
1793 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1795 #if _LIBCPP_DEBUG_LEVEL >= 2
1796 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1797 "vector::insert(iterator, range) called with an iterator not"
1798 " referring to this vector");
1800 difference_type __off = __position - begin();
1801 pointer __p = this->__begin_ + __off;
1802 allocator_type& __a = this->__alloc();
1803 pointer __old_last = this->__end_;
1804 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1806 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
1810 __split_buffer<value_type, allocator_type&> __v(__a);
1811 if (__first != __last)
1813 #ifndef _LIBCPP_NO_EXCEPTIONS
1816 #endif // _LIBCPP_NO_EXCEPTIONS
1817 __v.__construct_at_end(__first, __last);
1818 difference_type __old_size = __old_last - this->__begin_;
1819 difference_type __old_p = __p - this->__begin_;
1820 reserve(__recommend(size() + __v.size()));
1821 __p = this->__begin_ + __old_p;
1822 __old_last = this->__begin_ + __old_size;
1823 #ifndef _LIBCPP_NO_EXCEPTIONS
1827 erase(__make_iter(__old_last), end());
1830 #endif // _LIBCPP_NO_EXCEPTIONS
1832 __p = _VSTD::rotate(__p, __old_last, this->__end_);
1833 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1834 make_move_iterator(__v.end()));
1835 return begin() + __off;
1838 template <class _Tp, class _Allocator>
1839 template <class _ForwardIterator>
1842 __is_forward_iterator<_ForwardIterator>::value &&
1845 typename iterator_traits<_ForwardIterator>::reference>::value,
1846 typename vector<_Tp, _Allocator>::iterator
1848 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1850 #if _LIBCPP_DEBUG_LEVEL >= 2
1851 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1852 "vector::insert(iterator, range) called with an iterator not"
1853 " referring to this vector");
1855 pointer __p = this->__begin_ + (__position - begin());
1856 difference_type __n = _VSTD::distance(__first, __last);
1859 if (__n <= this->__end_cap() - this->__end_)
1861 size_type __old_n = __n;
1862 pointer __old_last = this->__end_;
1863 _ForwardIterator __m = __last;
1864 difference_type __dx = this->__end_ - __p;
1868 _VSTD::advance(__m, this->__end_ - __p);
1869 __construct_at_end(__m, __last);
1874 __move_range(__p, __old_last, __p + __old_n);
1875 _VSTD::copy(__first, __m, __p);
1880 allocator_type& __a = this->__alloc();
1881 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1882 __v.__construct_at_end(__first, __last);
1883 __p = __swap_out_circular_buffer(__v, __p);
1886 return __make_iter(__p);
1889 template <class _Tp, class _Allocator>
1891 vector<_Tp, _Allocator>::resize(size_type __sz)
1893 size_type __cs = size();
1895 this->__append(__sz - __cs);
1896 else if (__cs > __sz)
1897 this->__destruct_at_end(this->__begin_ + __sz);
1900 template <class _Tp, class _Allocator>
1902 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
1904 size_type __cs = size();
1906 this->__append(__sz - __cs, __x);
1907 else if (__cs > __sz)
1908 this->__destruct_at_end(this->__begin_ + __sz);
1911 template <class _Tp, class _Allocator>
1913 vector<_Tp, _Allocator>::swap(vector& __x)
1914 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1915 __is_nothrow_swappable<allocator_type>::value)
1917 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
1918 this->__alloc() == __x.__alloc(),
1919 "vector::swap: Either propagate_on_container_swap must be true"
1920 " or the allocators must compare equal");
1921 _VSTD::swap(this->__begin_, __x.__begin_);
1922 _VSTD::swap(this->__end_, __x.__end_);
1923 _VSTD::swap(this->__end_cap(), __x.__end_cap());
1924 __base::__swap_alloc(this->__alloc(), __x.__alloc());
1925 #if _LIBCPP_DEBUG_LEVEL >= 2
1926 __get_db()->swap(this, &__x);
1927 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1930 template <class _Tp, class _Allocator>
1932 vector<_Tp, _Allocator>::__invariants() const
1934 if (this->__begin_ == nullptr)
1936 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
1941 if (this->__begin_ > this->__end_)
1943 if (this->__begin_ == this->__end_cap())
1945 if (this->__end_ > this->__end_cap())
1951 #if _LIBCPP_DEBUG_LEVEL >= 2
1953 template <class _Tp, class _Allocator>
1955 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
1957 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
1960 template <class _Tp, class _Allocator>
1962 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
1964 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
1967 template <class _Tp, class _Allocator>
1969 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
1971 const_pointer __p = __i->base() + __n;
1972 return this->__begin_ <= __p && __p <= this->__end_;
1975 template <class _Tp, class _Allocator>
1977 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1979 const_pointer __p = __i->base() + __n;
1980 return this->__begin_ <= __p && __p < this->__end_;
1983 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1985 template <class _Tp, class _Allocator>
1986 _LIBCPP_INLINE_VISIBILITY inline
1988 vector<_Tp, _Allocator>::__invalidate_all_iterators()
1990 #if _LIBCPP_DEBUG_LEVEL >= 2
1991 __get_db()->__invalidate_all(this);
1992 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1997 template <class _Allocator> class vector<bool, _Allocator>;
1999 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2001 template <class _Allocator>
2002 struct __has_storage_type<vector<bool, _Allocator> >
2004 static const bool value = true;
2007 template <class _Allocator>
2008 class _LIBCPP_TYPE_VIS vector<bool, _Allocator>
2009 : private __vector_base_common<true>
2012 typedef vector __self;
2013 typedef bool value_type;
2014 typedef _Allocator allocator_type;
2015 typedef allocator_traits<allocator_type> __alloc_traits;
2016 typedef typename __alloc_traits::size_type size_type;
2017 typedef typename __alloc_traits::difference_type difference_type;
2018 typedef size_type __storage_type;
2019 typedef __bit_iterator<vector, false> pointer;
2020 typedef __bit_iterator<vector, true> const_pointer;
2021 #ifdef _LIBCPP_DEBUG
2022 typedef __debug_iter<vector, pointer> iterator;
2023 typedef __debug_iter<vector, const_pointer> const_iterator;
2025 friend class __debug_iter<vector, pointer>;
2026 friend class __debug_iter<vector, const_pointer>;
2028 pair<iterator*, const_iterator*> __iterator_list_;
2030 _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;}
2031 _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;}
2032 #else // _LIBCPP_DEBUG
2033 typedef pointer iterator;
2034 typedef const_pointer const_iterator;
2035 #endif // _LIBCPP_DEBUG
2036 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2037 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
2040 typedef typename __alloc_traits::template
2041 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
2042 rebind_alloc<__storage_type>
2044 rebind_alloc<__storage_type>::other
2046 __storage_allocator;
2047 typedef allocator_traits<__storage_allocator> __storage_traits;
2048 typedef typename __storage_traits::pointer __storage_pointer;
2049 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2051 __storage_pointer __begin_;
2053 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2055 typedef __bit_reference<vector> reference;
2056 typedef __bit_const_reference<vector> const_reference;
2058 _LIBCPP_INLINE_VISIBILITY
2059 size_type& __cap() _NOEXCEPT
2060 {return __cap_alloc_.first();}
2061 _LIBCPP_INLINE_VISIBILITY
2062 const size_type& __cap() const _NOEXCEPT
2063 {return __cap_alloc_.first();}
2064 _LIBCPP_INLINE_VISIBILITY
2065 __storage_allocator& __alloc() _NOEXCEPT
2066 {return __cap_alloc_.second();}
2067 _LIBCPP_INLINE_VISIBILITY
2068 const __storage_allocator& __alloc() const _NOEXCEPT
2069 {return __cap_alloc_.second();}
2071 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2073 _LIBCPP_INLINE_VISIBILITY
2074 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2075 {return __n * __bits_per_word;}
2076 _LIBCPP_INLINE_VISIBILITY
2077 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2078 {return (__n - 1) / __bits_per_word + 1;}
2081 _LIBCPP_INLINE_VISIBILITY
2083 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2084 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a);
2086 explicit vector(size_type __n);
2087 vector(size_type __n, const value_type& __v);
2088 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2089 template <class _InputIterator>
2090 vector(_InputIterator __first, _InputIterator __last,
2091 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2092 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2093 template <class _InputIterator>
2094 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2095 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2096 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2097 template <class _ForwardIterator>
2098 vector(_ForwardIterator __first, _ForwardIterator __last,
2099 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2100 template <class _ForwardIterator>
2101 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2102 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2104 vector(const vector& __v);
2105 vector(const vector& __v, const allocator_type& __a);
2106 vector& operator=(const vector& __v);
2107 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2108 vector(initializer_list<value_type> __il);
2109 vector(initializer_list<value_type> __il, const allocator_type& __a);
2110 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2112 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2113 _LIBCPP_INLINE_VISIBILITY
2114 vector(vector&& __v)
2115 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2116 vector(vector&& __v, const allocator_type& __a);
2117 _LIBCPP_INLINE_VISIBILITY
2118 vector& operator=(vector&& __v)
2120 __alloc_traits::propagate_on_container_move_assignment::value &&
2121 is_nothrow_move_assignable<allocator_type>::value);
2122 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2123 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2124 _LIBCPP_INLINE_VISIBILITY
2125 vector& operator=(initializer_list<value_type> __il)
2126 {assign(__il.begin(), __il.end()); return *this;}
2127 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2129 template <class _InputIterator>
2132 __is_input_iterator<_InputIterator>::value &&
2133 !__is_forward_iterator<_InputIterator>::value,
2136 assign(_InputIterator __first, _InputIterator __last);
2137 template <class _ForwardIterator>
2140 __is_forward_iterator<_ForwardIterator>::value,
2143 assign(_ForwardIterator __first, _ForwardIterator __last);
2145 void assign(size_type __n, const value_type& __x);
2146 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2147 _LIBCPP_INLINE_VISIBILITY
2148 void assign(initializer_list<value_type> __il)
2149 {assign(__il.begin(), __il.end());}
2150 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2152 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2153 {return allocator_type(this->__alloc());}
2155 size_type max_size() const _NOEXCEPT;
2156 _LIBCPP_INLINE_VISIBILITY
2157 size_type capacity() const _NOEXCEPT
2158 {return __internal_cap_to_external(__cap());}
2159 _LIBCPP_INLINE_VISIBILITY
2160 size_type size() const _NOEXCEPT
2162 _LIBCPP_INLINE_VISIBILITY
2163 bool empty() const _NOEXCEPT
2164 {return __size_ == 0;}
2165 void reserve(size_type __n);
2166 void shrink_to_fit() _NOEXCEPT;
2168 _LIBCPP_INLINE_VISIBILITY
2169 iterator begin() _NOEXCEPT
2170 {return __make_iter(0);}
2171 _LIBCPP_INLINE_VISIBILITY
2172 const_iterator begin() const _NOEXCEPT
2173 {return __make_iter(0);}
2174 _LIBCPP_INLINE_VISIBILITY
2175 iterator end() _NOEXCEPT
2176 {return __make_iter(__size_);}
2177 _LIBCPP_INLINE_VISIBILITY
2178 const_iterator end() const _NOEXCEPT
2179 {return __make_iter(__size_);}
2181 _LIBCPP_INLINE_VISIBILITY
2182 reverse_iterator rbegin() _NOEXCEPT
2183 {return reverse_iterator(end());}
2184 _LIBCPP_INLINE_VISIBILITY
2185 const_reverse_iterator rbegin() const _NOEXCEPT
2186 {return const_reverse_iterator(end());}
2187 _LIBCPP_INLINE_VISIBILITY
2188 reverse_iterator rend() _NOEXCEPT
2189 {return reverse_iterator(begin());}
2190 _LIBCPP_INLINE_VISIBILITY
2191 const_reverse_iterator rend() const _NOEXCEPT
2192 {return const_reverse_iterator(begin());}
2194 _LIBCPP_INLINE_VISIBILITY
2195 const_iterator cbegin() const _NOEXCEPT
2196 {return __make_iter(0);}
2197 _LIBCPP_INLINE_VISIBILITY
2198 const_iterator cend() const _NOEXCEPT
2199 {return __make_iter(__size_);}
2200 _LIBCPP_INLINE_VISIBILITY
2201 const_reverse_iterator crbegin() const _NOEXCEPT
2203 _LIBCPP_INLINE_VISIBILITY
2204 const_reverse_iterator crend() const _NOEXCEPT
2207 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2208 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2209 reference at(size_type __n);
2210 const_reference at(size_type __n) const;
2212 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2213 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2214 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2215 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2217 void push_back(const value_type& __x);
2218 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2220 iterator insert(const_iterator __position, const value_type& __x);
2221 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2222 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2223 template <class _InputIterator>
2226 __is_input_iterator <_InputIterator>::value &&
2227 !__is_forward_iterator<_InputIterator>::value,
2230 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2231 template <class _ForwardIterator>
2234 __is_forward_iterator<_ForwardIterator>::value,
2237 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2238 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2239 _LIBCPP_INLINE_VISIBILITY
2240 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2241 {return insert(__position, __il.begin(), __il.end());}
2242 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2244 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2245 iterator erase(const_iterator __first, const_iterator __last);
2247 _LIBCPP_INLINE_VISIBILITY
2248 void clear() _NOEXCEPT {__size_ = 0;}
2251 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2252 __is_nothrow_swappable<allocator_type>::value);
2254 void resize(size_type __sz, value_type __x = false);
2255 void flip() _NOEXCEPT;
2257 bool __invariants() const;
2260 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2261 void allocate(size_type __n);
2262 void deallocate() _NOEXCEPT;
2263 _LIBCPP_INLINE_VISIBILITY
2264 static size_type __align(size_type __new_size) _NOEXCEPT
2265 {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);};
2266 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2267 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2268 template <class _ForwardIterator>
2271 __is_forward_iterator<_ForwardIterator>::value,
2274 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2275 void __append(size_type __n, const_reference __x);
2276 _LIBCPP_INLINE_VISIBILITY
2277 reference __make_ref(size_type __pos) _NOEXCEPT
2278 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2279 _LIBCPP_INLINE_VISIBILITY
2280 const_reference __make_ref(size_type __pos) const _NOEXCEPT
2281 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2282 #ifdef _LIBCPP_DEBUG
2283 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos)
2284 {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2285 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const
2286 {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2287 _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p)
2288 {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));}
2289 #else // _LIBCPP_DEBUG
2290 _LIBCPP_INLINE_VISIBILITY
2291 iterator __make_iter(size_type __pos) _NOEXCEPT
2292 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2293 _LIBCPP_INLINE_VISIBILITY
2294 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2295 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2296 _LIBCPP_INLINE_VISIBILITY
2297 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2298 {return begin() + (__p - cbegin());}
2299 #endif // _LIBCPP_DEBUG
2301 _LIBCPP_INLINE_VISIBILITY
2302 void __copy_assign_alloc(const vector& __v)
2303 {__copy_assign_alloc(__v, integral_constant<bool,
2304 __storage_traits::propagate_on_container_copy_assignment::value>());}
2305 _LIBCPP_INLINE_VISIBILITY
2306 void __copy_assign_alloc(const vector& __c, true_type)
2308 if (__alloc() != __c.__alloc())
2310 __alloc() = __c.__alloc();
2313 _LIBCPP_INLINE_VISIBILITY
2314 void __copy_assign_alloc(const vector&, false_type)
2317 void __move_assign(vector& __c, false_type);
2318 void __move_assign(vector& __c, true_type)
2319 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2320 _LIBCPP_INLINE_VISIBILITY
2321 void __move_assign_alloc(vector& __c)
2323 !__storage_traits::propagate_on_container_move_assignment::value ||
2324 is_nothrow_move_assignable<allocator_type>::value)
2325 {__move_assign_alloc(__c, integral_constant<bool,
2326 __storage_traits::propagate_on_container_move_assignment::value>());}
2327 _LIBCPP_INLINE_VISIBILITY
2328 void __move_assign_alloc(vector& __c, true_type)
2329 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2331 __alloc() = _VSTD::move(__c.__alloc());
2334 _LIBCPP_INLINE_VISIBILITY
2335 void __move_assign_alloc(vector&, false_type)
2339 _LIBCPP_INLINE_VISIBILITY
2340 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y)
2342 !__storage_traits::propagate_on_container_swap::value ||
2343 __is_nothrow_swappable<allocator_type>::value)
2344 {__swap_alloc(__x, __y, integral_constant<bool,
2345 __storage_traits::propagate_on_container_swap::value>());}
2347 _LIBCPP_INLINE_VISIBILITY
2348 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type)
2349 _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
2354 _LIBCPP_INLINE_VISIBILITY
2355 static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type)
2359 size_t __hash_code() const _NOEXCEPT;
2361 friend class __bit_reference<vector>;
2362 friend class __bit_const_reference<vector>;
2363 friend class __bit_iterator<vector, false>;
2364 friend class __bit_iterator<vector, true>;
2365 friend struct __bit_array<vector>;
2366 friend struct _LIBCPP_TYPE_VIS hash<vector>;
2369 template <class _Allocator>
2370 #ifndef _LIBCPP_DEBUG
2371 _LIBCPP_INLINE_VISIBILITY inline
2374 vector<bool, _Allocator>::__invalidate_all_iterators()
2376 #ifdef _LIBCPP_DEBUG
2377 iterator::__remove_all(this);
2378 const_iterator::__remove_all(this);
2379 #endif // _LIBCPP_DEBUG
2382 // Allocate space for __n objects
2383 // throws length_error if __n > max_size()
2384 // throws (probably bad_alloc) if memory run out
2385 // Precondition: __begin_ == __end_ == __cap() == 0
2386 // Precondition: __n > 0
2387 // Postcondition: capacity() == __n
2388 // Postcondition: size() == 0
2389 template <class _Allocator>
2391 vector<bool, _Allocator>::allocate(size_type __n)
2393 if (__n > max_size())
2394 this->__throw_length_error();
2395 __n = __external_cap_to_internal(__n);
2396 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2398 this->__cap() = __n;
2401 template <class _Allocator>
2403 vector<bool, _Allocator>::deallocate() _NOEXCEPT
2405 if (this->__begin_ != nullptr)
2407 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2408 __invalidate_all_iterators();
2409 this->__begin_ = nullptr;
2410 this->__size_ = this->__cap() = 0;
2414 template <class _Allocator>
2415 typename vector<bool, _Allocator>::size_type
2416 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2418 size_type __amax = __storage_traits::max_size(__alloc());
2419 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2420 if (__nmax / __bits_per_word <= __amax)
2422 return __internal_cap_to_external(__amax);
2425 // Precondition: __new_size > capacity()
2426 template <class _Allocator>
2427 _LIBCPP_INLINE_VISIBILITY inline
2428 typename vector<bool, _Allocator>::size_type
2429 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2431 const size_type __ms = max_size();
2432 if (__new_size > __ms)
2433 this->__throw_length_error();
2434 const size_type __cap = capacity();
2435 if (__cap >= __ms / 2)
2437 return _VSTD::max(2*__cap, __align(__new_size));
2440 // Default constructs __n objects starting at __end_
2441 // Precondition: __n > 0
2442 // Precondition: size() + __n <= capacity()
2443 // Postcondition: size() == size() + __n
2444 template <class _Allocator>
2445 _LIBCPP_INLINE_VISIBILITY inline
2447 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2449 size_type __old_size = this->__size_;
2450 this->__size_ += __n;
2451 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2454 template <class _Allocator>
2455 template <class _ForwardIterator>
2458 __is_forward_iterator<_ForwardIterator>::value,
2461 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2463 size_type __old_size = this->__size_;
2464 this->__size_ += _VSTD::distance(__first, __last);
2465 _VSTD::copy(__first, __last, __make_iter(__old_size));
2468 template <class _Allocator>
2469 _LIBCPP_INLINE_VISIBILITY inline
2470 vector<bool, _Allocator>::vector()
2471 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2472 : __begin_(nullptr),
2478 template <class _Allocator>
2479 _LIBCPP_INLINE_VISIBILITY inline
2480 vector<bool, _Allocator>::vector(const allocator_type& __a)
2481 : __begin_(nullptr),
2483 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2487 template <class _Allocator>
2488 vector<bool, _Allocator>::vector(size_type __n)
2489 : __begin_(nullptr),
2496 __construct_at_end(__n, false);
2500 template <class _Allocator>
2501 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2502 : __begin_(nullptr),
2509 __construct_at_end(__n, __x);
2513 template <class _Allocator>
2514 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2515 : __begin_(nullptr),
2517 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2522 __construct_at_end(__n, __x);
2526 template <class _Allocator>
2527 template <class _InputIterator>
2528 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2529 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2530 !__is_forward_iterator<_InputIterator>::value>::type*)
2531 : __begin_(nullptr),
2535 #ifndef _LIBCPP_NO_EXCEPTIONS
2538 #endif // _LIBCPP_NO_EXCEPTIONS
2539 for (; __first != __last; ++__first)
2540 push_back(*__first);
2541 #ifndef _LIBCPP_NO_EXCEPTIONS
2545 if (__begin_ != nullptr)
2546 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2547 __invalidate_all_iterators();
2550 #endif // _LIBCPP_NO_EXCEPTIONS
2553 template <class _Allocator>
2554 template <class _InputIterator>
2555 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2556 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2557 !__is_forward_iterator<_InputIterator>::value>::type*)
2558 : __begin_(nullptr),
2560 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2562 #ifndef _LIBCPP_NO_EXCEPTIONS
2565 #endif // _LIBCPP_NO_EXCEPTIONS
2566 for (; __first != __last; ++__first)
2567 push_back(*__first);
2568 #ifndef _LIBCPP_NO_EXCEPTIONS
2572 if (__begin_ != nullptr)
2573 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2574 __invalidate_all_iterators();
2577 #endif // _LIBCPP_NO_EXCEPTIONS
2580 template <class _Allocator>
2581 template <class _ForwardIterator>
2582 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2583 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2584 : __begin_(nullptr),
2588 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2592 __construct_at_end(__first, __last);
2596 template <class _Allocator>
2597 template <class _ForwardIterator>
2598 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2599 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2600 : __begin_(nullptr),
2602 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2604 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2608 __construct_at_end(__first, __last);
2612 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2614 template <class _Allocator>
2615 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2616 : __begin_(nullptr),
2620 size_type __n = static_cast<size_type>(__il.size());
2624 __construct_at_end(__il.begin(), __il.end());
2628 template <class _Allocator>
2629 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2630 : __begin_(nullptr),
2632 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2634 size_type __n = static_cast<size_type>(__il.size());
2638 __construct_at_end(__il.begin(), __il.end());
2642 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2644 template <class _Allocator>
2645 vector<bool, _Allocator>::~vector()
2647 if (__begin_ != nullptr)
2648 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2649 #ifdef _LIBCPP_DEBUG
2650 __invalidate_all_iterators();
2654 template <class _Allocator>
2655 vector<bool, _Allocator>::vector(const vector& __v)
2656 : __begin_(nullptr),
2658 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2662 allocate(__v.size());
2663 __construct_at_end(__v.begin(), __v.end());
2667 template <class _Allocator>
2668 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2669 : __begin_(nullptr),
2671 __cap_alloc_(0, __a)
2675 allocate(__v.size());
2676 __construct_at_end(__v.begin(), __v.end());
2680 template <class _Allocator>
2681 vector<bool, _Allocator>&
2682 vector<bool, _Allocator>::operator=(const vector& __v)
2686 __copy_assign_alloc(__v);
2689 if (__v.__size_ > capacity())
2692 allocate(__v.__size_);
2694 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2696 __size_ = __v.__size_;
2701 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2703 template <class _Allocator>
2704 _LIBCPP_INLINE_VISIBILITY inline
2705 vector<bool, _Allocator>::vector(vector&& __v)
2706 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2707 : __begin_(__v.__begin_),
2708 __size_(__v.__size_),
2709 __cap_alloc_(__v.__cap_alloc_)
2711 __v.__begin_ = nullptr;
2716 template <class _Allocator>
2717 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2718 : __begin_(nullptr),
2720 __cap_alloc_(0, __a)
2722 if (__a == allocator_type(__v.__alloc()))
2724 this->__begin_ = __v.__begin_;
2725 this->__size_ = __v.__size_;
2726 this->__cap() = __v.__cap();
2727 __v.__begin_ = nullptr;
2728 __v.__cap() = __v.__size_ = 0;
2730 else if (__v.size() > 0)
2732 allocate(__v.size());
2733 __construct_at_end(__v.begin(), __v.end());
2737 template <class _Allocator>
2738 _LIBCPP_INLINE_VISIBILITY inline
2739 vector<bool, _Allocator>&
2740 vector<bool, _Allocator>::operator=(vector&& __v)
2742 __alloc_traits::propagate_on_container_move_assignment::value &&
2743 is_nothrow_move_assignable<allocator_type>::value)
2745 __move_assign(__v, integral_constant<bool,
2746 __storage_traits::propagate_on_container_move_assignment::value>());
2750 template <class _Allocator>
2752 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2754 if (__alloc() != __c.__alloc())
2755 assign(__c.begin(), __c.end());
2757 __move_assign(__c, true_type());
2760 template <class _Allocator>
2762 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2763 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2766 this->__begin_ = __c.__begin_;
2767 this->__size_ = __c.__size_;
2768 this->__cap() = __c.__cap();
2769 __move_assign_alloc(__c);
2770 __c.__begin_ = nullptr;
2771 __c.__cap() = __c.__size_ = 0;
2774 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2776 template <class _Allocator>
2778 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2783 size_type __c = capacity();
2788 vector __v(__alloc());
2789 __v.reserve(__recommend(__n));
2793 _VSTD::fill_n(begin(), __n, __x);
2797 template <class _Allocator>
2798 template <class _InputIterator>
2801 __is_input_iterator<_InputIterator>::value &&
2802 !__is_forward_iterator<_InputIterator>::value,
2805 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2808 for (; __first != __last; ++__first)
2809 push_back(*__first);
2812 template <class _Allocator>
2813 template <class _ForwardIterator>
2816 __is_forward_iterator<_ForwardIterator>::value,
2819 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2822 difference_type __n = _VSTD::distance(__first, __last);
2825 if (__n > capacity())
2830 __construct_at_end(__first, __last);
2834 template <class _Allocator>
2836 vector<bool, _Allocator>::reserve(size_type __n)
2838 if (__n > capacity())
2840 vector __v(this->__alloc());
2842 __v.__construct_at_end(this->begin(), this->end());
2844 __invalidate_all_iterators();
2848 template <class _Allocator>
2850 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
2852 if (__external_cap_to_internal(size()) > __cap())
2854 #ifndef _LIBCPP_NO_EXCEPTIONS
2857 #endif // _LIBCPP_NO_EXCEPTIONS
2858 vector(*this, allocator_type(__alloc())).swap(*this);
2859 #ifndef _LIBCPP_NO_EXCEPTIONS
2864 #endif // _LIBCPP_NO_EXCEPTIONS
2868 template <class _Allocator>
2869 typename vector<bool, _Allocator>::reference
2870 vector<bool, _Allocator>::at(size_type __n)
2873 this->__throw_out_of_range();
2874 return (*this)[__n];
2877 template <class _Allocator>
2878 typename vector<bool, _Allocator>::const_reference
2879 vector<bool, _Allocator>::at(size_type __n) const
2882 this->__throw_out_of_range();
2883 return (*this)[__n];
2886 template <class _Allocator>
2888 vector<bool, _Allocator>::push_back(const value_type& __x)
2890 if (this->__size_ == this->capacity())
2891 reserve(__recommend(this->__size_ + 1));
2896 template <class _Allocator>
2897 typename vector<bool, _Allocator>::iterator
2898 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
2901 if (size() < capacity())
2903 const_iterator __old_end = end();
2905 _VSTD::copy_backward(__position, __old_end, end());
2906 __r = __const_iterator_cast(__position);
2910 vector __v(__alloc());
2911 __v.reserve(__recommend(__size_ + 1));
2912 __v.__size_ = __size_ + 1;
2913 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2914 _VSTD::copy_backward(__position, cend(), __v.end());
2921 template <class _Allocator>
2922 typename vector<bool, _Allocator>::iterator
2923 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
2926 size_type __c = capacity();
2927 if (__n <= __c && size() <= __c - __n)
2929 const_iterator __old_end = end();
2931 _VSTD::copy_backward(__position, __old_end, end());
2932 __r = __const_iterator_cast(__position);
2936 vector __v(__alloc());
2937 __v.reserve(__recommend(__size_ + __n));
2938 __v.__size_ = __size_ + __n;
2939 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2940 _VSTD::copy_backward(__position, cend(), __v.end());
2943 _VSTD::fill_n(__r, __n, __x);
2947 template <class _Allocator>
2948 template <class _InputIterator>
2951 __is_input_iterator <_InputIterator>::value &&
2952 !__is_forward_iterator<_InputIterator>::value,
2953 typename vector<bool, _Allocator>::iterator
2955 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
2957 difference_type __off = __position - begin();
2958 iterator __p = __const_iterator_cast(__position);
2959 iterator __old_end = end();
2960 for (; size() != capacity() && __first != __last; ++__first)
2965 vector __v(__alloc());
2966 if (__first != __last)
2968 #ifndef _LIBCPP_NO_EXCEPTIONS
2971 #endif // _LIBCPP_NO_EXCEPTIONS
2972 __v.assign(__first, __last);
2973 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
2974 difference_type __old_p = __p - begin();
2975 reserve(__recommend(size() + __v.size()));
2976 __p = begin() + __old_p;
2977 __old_end = begin() + __old_size;
2978 #ifndef _LIBCPP_NO_EXCEPTIONS
2982 erase(__old_end, end());
2985 #endif // _LIBCPP_NO_EXCEPTIONS
2987 __p = _VSTD::rotate(__p, __old_end, end());
2988 insert(__p, __v.begin(), __v.end());
2989 return begin() + __off;
2992 template <class _Allocator>
2993 template <class _ForwardIterator>
2996 __is_forward_iterator<_ForwardIterator>::value,
2997 typename vector<bool, _Allocator>::iterator
2999 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3001 difference_type __n = _VSTD::distance(__first, __last);
3003 size_type __c = capacity();
3004 if (__n <= __c && size() <= __c - __n)
3006 const_iterator __old_end = end();
3008 _VSTD::copy_backward(__position, __old_end, end());
3009 __r = __const_iterator_cast(__position);
3013 vector __v(__alloc());
3014 __v.reserve(__recommend(__size_ + __n));
3015 __v.__size_ = __size_ + __n;
3016 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3017 _VSTD::copy_backward(__position, cend(), __v.end());
3020 _VSTD::copy(__first, __last, __r);
3024 template <class _Allocator>
3025 _LIBCPP_INLINE_VISIBILITY inline
3026 typename vector<bool, _Allocator>::iterator
3027 vector<bool, _Allocator>::erase(const_iterator __position)
3029 iterator __r = __const_iterator_cast(__position);
3030 _VSTD::copy(__position + 1, this->cend(), __r);
3035 template <class _Allocator>
3036 typename vector<bool, _Allocator>::iterator
3037 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3039 iterator __r = __const_iterator_cast(__first);
3040 difference_type __d = __last - __first;
3041 _VSTD::copy(__last, this->cend(), __r);
3046 template <class _Allocator>
3048 vector<bool, _Allocator>::swap(vector& __x)
3049 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3050 __is_nothrow_swappable<allocator_type>::value)
3052 _VSTD::swap(this->__begin_, __x.__begin_);
3053 _VSTD::swap(this->__size_, __x.__size_);
3054 _VSTD::swap(this->__cap(), __x.__cap());
3055 __swap_alloc(this->__alloc(), __x.__alloc());
3056 #ifdef _LIBCPP_DEBUG
3057 iterator::swap(this, &__x);
3058 const_iterator::swap(this, &__x);
3059 #endif // _LIBCPP_DEBUG
3062 template <class _Allocator>
3064 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3066 size_type __cs = size();
3070 size_type __c = capacity();
3071 size_type __n = __sz - __cs;
3072 if (__n <= __c && __cs <= __c - __n)
3079 vector __v(__alloc());
3080 __v.reserve(__recommend(__size_ + __n));
3081 __v.__size_ = __size_ + __n;
3082 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3085 _VSTD::fill_n(__r, __n, __x);
3091 template <class _Allocator>
3093 vector<bool, _Allocator>::flip() _NOEXCEPT
3095 // do middle whole words
3096 size_type __n = __size_;
3097 __storage_pointer __p = __begin_;
3098 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3100 // do last partial word
3103 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3104 __storage_type __b = *__p & __m;
3110 template <class _Allocator>
3112 vector<bool, _Allocator>::__invariants() const
3114 if (this->__begin_ == nullptr)
3116 if (this->__size_ != 0 || this->__cap() != 0)
3121 if (this->__cap() == 0)
3123 if (this->__size_ > this->capacity())
3129 template <class _Allocator>
3131 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3134 // do middle whole words
3135 size_type __n = __size_;
3136 __storage_pointer __p = __begin_;
3137 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3139 // do last partial word
3142 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3148 template <class _Allocator>
3149 struct _LIBCPP_TYPE_VIS hash<vector<bool, _Allocator> >
3150 : public unary_function<vector<bool, _Allocator>, size_t>
3152 _LIBCPP_INLINE_VISIBILITY
3153 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3154 {return __vec.__hash_code();}
3157 template <class _Tp, class _Allocator>
3158 _LIBCPP_INLINE_VISIBILITY inline
3160 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3162 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3163 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3166 template <class _Tp, class _Allocator>
3167 _LIBCPP_INLINE_VISIBILITY inline
3169 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3171 return !(__x == __y);
3174 template <class _Tp, class _Allocator>
3175 _LIBCPP_INLINE_VISIBILITY inline
3177 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3179 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3182 template <class _Tp, class _Allocator>
3183 _LIBCPP_INLINE_VISIBILITY inline
3185 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3190 template <class _Tp, class _Allocator>
3191 _LIBCPP_INLINE_VISIBILITY inline
3193 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3195 return !(__x < __y);
3198 template <class _Tp, class _Allocator>
3199 _LIBCPP_INLINE_VISIBILITY inline
3201 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3203 return !(__y < __x);
3206 template <class _Tp, class _Allocator>
3207 _LIBCPP_INLINE_VISIBILITY inline
3209 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3210 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3215 _LIBCPP_END_NAMESPACE_STD
3217 #endif // _LIBCPP_VECTOR