blob: 82bf6e0038d9feceae8bf7c65a36ac58b9f8eeba [file] [log] [blame]
Howard Hinnantc51e1022010-05-11 19:42:16 +00001// -*- C++ -*-
2//===------------------------------ vector --------------------------------===//
3//
Chandler Carruthd2012102019-01-19 10:56:40 +00004// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5// See https://llvm.org/LICENSE.txt for license information.
6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
Howard Hinnantc51e1022010-05-11 19:42:16 +00007//
8//===----------------------------------------------------------------------===//
9
10#ifndef _LIBCPP_VECTOR
11#define _LIBCPP_VECTOR
12
13/*
14 vector synopsis
15
16namespace std
17{
18
Howard Hinnant3b6579a2010-08-22 00:02:43 +000019template <class T, class Allocator = allocator<T> >
Howard Hinnantc51e1022010-05-11 19:42:16 +000020class vector
Howard Hinnant3b6579a2010-08-22 00:02:43 +000021{
22public:
23 typedef T value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +000024 typedef Allocator allocator_type;
25 typedef typename allocator_type::reference reference;
26 typedef typename allocator_type::const_reference const_reference;
27 typedef implementation-defined iterator;
28 typedef implementation-defined const_iterator;
29 typedef typename allocator_type::size_type size_type;
30 typedef typename allocator_type::difference_type difference_type;
31 typedef typename allocator_type::pointer pointer;
32 typedef typename allocator_type::const_pointer const_pointer;
33 typedef std::reverse_iterator<iterator> reverse_iterator;
34 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
35
Howard Hinnant1c936782011-06-03 19:40:40 +000036 vector()
37 noexcept(is_nothrow_default_constructible<allocator_type>::value);
38 explicit vector(const allocator_type&);
Howard Hinnantc51e1022010-05-11 19:42:16 +000039 explicit vector(size_type n);
Marshall Clowd3cbeaa2013-09-14 00:47:59 +000040 explicit vector(size_type n, const allocator_type&); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +000041 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);
Howard Hinnant1c936782011-06-03 19:40:40 +000045 vector(vector&& x)
46 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000047 vector(initializer_list<value_type> il);
48 vector(initializer_list<value_type> il, const allocator_type& a);
49 ~vector();
50 vector& operator=(const vector& x);
Howard Hinnant1c936782011-06-03 19:40:40 +000051 vector& operator=(vector&& x)
52 noexcept(
Marshall Clow2fe8a8d2015-08-18 18:57:00 +000053 allocator_type::propagate_on_container_move_assignment::value ||
54 allocator_type::is_always_equal::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +000055 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);
60
Howard Hinnant1c936782011-06-03 19:40:40 +000061 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000062
Howard Hinnant1c936782011-06-03 19:40:40 +000063 iterator begin() noexcept;
64 const_iterator begin() const noexcept;
65 iterator end() noexcept;
66 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000067
Howard Hinnant1c936782011-06-03 19:40:40 +000068 reverse_iterator rbegin() noexcept;
69 const_reverse_iterator rbegin() const noexcept;
70 reverse_iterator rend() noexcept;
71 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000072
Howard Hinnant1c936782011-06-03 19:40:40 +000073 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;
Howard Hinnantc51e1022010-05-11 19:42:16 +000077
Howard Hinnant1c936782011-06-03 19:40:40 +000078 size_type size() const noexcept;
79 size_type max_size() const noexcept;
80 size_type capacity() const noexcept;
81 bool empty() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000082 void reserve(size_type n);
Howard Hinnant1c936782011-06-03 19:40:40 +000083 void shrink_to_fit() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000084
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;
89
90 reference front();
91 const_reference front() const;
92 reference back();
93 const_reference back() const;
94
Howard Hinnant1c936782011-06-03 19:40:40 +000095 value_type* data() noexcept;
96 const value_type* data() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000097
98 void push_back(const value_type& x);
99 void push_back(value_type&& x);
100 template <class... Args>
Marshall Clowea52cc42017-01-24 23:09:12 +0000101 reference emplace_back(Args&&... args); // reference in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000102 void pop_back();
103
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);
111
112 iterator erase(const_iterator position);
113 iterator erase(const_iterator first, const_iterator last);
114
Howard Hinnant1c936782011-06-03 19:40:40 +0000115 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000116
117 void resize(size_type sz);
118 void resize(size_type sz, const value_type& c);
119
Howard Hinnant1c936782011-06-03 19:40:40 +0000120 void swap(vector&)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000121 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
122 allocator_traits<allocator_type>::is_always_equal::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000123
124 bool __invariants() const;
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000125};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000126
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000127template <class Allocator = allocator<T> >
Howard Hinnantc51e1022010-05-11 19:42:16 +0000128class vector<bool, Allocator>
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000129{
130public:
131 typedef bool value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000132 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;
141
142 class reference
143 {
144 public:
Howard Hinnant1c936782011-06-03 19:40:40 +0000145 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;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000151 };
152
153 class const_reference
154 {
155 public:
Howard Hinnant1c936782011-06-03 19:40:40 +0000156 const_reference(const reference&) noexcept;
157 operator bool() const noexcept;
158 const_iterator operator&() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000159 };
160
Howard Hinnant1c936782011-06-03 19:40:40 +0000161 vector()
162 noexcept(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantc2734962011-09-02 20:42:31 +0000163 explicit vector(const allocator_type&);
Marshall Clowd3cbeaa2013-09-14 00:47:59 +0000164 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
165 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000166 template <class InputIterator>
167 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
168 vector(const vector& x);
Howard Hinnant1c936782011-06-03 19:40:40 +0000169 vector(vector&& x)
170 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000171 vector(initializer_list<value_type> il);
172 vector(initializer_list<value_type> il, const allocator_type& a);
173 ~vector();
174 vector& operator=(const vector& x);
Howard Hinnant1c936782011-06-03 19:40:40 +0000175 vector& operator=(vector&& x)
176 noexcept(
Marshall Clow2fe8a8d2015-08-18 18:57:00 +0000177 allocator_type::propagate_on_container_move_assignment::value ||
178 allocator_type::is_always_equal::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000179 vector& operator=(initializer_list<value_type> il);
180 template <class InputIterator>
181 void assign(InputIterator first, InputIterator last);
182 void assign(size_type n, const value_type& u);
183 void assign(initializer_list<value_type> il);
184
Howard Hinnant1c936782011-06-03 19:40:40 +0000185 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000186
Howard Hinnant1c936782011-06-03 19:40:40 +0000187 iterator begin() noexcept;
188 const_iterator begin() const noexcept;
189 iterator end() noexcept;
190 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000191
Howard Hinnant1c936782011-06-03 19:40:40 +0000192 reverse_iterator rbegin() noexcept;
193 const_reverse_iterator rbegin() const noexcept;
194 reverse_iterator rend() noexcept;
195 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000196
Howard Hinnant1c936782011-06-03 19:40:40 +0000197 const_iterator cbegin() const noexcept;
198 const_iterator cend() const noexcept;
199 const_reverse_iterator crbegin() const noexcept;
200 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000201
Howard Hinnant1c936782011-06-03 19:40:40 +0000202 size_type size() const noexcept;
203 size_type max_size() const noexcept;
204 size_type capacity() const noexcept;
205 bool empty() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000206 void reserve(size_type n);
Howard Hinnant1c936782011-06-03 19:40:40 +0000207 void shrink_to_fit() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000208
209 reference operator[](size_type n);
210 const_reference operator[](size_type n) const;
211 reference at(size_type n);
212 const_reference at(size_type n) const;
213
214 reference front();
215 const_reference front() const;
216 reference back();
217 const_reference back() const;
218
219 void push_back(const value_type& x);
Marshall Clowea52cc42017-01-24 23:09:12 +0000220 template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000221 void pop_back();
222
Marshall Clowc46bb8e2013-08-13 23:54:12 +0000223 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000224 iterator insert(const_iterator position, const value_type& x);
225 iterator insert(const_iterator position, size_type n, const value_type& x);
226 template <class InputIterator>
227 iterator insert(const_iterator position, InputIterator first, InputIterator last);
228 iterator insert(const_iterator position, initializer_list<value_type> il);
229
230 iterator erase(const_iterator position);
231 iterator erase(const_iterator first, const_iterator last);
232
Howard Hinnant1c936782011-06-03 19:40:40 +0000233 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000234
235 void resize(size_type sz);
236 void resize(size_type sz, value_type x);
237
Howard Hinnant1c936782011-06-03 19:40:40 +0000238 void swap(vector&)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000239 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
240 allocator_traits<allocator_type>::is_always_equal::value); // C++17
Howard Hinnant1c936782011-06-03 19:40:40 +0000241 void flip() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000242
243 bool __invariants() const;
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000244};
Howard Hinnantc51e1022010-05-11 19:42:16 +0000245
Marshall Clowf0ca1492018-05-21 21:30:12 +0000246template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
247 vector(InputIterator, InputIterator, Allocator = Allocator())
248 -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>;
249
Howard Hinnantc51e1022010-05-11 19:42:16 +0000250template <class Allocator> struct hash<std::vector<bool, Allocator>>;
251
252template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
253template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
254template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
255template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
256template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
257template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
258
Howard Hinnant1c936782011-06-03 19:40:40 +0000259template <class T, class Allocator>
260void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
261 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000262
Marshall Clow29b53f22018-12-14 18:49:35 +0000263template <class T, class Allocator, class U>
264 void erase(vector<T, Allocator>& c, const U& value); // C++20
265template <class T, class Allocator, class Predicate>
266 void erase_if(vector<T, Allocator>& c, Predicate pred); // C++20
267
Howard Hinnantc51e1022010-05-11 19:42:16 +0000268} // std
269
270*/
271
272#include <__config>
Eric Fiselier876c6862016-02-20 00:19:45 +0000273#include <iosfwd> // for forward declaration of vector
Howard Hinnantc51e1022010-05-11 19:42:16 +0000274#include <__bit_reference>
275#include <type_traits>
276#include <climits>
277#include <limits>
278#include <initializer_list>
279#include <memory>
280#include <stdexcept>
281#include <algorithm>
282#include <cstring>
Marshall Clow0a1e7502018-09-12 19:41:40 +0000283#include <version>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000284#include <__split_buffer>
285#include <__functional_base>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000286
Eric Fiselier14b6de92014-08-10 23:53:08 +0000287#include <__debug>
Howard Hinnante6ff0b62013-08-02 00:26:35 +0000288
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000289#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000290#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000291#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000292
Eric Fiselierf4433a32017-05-31 22:07:49 +0000293_LIBCPP_PUSH_MACROS
294#include <__undef_macros>
295
296
Howard Hinnantc51e1022010-05-11 19:42:16 +0000297_LIBCPP_BEGIN_NAMESPACE_STD
298
299template <bool>
300class __vector_base_common
301{
302protected:
Louis Dionne16fe2952018-07-11 23:14:33 +0000303 _LIBCPP_INLINE_VISIBILITY __vector_base_common() {}
Marshall Clow8fea1612016-08-25 15:09:01 +0000304 _LIBCPP_NORETURN void __throw_length_error() const;
305 _LIBCPP_NORETURN void __throw_out_of_range() const;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000306};
307
308template <bool __b>
309void
310__vector_base_common<__b>::__throw_length_error() const
311{
Marshall Clow8fea1612016-08-25 15:09:01 +0000312 _VSTD::__throw_length_error("vector");
Howard Hinnantc51e1022010-05-11 19:42:16 +0000313}
314
315template <bool __b>
316void
317__vector_base_common<__b>::__throw_out_of_range() const
318{
Marshall Clow8fea1612016-08-25 15:09:01 +0000319 _VSTD::__throw_out_of_range("vector");
Howard Hinnantc51e1022010-05-11 19:42:16 +0000320}
321
Eric Fiselier1b57fa82016-09-15 22:27:07 +0000322_LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000323
324template <class _Tp, class _Allocator>
325class __vector_base
326 : protected __vector_base_common<true>
327{
Marshall Clowf0ca1492018-05-21 21:30:12 +0000328public:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000329 typedef _Allocator allocator_type;
330 typedef allocator_traits<allocator_type> __alloc_traits;
Marshall Clowf0ca1492018-05-21 21:30:12 +0000331 typedef typename __alloc_traits::size_type size_type;
332protected:
333 typedef _Tp value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000334 typedef value_type& reference;
335 typedef const value_type& const_reference;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000336 typedef typename __alloc_traits::difference_type difference_type;
337 typedef typename __alloc_traits::pointer pointer;
338 typedef typename __alloc_traits::const_pointer const_pointer;
339 typedef pointer iterator;
340 typedef const_pointer const_iterator;
341
342 pointer __begin_;
343 pointer __end_;
344 __compressed_pair<pointer, allocator_type> __end_cap_;
345
Howard Hinnant1c936782011-06-03 19:40:40 +0000346 _LIBCPP_INLINE_VISIBILITY
347 allocator_type& __alloc() _NOEXCEPT
348 {return __end_cap_.second();}
349 _LIBCPP_INLINE_VISIBILITY
350 const allocator_type& __alloc() const _NOEXCEPT
351 {return __end_cap_.second();}
352 _LIBCPP_INLINE_VISIBILITY
353 pointer& __end_cap() _NOEXCEPT
354 {return __end_cap_.first();}
355 _LIBCPP_INLINE_VISIBILITY
356 const pointer& __end_cap() const _NOEXCEPT
357 {return __end_cap_.first();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000358
Howard Hinnant1c936782011-06-03 19:40:40 +0000359 _LIBCPP_INLINE_VISIBILITY
360 __vector_base()
361 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantcf823322010-12-17 14:46:43 +0000362 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
Eric Fiselier4f1534c2018-06-05 22:32:52 +0000363#ifndef _LIBCPP_CXX03_LANG
364 _LIBCPP_INLINE_VISIBILITY __vector_base(allocator_type&& __a) _NOEXCEPT;
365#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000366 ~__vector_base();
367
Howard Hinnant1c936782011-06-03 19:40:40 +0000368 _LIBCPP_INLINE_VISIBILITY
369 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
370 _LIBCPP_INLINE_VISIBILITY
371 size_type capacity() const _NOEXCEPT
372 {return static_cast<size_type>(__end_cap() - __begin_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000373
Howard Hinnant1c936782011-06-03 19:40:40 +0000374 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant76053d72013-06-27 19:35:32 +0000375 void __destruct_at_end(pointer __new_last) _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000376
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000377 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000378 void __copy_assign_alloc(const __vector_base& __c)
379 {__copy_assign_alloc(__c, integral_constant<bool,
380 __alloc_traits::propagate_on_container_copy_assignment::value>());}
381
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000382 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000383 void __move_assign_alloc(__vector_base& __c)
Howard Hinnant1c936782011-06-03 19:40:40 +0000384 _NOEXCEPT_(
385 !__alloc_traits::propagate_on_container_move_assignment::value ||
386 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000387 {__move_assign_alloc(__c, integral_constant<bool,
388 __alloc_traits::propagate_on_container_move_assignment::value>());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000389private:
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000390 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000391 void __copy_assign_alloc(const __vector_base& __c, true_type)
392 {
393 if (__alloc() != __c.__alloc())
394 {
395 clear();
396 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
397 __begin_ = __end_ = __end_cap() = nullptr;
398 }
399 __alloc() = __c.__alloc();
400 }
401
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000402 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +0000403 void __copy_assign_alloc(const __vector_base&, false_type)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000404 {}
405
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000406 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc2734962011-09-02 20:42:31 +0000407 void __move_assign_alloc(__vector_base& __c, true_type)
Howard Hinnant1c936782011-06-03 19:40:40 +0000408 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000409 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000410 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000411 }
412
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +0000414 void __move_assign_alloc(__vector_base&, false_type)
Howard Hinnant1c936782011-06-03 19:40:40 +0000415 _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000416 {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000417};
418
419template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +0000420inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000421void
Howard Hinnant76053d72013-06-27 19:35:32 +0000422__vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000423{
Bruce Mitchener405fdcd2017-03-23 14:39:23 +0000424 pointer __soon_to_be_end = __end_;
425 while (__new_last != __soon_to_be_end)
426 __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__soon_to_be_end));
427 __end_ = __new_last;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000428}
429
430template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +0000431inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000432__vector_base<_Tp, _Allocator>::__vector_base()
Howard Hinnant1c936782011-06-03 19:40:40 +0000433 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant76053d72013-06-27 19:35:32 +0000434 : __begin_(nullptr),
435 __end_(nullptr),
436 __end_cap_(nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000437{
438}
439
440template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +0000441inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000442__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
Howard Hinnant76053d72013-06-27 19:35:32 +0000443 : __begin_(nullptr),
444 __end_(nullptr),
445 __end_cap_(nullptr, __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000446{
447}
448
Eric Fiselier4f1534c2018-06-05 22:32:52 +0000449#ifndef _LIBCPP_CXX03_LANG
450template <class _Tp, class _Allocator>
451inline _LIBCPP_INLINE_VISIBILITY
452__vector_base<_Tp, _Allocator>::__vector_base(allocator_type&& __a) _NOEXCEPT
453 : __begin_(nullptr),
454 __end_(nullptr),
455 __end_cap_(nullptr, std::move(__a)) {}
456#endif
457
Howard Hinnantc51e1022010-05-11 19:42:16 +0000458template <class _Tp, class _Allocator>
459__vector_base<_Tp, _Allocator>::~__vector_base()
460{
Howard Hinnant76053d72013-06-27 19:35:32 +0000461 if (__begin_ != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000462 {
463 clear();
464 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
465 }
466}
467
Eric Fiselier876c6862016-02-20 00:19:45 +0000468template <class _Tp, class _Allocator /* = allocator<_Tp> */>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000469class _LIBCPP_TEMPLATE_VIS vector
Howard Hinnantc51e1022010-05-11 19:42:16 +0000470 : private __vector_base<_Tp, _Allocator>
471{
472private:
473 typedef __vector_base<_Tp, _Allocator> __base;
Marshall Clow2cd9d372014-05-08 14:14:06 +0000474 typedef allocator<_Tp> __default_allocator_type;
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000475public:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000476 typedef vector __self;
Howard Hinnant3b6579a2010-08-22 00:02:43 +0000477 typedef _Tp value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000478 typedef _Allocator allocator_type;
479 typedef typename __base::__alloc_traits __alloc_traits;
480 typedef typename __base::reference reference;
481 typedef typename __base::const_reference const_reference;
482 typedef typename __base::size_type size_type;
483 typedef typename __base::difference_type difference_type;
484 typedef typename __base::pointer pointer;
485 typedef typename __base::const_pointer const_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000486 typedef __wrap_iter<pointer> iterator;
487 typedef __wrap_iter<const_pointer> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000488 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
489 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000490
Howard Hinnanta416ff02013-03-26 19:04:56 +0000491 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
492 "Allocator::value_type must be same type as value_type");
493
Howard Hinnant1c936782011-06-03 19:40:40 +0000494 _LIBCPP_INLINE_VISIBILITY
Marshall Clowe546cbb2015-06-04 02:05:41 +0000495 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant27e0e772011-09-14 18:33:51 +0000496 {
Howard Hinnanta47c6d52011-09-16 17:29:17 +0000497#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +0000498 __get_db()->__insert_c(this);
499#endif
500 }
501 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
Marshall Clow8f282f42015-06-04 00:10:20 +0000502#if _LIBCPP_STD_VER <= 14
503 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
504#else
505 _NOEXCEPT
506#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +0000507 : __base(__a)
508 {
Howard Hinnanta47c6d52011-09-16 17:29:17 +0000509#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +0000510 __get_db()->__insert_c(this);
511#endif
512 }
Howard Hinnantc51e1022010-05-11 19:42:16 +0000513 explicit vector(size_type __n);
Marshall Clowd3cbeaa2013-09-14 00:47:59 +0000514#if _LIBCPP_STD_VER > 11
515 explicit vector(size_type __n, const allocator_type& __a);
516#endif
Marshall Clowf0ca1492018-05-21 21:30:12 +0000517 vector(size_type __n, const value_type& __x);
518 vector(size_type __n, const value_type& __x, const allocator_type& __a);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000519 template <class _InputIterator>
Howard Hinnant66fce262013-09-21 21:13:54 +0000520 vector(_InputIterator __first,
Howard Hinnantc51e1022010-05-11 19:42:16 +0000521 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +0000522 !__is_forward_iterator<_InputIterator>::value &&
523 is_constructible<
524 value_type,
Howard Hinnant66fce262013-09-21 21:13:54 +0000525 typename iterator_traits<_InputIterator>::reference>::value,
526 _InputIterator>::type __last);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000527 template <class _InputIterator>
528 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
529 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +0000530 !__is_forward_iterator<_InputIterator>::value &&
531 is_constructible<
532 value_type,
533 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000534 template <class _ForwardIterator>
Howard Hinnant66fce262013-09-21 21:13:54 +0000535 vector(_ForwardIterator __first,
Howard Hinnant88010252013-03-28 17:44:32 +0000536 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
537 is_constructible<
538 value_type,
Howard Hinnant66fce262013-09-21 21:13:54 +0000539 typename iterator_traits<_ForwardIterator>::reference>::value,
540 _ForwardIterator>::type __last);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000541 template <class _ForwardIterator>
542 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
Howard Hinnant88010252013-03-28 17:44:32 +0000543 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
544 is_constructible<
545 value_type,
546 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000547
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000548 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant27e0e772011-09-14 18:33:51 +0000549 ~vector()
550 {
Marshall Clow68af4f32018-09-07 15:47:59 +0000551 __annotate_delete();
552#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +0000553 __get_db()->__erase_c(this);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000554#endif
Marshall Clow68af4f32018-09-07 15:47:59 +0000555 }
Howard Hinnantc51e1022010-05-11 19:42:16 +0000556
557 vector(const vector& __x);
558 vector(const vector& __x, const allocator_type& __a);
Howard Hinnantcf823322010-12-17 14:46:43 +0000559 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000560 vector& operator=(const vector& __x);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000561
562#ifndef _LIBCPP_CXX03_LANG
563 _LIBCPP_INLINE_VISIBILITY
564 vector(initializer_list<value_type> __il);
565
566 _LIBCPP_INLINE_VISIBILITY
567 vector(initializer_list<value_type> __il, const allocator_type& __a);
568
Howard Hinnantcf823322010-12-17 14:46:43 +0000569 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +0000570 vector(vector&& __x)
Marshall Clowe5108202015-07-14 14:46:32 +0000571#if _LIBCPP_STD_VER > 14
572 _NOEXCEPT;
573#else
Howard Hinnant1c936782011-06-03 19:40:40 +0000574 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Marshall Clowe5108202015-07-14 14:46:32 +0000575#endif
Eric Fiseliered9e9362017-04-16 02:40:45 +0000576
Howard Hinnantcf823322010-12-17 14:46:43 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000578 vector(vector&& __x, const allocator_type& __a);
Howard Hinnantcf823322010-12-17 14:46:43 +0000579 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +0000580 vector& operator=(vector&& __x)
Marshall Clow2fe8a8d2015-08-18 18:57:00 +0000581 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
Eric Fiseliered9e9362017-04-16 02:40:45 +0000582
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000583 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000584 vector& operator=(initializer_list<value_type> __il)
585 {assign(__il.begin(), __il.end()); return *this;}
Eric Fiseliered9e9362017-04-16 02:40:45 +0000586
587#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000588
589 template <class _InputIterator>
590 typename enable_if
591 <
592 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +0000593 !__is_forward_iterator<_InputIterator>::value &&
594 is_constructible<
595 value_type,
596 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +0000597 void
598 >::type
599 assign(_InputIterator __first, _InputIterator __last);
600 template <class _ForwardIterator>
601 typename enable_if
602 <
Howard Hinnant88010252013-03-28 17:44:32 +0000603 __is_forward_iterator<_ForwardIterator>::value &&
604 is_constructible<
605 value_type,
606 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +0000607 void
608 >::type
609 assign(_ForwardIterator __first, _ForwardIterator __last);
610
611 void assign(size_type __n, const_reference __u);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000612
613#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000614 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000615 void assign(initializer_list<value_type> __il)
616 {assign(__il.begin(), __il.end());}
Eric Fiseliered9e9362017-04-16 02:40:45 +0000617#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000618
Howard Hinnant1c936782011-06-03 19:40:40 +0000619 _LIBCPP_INLINE_VISIBILITY
620 allocator_type get_allocator() const _NOEXCEPT
621 {return this->__alloc();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000622
Howard Hinnant1c936782011-06-03 19:40:40 +0000623 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
624 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
625 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
626 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000627
Howard Hinnant1c936782011-06-03 19:40:40 +0000628 _LIBCPP_INLINE_VISIBILITY
629 reverse_iterator rbegin() _NOEXCEPT
630 {return reverse_iterator(end());}
631 _LIBCPP_INLINE_VISIBILITY
632 const_reverse_iterator rbegin() const _NOEXCEPT
633 {return const_reverse_iterator(end());}
634 _LIBCPP_INLINE_VISIBILITY
635 reverse_iterator rend() _NOEXCEPT
636 {return reverse_iterator(begin());}
637 _LIBCPP_INLINE_VISIBILITY
638 const_reverse_iterator rend() const _NOEXCEPT
639 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000640
Howard Hinnant1c936782011-06-03 19:40:40 +0000641 _LIBCPP_INLINE_VISIBILITY
642 const_iterator cbegin() const _NOEXCEPT
643 {return begin();}
644 _LIBCPP_INLINE_VISIBILITY
645 const_iterator cend() const _NOEXCEPT
646 {return end();}
647 _LIBCPP_INLINE_VISIBILITY
648 const_reverse_iterator crbegin() const _NOEXCEPT
649 {return rbegin();}
650 _LIBCPP_INLINE_VISIBILITY
651 const_reverse_iterator crend() const _NOEXCEPT
652 {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000653
Howard Hinnant1c936782011-06-03 19:40:40 +0000654 _LIBCPP_INLINE_VISIBILITY
655 size_type size() const _NOEXCEPT
656 {return static_cast<size_type>(this->__end_ - this->__begin_);}
657 _LIBCPP_INLINE_VISIBILITY
658 size_type capacity() const _NOEXCEPT
659 {return __base::capacity();}
Marshall Clow425f5752017-11-15 05:51:26 +0000660 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +0000661 bool empty() const _NOEXCEPT
662 {return this->__begin_ == this->__end_;}
663 size_type max_size() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000664 void reserve(size_type __n);
Howard Hinnant1c936782011-06-03 19:40:40 +0000665 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000666
Marshall Clowd6470492019-03-15 00:29:35 +0000667 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) _NOEXCEPT;
668 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000669 reference at(size_type __n);
670 const_reference at(size_type __n) const;
671
Marshall Clowd6470492019-03-15 00:29:35 +0000672 _LIBCPP_INLINE_VISIBILITY reference front() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +0000673 {
674 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
675 return *this->__begin_;
676 }
Marshall Clowd6470492019-03-15 00:29:35 +0000677 _LIBCPP_INLINE_VISIBILITY const_reference front() const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +0000678 {
679 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
680 return *this->__begin_;
681 }
Marshall Clowd6470492019-03-15 00:29:35 +0000682 _LIBCPP_INLINE_VISIBILITY reference back() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +0000683 {
684 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
685 return *(this->__end_ - 1);
686 }
Marshall Clowd6470492019-03-15 00:29:35 +0000687 _LIBCPP_INLINE_VISIBILITY const_reference back() const _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +0000688 {
689 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
690 return *(this->__end_ - 1);
691 }
Howard Hinnantc51e1022010-05-11 19:42:16 +0000692
Howard Hinnant1c936782011-06-03 19:40:40 +0000693 _LIBCPP_INLINE_VISIBILITY
694 value_type* data() _NOEXCEPT
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000695 {return _VSTD::__to_raw_pointer(this->__begin_);}
Howard Hinnant1c936782011-06-03 19:40:40 +0000696 _LIBCPP_INLINE_VISIBILITY
697 const value_type* data() const _NOEXCEPT
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000698 {return _VSTD::__to_raw_pointer(this->__begin_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000699
Eric Fiselier96919722017-10-17 13:03:17 +0000700#ifdef _LIBCPP_CXX03_LANG
701 _LIBCPP_INLINE_VISIBILITY
702 void __emplace_back(const value_type& __x) { push_back(__x); }
703#else
704 template <class _Arg>
705 _LIBCPP_INLINE_VISIBILITY
706 void __emplace_back(_Arg&& __arg) {
707 emplace_back(_VSTD::forward<_Arg>(__arg));
708 }
709#endif
710
Howard Hinnantcf823322010-12-17 14:46:43 +0000711 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000712
713#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd2cab2f2012-02-15 00:41:34 +0000714 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000715
Howard Hinnantc51e1022010-05-11 19:42:16 +0000716 template <class... _Args>
Evgeniy Stepanov2fb1cb62015-11-07 01:22:13 +0000717 _LIBCPP_INLINE_VISIBILITY
Marshall Clowea52cc42017-01-24 23:09:12 +0000718#if _LIBCPP_STD_VER > 14
Eric Fiselier34ba5b92016-07-21 03:20:17 +0000719 reference emplace_back(_Args&&... __args);
Marshall Clowea52cc42017-01-24 23:09:12 +0000720#else
721 void emplace_back(_Args&&... __args);
722#endif
Eric Fiseliered9e9362017-04-16 02:40:45 +0000723#endif // !_LIBCPP_CXX03_LANG
724
Evgeniy Stepanov2fb1cb62015-11-07 01:22:13 +0000725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000726 void pop_back();
727
728 iterator insert(const_iterator __position, const_reference __x);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000729
730#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000731 iterator insert(const_iterator __position, value_type&& __x);
732 template <class... _Args>
733 iterator emplace(const_iterator __position, _Args&&... __args);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000734#endif // !_LIBCPP_CXX03_LANG
735
Howard Hinnantc51e1022010-05-11 19:42:16 +0000736 iterator insert(const_iterator __position, size_type __n, const_reference __x);
737 template <class _InputIterator>
738 typename enable_if
739 <
740 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +0000741 !__is_forward_iterator<_InputIterator>::value &&
742 is_constructible<
743 value_type,
744 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +0000745 iterator
746 >::type
747 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
748 template <class _ForwardIterator>
749 typename enable_if
750 <
Howard Hinnant88010252013-03-28 17:44:32 +0000751 __is_forward_iterator<_ForwardIterator>::value &&
752 is_constructible<
753 value_type,
754 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +0000755 iterator
756 >::type
757 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000758
759#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant1c265cd2010-09-23 18:58:28 +0000760 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000761 iterator insert(const_iterator __position, initializer_list<value_type> __il)
762 {return insert(__position, __il.begin(), __il.end());}
Eric Fiseliered9e9362017-04-16 02:40:45 +0000763#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000764
Howard Hinnantcf823322010-12-17 14:46:43 +0000765 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000766 iterator erase(const_iterator __first, const_iterator __last);
767
Howard Hinnant1c936782011-06-03 19:40:40 +0000768 _LIBCPP_INLINE_VISIBILITY
769 void clear() _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +0000770 {
Marshall Clow2cd9d372014-05-08 14:14:06 +0000771 size_type __old_size = size();
Howard Hinnant27e0e772011-09-14 18:33:51 +0000772 __base::clear();
Marshall Clow2cd9d372014-05-08 14:14:06 +0000773 __annotate_shrink(__old_size);
Howard Hinnant27e0e772011-09-14 18:33:51 +0000774 __invalidate_all_iterators();
775 }
Howard Hinnantc51e1022010-05-11 19:42:16 +0000776
777 void resize(size_type __sz);
778 void resize(size_type __sz, const_reference __x);
779
Howard Hinnant1c936782011-06-03 19:40:40 +0000780 void swap(vector&)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000781#if _LIBCPP_STD_VER >= 14
Eric Fiselier873b8d32019-03-18 21:50:12 +0000782 _NOEXCEPT;
Marshall Clow8982dcd2015-07-13 20:04:56 +0000783#else
Eric Fiselier873b8d32019-03-18 21:50:12 +0000784 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
Marshall Clow8982dcd2015-07-13 20:04:56 +0000785 __is_nothrow_swappable<allocator_type>::value);
786#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000787
788 bool __invariants() const;
789
Howard Hinnanta47c6d52011-09-16 17:29:17 +0000790#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +0000791
792 bool __dereferenceable(const const_iterator* __i) const;
793 bool __decrementable(const const_iterator* __i) const;
794 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
795 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
796
Howard Hinnanta47c6d52011-09-16 17:29:17 +0000797#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +0000798
Howard Hinnantc51e1022010-05-11 19:42:16 +0000799private:
Howard Hinnantcf823322010-12-17 14:46:43 +0000800 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
Eric Fiselier69c51982016-12-28 06:06:09 +0000801 _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
Marshall Clow3ff48e02018-05-22 16:20:28 +0000802 void __vallocate(size_type __n);
803 void __vdeallocate() _NOEXCEPT;
Howard Hinnantcf823322010-12-17 14:46:43 +0000804 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
Howard Hinnanta5589382011-01-04 19:53:31 +0000805 void __construct_at_end(size_type __n);
Evgeniy Stepanov2fb1cb62015-11-07 01:22:13 +0000806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000807 void __construct_at_end(size_type __n, const_reference __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000808 template <class _ForwardIterator>
809 typename enable_if
810 <
811 __is_forward_iterator<_ForwardIterator>::value,
812 void
813 >::type
Eric Fiselieracfe6f02015-03-31 16:54:19 +0000814 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000815 void __append(size_type __n);
816 void __append(size_type __n, const_reference __x);
Howard Hinnantcf823322010-12-17 14:46:43 +0000817 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +0000818 iterator __make_iter(pointer __p) _NOEXCEPT;
Howard Hinnantcf823322010-12-17 14:46:43 +0000819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +0000820 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000821 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
822 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
823 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
Howard Hinnant1c936782011-06-03 19:40:40 +0000824 void __move_assign(vector& __c, true_type)
825 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Marshall Clow2fe8a8d2015-08-18 18:57:00 +0000826 void __move_assign(vector& __c, false_type)
827 _NOEXCEPT_(__alloc_traits::is_always_equal::value);
Howard Hinnant27e0e772011-09-14 18:33:51 +0000828 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant76053d72013-06-27 19:35:32 +0000829 void __destruct_at_end(pointer __new_last) _NOEXCEPT
Howard Hinnant27e0e772011-09-14 18:33:51 +0000830 {
Eric Fiselier69c51982016-12-28 06:06:09 +0000831 __invalidate_iterators_past(__new_last);
Marshall Clow2cd9d372014-05-08 14:14:06 +0000832 size_type __old_size = size();
Howard Hinnant27e0e772011-09-14 18:33:51 +0000833 __base::__destruct_at_end(__new_last);
Marshall Clow2cd9d372014-05-08 14:14:06 +0000834 __annotate_shrink(__old_size);
Howard Hinnant27e0e772011-09-14 18:33:51 +0000835 }
Eric Fiseliered9e9362017-04-16 02:40:45 +0000836
837#ifndef _LIBCPP_CXX03_LANG
Eric Fiselier7110f442019-03-19 19:19:44 +0000838 template <class _Up>
839 _LIBCPP_INLINE_VISIBILITY
840 inline void __push_back_slow_path(_Up&& __x);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000841
Howard Hinnantb6c49562012-02-26 15:30:12 +0000842 template <class... _Args>
Eric Fiselier7110f442019-03-19 19:19:44 +0000843 _LIBCPP_INLINE_VISIBILITY
844 inline void __emplace_back_slow_path(_Args&&... __args);
Eric Fiseliered9e9362017-04-16 02:40:45 +0000845#else
Eric Fiselier7110f442019-03-19 19:19:44 +0000846 template <class _Up>
847 _LIBCPP_INLINE_VISIBILITY
848 inline void __push_back_slow_path(_Up& __x);
Howard Hinnantb6c49562012-02-26 15:30:12 +0000849#endif
Eric Fiseliered9e9362017-04-16 02:40:45 +0000850
Marshall Clow2cd9d372014-05-08 14:14:06 +0000851 // The following functions are no-ops outside of AddressSanitizer mode.
852 // We call annotatations only for the default Allocator because other allocators
853 // may not meet the AddressSanitizer alignment constraints.
854 // See the documentation for __sanitizer_annotate_contiguous_container for more details.
Marshall Clow2cd9d372014-05-08 14:14:06 +0000855#ifndef _LIBCPP_HAS_NO_ASAN
Eric Fiselier6003c772016-12-23 23:37:52 +0000856 void __annotate_contiguous_container(const void *__beg, const void *__end,
857 const void *__old_mid,
858 const void *__new_mid) const
859 {
860
Marshall Clow2cd9d372014-05-08 14:14:06 +0000861 if (__beg && is_same<allocator_type, __default_allocator_type>::value)
862 __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
Marshall Clow2cd9d372014-05-08 14:14:06 +0000863 }
Eric Fiselier6003c772016-12-23 23:37:52 +0000864#else
865 _LIBCPP_INLINE_VISIBILITY
866 void __annotate_contiguous_container(const void*, const void*, const void*,
867 const void*) const {}
868#endif
869 _LIBCPP_INLINE_VISIBILITY
870 void __annotate_new(size_type __current_size) const {
Marshall Clow2cd9d372014-05-08 14:14:06 +0000871 __annotate_contiguous_container(data(), data() + capacity(),
872 data() + capacity(), data() + __current_size);
873 }
Eric Fiselier6003c772016-12-23 23:37:52 +0000874
875 _LIBCPP_INLINE_VISIBILITY
876 void __annotate_delete() const {
Marshall Clow2cd9d372014-05-08 14:14:06 +0000877 __annotate_contiguous_container(data(), data() + capacity(),
878 data() + size(), data() + capacity());
879 }
Eric Fiselier6003c772016-12-23 23:37:52 +0000880
881 _LIBCPP_INLINE_VISIBILITY
Kostya Serebryany4963c252014-09-02 23:43:38 +0000882 void __annotate_increase(size_type __n) const
Marshall Clow2cd9d372014-05-08 14:14:06 +0000883 {
884 __annotate_contiguous_container(data(), data() + capacity(),
885 data() + size(), data() + size() + __n);
886 }
Eric Fiselier6003c772016-12-23 23:37:52 +0000887
888 _LIBCPP_INLINE_VISIBILITY
Kostya Serebryany4963c252014-09-02 23:43:38 +0000889 void __annotate_shrink(size_type __old_size) const
Marshall Clow2cd9d372014-05-08 14:14:06 +0000890 {
891 __annotate_contiguous_container(data(), data() + capacity(),
892 data() + __old_size, data() + size());
893 }
Marshall Clowc78ffa52014-09-03 21:37:43 +0000894#ifndef _LIBCPP_HAS_NO_ASAN
Kostya Serebryany4963c252014-09-02 23:43:38 +0000895 // The annotation for size increase should happen before the actual increase,
896 // but if an exception is thrown after that the annotation has to be undone.
897 struct __RAII_IncreaseAnnotator {
898 __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1)
Eric Fiseliera7c043e2015-03-10 00:25:20 +0000899 : __commit(false), __v(__v), __old_size(__v.size() + __n) {
Kostya Serebryany4963c252014-09-02 23:43:38 +0000900 __v.__annotate_increase(__n);
901 }
902 void __done() { __commit = true; }
903 ~__RAII_IncreaseAnnotator() {
904 if (__commit) return;
Eric Fiseliera7c043e2015-03-10 00:25:20 +0000905 __v.__annotate_shrink(__old_size);
Kostya Serebryany4963c252014-09-02 23:43:38 +0000906 }
907 bool __commit;
Kostya Serebryany4963c252014-09-02 23:43:38 +0000908 const vector &__v;
Eric Fiseliera7c043e2015-03-10 00:25:20 +0000909 size_type __old_size;
Kostya Serebryany4963c252014-09-02 23:43:38 +0000910 };
Marshall Clowc78ffa52014-09-03 21:37:43 +0000911#else
912 struct __RAII_IncreaseAnnotator {
Eric Fiselier6003c772016-12-23 23:37:52 +0000913 _LIBCPP_INLINE_VISIBILITY
914 __RAII_IncreaseAnnotator(const vector &, size_type = 1) {}
915 _LIBCPP_INLINE_VISIBILITY void __done() {}
Marshall Clowc78ffa52014-09-03 21:37:43 +0000916 };
917#endif
918
Howard Hinnantc51e1022010-05-11 19:42:16 +0000919};
920
Marshall Clowf0ca1492018-05-21 21:30:12 +0000921#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
922template<class _InputIterator,
923 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
924 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
925 >
926vector(_InputIterator, _InputIterator)
927 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
928
929template<class _InputIterator,
930 class _Alloc,
931 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
932 >
933vector(_InputIterator, _InputIterator, _Alloc)
934 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
935#endif
936
Howard Hinnantc51e1022010-05-11 19:42:16 +0000937template <class _Tp, class _Allocator>
938void
939vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
940{
Marshall Clow2cd9d372014-05-08 14:14:06 +0000941 __annotate_delete();
Howard Hinnantd2cab2f2012-02-15 00:41:34 +0000942 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000943 _VSTD::swap(this->__begin_, __v.__begin_);
944 _VSTD::swap(this->__end_, __v.__end_);
945 _VSTD::swap(this->__end_cap(), __v.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000946 __v.__first_ = __v.__begin_;
Marshall Clow2cd9d372014-05-08 14:14:06 +0000947 __annotate_new(size());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000948 __invalidate_all_iterators();
949}
950
951template <class _Tp, class _Allocator>
952typename vector<_Tp, _Allocator>::pointer
953vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
954{
Marshall Clow2cd9d372014-05-08 14:14:06 +0000955 __annotate_delete();
Howard Hinnantc51e1022010-05-11 19:42:16 +0000956 pointer __r = __v.__begin_;
Howard Hinnantd2cab2f2012-02-15 00:41:34 +0000957 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
958 __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000959 _VSTD::swap(this->__begin_, __v.__begin_);
960 _VSTD::swap(this->__end_, __v.__end_);
961 _VSTD::swap(this->__end_cap(), __v.__end_cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000962 __v.__first_ = __v.__begin_;
Marshall Clow2cd9d372014-05-08 14:14:06 +0000963 __annotate_new(size());
Howard Hinnantc51e1022010-05-11 19:42:16 +0000964 __invalidate_all_iterators();
965 return __r;
966}
967
968// Allocate space for __n objects
969// throws length_error if __n > max_size()
970// throws (probably bad_alloc) if memory run out
971// Precondition: __begin_ == __end_ == __end_cap() == 0
972// Precondition: __n > 0
973// Postcondition: capacity() == __n
974// Postcondition: size() == 0
975template <class _Tp, class _Allocator>
976void
Marshall Clow3ff48e02018-05-22 16:20:28 +0000977vector<_Tp, _Allocator>::__vallocate(size_type __n)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000978{
979 if (__n > max_size())
980 this->__throw_length_error();
981 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
982 this->__end_cap() = this->__begin_ + __n;
Marshall Clow2cd9d372014-05-08 14:14:06 +0000983 __annotate_new(0);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000984}
985
986template <class _Tp, class _Allocator>
987void
Marshall Clow3ff48e02018-05-22 16:20:28 +0000988vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000989{
Howard Hinnant76053d72013-06-27 19:35:32 +0000990 if (this->__begin_ != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000991 {
992 clear();
993 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
Howard Hinnant76053d72013-06-27 19:35:32 +0000994 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000995 }
996}
997
998template <class _Tp, class _Allocator>
999typename vector<_Tp, _Allocator>::size_type
Howard Hinnant1c936782011-06-03 19:40:40 +00001000vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001001{
Eric Fiselierb5d9f442016-11-23 01:18:56 +00001002 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),
1003 numeric_limits<difference_type>::max());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001004}
1005
1006// Precondition: __new_size > capacity()
1007template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001008inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001009typename vector<_Tp, _Allocator>::size_type
1010vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
1011{
1012 const size_type __ms = max_size();
1013 if (__new_size > __ms)
1014 this->__throw_length_error();
1015 const size_type __cap = capacity();
1016 if (__cap >= __ms / 2)
1017 return __ms;
Alexis Hunt991d29b2011-07-29 23:31:58 +00001018 return _VSTD::max<size_type>(2*__cap, __new_size);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001019}
1020
1021// Default constructs __n objects starting at __end_
1022// throws if construction throws
1023// Precondition: __n > 0
1024// Precondition: size() + __n <= capacity()
1025// Postcondition: size() == size() + __n
1026template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001027void
1028vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
1029{
Howard Hinnantc51e1022010-05-11 19:42:16 +00001030 allocator_type& __a = this->__alloc();
1031 do
1032 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001033 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001034 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001035 ++this->__end_;
1036 --__n;
Kostya Serebryany4963c252014-09-02 23:43:38 +00001037 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001038 } while (__n > 0);
1039}
1040
Howard Hinnantc51e1022010-05-11 19:42:16 +00001041// Copy constructs __n objects starting at __end_ from __x
1042// throws if construction throws
1043// Precondition: __n > 0
1044// Precondition: size() + __n <= capacity()
1045// Postcondition: size() == old size() + __n
1046// Postcondition: [i] == __x for all i in [size() - __n, __n)
1047template <class _Tp, class _Allocator>
Evgeniy Stepanov2fb1cb62015-11-07 01:22:13 +00001048inline
Howard Hinnantc51e1022010-05-11 19:42:16 +00001049void
1050vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
1051{
Howard Hinnantc51e1022010-05-11 19:42:16 +00001052 allocator_type& __a = this->__alloc();
1053 do
1054 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001055 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001056 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001057 ++this->__end_;
1058 --__n;
Kostya Serebryany4963c252014-09-02 23:43:38 +00001059 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001060 } while (__n > 0);
1061}
1062
1063template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001064template <class _ForwardIterator>
1065typename enable_if
1066<
1067 __is_forward_iterator<_ForwardIterator>::value,
1068 void
1069>::type
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001070vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001071{
1072 allocator_type& __a = this->__alloc();
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001073 __RAII_IncreaseAnnotator __annotator(*this, __n);
1074 __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_);
1075 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001076}
1077
1078// Default constructs __n objects starting at __end_
1079// throws if construction throws
1080// Postcondition: size() == size() + __n
Howard Hinnant1c936782011-06-03 19:40:40 +00001081// Exception safety: strong.
Howard Hinnantc51e1022010-05-11 19:42:16 +00001082template <class _Tp, class _Allocator>
1083void
1084vector<_Tp, _Allocator>::__append(size_type __n)
1085{
1086 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1087 this->__construct_at_end(__n);
1088 else
1089 {
1090 allocator_type& __a = this->__alloc();
1091 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1092 __v.__construct_at_end(__n);
1093 __swap_out_circular_buffer(__v);
1094 }
1095}
1096
1097// Default constructs __n objects starting at __end_
1098// throws if construction throws
1099// Postcondition: size() == size() + __n
Howard Hinnant1c936782011-06-03 19:40:40 +00001100// Exception safety: strong.
Howard Hinnantc51e1022010-05-11 19:42:16 +00001101template <class _Tp, class _Allocator>
1102void
1103vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
1104{
1105 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1106 this->__construct_at_end(__n, __x);
1107 else
1108 {
1109 allocator_type& __a = this->__alloc();
1110 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1111 __v.__construct_at_end(__n, __x);
1112 __swap_out_circular_buffer(__v);
1113 }
1114}
1115
1116template <class _Tp, class _Allocator>
1117vector<_Tp, _Allocator>::vector(size_type __n)
1118{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001119#if _LIBCPP_DEBUG_LEVEL >= 2
1120 __get_db()->__insert_c(this);
1121#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001122 if (__n > 0)
1123 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001124 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001125 __construct_at_end(__n);
1126 }
1127}
1128
Marshall Clowd3cbeaa2013-09-14 00:47:59 +00001129#if _LIBCPP_STD_VER > 11
1130template <class _Tp, class _Allocator>
1131vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
1132 : __base(__a)
1133{
1134#if _LIBCPP_DEBUG_LEVEL >= 2
1135 __get_db()->__insert_c(this);
1136#endif
1137 if (__n > 0)
1138 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001139 __vallocate(__n);
Marshall Clowd3cbeaa2013-09-14 00:47:59 +00001140 __construct_at_end(__n);
1141 }
1142}
1143#endif
1144
Howard Hinnantc51e1022010-05-11 19:42:16 +00001145template <class _Tp, class _Allocator>
Marshall Clowf0ca1492018-05-21 21:30:12 +00001146vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001147{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001148#if _LIBCPP_DEBUG_LEVEL >= 2
1149 __get_db()->__insert_c(this);
1150#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001151 if (__n > 0)
1152 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001153 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001154 __construct_at_end(__n, __x);
1155 }
1156}
1157
1158template <class _Tp, class _Allocator>
Marshall Clowf0ca1492018-05-21 21:30:12 +00001159vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001160 : __base(__a)
1161{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001162#if _LIBCPP_DEBUG_LEVEL >= 2
1163 __get_db()->__insert_c(this);
1164#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001165 if (__n > 0)
1166 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001167 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001168 __construct_at_end(__n, __x);
1169 }
1170}
1171
1172template <class _Tp, class _Allocator>
1173template <class _InputIterator>
Howard Hinnant66fce262013-09-21 21:13:54 +00001174vector<_Tp, _Allocator>::vector(_InputIterator __first,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001175 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +00001176 !__is_forward_iterator<_InputIterator>::value &&
1177 is_constructible<
1178 value_type,
Howard Hinnant66fce262013-09-21 21:13:54 +00001179 typename iterator_traits<_InputIterator>::reference>::value,
1180 _InputIterator>::type __last)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001181{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001182#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001183 __get_db()->__insert_c(this);
1184#endif
Howard Hinnant9cd22302011-09-16 18:41:29 +00001185 for (; __first != __last; ++__first)
Eric Fiselier96919722017-10-17 13:03:17 +00001186 __emplace_back(*__first);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001187}
1188
1189template <class _Tp, class _Allocator>
1190template <class _InputIterator>
1191vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1192 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +00001193 !__is_forward_iterator<_InputIterator>::value &&
1194 is_constructible<
1195 value_type,
1196 typename iterator_traits<_InputIterator>::reference>::value>::type*)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001197 : __base(__a)
1198{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001199#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001200 __get_db()->__insert_c(this);
1201#endif
Howard Hinnant9cd22302011-09-16 18:41:29 +00001202 for (; __first != __last; ++__first)
Eric Fiselier96919722017-10-17 13:03:17 +00001203 __emplace_back(*__first);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001204}
1205
1206template <class _Tp, class _Allocator>
1207template <class _ForwardIterator>
Howard Hinnant66fce262013-09-21 21:13:54 +00001208vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
Howard Hinnant88010252013-03-28 17:44:32 +00001209 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1210 is_constructible<
1211 value_type,
Howard Hinnant66fce262013-09-21 21:13:54 +00001212 typename iterator_traits<_ForwardIterator>::reference>::value,
1213 _ForwardIterator>::type __last)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001214{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001215#if _LIBCPP_DEBUG_LEVEL >= 2
1216 __get_db()->__insert_c(this);
1217#endif
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001218 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001219 if (__n > 0)
1220 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001221 __vallocate(__n);
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001222 __construct_at_end(__first, __last, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001223 }
1224}
1225
1226template <class _Tp, class _Allocator>
1227template <class _ForwardIterator>
1228vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
Howard Hinnant88010252013-03-28 17:44:32 +00001229 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1230 is_constructible<
1231 value_type,
1232 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001233 : __base(__a)
1234{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001235#if _LIBCPP_DEBUG_LEVEL >= 2
1236 __get_db()->__insert_c(this);
1237#endif
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001238 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001239 if (__n > 0)
1240 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001241 __vallocate(__n);
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001242 __construct_at_end(__first, __last, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001243 }
1244}
1245
1246template <class _Tp, class _Allocator>
1247vector<_Tp, _Allocator>::vector(const vector& __x)
1248 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1249{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001250#if _LIBCPP_DEBUG_LEVEL >= 2
1251 __get_db()->__insert_c(this);
1252#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001253 size_type __n = __x.size();
1254 if (__n > 0)
1255 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001256 __vallocate(__n);
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001257 __construct_at_end(__x.__begin_, __x.__end_, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001258 }
1259}
1260
1261template <class _Tp, class _Allocator>
1262vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1263 : __base(__a)
1264{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001265#if _LIBCPP_DEBUG_LEVEL >= 2
1266 __get_db()->__insert_c(this);
1267#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001268 size_type __n = __x.size();
1269 if (__n > 0)
1270 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001271 __vallocate(__n);
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001272 __construct_at_end(__x.__begin_, __x.__end_, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001273 }
1274}
1275
Eric Fiseliered9e9362017-04-16 02:40:45 +00001276#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001277
1278template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001279inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001280vector<_Tp, _Allocator>::vector(vector&& __x)
Marshall Clowe5108202015-07-14 14:46:32 +00001281#if _LIBCPP_STD_VER > 14
1282 _NOEXCEPT
1283#else
Howard Hinnant1c936782011-06-03 19:40:40 +00001284 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Marshall Clowe5108202015-07-14 14:46:32 +00001285#endif
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001286 : __base(_VSTD::move(__x.__alloc()))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001287{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001288#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001289 __get_db()->__insert_c(this);
Howard Hinnanta1e60cd2011-09-19 16:34:29 +00001290 __get_db()->swap(this, &__x);
Howard Hinnant27e0e772011-09-14 18:33:51 +00001291#endif
Howard Hinnant9cd22302011-09-16 18:41:29 +00001292 this->__begin_ = __x.__begin_;
1293 this->__end_ = __x.__end_;
1294 this->__end_cap() = __x.__end_cap();
Howard Hinnant76053d72013-06-27 19:35:32 +00001295 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001296}
1297
1298template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001299inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001300vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1301 : __base(__a)
1302{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001303#if _LIBCPP_DEBUG_LEVEL >= 2
1304 __get_db()->__insert_c(this);
1305#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001306 if (__a == __x.__alloc())
1307 {
1308 this->__begin_ = __x.__begin_;
1309 this->__end_ = __x.__end_;
1310 this->__end_cap() = __x.__end_cap();
1311 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
Howard Hinnanta1e60cd2011-09-19 16:34:29 +00001312#if _LIBCPP_DEBUG_LEVEL >= 2
1313 __get_db()->swap(this, &__x);
1314#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001315 }
1316 else
1317 {
Howard Hinnantc834c512011-11-29 18:15:50 +00001318 typedef move_iterator<iterator> _Ip;
1319 assign(_Ip(__x.begin()), _Ip(__x.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001320 }
1321}
1322
1323template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001324inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001325vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1326{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001327#if _LIBCPP_DEBUG_LEVEL >= 2
1328 __get_db()->__insert_c(this);
1329#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001330 if (__il.size() > 0)
1331 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001332 __vallocate(__il.size());
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001333 __construct_at_end(__il.begin(), __il.end(), __il.size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001334 }
1335}
1336
1337template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001338inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001339vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1340 : __base(__a)
1341{
Howard Hinnant9cd22302011-09-16 18:41:29 +00001342#if _LIBCPP_DEBUG_LEVEL >= 2
1343 __get_db()->__insert_c(this);
1344#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001345 if (__il.size() > 0)
1346 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001347 __vallocate(__il.size());
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001348 __construct_at_end(__il.begin(), __il.end(), __il.size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001349 }
1350}
1351
1352template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001353inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001354vector<_Tp, _Allocator>&
1355vector<_Tp, _Allocator>::operator=(vector&& __x)
Marshall Clow2fe8a8d2015-08-18 18:57:00 +00001356 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001357{
1358 __move_assign(__x, integral_constant<bool,
1359 __alloc_traits::propagate_on_container_move_assignment::value>());
1360 return *this;
1361}
1362
1363template <class _Tp, class _Allocator>
1364void
1365vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
Marshall Clow2fe8a8d2015-08-18 18:57:00 +00001366 _NOEXCEPT_(__alloc_traits::is_always_equal::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001367{
1368 if (__base::__alloc() != __c.__alloc())
1369 {
Howard Hinnantc834c512011-11-29 18:15:50 +00001370 typedef move_iterator<iterator> _Ip;
1371 assign(_Ip(__c.begin()), _Ip(__c.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001372 }
1373 else
1374 __move_assign(__c, true_type());
1375}
1376
1377template <class _Tp, class _Allocator>
1378void
1379vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
Howard Hinnant1c936782011-06-03 19:40:40 +00001380 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001381{
Marshall Clow3ff48e02018-05-22 16:20:28 +00001382 __vdeallocate();
Marshall Clow136d45c2014-07-21 15:11:13 +00001383 __base::__move_assign_alloc(__c); // this can throw
Howard Hinnantc51e1022010-05-11 19:42:16 +00001384 this->__begin_ = __c.__begin_;
1385 this->__end_ = __c.__end_;
1386 this->__end_cap() = __c.__end_cap();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001387 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
Howard Hinnanta1e60cd2011-09-19 16:34:29 +00001388#if _LIBCPP_DEBUG_LEVEL >= 2
1389 __get_db()->swap(this, &__c);
1390#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001391}
1392
Eric Fiseliered9e9362017-04-16 02:40:45 +00001393#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001394
1395template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001396inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001397vector<_Tp, _Allocator>&
1398vector<_Tp, _Allocator>::operator=(const vector& __x)
1399{
1400 if (this != &__x)
1401 {
1402 __base::__copy_assign_alloc(__x);
1403 assign(__x.__begin_, __x.__end_);
1404 }
1405 return *this;
1406}
1407
1408template <class _Tp, class _Allocator>
1409template <class _InputIterator>
1410typename enable_if
1411<
1412 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +00001413 !__is_forward_iterator<_InputIterator>::value &&
1414 is_constructible<
1415 _Tp,
1416 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001417 void
1418>::type
1419vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1420{
1421 clear();
1422 for (; __first != __last; ++__first)
Eric Fiselier96919722017-10-17 13:03:17 +00001423 __emplace_back(*__first);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001424}
1425
1426template <class _Tp, class _Allocator>
1427template <class _ForwardIterator>
1428typename enable_if
1429<
Howard Hinnant88010252013-03-28 17:44:32 +00001430 __is_forward_iterator<_ForwardIterator>::value &&
1431 is_constructible<
1432 _Tp,
1433 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001434 void
1435>::type
1436vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1437{
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001438 size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
1439 if (__new_size <= capacity())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001440 {
1441 _ForwardIterator __mid = __last;
1442 bool __growing = false;
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001443 if (__new_size > size())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001444 {
1445 __growing = true;
1446 __mid = __first;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001447 _VSTD::advance(__mid, size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001448 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001449 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001450 if (__growing)
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001451 __construct_at_end(__mid, __last, __new_size - size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001452 else
1453 this->__destruct_at_end(__m);
1454 }
1455 else
1456 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001457 __vdeallocate();
1458 __vallocate(__recommend(__new_size));
Eric Fiselieracfe6f02015-03-31 16:54:19 +00001459 __construct_at_end(__first, __last, __new_size);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001460 }
Eric Fiselier69c51982016-12-28 06:06:09 +00001461 __invalidate_all_iterators();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001462}
1463
1464template <class _Tp, class _Allocator>
1465void
1466vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1467{
1468 if (__n <= capacity())
1469 {
1470 size_type __s = size();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001471 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001472 if (__n > __s)
1473 __construct_at_end(__n - __s, __u);
1474 else
Howard Hinnant155c2af2010-05-24 17:49:41 +00001475 this->__destruct_at_end(this->__begin_ + __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001476 }
1477 else
1478 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00001479 __vdeallocate();
1480 __vallocate(__recommend(static_cast<size_type>(__n)));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001481 __construct_at_end(__n, __u);
1482 }
Eric Fiselier69c51982016-12-28 06:06:09 +00001483 __invalidate_all_iterators();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001484}
1485
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001486template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001487inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001488typename vector<_Tp, _Allocator>::iterator
Howard Hinnant1c936782011-06-03 19:40:40 +00001489vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001490{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001491#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantc51e1022010-05-11 19:42:16 +00001492 return iterator(this, __p);
1493#else
1494 return iterator(__p);
1495#endif
1496}
1497
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001498template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001499inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001500typename vector<_Tp, _Allocator>::const_iterator
Howard Hinnant1c936782011-06-03 19:40:40 +00001501vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001502{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001503#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantc51e1022010-05-11 19:42:16 +00001504 return const_iterator(this, __p);
1505#else
1506 return const_iterator(__p);
1507#endif
1508}
1509
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001510template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001511inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001512typename vector<_Tp, _Allocator>::iterator
Howard Hinnant1c936782011-06-03 19:40:40 +00001513vector<_Tp, _Allocator>::begin() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001514{
1515 return __make_iter(this->__begin_);
1516}
1517
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001518template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001519inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001520typename vector<_Tp, _Allocator>::const_iterator
Howard Hinnant1c936782011-06-03 19:40:40 +00001521vector<_Tp, _Allocator>::begin() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001522{
1523 return __make_iter(this->__begin_);
1524}
1525
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001526template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001527inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001528typename vector<_Tp, _Allocator>::iterator
Howard Hinnant1c936782011-06-03 19:40:40 +00001529vector<_Tp, _Allocator>::end() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001530{
1531 return __make_iter(this->__end_);
1532}
1533
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001534template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001535inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001536typename vector<_Tp, _Allocator>::const_iterator
Howard Hinnant1c936782011-06-03 19:40:40 +00001537vector<_Tp, _Allocator>::end() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001538{
1539 return __make_iter(this->__end_);
1540}
1541
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001542template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001543inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001544typename vector<_Tp, _Allocator>::reference
Marshall Clowd6470492019-03-15 00:29:35 +00001545vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001546{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001547 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
Howard Hinnantc51e1022010-05-11 19:42:16 +00001548 return this->__begin_[__n];
1549}
1550
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001551template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001552inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001553typename vector<_Tp, _Allocator>::const_reference
Marshall Clowd6470492019-03-15 00:29:35 +00001554vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001555{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001556 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
Howard Hinnantc51e1022010-05-11 19:42:16 +00001557 return this->__begin_[__n];
1558}
1559
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001560template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001561typename vector<_Tp, _Allocator>::reference
1562vector<_Tp, _Allocator>::at(size_type __n)
1563{
1564 if (__n >= size())
1565 this->__throw_out_of_range();
1566 return this->__begin_[__n];
1567}
1568
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001569template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001570typename vector<_Tp, _Allocator>::const_reference
1571vector<_Tp, _Allocator>::at(size_type __n) const
1572{
1573 if (__n >= size())
1574 this->__throw_out_of_range();
1575 return this->__begin_[__n];
1576}
1577
1578template <class _Tp, class _Allocator>
1579void
1580vector<_Tp, _Allocator>::reserve(size_type __n)
1581{
1582 if (__n > capacity())
1583 {
1584 allocator_type& __a = this->__alloc();
Howard Hinnant1c936782011-06-03 19:40:40 +00001585 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001586 __swap_out_circular_buffer(__v);
1587 }
1588}
1589
1590template <class _Tp, class _Allocator>
1591void
Howard Hinnant1c936782011-06-03 19:40:40 +00001592vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00001593{
1594 if (capacity() > size())
1595 {
1596#ifndef _LIBCPP_NO_EXCEPTIONS
1597 try
1598 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001599#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001600 allocator_type& __a = this->__alloc();
Howard Hinnant1c936782011-06-03 19:40:40 +00001601 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001602 __swap_out_circular_buffer(__v);
1603#ifndef _LIBCPP_NO_EXCEPTIONS
1604 }
1605 catch (...)
1606 {
1607 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001608#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001609 }
1610}
1611
1612template <class _Tp, class _Allocator>
Howard Hinnantd2cab2f2012-02-15 00:41:34 +00001613template <class _Up>
1614void
Eric Fiseliered9e9362017-04-16 02:40:45 +00001615#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd2cab2f2012-02-15 00:41:34 +00001616vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1617#else
1618vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1619#endif
1620{
1621 allocator_type& __a = this->__alloc();
1622 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1623 // __v.push_back(_VSTD::forward<_Up>(__x));
Howard Hinnant5adee4c2013-01-11 20:36:59 +00001624 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
1625 __v.__end_++;
Howard Hinnantd2cab2f2012-02-15 00:41:34 +00001626 __swap_out_circular_buffer(__v);
1627}
1628
1629template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001630inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001631void
1632vector<_Tp, _Allocator>::push_back(const_reference __x)
1633{
Howard Hinnantd2cab2f2012-02-15 00:41:34 +00001634 if (this->__end_ != this->__end_cap())
Howard Hinnantc51e1022010-05-11 19:42:16 +00001635 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001636 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001637 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001638 _VSTD::__to_raw_pointer(this->__end_), __x);
Kostya Serebryany4963c252014-09-02 23:43:38 +00001639 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001640 ++this->__end_;
1641 }
1642 else
Howard Hinnantd2cab2f2012-02-15 00:41:34 +00001643 __push_back_slow_path(__x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001644}
1645
Eric Fiseliered9e9362017-04-16 02:40:45 +00001646#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001647
1648template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001649inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001650void
1651vector<_Tp, _Allocator>::push_back(value_type&& __x)
1652{
1653 if (this->__end_ < this->__end_cap())
1654 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001655 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001656 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001657 _VSTD::__to_raw_pointer(this->__end_),
1658 _VSTD::move(__x));
Kostya Serebryany4963c252014-09-02 23:43:38 +00001659 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001660 ++this->__end_;
1661 }
1662 else
Howard Hinnantd2cab2f2012-02-15 00:41:34 +00001663 __push_back_slow_path(_VSTD::move(__x));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001664}
1665
1666template <class _Tp, class _Allocator>
1667template <class... _Args>
1668void
Howard Hinnantb6c49562012-02-26 15:30:12 +00001669vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1670{
1671 allocator_type& __a = this->__alloc();
1672 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1673// __v.emplace_back(_VSTD::forward<_Args>(__args)...);
Howard Hinnant5adee4c2013-01-11 20:36:59 +00001674 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
1675 __v.__end_++;
Howard Hinnantb6c49562012-02-26 15:30:12 +00001676 __swap_out_circular_buffer(__v);
1677}
1678
1679template <class _Tp, class _Allocator>
1680template <class... _Args>
Evgeniy Stepanov2fb1cb62015-11-07 01:22:13 +00001681inline
Marshall Clowea52cc42017-01-24 23:09:12 +00001682#if _LIBCPP_STD_VER > 14
Eric Fiselier34ba5b92016-07-21 03:20:17 +00001683typename vector<_Tp, _Allocator>::reference
Marshall Clowea52cc42017-01-24 23:09:12 +00001684#else
1685void
1686#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001687vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1688{
1689 if (this->__end_ < this->__end_cap())
1690 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001691 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001692 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001693 _VSTD::__to_raw_pointer(this->__end_),
1694 _VSTD::forward<_Args>(__args)...);
Kostya Serebryany4963c252014-09-02 23:43:38 +00001695 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001696 ++this->__end_;
1697 }
1698 else
Howard Hinnantb6c49562012-02-26 15:30:12 +00001699 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
Marshall Clowea52cc42017-01-24 23:09:12 +00001700#if _LIBCPP_STD_VER > 14
Eric Fiselier34ba5b92016-07-21 03:20:17 +00001701 return this->back();
Marshall Clowea52cc42017-01-24 23:09:12 +00001702#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001703}
1704
Eric Fiseliered9e9362017-04-16 02:40:45 +00001705#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001706
1707template <class _Tp, class _Allocator>
Evgeniy Stepanov2fb1cb62015-11-07 01:22:13 +00001708inline
Howard Hinnantc51e1022010-05-11 19:42:16 +00001709void
1710vector<_Tp, _Allocator>::pop_back()
1711{
Howard Hinnant27e0e772011-09-14 18:33:51 +00001712 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
Howard Hinnantc51e1022010-05-11 19:42:16 +00001713 this->__destruct_at_end(this->__end_ - 1);
1714}
1715
1716template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00001717inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001718typename vector<_Tp, _Allocator>::iterator
1719vector<_Tp, _Allocator>::erase(const_iterator __position)
1720{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001721#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001722 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1723 "vector::erase(iterator) called with an iterator not"
1724 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001725#endif
Howard Hinnant58d52d52013-03-25 22:12:26 +00001726 _LIBCPP_ASSERT(__position != end(),
1727 "vector::erase(iterator) called with a non-dereferenceable iterator");
Howard Hinnant76053d72013-06-27 19:35:32 +00001728 difference_type __ps = __position - cbegin();
1729 pointer __p = this->__begin_ + __ps;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001730 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
Eric Fiselier69c51982016-12-28 06:06:09 +00001731 this->__invalidate_iterators_past(__p-1);
1732 iterator __r = __make_iter(__p);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001733 return __r;
1734}
1735
1736template <class _Tp, class _Allocator>
1737typename vector<_Tp, _Allocator>::iterator
1738vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1739{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001740#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001741 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1742 "vector::erase(iterator, iterator) called with an iterator not"
1743 " referring to this vector");
Eric Fiselier69c51982016-12-28 06:06:09 +00001744 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
1745 "vector::erase(iterator, iterator) called with an iterator not"
1746 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001747#endif
Howard Hinnant27e0e772011-09-14 18:33:51 +00001748 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
Howard Hinnantc51e1022010-05-11 19:42:16 +00001749 pointer __p = this->__begin_ + (__first - begin());
Eric Fiselier69c51982016-12-28 06:06:09 +00001750 if (__first != __last) {
Howard Hinnantc580cc32013-04-18 15:02:57 +00001751 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
Eric Fiselier69c51982016-12-28 06:06:09 +00001752 this->__invalidate_iterators_past(__p - 1);
1753 }
1754 iterator __r = __make_iter(__p);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001755 return __r;
1756}
1757
1758template <class _Tp, class _Allocator>
1759void
1760vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1761{
1762 pointer __old_last = this->__end_;
1763 difference_type __n = __old_last - __to;
1764 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1765 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001766 _VSTD::__to_raw_pointer(this->__end_),
1767 _VSTD::move(*__i));
1768 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001769}
1770
1771template <class _Tp, class _Allocator>
1772typename vector<_Tp, _Allocator>::iterator
1773vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1774{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001775#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001776 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1777 "vector::insert(iterator, x) called with an iterator not"
1778 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001779#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001780 pointer __p = this->__begin_ + (__position - begin());
1781 if (this->__end_ < this->__end_cap())
1782 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001783 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001784 if (__p == this->__end_)
1785 {
1786 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001787 _VSTD::__to_raw_pointer(this->__end_), __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001788 ++this->__end_;
1789 }
1790 else
1791 {
1792 __move_range(__p, this->__end_, __p + 1);
1793 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1794 if (__p <= __xr && __xr < this->__end_)
1795 ++__xr;
1796 *__p = *__xr;
1797 }
Kostya Serebryany4963c252014-09-02 23:43:38 +00001798 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001799 }
1800 else
1801 {
1802 allocator_type& __a = this->__alloc();
1803 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1804 __v.push_back(__x);
1805 __p = __swap_out_circular_buffer(__v, __p);
1806 }
1807 return __make_iter(__p);
1808}
1809
Eric Fiseliered9e9362017-04-16 02:40:45 +00001810#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001811
1812template <class _Tp, class _Allocator>
1813typename vector<_Tp, _Allocator>::iterator
1814vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1815{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001816#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001817 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1818 "vector::insert(iterator, x) called with an iterator not"
1819 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001820#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001821 pointer __p = this->__begin_ + (__position - begin());
1822 if (this->__end_ < this->__end_cap())
1823 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001824 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001825 if (__p == this->__end_)
1826 {
1827 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001828 _VSTD::__to_raw_pointer(this->__end_),
1829 _VSTD::move(__x));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001830 ++this->__end_;
1831 }
1832 else
1833 {
1834 __move_range(__p, this->__end_, __p + 1);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001835 *__p = _VSTD::move(__x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001836 }
Kostya Serebryany4963c252014-09-02 23:43:38 +00001837 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001838 }
1839 else
1840 {
1841 allocator_type& __a = this->__alloc();
1842 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001843 __v.push_back(_VSTD::move(__x));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001844 __p = __swap_out_circular_buffer(__v, __p);
1845 }
1846 return __make_iter(__p);
1847}
1848
1849template <class _Tp, class _Allocator>
1850template <class... _Args>
1851typename vector<_Tp, _Allocator>::iterator
1852vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1853{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001854#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001855 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1856 "vector::emplace(iterator, x) called with an iterator not"
1857 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001858#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001859 pointer __p = this->__begin_ + (__position - begin());
1860 if (this->__end_ < this->__end_cap())
1861 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00001862 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001863 if (__p == this->__end_)
1864 {
1865 __alloc_traits::construct(this->__alloc(),
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001866 _VSTD::__to_raw_pointer(this->__end_),
1867 _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001868 ++this->__end_;
1869 }
1870 else
1871 {
Marshall Clowa591b9a2016-07-11 21:38:08 +00001872 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001873 __move_range(__p, this->__end_, __p + 1);
Marshall Clowa591b9a2016-07-11 21:38:08 +00001874 *__p = _VSTD::move(__tmp.get());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001875 }
Kostya Serebryany4963c252014-09-02 23:43:38 +00001876 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001877 }
1878 else
1879 {
1880 allocator_type& __a = this->__alloc();
1881 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001882 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001883 __p = __swap_out_circular_buffer(__v, __p);
1884 }
1885 return __make_iter(__p);
1886}
1887
Eric Fiseliered9e9362017-04-16 02:40:45 +00001888#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001889
1890template <class _Tp, class _Allocator>
1891typename vector<_Tp, _Allocator>::iterator
1892vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1893{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001894#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001895 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1896 "vector::insert(iterator, n, x) called with an iterator not"
1897 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001898#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001899 pointer __p = this->__begin_ + (__position - begin());
1900 if (__n > 0)
1901 {
1902 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1903 {
1904 size_type __old_n = __n;
1905 pointer __old_last = this->__end_;
1906 if (__n > static_cast<size_type>(this->__end_ - __p))
1907 {
1908 size_type __cx = __n - (this->__end_ - __p);
1909 __construct_at_end(__cx, __x);
1910 __n -= __cx;
1911 }
1912 if (__n > 0)
1913 {
Eric Fiselier2a649652014-11-14 18:28:36 +00001914 __RAII_IncreaseAnnotator __annotator(*this, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001915 __move_range(__p, __old_last, __p + __old_n);
Kostya Serebryany4963c252014-09-02 23:43:38 +00001916 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001917 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1918 if (__p <= __xr && __xr < this->__end_)
1919 __xr += __old_n;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001920 _VSTD::fill_n(__p, __n, *__xr);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001921 }
1922 }
1923 else
1924 {
1925 allocator_type& __a = this->__alloc();
1926 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1927 __v.__construct_at_end(__n, __x);
1928 __p = __swap_out_circular_buffer(__v, __p);
1929 }
1930 }
1931 return __make_iter(__p);
1932}
1933
1934template <class _Tp, class _Allocator>
1935template <class _InputIterator>
1936typename enable_if
1937<
1938 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant88010252013-03-28 17:44:32 +00001939 !__is_forward_iterator<_InputIterator>::value &&
1940 is_constructible<
1941 _Tp,
1942 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001943 typename vector<_Tp, _Allocator>::iterator
1944>::type
1945vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1946{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001947#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00001948 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1949 "vector::insert(iterator, range) called with an iterator not"
1950 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00001951#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001952 difference_type __off = __position - begin();
1953 pointer __p = this->__begin_ + __off;
1954 allocator_type& __a = this->__alloc();
1955 pointer __old_last = this->__end_;
1956 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1957 {
Eric Fiselier489fd502015-07-18 18:22:12 +00001958 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001959 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
Howard Hinnantc51e1022010-05-11 19:42:16 +00001960 *__first);
1961 ++this->__end_;
Eric Fiselier489fd502015-07-18 18:22:12 +00001962 __annotator.__done();
Howard Hinnantc51e1022010-05-11 19:42:16 +00001963 }
1964 __split_buffer<value_type, allocator_type&> __v(__a);
1965 if (__first != __last)
1966 {
1967#ifndef _LIBCPP_NO_EXCEPTIONS
1968 try
1969 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001970#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001971 __v.__construct_at_end(__first, __last);
1972 difference_type __old_size = __old_last - this->__begin_;
1973 difference_type __old_p = __p - this->__begin_;
1974 reserve(__recommend(size() + __v.size()));
1975 __p = this->__begin_ + __old_p;
1976 __old_last = this->__begin_ + __old_size;
1977#ifndef _LIBCPP_NO_EXCEPTIONS
1978 }
1979 catch (...)
1980 {
1981 erase(__make_iter(__old_last), end());
1982 throw;
1983 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001984#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001985 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001986 __p = _VSTD::rotate(__p, __old_last, this->__end_);
Howard Hinnant9cd22302011-09-16 18:41:29 +00001987 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1988 make_move_iterator(__v.end()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001989 return begin() + __off;
1990}
1991
1992template <class _Tp, class _Allocator>
1993template <class _ForwardIterator>
1994typename enable_if
1995<
Howard Hinnant88010252013-03-28 17:44:32 +00001996 __is_forward_iterator<_ForwardIterator>::value &&
1997 is_constructible<
1998 _Tp,
1999 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantc51e1022010-05-11 19:42:16 +00002000 typename vector<_Tp, _Allocator>::iterator
2001>::type
2002vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
2003{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002004#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00002005 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
2006 "vector::insert(iterator, range) called with an iterator not"
2007 " referring to this vector");
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002008#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002009 pointer __p = this->__begin_ + (__position - begin());
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002010 difference_type __n = _VSTD::distance(__first, __last);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002011 if (__n > 0)
2012 {
2013 if (__n <= this->__end_cap() - this->__end_)
2014 {
2015 size_type __old_n = __n;
2016 pointer __old_last = this->__end_;
2017 _ForwardIterator __m = __last;
2018 difference_type __dx = this->__end_ - __p;
2019 if (__n > __dx)
2020 {
2021 __m = __first;
Eric Fiselieracfe6f02015-03-31 16:54:19 +00002022 difference_type __diff = this->__end_ - __p;
2023 _VSTD::advance(__m, __diff);
2024 __construct_at_end(__m, __last, __n - __diff);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002025 __n = __dx;
2026 }
2027 if (__n > 0)
2028 {
Kostya Serebryany4963c252014-09-02 23:43:38 +00002029 __RAII_IncreaseAnnotator __annotator(*this, __n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002030 __move_range(__p, __old_last, __p + __old_n);
Kostya Serebryany4963c252014-09-02 23:43:38 +00002031 __annotator.__done();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002032 _VSTD::copy(__first, __m, __p);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002033 }
2034 }
2035 else
2036 {
2037 allocator_type& __a = this->__alloc();
2038 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
2039 __v.__construct_at_end(__first, __last);
2040 __p = __swap_out_circular_buffer(__v, __p);
2041 }
2042 }
2043 return __make_iter(__p);
2044}
2045
2046template <class _Tp, class _Allocator>
2047void
2048vector<_Tp, _Allocator>::resize(size_type __sz)
2049{
2050 size_type __cs = size();
2051 if (__cs < __sz)
2052 this->__append(__sz - __cs);
2053 else if (__cs > __sz)
2054 this->__destruct_at_end(this->__begin_ + __sz);
2055}
2056
2057template <class _Tp, class _Allocator>
2058void
2059vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
2060{
2061 size_type __cs = size();
2062 if (__cs < __sz)
2063 this->__append(__sz - __cs, __x);
2064 else if (__cs > __sz)
2065 this->__destruct_at_end(this->__begin_ + __sz);
2066}
2067
2068template <class _Tp, class _Allocator>
2069void
2070vector<_Tp, _Allocator>::swap(vector& __x)
Marshall Clow8982dcd2015-07-13 20:04:56 +00002071#if _LIBCPP_STD_VER >= 14
Eric Fiselier873b8d32019-03-18 21:50:12 +00002072 _NOEXCEPT
Marshall Clow8982dcd2015-07-13 20:04:56 +00002073#else
Eric Fiselier873b8d32019-03-18 21:50:12 +00002074 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
Marshall Clow8982dcd2015-07-13 20:04:56 +00002075 __is_nothrow_swappable<allocator_type>::value)
2076#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002077{
Howard Hinnant27e0e772011-09-14 18:33:51 +00002078 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
2079 this->__alloc() == __x.__alloc(),
2080 "vector::swap: Either propagate_on_container_swap must be true"
2081 " or the allocators must compare equal");
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002082 _VSTD::swap(this->__begin_, __x.__begin_);
2083 _VSTD::swap(this->__end_, __x.__end_);
2084 _VSTD::swap(this->__end_cap(), __x.__end_cap());
Eric Fiseliered9e9362017-04-16 02:40:45 +00002085 __swap_allocator(this->__alloc(), __x.__alloc(),
Marshall Clow8982dcd2015-07-13 20:04:56 +00002086 integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002087#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00002088 __get_db()->swap(this, &__x);
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002089#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantc51e1022010-05-11 19:42:16 +00002090}
2091
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002092template <class _Tp, class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00002093bool
2094vector<_Tp, _Allocator>::__invariants() const
2095{
Howard Hinnant76053d72013-06-27 19:35:32 +00002096 if (this->__begin_ == nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002097 {
Howard Hinnant76053d72013-06-27 19:35:32 +00002098 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002099 return false;
2100 }
2101 else
2102 {
2103 if (this->__begin_ > this->__end_)
2104 return false;
2105 if (this->__begin_ == this->__end_cap())
2106 return false;
2107 if (this->__end_ > this->__end_cap())
2108 return false;
2109 }
2110 return true;
2111}
2112
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002113#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00002114
Howard Hinnantc51e1022010-05-11 19:42:16 +00002115template <class _Tp, class _Allocator>
Howard Hinnant27e0e772011-09-14 18:33:51 +00002116bool
2117vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
2118{
2119 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
2120}
2121
2122template <class _Tp, class _Allocator>
2123bool
2124vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
2125{
2126 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
2127}
2128
2129template <class _Tp, class _Allocator>
2130bool
2131vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2132{
2133 const_pointer __p = __i->base() + __n;
2134 return this->__begin_ <= __p && __p <= this->__end_;
2135}
2136
2137template <class _Tp, class _Allocator>
2138bool
2139vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2140{
2141 const_pointer __p = __i->base() + __n;
2142 return this->__begin_ <= __p && __p < this->__end_;
2143}
2144
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002145#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00002146
2147template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002148inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002149void
2150vector<_Tp, _Allocator>::__invalidate_all_iterators()
2151{
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002152#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant27e0e772011-09-14 18:33:51 +00002153 __get_db()->__invalidate_all(this);
Howard Hinnanta47c6d52011-09-16 17:29:17 +00002154#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantc51e1022010-05-11 19:42:16 +00002155}
2156
Eric Fiselier69c51982016-12-28 06:06:09 +00002157
2158template <class _Tp, class _Allocator>
2159inline _LIBCPP_INLINE_VISIBILITY
2160void
2161vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) {
2162#if _LIBCPP_DEBUG_LEVEL >= 2
2163 __c_node* __c = __get_db()->__find_c_and_lock(this);
2164 for (__i_node** __p = __c->end_; __p != __c->beg_; ) {
2165 --__p;
2166 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
2167 if (__i->base() > __new_last) {
2168 (*__p)->__c_ = nullptr;
2169 if (--__c->end_ != __p)
2170 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
2171 }
2172 }
2173 __get_db()->unlock();
2174#else
2175 ((void)__new_last);
2176#endif
2177}
2178
Howard Hinnantc51e1022010-05-11 19:42:16 +00002179// vector<bool>
2180
2181template <class _Allocator> class vector<bool, _Allocator>;
2182
2183template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2184
2185template <class _Allocator>
Howard Hinnantb4ef6482011-07-02 20:33:23 +00002186struct __has_storage_type<vector<bool, _Allocator> >
2187{
2188 static const bool value = true;
2189};
2190
2191template <class _Allocator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00002192class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00002193 : private __vector_base_common<true>
2194{
2195public:
2196 typedef vector __self;
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002197 typedef bool value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002198 typedef _Allocator allocator_type;
2199 typedef allocator_traits<allocator_type> __alloc_traits;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002200 typedef typename __alloc_traits::size_type size_type;
2201 typedef typename __alloc_traits::difference_type difference_type;
Howard Hinnant896b7622012-05-07 16:50:38 +00002202 typedef size_type __storage_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002203 typedef __bit_iterator<vector, false> pointer;
2204 typedef __bit_iterator<vector, true> const_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002205 typedef pointer iterator;
2206 typedef const_pointer const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002207 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2208 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002209
2210private:
Marshall Clow940e01c2015-04-07 05:21:38 +00002211 typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002212 typedef allocator_traits<__storage_allocator> __storage_traits;
2213 typedef typename __storage_traits::pointer __storage_pointer;
2214 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2215
2216 __storage_pointer __begin_;
2217 size_type __size_;
2218 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
Howard Hinnant71d1c192011-07-09 15:50:42 +00002219public:
Howard Hinnantb4ef6482011-07-02 20:33:23 +00002220 typedef __bit_reference<vector> reference;
2221 typedef __bit_const_reference<vector> const_reference;
Howard Hinnant71d1c192011-07-09 15:50:42 +00002222private:
Howard Hinnant1c936782011-06-03 19:40:40 +00002223 _LIBCPP_INLINE_VISIBILITY
2224 size_type& __cap() _NOEXCEPT
2225 {return __cap_alloc_.first();}
2226 _LIBCPP_INLINE_VISIBILITY
2227 const size_type& __cap() const _NOEXCEPT
2228 {return __cap_alloc_.first();}
2229 _LIBCPP_INLINE_VISIBILITY
2230 __storage_allocator& __alloc() _NOEXCEPT
2231 {return __cap_alloc_.second();}
2232 _LIBCPP_INLINE_VISIBILITY
2233 const __storage_allocator& __alloc() const _NOEXCEPT
2234 {return __cap_alloc_.second();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002235
2236 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2237
Howard Hinnant1c936782011-06-03 19:40:40 +00002238 _LIBCPP_INLINE_VISIBILITY
2239 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002240 {return __n * __bits_per_word;}
Howard Hinnant1c936782011-06-03 19:40:40 +00002241 _LIBCPP_INLINE_VISIBILITY
2242 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002243 {return (__n - 1) / __bits_per_word + 1;}
2244
2245public:
Howard Hinnant1c936782011-06-03 19:40:40 +00002246 _LIBCPP_INLINE_VISIBILITY
Marshall Clowe546cbb2015-06-04 02:05:41 +00002247 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Marshall Clow8f282f42015-06-04 00:10:20 +00002248
2249 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
2250#if _LIBCPP_STD_VER <= 14
2251 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
2252#else
2253 _NOEXCEPT;
2254#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002255 ~vector();
2256 explicit vector(size_type __n);
Marshall Clowd3cbeaa2013-09-14 00:47:59 +00002257#if _LIBCPP_STD_VER > 11
2258 explicit vector(size_type __n, const allocator_type& __a);
2259#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002260 vector(size_type __n, const value_type& __v);
2261 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2262 template <class _InputIterator>
2263 vector(_InputIterator __first, _InputIterator __last,
2264 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2265 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2266 template <class _InputIterator>
2267 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2268 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2269 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2270 template <class _ForwardIterator>
2271 vector(_ForwardIterator __first, _ForwardIterator __last,
2272 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2273 template <class _ForwardIterator>
2274 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2275 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2276
2277 vector(const vector& __v);
2278 vector(const vector& __v, const allocator_type& __a);
2279 vector& operator=(const vector& __v);
Eric Fiseliered9e9362017-04-16 02:40:45 +00002280
2281#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00002282 vector(initializer_list<value_type> __il);
2283 vector(initializer_list<value_type> __il, const allocator_type& __a);
2284
Howard Hinnant1c936782011-06-03 19:40:40 +00002285 _LIBCPP_INLINE_VISIBILITY
2286 vector(vector&& __v)
Marshall Clowe5108202015-07-14 14:46:32 +00002287#if _LIBCPP_STD_VER > 14
2288 _NOEXCEPT;
2289#else
Howard Hinnant1c936782011-06-03 19:40:40 +00002290 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Marshall Clowe5108202015-07-14 14:46:32 +00002291#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002292 vector(vector&& __v, const allocator_type& __a);
Howard Hinnant1c936782011-06-03 19:40:40 +00002293 _LIBCPP_INLINE_VISIBILITY
2294 vector& operator=(vector&& __v)
Marshall Clow2fe8a8d2015-08-18 18:57:00 +00002295 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
Eric Fiseliered9e9362017-04-16 02:40:45 +00002296
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002297 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002298 vector& operator=(initializer_list<value_type> __il)
2299 {assign(__il.begin(), __il.end()); return *this;}
Eric Fiseliered9e9362017-04-16 02:40:45 +00002300
2301#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00002302
2303 template <class _InputIterator>
2304 typename enable_if
2305 <
2306 __is_input_iterator<_InputIterator>::value &&
2307 !__is_forward_iterator<_InputIterator>::value,
2308 void
2309 >::type
2310 assign(_InputIterator __first, _InputIterator __last);
2311 template <class _ForwardIterator>
2312 typename enable_if
2313 <
2314 __is_forward_iterator<_ForwardIterator>::value,
2315 void
2316 >::type
2317 assign(_ForwardIterator __first, _ForwardIterator __last);
2318
2319 void assign(size_type __n, const value_type& __x);
Eric Fiseliered9e9362017-04-16 02:40:45 +00002320
2321#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002322 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002323 void assign(initializer_list<value_type> __il)
2324 {assign(__il.begin(), __il.end());}
Eric Fiseliered9e9362017-04-16 02:40:45 +00002325#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002326
Howard Hinnant1c936782011-06-03 19:40:40 +00002327 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002328 {return allocator_type(this->__alloc());}
2329
Howard Hinnant1c936782011-06-03 19:40:40 +00002330 size_type max_size() const _NOEXCEPT;
2331 _LIBCPP_INLINE_VISIBILITY
2332 size_type capacity() const _NOEXCEPT
2333 {return __internal_cap_to_external(__cap());}
2334 _LIBCPP_INLINE_VISIBILITY
2335 size_type size() const _NOEXCEPT
2336 {return __size_;}
Marshall Clow425f5752017-11-15 05:51:26 +00002337 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +00002338 bool empty() const _NOEXCEPT
2339 {return __size_ == 0;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002340 void reserve(size_type __n);
Howard Hinnant1c936782011-06-03 19:40:40 +00002341 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002342
Howard Hinnant1c936782011-06-03 19:40:40 +00002343 _LIBCPP_INLINE_VISIBILITY
2344 iterator begin() _NOEXCEPT
2345 {return __make_iter(0);}
2346 _LIBCPP_INLINE_VISIBILITY
2347 const_iterator begin() const _NOEXCEPT
2348 {return __make_iter(0);}
2349 _LIBCPP_INLINE_VISIBILITY
2350 iterator end() _NOEXCEPT
2351 {return __make_iter(__size_);}
2352 _LIBCPP_INLINE_VISIBILITY
2353 const_iterator end() const _NOEXCEPT
2354 {return __make_iter(__size_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002355
Howard Hinnant1c936782011-06-03 19:40:40 +00002356 _LIBCPP_INLINE_VISIBILITY
2357 reverse_iterator rbegin() _NOEXCEPT
2358 {return reverse_iterator(end());}
2359 _LIBCPP_INLINE_VISIBILITY
2360 const_reverse_iterator rbegin() const _NOEXCEPT
2361 {return const_reverse_iterator(end());}
2362 _LIBCPP_INLINE_VISIBILITY
2363 reverse_iterator rend() _NOEXCEPT
2364 {return reverse_iterator(begin());}
2365 _LIBCPP_INLINE_VISIBILITY
2366 const_reverse_iterator rend() const _NOEXCEPT
2367 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002368
Howard Hinnant1c936782011-06-03 19:40:40 +00002369 _LIBCPP_INLINE_VISIBILITY
2370 const_iterator cbegin() const _NOEXCEPT
2371 {return __make_iter(0);}
2372 _LIBCPP_INLINE_VISIBILITY
2373 const_iterator cend() const _NOEXCEPT
2374 {return __make_iter(__size_);}
2375 _LIBCPP_INLINE_VISIBILITY
2376 const_reverse_iterator crbegin() const _NOEXCEPT
2377 {return rbegin();}
2378 _LIBCPP_INLINE_VISIBILITY
2379 const_reverse_iterator crend() const _NOEXCEPT
2380 {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002381
2382 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2383 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2384 reference at(size_type __n);
2385 const_reference at(size_type __n) const;
2386
2387 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2388 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2389 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2390 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2391
2392 void push_back(const value_type& __x);
Marshall Clowc46bb8e2013-08-13 23:54:12 +00002393#if _LIBCPP_STD_VER > 11
2394 template <class... _Args>
Marshall Clowea52cc42017-01-24 23:09:12 +00002395#if _LIBCPP_STD_VER > 14
2396 _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args)
2397#else
2398 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
2399#endif
2400 {
Eric Fiselier34ba5b92016-07-21 03:20:17 +00002401 push_back ( value_type ( _VSTD::forward<_Args>(__args)... ));
Marshall Clowea52cc42017-01-24 23:09:12 +00002402#if _LIBCPP_STD_VER > 14
Eric Fiselier34ba5b92016-07-21 03:20:17 +00002403 return this->back();
Marshall Clowea52cc42017-01-24 23:09:12 +00002404#endif
Eric Fiselier34ba5b92016-07-21 03:20:17 +00002405 }
Marshall Clowc46bb8e2013-08-13 23:54:12 +00002406#endif
2407
Howard Hinnantc51e1022010-05-11 19:42:16 +00002408 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2409
Marshall Clowc46bb8e2013-08-13 23:54:12 +00002410#if _LIBCPP_STD_VER > 11
2411 template <class... _Args>
2412 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
2413 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
2414#endif
2415
Howard Hinnantc51e1022010-05-11 19:42:16 +00002416 iterator insert(const_iterator __position, const value_type& __x);
2417 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2418 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2419 template <class _InputIterator>
2420 typename enable_if
2421 <
2422 __is_input_iterator <_InputIterator>::value &&
2423 !__is_forward_iterator<_InputIterator>::value,
2424 iterator
2425 >::type
2426 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2427 template <class _ForwardIterator>
2428 typename enable_if
2429 <
2430 __is_forward_iterator<_ForwardIterator>::value,
2431 iterator
2432 >::type
2433 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
Eric Fiseliered9e9362017-04-16 02:40:45 +00002434
2435#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002436 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002437 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2438 {return insert(__position, __il.begin(), __il.end());}
Eric Fiseliered9e9362017-04-16 02:40:45 +00002439#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002440
Howard Hinnantcf823322010-12-17 14:46:43 +00002441 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002442 iterator erase(const_iterator __first, const_iterator __last);
2443
Howard Hinnant1c936782011-06-03 19:40:40 +00002444 _LIBCPP_INLINE_VISIBILITY
2445 void clear() _NOEXCEPT {__size_ = 0;}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002446
Howard Hinnant1c936782011-06-03 19:40:40 +00002447 void swap(vector&)
Marshall Clow8982dcd2015-07-13 20:04:56 +00002448#if _LIBCPP_STD_VER >= 14
2449 _NOEXCEPT;
2450#else
Eric Fiselier69c51982016-12-28 06:06:09 +00002451 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
Marshall Clow8982dcd2015-07-13 20:04:56 +00002452 __is_nothrow_swappable<allocator_type>::value);
2453#endif
Marshall Clow89eb3822016-04-07 14:20:31 +00002454 static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); }
Howard Hinnantc51e1022010-05-11 19:42:16 +00002455
2456 void resize(size_type __sz, value_type __x = false);
Howard Hinnant1c936782011-06-03 19:40:40 +00002457 void flip() _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002458
2459 bool __invariants() const;
2460
2461private:
Howard Hinnantcf823322010-12-17 14:46:43 +00002462 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
Marshall Clow3ff48e02018-05-22 16:20:28 +00002463 void __vallocate(size_type __n);
2464 void __vdeallocate() _NOEXCEPT;
Howard Hinnant1c936782011-06-03 19:40:40 +00002465 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantea382952013-08-14 18:00:20 +00002466 static size_type __align_it(size_type __new_size) _NOEXCEPT
Eric Fiselierb41db9a2018-10-01 01:59:37 +00002467 {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}
Howard Hinnantcf823322010-12-17 14:46:43 +00002468 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2469 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002470 template <class _ForwardIterator>
2471 typename enable_if
2472 <
2473 __is_forward_iterator<_ForwardIterator>::value,
2474 void
2475 >::type
2476 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2477 void __append(size_type __n, const_reference __x);
Howard Hinnant1c936782011-06-03 19:40:40 +00002478 _LIBCPP_INLINE_VISIBILITY
2479 reference __make_ref(size_type __pos) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002480 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
Howard Hinnant1c936782011-06-03 19:40:40 +00002481 _LIBCPP_INLINE_VISIBILITY
2482 const_reference __make_ref(size_type __pos) const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002483 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
Howard Hinnant1c936782011-06-03 19:40:40 +00002484 _LIBCPP_INLINE_VISIBILITY
2485 iterator __make_iter(size_type __pos) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002486 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
Howard Hinnant1c936782011-06-03 19:40:40 +00002487 _LIBCPP_INLINE_VISIBILITY
2488 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002489 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
Howard Hinnant1c936782011-06-03 19:40:40 +00002490 _LIBCPP_INLINE_VISIBILITY
2491 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
Howard Hinnant76053d72013-06-27 19:35:32 +00002492 {return begin() + (__p - cbegin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00002493
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002494 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002495 void __copy_assign_alloc(const vector& __v)
2496 {__copy_assign_alloc(__v, integral_constant<bool,
2497 __storage_traits::propagate_on_container_copy_assignment::value>());}
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002498 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002499 void __copy_assign_alloc(const vector& __c, true_type)
2500 {
2501 if (__alloc() != __c.__alloc())
Marshall Clow3ff48e02018-05-22 16:20:28 +00002502 __vdeallocate();
Howard Hinnantc51e1022010-05-11 19:42:16 +00002503 __alloc() = __c.__alloc();
2504 }
2505
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002506 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +00002507 void __copy_assign_alloc(const vector&, false_type)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002508 {}
2509
2510 void __move_assign(vector& __c, false_type);
Howard Hinnant1c936782011-06-03 19:40:40 +00002511 void __move_assign(vector& __c, true_type)
2512 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002513 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002514 void __move_assign_alloc(vector& __c)
Howard Hinnant1c936782011-06-03 19:40:40 +00002515 _NOEXCEPT_(
2516 !__storage_traits::propagate_on_container_move_assignment::value ||
2517 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002518 {__move_assign_alloc(__c, integral_constant<bool,
2519 __storage_traits::propagate_on_container_move_assignment::value>());}
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002520 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc2734962011-09-02 20:42:31 +00002521 void __move_assign_alloc(vector& __c, true_type)
Howard Hinnant1c936782011-06-03 19:40:40 +00002522 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002523 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002524 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002525 }
2526
Howard Hinnant1c265cd2010-09-23 18:58:28 +00002527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant28b24882011-12-01 20:21:04 +00002528 void __move_assign_alloc(vector&, false_type)
Howard Hinnant1c936782011-06-03 19:40:40 +00002529 _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002530 {}
2531
Howard Hinnant1c936782011-06-03 19:40:40 +00002532 size_t __hash_code() const _NOEXCEPT;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002533
2534 friend class __bit_reference<vector>;
2535 friend class __bit_const_reference<vector>;
2536 friend class __bit_iterator<vector, false>;
2537 friend class __bit_iterator<vector, true>;
Howard Hinnant4210a0f2012-08-17 17:10:18 +00002538 friend struct __bit_array<vector>;
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00002539 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002540};
2541
2542template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002543inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002544void
2545vector<bool, _Allocator>::__invalidate_all_iterators()
2546{
Howard Hinnantc51e1022010-05-11 19:42:16 +00002547}
2548
2549// Allocate space for __n objects
2550// throws length_error if __n > max_size()
2551// throws (probably bad_alloc) if memory run out
2552// Precondition: __begin_ == __end_ == __cap() == 0
2553// Precondition: __n > 0
2554// Postcondition: capacity() == __n
2555// Postcondition: size() == 0
2556template <class _Allocator>
2557void
Marshall Clow3ff48e02018-05-22 16:20:28 +00002558vector<bool, _Allocator>::__vallocate(size_type __n)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002559{
2560 if (__n > max_size())
2561 this->__throw_length_error();
2562 __n = __external_cap_to_internal(__n);
2563 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2564 this->__size_ = 0;
2565 this->__cap() = __n;
2566}
2567
2568template <class _Allocator>
2569void
Marshall Clow3ff48e02018-05-22 16:20:28 +00002570vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002571{
Howard Hinnant76053d72013-06-27 19:35:32 +00002572 if (this->__begin_ != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002573 {
2574 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2575 __invalidate_all_iterators();
Howard Hinnant76053d72013-06-27 19:35:32 +00002576 this->__begin_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002577 this->__size_ = this->__cap() = 0;
2578 }
2579}
2580
2581template <class _Allocator>
2582typename vector<bool, _Allocator>::size_type
Howard Hinnant1c936782011-06-03 19:40:40 +00002583vector<bool, _Allocator>::max_size() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00002584{
2585 size_type __amax = __storage_traits::max_size(__alloc());
2586 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2587 if (__nmax / __bits_per_word <= __amax)
2588 return __nmax;
2589 return __internal_cap_to_external(__amax);
2590}
2591
2592// Precondition: __new_size > capacity()
2593template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002594inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002595typename vector<bool, _Allocator>::size_type
2596vector<bool, _Allocator>::__recommend(size_type __new_size) const
2597{
2598 const size_type __ms = max_size();
2599 if (__new_size > __ms)
2600 this->__throw_length_error();
2601 const size_type __cap = capacity();
2602 if (__cap >= __ms / 2)
2603 return __ms;
Howard Hinnantea382952013-08-14 18:00:20 +00002604 return _VSTD::max(2*__cap, __align_it(__new_size));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002605}
2606
2607// Default constructs __n objects starting at __end_
2608// Precondition: __n > 0
2609// Precondition: size() + __n <= capacity()
2610// Postcondition: size() == size() + __n
2611template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002612inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002613void
2614vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2615{
2616 size_type __old_size = this->__size_;
2617 this->__size_ += __n;
Marshall Clow1893ec72018-10-23 20:07:45 +00002618 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2619 {
2620 if (this->__size_ <= __bits_per_word)
2621 this->__begin_[0] = __storage_type(0);
2622 else
2623 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2624 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002625 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002626}
2627
2628template <class _Allocator>
2629template <class _ForwardIterator>
2630typename enable_if
2631<
2632 __is_forward_iterator<_ForwardIterator>::value,
2633 void
2634>::type
2635vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2636{
2637 size_type __old_size = this->__size_;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002638 this->__size_ += _VSTD::distance(__first, __last);
Marshall Clow1893ec72018-10-23 20:07:45 +00002639 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2640 {
2641 if (this->__size_ <= __bits_per_word)
2642 this->__begin_[0] = __storage_type(0);
2643 else
2644 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2645 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002646 _VSTD::copy(__first, __last, __make_iter(__old_size));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002647}
2648
2649template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002650inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002651vector<bool, _Allocator>::vector()
Marshall Clowe546cbb2015-06-04 02:05:41 +00002652 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant76053d72013-06-27 19:35:32 +00002653 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002654 __size_(0),
2655 __cap_alloc_(0)
2656{
2657}
2658
2659template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002660inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002661vector<bool, _Allocator>::vector(const allocator_type& __a)
Marshall Clow8f282f42015-06-04 00:10:20 +00002662#if _LIBCPP_STD_VER <= 14
2663 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
2664#else
2665 _NOEXCEPT
2666#endif
Howard Hinnant76053d72013-06-27 19:35:32 +00002667 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002668 __size_(0),
2669 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2670{
2671}
2672
2673template <class _Allocator>
2674vector<bool, _Allocator>::vector(size_type __n)
Howard Hinnant76053d72013-06-27 19:35:32 +00002675 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002676 __size_(0),
2677 __cap_alloc_(0)
2678{
2679 if (__n > 0)
2680 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002681 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002682 __construct_at_end(__n, false);
2683 }
2684}
2685
Marshall Clowd3cbeaa2013-09-14 00:47:59 +00002686#if _LIBCPP_STD_VER > 11
2687template <class _Allocator>
2688vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2689 : __begin_(nullptr),
2690 __size_(0),
2691 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2692{
2693 if (__n > 0)
2694 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002695 __vallocate(__n);
Marshall Clowd3cbeaa2013-09-14 00:47:59 +00002696 __construct_at_end(__n, false);
2697 }
2698}
2699#endif
2700
Howard Hinnantc51e1022010-05-11 19:42:16 +00002701template <class _Allocator>
2702vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
Howard Hinnant76053d72013-06-27 19:35:32 +00002703 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002704 __size_(0),
2705 __cap_alloc_(0)
2706{
2707 if (__n > 0)
2708 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002709 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002710 __construct_at_end(__n, __x);
2711 }
2712}
2713
2714template <class _Allocator>
2715vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
Howard Hinnant76053d72013-06-27 19:35:32 +00002716 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002717 __size_(0),
2718 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2719{
2720 if (__n > 0)
2721 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002722 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002723 __construct_at_end(__n, __x);
2724 }
2725}
2726
2727template <class _Allocator>
2728template <class _InputIterator>
2729vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2730 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2731 !__is_forward_iterator<_InputIterator>::value>::type*)
Howard Hinnant76053d72013-06-27 19:35:32 +00002732 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002733 __size_(0),
2734 __cap_alloc_(0)
2735{
2736#ifndef _LIBCPP_NO_EXCEPTIONS
2737 try
2738 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002739#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002740 for (; __first != __last; ++__first)
2741 push_back(*__first);
2742#ifndef _LIBCPP_NO_EXCEPTIONS
2743 }
2744 catch (...)
2745 {
Howard Hinnant76053d72013-06-27 19:35:32 +00002746 if (__begin_ != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002747 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2748 __invalidate_all_iterators();
2749 throw;
2750 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002751#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002752}
2753
2754template <class _Allocator>
2755template <class _InputIterator>
2756vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2757 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2758 !__is_forward_iterator<_InputIterator>::value>::type*)
Howard Hinnant76053d72013-06-27 19:35:32 +00002759 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002760 __size_(0),
2761 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2762{
2763#ifndef _LIBCPP_NO_EXCEPTIONS
2764 try
2765 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002766#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002767 for (; __first != __last; ++__first)
2768 push_back(*__first);
2769#ifndef _LIBCPP_NO_EXCEPTIONS
2770 }
2771 catch (...)
2772 {
Howard Hinnant76053d72013-06-27 19:35:32 +00002773 if (__begin_ != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002774 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2775 __invalidate_all_iterators();
2776 throw;
2777 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00002778#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00002779}
2780
2781template <class _Allocator>
2782template <class _ForwardIterator>
2783vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2784 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
Howard Hinnant76053d72013-06-27 19:35:32 +00002785 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002786 __size_(0),
2787 __cap_alloc_(0)
2788{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002789 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002790 if (__n > 0)
2791 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002792 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002793 __construct_at_end(__first, __last);
2794 }
2795}
2796
2797template <class _Allocator>
2798template <class _ForwardIterator>
2799vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2800 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
Howard Hinnant76053d72013-06-27 19:35:32 +00002801 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002802 __size_(0),
2803 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2804{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002805 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantc51e1022010-05-11 19:42:16 +00002806 if (__n > 0)
2807 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002808 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002809 __construct_at_end(__first, __last);
2810 }
2811}
2812
Eric Fiseliered9e9362017-04-16 02:40:45 +00002813#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant33711792011-08-12 21:56:02 +00002814
Howard Hinnantc51e1022010-05-11 19:42:16 +00002815template <class _Allocator>
2816vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
Howard Hinnant76053d72013-06-27 19:35:32 +00002817 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002818 __size_(0),
2819 __cap_alloc_(0)
2820{
2821 size_type __n = static_cast<size_type>(__il.size());
2822 if (__n > 0)
2823 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002824 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002825 __construct_at_end(__il.begin(), __il.end());
2826 }
2827}
2828
2829template <class _Allocator>
2830vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
Howard Hinnant76053d72013-06-27 19:35:32 +00002831 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002832 __size_(0),
2833 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2834{
2835 size_type __n = static_cast<size_type>(__il.size());
2836 if (__n > 0)
2837 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002838 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002839 __construct_at_end(__il.begin(), __il.end());
2840 }
2841}
2842
Eric Fiseliered9e9362017-04-16 02:40:45 +00002843#endif // _LIBCPP_CXX03_LANG
Howard Hinnant33711792011-08-12 21:56:02 +00002844
Howard Hinnantc51e1022010-05-11 19:42:16 +00002845template <class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00002846vector<bool, _Allocator>::~vector()
2847{
Howard Hinnant76053d72013-06-27 19:35:32 +00002848 if (__begin_ != nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002849 __storage_traits::deallocate(__alloc(), __begin_, __cap());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002850 __invalidate_all_iterators();
Howard Hinnantc51e1022010-05-11 19:42:16 +00002851}
2852
2853template <class _Allocator>
2854vector<bool, _Allocator>::vector(const vector& __v)
Howard Hinnant76053d72013-06-27 19:35:32 +00002855 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002856 __size_(0),
2857 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2858{
2859 if (__v.size() > 0)
2860 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002861 __vallocate(__v.size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002862 __construct_at_end(__v.begin(), __v.end());
2863 }
2864}
2865
2866template <class _Allocator>
2867vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
Howard Hinnant76053d72013-06-27 19:35:32 +00002868 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002869 __size_(0),
2870 __cap_alloc_(0, __a)
2871{
2872 if (__v.size() > 0)
2873 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002874 __vallocate(__v.size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002875 __construct_at_end(__v.begin(), __v.end());
2876 }
2877}
2878
2879template <class _Allocator>
2880vector<bool, _Allocator>&
2881vector<bool, _Allocator>::operator=(const vector& __v)
2882{
2883 if (this != &__v)
2884 {
2885 __copy_assign_alloc(__v);
2886 if (__v.__size_)
2887 {
2888 if (__v.__size_ > capacity())
2889 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002890 __vdeallocate();
2891 __vallocate(__v.__size_);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002892 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002893 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002894 }
2895 __size_ = __v.__size_;
2896 }
2897 return *this;
2898}
2899
Eric Fiseliered9e9362017-04-16 02:40:45 +00002900#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant74279a52010-09-04 23:28:19 +00002901
Howard Hinnantc51e1022010-05-11 19:42:16 +00002902template <class _Allocator>
Eric Fiselier4f1534c2018-06-05 22:32:52 +00002903inline _LIBCPP_INLINE_VISIBILITY vector<bool, _Allocator>::vector(vector&& __v)
Marshall Clowe5108202015-07-14 14:46:32 +00002904#if _LIBCPP_STD_VER > 14
Eric Fiselier4f1534c2018-06-05 22:32:52 +00002905 _NOEXCEPT
Marshall Clowe5108202015-07-14 14:46:32 +00002906#else
Eric Fiselier4f1534c2018-06-05 22:32:52 +00002907 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Marshall Clowe5108202015-07-14 14:46:32 +00002908#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00002909 : __begin_(__v.__begin_),
2910 __size_(__v.__size_),
Eric Fiselier4f1534c2018-06-05 22:32:52 +00002911 __cap_alloc_(std::move(__v.__cap_alloc_)) {
Howard Hinnant76053d72013-06-27 19:35:32 +00002912 __v.__begin_ = nullptr;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002913 __v.__size_ = 0;
2914 __v.__cap() = 0;
2915}
2916
2917template <class _Allocator>
2918vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
Howard Hinnant76053d72013-06-27 19:35:32 +00002919 : __begin_(nullptr),
Howard Hinnantc51e1022010-05-11 19:42:16 +00002920 __size_(0),
2921 __cap_alloc_(0, __a)
2922{
2923 if (__a == allocator_type(__v.__alloc()))
2924 {
2925 this->__begin_ = __v.__begin_;
2926 this->__size_ = __v.__size_;
2927 this->__cap() = __v.__cap();
2928 __v.__begin_ = nullptr;
2929 __v.__cap() = __v.__size_ = 0;
2930 }
2931 else if (__v.size() > 0)
2932 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00002933 __vallocate(__v.size());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002934 __construct_at_end(__v.begin(), __v.end());
2935 }
2936}
2937
2938template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00002939inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002940vector<bool, _Allocator>&
2941vector<bool, _Allocator>::operator=(vector&& __v)
Marshall Clow2fe8a8d2015-08-18 18:57:00 +00002942 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002943{
2944 __move_assign(__v, integral_constant<bool,
2945 __storage_traits::propagate_on_container_move_assignment::value>());
Argyrios Kyrtzidisaf904652012-10-13 02:03:45 +00002946 return *this;
Howard Hinnantc51e1022010-05-11 19:42:16 +00002947}
2948
2949template <class _Allocator>
2950void
2951vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2952{
2953 if (__alloc() != __c.__alloc())
2954 assign(__c.begin(), __c.end());
2955 else
2956 __move_assign(__c, true_type());
2957}
2958
2959template <class _Allocator>
2960void
2961vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
Howard Hinnant1c936782011-06-03 19:40:40 +00002962 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002963{
Marshall Clow3ff48e02018-05-22 16:20:28 +00002964 __vdeallocate();
Marshall Clowb4871fa2014-07-21 15:15:15 +00002965 __move_assign_alloc(__c);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002966 this->__begin_ = __c.__begin_;
2967 this->__size_ = __c.__size_;
2968 this->__cap() = __c.__cap();
Howard Hinnantc51e1022010-05-11 19:42:16 +00002969 __c.__begin_ = nullptr;
2970 __c.__cap() = __c.__size_ = 0;
2971}
Howard Hinnant74279a52010-09-04 23:28:19 +00002972
Eric Fiseliered9e9362017-04-16 02:40:45 +00002973#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00002974
2975template <class _Allocator>
2976void
2977vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2978{
2979 __size_ = 0;
2980 if (__n > 0)
2981 {
2982 size_type __c = capacity();
2983 if (__n <= __c)
2984 __size_ = __n;
2985 else
2986 {
2987 vector __v(__alloc());
2988 __v.reserve(__recommend(__n));
2989 __v.__size_ = __n;
2990 swap(__v);
2991 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002992 _VSTD::fill_n(begin(), __n, __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002993 }
Eric Fiselier69c51982016-12-28 06:06:09 +00002994 __invalidate_all_iterators();
Howard Hinnantc51e1022010-05-11 19:42:16 +00002995}
2996
2997template <class _Allocator>
2998template <class _InputIterator>
2999typename enable_if
3000<
3001 __is_input_iterator<_InputIterator>::value &&
3002 !__is_forward_iterator<_InputIterator>::value,
3003 void
3004>::type
3005vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
3006{
3007 clear();
3008 for (; __first != __last; ++__first)
3009 push_back(*__first);
3010}
3011
3012template <class _Allocator>
3013template <class _ForwardIterator>
3014typename enable_if
3015<
3016 __is_forward_iterator<_ForwardIterator>::value,
3017 void
3018>::type
3019vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
3020{
3021 clear();
Eric Fiselier6003c772016-12-23 23:37:52 +00003022 difference_type __ns = _VSTD::distance(__first, __last);
3023 _LIBCPP_ASSERT(__ns >= 0, "invalid range specified");
3024 const size_t __n = static_cast<size_type>(__ns);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003025 if (__n)
3026 {
3027 if (__n > capacity())
3028 {
Marshall Clow3ff48e02018-05-22 16:20:28 +00003029 __vdeallocate();
3030 __vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003031 }
3032 __construct_at_end(__first, __last);
3033 }
3034}
3035
3036template <class _Allocator>
3037void
3038vector<bool, _Allocator>::reserve(size_type __n)
3039{
3040 if (__n > capacity())
3041 {
3042 vector __v(this->__alloc());
Marshall Clow3ff48e02018-05-22 16:20:28 +00003043 __v.__vallocate(__n);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003044 __v.__construct_at_end(this->begin(), this->end());
3045 swap(__v);
3046 __invalidate_all_iterators();
3047 }
3048}
3049
3050template <class _Allocator>
3051void
Howard Hinnant1c936782011-06-03 19:40:40 +00003052vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00003053{
3054 if (__external_cap_to_internal(size()) > __cap())
3055 {
3056#ifndef _LIBCPP_NO_EXCEPTIONS
3057 try
3058 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003059#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00003060 vector(*this, allocator_type(__alloc())).swap(*this);
3061#ifndef _LIBCPP_NO_EXCEPTIONS
3062 }
3063 catch (...)
3064 {
3065 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003066#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00003067 }
3068}
3069
3070template <class _Allocator>
3071typename vector<bool, _Allocator>::reference
3072vector<bool, _Allocator>::at(size_type __n)
3073{
3074 if (__n >= size())
3075 this->__throw_out_of_range();
3076 return (*this)[__n];
3077}
3078
3079template <class _Allocator>
3080typename vector<bool, _Allocator>::const_reference
3081vector<bool, _Allocator>::at(size_type __n) const
3082{
3083 if (__n >= size())
3084 this->__throw_out_of_range();
3085 return (*this)[__n];
3086}
3087
3088template <class _Allocator>
3089void
3090vector<bool, _Allocator>::push_back(const value_type& __x)
3091{
3092 if (this->__size_ == this->capacity())
3093 reserve(__recommend(this->__size_ + 1));
3094 ++this->__size_;
3095 back() = __x;
3096}
3097
3098template <class _Allocator>
3099typename vector<bool, _Allocator>::iterator
3100vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
3101{
3102 iterator __r;
3103 if (size() < capacity())
3104 {
3105 const_iterator __old_end = end();
3106 ++__size_;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003107 _VSTD::copy_backward(__position, __old_end, end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003108 __r = __const_iterator_cast(__position);
3109 }
3110 else
3111 {
3112 vector __v(__alloc());
3113 __v.reserve(__recommend(__size_ + 1));
3114 __v.__size_ = __size_ + 1;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003115 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3116 _VSTD::copy_backward(__position, cend(), __v.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003117 swap(__v);
3118 }
3119 *__r = __x;
3120 return __r;
3121}
3122
3123template <class _Allocator>
3124typename vector<bool, _Allocator>::iterator
3125vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
3126{
3127 iterator __r;
3128 size_type __c = capacity();
3129 if (__n <= __c && size() <= __c - __n)
3130 {
3131 const_iterator __old_end = end();
3132 __size_ += __n;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003133 _VSTD::copy_backward(__position, __old_end, end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003134 __r = __const_iterator_cast(__position);
3135 }
3136 else
3137 {
3138 vector __v(__alloc());
3139 __v.reserve(__recommend(__size_ + __n));
3140 __v.__size_ = __size_ + __n;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003141 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3142 _VSTD::copy_backward(__position, cend(), __v.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003143 swap(__v);
3144 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003145 _VSTD::fill_n(__r, __n, __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003146 return __r;
3147}
3148
3149template <class _Allocator>
3150template <class _InputIterator>
3151typename enable_if
3152<
3153 __is_input_iterator <_InputIterator>::value &&
3154 !__is_forward_iterator<_InputIterator>::value,
3155 typename vector<bool, _Allocator>::iterator
3156>::type
3157vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
3158{
3159 difference_type __off = __position - begin();
3160 iterator __p = __const_iterator_cast(__position);
3161 iterator __old_end = end();
3162 for (; size() != capacity() && __first != __last; ++__first)
3163 {
3164 ++this->__size_;
3165 back() = *__first;
3166 }
3167 vector __v(__alloc());
3168 if (__first != __last)
3169 {
3170#ifndef _LIBCPP_NO_EXCEPTIONS
3171 try
3172 {
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003173#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00003174 __v.assign(__first, __last);
3175 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
3176 difference_type __old_p = __p - begin();
3177 reserve(__recommend(size() + __v.size()));
3178 __p = begin() + __old_p;
3179 __old_end = begin() + __old_size;
3180#ifndef _LIBCPP_NO_EXCEPTIONS
3181 }
3182 catch (...)
3183 {
3184 erase(__old_end, end());
3185 throw;
3186 }
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003187#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00003188 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003189 __p = _VSTD::rotate(__p, __old_end, end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003190 insert(__p, __v.begin(), __v.end());
3191 return begin() + __off;
3192}
3193
3194template <class _Allocator>
3195template <class _ForwardIterator>
3196typename enable_if
3197<
3198 __is_forward_iterator<_ForwardIterator>::value,
3199 typename vector<bool, _Allocator>::iterator
3200>::type
3201vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3202{
Eric Fiselier654dd332016-12-11 05:31:00 +00003203 const difference_type __n_signed = _VSTD::distance(__first, __last);
3204 _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified");
3205 const size_type __n = static_cast<size_type>(__n_signed);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003206 iterator __r;
3207 size_type __c = capacity();
3208 if (__n <= __c && size() <= __c - __n)
3209 {
3210 const_iterator __old_end = end();
3211 __size_ += __n;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003212 _VSTD::copy_backward(__position, __old_end, end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003213 __r = __const_iterator_cast(__position);
3214 }
3215 else
3216 {
3217 vector __v(__alloc());
3218 __v.reserve(__recommend(__size_ + __n));
3219 __v.__size_ = __size_ + __n;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003220 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3221 _VSTD::copy_backward(__position, cend(), __v.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003222 swap(__v);
3223 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003224 _VSTD::copy(__first, __last, __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003225 return __r;
3226}
3227
3228template <class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003229inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003230typename vector<bool, _Allocator>::iterator
3231vector<bool, _Allocator>::erase(const_iterator __position)
3232{
3233 iterator __r = __const_iterator_cast(__position);
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003234 _VSTD::copy(__position + 1, this->cend(), __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003235 --__size_;
3236 return __r;
3237}
3238
3239template <class _Allocator>
3240typename vector<bool, _Allocator>::iterator
3241vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3242{
3243 iterator __r = __const_iterator_cast(__first);
3244 difference_type __d = __last - __first;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003245 _VSTD::copy(__last, this->cend(), __r);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003246 __size_ -= __d;
3247 return __r;
3248}
3249
3250template <class _Allocator>
3251void
3252vector<bool, _Allocator>::swap(vector& __x)
Marshall Clow8982dcd2015-07-13 20:04:56 +00003253#if _LIBCPP_STD_VER >= 14
3254 _NOEXCEPT
3255#else
Eric Fiselier69c51982016-12-28 06:06:09 +00003256 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
Marshall Clow8982dcd2015-07-13 20:04:56 +00003257 __is_nothrow_swappable<allocator_type>::value)
3258#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00003259{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003260 _VSTD::swap(this->__begin_, __x.__begin_);
3261 _VSTD::swap(this->__size_, __x.__size_);
3262 _VSTD::swap(this->__cap(), __x.__cap());
Eric Fiseliered9e9362017-04-16 02:40:45 +00003263 __swap_allocator(this->__alloc(), __x.__alloc(),
Marshall Clow8982dcd2015-07-13 20:04:56 +00003264 integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003265}
3266
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003267template <class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00003268void
3269vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3270{
3271 size_type __cs = size();
3272 if (__cs < __sz)
3273 {
3274 iterator __r;
3275 size_type __c = capacity();
3276 size_type __n = __sz - __cs;
3277 if (__n <= __c && __cs <= __c - __n)
3278 {
3279 __r = end();
3280 __size_ += __n;
3281 }
3282 else
3283 {
3284 vector __v(__alloc());
3285 __v.reserve(__recommend(__size_ + __n));
3286 __v.__size_ = __size_ + __n;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003287 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003288 swap(__v);
3289 }
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003290 _VSTD::fill_n(__r, __n, __x);
Howard Hinnantc51e1022010-05-11 19:42:16 +00003291 }
3292 else
3293 __size_ = __sz;
3294}
3295
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003296template <class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00003297void
Howard Hinnant1c936782011-06-03 19:40:40 +00003298vector<bool, _Allocator>::flip() _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00003299{
3300 // do middle whole words
3301 size_type __n = __size_;
3302 __storage_pointer __p = __begin_;
3303 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3304 *__p = ~*__p;
3305 // do last partial word
3306 if (__n > 0)
3307 {
3308 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3309 __storage_type __b = *__p & __m;
3310 *__p &= ~__m;
3311 *__p |= ~__b & __m;
3312 }
3313}
3314
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003315template <class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00003316bool
3317vector<bool, _Allocator>::__invariants() const
3318{
Howard Hinnant76053d72013-06-27 19:35:32 +00003319 if (this->__begin_ == nullptr)
Howard Hinnantc51e1022010-05-11 19:42:16 +00003320 {
3321 if (this->__size_ != 0 || this->__cap() != 0)
3322 return false;
3323 }
3324 else
3325 {
3326 if (this->__cap() == 0)
3327 return false;
3328 if (this->__size_ > this->capacity())
3329 return false;
3330 }
3331 return true;
3332}
3333
Howard Hinnant3b6579a2010-08-22 00:02:43 +00003334template <class _Allocator>
Howard Hinnantc51e1022010-05-11 19:42:16 +00003335size_t
Howard Hinnant1c936782011-06-03 19:40:40 +00003336vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00003337{
3338 size_t __h = 0;
3339 // do middle whole words
3340 size_type __n = __size_;
3341 __storage_pointer __p = __begin_;
3342 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3343 __h ^= *__p;
3344 // do last partial word
3345 if (__n > 0)
3346 {
3347 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3348 __h ^= *__p & __m;
3349 }
3350 return __h;
3351}
3352
3353template <class _Allocator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00003354struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
Howard Hinnantc51e1022010-05-11 19:42:16 +00003355 : public unary_function<vector<bool, _Allocator>, size_t>
3356{
Howard Hinnant1c265cd2010-09-23 18:58:28 +00003357 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c936782011-06-03 19:40:40 +00003358 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +00003359 {return __vec.__hash_code();}
3360};
3361
3362template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003363inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003364bool
3365operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3366{
3367 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003368 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003369}
3370
3371template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003372inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003373bool
3374operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3375{
3376 return !(__x == __y);
3377}
3378
3379template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003380inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003381bool
3382operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3383{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00003384 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00003385}
3386
3387template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003388inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003389bool
3390operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3391{
3392 return __y < __x;
3393}
3394
3395template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003396inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003397bool
3398operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3399{
3400 return !(__x < __y);
3401}
3402
3403template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003404inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003405bool
3406operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3407{
3408 return !(__y < __x);
3409}
3410
3411template <class _Tp, class _Allocator>
Howard Hinnantb8a8ca22013-10-04 22:09:00 +00003412inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00003413void
3414swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
Howard Hinnant1c936782011-06-03 19:40:40 +00003415 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00003416{
3417 __x.swap(__y);
3418}
3419
Marshall Clow29b53f22018-12-14 18:49:35 +00003420#if _LIBCPP_STD_VER > 17
3421template <class _Tp, class _Allocator, class _Up>
3422inline _LIBCPP_INLINE_VISIBILITY
3423void erase(vector<_Tp, _Allocator>& __c, const _Up& __v)
3424{ __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); }
3425
3426template <class _Tp, class _Allocator, class _Predicate>
3427inline _LIBCPP_INLINE_VISIBILITY
3428void erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred)
3429{ __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); }
3430#endif
3431
Howard Hinnantc51e1022010-05-11 19:42:16 +00003432_LIBCPP_END_NAMESPACE_STD
3433
Eric Fiselierf4433a32017-05-31 22:07:49 +00003434_LIBCPP_POP_MACROS
3435
Howard Hinnantc51e1022010-05-11 19:42:16 +00003436#endif // _LIBCPP_VECTOR