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 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
274 #pragma GCC system_header
277 _LIBCPP_BEGIN_NAMESPACE_STD
280 class __vector_base_common
283 _LIBCPP_ALWAYS_INLINE __vector_base_common() {}
284 void __throw_length_error() const;
285 void __throw_out_of_range() const;
290 __vector_base_common<__b>::__throw_length_error() const
292 #ifndef _LIBCPP_NO_EXCEPTIONS
293 throw length_error("vector");
295 assert(!"vector length_error");
301 __vector_base_common<__b>::__throw_out_of_range() const
303 #ifndef _LIBCPP_NO_EXCEPTIONS
304 throw out_of_range("vector");
306 assert(!"vector out_of_range");
311 #pragma warning( push )
312 #pragma warning( disable: 4231 )
314 extern template class __vector_base_common<true>;
316 #pragma warning( pop )
319 template <class _Tp, class _Allocator>
321 : protected __vector_base_common<true>
324 typedef _Tp value_type;
325 typedef _Allocator allocator_type;
326 typedef allocator_traits<allocator_type> __alloc_traits;
327 typedef value_type& reference;
328 typedef const value_type& const_reference;
329 typedef typename __alloc_traits::size_type size_type;
330 typedef typename __alloc_traits::difference_type difference_type;
331 typedef typename __alloc_traits::pointer pointer;
332 typedef typename __alloc_traits::const_pointer const_pointer;
333 typedef pointer iterator;
334 typedef const_pointer const_iterator;
338 __compressed_pair<pointer, allocator_type> __end_cap_;
340 _LIBCPP_INLINE_VISIBILITY
341 allocator_type& __alloc() _NOEXCEPT
342 {return __end_cap_.second();}
343 _LIBCPP_INLINE_VISIBILITY
344 const allocator_type& __alloc() const _NOEXCEPT
345 {return __end_cap_.second();}
346 _LIBCPP_INLINE_VISIBILITY
347 pointer& __end_cap() _NOEXCEPT
348 {return __end_cap_.first();}
349 _LIBCPP_INLINE_VISIBILITY
350 const pointer& __end_cap() const _NOEXCEPT
351 {return __end_cap_.first();}
353 _LIBCPP_INLINE_VISIBILITY
355 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
356 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
359 _LIBCPP_INLINE_VISIBILITY
360 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
361 _LIBCPP_INLINE_VISIBILITY
362 size_type capacity() const _NOEXCEPT
363 {return static_cast<size_type>(__end_cap() - __begin_);}
365 _LIBCPP_INLINE_VISIBILITY
366 void __destruct_at_end(const_pointer __new_last) _NOEXCEPT
367 {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());}
368 _LIBCPP_INLINE_VISIBILITY
369 void __destruct_at_end(const_pointer __new_last, false_type) _NOEXCEPT;
370 _LIBCPP_INLINE_VISIBILITY
371 void __destruct_at_end(const_pointer __new_last, true_type) _NOEXCEPT;
373 _LIBCPP_INLINE_VISIBILITY
374 void __copy_assign_alloc(const __vector_base& __c)
375 {__copy_assign_alloc(__c, integral_constant<bool,
376 __alloc_traits::propagate_on_container_copy_assignment::value>());}
378 _LIBCPP_INLINE_VISIBILITY
379 void __move_assign_alloc(__vector_base& __c)
381 !__alloc_traits::propagate_on_container_move_assignment::value ||
382 is_nothrow_move_assignable<allocator_type>::value)
383 {__move_assign_alloc(__c, integral_constant<bool,
384 __alloc_traits::propagate_on_container_move_assignment::value>());}
386 _LIBCPP_INLINE_VISIBILITY
387 static void __swap_alloc(allocator_type& __x, allocator_type& __y)
389 !__alloc_traits::propagate_on_container_swap::value ||
390 __is_nothrow_swappable<allocator_type>::value)
391 {__swap_alloc(__x, __y, integral_constant<bool,
392 __alloc_traits::propagate_on_container_swap::value>());}
394 _LIBCPP_INLINE_VISIBILITY
395 void __copy_assign_alloc(const __vector_base& __c, true_type)
397 if (__alloc() != __c.__alloc())
400 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
401 __begin_ = __end_ = __end_cap() = nullptr;
403 __alloc() = __c.__alloc();
406 _LIBCPP_INLINE_VISIBILITY
407 void __copy_assign_alloc(const __vector_base& __c, false_type)
410 _LIBCPP_INLINE_VISIBILITY
411 void __move_assign_alloc(__vector_base& __c, true_type)
412 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
414 __alloc() = _VSTD::move(__c.__alloc());
417 _LIBCPP_INLINE_VISIBILITY
418 void __move_assign_alloc(__vector_base& __c, false_type)
422 _LIBCPP_INLINE_VISIBILITY
423 static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type)
424 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
429 _LIBCPP_INLINE_VISIBILITY
430 static void __swap_alloc(allocator_type& __x, allocator_type& __y, false_type)
435 template <class _Tp, class _Allocator>
436 _LIBCPP_INLINE_VISIBILITY inline
438 __vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, false_type) _NOEXCEPT
440 while (__new_last < __end_)
441 __alloc_traits::destroy(__alloc(), const_cast<pointer>(--__end_));
444 template <class _Tp, class _Allocator>
445 _LIBCPP_INLINE_VISIBILITY inline
447 __vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, true_type) _NOEXCEPT
449 __end_ = const_cast<pointer>(__new_last);
452 template <class _Tp, class _Allocator>
453 _LIBCPP_INLINE_VISIBILITY inline
454 __vector_base<_Tp, _Allocator>::__vector_base()
455 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
462 template <class _Tp, class _Allocator>
463 _LIBCPP_INLINE_VISIBILITY inline
464 __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
471 template <class _Tp, class _Allocator>
472 __vector_base<_Tp, _Allocator>::~__vector_base()
477 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
481 template <class _Tp, class _Allocator = allocator<_Tp> >
482 class _LIBCPP_VISIBLE vector
483 : private __vector_base<_Tp, _Allocator>
486 typedef __vector_base<_Tp, _Allocator> __base;
488 typedef vector __self;
489 typedef _Tp value_type;
490 typedef _Allocator allocator_type;
491 typedef typename __base::__alloc_traits __alloc_traits;
492 typedef typename __base::reference reference;
493 typedef typename __base::const_reference const_reference;
494 typedef typename __base::size_type size_type;
495 typedef typename __base::difference_type difference_type;
496 typedef typename __base::pointer pointer;
497 typedef typename __base::const_pointer const_pointer;
498 typedef __wrap_iter<pointer> iterator;
499 typedef __wrap_iter<const_pointer> const_iterator;
500 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
501 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
503 _LIBCPP_INLINE_VISIBILITY
505 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
507 #if _LIBCPP_DEBUG_LEVEL >= 2
508 __get_db()->__insert_c(this);
511 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
514 #if _LIBCPP_DEBUG_LEVEL >= 2
515 __get_db()->__insert_c(this);
518 explicit vector(size_type __n);
519 vector(size_type __n, const_reference __x);
520 vector(size_type __n, const_reference __x, const allocator_type& __a);
521 template <class _InputIterator>
522 vector(_InputIterator __first, _InputIterator __last,
523 typename enable_if<__is_input_iterator <_InputIterator>::value &&
524 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
525 template <class _InputIterator>
526 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
527 typename enable_if<__is_input_iterator <_InputIterator>::value &&
528 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
529 template <class _ForwardIterator>
530 vector(_ForwardIterator __first, _ForwardIterator __last,
531 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
532 template <class _ForwardIterator>
533 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
534 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
535 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
536 _LIBCPP_INLINE_VISIBILITY
537 vector(initializer_list<value_type> __il);
538 _LIBCPP_INLINE_VISIBILITY
539 vector(initializer_list<value_type> __il, const allocator_type& __a);
540 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
541 #if _LIBCPP_DEBUG_LEVEL >= 2
542 _LIBCPP_INLINE_VISIBILITY
545 __get_db()->__erase_c(this);
549 vector(const vector& __x);
550 vector(const vector& __x, const allocator_type& __a);
551 _LIBCPP_INLINE_VISIBILITY
552 vector& operator=(const vector& __x);
553 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
554 _LIBCPP_INLINE_VISIBILITY
556 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
557 _LIBCPP_INLINE_VISIBILITY
558 vector(vector&& __x, const allocator_type& __a);
559 _LIBCPP_INLINE_VISIBILITY
560 vector& operator=(vector&& __x)
562 __alloc_traits::propagate_on_container_move_assignment::value &&
563 is_nothrow_move_assignable<allocator_type>::value);
564 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
565 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
566 _LIBCPP_INLINE_VISIBILITY
567 vector& operator=(initializer_list<value_type> __il)
568 {assign(__il.begin(), __il.end()); return *this;}
569 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
571 template <class _InputIterator>
574 __is_input_iterator <_InputIterator>::value &&
575 !__is_forward_iterator<_InputIterator>::value,
578 assign(_InputIterator __first, _InputIterator __last);
579 template <class _ForwardIterator>
582 __is_forward_iterator<_ForwardIterator>::value,
585 assign(_ForwardIterator __first, _ForwardIterator __last);
587 void assign(size_type __n, const_reference __u);
588 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
589 _LIBCPP_INLINE_VISIBILITY
590 void assign(initializer_list<value_type> __il)
591 {assign(__il.begin(), __il.end());}
592 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
594 _LIBCPP_INLINE_VISIBILITY
595 allocator_type get_allocator() const _NOEXCEPT
596 {return this->__alloc();}
598 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
599 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
600 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
601 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
603 _LIBCPP_INLINE_VISIBILITY
604 reverse_iterator rbegin() _NOEXCEPT
605 {return reverse_iterator(end());}
606 _LIBCPP_INLINE_VISIBILITY
607 const_reverse_iterator rbegin() const _NOEXCEPT
608 {return const_reverse_iterator(end());}
609 _LIBCPP_INLINE_VISIBILITY
610 reverse_iterator rend() _NOEXCEPT
611 {return reverse_iterator(begin());}
612 _LIBCPP_INLINE_VISIBILITY
613 const_reverse_iterator rend() const _NOEXCEPT
614 {return const_reverse_iterator(begin());}
616 _LIBCPP_INLINE_VISIBILITY
617 const_iterator cbegin() const _NOEXCEPT
619 _LIBCPP_INLINE_VISIBILITY
620 const_iterator cend() const _NOEXCEPT
622 _LIBCPP_INLINE_VISIBILITY
623 const_reverse_iterator crbegin() const _NOEXCEPT
625 _LIBCPP_INLINE_VISIBILITY
626 const_reverse_iterator crend() const _NOEXCEPT
629 _LIBCPP_INLINE_VISIBILITY
630 size_type size() const _NOEXCEPT
631 {return static_cast<size_type>(this->__end_ - this->__begin_);}
632 _LIBCPP_INLINE_VISIBILITY
633 size_type capacity() const _NOEXCEPT
634 {return __base::capacity();}
635 _LIBCPP_INLINE_VISIBILITY
636 bool empty() const _NOEXCEPT
637 {return this->__begin_ == this->__end_;}
638 size_type max_size() const _NOEXCEPT;
639 void reserve(size_type __n);
640 void shrink_to_fit() _NOEXCEPT;
642 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n);
643 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const;
644 reference at(size_type __n);
645 const_reference at(size_type __n) const;
647 _LIBCPP_INLINE_VISIBILITY reference front()
649 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
650 return *this->__begin_;
652 _LIBCPP_INLINE_VISIBILITY const_reference front() const
654 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
655 return *this->__begin_;
657 _LIBCPP_INLINE_VISIBILITY reference back()
659 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
660 return *(this->__end_ - 1);
662 _LIBCPP_INLINE_VISIBILITY const_reference back() const
664 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
665 return *(this->__end_ - 1);
668 _LIBCPP_INLINE_VISIBILITY
669 value_type* data() _NOEXCEPT
670 {return _VSTD::__to_raw_pointer(this->__begin_);}
671 _LIBCPP_INLINE_VISIBILITY
672 const value_type* data() const _NOEXCEPT
673 {return _VSTD::__to_raw_pointer(this->__begin_);}
675 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
676 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
677 void push_back(value_type&& __x);
678 #ifndef _LIBCPP_HAS_NO_VARIADICS
679 template <class... _Args>
680 void emplace_back(_Args&&... __args);
681 #endif // _LIBCPP_HAS_NO_VARIADICS
682 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
685 iterator insert(const_iterator __position, const_reference __x);
686 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
687 iterator insert(const_iterator __position, value_type&& __x);
688 #ifndef _LIBCPP_HAS_NO_VARIADICS
689 template <class... _Args>
690 iterator emplace(const_iterator __position, _Args&&... __args);
691 #endif // _LIBCPP_HAS_NO_VARIADICS
692 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
693 iterator insert(const_iterator __position, size_type __n, const_reference __x);
694 template <class _InputIterator>
697 __is_input_iterator <_InputIterator>::value &&
698 !__is_forward_iterator<_InputIterator>::value,
701 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
702 template <class _ForwardIterator>
705 __is_forward_iterator<_ForwardIterator>::value,
708 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
709 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
710 _LIBCPP_INLINE_VISIBILITY
711 iterator insert(const_iterator __position, initializer_list<value_type> __il)
712 {return insert(__position, __il.begin(), __il.end());}
713 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
715 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
716 iterator erase(const_iterator __first, const_iterator __last);
718 _LIBCPP_INLINE_VISIBILITY
719 void clear() _NOEXCEPT
722 __invalidate_all_iterators();
725 void resize(size_type __sz);
726 void resize(size_type __sz, const_reference __x);
729 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
730 __is_nothrow_swappable<allocator_type>::value);
732 bool __invariants() const;
734 #if _LIBCPP_DEBUG_LEVEL >= 2
736 bool __dereferenceable(const const_iterator* __i) const;
737 bool __decrementable(const const_iterator* __i) const;
738 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
739 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
741 #endif // _LIBCPP_DEBUG_LEVEL >= 2
744 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
745 void allocate(size_type __n);
746 void deallocate() _NOEXCEPT;
747 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
748 void __construct_at_end(size_type __n);
749 void __construct_at_end(size_type __n, const_reference __x);
750 template <class _ForwardIterator>
753 __is_forward_iterator<_ForwardIterator>::value,
756 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
757 void __move_construct_at_end(pointer __first, pointer __last);
758 void __append(size_type __n);
759 void __append(size_type __n, const_reference __x);
760 _LIBCPP_INLINE_VISIBILITY
761 iterator __make_iter(pointer __p) _NOEXCEPT;
762 _LIBCPP_INLINE_VISIBILITY
763 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
764 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
765 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
766 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
767 void __move_assign(vector& __c, true_type)
768 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
769 void __move_assign(vector& __c, false_type);
770 _LIBCPP_INLINE_VISIBILITY
771 void __destruct_at_end(const_pointer __new_last) _NOEXCEPT
773 #if _LIBCPP_DEBUG_LEVEL >= 2
774 __c_node* __c = __get_db()->__find_c_and_lock(this);
775 for (__i_node** __p = __c->end_; __p != __c->beg_; )
778 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
779 if (__i->base() > __new_last)
781 (*__p)->__c_ = nullptr;
782 if (--__c->end_ != __p)
783 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
786 __get_db()->unlock();
788 __base::__destruct_at_end(__new_last);
792 template <class _Tp, class _Allocator>
794 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
796 for (pointer __p = this->__end_; this->__begin_ < __p;)
797 __v.push_front(_VSTD::move_if_noexcept(*--__p));
798 _VSTD::swap(this->__begin_, __v.__begin_);
799 _VSTD::swap(this->__end_, __v.__end_);
800 _VSTD::swap(this->__end_cap(), __v.__end_cap());
801 __v.__first_ = __v.__begin_;
802 __invalidate_all_iterators();
805 template <class _Tp, class _Allocator>
806 typename vector<_Tp, _Allocator>::pointer
807 vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
809 pointer __r = __v.__begin_;
810 for (pointer __i = __p; this->__begin_ < __i;)
811 __v.push_front(_VSTD::move_if_noexcept(*--__i));
812 for (pointer __i = __p; __i < this->__end_; ++__i)
813 __v.push_back(_VSTD::move_if_noexcept(*__i));
814 _VSTD::swap(this->__begin_, __v.__begin_);
815 _VSTD::swap(this->__end_, __v.__end_);
816 _VSTD::swap(this->__end_cap(), __v.__end_cap());
817 __v.__first_ = __v.__begin_;
818 __invalidate_all_iterators();
822 // Allocate space for __n objects
823 // throws length_error if __n > max_size()
824 // throws (probably bad_alloc) if memory run out
825 // Precondition: __begin_ == __end_ == __end_cap() == 0
826 // Precondition: __n > 0
827 // Postcondition: capacity() == __n
828 // Postcondition: size() == 0
829 template <class _Tp, class _Allocator>
831 vector<_Tp, _Allocator>::allocate(size_type __n)
833 if (__n > max_size())
834 this->__throw_length_error();
835 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
836 this->__end_cap() = this->__begin_ + __n;
839 template <class _Tp, class _Allocator>
841 vector<_Tp, _Allocator>::deallocate() _NOEXCEPT
843 if (this->__begin_ != 0)
846 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
847 this->__begin_ = this->__end_ = this->__end_cap() = 0;
851 template <class _Tp, class _Allocator>
852 typename vector<_Tp, _Allocator>::size_type
853 vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
855 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always
858 // Precondition: __new_size > capacity()
859 template <class _Tp, class _Allocator>
860 _LIBCPP_INLINE_VISIBILITY inline
861 typename vector<_Tp, _Allocator>::size_type
862 vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
864 const size_type __ms = max_size();
865 if (__new_size > __ms)
866 this->__throw_length_error();
867 const size_type __cap = capacity();
868 if (__cap >= __ms / 2)
870 return _VSTD::max<size_type>(2*__cap, __new_size);
873 // Default constructs __n objects starting at __end_
874 // throws if construction throws
875 // Precondition: __n > 0
876 // Precondition: size() + __n <= capacity()
877 // Postcondition: size() == size() + __n
878 template <class _Tp, class _Allocator>
880 vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
882 allocator_type& __a = this->__alloc();
885 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
891 // Copy constructs __n objects starting at __end_ from __x
892 // throws if construction throws
893 // Precondition: __n > 0
894 // Precondition: size() + __n <= capacity()
895 // Postcondition: size() == old size() + __n
896 // Postcondition: [i] == __x for all i in [size() - __n, __n)
897 template <class _Tp, class _Allocator>
898 _LIBCPP_INLINE_VISIBILITY inline
900 vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
902 allocator_type& __a = this->__alloc();
905 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
911 template <class _Tp, class _Allocator>
912 template <class _ForwardIterator>
915 __is_forward_iterator<_ForwardIterator>::value,
918 vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
920 allocator_type& __a = this->__alloc();
921 for (; __first != __last; ++__first)
923 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first);
928 template <class _Tp, class _Allocator>
930 vector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last)
932 allocator_type& __a = this->__alloc();
933 for (; __first != __last; ++__first)
935 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
936 _VSTD::move(*__first));
941 // Default constructs __n objects starting at __end_
942 // throws if construction throws
943 // Postcondition: size() == size() + __n
944 // Exception safety: strong.
945 template <class _Tp, class _Allocator>
947 vector<_Tp, _Allocator>::__append(size_type __n)
949 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
950 this->__construct_at_end(__n);
953 allocator_type& __a = this->__alloc();
954 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
955 __v.__construct_at_end(__n);
956 __swap_out_circular_buffer(__v);
960 // Default constructs __n objects starting at __end_
961 // throws if construction throws
962 // Postcondition: size() == size() + __n
963 // Exception safety: strong.
964 template <class _Tp, class _Allocator>
966 vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
968 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
969 this->__construct_at_end(__n, __x);
972 allocator_type& __a = this->__alloc();
973 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
974 __v.__construct_at_end(__n, __x);
975 __swap_out_circular_buffer(__v);
979 template <class _Tp, class _Allocator>
980 vector<_Tp, _Allocator>::vector(size_type __n)
982 #if _LIBCPP_DEBUG_LEVEL >= 2
983 __get_db()->__insert_c(this);
988 __construct_at_end(__n);
992 template <class _Tp, class _Allocator>
993 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x)
995 #if _LIBCPP_DEBUG_LEVEL >= 2
996 __get_db()->__insert_c(this);
1001 __construct_at_end(__n, __x);
1005 template <class _Tp, class _Allocator>
1006 vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a)
1009 #if _LIBCPP_DEBUG_LEVEL >= 2
1010 __get_db()->__insert_c(this);
1015 __construct_at_end(__n, __x);
1019 template <class _Tp, class _Allocator>
1020 template <class _InputIterator>
1021 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
1022 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1023 !__is_forward_iterator<_InputIterator>::value>::type*)
1025 #if _LIBCPP_DEBUG_LEVEL >= 2
1026 __get_db()->__insert_c(this);
1028 for (; __first != __last; ++__first)
1029 push_back(*__first);
1032 template <class _Tp, class _Allocator>
1033 template <class _InputIterator>
1034 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1035 typename enable_if<__is_input_iterator <_InputIterator>::value &&
1036 !__is_forward_iterator<_InputIterator>::value>::type*)
1039 #if _LIBCPP_DEBUG_LEVEL >= 2
1040 __get_db()->__insert_c(this);
1042 for (; __first != __last; ++__first)
1043 push_back(*__first);
1046 template <class _Tp, class _Allocator>
1047 template <class _ForwardIterator>
1048 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
1049 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
1051 #if _LIBCPP_DEBUG_LEVEL >= 2
1052 __get_db()->__insert_c(this);
1054 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1058 __construct_at_end(__first, __last);
1062 template <class _Tp, class _Allocator>
1063 template <class _ForwardIterator>
1064 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
1065 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
1068 #if _LIBCPP_DEBUG_LEVEL >= 2
1069 __get_db()->__insert_c(this);
1071 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1075 __construct_at_end(__first, __last);
1079 template <class _Tp, class _Allocator>
1080 vector<_Tp, _Allocator>::vector(const vector& __x)
1081 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1083 #if _LIBCPP_DEBUG_LEVEL >= 2
1084 __get_db()->__insert_c(this);
1086 size_type __n = __x.size();
1090 __construct_at_end(__x.__begin_, __x.__end_);
1094 template <class _Tp, class _Allocator>
1095 vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1098 #if _LIBCPP_DEBUG_LEVEL >= 2
1099 __get_db()->__insert_c(this);
1101 size_type __n = __x.size();
1105 __construct_at_end(__x.__begin_, __x.__end_);
1109 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1111 template <class _Tp, class _Allocator>
1112 _LIBCPP_INLINE_VISIBILITY inline
1113 vector<_Tp, _Allocator>::vector(vector&& __x)
1114 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1115 : __base(_VSTD::move(__x.__alloc()))
1117 #if _LIBCPP_DEBUG_LEVEL >= 2
1118 __get_db()->__insert_c(this);
1119 __get_db()->swap(this, &__x);
1121 this->__begin_ = __x.__begin_;
1122 this->__end_ = __x.__end_;
1123 this->__end_cap() = __x.__end_cap();
1124 __x.__begin_ = __x.__end_ = __x.__end_cap() = 0;
1127 template <class _Tp, class _Allocator>
1128 _LIBCPP_INLINE_VISIBILITY inline
1129 vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1132 #if _LIBCPP_DEBUG_LEVEL >= 2
1133 __get_db()->__insert_c(this);
1135 if (__a == __x.__alloc())
1137 this->__begin_ = __x.__begin_;
1138 this->__end_ = __x.__end_;
1139 this->__end_cap() = __x.__end_cap();
1140 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1141 #if _LIBCPP_DEBUG_LEVEL >= 2
1142 __get_db()->swap(this, &__x);
1147 typedef move_iterator<iterator> _I;
1148 assign(_I(__x.begin()), _I(__x.end()));
1152 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1154 template <class _Tp, class _Allocator>
1155 _LIBCPP_INLINE_VISIBILITY inline
1156 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1158 #if _LIBCPP_DEBUG_LEVEL >= 2
1159 __get_db()->__insert_c(this);
1161 if (__il.size() > 0)
1163 allocate(__il.size());
1164 __construct_at_end(__il.begin(), __il.end());
1168 template <class _Tp, class _Allocator>
1169 _LIBCPP_INLINE_VISIBILITY inline
1170 vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1173 #if _LIBCPP_DEBUG_LEVEL >= 2
1174 __get_db()->__insert_c(this);
1176 if (__il.size() > 0)
1178 allocate(__il.size());
1179 __construct_at_end(__il.begin(), __il.end());
1183 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1185 template <class _Tp, class _Allocator>
1186 _LIBCPP_INLINE_VISIBILITY inline
1187 vector<_Tp, _Allocator>&
1188 vector<_Tp, _Allocator>::operator=(vector&& __x)
1190 __alloc_traits::propagate_on_container_move_assignment::value &&
1191 is_nothrow_move_assignable<allocator_type>::value)
1193 __move_assign(__x, integral_constant<bool,
1194 __alloc_traits::propagate_on_container_move_assignment::value>());
1198 template <class _Tp, class _Allocator>
1200 vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1202 if (__base::__alloc() != __c.__alloc())
1204 typedef move_iterator<iterator> _I;
1205 assign(_I(__c.begin()), _I(__c.end()));
1208 __move_assign(__c, true_type());
1211 template <class _Tp, class _Allocator>
1213 vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1214 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1217 this->__begin_ = __c.__begin_;
1218 this->__end_ = __c.__end_;
1219 this->__end_cap() = __c.__end_cap();
1220 __base::__move_assign_alloc(__c);
1221 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1222 #if _LIBCPP_DEBUG_LEVEL >= 2
1223 __get_db()->swap(this, &__c);
1227 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1229 template <class _Tp, class _Allocator>
1230 _LIBCPP_INLINE_VISIBILITY inline
1231 vector<_Tp, _Allocator>&
1232 vector<_Tp, _Allocator>::operator=(const vector& __x)
1236 __base::__copy_assign_alloc(__x);
1237 assign(__x.__begin_, __x.__end_);
1242 template <class _Tp, class _Allocator>
1243 template <class _InputIterator>
1246 __is_input_iterator <_InputIterator>::value &&
1247 !__is_forward_iterator<_InputIterator>::value,
1250 vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1253 for (; __first != __last; ++__first)
1254 push_back(*__first);
1257 template <class _Tp, class _Allocator>
1258 template <class _ForwardIterator>
1261 __is_forward_iterator<_ForwardIterator>::value,
1264 vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1266 typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last);
1267 if (static_cast<size_type>(__new_size) <= capacity())
1269 _ForwardIterator __mid = __last;
1270 bool __growing = false;
1271 if (static_cast<size_type>(__new_size) > size())
1275 _VSTD::advance(__mid, size());
1277 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
1279 __construct_at_end(__mid, __last);
1281 this->__destruct_at_end(__m);
1286 allocate(__recommend(static_cast<size_type>(__new_size)));
1287 __construct_at_end(__first, __last);
1291 template <class _Tp, class _Allocator>
1293 vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1295 if (__n <= capacity())
1297 size_type __s = size();
1298 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
1300 __construct_at_end(__n - __s, __u);
1302 this->__destruct_at_end(this->__begin_ + __n);
1307 allocate(__recommend(static_cast<size_type>(__n)));
1308 __construct_at_end(__n, __u);
1312 template <class _Tp, class _Allocator>
1313 _LIBCPP_INLINE_VISIBILITY inline
1314 typename vector<_Tp, _Allocator>::iterator
1315 vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
1317 #if _LIBCPP_DEBUG_LEVEL >= 2
1318 return iterator(this, __p);
1320 return iterator(__p);
1324 template <class _Tp, class _Allocator>
1325 _LIBCPP_INLINE_VISIBILITY inline
1326 typename vector<_Tp, _Allocator>::const_iterator
1327 vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
1329 #if _LIBCPP_DEBUG_LEVEL >= 2
1330 return const_iterator(this, __p);
1332 return const_iterator(__p);
1336 template <class _Tp, class _Allocator>
1337 _LIBCPP_INLINE_VISIBILITY inline
1338 typename vector<_Tp, _Allocator>::iterator
1339 vector<_Tp, _Allocator>::begin() _NOEXCEPT
1341 return __make_iter(this->__begin_);
1344 template <class _Tp, class _Allocator>
1345 _LIBCPP_INLINE_VISIBILITY inline
1346 typename vector<_Tp, _Allocator>::const_iterator
1347 vector<_Tp, _Allocator>::begin() const _NOEXCEPT
1349 return __make_iter(this->__begin_);
1352 template <class _Tp, class _Allocator>
1353 _LIBCPP_INLINE_VISIBILITY inline
1354 typename vector<_Tp, _Allocator>::iterator
1355 vector<_Tp, _Allocator>::end() _NOEXCEPT
1357 return __make_iter(this->__end_);
1360 template <class _Tp, class _Allocator>
1361 _LIBCPP_INLINE_VISIBILITY inline
1362 typename vector<_Tp, _Allocator>::const_iterator
1363 vector<_Tp, _Allocator>::end() const _NOEXCEPT
1365 return __make_iter(this->__end_);
1368 template <class _Tp, class _Allocator>
1369 _LIBCPP_INLINE_VISIBILITY inline
1370 typename vector<_Tp, _Allocator>::reference
1371 vector<_Tp, _Allocator>::operator[](size_type __n)
1373 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1374 return this->__begin_[__n];
1377 template <class _Tp, class _Allocator>
1378 _LIBCPP_INLINE_VISIBILITY inline
1379 typename vector<_Tp, _Allocator>::const_reference
1380 vector<_Tp, _Allocator>::operator[](size_type __n) const
1382 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1383 return this->__begin_[__n];
1386 template <class _Tp, class _Allocator>
1387 typename vector<_Tp, _Allocator>::reference
1388 vector<_Tp, _Allocator>::at(size_type __n)
1391 this->__throw_out_of_range();
1392 return this->__begin_[__n];
1395 template <class _Tp, class _Allocator>
1396 typename vector<_Tp, _Allocator>::const_reference
1397 vector<_Tp, _Allocator>::at(size_type __n) const
1400 this->__throw_out_of_range();
1401 return this->__begin_[__n];
1404 template <class _Tp, class _Allocator>
1406 vector<_Tp, _Allocator>::reserve(size_type __n)
1408 if (__n > capacity())
1410 allocator_type& __a = this->__alloc();
1411 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1412 __swap_out_circular_buffer(__v);
1416 template <class _Tp, class _Allocator>
1418 vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1420 if (capacity() > size())
1422 #ifndef _LIBCPP_NO_EXCEPTIONS
1425 #endif // _LIBCPP_NO_EXCEPTIONS
1426 allocator_type& __a = this->__alloc();
1427 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1428 __swap_out_circular_buffer(__v);
1429 #ifndef _LIBCPP_NO_EXCEPTIONS
1434 #endif // _LIBCPP_NO_EXCEPTIONS
1438 template <class _Tp, class _Allocator>
1440 vector<_Tp, _Allocator>::push_back(const_reference __x)
1442 if (this->__end_ < this->__end_cap())
1444 __alloc_traits::construct(this->__alloc(),
1445 _VSTD::__to_raw_pointer(this->__end_), __x);
1450 allocator_type& __a = this->__alloc();
1451 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1453 __swap_out_circular_buffer(__v);
1457 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1459 template <class _Tp, class _Allocator>
1461 vector<_Tp, _Allocator>::push_back(value_type&& __x)
1463 if (this->__end_ < this->__end_cap())
1465 __alloc_traits::construct(this->__alloc(),
1466 _VSTD::__to_raw_pointer(this->__end_),
1472 allocator_type& __a = this->__alloc();
1473 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1474 __v.push_back(_VSTD::move(__x));
1475 __swap_out_circular_buffer(__v);
1479 #ifndef _LIBCPP_HAS_NO_VARIADICS
1481 template <class _Tp, class _Allocator>
1482 template <class... _Args>
1484 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1486 if (this->__end_ < this->__end_cap())
1488 __alloc_traits::construct(this->__alloc(),
1489 _VSTD::__to_raw_pointer(this->__end_),
1490 _VSTD::forward<_Args>(__args)...);
1495 allocator_type& __a = this->__alloc();
1496 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1497 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1498 __swap_out_circular_buffer(__v);
1502 #endif // _LIBCPP_HAS_NO_VARIADICS
1503 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1505 template <class _Tp, class _Allocator>
1506 _LIBCPP_INLINE_VISIBILITY inline
1508 vector<_Tp, _Allocator>::pop_back()
1510 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1511 this->__destruct_at_end(this->__end_ - 1);
1514 template <class _Tp, class _Allocator>
1515 _LIBCPP_INLINE_VISIBILITY inline
1516 typename vector<_Tp, _Allocator>::iterator
1517 vector<_Tp, _Allocator>::erase(const_iterator __position)
1519 #if _LIBCPP_DEBUG_LEVEL >= 2
1520 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1521 "vector::erase(iterator) called with an iterator not"
1522 " referring to this vector");
1524 pointer __p = const_cast<pointer>(&*__position);
1525 iterator __r = __make_iter(__p);
1526 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1530 template <class _Tp, class _Allocator>
1531 typename vector<_Tp, _Allocator>::iterator
1532 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1534 #if _LIBCPP_DEBUG_LEVEL >= 2
1535 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1536 "vector::erase(iterator, iterator) called with an iterator not"
1537 " referring to this vector");
1539 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1540 pointer __p = this->__begin_ + (__first - begin());
1541 iterator __r = __make_iter(__p);
1542 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1546 template <class _Tp, class _Allocator>
1548 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1550 pointer __old_last = this->__end_;
1551 difference_type __n = __old_last - __to;
1552 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1553 __alloc_traits::construct(this->__alloc(),
1554 _VSTD::__to_raw_pointer(this->__end_),
1556 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1559 template <class _Tp, class _Allocator>
1560 typename vector<_Tp, _Allocator>::iterator
1561 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1563 #if _LIBCPP_DEBUG_LEVEL >= 2
1564 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1565 "vector::insert(iterator, x) called with an iterator not"
1566 " referring to this vector");
1568 pointer __p = this->__begin_ + (__position - begin());
1569 if (this->__end_ < this->__end_cap())
1571 if (__p == this->__end_)
1573 __alloc_traits::construct(this->__alloc(),
1574 _VSTD::__to_raw_pointer(this->__end_), __x);
1579 __move_range(__p, this->__end_, __p + 1);
1580 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1581 if (__p <= __xr && __xr < this->__end_)
1588 allocator_type& __a = this->__alloc();
1589 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1591 __p = __swap_out_circular_buffer(__v, __p);
1593 return __make_iter(__p);
1596 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1598 template <class _Tp, class _Allocator>
1599 typename vector<_Tp, _Allocator>::iterator
1600 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1602 #if _LIBCPP_DEBUG_LEVEL >= 2
1603 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1604 "vector::insert(iterator, x) called with an iterator not"
1605 " referring to this vector");
1607 pointer __p = this->__begin_ + (__position - begin());
1608 if (this->__end_ < this->__end_cap())
1610 if (__p == this->__end_)
1612 __alloc_traits::construct(this->__alloc(),
1613 _VSTD::__to_raw_pointer(this->__end_),
1619 __move_range(__p, this->__end_, __p + 1);
1620 *__p = _VSTD::move(__x);
1625 allocator_type& __a = this->__alloc();
1626 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1627 __v.push_back(_VSTD::move(__x));
1628 __p = __swap_out_circular_buffer(__v, __p);
1630 return __make_iter(__p);
1633 #ifndef _LIBCPP_HAS_NO_VARIADICS
1635 template <class _Tp, class _Allocator>
1636 template <class... _Args>
1637 typename vector<_Tp, _Allocator>::iterator
1638 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1640 #if _LIBCPP_DEBUG_LEVEL >= 2
1641 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1642 "vector::emplace(iterator, x) called with an iterator not"
1643 " referring to this vector");
1645 pointer __p = this->__begin_ + (__position - begin());
1646 if (this->__end_ < this->__end_cap())
1648 if (__p == this->__end_)
1650 __alloc_traits::construct(this->__alloc(),
1651 _VSTD::__to_raw_pointer(this->__end_),
1652 _VSTD::forward<_Args>(__args)...);
1657 __move_range(__p, this->__end_, __p + 1);
1658 *__p = value_type(_VSTD::forward<_Args>(__args)...);
1663 allocator_type& __a = this->__alloc();
1664 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1665 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1666 __p = __swap_out_circular_buffer(__v, __p);
1668 return __make_iter(__p);
1671 #endif // _LIBCPP_HAS_NO_VARIADICS
1672 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1674 template <class _Tp, class _Allocator>
1675 typename vector<_Tp, _Allocator>::iterator
1676 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1678 #if _LIBCPP_DEBUG_LEVEL >= 2
1679 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1680 "vector::insert(iterator, n, x) called with an iterator not"
1681 " referring to this vector");
1683 pointer __p = this->__begin_ + (__position - begin());
1686 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1688 size_type __old_n = __n;
1689 pointer __old_last = this->__end_;
1690 if (__n > static_cast<size_type>(this->__end_ - __p))
1692 size_type __cx = __n - (this->__end_ - __p);
1693 __construct_at_end(__cx, __x);
1698 __move_range(__p, __old_last, __p + __old_n);
1699 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1700 if (__p <= __xr && __xr < this->__end_)
1702 _VSTD::fill_n(__p, __n, *__xr);
1707 allocator_type& __a = this->__alloc();
1708 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1709 __v.__construct_at_end(__n, __x);
1710 __p = __swap_out_circular_buffer(__v, __p);
1713 return __make_iter(__p);
1716 template <class _Tp, class _Allocator>
1717 template <class _InputIterator>
1720 __is_input_iterator <_InputIterator>::value &&
1721 !__is_forward_iterator<_InputIterator>::value,
1722 typename vector<_Tp, _Allocator>::iterator
1724 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1726 #if _LIBCPP_DEBUG_LEVEL >= 2
1727 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1728 "vector::insert(iterator, range) called with an iterator not"
1729 " referring to this vector");
1731 difference_type __off = __position - begin();
1732 pointer __p = this->__begin_ + __off;
1733 allocator_type& __a = this->__alloc();
1734 pointer __old_last = this->__end_;
1735 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1737 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
1741 __split_buffer<value_type, allocator_type&> __v(__a);
1742 if (__first != __last)
1744 #ifndef _LIBCPP_NO_EXCEPTIONS
1747 #endif // _LIBCPP_NO_EXCEPTIONS
1748 __v.__construct_at_end(__first, __last);
1749 difference_type __old_size = __old_last - this->__begin_;
1750 difference_type __old_p = __p - this->__begin_;
1751 reserve(__recommend(size() + __v.size()));
1752 __p = this->__begin_ + __old_p;
1753 __old_last = this->__begin_ + __old_size;
1754 #ifndef _LIBCPP_NO_EXCEPTIONS
1758 erase(__make_iter(__old_last), end());
1761 #endif // _LIBCPP_NO_EXCEPTIONS
1763 __p = _VSTD::rotate(__p, __old_last, this->__end_);
1764 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1765 make_move_iterator(__v.end()));
1766 return begin() + __off;
1769 template <class _Tp, class _Allocator>
1770 template <class _ForwardIterator>
1773 __is_forward_iterator<_ForwardIterator>::value,
1774 typename vector<_Tp, _Allocator>::iterator
1776 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1778 #if _LIBCPP_DEBUG_LEVEL >= 2
1779 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1780 "vector::insert(iterator, range) called with an iterator not"
1781 " referring to this vector");
1783 pointer __p = this->__begin_ + (__position - begin());
1784 difference_type __n = _VSTD::distance(__first, __last);
1787 if (__n <= this->__end_cap() - this->__end_)
1789 size_type __old_n = __n;
1790 pointer __old_last = this->__end_;
1791 _ForwardIterator __m = __last;
1792 difference_type __dx = this->__end_ - __p;
1796 _VSTD::advance(__m, this->__end_ - __p);
1797 __construct_at_end(__m, __last);
1802 __move_range(__p, __old_last, __p + __old_n);
1803 _VSTD::copy(__first, __m, __p);
1808 allocator_type& __a = this->__alloc();
1809 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1810 __v.__construct_at_end(__first, __last);
1811 __p = __swap_out_circular_buffer(__v, __p);
1814 return __make_iter(__p);
1817 template <class _Tp, class _Allocator>
1819 vector<_Tp, _Allocator>::resize(size_type __sz)
1821 size_type __cs = size();
1823 this->__append(__sz - __cs);
1824 else if (__cs > __sz)
1825 this->__destruct_at_end(this->__begin_ + __sz);
1828 template <class _Tp, class _Allocator>
1830 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
1832 size_type __cs = size();
1834 this->__append(__sz - __cs, __x);
1835 else if (__cs > __sz)
1836 this->__destruct_at_end(this->__begin_ + __sz);
1839 template <class _Tp, class _Allocator>
1841 vector<_Tp, _Allocator>::swap(vector& __x)
1842 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1843 __is_nothrow_swappable<allocator_type>::value)
1845 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
1846 this->__alloc() == __x.__alloc(),
1847 "vector::swap: Either propagate_on_container_swap must be true"
1848 " or the allocators must compare equal");
1849 _VSTD::swap(this->__begin_, __x.__begin_);
1850 _VSTD::swap(this->__end_, __x.__end_);
1851 _VSTD::swap(this->__end_cap(), __x.__end_cap());
1852 __base::__swap_alloc(this->__alloc(), __x.__alloc());
1853 #if _LIBCPP_DEBUG_LEVEL >= 2
1854 __get_db()->swap(this, &__x);
1855 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1858 template <class _Tp, class _Allocator>
1860 vector<_Tp, _Allocator>::__invariants() const
1862 if (this->__begin_ == 0)
1864 if (this->__end_ != 0 || this->__end_cap() != 0)
1869 if (this->__begin_ > this->__end_)
1871 if (this->__begin_ == this->__end_cap())
1873 if (this->__end_ > this->__end_cap())
1879 #if _LIBCPP_DEBUG_LEVEL >= 2
1881 template <class _Tp, class _Allocator>
1883 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
1885 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
1888 template <class _Tp, class _Allocator>
1890 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
1892 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
1895 template <class _Tp, class _Allocator>
1897 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
1899 const_pointer __p = __i->base() + __n;
1900 return this->__begin_ <= __p && __p <= this->__end_;
1903 template <class _Tp, class _Allocator>
1905 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1907 const_pointer __p = __i->base() + __n;
1908 return this->__begin_ <= __p && __p < this->__end_;
1911 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1913 template <class _Tp, class _Allocator>
1914 _LIBCPP_INLINE_VISIBILITY inline
1916 vector<_Tp, _Allocator>::__invalidate_all_iterators()
1918 #if _LIBCPP_DEBUG_LEVEL >= 2
1919 __get_db()->__invalidate_all(this);
1920 #endif // _LIBCPP_DEBUG_LEVEL >= 2
1925 template <class _Allocator> class vector<bool, _Allocator>;
1927 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
1929 template <class _Allocator>
1930 struct __has_storage_type<vector<bool, _Allocator> >
1932 static const bool value = true;
1935 template <class _Allocator>
1936 class _LIBCPP_VISIBLE vector<bool, _Allocator>
1937 : private __vector_base_common<true>
1940 typedef vector __self;
1941 typedef bool value_type;
1942 typedef _Allocator allocator_type;
1943 typedef allocator_traits<allocator_type> __alloc_traits;
1944 typedef typename __alloc_traits::size_type size_type;
1945 typedef typename __alloc_traits::difference_type difference_type;
1946 typedef __bit_iterator<vector, false> pointer;
1947 typedef __bit_iterator<vector, true> const_pointer;
1948 #ifdef _LIBCPP_DEBUG
1949 typedef __debug_iter<vector, pointer> iterator;
1950 typedef __debug_iter<vector, const_pointer> const_iterator;
1952 friend class __debug_iter<vector, pointer>;
1953 friend class __debug_iter<vector, const_pointer>;
1955 pair<iterator*, const_iterator*> __iterator_list_;
1957 _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;}
1958 _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;}
1959 #else // _LIBCPP_DEBUG
1960 typedef pointer iterator;
1961 typedef const_pointer const_iterator;
1962 #endif // _LIBCPP_DEBUG
1963 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1964 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
1967 typedef size_type __storage_type;
1968 typedef typename __alloc_traits::template
1969 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1970 rebind_alloc<__storage_type>
1972 rebind_alloc<__storage_type>::other
1974 __storage_allocator;
1975 typedef allocator_traits<__storage_allocator> __storage_traits;
1976 typedef typename __storage_traits::pointer __storage_pointer;
1977 typedef typename __storage_traits::const_pointer __const_storage_pointer;
1979 __storage_pointer __begin_;
1981 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
1983 typedef __bit_reference<vector> reference;
1984 typedef __bit_const_reference<vector> const_reference;
1986 _LIBCPP_INLINE_VISIBILITY
1987 size_type& __cap() _NOEXCEPT
1988 {return __cap_alloc_.first();}
1989 _LIBCPP_INLINE_VISIBILITY
1990 const size_type& __cap() const _NOEXCEPT
1991 {return __cap_alloc_.first();}
1992 _LIBCPP_INLINE_VISIBILITY
1993 __storage_allocator& __alloc() _NOEXCEPT
1994 {return __cap_alloc_.second();}
1995 _LIBCPP_INLINE_VISIBILITY
1996 const __storage_allocator& __alloc() const _NOEXCEPT
1997 {return __cap_alloc_.second();}
1999 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2001 _LIBCPP_INLINE_VISIBILITY
2002 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2003 {return __n * __bits_per_word;}
2004 _LIBCPP_INLINE_VISIBILITY
2005 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2006 {return (__n - 1) / __bits_per_word + 1;}
2009 _LIBCPP_INLINE_VISIBILITY
2011 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2012 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a);
2014 explicit vector(size_type __n);
2015 vector(size_type __n, const value_type& __v);
2016 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2017 template <class _InputIterator>
2018 vector(_InputIterator __first, _InputIterator __last,
2019 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2020 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2021 template <class _InputIterator>
2022 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2023 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2024 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2025 template <class _ForwardIterator>
2026 vector(_ForwardIterator __first, _ForwardIterator __last,
2027 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2028 template <class _ForwardIterator>
2029 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2030 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2032 vector(const vector& __v);
2033 vector(const vector& __v, const allocator_type& __a);
2034 vector& operator=(const vector& __v);
2035 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2036 vector(initializer_list<value_type> __il);
2037 vector(initializer_list<value_type> __il, const allocator_type& __a);
2038 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2040 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2041 _LIBCPP_INLINE_VISIBILITY
2042 vector(vector&& __v)
2043 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2044 vector(vector&& __v, const allocator_type& __a);
2045 _LIBCPP_INLINE_VISIBILITY
2046 vector& operator=(vector&& __v)
2048 __alloc_traits::propagate_on_container_move_assignment::value &&
2049 is_nothrow_move_assignable<allocator_type>::value);
2050 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2051 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2052 _LIBCPP_INLINE_VISIBILITY
2053 vector& operator=(initializer_list<value_type> __il)
2054 {assign(__il.begin(), __il.end()); return *this;}
2055 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2057 template <class _InputIterator>
2060 __is_input_iterator<_InputIterator>::value &&
2061 !__is_forward_iterator<_InputIterator>::value,
2064 assign(_InputIterator __first, _InputIterator __last);
2065 template <class _ForwardIterator>
2068 __is_forward_iterator<_ForwardIterator>::value,
2071 assign(_ForwardIterator __first, _ForwardIterator __last);
2073 void assign(size_type __n, const value_type& __x);
2074 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2075 _LIBCPP_INLINE_VISIBILITY
2076 void assign(initializer_list<value_type> __il)
2077 {assign(__il.begin(), __il.end());}
2078 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2080 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2081 {return allocator_type(this->__alloc());}
2083 size_type max_size() const _NOEXCEPT;
2084 _LIBCPP_INLINE_VISIBILITY
2085 size_type capacity() const _NOEXCEPT
2086 {return __internal_cap_to_external(__cap());}
2087 _LIBCPP_INLINE_VISIBILITY
2088 size_type size() const _NOEXCEPT
2090 _LIBCPP_INLINE_VISIBILITY
2091 bool empty() const _NOEXCEPT
2092 {return __size_ == 0;}
2093 void reserve(size_type __n);
2094 void shrink_to_fit() _NOEXCEPT;
2096 _LIBCPP_INLINE_VISIBILITY
2097 iterator begin() _NOEXCEPT
2098 {return __make_iter(0);}
2099 _LIBCPP_INLINE_VISIBILITY
2100 const_iterator begin() const _NOEXCEPT
2101 {return __make_iter(0);}
2102 _LIBCPP_INLINE_VISIBILITY
2103 iterator end() _NOEXCEPT
2104 {return __make_iter(__size_);}
2105 _LIBCPP_INLINE_VISIBILITY
2106 const_iterator end() const _NOEXCEPT
2107 {return __make_iter(__size_);}
2109 _LIBCPP_INLINE_VISIBILITY
2110 reverse_iterator rbegin() _NOEXCEPT
2111 {return reverse_iterator(end());}
2112 _LIBCPP_INLINE_VISIBILITY
2113 const_reverse_iterator rbegin() const _NOEXCEPT
2114 {return const_reverse_iterator(end());}
2115 _LIBCPP_INLINE_VISIBILITY
2116 reverse_iterator rend() _NOEXCEPT
2117 {return reverse_iterator(begin());}
2118 _LIBCPP_INLINE_VISIBILITY
2119 const_reverse_iterator rend() const _NOEXCEPT
2120 {return const_reverse_iterator(begin());}
2122 _LIBCPP_INLINE_VISIBILITY
2123 const_iterator cbegin() const _NOEXCEPT
2124 {return __make_iter(0);}
2125 _LIBCPP_INLINE_VISIBILITY
2126 const_iterator cend() const _NOEXCEPT
2127 {return __make_iter(__size_);}
2128 _LIBCPP_INLINE_VISIBILITY
2129 const_reverse_iterator crbegin() const _NOEXCEPT
2131 _LIBCPP_INLINE_VISIBILITY
2132 const_reverse_iterator crend() const _NOEXCEPT
2135 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2136 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2137 reference at(size_type __n);
2138 const_reference at(size_type __n) const;
2140 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2141 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2142 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2143 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2145 void push_back(const value_type& __x);
2146 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2148 iterator insert(const_iterator __position, const value_type& __x);
2149 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2150 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2151 template <class _InputIterator>
2154 __is_input_iterator <_InputIterator>::value &&
2155 !__is_forward_iterator<_InputIterator>::value,
2158 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2159 template <class _ForwardIterator>
2162 __is_forward_iterator<_ForwardIterator>::value,
2165 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2166 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2167 _LIBCPP_INLINE_VISIBILITY
2168 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2169 {return insert(__position, __il.begin(), __il.end());}
2170 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2172 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2173 iterator erase(const_iterator __first, const_iterator __last);
2175 _LIBCPP_INLINE_VISIBILITY
2176 void clear() _NOEXCEPT {__size_ = 0;}
2179 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2180 __is_nothrow_swappable<allocator_type>::value);
2182 void resize(size_type __sz, value_type __x = false);
2183 void flip() _NOEXCEPT;
2185 bool __invariants() const;
2188 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2189 void allocate(size_type __n);
2190 void deallocate() _NOEXCEPT;
2191 _LIBCPP_INLINE_VISIBILITY
2192 static size_type __align(size_type __new_size) _NOEXCEPT
2193 {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);};
2194 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2195 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2196 template <class _ForwardIterator>
2199 __is_forward_iterator<_ForwardIterator>::value,
2202 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2203 void __append(size_type __n, const_reference __x);
2204 _LIBCPP_INLINE_VISIBILITY
2205 reference __make_ref(size_type __pos) _NOEXCEPT
2206 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2207 _LIBCPP_INLINE_VISIBILITY
2208 const_reference __make_ref(size_type __pos) const _NOEXCEPT
2209 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2210 #ifdef _LIBCPP_DEBUG
2211 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos)
2212 {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2213 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const
2214 {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2215 _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p)
2216 {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));}
2217 #else // _LIBCPP_DEBUG
2218 _LIBCPP_INLINE_VISIBILITY
2219 iterator __make_iter(size_type __pos) _NOEXCEPT
2220 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2221 _LIBCPP_INLINE_VISIBILITY
2222 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2223 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2224 _LIBCPP_INLINE_VISIBILITY
2225 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2226 {return iterator(const_cast<__storage_pointer>(__p.__seg_), __p.__ctz_);}
2227 #endif // _LIBCPP_DEBUG
2229 _LIBCPP_INLINE_VISIBILITY
2230 void __copy_assign_alloc(const vector& __v)
2231 {__copy_assign_alloc(__v, integral_constant<bool,
2232 __storage_traits::propagate_on_container_copy_assignment::value>());}
2233 _LIBCPP_INLINE_VISIBILITY
2234 void __copy_assign_alloc(const vector& __c, true_type)
2236 if (__alloc() != __c.__alloc())
2238 __alloc() = __c.__alloc();
2241 _LIBCPP_INLINE_VISIBILITY
2242 void __copy_assign_alloc(const vector& __c, false_type)
2245 void __move_assign(vector& __c, false_type);
2246 void __move_assign(vector& __c, true_type)
2247 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2248 _LIBCPP_INLINE_VISIBILITY
2249 void __move_assign_alloc(vector& __c)
2251 !__storage_traits::propagate_on_container_move_assignment::value ||
2252 is_nothrow_move_assignable<allocator_type>::value)
2253 {__move_assign_alloc(__c, integral_constant<bool,
2254 __storage_traits::propagate_on_container_move_assignment::value>());}
2255 _LIBCPP_INLINE_VISIBILITY
2256 void __move_assign_alloc(vector& __c, true_type)
2257 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2259 __alloc() = _VSTD::move(__c.__alloc());
2262 _LIBCPP_INLINE_VISIBILITY
2263 void __move_assign_alloc(vector& __c, false_type)
2267 _LIBCPP_INLINE_VISIBILITY
2268 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y)
2270 !__storage_traits::propagate_on_container_swap::value ||
2271 __is_nothrow_swappable<allocator_type>::value)
2272 {__swap_alloc(__x, __y, integral_constant<bool,
2273 __storage_traits::propagate_on_container_swap::value>());}
2275 _LIBCPP_INLINE_VISIBILITY
2276 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type)
2277 _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
2282 _LIBCPP_INLINE_VISIBILITY
2283 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, false_type)
2287 size_t __hash_code() const _NOEXCEPT;
2289 friend class __bit_reference<vector>;
2290 friend class __bit_const_reference<vector>;
2291 friend class __bit_iterator<vector, false>;
2292 friend class __bit_iterator<vector, true>;
2293 friend class __bit_array<vector>;
2294 friend struct _LIBCPP_VISIBLE hash<vector>;
2297 template <class _Allocator>
2298 #ifndef _LIBCPP_DEBUG
2299 _LIBCPP_INLINE_VISIBILITY inline
2302 vector<bool, _Allocator>::__invalidate_all_iterators()
2304 #ifdef _LIBCPP_DEBUG
2305 iterator::__remove_all(this);
2306 const_iterator::__remove_all(this);
2307 #endif // _LIBCPP_DEBUG
2310 // Allocate space for __n objects
2311 // throws length_error if __n > max_size()
2312 // throws (probably bad_alloc) if memory run out
2313 // Precondition: __begin_ == __end_ == __cap() == 0
2314 // Precondition: __n > 0
2315 // Postcondition: capacity() == __n
2316 // Postcondition: size() == 0
2317 template <class _Allocator>
2319 vector<bool, _Allocator>::allocate(size_type __n)
2321 if (__n > max_size())
2322 this->__throw_length_error();
2323 __n = __external_cap_to_internal(__n);
2324 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2326 this->__cap() = __n;
2329 template <class _Allocator>
2331 vector<bool, _Allocator>::deallocate() _NOEXCEPT
2333 if (this->__begin_ != 0)
2335 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2336 __invalidate_all_iterators();
2338 this->__size_ = this->__cap() = 0;
2342 template <class _Allocator>
2343 typename vector<bool, _Allocator>::size_type
2344 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2346 size_type __amax = __storage_traits::max_size(__alloc());
2347 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2348 if (__nmax / __bits_per_word <= __amax)
2350 return __internal_cap_to_external(__amax);
2353 // Precondition: __new_size > capacity()
2354 template <class _Allocator>
2355 _LIBCPP_INLINE_VISIBILITY inline
2356 typename vector<bool, _Allocator>::size_type
2357 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2359 const size_type __ms = max_size();
2360 if (__new_size > __ms)
2361 this->__throw_length_error();
2362 const size_type __cap = capacity();
2363 if (__cap >= __ms / 2)
2365 return _VSTD::max(2*__cap, __align(__new_size));
2368 // Default constructs __n objects starting at __end_
2369 // Precondition: __n > 0
2370 // Precondition: size() + __n <= capacity()
2371 // Postcondition: size() == size() + __n
2372 template <class _Allocator>
2373 _LIBCPP_INLINE_VISIBILITY inline
2375 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2377 size_type __old_size = this->__size_;
2378 this->__size_ += __n;
2379 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2382 template <class _Allocator>
2383 template <class _ForwardIterator>
2386 __is_forward_iterator<_ForwardIterator>::value,
2389 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2391 size_type __old_size = this->__size_;
2392 this->__size_ += _VSTD::distance(__first, __last);
2393 _VSTD::copy(__first, __last, __make_iter(__old_size));
2396 template <class _Allocator>
2397 _LIBCPP_INLINE_VISIBILITY inline
2398 vector<bool, _Allocator>::vector()
2399 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2406 template <class _Allocator>
2407 _LIBCPP_INLINE_VISIBILITY inline
2408 vector<bool, _Allocator>::vector(const allocator_type& __a)
2411 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2415 template <class _Allocator>
2416 vector<bool, _Allocator>::vector(size_type __n)
2424 __construct_at_end(__n, false);
2428 template <class _Allocator>
2429 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2437 __construct_at_end(__n, __x);
2441 template <class _Allocator>
2442 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2445 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2450 __construct_at_end(__n, __x);
2454 template <class _Allocator>
2455 template <class _InputIterator>
2456 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2457 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2458 !__is_forward_iterator<_InputIterator>::value>::type*)
2463 #ifndef _LIBCPP_NO_EXCEPTIONS
2466 #endif // _LIBCPP_NO_EXCEPTIONS
2467 for (; __first != __last; ++__first)
2468 push_back(*__first);
2469 #ifndef _LIBCPP_NO_EXCEPTIONS
2474 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2475 __invalidate_all_iterators();
2478 #endif // _LIBCPP_NO_EXCEPTIONS
2481 template <class _Allocator>
2482 template <class _InputIterator>
2483 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2484 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2485 !__is_forward_iterator<_InputIterator>::value>::type*)
2488 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2490 #ifndef _LIBCPP_NO_EXCEPTIONS
2493 #endif // _LIBCPP_NO_EXCEPTIONS
2494 for (; __first != __last; ++__first)
2495 push_back(*__first);
2496 #ifndef _LIBCPP_NO_EXCEPTIONS
2501 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2502 __invalidate_all_iterators();
2505 #endif // _LIBCPP_NO_EXCEPTIONS
2508 template <class _Allocator>
2509 template <class _ForwardIterator>
2510 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2511 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2516 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2520 __construct_at_end(__first, __last);
2524 template <class _Allocator>
2525 template <class _ForwardIterator>
2526 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2527 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2530 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2532 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2536 __construct_at_end(__first, __last);
2540 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2542 template <class _Allocator>
2543 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2548 size_type __n = static_cast<size_type>(__il.size());
2552 __construct_at_end(__il.begin(), __il.end());
2556 template <class _Allocator>
2557 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2560 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2562 size_type __n = static_cast<size_type>(__il.size());
2566 __construct_at_end(__il.begin(), __il.end());
2570 #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2572 template <class _Allocator>
2573 vector<bool, _Allocator>::~vector()
2576 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2577 #ifdef _LIBCPP_DEBUG
2578 __invalidate_all_iterators();
2582 template <class _Allocator>
2583 vector<bool, _Allocator>::vector(const vector& __v)
2586 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2590 allocate(__v.size());
2591 __construct_at_end(__v.begin(), __v.end());
2595 template <class _Allocator>
2596 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2599 __cap_alloc_(0, __a)
2603 allocate(__v.size());
2604 __construct_at_end(__v.begin(), __v.end());
2608 template <class _Allocator>
2609 vector<bool, _Allocator>&
2610 vector<bool, _Allocator>::operator=(const vector& __v)
2614 __copy_assign_alloc(__v);
2617 if (__v.__size_ > capacity())
2620 allocate(__v.__size_);
2622 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2624 __size_ = __v.__size_;
2629 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2631 template <class _Allocator>
2632 _LIBCPP_INLINE_VISIBILITY inline
2633 vector<bool, _Allocator>::vector(vector&& __v)
2634 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2635 : __begin_(__v.__begin_),
2636 __size_(__v.__size_),
2637 __cap_alloc_(__v.__cap_alloc_)
2644 template <class _Allocator>
2645 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2648 __cap_alloc_(0, __a)
2650 if (__a == allocator_type(__v.__alloc()))
2652 this->__begin_ = __v.__begin_;
2653 this->__size_ = __v.__size_;
2654 this->__cap() = __v.__cap();
2655 __v.__begin_ = nullptr;
2656 __v.__cap() = __v.__size_ = 0;
2658 else if (__v.size() > 0)
2660 allocate(__v.size());
2661 __construct_at_end(__v.begin(), __v.end());
2665 template <class _Allocator>
2666 _LIBCPP_INLINE_VISIBILITY inline
2667 vector<bool, _Allocator>&
2668 vector<bool, _Allocator>::operator=(vector&& __v)
2670 __alloc_traits::propagate_on_container_move_assignment::value &&
2671 is_nothrow_move_assignable<allocator_type>::value)
2673 __move_assign(__v, integral_constant<bool,
2674 __storage_traits::propagate_on_container_move_assignment::value>());
2677 template <class _Allocator>
2679 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2681 if (__alloc() != __c.__alloc())
2682 assign(__c.begin(), __c.end());
2684 __move_assign(__c, true_type());
2687 template <class _Allocator>
2689 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2690 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2693 this->__begin_ = __c.__begin_;
2694 this->__size_ = __c.__size_;
2695 this->__cap() = __c.__cap();
2696 __move_assign_alloc(__c);
2697 __c.__begin_ = nullptr;
2698 __c.__cap() = __c.__size_ = 0;
2701 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2703 template <class _Allocator>
2705 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2710 size_type __c = capacity();
2715 vector __v(__alloc());
2716 __v.reserve(__recommend(__n));
2720 _VSTD::fill_n(begin(), __n, __x);
2724 template <class _Allocator>
2725 template <class _InputIterator>
2728 __is_input_iterator<_InputIterator>::value &&
2729 !__is_forward_iterator<_InputIterator>::value,
2732 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2735 for (; __first != __last; ++__first)
2736 push_back(*__first);
2739 template <class _Allocator>
2740 template <class _ForwardIterator>
2743 __is_forward_iterator<_ForwardIterator>::value,
2746 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2749 difference_type __n = _VSTD::distance(__first, __last);
2752 if (__n > capacity())
2757 __construct_at_end(__first, __last);
2761 template <class _Allocator>
2763 vector<bool, _Allocator>::reserve(size_type __n)
2765 if (__n > capacity())
2767 vector __v(this->__alloc());
2769 __v.__construct_at_end(this->begin(), this->end());
2771 __invalidate_all_iterators();
2775 template <class _Allocator>
2777 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
2779 if (__external_cap_to_internal(size()) > __cap())
2781 #ifndef _LIBCPP_NO_EXCEPTIONS
2784 #endif // _LIBCPP_NO_EXCEPTIONS
2785 vector(*this, allocator_type(__alloc())).swap(*this);
2786 #ifndef _LIBCPP_NO_EXCEPTIONS
2791 #endif // _LIBCPP_NO_EXCEPTIONS
2795 template <class _Allocator>
2796 typename vector<bool, _Allocator>::reference
2797 vector<bool, _Allocator>::at(size_type __n)
2800 this->__throw_out_of_range();
2801 return (*this)[__n];
2804 template <class _Allocator>
2805 typename vector<bool, _Allocator>::const_reference
2806 vector<bool, _Allocator>::at(size_type __n) const
2809 this->__throw_out_of_range();
2810 return (*this)[__n];
2813 template <class _Allocator>
2815 vector<bool, _Allocator>::push_back(const value_type& __x)
2817 if (this->__size_ == this->capacity())
2818 reserve(__recommend(this->__size_ + 1));
2823 template <class _Allocator>
2824 typename vector<bool, _Allocator>::iterator
2825 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
2828 if (size() < capacity())
2830 const_iterator __old_end = end();
2832 _VSTD::copy_backward(__position, __old_end, end());
2833 __r = __const_iterator_cast(__position);
2837 vector __v(__alloc());
2838 __v.reserve(__recommend(__size_ + 1));
2839 __v.__size_ = __size_ + 1;
2840 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2841 _VSTD::copy_backward(__position, cend(), __v.end());
2848 template <class _Allocator>
2849 typename vector<bool, _Allocator>::iterator
2850 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
2853 size_type __c = capacity();
2854 if (__n <= __c && size() <= __c - __n)
2856 const_iterator __old_end = end();
2858 _VSTD::copy_backward(__position, __old_end, end());
2859 __r = __const_iterator_cast(__position);
2863 vector __v(__alloc());
2864 __v.reserve(__recommend(__size_ + __n));
2865 __v.__size_ = __size_ + __n;
2866 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2867 _VSTD::copy_backward(__position, cend(), __v.end());
2870 _VSTD::fill_n(__r, __n, __x);
2874 template <class _Allocator>
2875 template <class _InputIterator>
2878 __is_input_iterator <_InputIterator>::value &&
2879 !__is_forward_iterator<_InputIterator>::value,
2880 typename vector<bool, _Allocator>::iterator
2882 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
2884 difference_type __off = __position - begin();
2885 iterator __p = __const_iterator_cast(__position);
2886 iterator __old_end = end();
2887 for (; size() != capacity() && __first != __last; ++__first)
2892 vector __v(__alloc());
2893 if (__first != __last)
2895 #ifndef _LIBCPP_NO_EXCEPTIONS
2898 #endif // _LIBCPP_NO_EXCEPTIONS
2899 __v.assign(__first, __last);
2900 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
2901 difference_type __old_p = __p - begin();
2902 reserve(__recommend(size() + __v.size()));
2903 __p = begin() + __old_p;
2904 __old_end = begin() + __old_size;
2905 #ifndef _LIBCPP_NO_EXCEPTIONS
2909 erase(__old_end, end());
2912 #endif // _LIBCPP_NO_EXCEPTIONS
2914 __p = _VSTD::rotate(__p, __old_end, end());
2915 insert(__p, __v.begin(), __v.end());
2916 return begin() + __off;
2919 template <class _Allocator>
2920 template <class _ForwardIterator>
2923 __is_forward_iterator<_ForwardIterator>::value,
2924 typename vector<bool, _Allocator>::iterator
2926 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
2928 difference_type __n = _VSTD::distance(__first, __last);
2930 size_type __c = capacity();
2931 if (__n <= __c && size() <= __c - __n)
2933 const_iterator __old_end = end();
2935 _VSTD::copy_backward(__position, __old_end, end());
2936 __r = __const_iterator_cast(__position);
2940 vector __v(__alloc());
2941 __v.reserve(__recommend(__size_ + __n));
2942 __v.__size_ = __size_ + __n;
2943 __r = _VSTD::copy(cbegin(), __position, __v.begin());
2944 _VSTD::copy_backward(__position, cend(), __v.end());
2947 _VSTD::copy(__first, __last, __r);
2951 template <class _Allocator>
2952 _LIBCPP_INLINE_VISIBILITY inline
2953 typename vector<bool, _Allocator>::iterator
2954 vector<bool, _Allocator>::erase(const_iterator __position)
2956 iterator __r = __const_iterator_cast(__position);
2957 _VSTD::copy(__position + 1, this->cend(), __r);
2962 template <class _Allocator>
2963 typename vector<bool, _Allocator>::iterator
2964 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
2966 iterator __r = __const_iterator_cast(__first);
2967 difference_type __d = __last - __first;
2968 _VSTD::copy(__last, this->cend(), __r);
2973 template <class _Allocator>
2975 vector<bool, _Allocator>::swap(vector& __x)
2976 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2977 __is_nothrow_swappable<allocator_type>::value)
2979 _VSTD::swap(this->__begin_, __x.__begin_);
2980 _VSTD::swap(this->__size_, __x.__size_);
2981 _VSTD::swap(this->__cap(), __x.__cap());
2982 __swap_alloc(this->__alloc(), __x.__alloc());
2983 #ifdef _LIBCPP_DEBUG
2984 iterator::swap(this, &__x);
2985 const_iterator::swap(this, &__x);
2986 #endif // _LIBCPP_DEBUG
2989 template <class _Allocator>
2991 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
2993 size_type __cs = size();
2997 size_type __c = capacity();
2998 size_type __n = __sz - __cs;
2999 if (__n <= __c && __cs <= __c - __n)
3006 vector __v(__alloc());
3007 __v.reserve(__recommend(__size_ + __n));
3008 __v.__size_ = __size_ + __n;
3009 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3012 _VSTD::fill_n(__r, __n, __x);
3018 template <class _Allocator>
3020 vector<bool, _Allocator>::flip() _NOEXCEPT
3022 // do middle whole words
3023 size_type __n = __size_;
3024 __storage_pointer __p = __begin_;
3025 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3027 // do last partial word
3030 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3031 __storage_type __b = *__p & __m;
3037 template <class _Allocator>
3039 vector<bool, _Allocator>::__invariants() const
3041 if (this->__begin_ == 0)
3043 if (this->__size_ != 0 || this->__cap() != 0)
3048 if (this->__cap() == 0)
3050 if (this->__size_ > this->capacity())
3056 template <class _Allocator>
3058 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3061 // do middle whole words
3062 size_type __n = __size_;
3063 __storage_pointer __p = __begin_;
3064 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3066 // do last partial word
3069 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3075 template <class _Allocator>
3076 struct _LIBCPP_VISIBLE hash<vector<bool, _Allocator> >
3077 : public unary_function<vector<bool, _Allocator>, size_t>
3079 _LIBCPP_INLINE_VISIBILITY
3080 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3081 {return __vec.__hash_code();}
3084 template <class _Tp, class _Allocator>
3085 _LIBCPP_INLINE_VISIBILITY inline
3087 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3089 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3090 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3093 template <class _Tp, class _Allocator>
3094 _LIBCPP_INLINE_VISIBILITY inline
3096 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3098 return !(__x == __y);
3101 template <class _Tp, class _Allocator>
3102 _LIBCPP_INLINE_VISIBILITY inline
3104 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3106 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3109 template <class _Tp, class _Allocator>
3110 _LIBCPP_INLINE_VISIBILITY inline
3112 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3117 template <class _Tp, class _Allocator>
3118 _LIBCPP_INLINE_VISIBILITY inline
3120 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3122 return !(__x < __y);
3125 template <class _Tp, class _Allocator>
3126 _LIBCPP_INLINE_VISIBILITY inline
3128 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3130 return !(__y < __x);
3133 template <class _Tp, class _Allocator>
3134 _LIBCPP_INLINE_VISIBILITY inline
3136 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3137 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3142 _LIBCPP_END_NAMESPACE_STD
3144 #endif // _LIBCPP_VECTOR