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