blob: 48e970a2f401dbb2f7892f7ccc81a895fcfbe0f8 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===------------------------------ vector --------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_VECTOR
12#define _LIBCPP_VECTOR
13
14/*
15 vector synopsis
16
17namespace std
18{
19
Howard Hinnant324bb032010-08-22 00:02:43 +000020template <class T, class Allocator = allocator<T> >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000021class vector
Howard Hinnant324bb032010-08-22 00:02:43 +000022{
23public:
24 typedef T value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000025 typedef Allocator allocator_type;
26 typedef typename allocator_type::reference reference;
27 typedef typename allocator_type::const_reference const_reference;
28 typedef implementation-defined iterator;
29 typedef implementation-defined const_iterator;
30 typedef typename allocator_type::size_type size_type;
31 typedef typename allocator_type::difference_type difference_type;
32 typedef typename allocator_type::pointer pointer;
33 typedef typename allocator_type::const_pointer const_pointer;
34 typedef std::reverse_iterator<iterator> reverse_iterator;
35 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
36
Howard Hinnantd1d27a42011-06-03 19:40:40 +000037 vector()
38 noexcept(is_nothrow_default_constructible<allocator_type>::value);
39 explicit vector(const allocator_type&);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000040 explicit vector(size_type n);
Marshall Clowa49a2c92013-09-14 00:47:59 +000041 explicit vector(size_type n, const allocator_type&); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000042 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
43 template <class InputIterator>
44 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
45 vector(const vector& x);
Howard Hinnantd1d27a42011-06-03 19:40:40 +000046 vector(vector&& x)
47 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000048 vector(initializer_list<value_type> il);
49 vector(initializer_list<value_type> il, const allocator_type& a);
50 ~vector();
51 vector& operator=(const vector& x);
Howard Hinnantd1d27a42011-06-03 19:40:40 +000052 vector& operator=(vector&& x)
53 noexcept(
54 allocator_type::propagate_on_container_move_assignment::value &&
55 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000056 vector& operator=(initializer_list<value_type> il);
57 template <class InputIterator>
58 void assign(InputIterator first, InputIterator last);
59 void assign(size_type n, const value_type& u);
60 void assign(initializer_list<value_type> il);
61
Howard Hinnantd1d27a42011-06-03 19:40:40 +000062 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000063
Howard Hinnantd1d27a42011-06-03 19:40:40 +000064 iterator begin() noexcept;
65 const_iterator begin() const noexcept;
66 iterator end() noexcept;
67 const_iterator end() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000068
Howard Hinnantd1d27a42011-06-03 19:40:40 +000069 reverse_iterator rbegin() noexcept;
70 const_reverse_iterator rbegin() const noexcept;
71 reverse_iterator rend() noexcept;
72 const_reverse_iterator rend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000073
Howard Hinnantd1d27a42011-06-03 19:40:40 +000074 const_iterator cbegin() const noexcept;
75 const_iterator cend() const noexcept;
76 const_reverse_iterator crbegin() const noexcept;
77 const_reverse_iterator crend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000078
Howard Hinnantd1d27a42011-06-03 19:40:40 +000079 size_type size() const noexcept;
80 size_type max_size() const noexcept;
81 size_type capacity() const noexcept;
82 bool empty() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000083 void reserve(size_type n);
Howard Hinnantd1d27a42011-06-03 19:40:40 +000084 void shrink_to_fit() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000085
86 reference operator[](size_type n);
87 const_reference operator[](size_type n) const;
88 reference at(size_type n);
89 const_reference at(size_type n) const;
90
91 reference front();
92 const_reference front() const;
93 reference back();
94 const_reference back() const;
95
Howard Hinnantd1d27a42011-06-03 19:40:40 +000096 value_type* data() noexcept;
97 const value_type* data() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000098
99 void push_back(const value_type& x);
100 void push_back(value_type&& x);
101 template <class... Args>
102 void emplace_back(Args&&... args);
103 void pop_back();
104
105 template <class... Args> iterator emplace(const_iterator position, Args&&... args);
106 iterator insert(const_iterator position, const value_type& x);
107 iterator insert(const_iterator position, value_type&& x);
108 iterator insert(const_iterator position, size_type n, const value_type& x);
109 template <class InputIterator>
110 iterator insert(const_iterator position, InputIterator first, InputIterator last);
111 iterator insert(const_iterator position, initializer_list<value_type> il);
112
113 iterator erase(const_iterator position);
114 iterator erase(const_iterator first, const_iterator last);
115
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000116 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000117
118 void resize(size_type sz);
119 void resize(size_type sz, const value_type& c);
120
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000121 void swap(vector&)
122 noexcept(!allocator_type::propagate_on_container_swap::value ||
123 __is_nothrow_swappable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000124
125 bool __invariants() const;
Howard Hinnant324bb032010-08-22 00:02:43 +0000126};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000127
Howard Hinnant324bb032010-08-22 00:02:43 +0000128template <class Allocator = allocator<T> >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000129class vector<bool, Allocator>
Howard Hinnant324bb032010-08-22 00:02:43 +0000130{
131public:
132 typedef bool value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000133 typedef Allocator allocator_type;
134 typedef implementation-defined iterator;
135 typedef implementation-defined const_iterator;
136 typedef typename allocator_type::size_type size_type;
137 typedef typename allocator_type::difference_type difference_type;
138 typedef iterator pointer;
139 typedef const_iterator const_pointer;
140 typedef std::reverse_iterator<iterator> reverse_iterator;
141 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
142
143 class reference
144 {
145 public:
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000146 reference(const reference&) noexcept;
147 operator bool() const noexcept;
148 reference& operator=(const bool x) noexcept;
149 reference& operator=(const reference& x) noexcept;
150 iterator operator&() const noexcept;
151 void flip() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000152 };
153
154 class const_reference
155 {
156 public:
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000157 const_reference(const reference&) noexcept;
158 operator bool() const noexcept;
159 const_iterator operator&() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000160 };
161
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000162 vector()
163 noexcept(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnant9cbee432011-09-02 20:42:31 +0000164 explicit vector(const allocator_type&);
Marshall Clowa49a2c92013-09-14 00:47:59 +0000165 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
166 vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000167 template <class InputIterator>
168 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
169 vector(const vector& x);
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000170 vector(vector&& x)
171 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000172 vector(initializer_list<value_type> il);
173 vector(initializer_list<value_type> il, const allocator_type& a);
174 ~vector();
175 vector& operator=(const vector& x);
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000176 vector& operator=(vector&& x)
177 noexcept(
178 allocator_type::propagate_on_container_move_assignment::value &&
179 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000180 vector& operator=(initializer_list<value_type> il);
181 template <class InputIterator>
182 void assign(InputIterator first, InputIterator last);
183 void assign(size_type n, const value_type& u);
184 void assign(initializer_list<value_type> il);
185
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000186 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000187
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000188 iterator begin() noexcept;
189 const_iterator begin() const noexcept;
190 iterator end() noexcept;
191 const_iterator end() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000192
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000193 reverse_iterator rbegin() noexcept;
194 const_reverse_iterator rbegin() const noexcept;
195 reverse_iterator rend() noexcept;
196 const_reverse_iterator rend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000197
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000198 const_iterator cbegin() const noexcept;
199 const_iterator cend() const noexcept;
200 const_reverse_iterator crbegin() const noexcept;
201 const_reverse_iterator crend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000202
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000203 size_type size() const noexcept;
204 size_type max_size() const noexcept;
205 size_type capacity() const noexcept;
206 bool empty() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000207 void reserve(size_type n);
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000208 void shrink_to_fit() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000209
210 reference operator[](size_type n);
211 const_reference operator[](size_type n) const;
212 reference at(size_type n);
213 const_reference at(size_type n) const;
214
215 reference front();
216 const_reference front() const;
217 reference back();
218 const_reference back() const;
219
220 void push_back(const value_type& x);
Marshall Clow198a2a52013-08-13 23:54:12 +0000221 template <class... Args> void emplace_back(Args&&... args); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000222 void pop_back();
223
Marshall Clow198a2a52013-08-13 23:54:12 +0000224 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000225 iterator insert(const_iterator position, const value_type& x);
226 iterator insert(const_iterator position, size_type n, const value_type& x);
227 template <class InputIterator>
228 iterator insert(const_iterator position, InputIterator first, InputIterator last);
229 iterator insert(const_iterator position, initializer_list<value_type> il);
230
231 iterator erase(const_iterator position);
232 iterator erase(const_iterator first, const_iterator last);
233
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000234 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
236 void resize(size_type sz);
237 void resize(size_type sz, value_type x);
238
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000239 void swap(vector&)
240 noexcept(!allocator_type::propagate_on_container_swap::value ||
241 __is_nothrow_swappable<allocator_type>::value);
242 void flip() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000243
244 bool __invariants() const;
Howard Hinnant324bb032010-08-22 00:02:43 +0000245};
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000246
247template <class Allocator> struct hash<std::vector<bool, Allocator>>;
248
249template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
250template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
251template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
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);
255
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000256template <class T, class Allocator>
257void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
258 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000259
260} // std
261
262*/
263
264#include <__config>
265#include <__bit_reference>
266#include <type_traits>
267#include <climits>
268#include <limits>
269#include <initializer_list>
270#include <memory>
271#include <stdexcept>
272#include <algorithm>
273#include <cstring>
274#include <__split_buffer>
275#include <__functional_base>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000276
Howard Hinnant66c6f972011-11-29 16:45:27 +0000277#include <__undef_min_max>
278
Eric Fiselierb9536102014-08-10 23:53:08 +0000279#include <__debug>
Howard Hinnant8b00e6c2013-08-02 00:26:35 +0000280
Howard Hinnant08e17472011-10-17 20:05:10 +0000281#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000282#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000283#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000284
285_LIBCPP_BEGIN_NAMESPACE_STD
286
287template <bool>
288class __vector_base_common
289{
290protected:
291 _LIBCPP_ALWAYS_INLINE __vector_base_common() {}
292 void __throw_length_error() const;
293 void __throw_out_of_range() const;
294};
295
296template <bool __b>
297void
298__vector_base_common<__b>::__throw_length_error() const
299{
300#ifndef _LIBCPP_NO_EXCEPTIONS
301 throw length_error("vector");
302#else
303 assert(!"vector length_error");
304#endif
305}
306
307template <bool __b>
308void
309__vector_base_common<__b>::__throw_out_of_range() const
310{
311#ifndef _LIBCPP_NO_EXCEPTIONS
312 throw out_of_range("vector");
313#else
314 assert(!"vector out_of_range");
315#endif
316}
317
Howard Hinnante9df0a52013-08-01 18:17:34 +0000318#ifdef _LIBCPP_MSVC
Howard Hinnant78b68282011-10-22 20:59:45 +0000319#pragma warning( push )
320#pragma warning( disable: 4231 )
Howard Hinnante9df0a52013-08-01 18:17:34 +0000321#endif // _LIBCPP_MSVC
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000322_LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS __vector_base_common<true>)
Howard Hinnante9df0a52013-08-01 18:17:34 +0000323#ifdef _LIBCPP_MSVC
Howard Hinnant78b68282011-10-22 20:59:45 +0000324#pragma warning( pop )
Howard Hinnante9df0a52013-08-01 18:17:34 +0000325#endif // _LIBCPP_MSVC
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000326
327template <class _Tp, class _Allocator>
328class __vector_base
329 : protected __vector_base_common<true>
330{
331protected:
Howard Hinnant324bb032010-08-22 00:02:43 +0000332 typedef _Tp value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000333 typedef _Allocator allocator_type;
334 typedef allocator_traits<allocator_type> __alloc_traits;
335 typedef value_type& reference;
336 typedef const value_type& const_reference;
337 typedef typename __alloc_traits::size_type size_type;
338 typedef typename __alloc_traits::difference_type difference_type;
339 typedef typename __alloc_traits::pointer pointer;
340 typedef typename __alloc_traits::const_pointer const_pointer;
341 typedef pointer iterator;
342 typedef const_pointer const_iterator;
343
344 pointer __begin_;
345 pointer __end_;
346 __compressed_pair<pointer, allocator_type> __end_cap_;
347
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000348 _LIBCPP_INLINE_VISIBILITY
349 allocator_type& __alloc() _NOEXCEPT
350 {return __end_cap_.second();}
351 _LIBCPP_INLINE_VISIBILITY
352 const allocator_type& __alloc() const _NOEXCEPT
353 {return __end_cap_.second();}
354 _LIBCPP_INLINE_VISIBILITY
355 pointer& __end_cap() _NOEXCEPT
356 {return __end_cap_.first();}
357 _LIBCPP_INLINE_VISIBILITY
358 const pointer& __end_cap() const _NOEXCEPT
359 {return __end_cap_.first();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000360
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000361 _LIBCPP_INLINE_VISIBILITY
362 __vector_base()
363 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000364 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000365 ~__vector_base();
366
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000367 _LIBCPP_INLINE_VISIBILITY
368 void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
369 _LIBCPP_INLINE_VISIBILITY
370 size_type capacity() const _NOEXCEPT
371 {return static_cast<size_type>(__end_cap() - __begin_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000372
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000373 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000374 void __destruct_at_end(pointer __new_last) _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000375
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000376 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000377 void __copy_assign_alloc(const __vector_base& __c)
378 {__copy_assign_alloc(__c, integral_constant<bool,
379 __alloc_traits::propagate_on_container_copy_assignment::value>());}
380
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000381 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000382 void __move_assign_alloc(__vector_base& __c)
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000383 _NOEXCEPT_(
384 !__alloc_traits::propagate_on_container_move_assignment::value ||
385 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000386 {__move_assign_alloc(__c, integral_constant<bool,
387 __alloc_traits::propagate_on_container_move_assignment::value>());}
388
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000390 static void __swap_alloc(allocator_type& __x, allocator_type& __y)
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000391 _NOEXCEPT_(
392 !__alloc_traits::propagate_on_container_swap::value ||
393 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000394 {__swap_alloc(__x, __y, integral_constant<bool,
395 __alloc_traits::propagate_on_container_swap::value>());}
396private:
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000397 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000398 void __copy_assign_alloc(const __vector_base& __c, true_type)
399 {
400 if (__alloc() != __c.__alloc())
401 {
402 clear();
403 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
404 __begin_ = __end_ = __end_cap() = nullptr;
405 }
406 __alloc() = __c.__alloc();
407 }
408
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000409 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +0000410 void __copy_assign_alloc(const __vector_base&, false_type)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000411 {}
412
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000413 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant9cbee432011-09-02 20:42:31 +0000414 void __move_assign_alloc(__vector_base& __c, true_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000415 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000416 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000417 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000418 }
419
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000420 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +0000421 void __move_assign_alloc(__vector_base&, false_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000422 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000423 {}
424
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000425 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000426 static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000427 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000428 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000429 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000430 swap(__x, __y);
431 }
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000432 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +0000433 static void __swap_alloc(allocator_type&, allocator_type&, false_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000434 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000435 {}
436};
437
438template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +0000439inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000440void
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000441__vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000442{
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +0000443 while (__new_last != __end_)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000444 __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000445}
446
447template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +0000448inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000449__vector_base<_Tp, _Allocator>::__vector_base()
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000450 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000451 : __begin_(nullptr),
452 __end_(nullptr),
453 __end_cap_(nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000454{
455}
456
457template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +0000458inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000459__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000460 : __begin_(nullptr),
461 __end_(nullptr),
462 __end_cap_(nullptr, __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000463{
464}
465
466template <class _Tp, class _Allocator>
467__vector_base<_Tp, _Allocator>::~__vector_base()
468{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000469 if (__begin_ != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000470 {
471 clear();
472 __alloc_traits::deallocate(__alloc(), __begin_, capacity());
473 }
474}
475
476template <class _Tp, class _Allocator = allocator<_Tp> >
Howard Hinnant0f678bd2013-08-12 18:38:34 +0000477class _LIBCPP_TYPE_VIS_ONLY vector
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000478 : private __vector_base<_Tp, _Allocator>
479{
480private:
481 typedef __vector_base<_Tp, _Allocator> __base;
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000482 typedef allocator<_Tp> __default_allocator_type;
Howard Hinnant324bb032010-08-22 00:02:43 +0000483public:
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000484 typedef vector __self;
Howard Hinnant324bb032010-08-22 00:02:43 +0000485 typedef _Tp value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000486 typedef _Allocator allocator_type;
487 typedef typename __base::__alloc_traits __alloc_traits;
488 typedef typename __base::reference reference;
489 typedef typename __base::const_reference const_reference;
490 typedef typename __base::size_type size_type;
491 typedef typename __base::difference_type difference_type;
492 typedef typename __base::pointer pointer;
493 typedef typename __base::const_pointer const_pointer;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000494 typedef __wrap_iter<pointer> iterator;
495 typedef __wrap_iter<const_pointer> const_iterator;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000496 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
497 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000498
Howard Hinnant02d5e182013-03-26 19:04:56 +0000499 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
500 "Allocator::value_type must be same type as value_type");
501
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000502 _LIBCPP_INLINE_VISIBILITY
503 vector()
504 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant7a563db2011-09-14 18:33:51 +0000505 {
Howard Hinnantabe26282011-09-16 17:29:17 +0000506#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +0000507 __get_db()->__insert_c(this);
508#endif
509 }
510 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
511 : __base(__a)
512 {
Howard Hinnantabe26282011-09-16 17:29:17 +0000513#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +0000514 __get_db()->__insert_c(this);
515#endif
516 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000517 explicit vector(size_type __n);
Marshall Clowa49a2c92013-09-14 00:47:59 +0000518#if _LIBCPP_STD_VER > 11
519 explicit vector(size_type __n, const allocator_type& __a);
520#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000521 vector(size_type __n, const_reference __x);
522 vector(size_type __n, const_reference __x, const allocator_type& __a);
523 template <class _InputIterator>
Howard Hinnantde589f22013-09-21 21:13:54 +0000524 vector(_InputIterator __first,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +0000526 !__is_forward_iterator<_InputIterator>::value &&
527 is_constructible<
528 value_type,
Howard Hinnantde589f22013-09-21 21:13:54 +0000529 typename iterator_traits<_InputIterator>::reference>::value,
530 _InputIterator>::type __last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000531 template <class _InputIterator>
532 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
533 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +0000534 !__is_forward_iterator<_InputIterator>::value &&
535 is_constructible<
536 value_type,
537 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000538 template <class _ForwardIterator>
Howard Hinnantde589f22013-09-21 21:13:54 +0000539 vector(_ForwardIterator __first,
Howard Hinnant742fecb2013-03-28 17:44:32 +0000540 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
541 is_constructible<
542 value_type,
Howard Hinnantde589f22013-09-21 21:13:54 +0000543 typename iterator_traits<_ForwardIterator>::reference>::value,
544 _ForwardIterator>::type __last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000545 template <class _ForwardIterator>
546 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
Howard Hinnant742fecb2013-03-28 17:44:32 +0000547 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
548 is_constructible<
549 value_type,
550 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
Howard Hinnante3e32912011-08-12 21:56:02 +0000551#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000552 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000553 vector(initializer_list<value_type> __il);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000555 vector(initializer_list<value_type> __il, const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000556#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantabe26282011-09-16 17:29:17 +0000557#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000558 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7a563db2011-09-14 18:33:51 +0000559 ~vector()
560 {
561 __get_db()->__erase_c(this);
562 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000563#endif
564
565 vector(const vector& __x);
566 vector(const vector& __x, const allocator_type& __a);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000568 vector& operator=(const vector& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000569#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000570 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000571 vector(vector&& __x)
572 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000574 vector(vector&& __x, const allocator_type& __a);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000576 vector& operator=(vector&& __x)
577 _NOEXCEPT_(
578 __alloc_traits::propagate_on_container_move_assignment::value &&
579 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000580#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000581#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 vector& operator=(initializer_list<value_type> __il)
584 {assign(__il.begin(), __il.end()); return *this;}
Howard Hinnante3e32912011-08-12 21:56:02 +0000585#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000586
587 template <class _InputIterator>
588 typename enable_if
589 <
590 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +0000591 !__is_forward_iterator<_InputIterator>::value &&
592 is_constructible<
593 value_type,
594 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000595 void
596 >::type
597 assign(_InputIterator __first, _InputIterator __last);
598 template <class _ForwardIterator>
599 typename enable_if
600 <
Howard Hinnant742fecb2013-03-28 17:44:32 +0000601 __is_forward_iterator<_ForwardIterator>::value &&
602 is_constructible<
603 value_type,
604 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000605 void
606 >::type
607 assign(_ForwardIterator __first, _ForwardIterator __last);
608
609 void assign(size_type __n, const_reference __u);
Howard Hinnante3e32912011-08-12 21:56:02 +0000610#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000611 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000612 void assign(initializer_list<value_type> __il)
613 {assign(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000614#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000615
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000616 _LIBCPP_INLINE_VISIBILITY
617 allocator_type get_allocator() const _NOEXCEPT
618 {return this->__alloc();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000619
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000620 _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
621 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
622 _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
623 _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000624
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000625 _LIBCPP_INLINE_VISIBILITY
626 reverse_iterator rbegin() _NOEXCEPT
627 {return reverse_iterator(end());}
628 _LIBCPP_INLINE_VISIBILITY
629 const_reverse_iterator rbegin() const _NOEXCEPT
630 {return const_reverse_iterator(end());}
631 _LIBCPP_INLINE_VISIBILITY
632 reverse_iterator rend() _NOEXCEPT
633 {return reverse_iterator(begin());}
634 _LIBCPP_INLINE_VISIBILITY
635 const_reverse_iterator rend() const _NOEXCEPT
636 {return const_reverse_iterator(begin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000637
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000638 _LIBCPP_INLINE_VISIBILITY
639 const_iterator cbegin() const _NOEXCEPT
640 {return begin();}
641 _LIBCPP_INLINE_VISIBILITY
642 const_iterator cend() const _NOEXCEPT
643 {return end();}
644 _LIBCPP_INLINE_VISIBILITY
645 const_reverse_iterator crbegin() const _NOEXCEPT
646 {return rbegin();}
647 _LIBCPP_INLINE_VISIBILITY
648 const_reverse_iterator crend() const _NOEXCEPT
649 {return rend();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000650
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000651 _LIBCPP_INLINE_VISIBILITY
652 size_type size() const _NOEXCEPT
653 {return static_cast<size_type>(this->__end_ - this->__begin_);}
654 _LIBCPP_INLINE_VISIBILITY
655 size_type capacity() const _NOEXCEPT
656 {return __base::capacity();}
657 _LIBCPP_INLINE_VISIBILITY
658 bool empty() const _NOEXCEPT
659 {return this->__begin_ == this->__end_;}
660 size_type max_size() const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000661 void reserve(size_type __n);
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000662 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000663
664 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n);
665 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const;
666 reference at(size_type __n);
667 const_reference at(size_type __n) const;
668
Howard Hinnant7a563db2011-09-14 18:33:51 +0000669 _LIBCPP_INLINE_VISIBILITY reference front()
670 {
671 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
672 return *this->__begin_;
673 }
674 _LIBCPP_INLINE_VISIBILITY const_reference front() const
675 {
676 _LIBCPP_ASSERT(!empty(), "front() called for empty vector");
677 return *this->__begin_;
678 }
679 _LIBCPP_INLINE_VISIBILITY reference back()
680 {
681 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
682 return *(this->__end_ - 1);
683 }
684 _LIBCPP_INLINE_VISIBILITY const_reference back() const
685 {
686 _LIBCPP_ASSERT(!empty(), "back() called for empty vector");
687 return *(this->__end_ - 1);
688 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000689
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000690 _LIBCPP_INLINE_VISIBILITY
691 value_type* data() _NOEXCEPT
Howard Hinnant0949eed2011-06-30 21:18:19 +0000692 {return _VSTD::__to_raw_pointer(this->__begin_);}
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000693 _LIBCPP_INLINE_VISIBILITY
694 const value_type* data() const _NOEXCEPT
Howard Hinnant0949eed2011-06-30 21:18:19 +0000695 {return _VSTD::__to_raw_pointer(this->__begin_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000696
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000697 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000698#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +0000699 _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000700#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000701 template <class... _Args>
702 void emplace_back(_Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000703#endif // _LIBCPP_HAS_NO_VARIADICS
704#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000705 void pop_back();
706
707 iterator insert(const_iterator __position, const_reference __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000708#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000709 iterator insert(const_iterator __position, value_type&& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000710#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000711 template <class... _Args>
712 iterator emplace(const_iterator __position, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000713#endif // _LIBCPP_HAS_NO_VARIADICS
714#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000715 iterator insert(const_iterator __position, size_type __n, const_reference __x);
716 template <class _InputIterator>
717 typename enable_if
718 <
719 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +0000720 !__is_forward_iterator<_InputIterator>::value &&
721 is_constructible<
722 value_type,
723 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000724 iterator
725 >::type
726 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
727 template <class _ForwardIterator>
728 typename enable_if
729 <
Howard Hinnant742fecb2013-03-28 17:44:32 +0000730 __is_forward_iterator<_ForwardIterator>::value &&
731 is_constructible<
732 value_type,
733 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000734 iterator
735 >::type
736 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +0000737#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +0000738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000739 iterator insert(const_iterator __position, initializer_list<value_type> __il)
740 {return insert(__position, __il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000741#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000742
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000743 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000744 iterator erase(const_iterator __first, const_iterator __last);
745
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000746 _LIBCPP_INLINE_VISIBILITY
747 void clear() _NOEXCEPT
Howard Hinnant7a563db2011-09-14 18:33:51 +0000748 {
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000749 size_type __old_size = size();
Howard Hinnant7a563db2011-09-14 18:33:51 +0000750 __base::clear();
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000751 __annotate_shrink(__old_size);
Howard Hinnant7a563db2011-09-14 18:33:51 +0000752 __invalidate_all_iterators();
753 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000754
755 void resize(size_type __sz);
756 void resize(size_type __sz, const_reference __x);
757
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000758 void swap(vector&)
759 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
760 __is_nothrow_swappable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000761
762 bool __invariants() const;
763
Howard Hinnantabe26282011-09-16 17:29:17 +0000764#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +0000765
766 bool __dereferenceable(const const_iterator* __i) const;
767 bool __decrementable(const const_iterator* __i) const;
768 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
769 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
770
Howard Hinnantabe26282011-09-16 17:29:17 +0000771#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +0000772
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000773private:
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000774 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000775 void allocate(size_type __n);
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000776 void deallocate() _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000777 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
Howard Hinnant04240d92011-01-04 19:53:31 +0000778 void __construct_at_end(size_type __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000779 void __construct_at_end(size_type __n, const_reference __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000780 template <class _ForwardIterator>
781 typename enable_if
782 <
783 __is_forward_iterator<_ForwardIterator>::value,
784 void
785 >::type
Eric Fiselier088ed9f2015-03-31 16:54:19 +0000786 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000787 void __append(size_type __n);
788 void __append(size_type __n, const_reference __x);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000789 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000790 iterator __make_iter(pointer __p) _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +0000791 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000792 const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000793 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
794 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
795 void __move_range(pointer __from_s, pointer __from_e, pointer __to);
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000796 void __move_assign(vector& __c, true_type)
797 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000798 void __move_assign(vector& __c, false_type);
Howard Hinnant7a563db2011-09-14 18:33:51 +0000799 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000800 void __destruct_at_end(pointer __new_last) _NOEXCEPT
Howard Hinnant7a563db2011-09-14 18:33:51 +0000801 {
Howard Hinnantabe26282011-09-16 17:29:17 +0000802#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +0000803 __c_node* __c = __get_db()->__find_c_and_lock(this);
804 for (__i_node** __p = __c->end_; __p != __c->beg_; )
805 {
806 --__p;
807 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
808 if (__i->base() > __new_last)
809 {
810 (*__p)->__c_ = nullptr;
811 if (--__c->end_ != __p)
812 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
813 }
814 }
815 __get_db()->unlock();
816#endif
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000817 size_type __old_size = size();
Howard Hinnant7a563db2011-09-14 18:33:51 +0000818 __base::__destruct_at_end(__new_last);
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000819 __annotate_shrink(__old_size);
Howard Hinnant7a563db2011-09-14 18:33:51 +0000820 }
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +0000821 template <class _Up>
822 void
823#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
824 __push_back_slow_path(_Up&& __x);
825#else
826 __push_back_slow_path(_Up& __x);
827#endif
Howard Hinnant0438ea22012-02-26 15:30:12 +0000828#if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
829 template <class... _Args>
830 void
831 __emplace_back_slow_path(_Args&&... __args);
832#endif
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000833 // The following functions are no-ops outside of AddressSanitizer mode.
834 // We call annotatations only for the default Allocator because other allocators
835 // may not meet the AddressSanitizer alignment constraints.
836 // See the documentation for __sanitizer_annotate_contiguous_container for more details.
837 void __annotate_contiguous_container
Kostya Serebryany497f9122014-09-02 23:43:38 +0000838 (const void *__beg, const void *__end, const void *__old_mid, const void *__new_mid) const
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000839 {
840#ifndef _LIBCPP_HAS_NO_ASAN
841 if (__beg && is_same<allocator_type, __default_allocator_type>::value)
842 __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
843#endif
844 }
845
Kostya Serebryany497f9122014-09-02 23:43:38 +0000846 void __annotate_new(size_type __current_size) const
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000847 {
848 __annotate_contiguous_container(data(), data() + capacity(),
849 data() + capacity(), data() + __current_size);
850 }
Kostya Serebryany497f9122014-09-02 23:43:38 +0000851 void __annotate_delete() const
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000852 {
853 __annotate_contiguous_container(data(), data() + capacity(),
854 data() + size(), data() + capacity());
855 }
Kostya Serebryany497f9122014-09-02 23:43:38 +0000856 void __annotate_increase(size_type __n) const
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000857 {
858 __annotate_contiguous_container(data(), data() + capacity(),
859 data() + size(), data() + size() + __n);
860 }
Kostya Serebryany497f9122014-09-02 23:43:38 +0000861 void __annotate_shrink(size_type __old_size) const
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000862 {
863 __annotate_contiguous_container(data(), data() + capacity(),
864 data() + __old_size, data() + size());
865 }
Marshall Clow26f472d2014-09-03 21:37:43 +0000866#ifndef _LIBCPP_HAS_NO_ASAN
Kostya Serebryany497f9122014-09-02 23:43:38 +0000867 // The annotation for size increase should happen before the actual increase,
868 // but if an exception is thrown after that the annotation has to be undone.
869 struct __RAII_IncreaseAnnotator {
870 __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1)
Eric Fiselier9f4f2212015-03-10 00:25:20 +0000871 : __commit(false), __v(__v), __old_size(__v.size() + __n) {
Kostya Serebryany497f9122014-09-02 23:43:38 +0000872 __v.__annotate_increase(__n);
873 }
874 void __done() { __commit = true; }
875 ~__RAII_IncreaseAnnotator() {
876 if (__commit) return;
Eric Fiselier9f4f2212015-03-10 00:25:20 +0000877 __v.__annotate_shrink(__old_size);
Kostya Serebryany497f9122014-09-02 23:43:38 +0000878 }
879 bool __commit;
Kostya Serebryany497f9122014-09-02 23:43:38 +0000880 const vector &__v;
Eric Fiselier9f4f2212015-03-10 00:25:20 +0000881 size_type __old_size;
Kostya Serebryany497f9122014-09-02 23:43:38 +0000882 };
Marshall Clow26f472d2014-09-03 21:37:43 +0000883#else
884 struct __RAII_IncreaseAnnotator {
885 inline __RAII_IncreaseAnnotator(const vector &, size_type __n = 1) {}
886 inline void __done() {}
887 };
888#endif
889
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000890};
891
892template <class _Tp, class _Allocator>
893void
894vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
895{
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000896 __annotate_delete();
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +0000897 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000898 _VSTD::swap(this->__begin_, __v.__begin_);
899 _VSTD::swap(this->__end_, __v.__end_);
900 _VSTD::swap(this->__end_cap(), __v.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000901 __v.__first_ = __v.__begin_;
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000902 __annotate_new(size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000903 __invalidate_all_iterators();
904}
905
906template <class _Tp, class _Allocator>
907typename vector<_Tp, _Allocator>::pointer
908vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
909{
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000910 __annotate_delete();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000911 pointer __r = __v.__begin_;
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +0000912 __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_);
913 __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000914 _VSTD::swap(this->__begin_, __v.__begin_);
915 _VSTD::swap(this->__end_, __v.__end_);
916 _VSTD::swap(this->__end_cap(), __v.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000917 __v.__first_ = __v.__begin_;
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000918 __annotate_new(size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000919 __invalidate_all_iterators();
920 return __r;
921}
922
923// Allocate space for __n objects
924// throws length_error if __n > max_size()
925// throws (probably bad_alloc) if memory run out
926// Precondition: __begin_ == __end_ == __end_cap() == 0
927// Precondition: __n > 0
928// Postcondition: capacity() == __n
929// Postcondition: size() == 0
930template <class _Tp, class _Allocator>
931void
932vector<_Tp, _Allocator>::allocate(size_type __n)
933{
934 if (__n > max_size())
935 this->__throw_length_error();
936 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
937 this->__end_cap() = this->__begin_ + __n;
Marshall Clow1f50f2d2014-05-08 14:14:06 +0000938 __annotate_new(0);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000939}
940
941template <class _Tp, class _Allocator>
942void
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000943vector<_Tp, _Allocator>::deallocate() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000944{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000945 if (this->__begin_ != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000946 {
947 clear();
948 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
Howard Hinnant2c39cbe2013-06-27 19:35:32 +0000949 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000950 }
951}
952
953template <class _Tp, class _Allocator>
954typename vector<_Tp, _Allocator>::size_type
Howard Hinnantd1d27a42011-06-03 19:40:40 +0000955vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000956{
Sean Hunt110b8bf2011-07-29 23:31:58 +0000957 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000958}
959
960// Precondition: __new_size > capacity()
961template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +0000962inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000963typename vector<_Tp, _Allocator>::size_type
964vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
965{
966 const size_type __ms = max_size();
967 if (__new_size > __ms)
968 this->__throw_length_error();
969 const size_type __cap = capacity();
970 if (__cap >= __ms / 2)
971 return __ms;
Sean Hunt110b8bf2011-07-29 23:31:58 +0000972 return _VSTD::max<size_type>(2*__cap, __new_size);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000973}
974
975// Default constructs __n objects starting at __end_
976// throws if construction throws
977// Precondition: __n > 0
978// Precondition: size() + __n <= capacity()
979// Postcondition: size() == size() + __n
980template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000981void
982vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
983{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000984 allocator_type& __a = this->__alloc();
985 do
986 {
Kostya Serebryany497f9122014-09-02 23:43:38 +0000987 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnant0949eed2011-06-30 21:18:19 +0000988 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000989 ++this->__end_;
990 --__n;
Kostya Serebryany497f9122014-09-02 23:43:38 +0000991 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000992 } while (__n > 0);
993}
994
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000995// Copy constructs __n objects starting at __end_ from __x
996// throws if construction throws
997// Precondition: __n > 0
998// Precondition: size() + __n <= capacity()
999// Postcondition: size() == old size() + __n
1000// Postcondition: [i] == __x for all i in [size() - __n, __n)
1001template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001002inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001003void
1004vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
1005{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001006 allocator_type& __a = this->__alloc();
1007 do
1008 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001009 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001010 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001011 ++this->__end_;
1012 --__n;
Kostya Serebryany497f9122014-09-02 23:43:38 +00001013 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001014 } while (__n > 0);
1015}
1016
1017template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001018template <class _ForwardIterator>
1019typename enable_if
1020<
1021 __is_forward_iterator<_ForwardIterator>::value,
1022 void
1023>::type
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001024vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001025{
1026 allocator_type& __a = this->__alloc();
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001027 __RAII_IncreaseAnnotator __annotator(*this, __n);
1028 __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_);
1029 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001030}
1031
1032// Default constructs __n objects starting at __end_
1033// throws if construction throws
1034// Postcondition: size() == size() + __n
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001035// Exception safety: strong.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001036template <class _Tp, class _Allocator>
1037void
1038vector<_Tp, _Allocator>::__append(size_type __n)
1039{
1040 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1041 this->__construct_at_end(__n);
1042 else
1043 {
1044 allocator_type& __a = this->__alloc();
1045 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1046 __v.__construct_at_end(__n);
1047 __swap_out_circular_buffer(__v);
1048 }
1049}
1050
1051// Default constructs __n objects starting at __end_
1052// throws if construction throws
1053// Postcondition: size() == size() + __n
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001054// Exception safety: strong.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001055template <class _Tp, class _Allocator>
1056void
1057vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
1058{
1059 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1060 this->__construct_at_end(__n, __x);
1061 else
1062 {
1063 allocator_type& __a = this->__alloc();
1064 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1065 __v.__construct_at_end(__n, __x);
1066 __swap_out_circular_buffer(__v);
1067 }
1068}
1069
1070template <class _Tp, class _Allocator>
1071vector<_Tp, _Allocator>::vector(size_type __n)
1072{
Howard Hinnant0442b122011-09-16 18:41:29 +00001073#if _LIBCPP_DEBUG_LEVEL >= 2
1074 __get_db()->__insert_c(this);
1075#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001076 if (__n > 0)
1077 {
1078 allocate(__n);
1079 __construct_at_end(__n);
1080 }
1081}
1082
Marshall Clowa49a2c92013-09-14 00:47:59 +00001083#if _LIBCPP_STD_VER > 11
1084template <class _Tp, class _Allocator>
1085vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
1086 : __base(__a)
1087{
1088#if _LIBCPP_DEBUG_LEVEL >= 2
1089 __get_db()->__insert_c(this);
1090#endif
1091 if (__n > 0)
1092 {
1093 allocate(__n);
1094 __construct_at_end(__n);
1095 }
1096}
1097#endif
1098
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001099template <class _Tp, class _Allocator>
1100vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x)
1101{
Howard Hinnant0442b122011-09-16 18:41:29 +00001102#if _LIBCPP_DEBUG_LEVEL >= 2
1103 __get_db()->__insert_c(this);
1104#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001105 if (__n > 0)
1106 {
1107 allocate(__n);
1108 __construct_at_end(__n, __x);
1109 }
1110}
1111
1112template <class _Tp, class _Allocator>
1113vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a)
1114 : __base(__a)
1115{
Howard Hinnant0442b122011-09-16 18:41:29 +00001116#if _LIBCPP_DEBUG_LEVEL >= 2
1117 __get_db()->__insert_c(this);
1118#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001119 if (__n > 0)
1120 {
1121 allocate(__n);
1122 __construct_at_end(__n, __x);
1123 }
1124}
1125
1126template <class _Tp, class _Allocator>
1127template <class _InputIterator>
Howard Hinnantde589f22013-09-21 21:13:54 +00001128vector<_Tp, _Allocator>::vector(_InputIterator __first,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001129 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +00001130 !__is_forward_iterator<_InputIterator>::value &&
1131 is_constructible<
1132 value_type,
Howard Hinnantde589f22013-09-21 21:13:54 +00001133 typename iterator_traits<_InputIterator>::reference>::value,
1134 _InputIterator>::type __last)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001135{
Howard Hinnantabe26282011-09-16 17:29:17 +00001136#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001137 __get_db()->__insert_c(this);
1138#endif
Howard Hinnant0442b122011-09-16 18:41:29 +00001139 for (; __first != __last; ++__first)
1140 push_back(*__first);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001141}
1142
1143template <class _Tp, class _Allocator>
1144template <class _InputIterator>
1145vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1146 typename enable_if<__is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +00001147 !__is_forward_iterator<_InputIterator>::value &&
1148 is_constructible<
1149 value_type,
1150 typename iterator_traits<_InputIterator>::reference>::value>::type*)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001151 : __base(__a)
1152{
Howard Hinnantabe26282011-09-16 17:29:17 +00001153#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001154 __get_db()->__insert_c(this);
1155#endif
Howard Hinnant0442b122011-09-16 18:41:29 +00001156 for (; __first != __last; ++__first)
1157 push_back(*__first);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001158}
1159
1160template <class _Tp, class _Allocator>
1161template <class _ForwardIterator>
Howard Hinnantde589f22013-09-21 21:13:54 +00001162vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
Howard Hinnant742fecb2013-03-28 17:44:32 +00001163 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1164 is_constructible<
1165 value_type,
Howard Hinnantde589f22013-09-21 21:13:54 +00001166 typename iterator_traits<_ForwardIterator>::reference>::value,
1167 _ForwardIterator>::type __last)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001168{
Howard Hinnant0442b122011-09-16 18:41:29 +00001169#if _LIBCPP_DEBUG_LEVEL >= 2
1170 __get_db()->__insert_c(this);
1171#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001172 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001173 if (__n > 0)
1174 {
1175 allocate(__n);
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001176 __construct_at_end(__first, __last, __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001177 }
1178}
1179
1180template <class _Tp, class _Allocator>
1181template <class _ForwardIterator>
1182vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
Howard Hinnant742fecb2013-03-28 17:44:32 +00001183 typename enable_if<__is_forward_iterator<_ForwardIterator>::value &&
1184 is_constructible<
1185 value_type,
1186 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001187 : __base(__a)
1188{
Howard Hinnant0442b122011-09-16 18:41:29 +00001189#if _LIBCPP_DEBUG_LEVEL >= 2
1190 __get_db()->__insert_c(this);
1191#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001192 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001193 if (__n > 0)
1194 {
1195 allocate(__n);
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001196 __construct_at_end(__first, __last, __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001197 }
1198}
1199
1200template <class _Tp, class _Allocator>
1201vector<_Tp, _Allocator>::vector(const vector& __x)
1202 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1203{
Howard Hinnant0442b122011-09-16 18:41:29 +00001204#if _LIBCPP_DEBUG_LEVEL >= 2
1205 __get_db()->__insert_c(this);
1206#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001207 size_type __n = __x.size();
1208 if (__n > 0)
1209 {
1210 allocate(__n);
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001211 __construct_at_end(__x.__begin_, __x.__end_, __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001212 }
1213}
1214
1215template <class _Tp, class _Allocator>
1216vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1217 : __base(__a)
1218{
Howard Hinnant0442b122011-09-16 18:41:29 +00001219#if _LIBCPP_DEBUG_LEVEL >= 2
1220 __get_db()->__insert_c(this);
1221#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001222 size_type __n = __x.size();
1223 if (__n > 0)
1224 {
1225 allocate(__n);
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001226 __construct_at_end(__x.__begin_, __x.__end_, __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001227 }
1228}
1229
Howard Hinnant73d21a42010-09-04 23:28:19 +00001230#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001231
1232template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001233inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001234vector<_Tp, _Allocator>::vector(vector&& __x)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001235 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001236 : __base(_VSTD::move(__x.__alloc()))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001237{
Howard Hinnantabe26282011-09-16 17:29:17 +00001238#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001239 __get_db()->__insert_c(this);
Howard Hinnante6125bd2011-09-19 16:34:29 +00001240 __get_db()->swap(this, &__x);
Howard Hinnant7a563db2011-09-14 18:33:51 +00001241#endif
Howard Hinnant0442b122011-09-16 18:41:29 +00001242 this->__begin_ = __x.__begin_;
1243 this->__end_ = __x.__end_;
1244 this->__end_cap() = __x.__end_cap();
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00001245 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001246}
1247
1248template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001249inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001250vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1251 : __base(__a)
1252{
Howard Hinnant0442b122011-09-16 18:41:29 +00001253#if _LIBCPP_DEBUG_LEVEL >= 2
1254 __get_db()->__insert_c(this);
1255#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001256 if (__a == __x.__alloc())
1257 {
1258 this->__begin_ = __x.__begin_;
1259 this->__end_ = __x.__end_;
1260 this->__end_cap() = __x.__end_cap();
1261 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
Howard Hinnante6125bd2011-09-19 16:34:29 +00001262#if _LIBCPP_DEBUG_LEVEL >= 2
1263 __get_db()->swap(this, &__x);
1264#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001265 }
1266 else
1267 {
Howard Hinnant99968442011-11-29 18:15:50 +00001268 typedef move_iterator<iterator> _Ip;
1269 assign(_Ip(__x.begin()), _Ip(__x.end()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001270 }
1271}
1272
Howard Hinnante3e32912011-08-12 21:56:02 +00001273#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1274
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001275template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001276inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001277vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1278{
Howard Hinnant0442b122011-09-16 18:41:29 +00001279#if _LIBCPP_DEBUG_LEVEL >= 2
1280 __get_db()->__insert_c(this);
1281#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001282 if (__il.size() > 0)
1283 {
1284 allocate(__il.size());
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001285 __construct_at_end(__il.begin(), __il.end(), __il.size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001286 }
1287}
1288
1289template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001290inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001291vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1292 : __base(__a)
1293{
Howard Hinnant0442b122011-09-16 18:41:29 +00001294#if _LIBCPP_DEBUG_LEVEL >= 2
1295 __get_db()->__insert_c(this);
1296#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001297 if (__il.size() > 0)
1298 {
1299 allocate(__il.size());
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001300 __construct_at_end(__il.begin(), __il.end(), __il.size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001301 }
1302}
1303
Howard Hinnante3e32912011-08-12 21:56:02 +00001304#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1305
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001306template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001307inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001308vector<_Tp, _Allocator>&
1309vector<_Tp, _Allocator>::operator=(vector&& __x)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001310 _NOEXCEPT_(
1311 __alloc_traits::propagate_on_container_move_assignment::value &&
1312 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001313{
1314 __move_assign(__x, integral_constant<bool,
1315 __alloc_traits::propagate_on_container_move_assignment::value>());
1316 return *this;
1317}
1318
1319template <class _Tp, class _Allocator>
1320void
1321vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1322{
1323 if (__base::__alloc() != __c.__alloc())
1324 {
Howard Hinnant99968442011-11-29 18:15:50 +00001325 typedef move_iterator<iterator> _Ip;
1326 assign(_Ip(__c.begin()), _Ip(__c.end()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001327 }
1328 else
1329 __move_assign(__c, true_type());
1330}
1331
1332template <class _Tp, class _Allocator>
1333void
1334vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001335 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001336{
1337 deallocate();
Marshall Clow3c2eac62014-07-21 15:11:13 +00001338 __base::__move_assign_alloc(__c); // this can throw
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001339 this->__begin_ = __c.__begin_;
1340 this->__end_ = __c.__end_;
1341 this->__end_cap() = __c.__end_cap();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001342 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
Howard Hinnante6125bd2011-09-19 16:34:29 +00001343#if _LIBCPP_DEBUG_LEVEL >= 2
1344 __get_db()->swap(this, &__c);
1345#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001346}
1347
Howard Hinnant73d21a42010-09-04 23:28:19 +00001348#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001349
1350template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001351inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001352vector<_Tp, _Allocator>&
1353vector<_Tp, _Allocator>::operator=(const vector& __x)
1354{
1355 if (this != &__x)
1356 {
1357 __base::__copy_assign_alloc(__x);
1358 assign(__x.__begin_, __x.__end_);
1359 }
1360 return *this;
1361}
1362
1363template <class _Tp, class _Allocator>
1364template <class _InputIterator>
1365typename enable_if
1366<
1367 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +00001368 !__is_forward_iterator<_InputIterator>::value &&
1369 is_constructible<
1370 _Tp,
1371 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001372 void
1373>::type
1374vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1375{
1376 clear();
1377 for (; __first != __last; ++__first)
1378 push_back(*__first);
1379}
1380
1381template <class _Tp, class _Allocator>
1382template <class _ForwardIterator>
1383typename enable_if
1384<
Howard Hinnant742fecb2013-03-28 17:44:32 +00001385 __is_forward_iterator<_ForwardIterator>::value &&
1386 is_constructible<
1387 _Tp,
1388 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001389 void
1390>::type
1391vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1392{
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001393 size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
1394 if (__new_size <= capacity())
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001395 {
1396 _ForwardIterator __mid = __last;
1397 bool __growing = false;
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001398 if (__new_size > size())
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001399 {
1400 __growing = true;
1401 __mid = __first;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001402 _VSTD::advance(__mid, size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001403 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00001404 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001405 if (__growing)
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001406 __construct_at_end(__mid, __last, __new_size - size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001407 else
1408 this->__destruct_at_end(__m);
1409 }
1410 else
1411 {
1412 deallocate();
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001413 allocate(__recommend(__new_size));
1414 __construct_at_end(__first, __last, __new_size);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001415 }
1416}
1417
1418template <class _Tp, class _Allocator>
1419void
1420vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1421{
1422 if (__n <= capacity())
1423 {
1424 size_type __s = size();
Howard Hinnant0949eed2011-06-30 21:18:19 +00001425 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001426 if (__n > __s)
1427 __construct_at_end(__n - __s, __u);
1428 else
Howard Hinnantadff4892010-05-24 17:49:41 +00001429 this->__destruct_at_end(this->__begin_ + __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001430 }
1431 else
1432 {
1433 deallocate();
1434 allocate(__recommend(static_cast<size_type>(__n)));
1435 __construct_at_end(__n, __u);
1436 }
1437}
1438
Howard Hinnant324bb032010-08-22 00:02:43 +00001439template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001440inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001441typename vector<_Tp, _Allocator>::iterator
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001442vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001443{
Howard Hinnantabe26282011-09-16 17:29:17 +00001444#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001445 return iterator(this, __p);
1446#else
1447 return iterator(__p);
1448#endif
1449}
1450
Howard Hinnant324bb032010-08-22 00:02:43 +00001451template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001452inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001453typename vector<_Tp, _Allocator>::const_iterator
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001454vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001455{
Howard Hinnantabe26282011-09-16 17:29:17 +00001456#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001457 return const_iterator(this, __p);
1458#else
1459 return const_iterator(__p);
1460#endif
1461}
1462
Howard Hinnant324bb032010-08-22 00:02:43 +00001463template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001464inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001465typename vector<_Tp, _Allocator>::iterator
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001466vector<_Tp, _Allocator>::begin() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001467{
1468 return __make_iter(this->__begin_);
1469}
1470
Howard Hinnant324bb032010-08-22 00:02:43 +00001471template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001472inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001473typename vector<_Tp, _Allocator>::const_iterator
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001474vector<_Tp, _Allocator>::begin() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001475{
1476 return __make_iter(this->__begin_);
1477}
1478
Howard Hinnant324bb032010-08-22 00:02:43 +00001479template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001480inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001481typename vector<_Tp, _Allocator>::iterator
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001482vector<_Tp, _Allocator>::end() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001483{
1484 return __make_iter(this->__end_);
1485}
1486
Howard Hinnant324bb032010-08-22 00:02:43 +00001487template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001488inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001489typename vector<_Tp, _Allocator>::const_iterator
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001490vector<_Tp, _Allocator>::end() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001491{
1492 return __make_iter(this->__end_);
1493}
1494
Howard Hinnant324bb032010-08-22 00:02:43 +00001495template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001496inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001497typename vector<_Tp, _Allocator>::reference
1498vector<_Tp, _Allocator>::operator[](size_type __n)
1499{
Howard Hinnant7a563db2011-09-14 18:33:51 +00001500 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001501 return this->__begin_[__n];
1502}
1503
Howard Hinnant324bb032010-08-22 00:02:43 +00001504template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001505inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001506typename vector<_Tp, _Allocator>::const_reference
1507vector<_Tp, _Allocator>::operator[](size_type __n) const
1508{
Howard Hinnant7a563db2011-09-14 18:33:51 +00001509 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001510 return this->__begin_[__n];
1511}
1512
Howard Hinnant324bb032010-08-22 00:02:43 +00001513template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001514typename vector<_Tp, _Allocator>::reference
1515vector<_Tp, _Allocator>::at(size_type __n)
1516{
1517 if (__n >= size())
1518 this->__throw_out_of_range();
1519 return this->__begin_[__n];
1520}
1521
Howard Hinnant324bb032010-08-22 00:02:43 +00001522template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001523typename vector<_Tp, _Allocator>::const_reference
1524vector<_Tp, _Allocator>::at(size_type __n) const
1525{
1526 if (__n >= size())
1527 this->__throw_out_of_range();
1528 return this->__begin_[__n];
1529}
1530
1531template <class _Tp, class _Allocator>
1532void
1533vector<_Tp, _Allocator>::reserve(size_type __n)
1534{
1535 if (__n > capacity())
1536 {
1537 allocator_type& __a = this->__alloc();
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001538 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001539 __swap_out_circular_buffer(__v);
1540 }
1541}
1542
1543template <class _Tp, class _Allocator>
1544void
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001545vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001546{
1547 if (capacity() > size())
1548 {
1549#ifndef _LIBCPP_NO_EXCEPTIONS
1550 try
1551 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001552#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001553 allocator_type& __a = this->__alloc();
Howard Hinnantd1d27a42011-06-03 19:40:40 +00001554 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001555 __swap_out_circular_buffer(__v);
1556#ifndef _LIBCPP_NO_EXCEPTIONS
1557 }
1558 catch (...)
1559 {
1560 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001561#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001562 }
1563}
1564
1565template <class _Tp, class _Allocator>
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +00001566template <class _Up>
1567void
1568#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1569vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1570#else
1571vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1572#endif
1573{
1574 allocator_type& __a = this->__alloc();
1575 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1576 // __v.push_back(_VSTD::forward<_Up>(__x));
Howard Hinnantf619e232013-01-11 20:36:59 +00001577 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x));
1578 __v.__end_++;
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +00001579 __swap_out_circular_buffer(__v);
1580}
1581
1582template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001583inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001584void
1585vector<_Tp, _Allocator>::push_back(const_reference __x)
1586{
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +00001587 if (this->__end_ != this->__end_cap())
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001588 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001589 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001590 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001591 _VSTD::__to_raw_pointer(this->__end_), __x);
Kostya Serebryany497f9122014-09-02 23:43:38 +00001592 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001593 ++this->__end_;
1594 }
1595 else
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +00001596 __push_back_slow_path(__x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001597}
1598
Howard Hinnant73d21a42010-09-04 23:28:19 +00001599#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001600
1601template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001602inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001603void
1604vector<_Tp, _Allocator>::push_back(value_type&& __x)
1605{
1606 if (this->__end_ < this->__end_cap())
1607 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001608 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001609 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001610 _VSTD::__to_raw_pointer(this->__end_),
1611 _VSTD::move(__x));
Kostya Serebryany497f9122014-09-02 23:43:38 +00001612 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001613 ++this->__end_;
1614 }
1615 else
Howard Hinnantb0bfd9b2012-02-15 00:41:34 +00001616 __push_back_slow_path(_VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001617}
1618
Howard Hinnant73d21a42010-09-04 23:28:19 +00001619#ifndef _LIBCPP_HAS_NO_VARIADICS
1620
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001621template <class _Tp, class _Allocator>
1622template <class... _Args>
1623void
Howard Hinnant0438ea22012-02-26 15:30:12 +00001624vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1625{
1626 allocator_type& __a = this->__alloc();
1627 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1628// __v.emplace_back(_VSTD::forward<_Args>(__args)...);
Howard Hinnantf619e232013-01-11 20:36:59 +00001629 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
1630 __v.__end_++;
Howard Hinnant0438ea22012-02-26 15:30:12 +00001631 __swap_out_circular_buffer(__v);
1632}
1633
1634template <class _Tp, class _Allocator>
1635template <class... _Args>
Howard Hinnant1e564242013-10-04 22:09:00 +00001636inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnant0438ea22012-02-26 15:30:12 +00001637void
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001638vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1639{
1640 if (this->__end_ < this->__end_cap())
1641 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001642 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001643 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001644 _VSTD::__to_raw_pointer(this->__end_),
1645 _VSTD::forward<_Args>(__args)...);
Kostya Serebryany497f9122014-09-02 23:43:38 +00001646 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001647 ++this->__end_;
1648 }
1649 else
Howard Hinnant0438ea22012-02-26 15:30:12 +00001650 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001651}
1652
Howard Hinnant73d21a42010-09-04 23:28:19 +00001653#endif // _LIBCPP_HAS_NO_VARIADICS
1654#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001655
1656template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001657inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001658void
1659vector<_Tp, _Allocator>::pop_back()
1660{
Howard Hinnant7a563db2011-09-14 18:33:51 +00001661 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001662 this->__destruct_at_end(this->__end_ - 1);
1663}
1664
1665template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00001666inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001667typename vector<_Tp, _Allocator>::iterator
1668vector<_Tp, _Allocator>::erase(const_iterator __position)
1669{
Howard Hinnantabe26282011-09-16 17:29:17 +00001670#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001671 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1672 "vector::erase(iterator) called with an iterator not"
1673 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001674#endif
Howard Hinnant782da332013-03-25 22:12:26 +00001675 _LIBCPP_ASSERT(__position != end(),
1676 "vector::erase(iterator) called with a non-dereferenceable iterator");
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00001677 difference_type __ps = __position - cbegin();
1678 pointer __p = this->__begin_ + __ps;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001679 iterator __r = __make_iter(__p);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001680 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001681 return __r;
1682}
1683
1684template <class _Tp, class _Allocator>
1685typename vector<_Tp, _Allocator>::iterator
1686vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1687{
Howard Hinnantabe26282011-09-16 17:29:17 +00001688#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001689 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1690 "vector::erase(iterator, iterator) called with an iterator not"
1691 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001692#endif
Howard Hinnant7a563db2011-09-14 18:33:51 +00001693 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001694 pointer __p = this->__begin_ + (__first - begin());
1695 iterator __r = __make_iter(__p);
Howard Hinnantb4e67cf2013-04-18 15:02:57 +00001696 if (__first != __last)
1697 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001698 return __r;
1699}
1700
1701template <class _Tp, class _Allocator>
1702void
1703vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1704{
1705 pointer __old_last = this->__end_;
1706 difference_type __n = __old_last - __to;
1707 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1708 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001709 _VSTD::__to_raw_pointer(this->__end_),
1710 _VSTD::move(*__i));
1711 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001712}
1713
1714template <class _Tp, class _Allocator>
1715typename vector<_Tp, _Allocator>::iterator
1716vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1717{
Howard Hinnantabe26282011-09-16 17:29:17 +00001718#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001719 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1720 "vector::insert(iterator, x) called with an iterator not"
1721 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001722#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001723 pointer __p = this->__begin_ + (__position - begin());
1724 if (this->__end_ < this->__end_cap())
1725 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001726 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001727 if (__p == this->__end_)
1728 {
1729 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001730 _VSTD::__to_raw_pointer(this->__end_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001731 ++this->__end_;
1732 }
1733 else
1734 {
1735 __move_range(__p, this->__end_, __p + 1);
1736 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1737 if (__p <= __xr && __xr < this->__end_)
1738 ++__xr;
1739 *__p = *__xr;
1740 }
Kostya Serebryany497f9122014-09-02 23:43:38 +00001741 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001742 }
1743 else
1744 {
1745 allocator_type& __a = this->__alloc();
1746 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1747 __v.push_back(__x);
1748 __p = __swap_out_circular_buffer(__v, __p);
1749 }
1750 return __make_iter(__p);
1751}
1752
Howard Hinnant73d21a42010-09-04 23:28:19 +00001753#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001754
1755template <class _Tp, class _Allocator>
1756typename vector<_Tp, _Allocator>::iterator
1757vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1758{
Howard Hinnantabe26282011-09-16 17:29:17 +00001759#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001760 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1761 "vector::insert(iterator, x) called with an iterator not"
1762 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001763#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001764 pointer __p = this->__begin_ + (__position - begin());
1765 if (this->__end_ < this->__end_cap())
1766 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001767 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001768 if (__p == this->__end_)
1769 {
1770 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001771 _VSTD::__to_raw_pointer(this->__end_),
1772 _VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001773 ++this->__end_;
1774 }
1775 else
1776 {
1777 __move_range(__p, this->__end_, __p + 1);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001778 *__p = _VSTD::move(__x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001779 }
Kostya Serebryany497f9122014-09-02 23:43:38 +00001780 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001781 }
1782 else
1783 {
1784 allocator_type& __a = this->__alloc();
1785 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001786 __v.push_back(_VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001787 __p = __swap_out_circular_buffer(__v, __p);
1788 }
1789 return __make_iter(__p);
1790}
1791
Howard Hinnant73d21a42010-09-04 23:28:19 +00001792#ifndef _LIBCPP_HAS_NO_VARIADICS
1793
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001794template <class _Tp, class _Allocator>
1795template <class... _Args>
1796typename vector<_Tp, _Allocator>::iterator
1797vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1798{
Howard Hinnantabe26282011-09-16 17:29:17 +00001799#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001800 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1801 "vector::emplace(iterator, x) called with an iterator not"
1802 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001803#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001804 pointer __p = this->__begin_ + (__position - begin());
1805 if (this->__end_ < this->__end_cap())
1806 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001807 __RAII_IncreaseAnnotator __annotator(*this);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001808 if (__p == this->__end_)
1809 {
1810 __alloc_traits::construct(this->__alloc(),
Howard Hinnant0949eed2011-06-30 21:18:19 +00001811 _VSTD::__to_raw_pointer(this->__end_),
1812 _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001813 ++this->__end_;
1814 }
1815 else
1816 {
Howard Hinnanta58402a2012-07-08 23:23:04 +00001817 value_type __tmp(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001818 __move_range(__p, this->__end_, __p + 1);
Howard Hinnanta58402a2012-07-08 23:23:04 +00001819 *__p = _VSTD::move(__tmp);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001820 }
Kostya Serebryany497f9122014-09-02 23:43:38 +00001821 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001822 }
1823 else
1824 {
1825 allocator_type& __a = this->__alloc();
1826 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
Howard Hinnant0949eed2011-06-30 21:18:19 +00001827 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001828 __p = __swap_out_circular_buffer(__v, __p);
1829 }
1830 return __make_iter(__p);
1831}
1832
Howard Hinnant73d21a42010-09-04 23:28:19 +00001833#endif // _LIBCPP_HAS_NO_VARIADICS
1834#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001835
1836template <class _Tp, class _Allocator>
1837typename vector<_Tp, _Allocator>::iterator
1838vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1839{
Howard Hinnantabe26282011-09-16 17:29:17 +00001840#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001841 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1842 "vector::insert(iterator, n, x) called with an iterator not"
1843 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001844#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001845 pointer __p = this->__begin_ + (__position - begin());
1846 if (__n > 0)
1847 {
1848 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1849 {
1850 size_type __old_n = __n;
1851 pointer __old_last = this->__end_;
1852 if (__n > static_cast<size_type>(this->__end_ - __p))
1853 {
1854 size_type __cx = __n - (this->__end_ - __p);
1855 __construct_at_end(__cx, __x);
1856 __n -= __cx;
1857 }
1858 if (__n > 0)
1859 {
Eric Fiselierd7590952014-11-14 18:28:36 +00001860 __RAII_IncreaseAnnotator __annotator(*this, __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001861 __move_range(__p, __old_last, __p + __old_n);
Kostya Serebryany497f9122014-09-02 23:43:38 +00001862 __annotator.__done();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001863 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1864 if (__p <= __xr && __xr < this->__end_)
1865 __xr += __old_n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001866 _VSTD::fill_n(__p, __n, *__xr);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001867 }
1868 }
1869 else
1870 {
1871 allocator_type& __a = this->__alloc();
1872 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1873 __v.__construct_at_end(__n, __x);
1874 __p = __swap_out_circular_buffer(__v, __p);
1875 }
1876 }
1877 return __make_iter(__p);
1878}
1879
1880template <class _Tp, class _Allocator>
1881template <class _InputIterator>
1882typename enable_if
1883<
1884 __is_input_iterator <_InputIterator>::value &&
Howard Hinnant742fecb2013-03-28 17:44:32 +00001885 !__is_forward_iterator<_InputIterator>::value &&
1886 is_constructible<
1887 _Tp,
1888 typename iterator_traits<_InputIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001889 typename vector<_Tp, _Allocator>::iterator
1890>::type
1891vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1892{
Howard Hinnantabe26282011-09-16 17:29:17 +00001893#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001894 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1895 "vector::insert(iterator, range) called with an iterator not"
1896 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001897#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001898 difference_type __off = __position - begin();
1899 pointer __p = this->__begin_ + __off;
1900 allocator_type& __a = this->__alloc();
1901 pointer __old_last = this->__end_;
1902 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1903 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001904 __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001905 *__first);
1906 ++this->__end_;
1907 }
1908 __split_buffer<value_type, allocator_type&> __v(__a);
1909 if (__first != __last)
1910 {
1911#ifndef _LIBCPP_NO_EXCEPTIONS
1912 try
1913 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001914#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001915 __v.__construct_at_end(__first, __last);
1916 difference_type __old_size = __old_last - this->__begin_;
1917 difference_type __old_p = __p - this->__begin_;
1918 reserve(__recommend(size() + __v.size()));
1919 __p = this->__begin_ + __old_p;
1920 __old_last = this->__begin_ + __old_size;
1921#ifndef _LIBCPP_NO_EXCEPTIONS
1922 }
1923 catch (...)
1924 {
1925 erase(__make_iter(__old_last), end());
1926 throw;
1927 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001928#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001929 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00001930 __p = _VSTD::rotate(__p, __old_last, this->__end_);
Howard Hinnant0442b122011-09-16 18:41:29 +00001931 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1932 make_move_iterator(__v.end()));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001933 return begin() + __off;
1934}
1935
1936template <class _Tp, class _Allocator>
1937template <class _ForwardIterator>
1938typename enable_if
1939<
Howard Hinnant742fecb2013-03-28 17:44:32 +00001940 __is_forward_iterator<_ForwardIterator>::value &&
1941 is_constructible<
1942 _Tp,
1943 typename iterator_traits<_ForwardIterator>::reference>::value,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001944 typename vector<_Tp, _Allocator>::iterator
1945>::type
1946vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1947{
Howard Hinnantabe26282011-09-16 17:29:17 +00001948#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00001949 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1950 "vector::insert(iterator, range) called with an iterator not"
1951 " referring to this vector");
Howard Hinnantabe26282011-09-16 17:29:17 +00001952#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001953 pointer __p = this->__begin_ + (__position - begin());
Howard Hinnant0949eed2011-06-30 21:18:19 +00001954 difference_type __n = _VSTD::distance(__first, __last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001955 if (__n > 0)
1956 {
1957 if (__n <= this->__end_cap() - this->__end_)
1958 {
1959 size_type __old_n = __n;
1960 pointer __old_last = this->__end_;
1961 _ForwardIterator __m = __last;
1962 difference_type __dx = this->__end_ - __p;
1963 if (__n > __dx)
1964 {
1965 __m = __first;
Eric Fiselier088ed9f2015-03-31 16:54:19 +00001966 difference_type __diff = this->__end_ - __p;
1967 _VSTD::advance(__m, __diff);
1968 __construct_at_end(__m, __last, __n - __diff);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001969 __n = __dx;
1970 }
1971 if (__n > 0)
1972 {
Kostya Serebryany497f9122014-09-02 23:43:38 +00001973 __RAII_IncreaseAnnotator __annotator(*this, __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001974 __move_range(__p, __old_last, __p + __old_n);
Kostya Serebryany497f9122014-09-02 23:43:38 +00001975 __annotator.__done();
Howard Hinnant0949eed2011-06-30 21:18:19 +00001976 _VSTD::copy(__first, __m, __p);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001977 }
1978 }
1979 else
1980 {
1981 allocator_type& __a = this->__alloc();
1982 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1983 __v.__construct_at_end(__first, __last);
1984 __p = __swap_out_circular_buffer(__v, __p);
1985 }
1986 }
1987 return __make_iter(__p);
1988}
1989
1990template <class _Tp, class _Allocator>
1991void
1992vector<_Tp, _Allocator>::resize(size_type __sz)
1993{
1994 size_type __cs = size();
1995 if (__cs < __sz)
1996 this->__append(__sz - __cs);
1997 else if (__cs > __sz)
1998 this->__destruct_at_end(this->__begin_ + __sz);
1999}
2000
2001template <class _Tp, class _Allocator>
2002void
2003vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
2004{
2005 size_type __cs = size();
2006 if (__cs < __sz)
2007 this->__append(__sz - __cs, __x);
2008 else if (__cs > __sz)
2009 this->__destruct_at_end(this->__begin_ + __sz);
2010}
2011
2012template <class _Tp, class _Allocator>
2013void
2014vector<_Tp, _Allocator>::swap(vector& __x)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002015 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2016 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002017{
Howard Hinnant7a563db2011-09-14 18:33:51 +00002018 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
2019 this->__alloc() == __x.__alloc(),
2020 "vector::swap: Either propagate_on_container_swap must be true"
2021 " or the allocators must compare equal");
Howard Hinnant0949eed2011-06-30 21:18:19 +00002022 _VSTD::swap(this->__begin_, __x.__begin_);
2023 _VSTD::swap(this->__end_, __x.__end_);
2024 _VSTD::swap(this->__end_cap(), __x.__end_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002025 __base::__swap_alloc(this->__alloc(), __x.__alloc());
Howard Hinnantabe26282011-09-16 17:29:17 +00002026#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00002027 __get_db()->swap(this, &__x);
Howard Hinnantabe26282011-09-16 17:29:17 +00002028#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002029}
2030
Howard Hinnant324bb032010-08-22 00:02:43 +00002031template <class _Tp, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002032bool
2033vector<_Tp, _Allocator>::__invariants() const
2034{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002035 if (this->__begin_ == nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002036 {
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002037 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002038 return false;
2039 }
2040 else
2041 {
2042 if (this->__begin_ > this->__end_)
2043 return false;
2044 if (this->__begin_ == this->__end_cap())
2045 return false;
2046 if (this->__end_ > this->__end_cap())
2047 return false;
2048 }
2049 return true;
2050}
2051
Howard Hinnantabe26282011-09-16 17:29:17 +00002052#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00002053
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002054template <class _Tp, class _Allocator>
Howard Hinnant7a563db2011-09-14 18:33:51 +00002055bool
2056vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
2057{
2058 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
2059}
2060
2061template <class _Tp, class _Allocator>
2062bool
2063vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
2064{
2065 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
2066}
2067
2068template <class _Tp, class _Allocator>
2069bool
2070vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2071{
2072 const_pointer __p = __i->base() + __n;
2073 return this->__begin_ <= __p && __p <= this->__end_;
2074}
2075
2076template <class _Tp, class _Allocator>
2077bool
2078vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2079{
2080 const_pointer __p = __i->base() + __n;
2081 return this->__begin_ <= __p && __p < this->__end_;
2082}
2083
Howard Hinnantabe26282011-09-16 17:29:17 +00002084#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00002085
2086template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002087inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002088void
2089vector<_Tp, _Allocator>::__invalidate_all_iterators()
2090{
Howard Hinnantabe26282011-09-16 17:29:17 +00002091#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnant7a563db2011-09-14 18:33:51 +00002092 __get_db()->__invalidate_all(this);
Howard Hinnantabe26282011-09-16 17:29:17 +00002093#endif // _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002094}
2095
2096// vector<bool>
2097
2098template <class _Allocator> class vector<bool, _Allocator>;
2099
2100template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2101
2102template <class _Allocator>
Howard Hinnantf03c3b42011-07-02 20:33:23 +00002103struct __has_storage_type<vector<bool, _Allocator> >
2104{
2105 static const bool value = true;
2106};
2107
2108template <class _Allocator>
Howard Hinnant0f678bd2013-08-12 18:38:34 +00002109class _LIBCPP_TYPE_VIS_ONLY vector<bool, _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002110 : private __vector_base_common<true>
2111{
2112public:
2113 typedef vector __self;
Howard Hinnant324bb032010-08-22 00:02:43 +00002114 typedef bool value_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002115 typedef _Allocator allocator_type;
2116 typedef allocator_traits<allocator_type> __alloc_traits;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002117 typedef typename __alloc_traits::size_type size_type;
2118 typedef typename __alloc_traits::difference_type difference_type;
Howard Hinnantf867f632012-05-07 16:50:38 +00002119 typedef size_type __storage_type;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002120 typedef __bit_iterator<vector, false> pointer;
2121 typedef __bit_iterator<vector, true> const_pointer;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002122 typedef pointer iterator;
2123 typedef const_pointer const_iterator;
Howard Hinnant0949eed2011-06-30 21:18:19 +00002124 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2125 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002126
2127private:
Marshall Clow66302c62015-04-07 05:21:38 +00002128 typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002129 typedef allocator_traits<__storage_allocator> __storage_traits;
2130 typedef typename __storage_traits::pointer __storage_pointer;
2131 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2132
2133 __storage_pointer __begin_;
2134 size_type __size_;
2135 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
Howard Hinnant2bf1c082011-07-09 15:50:42 +00002136public:
Howard Hinnantf03c3b42011-07-02 20:33:23 +00002137 typedef __bit_reference<vector> reference;
2138 typedef __bit_const_reference<vector> const_reference;
Howard Hinnant2bf1c082011-07-09 15:50:42 +00002139private:
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002140 _LIBCPP_INLINE_VISIBILITY
2141 size_type& __cap() _NOEXCEPT
2142 {return __cap_alloc_.first();}
2143 _LIBCPP_INLINE_VISIBILITY
2144 const size_type& __cap() const _NOEXCEPT
2145 {return __cap_alloc_.first();}
2146 _LIBCPP_INLINE_VISIBILITY
2147 __storage_allocator& __alloc() _NOEXCEPT
2148 {return __cap_alloc_.second();}
2149 _LIBCPP_INLINE_VISIBILITY
2150 const __storage_allocator& __alloc() const _NOEXCEPT
2151 {return __cap_alloc_.second();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002152
2153 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2154
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002155 _LIBCPP_INLINE_VISIBILITY
2156 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002157 {return __n * __bits_per_word;}
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002158 _LIBCPP_INLINE_VISIBILITY
2159 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002160 {return (__n - 1) / __bits_per_word + 1;}
2161
2162public:
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002163 _LIBCPP_INLINE_VISIBILITY
2164 vector()
2165 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00002166 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002167 ~vector();
2168 explicit vector(size_type __n);
Marshall Clowa49a2c92013-09-14 00:47:59 +00002169#if _LIBCPP_STD_VER > 11
2170 explicit vector(size_type __n, const allocator_type& __a);
2171#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002172 vector(size_type __n, const value_type& __v);
2173 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2174 template <class _InputIterator>
2175 vector(_InputIterator __first, _InputIterator __last,
2176 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2177 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2178 template <class _InputIterator>
2179 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2180 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2181 !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2182 template <class _ForwardIterator>
2183 vector(_ForwardIterator __first, _ForwardIterator __last,
2184 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2185 template <class _ForwardIterator>
2186 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2187 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2188
2189 vector(const vector& __v);
2190 vector(const vector& __v, const allocator_type& __a);
2191 vector& operator=(const vector& __v);
Howard Hinnante3e32912011-08-12 21:56:02 +00002192#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002193 vector(initializer_list<value_type> __il);
2194 vector(initializer_list<value_type> __il, const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +00002195#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002196
Howard Hinnant73d21a42010-09-04 23:28:19 +00002197#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002198 _LIBCPP_INLINE_VISIBILITY
2199 vector(vector&& __v)
2200 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002201 vector(vector&& __v, const allocator_type& __a);
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002202 _LIBCPP_INLINE_VISIBILITY
2203 vector& operator=(vector&& __v)
2204 _NOEXCEPT_(
2205 __alloc_traits::propagate_on_container_move_assignment::value &&
2206 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnant73d21a42010-09-04 23:28:19 +00002207#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +00002208#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002209 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002210 vector& operator=(initializer_list<value_type> __il)
2211 {assign(__il.begin(), __il.end()); return *this;}
Howard Hinnante3e32912011-08-12 21:56:02 +00002212#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002213
2214 template <class _InputIterator>
2215 typename enable_if
2216 <
2217 __is_input_iterator<_InputIterator>::value &&
2218 !__is_forward_iterator<_InputIterator>::value,
2219 void
2220 >::type
2221 assign(_InputIterator __first, _InputIterator __last);
2222 template <class _ForwardIterator>
2223 typename enable_if
2224 <
2225 __is_forward_iterator<_ForwardIterator>::value,
2226 void
2227 >::type
2228 assign(_ForwardIterator __first, _ForwardIterator __last);
2229
2230 void assign(size_type __n, const value_type& __x);
Howard Hinnante3e32912011-08-12 21:56:02 +00002231#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002232 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002233 void assign(initializer_list<value_type> __il)
2234 {assign(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00002235#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002236
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002237 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002238 {return allocator_type(this->__alloc());}
2239
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002240 size_type max_size() const _NOEXCEPT;
2241 _LIBCPP_INLINE_VISIBILITY
2242 size_type capacity() const _NOEXCEPT
2243 {return __internal_cap_to_external(__cap());}
2244 _LIBCPP_INLINE_VISIBILITY
2245 size_type size() const _NOEXCEPT
2246 {return __size_;}
2247 _LIBCPP_INLINE_VISIBILITY
2248 bool empty() const _NOEXCEPT
2249 {return __size_ == 0;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002250 void reserve(size_type __n);
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002251 void shrink_to_fit() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002252
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002253 _LIBCPP_INLINE_VISIBILITY
2254 iterator begin() _NOEXCEPT
2255 {return __make_iter(0);}
2256 _LIBCPP_INLINE_VISIBILITY
2257 const_iterator begin() const _NOEXCEPT
2258 {return __make_iter(0);}
2259 _LIBCPP_INLINE_VISIBILITY
2260 iterator end() _NOEXCEPT
2261 {return __make_iter(__size_);}
2262 _LIBCPP_INLINE_VISIBILITY
2263 const_iterator end() const _NOEXCEPT
2264 {return __make_iter(__size_);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002265
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002266 _LIBCPP_INLINE_VISIBILITY
2267 reverse_iterator rbegin() _NOEXCEPT
2268 {return reverse_iterator(end());}
2269 _LIBCPP_INLINE_VISIBILITY
2270 const_reverse_iterator rbegin() const _NOEXCEPT
2271 {return const_reverse_iterator(end());}
2272 _LIBCPP_INLINE_VISIBILITY
2273 reverse_iterator rend() _NOEXCEPT
2274 {return reverse_iterator(begin());}
2275 _LIBCPP_INLINE_VISIBILITY
2276 const_reverse_iterator rend() const _NOEXCEPT
2277 {return const_reverse_iterator(begin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002278
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002279 _LIBCPP_INLINE_VISIBILITY
2280 const_iterator cbegin() const _NOEXCEPT
2281 {return __make_iter(0);}
2282 _LIBCPP_INLINE_VISIBILITY
2283 const_iterator cend() const _NOEXCEPT
2284 {return __make_iter(__size_);}
2285 _LIBCPP_INLINE_VISIBILITY
2286 const_reverse_iterator crbegin() const _NOEXCEPT
2287 {return rbegin();}
2288 _LIBCPP_INLINE_VISIBILITY
2289 const_reverse_iterator crend() const _NOEXCEPT
2290 {return rend();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002291
2292 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2293 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2294 reference at(size_type __n);
2295 const_reference at(size_type __n) const;
2296
2297 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2298 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2299 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2300 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2301
2302 void push_back(const value_type& __x);
Marshall Clow198a2a52013-08-13 23:54:12 +00002303#if _LIBCPP_STD_VER > 11
2304 template <class... _Args>
2305 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
2306 { push_back ( value_type ( _VSTD::forward<_Args>(__args)... )); }
2307#endif
2308
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002309 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2310
Marshall Clow198a2a52013-08-13 23:54:12 +00002311#if _LIBCPP_STD_VER > 11
2312 template <class... _Args>
2313 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
2314 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
2315#endif
2316
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002317 iterator insert(const_iterator __position, const value_type& __x);
2318 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2319 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2320 template <class _InputIterator>
2321 typename enable_if
2322 <
2323 __is_input_iterator <_InputIterator>::value &&
2324 !__is_forward_iterator<_InputIterator>::value,
2325 iterator
2326 >::type
2327 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2328 template <class _ForwardIterator>
2329 typename enable_if
2330 <
2331 __is_forward_iterator<_ForwardIterator>::value,
2332 iterator
2333 >::type
2334 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
Howard Hinnante3e32912011-08-12 21:56:02 +00002335#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002336 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002337 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2338 {return insert(__position, __il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +00002339#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002340
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00002341 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002342 iterator erase(const_iterator __first, const_iterator __last);
2343
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002344 _LIBCPP_INLINE_VISIBILITY
2345 void clear() _NOEXCEPT {__size_ = 0;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002346
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002347 void swap(vector&)
2348 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2349 __is_nothrow_swappable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002350
2351 void resize(size_type __sz, value_type __x = false);
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002352 void flip() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002353
2354 bool __invariants() const;
2355
2356private:
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00002357 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002358 void allocate(size_type __n);
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002359 void deallocate() _NOEXCEPT;
2360 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7f764502013-08-14 18:00:20 +00002361 static size_type __align_it(size_type __new_size) _NOEXCEPT
Marshall Clow0d1965d2014-07-28 15:02:42 +00002362 {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);};
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00002363 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2364 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002365 template <class _ForwardIterator>
2366 typename enable_if
2367 <
2368 __is_forward_iterator<_ForwardIterator>::value,
2369 void
2370 >::type
2371 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2372 void __append(size_type __n, const_reference __x);
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002373 _LIBCPP_INLINE_VISIBILITY
2374 reference __make_ref(size_type __pos) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002375 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002376 _LIBCPP_INLINE_VISIBILITY
2377 const_reference __make_ref(size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002378 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002379 _LIBCPP_INLINE_VISIBILITY
2380 iterator __make_iter(size_type __pos) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002381 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002382 _LIBCPP_INLINE_VISIBILITY
2383 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002384 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002385 _LIBCPP_INLINE_VISIBILITY
2386 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002387 {return begin() + (__p - cbegin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002388
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002390 void __copy_assign_alloc(const vector& __v)
2391 {__copy_assign_alloc(__v, integral_constant<bool,
2392 __storage_traits::propagate_on_container_copy_assignment::value>());}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002393 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002394 void __copy_assign_alloc(const vector& __c, true_type)
2395 {
2396 if (__alloc() != __c.__alloc())
2397 deallocate();
2398 __alloc() = __c.__alloc();
2399 }
2400
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002401 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +00002402 void __copy_assign_alloc(const vector&, false_type)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002403 {}
2404
2405 void __move_assign(vector& __c, false_type);
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002406 void __move_assign(vector& __c, true_type)
2407 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002409 void __move_assign_alloc(vector& __c)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002410 _NOEXCEPT_(
2411 !__storage_traits::propagate_on_container_move_assignment::value ||
2412 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002413 {__move_assign_alloc(__c, integral_constant<bool,
2414 __storage_traits::propagate_on_container_move_assignment::value>());}
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002415 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant9cbee432011-09-02 20:42:31 +00002416 void __move_assign_alloc(vector& __c, true_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002417 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002418 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00002419 __alloc() = _VSTD::move(__c.__alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002420 }
2421
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002422 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +00002423 void __move_assign_alloc(vector&, false_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002424 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002425 {}
2426
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002427 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002428 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002429 _NOEXCEPT_(
2430 !__storage_traits::propagate_on_container_swap::value ||
2431 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002432 {__swap_alloc(__x, __y, integral_constant<bool,
2433 __storage_traits::propagate_on_container_swap::value>());}
2434
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002435 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002436 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002437 _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002438 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00002439 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002440 swap(__x, __y);
2441 }
Howard Hinnantee6ccd02010-09-23 18:58:28 +00002442 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantec3773c2011-12-01 20:21:04 +00002443 static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002444 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002445 {}
2446
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002447 size_t __hash_code() const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002448
2449 friend class __bit_reference<vector>;
2450 friend class __bit_const_reference<vector>;
2451 friend class __bit_iterator<vector, false>;
2452 friend class __bit_iterator<vector, true>;
Howard Hinnant4ae952a2012-08-17 17:10:18 +00002453 friend struct __bit_array<vector>;
Howard Hinnant0f678bd2013-08-12 18:38:34 +00002454 friend struct _LIBCPP_TYPE_VIS_ONLY hash<vector>;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002455};
2456
2457template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002458inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002459void
2460vector<bool, _Allocator>::__invalidate_all_iterators()
2461{
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002462}
2463
2464// Allocate space for __n objects
2465// throws length_error if __n > max_size()
2466// throws (probably bad_alloc) if memory run out
2467// Precondition: __begin_ == __end_ == __cap() == 0
2468// Precondition: __n > 0
2469// Postcondition: capacity() == __n
2470// Postcondition: size() == 0
2471template <class _Allocator>
2472void
2473vector<bool, _Allocator>::allocate(size_type __n)
2474{
2475 if (__n > max_size())
2476 this->__throw_length_error();
2477 __n = __external_cap_to_internal(__n);
2478 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2479 this->__size_ = 0;
2480 this->__cap() = __n;
2481}
2482
2483template <class _Allocator>
2484void
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002485vector<bool, _Allocator>::deallocate() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002486{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002487 if (this->__begin_ != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002488 {
2489 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2490 __invalidate_all_iterators();
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002491 this->__begin_ = nullptr;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002492 this->__size_ = this->__cap() = 0;
2493 }
2494}
2495
2496template <class _Allocator>
2497typename vector<bool, _Allocator>::size_type
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002498vector<bool, _Allocator>::max_size() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002499{
2500 size_type __amax = __storage_traits::max_size(__alloc());
2501 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2502 if (__nmax / __bits_per_word <= __amax)
2503 return __nmax;
2504 return __internal_cap_to_external(__amax);
2505}
2506
2507// Precondition: __new_size > capacity()
2508template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002509inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002510typename vector<bool, _Allocator>::size_type
2511vector<bool, _Allocator>::__recommend(size_type __new_size) const
2512{
2513 const size_type __ms = max_size();
2514 if (__new_size > __ms)
2515 this->__throw_length_error();
2516 const size_type __cap = capacity();
2517 if (__cap >= __ms / 2)
2518 return __ms;
Howard Hinnant7f764502013-08-14 18:00:20 +00002519 return _VSTD::max(2*__cap, __align_it(__new_size));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002520}
2521
2522// Default constructs __n objects starting at __end_
2523// Precondition: __n > 0
2524// Precondition: size() + __n <= capacity()
2525// Postcondition: size() == size() + __n
2526template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002527inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002528void
2529vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2530{
2531 size_type __old_size = this->__size_;
2532 this->__size_ += __n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00002533 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002534}
2535
2536template <class _Allocator>
2537template <class _ForwardIterator>
2538typename enable_if
2539<
2540 __is_forward_iterator<_ForwardIterator>::value,
2541 void
2542>::type
2543vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2544{
2545 size_type __old_size = this->__size_;
Howard Hinnant0949eed2011-06-30 21:18:19 +00002546 this->__size_ += _VSTD::distance(__first, __last);
2547 _VSTD::copy(__first, __last, __make_iter(__old_size));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002548}
2549
2550template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002551inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002552vector<bool, _Allocator>::vector()
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002553 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002554 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002555 __size_(0),
2556 __cap_alloc_(0)
2557{
2558}
2559
2560template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002561inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002562vector<bool, _Allocator>::vector(const allocator_type& __a)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002563 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002564 __size_(0),
2565 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2566{
2567}
2568
2569template <class _Allocator>
2570vector<bool, _Allocator>::vector(size_type __n)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002571 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002572 __size_(0),
2573 __cap_alloc_(0)
2574{
2575 if (__n > 0)
2576 {
2577 allocate(__n);
2578 __construct_at_end(__n, false);
2579 }
2580}
2581
Marshall Clowa49a2c92013-09-14 00:47:59 +00002582#if _LIBCPP_STD_VER > 11
2583template <class _Allocator>
2584vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2585 : __begin_(nullptr),
2586 __size_(0),
2587 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2588{
2589 if (__n > 0)
2590 {
2591 allocate(__n);
2592 __construct_at_end(__n, false);
2593 }
2594}
2595#endif
2596
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002597template <class _Allocator>
2598vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002599 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002600 __size_(0),
2601 __cap_alloc_(0)
2602{
2603 if (__n > 0)
2604 {
2605 allocate(__n);
2606 __construct_at_end(__n, __x);
2607 }
2608}
2609
2610template <class _Allocator>
2611vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002612 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002613 __size_(0),
2614 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2615{
2616 if (__n > 0)
2617 {
2618 allocate(__n);
2619 __construct_at_end(__n, __x);
2620 }
2621}
2622
2623template <class _Allocator>
2624template <class _InputIterator>
2625vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2626 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2627 !__is_forward_iterator<_InputIterator>::value>::type*)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002628 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002629 __size_(0),
2630 __cap_alloc_(0)
2631{
2632#ifndef _LIBCPP_NO_EXCEPTIONS
2633 try
2634 {
Howard Hinnant324bb032010-08-22 00:02:43 +00002635#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002636 for (; __first != __last; ++__first)
2637 push_back(*__first);
2638#ifndef _LIBCPP_NO_EXCEPTIONS
2639 }
2640 catch (...)
2641 {
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002642 if (__begin_ != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002643 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2644 __invalidate_all_iterators();
2645 throw;
2646 }
Howard Hinnant324bb032010-08-22 00:02:43 +00002647#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002648}
2649
2650template <class _Allocator>
2651template <class _InputIterator>
2652vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2653 typename enable_if<__is_input_iterator <_InputIterator>::value &&
2654 !__is_forward_iterator<_InputIterator>::value>::type*)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002655 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002656 __size_(0),
2657 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2658{
2659#ifndef _LIBCPP_NO_EXCEPTIONS
2660 try
2661 {
Howard Hinnant324bb032010-08-22 00:02:43 +00002662#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002663 for (; __first != __last; ++__first)
2664 push_back(*__first);
2665#ifndef _LIBCPP_NO_EXCEPTIONS
2666 }
2667 catch (...)
2668 {
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002669 if (__begin_ != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002670 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2671 __invalidate_all_iterators();
2672 throw;
2673 }
Howard Hinnant324bb032010-08-22 00:02:43 +00002674#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002675}
2676
2677template <class _Allocator>
2678template <class _ForwardIterator>
2679vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2680 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002681 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002682 __size_(0),
2683 __cap_alloc_(0)
2684{
Howard Hinnant0949eed2011-06-30 21:18:19 +00002685 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002686 if (__n > 0)
2687 {
2688 allocate(__n);
2689 __construct_at_end(__first, __last);
2690 }
2691}
2692
2693template <class _Allocator>
2694template <class _ForwardIterator>
2695vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2696 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002697 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002698 __size_(0),
2699 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2700{
Howard Hinnant0949eed2011-06-30 21:18:19 +00002701 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002702 if (__n > 0)
2703 {
2704 allocate(__n);
2705 __construct_at_end(__first, __last);
2706 }
2707}
2708
Howard Hinnante3e32912011-08-12 21:56:02 +00002709#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2710
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002711template <class _Allocator>
2712vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002713 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002714 __size_(0),
2715 __cap_alloc_(0)
2716{
2717 size_type __n = static_cast<size_type>(__il.size());
2718 if (__n > 0)
2719 {
2720 allocate(__n);
2721 __construct_at_end(__il.begin(), __il.end());
2722 }
2723}
2724
2725template <class _Allocator>
2726vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002727 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002728 __size_(0),
2729 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2730{
2731 size_type __n = static_cast<size_type>(__il.size());
2732 if (__n > 0)
2733 {
2734 allocate(__n);
2735 __construct_at_end(__il.begin(), __il.end());
2736 }
2737}
2738
Howard Hinnante3e32912011-08-12 21:56:02 +00002739#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2740
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002741template <class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002742vector<bool, _Allocator>::~vector()
2743{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002744 if (__begin_ != nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002745 __storage_traits::deallocate(__alloc(), __begin_, __cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002746 __invalidate_all_iterators();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002747}
2748
2749template <class _Allocator>
2750vector<bool, _Allocator>::vector(const vector& __v)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002751 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002752 __size_(0),
2753 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2754{
2755 if (__v.size() > 0)
2756 {
2757 allocate(__v.size());
2758 __construct_at_end(__v.begin(), __v.end());
2759 }
2760}
2761
2762template <class _Allocator>
2763vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002764 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002765 __size_(0),
2766 __cap_alloc_(0, __a)
2767{
2768 if (__v.size() > 0)
2769 {
2770 allocate(__v.size());
2771 __construct_at_end(__v.begin(), __v.end());
2772 }
2773}
2774
2775template <class _Allocator>
2776vector<bool, _Allocator>&
2777vector<bool, _Allocator>::operator=(const vector& __v)
2778{
2779 if (this != &__v)
2780 {
2781 __copy_assign_alloc(__v);
2782 if (__v.__size_)
2783 {
2784 if (__v.__size_ > capacity())
2785 {
2786 deallocate();
2787 allocate(__v.__size_);
2788 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00002789 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002790 }
2791 __size_ = __v.__size_;
2792 }
2793 return *this;
2794}
2795
Howard Hinnant73d21a42010-09-04 23:28:19 +00002796#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2797
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002798template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002799inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002800vector<bool, _Allocator>::vector(vector&& __v)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002801 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002802 : __begin_(__v.__begin_),
2803 __size_(__v.__size_),
2804 __cap_alloc_(__v.__cap_alloc_)
2805{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002806 __v.__begin_ = nullptr;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002807 __v.__size_ = 0;
2808 __v.__cap() = 0;
2809}
2810
2811template <class _Allocator>
2812vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00002813 : __begin_(nullptr),
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002814 __size_(0),
2815 __cap_alloc_(0, __a)
2816{
2817 if (__a == allocator_type(__v.__alloc()))
2818 {
2819 this->__begin_ = __v.__begin_;
2820 this->__size_ = __v.__size_;
2821 this->__cap() = __v.__cap();
2822 __v.__begin_ = nullptr;
2823 __v.__cap() = __v.__size_ = 0;
2824 }
2825 else if (__v.size() > 0)
2826 {
2827 allocate(__v.size());
2828 __construct_at_end(__v.begin(), __v.end());
2829 }
2830}
2831
2832template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00002833inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002834vector<bool, _Allocator>&
2835vector<bool, _Allocator>::operator=(vector&& __v)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002836 _NOEXCEPT_(
2837 __alloc_traits::propagate_on_container_move_assignment::value &&
2838 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002839{
2840 __move_assign(__v, integral_constant<bool,
2841 __storage_traits::propagate_on_container_move_assignment::value>());
Argyrios Kyrtzidis1dc6f7a2012-10-13 02:03:45 +00002842 return *this;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002843}
2844
2845template <class _Allocator>
2846void
2847vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2848{
2849 if (__alloc() != __c.__alloc())
2850 assign(__c.begin(), __c.end());
2851 else
2852 __move_assign(__c, true_type());
2853}
2854
2855template <class _Allocator>
2856void
2857vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002858 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002859{
2860 deallocate();
Marshall Clowdb5e54d2014-07-21 15:15:15 +00002861 __move_assign_alloc(__c);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002862 this->__begin_ = __c.__begin_;
2863 this->__size_ = __c.__size_;
2864 this->__cap() = __c.__cap();
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002865 __c.__begin_ = nullptr;
2866 __c.__cap() = __c.__size_ = 0;
2867}
Howard Hinnant73d21a42010-09-04 23:28:19 +00002868
2869#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002870
2871template <class _Allocator>
2872void
2873vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2874{
2875 __size_ = 0;
2876 if (__n > 0)
2877 {
2878 size_type __c = capacity();
2879 if (__n <= __c)
2880 __size_ = __n;
2881 else
2882 {
2883 vector __v(__alloc());
2884 __v.reserve(__recommend(__n));
2885 __v.__size_ = __n;
2886 swap(__v);
2887 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00002888 _VSTD::fill_n(begin(), __n, __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002889 }
2890}
2891
2892template <class _Allocator>
2893template <class _InputIterator>
2894typename enable_if
2895<
2896 __is_input_iterator<_InputIterator>::value &&
2897 !__is_forward_iterator<_InputIterator>::value,
2898 void
2899>::type
2900vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2901{
2902 clear();
2903 for (; __first != __last; ++__first)
2904 push_back(*__first);
2905}
2906
2907template <class _Allocator>
2908template <class _ForwardIterator>
2909typename enable_if
2910<
2911 __is_forward_iterator<_ForwardIterator>::value,
2912 void
2913>::type
2914vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2915{
2916 clear();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002917 difference_type __n = _VSTD::distance(__first, __last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002918 if (__n)
2919 {
2920 if (__n > capacity())
2921 {
2922 deallocate();
2923 allocate(__n);
2924 }
2925 __construct_at_end(__first, __last);
2926 }
2927}
2928
2929template <class _Allocator>
2930void
2931vector<bool, _Allocator>::reserve(size_type __n)
2932{
2933 if (__n > capacity())
2934 {
2935 vector __v(this->__alloc());
2936 __v.allocate(__n);
2937 __v.__construct_at_end(this->begin(), this->end());
2938 swap(__v);
2939 __invalidate_all_iterators();
2940 }
2941}
2942
2943template <class _Allocator>
2944void
Howard Hinnantd1d27a42011-06-03 19:40:40 +00002945vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002946{
2947 if (__external_cap_to_internal(size()) > __cap())
2948 {
2949#ifndef _LIBCPP_NO_EXCEPTIONS
2950 try
2951 {
Howard Hinnant324bb032010-08-22 00:02:43 +00002952#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002953 vector(*this, allocator_type(__alloc())).swap(*this);
2954#ifndef _LIBCPP_NO_EXCEPTIONS
2955 }
2956 catch (...)
2957 {
2958 }
Howard Hinnant324bb032010-08-22 00:02:43 +00002959#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002960 }
2961}
2962
2963template <class _Allocator>
2964typename vector<bool, _Allocator>::reference
2965vector<bool, _Allocator>::at(size_type __n)
2966{
2967 if (__n >= size())
2968 this->__throw_out_of_range();
2969 return (*this)[__n];
2970}
2971
2972template <class _Allocator>
2973typename vector<bool, _Allocator>::const_reference
2974vector<bool, _Allocator>::at(size_type __n) const
2975{
2976 if (__n >= size())
2977 this->__throw_out_of_range();
2978 return (*this)[__n];
2979}
2980
2981template <class _Allocator>
2982void
2983vector<bool, _Allocator>::push_back(const value_type& __x)
2984{
2985 if (this->__size_ == this->capacity())
2986 reserve(__recommend(this->__size_ + 1));
2987 ++this->__size_;
2988 back() = __x;
2989}
2990
2991template <class _Allocator>
2992typename vector<bool, _Allocator>::iterator
2993vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
2994{
2995 iterator __r;
2996 if (size() < capacity())
2997 {
2998 const_iterator __old_end = end();
2999 ++__size_;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003000 _VSTD::copy_backward(__position, __old_end, end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003001 __r = __const_iterator_cast(__position);
3002 }
3003 else
3004 {
3005 vector __v(__alloc());
3006 __v.reserve(__recommend(__size_ + 1));
3007 __v.__size_ = __size_ + 1;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003008 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3009 _VSTD::copy_backward(__position, cend(), __v.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003010 swap(__v);
3011 }
3012 *__r = __x;
3013 return __r;
3014}
3015
3016template <class _Allocator>
3017typename vector<bool, _Allocator>::iterator
3018vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
3019{
3020 iterator __r;
3021 size_type __c = capacity();
3022 if (__n <= __c && size() <= __c - __n)
3023 {
3024 const_iterator __old_end = end();
3025 __size_ += __n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003026 _VSTD::copy_backward(__position, __old_end, end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003027 __r = __const_iterator_cast(__position);
3028 }
3029 else
3030 {
3031 vector __v(__alloc());
3032 __v.reserve(__recommend(__size_ + __n));
3033 __v.__size_ = __size_ + __n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003034 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3035 _VSTD::copy_backward(__position, cend(), __v.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003036 swap(__v);
3037 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00003038 _VSTD::fill_n(__r, __n, __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003039 return __r;
3040}
3041
3042template <class _Allocator>
3043template <class _InputIterator>
3044typename enable_if
3045<
3046 __is_input_iterator <_InputIterator>::value &&
3047 !__is_forward_iterator<_InputIterator>::value,
3048 typename vector<bool, _Allocator>::iterator
3049>::type
3050vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
3051{
3052 difference_type __off = __position - begin();
3053 iterator __p = __const_iterator_cast(__position);
3054 iterator __old_end = end();
3055 for (; size() != capacity() && __first != __last; ++__first)
3056 {
3057 ++this->__size_;
3058 back() = *__first;
3059 }
3060 vector __v(__alloc());
3061 if (__first != __last)
3062 {
3063#ifndef _LIBCPP_NO_EXCEPTIONS
3064 try
3065 {
Howard Hinnant324bb032010-08-22 00:02:43 +00003066#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003067 __v.assign(__first, __last);
3068 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
3069 difference_type __old_p = __p - begin();
3070 reserve(__recommend(size() + __v.size()));
3071 __p = begin() + __old_p;
3072 __old_end = begin() + __old_size;
3073#ifndef _LIBCPP_NO_EXCEPTIONS
3074 }
3075 catch (...)
3076 {
3077 erase(__old_end, end());
3078 throw;
3079 }
Howard Hinnant324bb032010-08-22 00:02:43 +00003080#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003081 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00003082 __p = _VSTD::rotate(__p, __old_end, end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003083 insert(__p, __v.begin(), __v.end());
3084 return begin() + __off;
3085}
3086
3087template <class _Allocator>
3088template <class _ForwardIterator>
3089typename enable_if
3090<
3091 __is_forward_iterator<_ForwardIterator>::value,
3092 typename vector<bool, _Allocator>::iterator
3093>::type
3094vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3095{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003096 difference_type __n = _VSTD::distance(__first, __last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003097 iterator __r;
3098 size_type __c = capacity();
3099 if (__n <= __c && size() <= __c - __n)
3100 {
3101 const_iterator __old_end = end();
3102 __size_ += __n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003103 _VSTD::copy_backward(__position, __old_end, end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003104 __r = __const_iterator_cast(__position);
3105 }
3106 else
3107 {
3108 vector __v(__alloc());
3109 __v.reserve(__recommend(__size_ + __n));
3110 __v.__size_ = __size_ + __n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003111 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3112 _VSTD::copy_backward(__position, cend(), __v.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003113 swap(__v);
3114 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00003115 _VSTD::copy(__first, __last, __r);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003116 return __r;
3117}
3118
3119template <class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003120inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003121typename vector<bool, _Allocator>::iterator
3122vector<bool, _Allocator>::erase(const_iterator __position)
3123{
3124 iterator __r = __const_iterator_cast(__position);
Howard Hinnant0949eed2011-06-30 21:18:19 +00003125 _VSTD::copy(__position + 1, this->cend(), __r);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003126 --__size_;
3127 return __r;
3128}
3129
3130template <class _Allocator>
3131typename vector<bool, _Allocator>::iterator
3132vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3133{
3134 iterator __r = __const_iterator_cast(__first);
3135 difference_type __d = __last - __first;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003136 _VSTD::copy(__last, this->cend(), __r);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003137 __size_ -= __d;
3138 return __r;
3139}
3140
3141template <class _Allocator>
3142void
3143vector<bool, _Allocator>::swap(vector& __x)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00003144 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3145 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003146{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003147 _VSTD::swap(this->__begin_, __x.__begin_);
3148 _VSTD::swap(this->__size_, __x.__size_);
3149 _VSTD::swap(this->__cap(), __x.__cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003150 __swap_alloc(this->__alloc(), __x.__alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003151}
3152
Howard Hinnant324bb032010-08-22 00:02:43 +00003153template <class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003154void
3155vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3156{
3157 size_type __cs = size();
3158 if (__cs < __sz)
3159 {
3160 iterator __r;
3161 size_type __c = capacity();
3162 size_type __n = __sz - __cs;
3163 if (__n <= __c && __cs <= __c - __n)
3164 {
3165 __r = end();
3166 __size_ += __n;
3167 }
3168 else
3169 {
3170 vector __v(__alloc());
3171 __v.reserve(__recommend(__size_ + __n));
3172 __v.__size_ = __size_ + __n;
Howard Hinnant0949eed2011-06-30 21:18:19 +00003173 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003174 swap(__v);
3175 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00003176 _VSTD::fill_n(__r, __n, __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003177 }
3178 else
3179 __size_ = __sz;
3180}
3181
Howard Hinnant324bb032010-08-22 00:02:43 +00003182template <class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003183void
Howard Hinnantd1d27a42011-06-03 19:40:40 +00003184vector<bool, _Allocator>::flip() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003185{
3186 // do middle whole words
3187 size_type __n = __size_;
3188 __storage_pointer __p = __begin_;
3189 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3190 *__p = ~*__p;
3191 // do last partial word
3192 if (__n > 0)
3193 {
3194 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3195 __storage_type __b = *__p & __m;
3196 *__p &= ~__m;
3197 *__p |= ~__b & __m;
3198 }
3199}
3200
Howard Hinnant324bb032010-08-22 00:02:43 +00003201template <class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003202bool
3203vector<bool, _Allocator>::__invariants() const
3204{
Howard Hinnant2c39cbe2013-06-27 19:35:32 +00003205 if (this->__begin_ == nullptr)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003206 {
3207 if (this->__size_ != 0 || this->__cap() != 0)
3208 return false;
3209 }
3210 else
3211 {
3212 if (this->__cap() == 0)
3213 return false;
3214 if (this->__size_ > this->capacity())
3215 return false;
3216 }
3217 return true;
3218}
3219
Howard Hinnant324bb032010-08-22 00:02:43 +00003220template <class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003221size_t
Howard Hinnantd1d27a42011-06-03 19:40:40 +00003222vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003223{
3224 size_t __h = 0;
3225 // do middle whole words
3226 size_type __n = __size_;
3227 __storage_pointer __p = __begin_;
3228 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3229 __h ^= *__p;
3230 // do last partial word
3231 if (__n > 0)
3232 {
3233 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3234 __h ^= *__p & __m;
3235 }
3236 return __h;
3237}
3238
3239template <class _Allocator>
Howard Hinnant0f678bd2013-08-12 18:38:34 +00003240struct _LIBCPP_TYPE_VIS_ONLY hash<vector<bool, _Allocator> >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003241 : public unary_function<vector<bool, _Allocator>, size_t>
3242{
Howard Hinnantee6ccd02010-09-23 18:58:28 +00003243 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantd1d27a42011-06-03 19:40:40 +00003244 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003245 {return __vec.__hash_code();}
3246};
3247
3248template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003249inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003250bool
3251operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3252{
3253 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003254 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003255}
3256
3257template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003258inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003259bool
3260operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3261{
3262 return !(__x == __y);
3263}
3264
3265template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003266inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003267bool
3268operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3269{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003270 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003271}
3272
3273template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003274inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003275bool
3276operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3277{
3278 return __y < __x;
3279}
3280
3281template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003282inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003283bool
3284operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3285{
3286 return !(__x < __y);
3287}
3288
3289template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003290inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003291bool
3292operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3293{
3294 return !(__y < __x);
3295}
3296
3297template <class _Tp, class _Allocator>
Howard Hinnant1e564242013-10-04 22:09:00 +00003298inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003299void
3300swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
Howard Hinnantd1d27a42011-06-03 19:40:40 +00003301 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003302{
3303 __x.swap(__y);
3304}
3305
3306_LIBCPP_END_NAMESPACE_STD
3307
3308#endif // _LIBCPP_VECTOR