root / lab4 / .minix-src / include / c++ / vector
History | View | Annotate | Download (106 KB)
1 | 13 | up20180614 | // -*- C++ -*- |
---|---|---|---|
2 | //===------------------------------ vector --------------------------------===// |
||
3 | // |
||
4 | // The LLVM Compiler Infrastructure |
||
5 | // |
||
6 | // This file is dual licensed under the MIT and the University of Illinois Open |
||
7 | // Source Licenses. See LICENSE.TXT for details. |
||
8 | // |
||
9 | //===----------------------------------------------------------------------===// |
||
10 | |||
11 | #ifndef _LIBCPP_VECTOR |
||
12 | #define _LIBCPP_VECTOR |
||
13 | |||
14 | /* |
||
15 | vector synopsis |
||
16 | |||
17 | namespace std |
||
18 | { |
||
19 | |||
20 | template <class T, class Allocator = allocator<T> > |
||
21 | class vector |
||
22 | { |
||
23 | public: |
||
24 | typedef T value_type; |
||
25 | typedef Allocator allocator_type; |
||
26 | typedef typename allocator_type::reference reference; |
||
27 | typedef typename allocator_type::const_reference const_reference; |
||
28 | typedef implementation-defined iterator; |
||
29 | typedef implementation-defined const_iterator; |
||
30 | typedef typename allocator_type::size_type size_type; |
||
31 | typedef typename allocator_type::difference_type difference_type; |
||
32 | typedef typename allocator_type::pointer pointer; |
||
33 | typedef typename allocator_type::const_pointer const_pointer; |
||
34 | typedef std::reverse_iterator<iterator> reverse_iterator; |
||
35 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
||
36 | |||
37 | vector() |
||
38 | noexcept(is_nothrow_default_constructible<allocator_type>::value); |
||
39 | explicit vector(const allocator_type&); |
||
40 | explicit vector(size_type n); |
||
41 | explicit vector(size_type n, const allocator_type&); // C++14 |
||
42 | 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); |
||
46 | vector(vector&& x) |
||
47 | noexcept(is_nothrow_move_constructible<allocator_type>::value); |
||
48 | 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); |
||
52 | vector& operator=(vector&& x) |
||
53 | noexcept( |
||
54 | allocator_type::propagate_on_container_move_assignment::value || |
||
55 | allocator_type::is_always_equal::value); // C++17 |
||
56 | 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 | |||
62 | allocator_type get_allocator() const noexcept; |
||
63 | |||
64 | iterator begin() noexcept; |
||
65 | const_iterator begin() const noexcept; |
||
66 | iterator end() noexcept; |
||
67 | const_iterator end() const noexcept; |
||
68 | |||
69 | reverse_iterator rbegin() noexcept; |
||
70 | const_reverse_iterator rbegin() const noexcept; |
||
71 | reverse_iterator rend() noexcept; |
||
72 | const_reverse_iterator rend() const noexcept; |
||
73 | |||
74 | 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; |
||
78 | |||
79 | size_type size() const noexcept; |
||
80 | size_type max_size() const noexcept; |
||
81 | size_type capacity() const noexcept; |
||
82 | bool empty() const noexcept; |
||
83 | void reserve(size_type n); |
||
84 | void shrink_to_fit() noexcept; |
||
85 | |||
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 | |||
96 | value_type* data() noexcept; |
||
97 | const value_type* data() const noexcept; |
||
98 | |||
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 | |||
116 | void clear() noexcept; |
||
117 | |||
118 | void resize(size_type sz); |
||
119 | void resize(size_type sz, const value_type& c); |
||
120 | |||
121 | void swap(vector&) |
||
122 | noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value || |
||
123 | allocator_traits<allocator_type>::is_always_equal::value); // C++17 |
||
124 | |||
125 | bool __invariants() const; |
||
126 | }; |
||
127 | |||
128 | template <class Allocator = allocator<T> > |
||
129 | class vector<bool, Allocator> |
||
130 | { |
||
131 | public: |
||
132 | typedef bool value_type; |
||
133 | 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: |
||
146 | 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; |
||
152 | }; |
||
153 | |||
154 | class const_reference |
||
155 | { |
||
156 | public: |
||
157 | const_reference(const reference&) noexcept; |
||
158 | operator bool() const noexcept; |
||
159 | const_iterator operator&() const noexcept; |
||
160 | }; |
||
161 | |||
162 | vector() |
||
163 | noexcept(is_nothrow_default_constructible<allocator_type>::value); |
||
164 | explicit vector(const allocator_type&); |
||
165 | 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()); |
||
167 | template <class InputIterator> |
||
168 | vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); |
||
169 | vector(const vector& x); |
||
170 | vector(vector&& x) |
||
171 | noexcept(is_nothrow_move_constructible<allocator_type>::value); |
||
172 | 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); |
||
176 | vector& operator=(vector&& x) |
||
177 | noexcept( |
||
178 | allocator_type::propagate_on_container_move_assignment::value || |
||
179 | allocator_type::is_always_equal::value); // C++17 |
||
180 | 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 | |||
186 | allocator_type get_allocator() const noexcept; |
||
187 | |||
188 | iterator begin() noexcept; |
||
189 | const_iterator begin() const noexcept; |
||
190 | iterator end() noexcept; |
||
191 | const_iterator end() const noexcept; |
||
192 | |||
193 | reverse_iterator rbegin() noexcept; |
||
194 | const_reverse_iterator rbegin() const noexcept; |
||
195 | reverse_iterator rend() noexcept; |
||
196 | const_reverse_iterator rend() const noexcept; |
||
197 | |||
198 | 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; |
||
202 | |||
203 | size_type size() const noexcept; |
||
204 | size_type max_size() const noexcept; |
||
205 | size_type capacity() const noexcept; |
||
206 | bool empty() const noexcept; |
||
207 | void reserve(size_type n); |
||
208 | void shrink_to_fit() noexcept; |
||
209 | |||
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); |
||
221 | template <class... Args> void emplace_back(Args&&... args); // C++14 |
||
222 | void pop_back(); |
||
223 | |||
224 | template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14 |
||
225 | 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 | |||
234 | void clear() noexcept; |
||
235 | |||
236 | void resize(size_type sz); |
||
237 | void resize(size_type sz, value_type x); |
||
238 | |||
239 | void swap(vector&) |
||
240 | noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value || |
||
241 | allocator_traits<allocator_type>::is_always_equal::value); // C++17 |
||
242 | void flip() noexcept; |
||
243 | |||
244 | bool __invariants() const; |
||
245 | }; |
||
246 | |||
247 | template <class Allocator> struct hash<std::vector<bool, Allocator>>; |
||
248 | |||
249 | template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); |
||
250 | template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); |
||
251 | template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); |
||
252 | template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); |
||
253 | template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); |
||
254 | template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); |
||
255 | |||
256 | template <class T, class Allocator> |
||
257 | void swap(vector<T,Allocator>& x, vector<T,Allocator>& y) |
||
258 | noexcept(noexcept(x.swap(y))); |
||
259 | |||
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> |
||
276 | |||
277 | #include <__undef_min_max> |
||
278 | |||
279 | #include <__debug> |
||
280 | |||
281 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
||
282 | #pragma GCC system_header |
||
283 | #endif |
||
284 | |||
285 | _LIBCPP_BEGIN_NAMESPACE_STD |
||
286 | |||
287 | template <bool> |
||
288 | class __vector_base_common |
||
289 | { |
||
290 | protected: |
||
291 | _LIBCPP_ALWAYS_INLINE __vector_base_common() {} |
||
292 | void __throw_length_error() const; |
||
293 | void __throw_out_of_range() const; |
||
294 | }; |
||
295 | |||
296 | template <bool __b> |
||
297 | void |
||
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 | |||
307 | template <bool __b> |
||
308 | void |
||
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 | |||
318 | #ifdef _LIBCPP_MSVC |
||
319 | #pragma warning( push ) |
||
320 | #pragma warning( disable: 4231 ) |
||
321 | #endif // _LIBCPP_MSVC |
||
322 | _LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS __vector_base_common<true>) |
||
323 | #ifdef _LIBCPP_MSVC |
||
324 | #pragma warning( pop ) |
||
325 | #endif // _LIBCPP_MSVC |
||
326 | |||
327 | template <class _Tp, class _Allocator> |
||
328 | class __vector_base |
||
329 | : protected __vector_base_common<true> |
||
330 | { |
||
331 | protected: |
||
332 | typedef _Tp value_type; |
||
333 | 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 | |||
348 | _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();} |
||
360 | |||
361 | _LIBCPP_INLINE_VISIBILITY |
||
362 | __vector_base() |
||
363 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); |
||
364 | _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a); |
||
365 | ~__vector_base(); |
||
366 | |||
367 | _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_);} |
||
372 | |||
373 | _LIBCPP_INLINE_VISIBILITY |
||
374 | void __destruct_at_end(pointer __new_last) _NOEXCEPT; |
||
375 | |||
376 | _LIBCPP_INLINE_VISIBILITY |
||
377 | 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 | |||
381 | _LIBCPP_INLINE_VISIBILITY |
||
382 | void __move_assign_alloc(__vector_base& __c) |
||
383 | _NOEXCEPT_( |
||
384 | !__alloc_traits::propagate_on_container_move_assignment::value || |
||
385 | is_nothrow_move_assignable<allocator_type>::value) |
||
386 | {__move_assign_alloc(__c, integral_constant<bool, |
||
387 | __alloc_traits::propagate_on_container_move_assignment::value>());} |
||
388 | private: |
||
389 | _LIBCPP_INLINE_VISIBILITY |
||
390 | void __copy_assign_alloc(const __vector_base& __c, true_type) |
||
391 | { |
||
392 | if (__alloc() != __c.__alloc()) |
||
393 | { |
||
394 | clear(); |
||
395 | __alloc_traits::deallocate(__alloc(), __begin_, capacity()); |
||
396 | __begin_ = __end_ = __end_cap() = nullptr; |
||
397 | } |
||
398 | __alloc() = __c.__alloc(); |
||
399 | } |
||
400 | |||
401 | _LIBCPP_INLINE_VISIBILITY |
||
402 | void __copy_assign_alloc(const __vector_base&, false_type) |
||
403 | {} |
||
404 | |||
405 | _LIBCPP_INLINE_VISIBILITY |
||
406 | void __move_assign_alloc(__vector_base& __c, true_type) |
||
407 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) |
||
408 | { |
||
409 | __alloc() = _VSTD::move(__c.__alloc()); |
||
410 | } |
||
411 | |||
412 | _LIBCPP_INLINE_VISIBILITY |
||
413 | void __move_assign_alloc(__vector_base&, false_type) |
||
414 | _NOEXCEPT |
||
415 | {} |
||
416 | }; |
||
417 | |||
418 | template <class _Tp, class _Allocator> |
||
419 | inline _LIBCPP_INLINE_VISIBILITY |
||
420 | void |
||
421 | __vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT |
||
422 | { |
||
423 | while (__new_last != __end_) |
||
424 | __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_)); |
||
425 | } |
||
426 | |||
427 | template <class _Tp, class _Allocator> |
||
428 | inline _LIBCPP_INLINE_VISIBILITY |
||
429 | __vector_base<_Tp, _Allocator>::__vector_base() |
||
430 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) |
||
431 | : __begin_(nullptr), |
||
432 | __end_(nullptr), |
||
433 | __end_cap_(nullptr) |
||
434 | { |
||
435 | } |
||
436 | |||
437 | template <class _Tp, class _Allocator> |
||
438 | inline _LIBCPP_INLINE_VISIBILITY |
||
439 | __vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a) |
||
440 | : __begin_(nullptr), |
||
441 | __end_(nullptr), |
||
442 | __end_cap_(nullptr, __a) |
||
443 | { |
||
444 | } |
||
445 | |||
446 | template <class _Tp, class _Allocator> |
||
447 | __vector_base<_Tp, _Allocator>::~__vector_base() |
||
448 | { |
||
449 | if (__begin_ != nullptr) |
||
450 | { |
||
451 | clear(); |
||
452 | __alloc_traits::deallocate(__alloc(), __begin_, capacity()); |
||
453 | } |
||
454 | } |
||
455 | |||
456 | template <class _Tp, class _Allocator = allocator<_Tp> > |
||
457 | class _LIBCPP_TYPE_VIS_ONLY vector |
||
458 | : private __vector_base<_Tp, _Allocator> |
||
459 | { |
||
460 | private: |
||
461 | typedef __vector_base<_Tp, _Allocator> __base; |
||
462 | typedef allocator<_Tp> __default_allocator_type; |
||
463 | public: |
||
464 | typedef vector __self; |
||
465 | typedef _Tp value_type; |
||
466 | typedef _Allocator allocator_type; |
||
467 | typedef typename __base::__alloc_traits __alloc_traits; |
||
468 | typedef typename __base::reference reference; |
||
469 | typedef typename __base::const_reference const_reference; |
||
470 | typedef typename __base::size_type size_type; |
||
471 | typedef typename __base::difference_type difference_type; |
||
472 | typedef typename __base::pointer pointer; |
||
473 | typedef typename __base::const_pointer const_pointer; |
||
474 | typedef __wrap_iter<pointer> iterator; |
||
475 | typedef __wrap_iter<const_pointer> const_iterator; |
||
476 | typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
||
477 | typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; |
||
478 | |||
479 | static_assert((is_same<typename allocator_type::value_type, value_type>::value), |
||
480 | "Allocator::value_type must be same type as value_type"); |
||
481 | |||
482 | _LIBCPP_INLINE_VISIBILITY |
||
483 | vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) |
||
484 | { |
||
485 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
486 | __get_db()->__insert_c(this); |
||
487 | #endif |
||
488 | } |
||
489 | _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) |
||
490 | #if _LIBCPP_STD_VER <= 14 |
||
491 | _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) |
||
492 | #else |
||
493 | _NOEXCEPT |
||
494 | #endif |
||
495 | : __base(__a) |
||
496 | { |
||
497 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
498 | __get_db()->__insert_c(this); |
||
499 | #endif |
||
500 | } |
||
501 | explicit vector(size_type __n); |
||
502 | #if _LIBCPP_STD_VER > 11 |
||
503 | explicit vector(size_type __n, const allocator_type& __a); |
||
504 | #endif |
||
505 | vector(size_type __n, const_reference __x); |
||
506 | vector(size_type __n, const_reference __x, const allocator_type& __a); |
||
507 | template <class _InputIterator> |
||
508 | vector(_InputIterator __first, |
||
509 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
510 | !__is_forward_iterator<_InputIterator>::value && |
||
511 | is_constructible< |
||
512 | value_type, |
||
513 | typename iterator_traits<_InputIterator>::reference>::value, |
||
514 | _InputIterator>::type __last); |
||
515 | template <class _InputIterator> |
||
516 | vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, |
||
517 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
518 | !__is_forward_iterator<_InputIterator>::value && |
||
519 | is_constructible< |
||
520 | value_type, |
||
521 | typename iterator_traits<_InputIterator>::reference>::value>::type* = 0); |
||
522 | template <class _ForwardIterator> |
||
523 | vector(_ForwardIterator __first, |
||
524 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value && |
||
525 | is_constructible< |
||
526 | value_type, |
||
527 | typename iterator_traits<_ForwardIterator>::reference>::value, |
||
528 | _ForwardIterator>::type __last); |
||
529 | template <class _ForwardIterator> |
||
530 | vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, |
||
531 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value && |
||
532 | is_constructible< |
||
533 | value_type, |
||
534 | typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0); |
||
535 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
536 | _LIBCPP_INLINE_VISIBILITY |
||
537 | vector(initializer_list<value_type> __il); |
||
538 | _LIBCPP_INLINE_VISIBILITY |
||
539 | vector(initializer_list<value_type> __il, const allocator_type& __a); |
||
540 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
541 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
542 | _LIBCPP_INLINE_VISIBILITY |
||
543 | ~vector() |
||
544 | { |
||
545 | __get_db()->__erase_c(this); |
||
546 | } |
||
547 | #endif |
||
548 | |||
549 | vector(const vector& __x); |
||
550 | vector(const vector& __x, const allocator_type& __a); |
||
551 | _LIBCPP_INLINE_VISIBILITY |
||
552 | vector& operator=(const vector& __x); |
||
553 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
554 | _LIBCPP_INLINE_VISIBILITY |
||
555 | vector(vector&& __x) |
||
556 | #if _LIBCPP_STD_VER > 14 |
||
557 | _NOEXCEPT; |
||
558 | #else |
||
559 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); |
||
560 | #endif |
||
561 | _LIBCPP_INLINE_VISIBILITY |
||
562 | vector(vector&& __x, const allocator_type& __a); |
||
563 | _LIBCPP_INLINE_VISIBILITY |
||
564 | vector& operator=(vector&& __x) |
||
565 | _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); |
||
566 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
567 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
568 | _LIBCPP_INLINE_VISIBILITY |
||
569 | vector& operator=(initializer_list<value_type> __il) |
||
570 | {assign(__il.begin(), __il.end()); return *this;} |
||
571 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
572 | |||
573 | template <class _InputIterator> |
||
574 | typename enable_if |
||
575 | < |
||
576 | __is_input_iterator <_InputIterator>::value && |
||
577 | !__is_forward_iterator<_InputIterator>::value && |
||
578 | is_constructible< |
||
579 | value_type, |
||
580 | typename iterator_traits<_InputIterator>::reference>::value, |
||
581 | void |
||
582 | >::type |
||
583 | assign(_InputIterator __first, _InputIterator __last); |
||
584 | template <class _ForwardIterator> |
||
585 | typename enable_if |
||
586 | < |
||
587 | __is_forward_iterator<_ForwardIterator>::value && |
||
588 | is_constructible< |
||
589 | value_type, |
||
590 | typename iterator_traits<_ForwardIterator>::reference>::value, |
||
591 | void |
||
592 | >::type |
||
593 | assign(_ForwardIterator __first, _ForwardIterator __last); |
||
594 | |||
595 | void assign(size_type __n, const_reference __u); |
||
596 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
597 | _LIBCPP_INLINE_VISIBILITY |
||
598 | void assign(initializer_list<value_type> __il) |
||
599 | {assign(__il.begin(), __il.end());} |
||
600 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
601 | |||
602 | _LIBCPP_INLINE_VISIBILITY |
||
603 | allocator_type get_allocator() const _NOEXCEPT |
||
604 | {return this->__alloc();} |
||
605 | |||
606 | _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT; |
||
607 | _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT; |
||
608 | _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT; |
||
609 | _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT; |
||
610 | |||
611 | _LIBCPP_INLINE_VISIBILITY |
||
612 | reverse_iterator rbegin() _NOEXCEPT |
||
613 | {return reverse_iterator(end());} |
||
614 | _LIBCPP_INLINE_VISIBILITY |
||
615 | const_reverse_iterator rbegin() const _NOEXCEPT |
||
616 | {return const_reverse_iterator(end());} |
||
617 | _LIBCPP_INLINE_VISIBILITY |
||
618 | reverse_iterator rend() _NOEXCEPT |
||
619 | {return reverse_iterator(begin());} |
||
620 | _LIBCPP_INLINE_VISIBILITY |
||
621 | const_reverse_iterator rend() const _NOEXCEPT |
||
622 | {return const_reverse_iterator(begin());} |
||
623 | |||
624 | _LIBCPP_INLINE_VISIBILITY |
||
625 | const_iterator cbegin() const _NOEXCEPT |
||
626 | {return begin();} |
||
627 | _LIBCPP_INLINE_VISIBILITY |
||
628 | const_iterator cend() const _NOEXCEPT |
||
629 | {return end();} |
||
630 | _LIBCPP_INLINE_VISIBILITY |
||
631 | const_reverse_iterator crbegin() const _NOEXCEPT |
||
632 | {return rbegin();} |
||
633 | _LIBCPP_INLINE_VISIBILITY |
||
634 | const_reverse_iterator crend() const _NOEXCEPT |
||
635 | {return rend();} |
||
636 | |||
637 | _LIBCPP_INLINE_VISIBILITY |
||
638 | size_type size() const _NOEXCEPT |
||
639 | {return static_cast<size_type>(this->__end_ - this->__begin_);} |
||
640 | _LIBCPP_INLINE_VISIBILITY |
||
641 | size_type capacity() const _NOEXCEPT |
||
642 | {return __base::capacity();} |
||
643 | _LIBCPP_INLINE_VISIBILITY |
||
644 | bool empty() const _NOEXCEPT |
||
645 | {return this->__begin_ == this->__end_;} |
||
646 | size_type max_size() const _NOEXCEPT; |
||
647 | void reserve(size_type __n); |
||
648 | void shrink_to_fit() _NOEXCEPT; |
||
649 | |||
650 | _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); |
||
651 | _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; |
||
652 | reference at(size_type __n); |
||
653 | const_reference at(size_type __n) const; |
||
654 | |||
655 | _LIBCPP_INLINE_VISIBILITY reference front() |
||
656 | { |
||
657 | _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); |
||
658 | return *this->__begin_; |
||
659 | } |
||
660 | _LIBCPP_INLINE_VISIBILITY const_reference front() const |
||
661 | { |
||
662 | _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); |
||
663 | return *this->__begin_; |
||
664 | } |
||
665 | _LIBCPP_INLINE_VISIBILITY reference back() |
||
666 | { |
||
667 | _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); |
||
668 | return *(this->__end_ - 1); |
||
669 | } |
||
670 | _LIBCPP_INLINE_VISIBILITY const_reference back() const |
||
671 | { |
||
672 | _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); |
||
673 | return *(this->__end_ - 1); |
||
674 | } |
||
675 | |||
676 | _LIBCPP_INLINE_VISIBILITY |
||
677 | value_type* data() _NOEXCEPT |
||
678 | {return _VSTD::__to_raw_pointer(this->__begin_);} |
||
679 | _LIBCPP_INLINE_VISIBILITY |
||
680 | const value_type* data() const _NOEXCEPT |
||
681 | {return _VSTD::__to_raw_pointer(this->__begin_);} |
||
682 | |||
683 | _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); |
||
684 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
685 | _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x); |
||
686 | #ifndef _LIBCPP_HAS_NO_VARIADICS |
||
687 | template <class... _Args> |
||
688 | void emplace_back(_Args&&... __args); |
||
689 | #endif // _LIBCPP_HAS_NO_VARIADICS |
||
690 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
691 | void pop_back(); |
||
692 | |||
693 | iterator insert(const_iterator __position, const_reference __x); |
||
694 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
695 | iterator insert(const_iterator __position, value_type&& __x); |
||
696 | #ifndef _LIBCPP_HAS_NO_VARIADICS |
||
697 | template <class... _Args> |
||
698 | iterator emplace(const_iterator __position, _Args&&... __args); |
||
699 | #endif // _LIBCPP_HAS_NO_VARIADICS |
||
700 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
701 | iterator insert(const_iterator __position, size_type __n, const_reference __x); |
||
702 | template <class _InputIterator> |
||
703 | typename enable_if |
||
704 | < |
||
705 | __is_input_iterator <_InputIterator>::value && |
||
706 | !__is_forward_iterator<_InputIterator>::value && |
||
707 | is_constructible< |
||
708 | value_type, |
||
709 | typename iterator_traits<_InputIterator>::reference>::value, |
||
710 | iterator |
||
711 | >::type |
||
712 | insert(const_iterator __position, _InputIterator __first, _InputIterator __last); |
||
713 | template <class _ForwardIterator> |
||
714 | typename enable_if |
||
715 | < |
||
716 | __is_forward_iterator<_ForwardIterator>::value && |
||
717 | is_constructible< |
||
718 | value_type, |
||
719 | typename iterator_traits<_ForwardIterator>::reference>::value, |
||
720 | iterator |
||
721 | >::type |
||
722 | insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); |
||
723 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
724 | _LIBCPP_INLINE_VISIBILITY |
||
725 | iterator insert(const_iterator __position, initializer_list<value_type> __il) |
||
726 | {return insert(__position, __il.begin(), __il.end());} |
||
727 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
728 | |||
729 | _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); |
||
730 | iterator erase(const_iterator __first, const_iterator __last); |
||
731 | |||
732 | _LIBCPP_INLINE_VISIBILITY |
||
733 | void clear() _NOEXCEPT |
||
734 | { |
||
735 | size_type __old_size = size(); |
||
736 | __base::clear(); |
||
737 | __annotate_shrink(__old_size); |
||
738 | __invalidate_all_iterators(); |
||
739 | } |
||
740 | |||
741 | void resize(size_type __sz); |
||
742 | void resize(size_type __sz, const_reference __x); |
||
743 | |||
744 | void swap(vector&) |
||
745 | #if _LIBCPP_STD_VER >= 14 |
||
746 | _NOEXCEPT; |
||
747 | #else |
||
748 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || |
||
749 | __is_nothrow_swappable<allocator_type>::value); |
||
750 | #endif |
||
751 | |||
752 | bool __invariants() const; |
||
753 | |||
754 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
755 | |||
756 | bool __dereferenceable(const const_iterator* __i) const; |
||
757 | bool __decrementable(const const_iterator* __i) const; |
||
758 | bool __addable(const const_iterator* __i, ptrdiff_t __n) const; |
||
759 | bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; |
||
760 | |||
761 | #endif // _LIBCPP_DEBUG_LEVEL >= 2 |
||
762 | |||
763 | private: |
||
764 | _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); |
||
765 | void allocate(size_type __n); |
||
766 | void deallocate() _NOEXCEPT; |
||
767 | _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; |
||
768 | void __construct_at_end(size_type __n); |
||
769 | void __construct_at_end(size_type __n, const_reference __x); |
||
770 | template <class _ForwardIterator> |
||
771 | typename enable_if |
||
772 | < |
||
773 | __is_forward_iterator<_ForwardIterator>::value, |
||
774 | void |
||
775 | >::type |
||
776 | __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n); |
||
777 | void __append(size_type __n); |
||
778 | void __append(size_type __n, const_reference __x); |
||
779 | _LIBCPP_INLINE_VISIBILITY |
||
780 | iterator __make_iter(pointer __p) _NOEXCEPT; |
||
781 | _LIBCPP_INLINE_VISIBILITY |
||
782 | const_iterator __make_iter(const_pointer __p) const _NOEXCEPT; |
||
783 | void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); |
||
784 | pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); |
||
785 | void __move_range(pointer __from_s, pointer __from_e, pointer __to); |
||
786 | void __move_assign(vector& __c, true_type) |
||
787 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); |
||
788 | void __move_assign(vector& __c, false_type) |
||
789 | _NOEXCEPT_(__alloc_traits::is_always_equal::value); |
||
790 | _LIBCPP_INLINE_VISIBILITY |
||
791 | void __destruct_at_end(pointer __new_last) _NOEXCEPT |
||
792 | { |
||
793 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
794 | __c_node* __c = __get_db()->__find_c_and_lock(this); |
||
795 | for (__i_node** __p = __c->end_; __p != __c->beg_; ) |
||
796 | { |
||
797 | --__p; |
||
798 | const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); |
||
799 | if (__i->base() > __new_last) |
||
800 | { |
||
801 | (*__p)->__c_ = nullptr; |
||
802 | if (--__c->end_ != __p) |
||
803 | memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); |
||
804 | } |
||
805 | } |
||
806 | __get_db()->unlock(); |
||
807 | #endif |
||
808 | size_type __old_size = size(); |
||
809 | __base::__destruct_at_end(__new_last); |
||
810 | __annotate_shrink(__old_size); |
||
811 | } |
||
812 | template <class _Up> |
||
813 | void |
||
814 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
815 | __push_back_slow_path(_Up&& __x); |
||
816 | #else |
||
817 | __push_back_slow_path(_Up& __x); |
||
818 | #endif |
||
819 | #if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) |
||
820 | template <class... _Args> |
||
821 | void |
||
822 | __emplace_back_slow_path(_Args&&... __args); |
||
823 | #endif |
||
824 | // The following functions are no-ops outside of AddressSanitizer mode. |
||
825 | // We call annotatations only for the default Allocator because other allocators |
||
826 | // may not meet the AddressSanitizer alignment constraints. |
||
827 | // See the documentation for __sanitizer_annotate_contiguous_container for more details. |
||
828 | void __annotate_contiguous_container |
||
829 | (const void *__beg, const void *__end, const void *__old_mid, const void *__new_mid) const |
||
830 | { |
||
831 | #ifndef _LIBCPP_HAS_NO_ASAN |
||
832 | if (__beg && is_same<allocator_type, __default_allocator_type>::value) |
||
833 | __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid); |
||
834 | #endif |
||
835 | } |
||
836 | |||
837 | void __annotate_new(size_type __current_size) const |
||
838 | { |
||
839 | __annotate_contiguous_container(data(), data() + capacity(), |
||
840 | data() + capacity(), data() + __current_size); |
||
841 | } |
||
842 | void __annotate_delete() const |
||
843 | { |
||
844 | __annotate_contiguous_container(data(), data() + capacity(), |
||
845 | data() + size(), data() + capacity()); |
||
846 | } |
||
847 | void __annotate_increase(size_type __n) const |
||
848 | { |
||
849 | __annotate_contiguous_container(data(), data() + capacity(), |
||
850 | data() + size(), data() + size() + __n); |
||
851 | } |
||
852 | void __annotate_shrink(size_type __old_size) const |
||
853 | { |
||
854 | __annotate_contiguous_container(data(), data() + capacity(), |
||
855 | data() + __old_size, data() + size()); |
||
856 | } |
||
857 | #ifndef _LIBCPP_HAS_NO_ASAN |
||
858 | // The annotation for size increase should happen before the actual increase, |
||
859 | // but if an exception is thrown after that the annotation has to be undone. |
||
860 | struct __RAII_IncreaseAnnotator { |
||
861 | __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1) |
||
862 | : __commit(false), __v(__v), __old_size(__v.size() + __n) { |
||
863 | __v.__annotate_increase(__n); |
||
864 | } |
||
865 | void __done() { __commit = true; } |
||
866 | ~__RAII_IncreaseAnnotator() { |
||
867 | if (__commit) return; |
||
868 | __v.__annotate_shrink(__old_size); |
||
869 | } |
||
870 | bool __commit; |
||
871 | const vector &__v; |
||
872 | size_type __old_size; |
||
873 | }; |
||
874 | #else |
||
875 | struct __RAII_IncreaseAnnotator { |
||
876 | inline __RAII_IncreaseAnnotator(const vector &, size_type __n = 1) {} |
||
877 | inline void __done() {} |
||
878 | }; |
||
879 | #endif |
||
880 | |||
881 | }; |
||
882 | |||
883 | template <class _Tp, class _Allocator> |
||
884 | void |
||
885 | vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) |
||
886 | { |
||
887 | __annotate_delete(); |
||
888 | __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_); |
||
889 | _VSTD::swap(this->__begin_, __v.__begin_); |
||
890 | _VSTD::swap(this->__end_, __v.__end_); |
||
891 | _VSTD::swap(this->__end_cap(), __v.__end_cap()); |
||
892 | __v.__first_ = __v.__begin_; |
||
893 | __annotate_new(size()); |
||
894 | __invalidate_all_iterators(); |
||
895 | } |
||
896 | |||
897 | template <class _Tp, class _Allocator> |
||
898 | typename vector<_Tp, _Allocator>::pointer |
||
899 | vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) |
||
900 | { |
||
901 | __annotate_delete(); |
||
902 | pointer __r = __v.__begin_; |
||
903 | __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_); |
||
904 | __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_); |
||
905 | _VSTD::swap(this->__begin_, __v.__begin_); |
||
906 | _VSTD::swap(this->__end_, __v.__end_); |
||
907 | _VSTD::swap(this->__end_cap(), __v.__end_cap()); |
||
908 | __v.__first_ = __v.__begin_; |
||
909 | __annotate_new(size()); |
||
910 | __invalidate_all_iterators(); |
||
911 | return __r; |
||
912 | } |
||
913 | |||
914 | // Allocate space for __n objects |
||
915 | // throws length_error if __n > max_size() |
||
916 | // throws (probably bad_alloc) if memory run out |
||
917 | // Precondition: __begin_ == __end_ == __end_cap() == 0 |
||
918 | // Precondition: __n > 0 |
||
919 | // Postcondition: capacity() == __n |
||
920 | // Postcondition: size() == 0 |
||
921 | template <class _Tp, class _Allocator> |
||
922 | void |
||
923 | vector<_Tp, _Allocator>::allocate(size_type __n) |
||
924 | { |
||
925 | if (__n > max_size()) |
||
926 | this->__throw_length_error(); |
||
927 | this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); |
||
928 | this->__end_cap() = this->__begin_ + __n; |
||
929 | __annotate_new(0); |
||
930 | } |
||
931 | |||
932 | template <class _Tp, class _Allocator> |
||
933 | void |
||
934 | vector<_Tp, _Allocator>::deallocate() _NOEXCEPT |
||
935 | { |
||
936 | if (this->__begin_ != nullptr) |
||
937 | { |
||
938 | clear(); |
||
939 | __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); |
||
940 | this->__begin_ = this->__end_ = this->__end_cap() = nullptr; |
||
941 | } |
||
942 | } |
||
943 | |||
944 | template <class _Tp, class _Allocator> |
||
945 | typename vector<_Tp, _Allocator>::size_type |
||
946 | vector<_Tp, _Allocator>::max_size() const _NOEXCEPT |
||
947 | { |
||
948 | return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always |
||
949 | } |
||
950 | |||
951 | // Precondition: __new_size > capacity() |
||
952 | template <class _Tp, class _Allocator> |
||
953 | inline _LIBCPP_INLINE_VISIBILITY |
||
954 | typename vector<_Tp, _Allocator>::size_type |
||
955 | vector<_Tp, _Allocator>::__recommend(size_type __new_size) const |
||
956 | { |
||
957 | const size_type __ms = max_size(); |
||
958 | if (__new_size > __ms) |
||
959 | this->__throw_length_error(); |
||
960 | const size_type __cap = capacity(); |
||
961 | if (__cap >= __ms / 2) |
||
962 | return __ms; |
||
963 | return _VSTD::max<size_type>(2*__cap, __new_size); |
||
964 | } |
||
965 | |||
966 | // Default constructs __n objects starting at __end_ |
||
967 | // throws if construction throws |
||
968 | // Precondition: __n > 0 |
||
969 | // Precondition: size() + __n <= capacity() |
||
970 | // Postcondition: size() == size() + __n |
||
971 | template <class _Tp, class _Allocator> |
||
972 | void |
||
973 | vector<_Tp, _Allocator>::__construct_at_end(size_type __n) |
||
974 | { |
||
975 | allocator_type& __a = this->__alloc(); |
||
976 | do |
||
977 | { |
||
978 | __RAII_IncreaseAnnotator __annotator(*this); |
||
979 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); |
||
980 | ++this->__end_; |
||
981 | --__n; |
||
982 | __annotator.__done(); |
||
983 | } while (__n > 0); |
||
984 | } |
||
985 | |||
986 | // Copy constructs __n objects starting at __end_ from __x |
||
987 | // throws if construction throws |
||
988 | // Precondition: __n > 0 |
||
989 | // Precondition: size() + __n <= capacity() |
||
990 | // Postcondition: size() == old size() + __n |
||
991 | // Postcondition: [i] == __x for all i in [size() - __n, __n) |
||
992 | template <class _Tp, class _Allocator> |
||
993 | inline _LIBCPP_INLINE_VISIBILITY |
||
994 | void |
||
995 | vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) |
||
996 | { |
||
997 | allocator_type& __a = this->__alloc(); |
||
998 | do |
||
999 | { |
||
1000 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1001 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); |
||
1002 | ++this->__end_; |
||
1003 | --__n; |
||
1004 | __annotator.__done(); |
||
1005 | } while (__n > 0); |
||
1006 | } |
||
1007 | |||
1008 | template <class _Tp, class _Allocator> |
||
1009 | template <class _ForwardIterator> |
||
1010 | typename enable_if |
||
1011 | < |
||
1012 | __is_forward_iterator<_ForwardIterator>::value, |
||
1013 | void |
||
1014 | >::type |
||
1015 | vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n) |
||
1016 | { |
||
1017 | allocator_type& __a = this->__alloc(); |
||
1018 | __RAII_IncreaseAnnotator __annotator(*this, __n); |
||
1019 | __alloc_traits::__construct_range_forward(__a, __first, __last, this->__end_); |
||
1020 | __annotator.__done(); |
||
1021 | } |
||
1022 | |||
1023 | // Default constructs __n objects starting at __end_ |
||
1024 | // throws if construction throws |
||
1025 | // Postcondition: size() == size() + __n |
||
1026 | // Exception safety: strong. |
||
1027 | template <class _Tp, class _Allocator> |
||
1028 | void |
||
1029 | vector<_Tp, _Allocator>::__append(size_type __n) |
||
1030 | { |
||
1031 | if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) |
||
1032 | this->__construct_at_end(__n); |
||
1033 | else |
||
1034 | { |
||
1035 | allocator_type& __a = this->__alloc(); |
||
1036 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); |
||
1037 | __v.__construct_at_end(__n); |
||
1038 | __swap_out_circular_buffer(__v); |
||
1039 | } |
||
1040 | } |
||
1041 | |||
1042 | // Default constructs __n objects starting at __end_ |
||
1043 | // throws if construction throws |
||
1044 | // Postcondition: size() == size() + __n |
||
1045 | // Exception safety: strong. |
||
1046 | template <class _Tp, class _Allocator> |
||
1047 | void |
||
1048 | vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) |
||
1049 | { |
||
1050 | if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) |
||
1051 | this->__construct_at_end(__n, __x); |
||
1052 | else |
||
1053 | { |
||
1054 | allocator_type& __a = this->__alloc(); |
||
1055 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); |
||
1056 | __v.__construct_at_end(__n, __x); |
||
1057 | __swap_out_circular_buffer(__v); |
||
1058 | } |
||
1059 | } |
||
1060 | |||
1061 | template <class _Tp, class _Allocator> |
||
1062 | vector<_Tp, _Allocator>::vector(size_type __n) |
||
1063 | { |
||
1064 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1065 | __get_db()->__insert_c(this); |
||
1066 | #endif |
||
1067 | if (__n > 0) |
||
1068 | { |
||
1069 | allocate(__n); |
||
1070 | __construct_at_end(__n); |
||
1071 | } |
||
1072 | } |
||
1073 | |||
1074 | #if _LIBCPP_STD_VER > 11 |
||
1075 | template <class _Tp, class _Allocator> |
||
1076 | vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a) |
||
1077 | : __base(__a) |
||
1078 | { |
||
1079 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1080 | __get_db()->__insert_c(this); |
||
1081 | #endif |
||
1082 | if (__n > 0) |
||
1083 | { |
||
1084 | allocate(__n); |
||
1085 | __construct_at_end(__n); |
||
1086 | } |
||
1087 | } |
||
1088 | #endif |
||
1089 | |||
1090 | template <class _Tp, class _Allocator> |
||
1091 | vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) |
||
1092 | { |
||
1093 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1094 | __get_db()->__insert_c(this); |
||
1095 | #endif |
||
1096 | if (__n > 0) |
||
1097 | { |
||
1098 | allocate(__n); |
||
1099 | __construct_at_end(__n, __x); |
||
1100 | } |
||
1101 | } |
||
1102 | |||
1103 | template <class _Tp, class _Allocator> |
||
1104 | vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) |
||
1105 | : __base(__a) |
||
1106 | { |
||
1107 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1108 | __get_db()->__insert_c(this); |
||
1109 | #endif |
||
1110 | if (__n > 0) |
||
1111 | { |
||
1112 | allocate(__n); |
||
1113 | __construct_at_end(__n, __x); |
||
1114 | } |
||
1115 | } |
||
1116 | |||
1117 | template <class _Tp, class _Allocator> |
||
1118 | template <class _InputIterator> |
||
1119 | vector<_Tp, _Allocator>::vector(_InputIterator __first, |
||
1120 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
1121 | !__is_forward_iterator<_InputIterator>::value && |
||
1122 | is_constructible< |
||
1123 | value_type, |
||
1124 | typename iterator_traits<_InputIterator>::reference>::value, |
||
1125 | _InputIterator>::type __last) |
||
1126 | { |
||
1127 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1128 | __get_db()->__insert_c(this); |
||
1129 | #endif |
||
1130 | for (; __first != __last; ++__first) |
||
1131 | push_back(*__first); |
||
1132 | } |
||
1133 | |||
1134 | template <class _Tp, class _Allocator> |
||
1135 | template <class _InputIterator> |
||
1136 | vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, |
||
1137 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
1138 | !__is_forward_iterator<_InputIterator>::value && |
||
1139 | is_constructible< |
||
1140 | value_type, |
||
1141 | typename iterator_traits<_InputIterator>::reference>::value>::type*) |
||
1142 | : __base(__a) |
||
1143 | { |
||
1144 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1145 | __get_db()->__insert_c(this); |
||
1146 | #endif |
||
1147 | for (; __first != __last; ++__first) |
||
1148 | push_back(*__first); |
||
1149 | } |
||
1150 | |||
1151 | template <class _Tp, class _Allocator> |
||
1152 | template <class _ForwardIterator> |
||
1153 | vector<_Tp, _Allocator>::vector(_ForwardIterator __first, |
||
1154 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value && |
||
1155 | is_constructible< |
||
1156 | value_type, |
||
1157 | typename iterator_traits<_ForwardIterator>::reference>::value, |
||
1158 | _ForwardIterator>::type __last) |
||
1159 | { |
||
1160 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1161 | __get_db()->__insert_c(this); |
||
1162 | #endif |
||
1163 | size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); |
||
1164 | if (__n > 0) |
||
1165 | { |
||
1166 | allocate(__n); |
||
1167 | __construct_at_end(__first, __last, __n); |
||
1168 | } |
||
1169 | } |
||
1170 | |||
1171 | template <class _Tp, class _Allocator> |
||
1172 | template <class _ForwardIterator> |
||
1173 | vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, |
||
1174 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value && |
||
1175 | is_constructible< |
||
1176 | value_type, |
||
1177 | typename iterator_traits<_ForwardIterator>::reference>::value>::type*) |
||
1178 | : __base(__a) |
||
1179 | { |
||
1180 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1181 | __get_db()->__insert_c(this); |
||
1182 | #endif |
||
1183 | size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); |
||
1184 | if (__n > 0) |
||
1185 | { |
||
1186 | allocate(__n); |
||
1187 | __construct_at_end(__first, __last, __n); |
||
1188 | } |
||
1189 | } |
||
1190 | |||
1191 | template <class _Tp, class _Allocator> |
||
1192 | vector<_Tp, _Allocator>::vector(const vector& __x) |
||
1193 | : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) |
||
1194 | { |
||
1195 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1196 | __get_db()->__insert_c(this); |
||
1197 | #endif |
||
1198 | size_type __n = __x.size(); |
||
1199 | if (__n > 0) |
||
1200 | { |
||
1201 | allocate(__n); |
||
1202 | __construct_at_end(__x.__begin_, __x.__end_, __n); |
||
1203 | } |
||
1204 | } |
||
1205 | |||
1206 | template <class _Tp, class _Allocator> |
||
1207 | vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) |
||
1208 | : __base(__a) |
||
1209 | { |
||
1210 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1211 | __get_db()->__insert_c(this); |
||
1212 | #endif |
||
1213 | size_type __n = __x.size(); |
||
1214 | if (__n > 0) |
||
1215 | { |
||
1216 | allocate(__n); |
||
1217 | __construct_at_end(__x.__begin_, __x.__end_, __n); |
||
1218 | } |
||
1219 | } |
||
1220 | |||
1221 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1222 | |||
1223 | template <class _Tp, class _Allocator> |
||
1224 | inline _LIBCPP_INLINE_VISIBILITY |
||
1225 | vector<_Tp, _Allocator>::vector(vector&& __x) |
||
1226 | #if _LIBCPP_STD_VER > 14 |
||
1227 | _NOEXCEPT |
||
1228 | #else |
||
1229 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) |
||
1230 | #endif |
||
1231 | : __base(_VSTD::move(__x.__alloc())) |
||
1232 | { |
||
1233 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1234 | __get_db()->__insert_c(this); |
||
1235 | __get_db()->swap(this, &__x); |
||
1236 | #endif |
||
1237 | this->__begin_ = __x.__begin_; |
||
1238 | this->__end_ = __x.__end_; |
||
1239 | this->__end_cap() = __x.__end_cap(); |
||
1240 | __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; |
||
1241 | } |
||
1242 | |||
1243 | template <class _Tp, class _Allocator> |
||
1244 | inline _LIBCPP_INLINE_VISIBILITY |
||
1245 | vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) |
||
1246 | : __base(__a) |
||
1247 | { |
||
1248 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1249 | __get_db()->__insert_c(this); |
||
1250 | #endif |
||
1251 | if (__a == __x.__alloc()) |
||
1252 | { |
||
1253 | this->__begin_ = __x.__begin_; |
||
1254 | this->__end_ = __x.__end_; |
||
1255 | this->__end_cap() = __x.__end_cap(); |
||
1256 | __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; |
||
1257 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1258 | __get_db()->swap(this, &__x); |
||
1259 | #endif |
||
1260 | } |
||
1261 | else |
||
1262 | { |
||
1263 | typedef move_iterator<iterator> _Ip; |
||
1264 | assign(_Ip(__x.begin()), _Ip(__x.end())); |
||
1265 | } |
||
1266 | } |
||
1267 | |||
1268 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
1269 | |||
1270 | template <class _Tp, class _Allocator> |
||
1271 | inline _LIBCPP_INLINE_VISIBILITY |
||
1272 | vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) |
||
1273 | { |
||
1274 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1275 | __get_db()->__insert_c(this); |
||
1276 | #endif |
||
1277 | if (__il.size() > 0) |
||
1278 | { |
||
1279 | allocate(__il.size()); |
||
1280 | __construct_at_end(__il.begin(), __il.end(), __il.size()); |
||
1281 | } |
||
1282 | } |
||
1283 | |||
1284 | template <class _Tp, class _Allocator> |
||
1285 | inline _LIBCPP_INLINE_VISIBILITY |
||
1286 | vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) |
||
1287 | : __base(__a) |
||
1288 | { |
||
1289 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1290 | __get_db()->__insert_c(this); |
||
1291 | #endif |
||
1292 | if (__il.size() > 0) |
||
1293 | { |
||
1294 | allocate(__il.size()); |
||
1295 | __construct_at_end(__il.begin(), __il.end(), __il.size()); |
||
1296 | } |
||
1297 | } |
||
1298 | |||
1299 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
1300 | |||
1301 | template <class _Tp, class _Allocator> |
||
1302 | inline _LIBCPP_INLINE_VISIBILITY |
||
1303 | vector<_Tp, _Allocator>& |
||
1304 | vector<_Tp, _Allocator>::operator=(vector&& __x) |
||
1305 | _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) |
||
1306 | { |
||
1307 | __move_assign(__x, integral_constant<bool, |
||
1308 | __alloc_traits::propagate_on_container_move_assignment::value>()); |
||
1309 | return *this; |
||
1310 | } |
||
1311 | |||
1312 | template <class _Tp, class _Allocator> |
||
1313 | void |
||
1314 | vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) |
||
1315 | _NOEXCEPT_(__alloc_traits::is_always_equal::value) |
||
1316 | { |
||
1317 | if (__base::__alloc() != __c.__alloc()) |
||
1318 | { |
||
1319 | typedef move_iterator<iterator> _Ip; |
||
1320 | assign(_Ip(__c.begin()), _Ip(__c.end())); |
||
1321 | } |
||
1322 | else |
||
1323 | __move_assign(__c, true_type()); |
||
1324 | } |
||
1325 | |||
1326 | template <class _Tp, class _Allocator> |
||
1327 | void |
||
1328 | vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) |
||
1329 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) |
||
1330 | { |
||
1331 | deallocate(); |
||
1332 | __base::__move_assign_alloc(__c); // this can throw |
||
1333 | this->__begin_ = __c.__begin_; |
||
1334 | this->__end_ = __c.__end_; |
||
1335 | this->__end_cap() = __c.__end_cap(); |
||
1336 | __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; |
||
1337 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1338 | __get_db()->swap(this, &__c); |
||
1339 | #endif |
||
1340 | } |
||
1341 | |||
1342 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1343 | |||
1344 | template <class _Tp, class _Allocator> |
||
1345 | inline _LIBCPP_INLINE_VISIBILITY |
||
1346 | vector<_Tp, _Allocator>& |
||
1347 | vector<_Tp, _Allocator>::operator=(const vector& __x) |
||
1348 | { |
||
1349 | if (this != &__x) |
||
1350 | { |
||
1351 | __base::__copy_assign_alloc(__x); |
||
1352 | assign(__x.__begin_, __x.__end_); |
||
1353 | } |
||
1354 | return *this; |
||
1355 | } |
||
1356 | |||
1357 | template <class _Tp, class _Allocator> |
||
1358 | template <class _InputIterator> |
||
1359 | typename enable_if |
||
1360 | < |
||
1361 | __is_input_iterator <_InputIterator>::value && |
||
1362 | !__is_forward_iterator<_InputIterator>::value && |
||
1363 | is_constructible< |
||
1364 | _Tp, |
||
1365 | typename iterator_traits<_InputIterator>::reference>::value, |
||
1366 | void |
||
1367 | >::type |
||
1368 | vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) |
||
1369 | { |
||
1370 | clear(); |
||
1371 | for (; __first != __last; ++__first) |
||
1372 | push_back(*__first); |
||
1373 | } |
||
1374 | |||
1375 | template <class _Tp, class _Allocator> |
||
1376 | template <class _ForwardIterator> |
||
1377 | typename enable_if |
||
1378 | < |
||
1379 | __is_forward_iterator<_ForwardIterator>::value && |
||
1380 | is_constructible< |
||
1381 | _Tp, |
||
1382 | typename iterator_traits<_ForwardIterator>::reference>::value, |
||
1383 | void |
||
1384 | >::type |
||
1385 | vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) |
||
1386 | { |
||
1387 | size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last)); |
||
1388 | if (__new_size <= capacity()) |
||
1389 | { |
||
1390 | _ForwardIterator __mid = __last; |
||
1391 | bool __growing = false; |
||
1392 | if (__new_size > size()) |
||
1393 | { |
||
1394 | __growing = true; |
||
1395 | __mid = __first; |
||
1396 | _VSTD::advance(__mid, size()); |
||
1397 | } |
||
1398 | pointer __m = _VSTD::copy(__first, __mid, this->__begin_); |
||
1399 | if (__growing) |
||
1400 | __construct_at_end(__mid, __last, __new_size - size()); |
||
1401 | else |
||
1402 | this->__destruct_at_end(__m); |
||
1403 | } |
||
1404 | else |
||
1405 | { |
||
1406 | deallocate(); |
||
1407 | allocate(__recommend(__new_size)); |
||
1408 | __construct_at_end(__first, __last, __new_size); |
||
1409 | } |
||
1410 | } |
||
1411 | |||
1412 | template <class _Tp, class _Allocator> |
||
1413 | void |
||
1414 | vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) |
||
1415 | { |
||
1416 | if (__n <= capacity()) |
||
1417 | { |
||
1418 | size_type __s = size(); |
||
1419 | _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u); |
||
1420 | if (__n > __s) |
||
1421 | __construct_at_end(__n - __s, __u); |
||
1422 | else |
||
1423 | this->__destruct_at_end(this->__begin_ + __n); |
||
1424 | } |
||
1425 | else |
||
1426 | { |
||
1427 | deallocate(); |
||
1428 | allocate(__recommend(static_cast<size_type>(__n))); |
||
1429 | __construct_at_end(__n, __u); |
||
1430 | } |
||
1431 | } |
||
1432 | |||
1433 | template <class _Tp, class _Allocator> |
||
1434 | inline _LIBCPP_INLINE_VISIBILITY |
||
1435 | typename vector<_Tp, _Allocator>::iterator |
||
1436 | vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT |
||
1437 | { |
||
1438 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1439 | return iterator(this, __p); |
||
1440 | #else |
||
1441 | return iterator(__p); |
||
1442 | #endif |
||
1443 | } |
||
1444 | |||
1445 | template <class _Tp, class _Allocator> |
||
1446 | inline _LIBCPP_INLINE_VISIBILITY |
||
1447 | typename vector<_Tp, _Allocator>::const_iterator |
||
1448 | vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT |
||
1449 | { |
||
1450 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1451 | return const_iterator(this, __p); |
||
1452 | #else |
||
1453 | return const_iterator(__p); |
||
1454 | #endif |
||
1455 | } |
||
1456 | |||
1457 | template <class _Tp, class _Allocator> |
||
1458 | inline _LIBCPP_INLINE_VISIBILITY |
||
1459 | typename vector<_Tp, _Allocator>::iterator |
||
1460 | vector<_Tp, _Allocator>::begin() _NOEXCEPT |
||
1461 | { |
||
1462 | return __make_iter(this->__begin_); |
||
1463 | } |
||
1464 | |||
1465 | template <class _Tp, class _Allocator> |
||
1466 | inline _LIBCPP_INLINE_VISIBILITY |
||
1467 | typename vector<_Tp, _Allocator>::const_iterator |
||
1468 | vector<_Tp, _Allocator>::begin() const _NOEXCEPT |
||
1469 | { |
||
1470 | return __make_iter(this->__begin_); |
||
1471 | } |
||
1472 | |||
1473 | template <class _Tp, class _Allocator> |
||
1474 | inline _LIBCPP_INLINE_VISIBILITY |
||
1475 | typename vector<_Tp, _Allocator>::iterator |
||
1476 | vector<_Tp, _Allocator>::end() _NOEXCEPT |
||
1477 | { |
||
1478 | return __make_iter(this->__end_); |
||
1479 | } |
||
1480 | |||
1481 | template <class _Tp, class _Allocator> |
||
1482 | inline _LIBCPP_INLINE_VISIBILITY |
||
1483 | typename vector<_Tp, _Allocator>::const_iterator |
||
1484 | vector<_Tp, _Allocator>::end() const _NOEXCEPT |
||
1485 | { |
||
1486 | return __make_iter(this->__end_); |
||
1487 | } |
||
1488 | |||
1489 | template <class _Tp, class _Allocator> |
||
1490 | inline _LIBCPP_INLINE_VISIBILITY |
||
1491 | typename vector<_Tp, _Allocator>::reference |
||
1492 | vector<_Tp, _Allocator>::operator[](size_type __n) |
||
1493 | { |
||
1494 | _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); |
||
1495 | return this->__begin_[__n]; |
||
1496 | } |
||
1497 | |||
1498 | template <class _Tp, class _Allocator> |
||
1499 | inline _LIBCPP_INLINE_VISIBILITY |
||
1500 | typename vector<_Tp, _Allocator>::const_reference |
||
1501 | vector<_Tp, _Allocator>::operator[](size_type __n) const |
||
1502 | { |
||
1503 | _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); |
||
1504 | return this->__begin_[__n]; |
||
1505 | } |
||
1506 | |||
1507 | template <class _Tp, class _Allocator> |
||
1508 | typename vector<_Tp, _Allocator>::reference |
||
1509 | vector<_Tp, _Allocator>::at(size_type __n) |
||
1510 | { |
||
1511 | if (__n >= size()) |
||
1512 | this->__throw_out_of_range(); |
||
1513 | return this->__begin_[__n]; |
||
1514 | } |
||
1515 | |||
1516 | template <class _Tp, class _Allocator> |
||
1517 | typename vector<_Tp, _Allocator>::const_reference |
||
1518 | vector<_Tp, _Allocator>::at(size_type __n) const |
||
1519 | { |
||
1520 | if (__n >= size()) |
||
1521 | this->__throw_out_of_range(); |
||
1522 | return this->__begin_[__n]; |
||
1523 | } |
||
1524 | |||
1525 | template <class _Tp, class _Allocator> |
||
1526 | void |
||
1527 | vector<_Tp, _Allocator>::reserve(size_type __n) |
||
1528 | { |
||
1529 | if (__n > capacity()) |
||
1530 | { |
||
1531 | allocator_type& __a = this->__alloc(); |
||
1532 | __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); |
||
1533 | __swap_out_circular_buffer(__v); |
||
1534 | } |
||
1535 | } |
||
1536 | |||
1537 | template <class _Tp, class _Allocator> |
||
1538 | void |
||
1539 | vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT |
||
1540 | { |
||
1541 | if (capacity() > size()) |
||
1542 | { |
||
1543 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
1544 | try |
||
1545 | { |
||
1546 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
1547 | allocator_type& __a = this->__alloc(); |
||
1548 | __split_buffer<value_type, allocator_type&> __v(size(), size(), __a); |
||
1549 | __swap_out_circular_buffer(__v); |
||
1550 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
1551 | } |
||
1552 | catch (...) |
||
1553 | { |
||
1554 | } |
||
1555 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
1556 | } |
||
1557 | } |
||
1558 | |||
1559 | template <class _Tp, class _Allocator> |
||
1560 | template <class _Up> |
||
1561 | void |
||
1562 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1563 | vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) |
||
1564 | #else |
||
1565 | vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x) |
||
1566 | #endif |
||
1567 | { |
||
1568 | allocator_type& __a = this->__alloc(); |
||
1569 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); |
||
1570 | // __v.push_back(_VSTD::forward<_Up>(__x)); |
||
1571 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x)); |
||
1572 | __v.__end_++; |
||
1573 | __swap_out_circular_buffer(__v); |
||
1574 | } |
||
1575 | |||
1576 | template <class _Tp, class _Allocator> |
||
1577 | inline _LIBCPP_INLINE_VISIBILITY |
||
1578 | void |
||
1579 | vector<_Tp, _Allocator>::push_back(const_reference __x) |
||
1580 | { |
||
1581 | if (this->__end_ != this->__end_cap()) |
||
1582 | { |
||
1583 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1584 | __alloc_traits::construct(this->__alloc(), |
||
1585 | _VSTD::__to_raw_pointer(this->__end_), __x); |
||
1586 | __annotator.__done(); |
||
1587 | ++this->__end_; |
||
1588 | } |
||
1589 | else |
||
1590 | __push_back_slow_path(__x); |
||
1591 | } |
||
1592 | |||
1593 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1594 | |||
1595 | template <class _Tp, class _Allocator> |
||
1596 | inline _LIBCPP_INLINE_VISIBILITY |
||
1597 | void |
||
1598 | vector<_Tp, _Allocator>::push_back(value_type&& __x) |
||
1599 | { |
||
1600 | if (this->__end_ < this->__end_cap()) |
||
1601 | { |
||
1602 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1603 | __alloc_traits::construct(this->__alloc(), |
||
1604 | _VSTD::__to_raw_pointer(this->__end_), |
||
1605 | _VSTD::move(__x)); |
||
1606 | __annotator.__done(); |
||
1607 | ++this->__end_; |
||
1608 | } |
||
1609 | else |
||
1610 | __push_back_slow_path(_VSTD::move(__x)); |
||
1611 | } |
||
1612 | |||
1613 | #ifndef _LIBCPP_HAS_NO_VARIADICS |
||
1614 | |||
1615 | template <class _Tp, class _Allocator> |
||
1616 | template <class... _Args> |
||
1617 | void |
||
1618 | vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) |
||
1619 | { |
||
1620 | allocator_type& __a = this->__alloc(); |
||
1621 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); |
||
1622 | // __v.emplace_back(_VSTD::forward<_Args>(__args)...); |
||
1623 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...); |
||
1624 | __v.__end_++; |
||
1625 | __swap_out_circular_buffer(__v); |
||
1626 | } |
||
1627 | |||
1628 | template <class _Tp, class _Allocator> |
||
1629 | template <class... _Args> |
||
1630 | inline _LIBCPP_INLINE_VISIBILITY |
||
1631 | void |
||
1632 | vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) |
||
1633 | { |
||
1634 | if (this->__end_ < this->__end_cap()) |
||
1635 | { |
||
1636 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1637 | __alloc_traits::construct(this->__alloc(), |
||
1638 | _VSTD::__to_raw_pointer(this->__end_), |
||
1639 | _VSTD::forward<_Args>(__args)...); |
||
1640 | __annotator.__done(); |
||
1641 | ++this->__end_; |
||
1642 | } |
||
1643 | else |
||
1644 | __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); |
||
1645 | } |
||
1646 | |||
1647 | #endif // _LIBCPP_HAS_NO_VARIADICS |
||
1648 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1649 | |||
1650 | template <class _Tp, class _Allocator> |
||
1651 | inline _LIBCPP_INLINE_VISIBILITY |
||
1652 | void |
||
1653 | vector<_Tp, _Allocator>::pop_back() |
||
1654 | { |
||
1655 | _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector"); |
||
1656 | this->__destruct_at_end(this->__end_ - 1); |
||
1657 | } |
||
1658 | |||
1659 | template <class _Tp, class _Allocator> |
||
1660 | inline _LIBCPP_INLINE_VISIBILITY |
||
1661 | typename vector<_Tp, _Allocator>::iterator |
||
1662 | vector<_Tp, _Allocator>::erase(const_iterator __position) |
||
1663 | { |
||
1664 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1665 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1666 | "vector::erase(iterator) called with an iterator not" |
||
1667 | " referring to this vector"); |
||
1668 | #endif |
||
1669 | _LIBCPP_ASSERT(__position != end(), |
||
1670 | "vector::erase(iterator) called with a non-dereferenceable iterator"); |
||
1671 | difference_type __ps = __position - cbegin(); |
||
1672 | pointer __p = this->__begin_ + __ps; |
||
1673 | iterator __r = __make_iter(__p); |
||
1674 | this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); |
||
1675 | return __r; |
||
1676 | } |
||
1677 | |||
1678 | template <class _Tp, class _Allocator> |
||
1679 | typename vector<_Tp, _Allocator>::iterator |
||
1680 | vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) |
||
1681 | { |
||
1682 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1683 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, |
||
1684 | "vector::erase(iterator, iterator) called with an iterator not" |
||
1685 | " referring to this vector"); |
||
1686 | #endif |
||
1687 | _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range"); |
||
1688 | pointer __p = this->__begin_ + (__first - begin()); |
||
1689 | iterator __r = __make_iter(__p); |
||
1690 | if (__first != __last) |
||
1691 | this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p)); |
||
1692 | return __r; |
||
1693 | } |
||
1694 | |||
1695 | template <class _Tp, class _Allocator> |
||
1696 | void |
||
1697 | vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) |
||
1698 | { |
||
1699 | pointer __old_last = this->__end_; |
||
1700 | difference_type __n = __old_last - __to; |
||
1701 | for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_) |
||
1702 | __alloc_traits::construct(this->__alloc(), |
||
1703 | _VSTD::__to_raw_pointer(this->__end_), |
||
1704 | _VSTD::move(*__i)); |
||
1705 | _VSTD::move_backward(__from_s, __from_s + __n, __old_last); |
||
1706 | } |
||
1707 | |||
1708 | template <class _Tp, class _Allocator> |
||
1709 | typename vector<_Tp, _Allocator>::iterator |
||
1710 | vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) |
||
1711 | { |
||
1712 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1713 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1714 | "vector::insert(iterator, x) called with an iterator not" |
||
1715 | " referring to this vector"); |
||
1716 | #endif |
||
1717 | pointer __p = this->__begin_ + (__position - begin()); |
||
1718 | if (this->__end_ < this->__end_cap()) |
||
1719 | { |
||
1720 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1721 | if (__p == this->__end_) |
||
1722 | { |
||
1723 | __alloc_traits::construct(this->__alloc(), |
||
1724 | _VSTD::__to_raw_pointer(this->__end_), __x); |
||
1725 | ++this->__end_; |
||
1726 | } |
||
1727 | else |
||
1728 | { |
||
1729 | __move_range(__p, this->__end_, __p + 1); |
||
1730 | const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); |
||
1731 | if (__p <= __xr && __xr < this->__end_) |
||
1732 | ++__xr; |
||
1733 | *__p = *__xr; |
||
1734 | } |
||
1735 | __annotator.__done(); |
||
1736 | } |
||
1737 | else |
||
1738 | { |
||
1739 | allocator_type& __a = this->__alloc(); |
||
1740 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); |
||
1741 | __v.push_back(__x); |
||
1742 | __p = __swap_out_circular_buffer(__v, __p); |
||
1743 | } |
||
1744 | return __make_iter(__p); |
||
1745 | } |
||
1746 | |||
1747 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1748 | |||
1749 | template <class _Tp, class _Allocator> |
||
1750 | typename vector<_Tp, _Allocator>::iterator |
||
1751 | vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) |
||
1752 | { |
||
1753 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1754 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1755 | "vector::insert(iterator, x) called with an iterator not" |
||
1756 | " referring to this vector"); |
||
1757 | #endif |
||
1758 | pointer __p = this->__begin_ + (__position - begin()); |
||
1759 | if (this->__end_ < this->__end_cap()) |
||
1760 | { |
||
1761 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1762 | if (__p == this->__end_) |
||
1763 | { |
||
1764 | __alloc_traits::construct(this->__alloc(), |
||
1765 | _VSTD::__to_raw_pointer(this->__end_), |
||
1766 | _VSTD::move(__x)); |
||
1767 | ++this->__end_; |
||
1768 | } |
||
1769 | else |
||
1770 | { |
||
1771 | __move_range(__p, this->__end_, __p + 1); |
||
1772 | *__p = _VSTD::move(__x); |
||
1773 | } |
||
1774 | __annotator.__done(); |
||
1775 | } |
||
1776 | else |
||
1777 | { |
||
1778 | allocator_type& __a = this->__alloc(); |
||
1779 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); |
||
1780 | __v.push_back(_VSTD::move(__x)); |
||
1781 | __p = __swap_out_circular_buffer(__v, __p); |
||
1782 | } |
||
1783 | return __make_iter(__p); |
||
1784 | } |
||
1785 | |||
1786 | #ifndef _LIBCPP_HAS_NO_VARIADICS |
||
1787 | |||
1788 | template <class _Tp, class _Allocator> |
||
1789 | template <class... _Args> |
||
1790 | typename vector<_Tp, _Allocator>::iterator |
||
1791 | vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) |
||
1792 | { |
||
1793 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1794 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1795 | "vector::emplace(iterator, x) called with an iterator not" |
||
1796 | " referring to this vector"); |
||
1797 | #endif |
||
1798 | pointer __p = this->__begin_ + (__position - begin()); |
||
1799 | if (this->__end_ < this->__end_cap()) |
||
1800 | { |
||
1801 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1802 | if (__p == this->__end_) |
||
1803 | { |
||
1804 | __alloc_traits::construct(this->__alloc(), |
||
1805 | _VSTD::__to_raw_pointer(this->__end_), |
||
1806 | _VSTD::forward<_Args>(__args)...); |
||
1807 | ++this->__end_; |
||
1808 | } |
||
1809 | else |
||
1810 | { |
||
1811 | value_type __tmp(_VSTD::forward<_Args>(__args)...); |
||
1812 | __move_range(__p, this->__end_, __p + 1); |
||
1813 | *__p = _VSTD::move(__tmp); |
||
1814 | } |
||
1815 | __annotator.__done(); |
||
1816 | } |
||
1817 | else |
||
1818 | { |
||
1819 | allocator_type& __a = this->__alloc(); |
||
1820 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); |
||
1821 | __v.emplace_back(_VSTD::forward<_Args>(__args)...); |
||
1822 | __p = __swap_out_circular_buffer(__v, __p); |
||
1823 | } |
||
1824 | return __make_iter(__p); |
||
1825 | } |
||
1826 | |||
1827 | #endif // _LIBCPP_HAS_NO_VARIADICS |
||
1828 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
1829 | |||
1830 | template <class _Tp, class _Allocator> |
||
1831 | typename vector<_Tp, _Allocator>::iterator |
||
1832 | vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) |
||
1833 | { |
||
1834 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1835 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1836 | "vector::insert(iterator, n, x) called with an iterator not" |
||
1837 | " referring to this vector"); |
||
1838 | #endif |
||
1839 | pointer __p = this->__begin_ + (__position - begin()); |
||
1840 | if (__n > 0) |
||
1841 | { |
||
1842 | if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_)) |
||
1843 | { |
||
1844 | size_type __old_n = __n; |
||
1845 | pointer __old_last = this->__end_; |
||
1846 | if (__n > static_cast<size_type>(this->__end_ - __p)) |
||
1847 | { |
||
1848 | size_type __cx = __n - (this->__end_ - __p); |
||
1849 | __construct_at_end(__cx, __x); |
||
1850 | __n -= __cx; |
||
1851 | } |
||
1852 | if (__n > 0) |
||
1853 | { |
||
1854 | __RAII_IncreaseAnnotator __annotator(*this, __n); |
||
1855 | __move_range(__p, __old_last, __p + __old_n); |
||
1856 | __annotator.__done(); |
||
1857 | const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); |
||
1858 | if (__p <= __xr && __xr < this->__end_) |
||
1859 | __xr += __old_n; |
||
1860 | _VSTD::fill_n(__p, __n, *__xr); |
||
1861 | } |
||
1862 | } |
||
1863 | else |
||
1864 | { |
||
1865 | allocator_type& __a = this->__alloc(); |
||
1866 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); |
||
1867 | __v.__construct_at_end(__n, __x); |
||
1868 | __p = __swap_out_circular_buffer(__v, __p); |
||
1869 | } |
||
1870 | } |
||
1871 | return __make_iter(__p); |
||
1872 | } |
||
1873 | |||
1874 | template <class _Tp, class _Allocator> |
||
1875 | template <class _InputIterator> |
||
1876 | typename enable_if |
||
1877 | < |
||
1878 | __is_input_iterator <_InputIterator>::value && |
||
1879 | !__is_forward_iterator<_InputIterator>::value && |
||
1880 | is_constructible< |
||
1881 | _Tp, |
||
1882 | typename iterator_traits<_InputIterator>::reference>::value, |
||
1883 | typename vector<_Tp, _Allocator>::iterator |
||
1884 | >::type |
||
1885 | vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) |
||
1886 | { |
||
1887 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1888 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1889 | "vector::insert(iterator, range) called with an iterator not" |
||
1890 | " referring to this vector"); |
||
1891 | #endif |
||
1892 | difference_type __off = __position - begin(); |
||
1893 | pointer __p = this->__begin_ + __off; |
||
1894 | allocator_type& __a = this->__alloc(); |
||
1895 | pointer __old_last = this->__end_; |
||
1896 | for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) |
||
1897 | { |
||
1898 | __RAII_IncreaseAnnotator __annotator(*this); |
||
1899 | __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), |
||
1900 | *__first); |
||
1901 | ++this->__end_; |
||
1902 | __annotator.__done(); |
||
1903 | } |
||
1904 | __split_buffer<value_type, allocator_type&> __v(__a); |
||
1905 | if (__first != __last) |
||
1906 | { |
||
1907 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
1908 | try |
||
1909 | { |
||
1910 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
1911 | __v.__construct_at_end(__first, __last); |
||
1912 | difference_type __old_size = __old_last - this->__begin_; |
||
1913 | difference_type __old_p = __p - this->__begin_; |
||
1914 | reserve(__recommend(size() + __v.size())); |
||
1915 | __p = this->__begin_ + __old_p; |
||
1916 | __old_last = this->__begin_ + __old_size; |
||
1917 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
1918 | } |
||
1919 | catch (...) |
||
1920 | { |
||
1921 | erase(__make_iter(__old_last), end()); |
||
1922 | throw; |
||
1923 | } |
||
1924 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
1925 | } |
||
1926 | __p = _VSTD::rotate(__p, __old_last, this->__end_); |
||
1927 | insert(__make_iter(__p), make_move_iterator(__v.begin()), |
||
1928 | make_move_iterator(__v.end())); |
||
1929 | return begin() + __off; |
||
1930 | } |
||
1931 | |||
1932 | template <class _Tp, class _Allocator> |
||
1933 | template <class _ForwardIterator> |
||
1934 | typename enable_if |
||
1935 | < |
||
1936 | __is_forward_iterator<_ForwardIterator>::value && |
||
1937 | is_constructible< |
||
1938 | _Tp, |
||
1939 | typename iterator_traits<_ForwardIterator>::reference>::value, |
||
1940 | typename vector<_Tp, _Allocator>::iterator |
||
1941 | >::type |
||
1942 | vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) |
||
1943 | { |
||
1944 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
1945 | _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, |
||
1946 | "vector::insert(iterator, range) called with an iterator not" |
||
1947 | " referring to this vector"); |
||
1948 | #endif |
||
1949 | pointer __p = this->__begin_ + (__position - begin()); |
||
1950 | difference_type __n = _VSTD::distance(__first, __last); |
||
1951 | if (__n > 0) |
||
1952 | { |
||
1953 | if (__n <= this->__end_cap() - this->__end_) |
||
1954 | { |
||
1955 | size_type __old_n = __n; |
||
1956 | pointer __old_last = this->__end_; |
||
1957 | _ForwardIterator __m = __last; |
||
1958 | difference_type __dx = this->__end_ - __p; |
||
1959 | if (__n > __dx) |
||
1960 | { |
||
1961 | __m = __first; |
||
1962 | difference_type __diff = this->__end_ - __p; |
||
1963 | _VSTD::advance(__m, __diff); |
||
1964 | __construct_at_end(__m, __last, __n - __diff); |
||
1965 | __n = __dx; |
||
1966 | } |
||
1967 | if (__n > 0) |
||
1968 | { |
||
1969 | __RAII_IncreaseAnnotator __annotator(*this, __n); |
||
1970 | __move_range(__p, __old_last, __p + __old_n); |
||
1971 | __annotator.__done(); |
||
1972 | _VSTD::copy(__first, __m, __p); |
||
1973 | } |
||
1974 | } |
||
1975 | else |
||
1976 | { |
||
1977 | allocator_type& __a = this->__alloc(); |
||
1978 | __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); |
||
1979 | __v.__construct_at_end(__first, __last); |
||
1980 | __p = __swap_out_circular_buffer(__v, __p); |
||
1981 | } |
||
1982 | } |
||
1983 | return __make_iter(__p); |
||
1984 | } |
||
1985 | |||
1986 | template <class _Tp, class _Allocator> |
||
1987 | void |
||
1988 | vector<_Tp, _Allocator>::resize(size_type __sz) |
||
1989 | { |
||
1990 | size_type __cs = size(); |
||
1991 | if (__cs < __sz) |
||
1992 | this->__append(__sz - __cs); |
||
1993 | else if (__cs > __sz) |
||
1994 | this->__destruct_at_end(this->__begin_ + __sz); |
||
1995 | } |
||
1996 | |||
1997 | template <class _Tp, class _Allocator> |
||
1998 | void |
||
1999 | vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) |
||
2000 | { |
||
2001 | size_type __cs = size(); |
||
2002 | if (__cs < __sz) |
||
2003 | this->__append(__sz - __cs, __x); |
||
2004 | else if (__cs > __sz) |
||
2005 | this->__destruct_at_end(this->__begin_ + __sz); |
||
2006 | } |
||
2007 | |||
2008 | template <class _Tp, class _Allocator> |
||
2009 | void |
||
2010 | vector<_Tp, _Allocator>::swap(vector& __x) |
||
2011 | #if _LIBCPP_STD_VER >= 14 |
||
2012 | _NOEXCEPT |
||
2013 | #else |
||
2014 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || |
||
2015 | __is_nothrow_swappable<allocator_type>::value) |
||
2016 | #endif |
||
2017 | { |
||
2018 | _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"); |
||
2022 | _VSTD::swap(this->__begin_, __x.__begin_); |
||
2023 | _VSTD::swap(this->__end_, __x.__end_); |
||
2024 | _VSTD::swap(this->__end_cap(), __x.__end_cap()); |
||
2025 | __swap_allocator(this->__alloc(), __x.__alloc(), |
||
2026 | integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>()); |
||
2027 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
2028 | __get_db()->swap(this, &__x); |
||
2029 | #endif // _LIBCPP_DEBUG_LEVEL >= 2 |
||
2030 | } |
||
2031 | |||
2032 | template <class _Tp, class _Allocator> |
||
2033 | bool |
||
2034 | vector<_Tp, _Allocator>::__invariants() const |
||
2035 | { |
||
2036 | if (this->__begin_ == nullptr) |
||
2037 | { |
||
2038 | if (this->__end_ != nullptr || this->__end_cap() != nullptr) |
||
2039 | return false; |
||
2040 | } |
||
2041 | else |
||
2042 | { |
||
2043 | if (this->__begin_ > this->__end_) |
||
2044 | return false; |
||
2045 | if (this->__begin_ == this->__end_cap()) |
||
2046 | return false; |
||
2047 | if (this->__end_ > this->__end_cap()) |
||
2048 | return false; |
||
2049 | } |
||
2050 | return true; |
||
2051 | } |
||
2052 | |||
2053 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
2054 | |||
2055 | template <class _Tp, class _Allocator> |
||
2056 | bool |
||
2057 | vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const |
||
2058 | { |
||
2059 | return this->__begin_ <= __i->base() && __i->base() < this->__end_; |
||
2060 | } |
||
2061 | |||
2062 | template <class _Tp, class _Allocator> |
||
2063 | bool |
||
2064 | vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const |
||
2065 | { |
||
2066 | return this->__begin_ < __i->base() && __i->base() <= this->__end_; |
||
2067 | } |
||
2068 | |||
2069 | template <class _Tp, class _Allocator> |
||
2070 | bool |
||
2071 | vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const |
||
2072 | { |
||
2073 | const_pointer __p = __i->base() + __n; |
||
2074 | return this->__begin_ <= __p && __p <= this->__end_; |
||
2075 | } |
||
2076 | |||
2077 | template <class _Tp, class _Allocator> |
||
2078 | bool |
||
2079 | vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const |
||
2080 | { |
||
2081 | const_pointer __p = __i->base() + __n; |
||
2082 | return this->__begin_ <= __p && __p < this->__end_; |
||
2083 | } |
||
2084 | |||
2085 | #endif // _LIBCPP_DEBUG_LEVEL >= 2 |
||
2086 | |||
2087 | template <class _Tp, class _Allocator> |
||
2088 | inline _LIBCPP_INLINE_VISIBILITY |
||
2089 | void |
||
2090 | vector<_Tp, _Allocator>::__invalidate_all_iterators() |
||
2091 | { |
||
2092 | #if _LIBCPP_DEBUG_LEVEL >= 2 |
||
2093 | __get_db()->__invalidate_all(this); |
||
2094 | #endif // _LIBCPP_DEBUG_LEVEL >= 2 |
||
2095 | } |
||
2096 | |||
2097 | // vector<bool> |
||
2098 | |||
2099 | template <class _Allocator> class vector<bool, _Allocator>; |
||
2100 | |||
2101 | template <class _Allocator> struct hash<vector<bool, _Allocator> >; |
||
2102 | |||
2103 | template <class _Allocator> |
||
2104 | struct __has_storage_type<vector<bool, _Allocator> > |
||
2105 | { |
||
2106 | static const bool value = true; |
||
2107 | }; |
||
2108 | |||
2109 | template <class _Allocator> |
||
2110 | class _LIBCPP_TYPE_VIS_ONLY vector<bool, _Allocator> |
||
2111 | : private __vector_base_common<true> |
||
2112 | { |
||
2113 | public: |
||
2114 | typedef vector __self; |
||
2115 | typedef bool value_type; |
||
2116 | typedef _Allocator allocator_type; |
||
2117 | typedef allocator_traits<allocator_type> __alloc_traits; |
||
2118 | typedef typename __alloc_traits::size_type size_type; |
||
2119 | typedef typename __alloc_traits::difference_type difference_type; |
||
2120 | typedef size_type __storage_type; |
||
2121 | typedef __bit_iterator<vector, false> pointer; |
||
2122 | typedef __bit_iterator<vector, true> const_pointer; |
||
2123 | typedef pointer iterator; |
||
2124 | typedef const_pointer const_iterator; |
||
2125 | typedef _VSTD::reverse_iterator<iterator> reverse_iterator; |
||
2126 | typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; |
||
2127 | |||
2128 | private: |
||
2129 | typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator; |
||
2130 | typedef allocator_traits<__storage_allocator> __storage_traits; |
||
2131 | typedef typename __storage_traits::pointer __storage_pointer; |
||
2132 | typedef typename __storage_traits::const_pointer __const_storage_pointer; |
||
2133 | |||
2134 | __storage_pointer __begin_; |
||
2135 | size_type __size_; |
||
2136 | __compressed_pair<size_type, __storage_allocator> __cap_alloc_; |
||
2137 | public: |
||
2138 | typedef __bit_reference<vector> reference; |
||
2139 | typedef __bit_const_reference<vector> const_reference; |
||
2140 | private: |
||
2141 | _LIBCPP_INLINE_VISIBILITY |
||
2142 | size_type& __cap() _NOEXCEPT |
||
2143 | {return __cap_alloc_.first();} |
||
2144 | _LIBCPP_INLINE_VISIBILITY |
||
2145 | const size_type& __cap() const _NOEXCEPT |
||
2146 | {return __cap_alloc_.first();} |
||
2147 | _LIBCPP_INLINE_VISIBILITY |
||
2148 | __storage_allocator& __alloc() _NOEXCEPT |
||
2149 | {return __cap_alloc_.second();} |
||
2150 | _LIBCPP_INLINE_VISIBILITY |
||
2151 | const __storage_allocator& __alloc() const _NOEXCEPT |
||
2152 | {return __cap_alloc_.second();} |
||
2153 | |||
2154 | static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); |
||
2155 | |||
2156 | _LIBCPP_INLINE_VISIBILITY |
||
2157 | static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT |
||
2158 | {return __n * __bits_per_word;} |
||
2159 | _LIBCPP_INLINE_VISIBILITY |
||
2160 | static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT |
||
2161 | {return (__n - 1) / __bits_per_word + 1;} |
||
2162 | |||
2163 | public: |
||
2164 | _LIBCPP_INLINE_VISIBILITY |
||
2165 | vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); |
||
2166 | |||
2167 | _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) |
||
2168 | #if _LIBCPP_STD_VER <= 14 |
||
2169 | _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value); |
||
2170 | #else |
||
2171 | _NOEXCEPT; |
||
2172 | #endif |
||
2173 | ~vector(); |
||
2174 | explicit vector(size_type __n); |
||
2175 | #if _LIBCPP_STD_VER > 11 |
||
2176 | explicit vector(size_type __n, const allocator_type& __a); |
||
2177 | #endif |
||
2178 | vector(size_type __n, const value_type& __v); |
||
2179 | vector(size_type __n, const value_type& __v, const allocator_type& __a); |
||
2180 | template <class _InputIterator> |
||
2181 | vector(_InputIterator __first, _InputIterator __last, |
||
2182 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
2183 | !__is_forward_iterator<_InputIterator>::value>::type* = 0); |
||
2184 | template <class _InputIterator> |
||
2185 | vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, |
||
2186 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
2187 | !__is_forward_iterator<_InputIterator>::value>::type* = 0); |
||
2188 | template <class _ForwardIterator> |
||
2189 | vector(_ForwardIterator __first, _ForwardIterator __last, |
||
2190 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); |
||
2191 | template <class _ForwardIterator> |
||
2192 | vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, |
||
2193 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); |
||
2194 | |||
2195 | vector(const vector& __v); |
||
2196 | vector(const vector& __v, const allocator_type& __a); |
||
2197 | vector& operator=(const vector& __v); |
||
2198 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2199 | vector(initializer_list<value_type> __il); |
||
2200 | vector(initializer_list<value_type> __il, const allocator_type& __a); |
||
2201 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2202 | |||
2203 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
2204 | _LIBCPP_INLINE_VISIBILITY |
||
2205 | vector(vector&& __v) |
||
2206 | #if _LIBCPP_STD_VER > 14 |
||
2207 | _NOEXCEPT; |
||
2208 | #else |
||
2209 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); |
||
2210 | #endif |
||
2211 | vector(vector&& __v, const allocator_type& __a); |
||
2212 | _LIBCPP_INLINE_VISIBILITY |
||
2213 | vector& operator=(vector&& __v) |
||
2214 | _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)); |
||
2215 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
2216 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2217 | _LIBCPP_INLINE_VISIBILITY |
||
2218 | vector& operator=(initializer_list<value_type> __il) |
||
2219 | {assign(__il.begin(), __il.end()); return *this;} |
||
2220 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2221 | |||
2222 | template <class _InputIterator> |
||
2223 | typename enable_if |
||
2224 | < |
||
2225 | __is_input_iterator<_InputIterator>::value && |
||
2226 | !__is_forward_iterator<_InputIterator>::value, |
||
2227 | void |
||
2228 | >::type |
||
2229 | assign(_InputIterator __first, _InputIterator __last); |
||
2230 | template <class _ForwardIterator> |
||
2231 | typename enable_if |
||
2232 | < |
||
2233 | __is_forward_iterator<_ForwardIterator>::value, |
||
2234 | void |
||
2235 | >::type |
||
2236 | assign(_ForwardIterator __first, _ForwardIterator __last); |
||
2237 | |||
2238 | void assign(size_type __n, const value_type& __x); |
||
2239 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2240 | _LIBCPP_INLINE_VISIBILITY |
||
2241 | void assign(initializer_list<value_type> __il) |
||
2242 | {assign(__il.begin(), __il.end());} |
||
2243 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2244 | |||
2245 | _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT |
||
2246 | {return allocator_type(this->__alloc());} |
||
2247 | |||
2248 | size_type max_size() const _NOEXCEPT; |
||
2249 | _LIBCPP_INLINE_VISIBILITY |
||
2250 | size_type capacity() const _NOEXCEPT |
||
2251 | {return __internal_cap_to_external(__cap());} |
||
2252 | _LIBCPP_INLINE_VISIBILITY |
||
2253 | size_type size() const _NOEXCEPT |
||
2254 | {return __size_;} |
||
2255 | _LIBCPP_INLINE_VISIBILITY |
||
2256 | bool empty() const _NOEXCEPT |
||
2257 | {return __size_ == 0;} |
||
2258 | void reserve(size_type __n); |
||
2259 | void shrink_to_fit() _NOEXCEPT; |
||
2260 | |||
2261 | _LIBCPP_INLINE_VISIBILITY |
||
2262 | iterator begin() _NOEXCEPT |
||
2263 | {return __make_iter(0);} |
||
2264 | _LIBCPP_INLINE_VISIBILITY |
||
2265 | const_iterator begin() const _NOEXCEPT |
||
2266 | {return __make_iter(0);} |
||
2267 | _LIBCPP_INLINE_VISIBILITY |
||
2268 | iterator end() _NOEXCEPT |
||
2269 | {return __make_iter(__size_);} |
||
2270 | _LIBCPP_INLINE_VISIBILITY |
||
2271 | const_iterator end() const _NOEXCEPT |
||
2272 | {return __make_iter(__size_);} |
||
2273 | |||
2274 | _LIBCPP_INLINE_VISIBILITY |
||
2275 | reverse_iterator rbegin() _NOEXCEPT |
||
2276 | {return reverse_iterator(end());} |
||
2277 | _LIBCPP_INLINE_VISIBILITY |
||
2278 | const_reverse_iterator rbegin() const _NOEXCEPT |
||
2279 | {return const_reverse_iterator(end());} |
||
2280 | _LIBCPP_INLINE_VISIBILITY |
||
2281 | reverse_iterator rend() _NOEXCEPT |
||
2282 | {return reverse_iterator(begin());} |
||
2283 | _LIBCPP_INLINE_VISIBILITY |
||
2284 | const_reverse_iterator rend() const _NOEXCEPT |
||
2285 | {return const_reverse_iterator(begin());} |
||
2286 | |||
2287 | _LIBCPP_INLINE_VISIBILITY |
||
2288 | const_iterator cbegin() const _NOEXCEPT |
||
2289 | {return __make_iter(0);} |
||
2290 | _LIBCPP_INLINE_VISIBILITY |
||
2291 | const_iterator cend() const _NOEXCEPT |
||
2292 | {return __make_iter(__size_);} |
||
2293 | _LIBCPP_INLINE_VISIBILITY |
||
2294 | const_reverse_iterator crbegin() const _NOEXCEPT |
||
2295 | {return rbegin();} |
||
2296 | _LIBCPP_INLINE_VISIBILITY |
||
2297 | const_reverse_iterator crend() const _NOEXCEPT |
||
2298 | {return rend();} |
||
2299 | |||
2300 | _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);} |
||
2301 | _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);} |
||
2302 | reference at(size_type __n); |
||
2303 | const_reference at(size_type __n) const; |
||
2304 | |||
2305 | _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);} |
||
2306 | _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);} |
||
2307 | _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);} |
||
2308 | _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);} |
||
2309 | |||
2310 | void push_back(const value_type& __x); |
||
2311 | #if _LIBCPP_STD_VER > 11 |
||
2312 | template <class... _Args> |
||
2313 | _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args) |
||
2314 | { push_back ( value_type ( _VSTD::forward<_Args>(__args)... )); } |
||
2315 | #endif |
||
2316 | |||
2317 | _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;} |
||
2318 | |||
2319 | #if _LIBCPP_STD_VER > 11 |
||
2320 | template <class... _Args> |
||
2321 | _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args) |
||
2322 | { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); } |
||
2323 | #endif |
||
2324 | |||
2325 | iterator insert(const_iterator __position, const value_type& __x); |
||
2326 | iterator insert(const_iterator __position, size_type __n, const value_type& __x); |
||
2327 | iterator insert(const_iterator __position, size_type __n, const_reference __x); |
||
2328 | template <class _InputIterator> |
||
2329 | typename enable_if |
||
2330 | < |
||
2331 | __is_input_iterator <_InputIterator>::value && |
||
2332 | !__is_forward_iterator<_InputIterator>::value, |
||
2333 | iterator |
||
2334 | >::type |
||
2335 | insert(const_iterator __position, _InputIterator __first, _InputIterator __last); |
||
2336 | template <class _ForwardIterator> |
||
2337 | typename enable_if |
||
2338 | < |
||
2339 | __is_forward_iterator<_ForwardIterator>::value, |
||
2340 | iterator |
||
2341 | >::type |
||
2342 | insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); |
||
2343 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2344 | _LIBCPP_INLINE_VISIBILITY |
||
2345 | iterator insert(const_iterator __position, initializer_list<value_type> __il) |
||
2346 | {return insert(__position, __il.begin(), __il.end());} |
||
2347 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2348 | |||
2349 | _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); |
||
2350 | iterator erase(const_iterator __first, const_iterator __last); |
||
2351 | |||
2352 | _LIBCPP_INLINE_VISIBILITY |
||
2353 | void clear() _NOEXCEPT {__size_ = 0;} |
||
2354 | |||
2355 | void swap(vector&) |
||
2356 | #if _LIBCPP_STD_VER >= 14 |
||
2357 | _NOEXCEPT; |
||
2358 | #else |
||
2359 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || |
||
2360 | __is_nothrow_swappable<allocator_type>::value); |
||
2361 | #endif |
||
2362 | |||
2363 | void resize(size_type __sz, value_type __x = false); |
||
2364 | void flip() _NOEXCEPT; |
||
2365 | |||
2366 | bool __invariants() const; |
||
2367 | |||
2368 | private: |
||
2369 | _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); |
||
2370 | void allocate(size_type __n); |
||
2371 | void deallocate() _NOEXCEPT; |
||
2372 | _LIBCPP_INLINE_VISIBILITY |
||
2373 | static size_type __align_it(size_type __new_size) _NOEXCEPT |
||
2374 | {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}; |
||
2375 | _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; |
||
2376 | _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x); |
||
2377 | template <class _ForwardIterator> |
||
2378 | typename enable_if |
||
2379 | < |
||
2380 | __is_forward_iterator<_ForwardIterator>::value, |
||
2381 | void |
||
2382 | >::type |
||
2383 | __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); |
||
2384 | void __append(size_type __n, const_reference __x); |
||
2385 | _LIBCPP_INLINE_VISIBILITY |
||
2386 | reference __make_ref(size_type __pos) _NOEXCEPT |
||
2387 | {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} |
||
2388 | _LIBCPP_INLINE_VISIBILITY |
||
2389 | const_reference __make_ref(size_type __pos) const _NOEXCEPT |
||
2390 | {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} |
||
2391 | _LIBCPP_INLINE_VISIBILITY |
||
2392 | iterator __make_iter(size_type __pos) _NOEXCEPT |
||
2393 | {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} |
||
2394 | _LIBCPP_INLINE_VISIBILITY |
||
2395 | const_iterator __make_iter(size_type __pos) const _NOEXCEPT |
||
2396 | {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} |
||
2397 | _LIBCPP_INLINE_VISIBILITY |
||
2398 | iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT |
||
2399 | {return begin() + (__p - cbegin());} |
||
2400 | |||
2401 | _LIBCPP_INLINE_VISIBILITY |
||
2402 | void __copy_assign_alloc(const vector& __v) |
||
2403 | {__copy_assign_alloc(__v, integral_constant<bool, |
||
2404 | __storage_traits::propagate_on_container_copy_assignment::value>());} |
||
2405 | _LIBCPP_INLINE_VISIBILITY |
||
2406 | void __copy_assign_alloc(const vector& __c, true_type) |
||
2407 | { |
||
2408 | if (__alloc() != __c.__alloc()) |
||
2409 | deallocate(); |
||
2410 | __alloc() = __c.__alloc(); |
||
2411 | } |
||
2412 | |||
2413 | _LIBCPP_INLINE_VISIBILITY |
||
2414 | void __copy_assign_alloc(const vector&, false_type) |
||
2415 | {} |
||
2416 | |||
2417 | void __move_assign(vector& __c, false_type); |
||
2418 | void __move_assign(vector& __c, true_type) |
||
2419 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); |
||
2420 | _LIBCPP_INLINE_VISIBILITY |
||
2421 | void __move_assign_alloc(vector& __c) |
||
2422 | _NOEXCEPT_( |
||
2423 | !__storage_traits::propagate_on_container_move_assignment::value || |
||
2424 | is_nothrow_move_assignable<allocator_type>::value) |
||
2425 | {__move_assign_alloc(__c, integral_constant<bool, |
||
2426 | __storage_traits::propagate_on_container_move_assignment::value>());} |
||
2427 | _LIBCPP_INLINE_VISIBILITY |
||
2428 | void __move_assign_alloc(vector& __c, true_type) |
||
2429 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) |
||
2430 | { |
||
2431 | __alloc() = _VSTD::move(__c.__alloc()); |
||
2432 | } |
||
2433 | |||
2434 | _LIBCPP_INLINE_VISIBILITY |
||
2435 | void __move_assign_alloc(vector&, false_type) |
||
2436 | _NOEXCEPT |
||
2437 | {} |
||
2438 | |||
2439 | size_t __hash_code() const _NOEXCEPT; |
||
2440 | |||
2441 | friend class __bit_reference<vector>; |
||
2442 | friend class __bit_const_reference<vector>; |
||
2443 | friend class __bit_iterator<vector, false>; |
||
2444 | friend class __bit_iterator<vector, true>; |
||
2445 | friend struct __bit_array<vector>; |
||
2446 | friend struct _LIBCPP_TYPE_VIS_ONLY hash<vector>; |
||
2447 | }; |
||
2448 | |||
2449 | template <class _Allocator> |
||
2450 | inline _LIBCPP_INLINE_VISIBILITY |
||
2451 | void |
||
2452 | vector<bool, _Allocator>::__invalidate_all_iterators() |
||
2453 | { |
||
2454 | } |
||
2455 | |||
2456 | // Allocate space for __n objects |
||
2457 | // throws length_error if __n > max_size() |
||
2458 | // throws (probably bad_alloc) if memory run out |
||
2459 | // Precondition: __begin_ == __end_ == __cap() == 0 |
||
2460 | // Precondition: __n > 0 |
||
2461 | // Postcondition: capacity() == __n |
||
2462 | // Postcondition: size() == 0 |
||
2463 | template <class _Allocator> |
||
2464 | void |
||
2465 | vector<bool, _Allocator>::allocate(size_type __n) |
||
2466 | { |
||
2467 | if (__n > max_size()) |
||
2468 | this->__throw_length_error(); |
||
2469 | __n = __external_cap_to_internal(__n); |
||
2470 | this->__begin_ = __storage_traits::allocate(this->__alloc(), __n); |
||
2471 | this->__size_ = 0; |
||
2472 | this->__cap() = __n; |
||
2473 | } |
||
2474 | |||
2475 | template <class _Allocator> |
||
2476 | void |
||
2477 | vector<bool, _Allocator>::deallocate() _NOEXCEPT |
||
2478 | { |
||
2479 | if (this->__begin_ != nullptr) |
||
2480 | { |
||
2481 | __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); |
||
2482 | __invalidate_all_iterators(); |
||
2483 | this->__begin_ = nullptr; |
||
2484 | this->__size_ = this->__cap() = 0; |
||
2485 | } |
||
2486 | } |
||
2487 | |||
2488 | template <class _Allocator> |
||
2489 | typename vector<bool, _Allocator>::size_type |
||
2490 | vector<bool, _Allocator>::max_size() const _NOEXCEPT |
||
2491 | { |
||
2492 | size_type __amax = __storage_traits::max_size(__alloc()); |
||
2493 | size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always |
||
2494 | if (__nmax / __bits_per_word <= __amax) |
||
2495 | return __nmax; |
||
2496 | return __internal_cap_to_external(__amax); |
||
2497 | } |
||
2498 | |||
2499 | // Precondition: __new_size > capacity() |
||
2500 | template <class _Allocator> |
||
2501 | inline _LIBCPP_INLINE_VISIBILITY |
||
2502 | typename vector<bool, _Allocator>::size_type |
||
2503 | vector<bool, _Allocator>::__recommend(size_type __new_size) const |
||
2504 | { |
||
2505 | const size_type __ms = max_size(); |
||
2506 | if (__new_size > __ms) |
||
2507 | this->__throw_length_error(); |
||
2508 | const size_type __cap = capacity(); |
||
2509 | if (__cap >= __ms / 2) |
||
2510 | return __ms; |
||
2511 | return _VSTD::max(2*__cap, __align_it(__new_size)); |
||
2512 | } |
||
2513 | |||
2514 | // Default constructs __n objects starting at __end_ |
||
2515 | // Precondition: __n > 0 |
||
2516 | // Precondition: size() + __n <= capacity() |
||
2517 | // Postcondition: size() == size() + __n |
||
2518 | template <class _Allocator> |
||
2519 | inline _LIBCPP_INLINE_VISIBILITY |
||
2520 | void |
||
2521 | vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) |
||
2522 | { |
||
2523 | size_type __old_size = this->__size_; |
||
2524 | this->__size_ += __n; |
||
2525 | _VSTD::fill_n(__make_iter(__old_size), __n, __x); |
||
2526 | } |
||
2527 | |||
2528 | template <class _Allocator> |
||
2529 | template <class _ForwardIterator> |
||
2530 | typename enable_if |
||
2531 | < |
||
2532 | __is_forward_iterator<_ForwardIterator>::value, |
||
2533 | void |
||
2534 | >::type |
||
2535 | vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) |
||
2536 | { |
||
2537 | size_type __old_size = this->__size_; |
||
2538 | this->__size_ += _VSTD::distance(__first, __last); |
||
2539 | _VSTD::copy(__first, __last, __make_iter(__old_size)); |
||
2540 | } |
||
2541 | |||
2542 | template <class _Allocator> |
||
2543 | inline _LIBCPP_INLINE_VISIBILITY |
||
2544 | vector<bool, _Allocator>::vector() |
||
2545 | _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) |
||
2546 | : __begin_(nullptr), |
||
2547 | __size_(0), |
||
2548 | __cap_alloc_(0) |
||
2549 | { |
||
2550 | } |
||
2551 | |||
2552 | template <class _Allocator> |
||
2553 | inline _LIBCPP_INLINE_VISIBILITY |
||
2554 | vector<bool, _Allocator>::vector(const allocator_type& __a) |
||
2555 | #if _LIBCPP_STD_VER <= 14 |
||
2556 | _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value) |
||
2557 | #else |
||
2558 | _NOEXCEPT |
||
2559 | #endif |
||
2560 | : __begin_(nullptr), |
||
2561 | __size_(0), |
||
2562 | __cap_alloc_(0, static_cast<__storage_allocator>(__a)) |
||
2563 | { |
||
2564 | } |
||
2565 | |||
2566 | template <class _Allocator> |
||
2567 | vector<bool, _Allocator>::vector(size_type __n) |
||
2568 | : __begin_(nullptr), |
||
2569 | __size_(0), |
||
2570 | __cap_alloc_(0) |
||
2571 | { |
||
2572 | if (__n > 0) |
||
2573 | { |
||
2574 | allocate(__n); |
||
2575 | __construct_at_end(__n, false); |
||
2576 | } |
||
2577 | } |
||
2578 | |||
2579 | #if _LIBCPP_STD_VER > 11 |
||
2580 | template <class _Allocator> |
||
2581 | vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a) |
||
2582 | : __begin_(nullptr), |
||
2583 | __size_(0), |
||
2584 | __cap_alloc_(0, static_cast<__storage_allocator>(__a)) |
||
2585 | { |
||
2586 | if (__n > 0) |
||
2587 | { |
||
2588 | allocate(__n); |
||
2589 | __construct_at_end(__n, false); |
||
2590 | } |
||
2591 | } |
||
2592 | #endif |
||
2593 | |||
2594 | template <class _Allocator> |
||
2595 | vector<bool, _Allocator>::vector(size_type __n, const value_type& __x) |
||
2596 | : __begin_(nullptr), |
||
2597 | __size_(0), |
||
2598 | __cap_alloc_(0) |
||
2599 | { |
||
2600 | if (__n > 0) |
||
2601 | { |
||
2602 | allocate(__n); |
||
2603 | __construct_at_end(__n, __x); |
||
2604 | } |
||
2605 | } |
||
2606 | |||
2607 | template <class _Allocator> |
||
2608 | vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) |
||
2609 | : __begin_(nullptr), |
||
2610 | __size_(0), |
||
2611 | __cap_alloc_(0, static_cast<__storage_allocator>(__a)) |
||
2612 | { |
||
2613 | if (__n > 0) |
||
2614 | { |
||
2615 | allocate(__n); |
||
2616 | __construct_at_end(__n, __x); |
||
2617 | } |
||
2618 | } |
||
2619 | |||
2620 | template <class _Allocator> |
||
2621 | template <class _InputIterator> |
||
2622 | vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, |
||
2623 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
2624 | !__is_forward_iterator<_InputIterator>::value>::type*) |
||
2625 | : __begin_(nullptr), |
||
2626 | __size_(0), |
||
2627 | __cap_alloc_(0) |
||
2628 | { |
||
2629 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
2630 | try |
||
2631 | { |
||
2632 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
2633 | for (; __first != __last; ++__first) |
||
2634 | push_back(*__first); |
||
2635 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
2636 | } |
||
2637 | catch (...) |
||
2638 | { |
||
2639 | if (__begin_ != nullptr) |
||
2640 | __storage_traits::deallocate(__alloc(), __begin_, __cap()); |
||
2641 | __invalidate_all_iterators(); |
||
2642 | throw; |
||
2643 | } |
||
2644 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
2645 | } |
||
2646 | |||
2647 | template <class _Allocator> |
||
2648 | template <class _InputIterator> |
||
2649 | vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, |
||
2650 | typename enable_if<__is_input_iterator <_InputIterator>::value && |
||
2651 | !__is_forward_iterator<_InputIterator>::value>::type*) |
||
2652 | : __begin_(nullptr), |
||
2653 | __size_(0), |
||
2654 | __cap_alloc_(0, static_cast<__storage_allocator>(__a)) |
||
2655 | { |
||
2656 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
2657 | try |
||
2658 | { |
||
2659 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
2660 | for (; __first != __last; ++__first) |
||
2661 | push_back(*__first); |
||
2662 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
2663 | } |
||
2664 | catch (...) |
||
2665 | { |
||
2666 | if (__begin_ != nullptr) |
||
2667 | __storage_traits::deallocate(__alloc(), __begin_, __cap()); |
||
2668 | __invalidate_all_iterators(); |
||
2669 | throw; |
||
2670 | } |
||
2671 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
2672 | } |
||
2673 | |||
2674 | template <class _Allocator> |
||
2675 | template <class _ForwardIterator> |
||
2676 | vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, |
||
2677 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) |
||
2678 | : __begin_(nullptr), |
||
2679 | __size_(0), |
||
2680 | __cap_alloc_(0) |
||
2681 | { |
||
2682 | size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); |
||
2683 | if (__n > 0) |
||
2684 | { |
||
2685 | allocate(__n); |
||
2686 | __construct_at_end(__first, __last); |
||
2687 | } |
||
2688 | } |
||
2689 | |||
2690 | template <class _Allocator> |
||
2691 | template <class _ForwardIterator> |
||
2692 | vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, |
||
2693 | typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) |
||
2694 | : __begin_(nullptr), |
||
2695 | __size_(0), |
||
2696 | __cap_alloc_(0, static_cast<__storage_allocator>(__a)) |
||
2697 | { |
||
2698 | size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); |
||
2699 | if (__n > 0) |
||
2700 | { |
||
2701 | allocate(__n); |
||
2702 | __construct_at_end(__first, __last); |
||
2703 | } |
||
2704 | } |
||
2705 | |||
2706 | #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2707 | |||
2708 | template <class _Allocator> |
||
2709 | vector<bool, _Allocator>::vector(initializer_list<value_type> __il) |
||
2710 | : __begin_(nullptr), |
||
2711 | __size_(0), |
||
2712 | __cap_alloc_(0) |
||
2713 | { |
||
2714 | size_type __n = static_cast<size_type>(__il.size()); |
||
2715 | if (__n > 0) |
||
2716 | { |
||
2717 | allocate(__n); |
||
2718 | __construct_at_end(__il.begin(), __il.end()); |
||
2719 | } |
||
2720 | } |
||
2721 | |||
2722 | template <class _Allocator> |
||
2723 | vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) |
||
2724 | : __begin_(nullptr), |
||
2725 | __size_(0), |
||
2726 | __cap_alloc_(0, static_cast<__storage_allocator>(__a)) |
||
2727 | { |
||
2728 | size_type __n = static_cast<size_type>(__il.size()); |
||
2729 | if (__n > 0) |
||
2730 | { |
||
2731 | allocate(__n); |
||
2732 | __construct_at_end(__il.begin(), __il.end()); |
||
2733 | } |
||
2734 | } |
||
2735 | |||
2736 | #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS |
||
2737 | |||
2738 | template <class _Allocator> |
||
2739 | vector<bool, _Allocator>::~vector() |
||
2740 | { |
||
2741 | if (__begin_ != nullptr) |
||
2742 | __storage_traits::deallocate(__alloc(), __begin_, __cap()); |
||
2743 | __invalidate_all_iterators(); |
||
2744 | } |
||
2745 | |||
2746 | template <class _Allocator> |
||
2747 | vector<bool, _Allocator>::vector(const vector& __v) |
||
2748 | : __begin_(nullptr), |
||
2749 | __size_(0), |
||
2750 | __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) |
||
2751 | { |
||
2752 | if (__v.size() > 0) |
||
2753 | { |
||
2754 | allocate(__v.size()); |
||
2755 | __construct_at_end(__v.begin(), __v.end()); |
||
2756 | } |
||
2757 | } |
||
2758 | |||
2759 | template <class _Allocator> |
||
2760 | vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) |
||
2761 | : __begin_(nullptr), |
||
2762 | __size_(0), |
||
2763 | __cap_alloc_(0, __a) |
||
2764 | { |
||
2765 | if (__v.size() > 0) |
||
2766 | { |
||
2767 | allocate(__v.size()); |
||
2768 | __construct_at_end(__v.begin(), __v.end()); |
||
2769 | } |
||
2770 | } |
||
2771 | |||
2772 | template <class _Allocator> |
||
2773 | vector<bool, _Allocator>& |
||
2774 | vector<bool, _Allocator>::operator=(const vector& __v) |
||
2775 | { |
||
2776 | if (this != &__v) |
||
2777 | { |
||
2778 | __copy_assign_alloc(__v); |
||
2779 | if (__v.__size_) |
||
2780 | { |
||
2781 | if (__v.__size_ > capacity()) |
||
2782 | { |
||
2783 | deallocate(); |
||
2784 | allocate(__v.__size_); |
||
2785 | } |
||
2786 | _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); |
||
2787 | } |
||
2788 | __size_ = __v.__size_; |
||
2789 | } |
||
2790 | return *this; |
||
2791 | } |
||
2792 | |||
2793 | #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
2794 | |||
2795 | template <class _Allocator> |
||
2796 | inline _LIBCPP_INLINE_VISIBILITY |
||
2797 | vector<bool, _Allocator>::vector(vector&& __v) |
||
2798 | #if _LIBCPP_STD_VER > 14 |
||
2799 | _NOEXCEPT |
||
2800 | #else |
||
2801 | _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) |
||
2802 | #endif |
||
2803 | : __begin_(__v.__begin_), |
||
2804 | __size_(__v.__size_), |
||
2805 | __cap_alloc_(__v.__cap_alloc_) |
||
2806 | { |
||
2807 | __v.__begin_ = nullptr; |
||
2808 | __v.__size_ = 0; |
||
2809 | __v.__cap() = 0; |
||
2810 | } |
||
2811 | |||
2812 | template <class _Allocator> |
||
2813 | vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a) |
||
2814 | : __begin_(nullptr), |
||
2815 | __size_(0), |
||
2816 | __cap_alloc_(0, __a) |
||
2817 | { |
||
2818 | if (__a == allocator_type(__v.__alloc())) |
||
2819 | { |
||
2820 | this->__begin_ = __v.__begin_; |
||
2821 | this->__size_ = __v.__size_; |
||
2822 | this->__cap() = __v.__cap(); |
||
2823 | __v.__begin_ = nullptr; |
||
2824 | __v.__cap() = __v.__size_ = 0; |
||
2825 | } |
||
2826 | else if (__v.size() > 0) |
||
2827 | { |
||
2828 | allocate(__v.size()); |
||
2829 | __construct_at_end(__v.begin(), __v.end()); |
||
2830 | } |
||
2831 | } |
||
2832 | |||
2833 | template <class _Allocator> |
||
2834 | inline _LIBCPP_INLINE_VISIBILITY |
||
2835 | vector<bool, _Allocator>& |
||
2836 | vector<bool, _Allocator>::operator=(vector&& __v) |
||
2837 | _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value)) |
||
2838 | { |
||
2839 | __move_assign(__v, integral_constant<bool, |
||
2840 | __storage_traits::propagate_on_container_move_assignment::value>()); |
||
2841 | return *this; |
||
2842 | } |
||
2843 | |||
2844 | template <class _Allocator> |
||
2845 | void |
||
2846 | vector<bool, _Allocator>::__move_assign(vector& __c, false_type) |
||
2847 | { |
||
2848 | if (__alloc() != __c.__alloc()) |
||
2849 | assign(__c.begin(), __c.end()); |
||
2850 | else |
||
2851 | __move_assign(__c, true_type()); |
||
2852 | } |
||
2853 | |||
2854 | template <class _Allocator> |
||
2855 | void |
||
2856 | vector<bool, _Allocator>::__move_assign(vector& __c, true_type) |
||
2857 | _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) |
||
2858 | { |
||
2859 | deallocate(); |
||
2860 | __move_assign_alloc(__c); |
||
2861 | this->__begin_ = __c.__begin_; |
||
2862 | this->__size_ = __c.__size_; |
||
2863 | this->__cap() = __c.__cap(); |
||
2864 | __c.__begin_ = nullptr; |
||
2865 | __c.__cap() = __c.__size_ = 0; |
||
2866 | } |
||
2867 | |||
2868 | #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES |
||
2869 | |||
2870 | template <class _Allocator> |
||
2871 | void |
||
2872 | vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) |
||
2873 | { |
||
2874 | __size_ = 0; |
||
2875 | if (__n > 0) |
||
2876 | { |
||
2877 | size_type __c = capacity(); |
||
2878 | if (__n <= __c) |
||
2879 | __size_ = __n; |
||
2880 | else |
||
2881 | { |
||
2882 | vector __v(__alloc()); |
||
2883 | __v.reserve(__recommend(__n)); |
||
2884 | __v.__size_ = __n; |
||
2885 | swap(__v); |
||
2886 | } |
||
2887 | _VSTD::fill_n(begin(), __n, __x); |
||
2888 | } |
||
2889 | } |
||
2890 | |||
2891 | template <class _Allocator> |
||
2892 | template <class _InputIterator> |
||
2893 | typename enable_if |
||
2894 | < |
||
2895 | __is_input_iterator<_InputIterator>::value && |
||
2896 | !__is_forward_iterator<_InputIterator>::value, |
||
2897 | void |
||
2898 | >::type |
||
2899 | vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) |
||
2900 | { |
||
2901 | clear(); |
||
2902 | for (; __first != __last; ++__first) |
||
2903 | push_back(*__first); |
||
2904 | } |
||
2905 | |||
2906 | template <class _Allocator> |
||
2907 | template <class _ForwardIterator> |
||
2908 | typename enable_if |
||
2909 | < |
||
2910 | __is_forward_iterator<_ForwardIterator>::value, |
||
2911 | void |
||
2912 | >::type |
||
2913 | vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) |
||
2914 | { |
||
2915 | clear(); |
||
2916 | difference_type __n = _VSTD::distance(__first, __last); |
||
2917 | if (__n) |
||
2918 | { |
||
2919 | if (__n > capacity()) |
||
2920 | { |
||
2921 | deallocate(); |
||
2922 | allocate(__n); |
||
2923 | } |
||
2924 | __construct_at_end(__first, __last); |
||
2925 | } |
||
2926 | } |
||
2927 | |||
2928 | template <class _Allocator> |
||
2929 | void |
||
2930 | vector<bool, _Allocator>::reserve(size_type __n) |
||
2931 | { |
||
2932 | if (__n > capacity()) |
||
2933 | { |
||
2934 | vector __v(this->__alloc()); |
||
2935 | __v.allocate(__n); |
||
2936 | __v.__construct_at_end(this->begin(), this->end()); |
||
2937 | swap(__v); |
||
2938 | __invalidate_all_iterators(); |
||
2939 | } |
||
2940 | } |
||
2941 | |||
2942 | template <class _Allocator> |
||
2943 | void |
||
2944 | vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT |
||
2945 | { |
||
2946 | if (__external_cap_to_internal(size()) > __cap()) |
||
2947 | { |
||
2948 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
2949 | try |
||
2950 | { |
||
2951 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
2952 | vector(*this, allocator_type(__alloc())).swap(*this); |
||
2953 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
2954 | } |
||
2955 | catch (...) |
||
2956 | { |
||
2957 | } |
||
2958 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
2959 | } |
||
2960 | } |
||
2961 | |||
2962 | template <class _Allocator> |
||
2963 | typename vector<bool, _Allocator>::reference |
||
2964 | vector<bool, _Allocator>::at(size_type __n) |
||
2965 | { |
||
2966 | if (__n >= size()) |
||
2967 | this->__throw_out_of_range(); |
||
2968 | return (*this)[__n]; |
||
2969 | } |
||
2970 | |||
2971 | template <class _Allocator> |
||
2972 | typename vector<bool, _Allocator>::const_reference |
||
2973 | vector<bool, _Allocator>::at(size_type __n) const |
||
2974 | { |
||
2975 | if (__n >= size()) |
||
2976 | this->__throw_out_of_range(); |
||
2977 | return (*this)[__n]; |
||
2978 | } |
||
2979 | |||
2980 | template <class _Allocator> |
||
2981 | void |
||
2982 | vector<bool, _Allocator>::push_back(const value_type& __x) |
||
2983 | { |
||
2984 | if (this->__size_ == this->capacity()) |
||
2985 | reserve(__recommend(this->__size_ + 1)); |
||
2986 | ++this->__size_; |
||
2987 | back() = __x; |
||
2988 | } |
||
2989 | |||
2990 | template <class _Allocator> |
||
2991 | typename vector<bool, _Allocator>::iterator |
||
2992 | vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) |
||
2993 | { |
||
2994 | iterator __r; |
||
2995 | if (size() < capacity()) |
||
2996 | { |
||
2997 | const_iterator __old_end = end(); |
||
2998 | ++__size_; |
||
2999 | _VSTD::copy_backward(__position, __old_end, end()); |
||
3000 | __r = __const_iterator_cast(__position); |
||
3001 | } |
||
3002 | else |
||
3003 | { |
||
3004 | vector __v(__alloc()); |
||
3005 | __v.reserve(__recommend(__size_ + 1)); |
||
3006 | __v.__size_ = __size_ + 1; |
||
3007 | __r = _VSTD::copy(cbegin(), __position, __v.begin()); |
||
3008 | _VSTD::copy_backward(__position, cend(), __v.end()); |
||
3009 | swap(__v); |
||
3010 | } |
||
3011 | *__r = __x; |
||
3012 | return __r; |
||
3013 | } |
||
3014 | |||
3015 | template <class _Allocator> |
||
3016 | typename vector<bool, _Allocator>::iterator |
||
3017 | vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) |
||
3018 | { |
||
3019 | iterator __r; |
||
3020 | size_type __c = capacity(); |
||
3021 | if (__n <= __c && size() <= __c - __n) |
||
3022 | { |
||
3023 | const_iterator __old_end = end(); |
||
3024 | __size_ += __n; |
||
3025 | _VSTD::copy_backward(__position, __old_end, end()); |
||
3026 | __r = __const_iterator_cast(__position); |
||
3027 | } |
||
3028 | else |
||
3029 | { |
||
3030 | vector __v(__alloc()); |
||
3031 | __v.reserve(__recommend(__size_ + __n)); |
||
3032 | __v.__size_ = __size_ + __n; |
||
3033 | __r = _VSTD::copy(cbegin(), __position, __v.begin()); |
||
3034 | _VSTD::copy_backward(__position, cend(), __v.end()); |
||
3035 | swap(__v); |
||
3036 | } |
||
3037 | _VSTD::fill_n(__r, __n, __x); |
||
3038 | return __r; |
||
3039 | } |
||
3040 | |||
3041 | template <class _Allocator> |
||
3042 | template <class _InputIterator> |
||
3043 | typename enable_if |
||
3044 | < |
||
3045 | __is_input_iterator <_InputIterator>::value && |
||
3046 | !__is_forward_iterator<_InputIterator>::value, |
||
3047 | typename vector<bool, _Allocator>::iterator |
||
3048 | >::type |
||
3049 | vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) |
||
3050 | { |
||
3051 | difference_type __off = __position - begin(); |
||
3052 | iterator __p = __const_iterator_cast(__position); |
||
3053 | iterator __old_end = end(); |
||
3054 | for (; size() != capacity() && __first != __last; ++__first) |
||
3055 | { |
||
3056 | ++this->__size_; |
||
3057 | back() = *__first; |
||
3058 | } |
||
3059 | vector __v(__alloc()); |
||
3060 | if (__first != __last) |
||
3061 | { |
||
3062 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
3063 | try |
||
3064 | { |
||
3065 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
3066 | __v.assign(__first, __last); |
||
3067 | difference_type __old_size = static_cast<difference_type>(__old_end - begin()); |
||
3068 | difference_type __old_p = __p - begin(); |
||
3069 | reserve(__recommend(size() + __v.size())); |
||
3070 | __p = begin() + __old_p; |
||
3071 | __old_end = begin() + __old_size; |
||
3072 | #ifndef _LIBCPP_NO_EXCEPTIONS |
||
3073 | } |
||
3074 | catch (...) |
||
3075 | { |
||
3076 | erase(__old_end, end()); |
||
3077 | throw; |
||
3078 | } |
||
3079 | #endif // _LIBCPP_NO_EXCEPTIONS |
||
3080 | } |
||
3081 | __p = _VSTD::rotate(__p, __old_end, end()); |
||
3082 | insert(__p, __v.begin(), __v.end()); |
||
3083 | return begin() + __off; |
||
3084 | } |
||
3085 | |||
3086 | template <class _Allocator> |
||
3087 | template <class _ForwardIterator> |
||
3088 | typename enable_if |
||
3089 | < |
||
3090 | __is_forward_iterator<_ForwardIterator>::value, |
||
3091 | typename vector<bool, _Allocator>::iterator |
||
3092 | >::type |
||
3093 | vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) |
||
3094 | { |
||
3095 | difference_type __n = _VSTD::distance(__first, __last); |
||
3096 | iterator __r; |
||
3097 | size_type __c = capacity(); |
||
3098 | if (__n <= __c && size() <= __c - __n) |
||
3099 | { |
||
3100 | const_iterator __old_end = end(); |
||
3101 | __size_ += __n; |
||
3102 | _VSTD::copy_backward(__position, __old_end, end()); |
||
3103 | __r = __const_iterator_cast(__position); |
||
3104 | } |
||
3105 | else |
||
3106 | { |
||
3107 | vector __v(__alloc()); |
||
3108 | __v.reserve(__recommend(__size_ + __n)); |
||
3109 | __v.__size_ = __size_ + __n; |
||
3110 | __r = _VSTD::copy(cbegin(), __position, __v.begin()); |
||
3111 | _VSTD::copy_backward(__position, cend(), __v.end()); |
||
3112 | swap(__v); |
||
3113 | } |
||
3114 | _VSTD::copy(__first, __last, __r); |
||
3115 | return __r; |
||
3116 | } |
||
3117 | |||
3118 | template <class _Allocator> |
||
3119 | inline _LIBCPP_INLINE_VISIBILITY |
||
3120 | typename vector<bool, _Allocator>::iterator |
||
3121 | vector<bool, _Allocator>::erase(const_iterator __position) |
||
3122 | { |
||
3123 | iterator __r = __const_iterator_cast(__position); |
||
3124 | _VSTD::copy(__position + 1, this->cend(), __r); |
||
3125 | --__size_; |
||
3126 | return __r; |
||
3127 | } |
||
3128 | |||
3129 | template <class _Allocator> |
||
3130 | typename vector<bool, _Allocator>::iterator |
||
3131 | vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) |
||
3132 | { |
||
3133 | iterator __r = __const_iterator_cast(__first); |
||
3134 | difference_type __d = __last - __first; |
||
3135 | _VSTD::copy(__last, this->cend(), __r); |
||
3136 | __size_ -= __d; |
||
3137 | return __r; |
||
3138 | } |
||
3139 | |||
3140 | template <class _Allocator> |
||
3141 | void |
||
3142 | vector<bool, _Allocator>::swap(vector& __x) |
||
3143 | #if _LIBCPP_STD_VER >= 14 |
||
3144 | _NOEXCEPT |
||
3145 | #else |
||
3146 | _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || |
||
3147 | __is_nothrow_swappable<allocator_type>::value) |
||
3148 | #endif |
||
3149 | { |
||
3150 | _VSTD::swap(this->__begin_, __x.__begin_); |
||
3151 | _VSTD::swap(this->__size_, __x.__size_); |
||
3152 | _VSTD::swap(this->__cap(), __x.__cap()); |
||
3153 | __swap_allocator(this->__alloc(), __x.__alloc(), |
||
3154 | integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>()); |
||
3155 | } |
||
3156 | |||
3157 | template <class _Allocator> |
||
3158 | void |
||
3159 | vector<bool, _Allocator>::resize(size_type __sz, value_type __x) |
||
3160 | { |
||
3161 | size_type __cs = size(); |
||
3162 | if (__cs < __sz) |
||
3163 | { |
||
3164 | iterator __r; |
||
3165 | size_type __c = capacity(); |
||
3166 | size_type __n = __sz - __cs; |
||
3167 | if (__n <= __c && __cs <= __c - __n) |
||
3168 | { |
||
3169 | __r = end(); |
||
3170 | __size_ += __n; |
||
3171 | } |
||
3172 | else |
||
3173 | { |
||
3174 | vector __v(__alloc()); |
||
3175 | __v.reserve(__recommend(__size_ + __n)); |
||
3176 | __v.__size_ = __size_ + __n; |
||
3177 | __r = _VSTD::copy(cbegin(), cend(), __v.begin()); |
||
3178 | swap(__v); |
||
3179 | } |
||
3180 | _VSTD::fill_n(__r, __n, __x); |
||
3181 | } |
||
3182 | else |
||
3183 | __size_ = __sz; |
||
3184 | } |
||
3185 | |||
3186 | template <class _Allocator> |
||
3187 | void |
||
3188 | vector<bool, _Allocator>::flip() _NOEXCEPT |
||
3189 | { |
||
3190 | // do middle whole words |
||
3191 | size_type __n = __size_; |
||
3192 | __storage_pointer __p = __begin_; |
||
3193 | for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) |
||
3194 | *__p = ~*__p; |
||
3195 | // do last partial word |
||
3196 | if (__n > 0) |
||
3197 | { |
||
3198 | __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
3199 | __storage_type __b = *__p & __m; |
||
3200 | *__p &= ~__m; |
||
3201 | *__p |= ~__b & __m; |
||
3202 | } |
||
3203 | } |
||
3204 | |||
3205 | template <class _Allocator> |
||
3206 | bool |
||
3207 | vector<bool, _Allocator>::__invariants() const |
||
3208 | { |
||
3209 | if (this->__begin_ == nullptr) |
||
3210 | { |
||
3211 | if (this->__size_ != 0 || this->__cap() != 0) |
||
3212 | return false; |
||
3213 | } |
||
3214 | else |
||
3215 | { |
||
3216 | if (this->__cap() == 0) |
||
3217 | return false; |
||
3218 | if (this->__size_ > this->capacity()) |
||
3219 | return false; |
||
3220 | } |
||
3221 | return true; |
||
3222 | } |
||
3223 | |||
3224 | template <class _Allocator> |
||
3225 | size_t |
||
3226 | vector<bool, _Allocator>::__hash_code() const _NOEXCEPT |
||
3227 | { |
||
3228 | size_t __h = 0; |
||
3229 | // do middle whole words |
||
3230 | size_type __n = __size_; |
||
3231 | __storage_pointer __p = __begin_; |
||
3232 | for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) |
||
3233 | __h ^= *__p; |
||
3234 | // do last partial word |
||
3235 | if (__n > 0) |
||
3236 | { |
||
3237 | const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); |
||
3238 | __h ^= *__p & __m; |
||
3239 | } |
||
3240 | return __h; |
||
3241 | } |
||
3242 | |||
3243 | template <class _Allocator> |
||
3244 | struct _LIBCPP_TYPE_VIS_ONLY hash<vector<bool, _Allocator> > |
||
3245 | : public unary_function<vector<bool, _Allocator>, size_t> |
||
3246 | { |
||
3247 | _LIBCPP_INLINE_VISIBILITY |
||
3248 | size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT |
||
3249 | {return __vec.__hash_code();} |
||
3250 | }; |
||
3251 | |||
3252 | template <class _Tp, class _Allocator> |
||
3253 | inline _LIBCPP_INLINE_VISIBILITY |
||
3254 | bool |
||
3255 | operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) |
||
3256 | { |
||
3257 | const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); |
||
3258 | return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); |
||
3259 | } |
||
3260 | |||
3261 | template <class _Tp, class _Allocator> |
||
3262 | inline _LIBCPP_INLINE_VISIBILITY |
||
3263 | bool |
||
3264 | operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) |
||
3265 | { |
||
3266 | return !(__x == __y); |
||
3267 | } |
||
3268 | |||
3269 | template <class _Tp, class _Allocator> |
||
3270 | inline _LIBCPP_INLINE_VISIBILITY |
||
3271 | bool |
||
3272 | operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) |
||
3273 | { |
||
3274 | return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); |
||
3275 | } |
||
3276 | |||
3277 | template <class _Tp, class _Allocator> |
||
3278 | inline _LIBCPP_INLINE_VISIBILITY |
||
3279 | bool |
||
3280 | operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) |
||
3281 | { |
||
3282 | return __y < __x; |
||
3283 | } |
||
3284 | |||
3285 | template <class _Tp, class _Allocator> |
||
3286 | inline _LIBCPP_INLINE_VISIBILITY |
||
3287 | bool |
||
3288 | operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) |
||
3289 | { |
||
3290 | return !(__x < __y); |
||
3291 | } |
||
3292 | |||
3293 | template <class _Tp, class _Allocator> |
||
3294 | inline _LIBCPP_INLINE_VISIBILITY |
||
3295 | bool |
||
3296 | operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) |
||
3297 | { |
||
3298 | return !(__y < __x); |
||
3299 | } |
||
3300 | |||
3301 | template <class _Tp, class _Allocator> |
||
3302 | inline _LIBCPP_INLINE_VISIBILITY |
||
3303 | void |
||
3304 | swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) |
||
3305 | _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) |
||
3306 | { |
||
3307 | __x.swap(__y); |
||
3308 | } |
||
3309 | |||
3310 | _LIBCPP_END_NAMESPACE_STD |
||
3311 | |||
3312 | #endif // _LIBCPP_VECTOR |