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 _LIBCPP_TEMPLATE_VIS __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_address(--__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, __default_init_tag())
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_cpp17_input_iterator <_InputIterator>::value &&
522 !__is_cpp17_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_cpp17_input_iterator <_InputIterator>::value &&
530 !__is_cpp17_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_cpp17_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_cpp17_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_cpp17_input_iterator <_InputIterator>::value &&
593 !__is_cpp17_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_cpp17_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_address(this->__begin_);}
696 _LIBCPP_INLINE_VISIBILITY
697 const value_type* data() const _NOEXCEPT
698 {return _VSTD::__to_address(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_cpp17_input_iterator <_InputIterator>::value &&
741 !__is_cpp17_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_cpp17_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_cpp17_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 _NOEXCEPT {}
868#endif
869 _LIBCPP_INLINE_VISIBILITY
870 void __annotate_new(size_type __current_size) const _NOEXCEPT {
871 __annotate_contiguous_container(data(), data() + capacity(),
872 data() + capacity(), data() + __current_size);
873 }
874
875 _LIBCPP_INLINE_VISIBILITY
876 void __annotate_delete() const _NOEXCEPT {
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 _NOEXCEPT
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 _NOEXCEPT
890 {
891 __annotate_contiguous_container(data(), data() + capacity(),
892 data() + __old_size, data() + size());
893 }
894
895 struct _ConstructTransaction {
896 explicit _ConstructTransaction(vector &__v, size_type __n)
897 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
898#ifndef _LIBCPP_HAS_NO_ASAN
899 __v_.__annotate_increase(__n);
900#endif
901 }
902 ~_ConstructTransaction() {
903 __v_.__end_ = __pos_;
904#ifndef _LIBCPP_HAS_NO_ASAN
905 if (__pos_ != __new_end_) {
906 __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
907 }
908#endif
909 }
910
911 vector &__v_;
912 pointer __pos_;
913 const_pointer const __new_end_;
914
915 private:
916 _ConstructTransaction(_ConstructTransaction const&) = delete;
917 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
918 };
919
920 template <class ..._Args>
921 _LIBCPP_INLINE_VISIBILITY
922 void __construct_one_at_end(_Args&& ...__args) {
923 _ConstructTransaction __tx(*this, 1);
924 __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_),
925 _VSTD::forward<_Args>(__args)...);
926 ++__tx.__pos_;
927 }
928};
929
930#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
931template<class _InputIterator,
932 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,
933 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
934 >
935vector(_InputIterator, _InputIterator)
936 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
937
938template<class _InputIterator,
939 class _Alloc,
940 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type
941 >
942vector(_InputIterator, _InputIterator, _Alloc)
943 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;
944#endif
945
946template <class _Tp, class _Allocator>
947void
948vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
949{
950
951 __annotate_delete();
952 __alloc_traits::__construct_backward_with_exception_guarantees(
953 this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
954 _VSTD::swap(this->__begin_, __v.__begin_);
955 _VSTD::swap(this->__end_, __v.__end_);
956 _VSTD::swap(this->__end_cap(), __v.__end_cap());
957 __v.__first_ = __v.__begin_;
958 __annotate_new(size());
959 __invalidate_all_iterators();
960}
961
962template <class _Tp, class _Allocator>
963typename vector<_Tp, _Allocator>::pointer
964vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
965{
966 __annotate_delete();
967 pointer __r = __v.__begin_;
968 __alloc_traits::__construct_backward_with_exception_guarantees(
969 this->__alloc(), this->__begin_, __p, __v.__begin_);
970 __alloc_traits::__construct_forward_with_exception_guarantees(
971 this->__alloc(), __p, this->__end_, __v.__end_);
972 _VSTD::swap(this->__begin_, __v.__begin_);
973 _VSTD::swap(this->__end_, __v.__end_);
974 _VSTD::swap(this->__end_cap(), __v.__end_cap());
975 __v.__first_ = __v.__begin_;
976 __annotate_new(size());
977 __invalidate_all_iterators();
978 return __r;
979}
980
981// Allocate space for __n objects
982// throws length_error if __n > max_size()
983// throws (probably bad_alloc) if memory run out
984// Precondition: __begin_ == __end_ == __end_cap() == 0
985// Precondition: __n > 0
986// Postcondition: capacity() == __n
987// Postcondition: size() == 0
988template <class _Tp, class _Allocator>
989void
990vector<_Tp, _Allocator>::__vallocate(size_type __n)
991{
992 if (__n > max_size())
993 this->__throw_length_error();
994 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);
995 this->__end_cap() = this->__begin_ + __n;
996 __annotate_new(0);
997}
998
999template <class _Tp, class _Allocator>
1000void
1001vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT
1002{
1003 if (this->__begin_ != nullptr)
1004 {
1005 clear();
1006 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
1007 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
1008 }
1009}
1010
1011template <class _Tp, class _Allocator>
1012typename vector<_Tp, _Allocator>::size_type
1013vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
1014{
1015 return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),
1016 numeric_limits<difference_type>::max());
1017}
1018
1019// Precondition: __new_size > capacity()
1020template <class _Tp, class _Allocator>
1021inline _LIBCPP_INLINE_VISIBILITY
1022typename vector<_Tp, _Allocator>::size_type
1023vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
1024{
1025 const size_type __ms = max_size();
1026 if (__new_size > __ms)
1027 this->__throw_length_error();
1028 const size_type __cap = capacity();
1029 if (__cap >= __ms / 2)
1030 return __ms;
1031 return _VSTD::max<size_type>(2*__cap, __new_size);
1032}
1033
1034// Default constructs __n objects starting at __end_
1035// throws if construction throws
1036// Precondition: __n > 0
1037// Precondition: size() + __n <= capacity()
1038// Postcondition: size() == size() + __n
1039template <class _Tp, class _Allocator>
1040void
1041vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
1042{
1043 _ConstructTransaction __tx(*this, __n);
1044 for (; __tx.__pos_ != __tx.__new_end_; ++__tx.__pos_) {
1045 __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_));
1046 }
1047}
1048
1049// Copy constructs __n objects starting at __end_ from __x
1050// throws if construction throws
1051// Precondition: __n > 0
1052// Precondition: size() + __n <= capacity()
1053// Postcondition: size() == old size() + __n
1054// Postcondition: [i] == __x for all i in [size() - __n, __n)
1055template <class _Tp, class _Allocator>
1056inline
1057void
1058vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
1059{
1060 _ConstructTransaction __tx(*this, __n);
1061 for (; __tx.__pos_ != __tx.__new_end_; ++__tx.__pos_) {
1062 __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_), __x);
1063 }
1064}
1065
1066template <class _Tp, class _Allocator>
1067template <class _ForwardIterator>
1068typename enable_if
1069<
1070 __is_cpp17_forward_iterator<_ForwardIterator>::value,
1071 void
1072>::type
1073vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
1074{
1075 _ConstructTransaction __tx(*this, __n);
1076 __alloc_traits::__construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_);
1077}
1078
1079// Default constructs __n objects starting at __end_
1080// throws if construction throws
1081// Postcondition: size() == size() + __n
1082// Exception safety: strong.
1083template <class _Tp, class _Allocator>
1084void
1085vector<_Tp, _Allocator>::__append(size_type __n)
1086{
1087 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1088 this->__construct_at_end(__n);
1089 else
1090 {
1091 allocator_type& __a = this->__alloc();
1092 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1093 __v.__construct_at_end(__n);
1094 __swap_out_circular_buffer(__v);
1095 }
1096}
1097
1098// Default constructs __n objects starting at __end_
1099// throws if construction throws
1100// Postcondition: size() == size() + __n
1101// Exception safety: strong.
1102template <class _Tp, class _Allocator>
1103void
1104vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
1105{
1106 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
1107 this->__construct_at_end(__n, __x);
1108 else
1109 {
1110 allocator_type& __a = this->__alloc();
1111 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
1112 __v.__construct_at_end(__n, __x);
1113 __swap_out_circular_buffer(__v);
1114 }
1115}
1116
1117template <class _Tp, class _Allocator>
1118vector<_Tp, _Allocator>::vector(size_type __n)
1119{
1120#if _LIBCPP_DEBUG_LEVEL >= 2
1121 __get_db()->__insert_c(this);
1122#endif
1123 if (__n > 0)
1124 {
1125 __vallocate(__n);
1126 __construct_at_end(__n);
1127 }
1128}
1129
1130#if _LIBCPP_STD_VER > 11
1131template <class _Tp, class _Allocator>
1132vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
1133 : __base(__a)
1134{
1135#if _LIBCPP_DEBUG_LEVEL >= 2
1136 __get_db()->__insert_c(this);
1137#endif
1138 if (__n > 0)
1139 {
1140 __vallocate(__n);
1141 __construct_at_end(__n);
1142 }
1143}
1144#endif
1145
1146template <class _Tp, class _Allocator>
1147vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)
1148{
1149#if _LIBCPP_DEBUG_LEVEL >= 2
1150 __get_db()->__insert_c(this);
1151#endif
1152 if (__n > 0)
1153 {
1154 __vallocate(__n);
1155 __construct_at_end(__n, __x);
1156 }
1157}
1158
1159template <class _Tp, class _Allocator>
1160vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
1161 : __base(__a)
1162{
1163#if _LIBCPP_DEBUG_LEVEL >= 2
1164 __get_db()->__insert_c(this);
1165#endif
1166 if (__n > 0)
1167 {
1168 __vallocate(__n);
1169 __construct_at_end(__n, __x);
1170 }
1171}
1172
1173template <class _Tp, class _Allocator>
1174template <class _InputIterator>
1175vector<_Tp, _Allocator>::vector(_InputIterator __first,
1176 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
1177 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1178 is_constructible<
1179 value_type,
1180 typename iterator_traits<_InputIterator>::reference>::value,
1181 _InputIterator>::type __last)
1182{
1183#if _LIBCPP_DEBUG_LEVEL >= 2
1184 __get_db()->__insert_c(this);
1185#endif
1186 for (; __first != __last; ++__first)
1187 __emplace_back(*__first);
1188}
1189
1190template <class _Tp, class _Allocator>
1191template <class _InputIterator>
1192vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
1193 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
1194 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1195 is_constructible<
1196 value_type,
1197 typename iterator_traits<_InputIterator>::reference>::value>::type*)
1198 : __base(__a)
1199{
1200#if _LIBCPP_DEBUG_LEVEL >= 2
1201 __get_db()->__insert_c(this);
1202#endif
1203 for (; __first != __last; ++__first)
1204 __emplace_back(*__first);
1205}
1206
1207template <class _Tp, class _Allocator>
1208template <class _ForwardIterator>
1209vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
1210 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
1211 is_constructible<
1212 value_type,
1213 typename iterator_traits<_ForwardIterator>::reference>::value,
1214 _ForwardIterator>::type __last)
1215{
1216#if _LIBCPP_DEBUG_LEVEL >= 2
1217 __get_db()->__insert_c(this);
1218#endif
1219 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1220 if (__n > 0)
1221 {
1222 __vallocate(__n);
1223 __construct_at_end(__first, __last, __n);
1224 }
1225}
1226
1227template <class _Tp, class _Allocator>
1228template <class _ForwardIterator>
1229vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
1230 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
1231 is_constructible<
1232 value_type,
1233 typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
1234 : __base(__a)
1235{
1236#if _LIBCPP_DEBUG_LEVEL >= 2
1237 __get_db()->__insert_c(this);
1238#endif
1239 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
1240 if (__n > 0)
1241 {
1242 __vallocate(__n);
1243 __construct_at_end(__first, __last, __n);
1244 }
1245}
1246
1247template <class _Tp, class _Allocator>
1248vector<_Tp, _Allocator>::vector(const vector& __x)
1249 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc()))
1250{
1251#if _LIBCPP_DEBUG_LEVEL >= 2
1252 __get_db()->__insert_c(this);
1253#endif
1254 size_type __n = __x.size();
1255 if (__n > 0)
1256 {
1257 __vallocate(__n);
1258 __construct_at_end(__x.__begin_, __x.__end_, __n);
1259 }
1260}
1261
1262template <class _Tp, class _Allocator>
1263vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a)
1264 : __base(__a)
1265{
1266#if _LIBCPP_DEBUG_LEVEL >= 2
1267 __get_db()->__insert_c(this);
1268#endif
1269 size_type __n = __x.size();
1270 if (__n > 0)
1271 {
1272 __vallocate(__n);
1273 __construct_at_end(__x.__begin_, __x.__end_, __n);
1274 }
1275}
1276
1277#ifndef _LIBCPP_CXX03_LANG
1278
1279template <class _Tp, class _Allocator>
1280inline _LIBCPP_INLINE_VISIBILITY
1281vector<_Tp, _Allocator>::vector(vector&& __x)
1282#if _LIBCPP_STD_VER > 14
1283 _NOEXCEPT
1284#else
1285 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
1286#endif
1287 : __base(_VSTD::move(__x.__alloc()))
1288{
1289#if _LIBCPP_DEBUG_LEVEL >= 2
1290 __get_db()->__insert_c(this);
1291 __get_db()->swap(this, &__x);
1292#endif
1293 this->__begin_ = __x.__begin_;
1294 this->__end_ = __x.__end_;
1295 this->__end_cap() = __x.__end_cap();
1296 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1297}
1298
1299template <class _Tp, class _Allocator>
1300inline _LIBCPP_INLINE_VISIBILITY
1301vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a)
1302 : __base(__a)
1303{
1304#if _LIBCPP_DEBUG_LEVEL >= 2
1305 __get_db()->__insert_c(this);
1306#endif
1307 if (__a == __x.__alloc())
1308 {
1309 this->__begin_ = __x.__begin_;
1310 this->__end_ = __x.__end_;
1311 this->__end_cap() = __x.__end_cap();
1312 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
1313#if _LIBCPP_DEBUG_LEVEL >= 2
1314 __get_db()->swap(this, &__x);
1315#endif
1316 }
1317 else
1318 {
1319 typedef move_iterator<iterator> _Ip;
1320 assign(_Ip(__x.begin()), _Ip(__x.end()));
1321 }
1322}
1323
1324template <class _Tp, class _Allocator>
1325inline _LIBCPP_INLINE_VISIBILITY
1326vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
1327{
1328#if _LIBCPP_DEBUG_LEVEL >= 2
1329 __get_db()->__insert_c(this);
1330#endif
1331 if (__il.size() > 0)
1332 {
1333 __vallocate(__il.size());
1334 __construct_at_end(__il.begin(), __il.end(), __il.size());
1335 }
1336}
1337
1338template <class _Tp, class _Allocator>
1339inline _LIBCPP_INLINE_VISIBILITY
1340vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
1341 : __base(__a)
1342{
1343#if _LIBCPP_DEBUG_LEVEL >= 2
1344 __get_db()->__insert_c(this);
1345#endif
1346 if (__il.size() > 0)
1347 {
1348 __vallocate(__il.size());
1349 __construct_at_end(__il.begin(), __il.end(), __il.size());
1350 }
1351}
1352
1353template <class _Tp, class _Allocator>
1354inline _LIBCPP_INLINE_VISIBILITY
1355vector<_Tp, _Allocator>&
1356vector<_Tp, _Allocator>::operator=(vector&& __x)
1357 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
1358{
1359 __move_assign(__x, integral_constant<bool,
1360 __alloc_traits::propagate_on_container_move_assignment::value>());
1361 return *this;
1362}
1363
1364template <class _Tp, class _Allocator>
1365void
1366vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
1367 _NOEXCEPT_(__alloc_traits::is_always_equal::value)
1368{
1369 if (__base::__alloc() != __c.__alloc())
1370 {
1371 typedef move_iterator<iterator> _Ip;
1372 assign(_Ip(__c.begin()), _Ip(__c.end()));
1373 }
1374 else
1375 __move_assign(__c, true_type());
1376}
1377
1378template <class _Tp, class _Allocator>
1379void
1380vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
1381 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
1382{
1383 __vdeallocate();
1384 __base::__move_assign_alloc(__c); // this can throw
1385 this->__begin_ = __c.__begin_;
1386 this->__end_ = __c.__end_;
1387 this->__end_cap() = __c.__end_cap();
1388 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
1389#if _LIBCPP_DEBUG_LEVEL >= 2
1390 __get_db()->swap(this, &__c);
1391#endif
1392}
1393
1394#endif // !_LIBCPP_CXX03_LANG
1395
1396template <class _Tp, class _Allocator>
1397inline _LIBCPP_INLINE_VISIBILITY
1398vector<_Tp, _Allocator>&
1399vector<_Tp, _Allocator>::operator=(const vector& __x)
1400{
1401 if (this != &__x)
1402 {
1403 __base::__copy_assign_alloc(__x);
1404 assign(__x.__begin_, __x.__end_);
1405 }
1406 return *this;
1407}
1408
1409template <class _Tp, class _Allocator>
1410template <class _InputIterator>
1411typename enable_if
1412<
1413 __is_cpp17_input_iterator <_InputIterator>::value &&
1414 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1415 is_constructible<
1416 _Tp,
1417 typename iterator_traits<_InputIterator>::reference>::value,
1418 void
1419>::type
1420vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
1421{
1422 clear();
1423 for (; __first != __last; ++__first)
1424 __emplace_back(*__first);
1425}
1426
1427template <class _Tp, class _Allocator>
1428template <class _ForwardIterator>
1429typename enable_if
1430<
1431 __is_cpp17_forward_iterator<_ForwardIterator>::value &&
1432 is_constructible<
1433 _Tp,
1434 typename iterator_traits<_ForwardIterator>::reference>::value,
1435 void
1436>::type
1437vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
1438{
1439 size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
1440 if (__new_size <= capacity())
1441 {
1442 _ForwardIterator __mid = __last;
1443 bool __growing = false;
1444 if (__new_size > size())
1445 {
1446 __growing = true;
1447 __mid = __first;
1448 _VSTD::advance(__mid, size());
1449 }
1450 pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
1451 if (__growing)
1452 __construct_at_end(__mid, __last, __new_size - size());
1453 else
1454 this->__destruct_at_end(__m);
1455 }
1456 else
1457 {
1458 __vdeallocate();
1459 __vallocate(__recommend(__new_size));
1460 __construct_at_end(__first, __last, __new_size);
1461 }
1462 __invalidate_all_iterators();
1463}
1464
1465template <class _Tp, class _Allocator>
1466void
1467vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
1468{
1469 if (__n <= capacity())
1470 {
1471 size_type __s = size();
1472 _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
1473 if (__n > __s)
1474 __construct_at_end(__n - __s, __u);
1475 else
1476 this->__destruct_at_end(this->__begin_ + __n);
1477 }
1478 else
1479 {
1480 __vdeallocate();
1481 __vallocate(__recommend(static_cast<size_type>(__n)));
1482 __construct_at_end(__n, __u);
1483 }
1484 __invalidate_all_iterators();
1485}
1486
1487template <class _Tp, class _Allocator>
1488inline _LIBCPP_INLINE_VISIBILITY
1489typename vector<_Tp, _Allocator>::iterator
1490vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
1491{
1492#if _LIBCPP_DEBUG_LEVEL >= 2
1493 return iterator(this, __p);
1494#else
1495 return iterator(__p);
1496#endif
1497}
1498
1499template <class _Tp, class _Allocator>
1500inline _LIBCPP_INLINE_VISIBILITY
1501typename vector<_Tp, _Allocator>::const_iterator
1502vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
1503{
1504#if _LIBCPP_DEBUG_LEVEL >= 2
1505 return const_iterator(this, __p);
1506#else
1507 return const_iterator(__p);
1508#endif
1509}
1510
1511template <class _Tp, class _Allocator>
1512inline _LIBCPP_INLINE_VISIBILITY
1513typename vector<_Tp, _Allocator>::iterator
1514vector<_Tp, _Allocator>::begin() _NOEXCEPT
1515{
1516 return __make_iter(this->__begin_);
1517}
1518
1519template <class _Tp, class _Allocator>
1520inline _LIBCPP_INLINE_VISIBILITY
1521typename vector<_Tp, _Allocator>::const_iterator
1522vector<_Tp, _Allocator>::begin() const _NOEXCEPT
1523{
1524 return __make_iter(this->__begin_);
1525}
1526
1527template <class _Tp, class _Allocator>
1528inline _LIBCPP_INLINE_VISIBILITY
1529typename vector<_Tp, _Allocator>::iterator
1530vector<_Tp, _Allocator>::end() _NOEXCEPT
1531{
1532 return __make_iter(this->__end_);
1533}
1534
1535template <class _Tp, class _Allocator>
1536inline _LIBCPP_INLINE_VISIBILITY
1537typename vector<_Tp, _Allocator>::const_iterator
1538vector<_Tp, _Allocator>::end() const _NOEXCEPT
1539{
1540 return __make_iter(this->__end_);
1541}
1542
1543template <class _Tp, class _Allocator>
1544inline _LIBCPP_INLINE_VISIBILITY
1545typename vector<_Tp, _Allocator>::reference
1546vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT
1547{
1548 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1549 return this->__begin_[__n];
1550}
1551
1552template <class _Tp, class _Allocator>
1553inline _LIBCPP_INLINE_VISIBILITY
1554typename vector<_Tp, _Allocator>::const_reference
1555vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT
1556{
1557 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
1558 return this->__begin_[__n];
1559}
1560
1561template <class _Tp, class _Allocator>
1562typename vector<_Tp, _Allocator>::reference
1563vector<_Tp, _Allocator>::at(size_type __n)
1564{
1565 if (__n >= size())
1566 this->__throw_out_of_range();
1567 return this->__begin_[__n];
1568}
1569
1570template <class _Tp, class _Allocator>
1571typename vector<_Tp, _Allocator>::const_reference
1572vector<_Tp, _Allocator>::at(size_type __n) const
1573{
1574 if (__n >= size())
1575 this->__throw_out_of_range();
1576 return this->__begin_[__n];
1577}
1578
1579template <class _Tp, class _Allocator>
1580void
1581vector<_Tp, _Allocator>::reserve(size_type __n)
1582{
1583 if (__n > capacity())
1584 {
1585 allocator_type& __a = this->__alloc();
1586 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
1587 __swap_out_circular_buffer(__v);
1588 }
1589}
1590
1591template <class _Tp, class _Allocator>
1592void
1593vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
1594{
1595 if (capacity() > size())
1596 {
1597#ifndef _LIBCPP_NO_EXCEPTIONS
1598 try
1599 {
1600#endif // _LIBCPP_NO_EXCEPTIONS
1601 allocator_type& __a = this->__alloc();
1602 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
1603 __swap_out_circular_buffer(__v);
1604#ifndef _LIBCPP_NO_EXCEPTIONS
1605 }
1606 catch (...)
1607 {
1608 }
1609#endif // _LIBCPP_NO_EXCEPTIONS
1610 }
1611}
1612
1613template <class _Tp, class _Allocator>
1614template <class _Up>
1615void
1616#ifndef _LIBCPP_CXX03_LANG
1617vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
1618#else
1619vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x)
1620#endif
1621{
1622 allocator_type& __a = this->__alloc();
1623 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1624 // __v.push_back(_VSTD::forward<_Up>(__x));
1625 __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x));
1626 __v.__end_++;
1627 __swap_out_circular_buffer(__v);
1628}
1629
1630template <class _Tp, class _Allocator>
1631inline _LIBCPP_INLINE_VISIBILITY
1632void
1633vector<_Tp, _Allocator>::push_back(const_reference __x)
1634{
1635 if (this->__end_ != this->__end_cap())
1636 {
1637 __construct_one_at_end(__x);
1638 }
1639 else
1640 __push_back_slow_path(__x);
1641}
1642
1643#ifndef _LIBCPP_CXX03_LANG
1644
1645template <class _Tp, class _Allocator>
1646inline _LIBCPP_INLINE_VISIBILITY
1647void
1648vector<_Tp, _Allocator>::push_back(value_type&& __x)
1649{
1650 if (this->__end_ < this->__end_cap())
1651 {
1652 __construct_one_at_end(_VSTD::move(__x));
1653 }
1654 else
1655 __push_back_slow_path(_VSTD::move(__x));
1656}
1657
1658template <class _Tp, class _Allocator>
1659template <class... _Args>
1660void
1661vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1662{
1663 allocator_type& __a = this->__alloc();
1664 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1665// __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1666 __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...);
1667 __v.__end_++;
1668 __swap_out_circular_buffer(__v);
1669}
1670
1671template <class _Tp, class _Allocator>
1672template <class... _Args>
1673inline
1674#if _LIBCPP_STD_VER > 14
1675typename vector<_Tp, _Allocator>::reference
1676#else
1677void
1678#endif
1679vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1680{
1681 if (this->__end_ < this->__end_cap())
1682 {
1683 __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
1684 }
1685 else
1686 __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
1687#if _LIBCPP_STD_VER > 14
1688 return this->back();
1689#endif
1690}
1691
1692#endif // !_LIBCPP_CXX03_LANG
1693
1694template <class _Tp, class _Allocator>
1695inline
1696void
1697vector<_Tp, _Allocator>::pop_back()
1698{
1699 _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1700 this->__destruct_at_end(this->__end_ - 1);
1701}
1702
1703template <class _Tp, class _Allocator>
1704inline _LIBCPP_INLINE_VISIBILITY
1705typename vector<_Tp, _Allocator>::iterator
1706vector<_Tp, _Allocator>::erase(const_iterator __position)
1707{
1708#if _LIBCPP_DEBUG_LEVEL >= 2
1709 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1710 "vector::erase(iterator) called with an iterator not"
1711 " referring to this vector");
1712#endif
1713 _LIBCPP_ASSERT(__position != end(),
1714 "vector::erase(iterator) called with a non-dereferenceable iterator");
1715 difference_type __ps = __position - cbegin();
1716 pointer __p = this->__begin_ + __ps;
1717 this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1718 this->__invalidate_iterators_past(__p-1);
1719 iterator __r = __make_iter(__p);
1720 return __r;
1721}
1722
1723template <class _Tp, class _Allocator>
1724typename vector<_Tp, _Allocator>::iterator
1725vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1726{
1727#if _LIBCPP_DEBUG_LEVEL >= 2
1728 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1729 "vector::erase(iterator, iterator) called with an iterator not"
1730 " referring to this vector");
1731 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__last) == this,
1732 "vector::erase(iterator, iterator) called with an iterator not"
1733 " referring to this vector");
1734#endif
1735 _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1736 pointer __p = this->__begin_ + (__first - begin());
1737 if (__first != __last) {
1738 this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1739 this->__invalidate_iterators_past(__p - 1);
1740 }
1741 iterator __r = __make_iter(__p);
1742 return __r;
1743}
1744
1745template <class _Tp, class _Allocator>
1746void
1747vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1748{
1749 pointer __old_last = this->__end_;
1750 difference_type __n = __old_last - __to;
1751 {
1752 pointer __i = __from_s + __n;
1753 _ConstructTransaction __tx(*this, __from_e - __i);
1754 for (; __i < __from_e; ++__i, ++__tx.__pos_) {
1755 __alloc_traits::construct(this->__alloc(),
1756 _VSTD::__to_address(__tx.__pos_),
1757 _VSTD::move(*__i));
1758 }
1759 }
1760 _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1761}
1762
1763template <class _Tp, class _Allocator>
1764typename vector<_Tp, _Allocator>::iterator
1765vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1766{
1767#if _LIBCPP_DEBUG_LEVEL >= 2
1768 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1769 "vector::insert(iterator, x) called with an iterator not"
1770 " referring to this vector");
1771#endif
1772 pointer __p = this->__begin_ + (__position - begin());
1773 if (this->__end_ < this->__end_cap())
1774 {
1775 if (__p == this->__end_)
1776 {
1777 __construct_one_at_end(__x);
1778 }
1779 else
1780 {
1781 __move_range(__p, this->__end_, __p + 1);
1782 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1783 if (__p <= __xr && __xr < this->__end_)
1784 ++__xr;
1785 *__p = *__xr;
1786 }
1787 }
1788 else
1789 {
1790 allocator_type& __a = this->__alloc();
1791 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1792 __v.push_back(__x);
1793 __p = __swap_out_circular_buffer(__v, __p);
1794 }
1795 return __make_iter(__p);
1796}
1797
1798#ifndef _LIBCPP_CXX03_LANG
1799
1800template <class _Tp, class _Allocator>
1801typename vector<_Tp, _Allocator>::iterator
1802vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1803{
1804#if _LIBCPP_DEBUG_LEVEL >= 2
1805 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1806 "vector::insert(iterator, x) called with an iterator not"
1807 " referring to this vector");
1808#endif
1809 pointer __p = this->__begin_ + (__position - begin());
1810 if (this->__end_ < this->__end_cap())
1811 {
1812 if (__p == this->__end_)
1813 {
1814 __construct_one_at_end(_VSTD::move(__x));
1815 }
1816 else
1817 {
1818 __move_range(__p, this->__end_, __p + 1);
1819 *__p = _VSTD::move(__x);
1820 }
1821 }
1822 else
1823 {
1824 allocator_type& __a = this->__alloc();
1825 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1826 __v.push_back(_VSTD::move(__x));
1827 __p = __swap_out_circular_buffer(__v, __p);
1828 }
1829 return __make_iter(__p);
1830}
1831
1832template <class _Tp, class _Allocator>
1833template <class... _Args>
1834typename vector<_Tp, _Allocator>::iterator
1835vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1836{
1837#if _LIBCPP_DEBUG_LEVEL >= 2
1838 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1839 "vector::emplace(iterator, x) called with an iterator not"
1840 " referring to this vector");
1841#endif
1842 pointer __p = this->__begin_ + (__position - begin());
1843 if (this->__end_ < this->__end_cap())
1844 {
1845 if (__p == this->__end_)
1846 {
1847 __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
1848 }
1849 else
1850 {
1851 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
1852 __move_range(__p, this->__end_, __p + 1);
1853 *__p = _VSTD::move(__tmp.get());
1854 }
1855 }
1856 else
1857 {
1858 allocator_type& __a = this->__alloc();
1859 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1860 __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1861 __p = __swap_out_circular_buffer(__v, __p);
1862 }
1863 return __make_iter(__p);
1864}
1865
1866#endif // !_LIBCPP_CXX03_LANG
1867
1868template <class _Tp, class _Allocator>
1869typename vector<_Tp, _Allocator>::iterator
1870vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1871{
1872#if _LIBCPP_DEBUG_LEVEL >= 2
1873 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1874 "vector::insert(iterator, n, x) called with an iterator not"
1875 " referring to this vector");
1876#endif
1877 pointer __p = this->__begin_ + (__position - begin());
1878 if (__n > 0)
1879 {
1880 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1881 {
1882 size_type __old_n = __n;
1883 pointer __old_last = this->__end_;
1884 if (__n > static_cast<size_type>(this->__end_ - __p))
1885 {
1886 size_type __cx = __n - (this->__end_ - __p);
1887 __construct_at_end(__cx, __x);
1888 __n -= __cx;
1889 }
1890 if (__n > 0)
1891 {
1892 __move_range(__p, __old_last, __p + __old_n);
1893 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1894 if (__p <= __xr && __xr < this->__end_)
1895 __xr += __old_n;
1896 _VSTD::fill_n(__p, __n, *__xr);
1897 }
1898 }
1899 else
1900 {
1901 allocator_type& __a = this->__alloc();
1902 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1903 __v.__construct_at_end(__n, __x);
1904 __p = __swap_out_circular_buffer(__v, __p);
1905 }
1906 }
1907 return __make_iter(__p);
1908}
1909
1910template <class _Tp, class _Allocator>
1911template <class _InputIterator>
1912typename enable_if
1913<
1914 __is_cpp17_input_iterator <_InputIterator>::value &&
1915 !__is_cpp17_forward_iterator<_InputIterator>::value &&
1916 is_constructible<
1917 _Tp,
1918 typename iterator_traits<_InputIterator>::reference>::value,
1919 typename vector<_Tp, _Allocator>::iterator
1920>::type
1921vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1922{
1923#if _LIBCPP_DEBUG_LEVEL >= 2
1924 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1925 "vector::insert(iterator, range) called with an iterator not"
1926 " referring to this vector");
1927#endif
1928 difference_type __off = __position - begin();
1929 pointer __p = this->__begin_ + __off;
1930 allocator_type& __a = this->__alloc();
1931 pointer __old_last = this->__end_;
1932 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1933 {
1934 __construct_one_at_end(*__first);
1935 }
1936 __split_buffer<value_type, allocator_type&> __v(__a);
1937 if (__first != __last)
1938 {
1939#ifndef _LIBCPP_NO_EXCEPTIONS
1940 try
1941 {
1942#endif // _LIBCPP_NO_EXCEPTIONS
1943 __v.__construct_at_end(__first, __last);
1944 difference_type __old_size = __old_last - this->__begin_;
1945 difference_type __old_p = __p - this->__begin_;
1946 reserve(__recommend(size() + __v.size()));
1947 __p = this->__begin_ + __old_p;
1948 __old_last = this->__begin_ + __old_size;
1949#ifndef _LIBCPP_NO_EXCEPTIONS
1950 }
1951 catch (...)
1952 {
1953 erase(__make_iter(__old_last), end());
1954 throw;
1955 }
1956#endif // _LIBCPP_NO_EXCEPTIONS
1957 }
1958 __p = _VSTD::rotate(__p, __old_last, this->__end_);
1959 insert(__make_iter(__p), make_move_iterator(__v.begin()),
1960 make_move_iterator(__v.end()));
1961 return begin() + __off;
1962}
1963
1964template <class _Tp, class _Allocator>
1965template <class _ForwardIterator>
1966typename enable_if
1967<
1968 __is_cpp17_forward_iterator<_ForwardIterator>::value &&
1969 is_constructible<
1970 _Tp,
1971 typename iterator_traits<_ForwardIterator>::reference>::value,
1972 typename vector<_Tp, _Allocator>::iterator
1973>::type
1974vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1975{
1976#if _LIBCPP_DEBUG_LEVEL >= 2
1977 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1978 "vector::insert(iterator, range) called with an iterator not"
1979 " referring to this vector");
1980#endif
1981 pointer __p = this->__begin_ + (__position - begin());
1982 difference_type __n = _VSTD::distance(__first, __last);
1983 if (__n > 0)
1984 {
1985 if (__n <= this->__end_cap() - this->__end_)
1986 {
1987 size_type __old_n = __n;
1988 pointer __old_last = this->__end_;
1989 _ForwardIterator __m = __last;
1990 difference_type __dx = this->__end_ - __p;
1991 if (__n > __dx)
1992 {
1993 __m = __first;
1994 difference_type __diff = this->__end_ - __p;
1995 _VSTD::advance(__m, __diff);
1996 __construct_at_end(__m, __last, __n - __diff);
1997 __n = __dx;
1998 }
1999 if (__n > 0)
2000 {
2001 __move_range(__p, __old_last, __p + __old_n);
2002 _VSTD::copy(__first, __m, __p);
2003 }
2004 }
2005 else
2006 {
2007 allocator_type& __a = this->__alloc();
2008 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
2009 __v.__construct_at_end(__first, __last);
2010 __p = __swap_out_circular_buffer(__v, __p);
2011 }
2012 }
2013 return __make_iter(__p);
2014}
2015
2016template <class _Tp, class _Allocator>
2017void
2018vector<_Tp, _Allocator>::resize(size_type __sz)
2019{
2020 size_type __cs = size();
2021 if (__cs < __sz)
2022 this->__append(__sz - __cs);
2023 else if (__cs > __sz)
2024 this->__destruct_at_end(this->__begin_ + __sz);
2025}
2026
2027template <class _Tp, class _Allocator>
2028void
2029vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
2030{
2031 size_type __cs = size();
2032 if (__cs < __sz)
2033 this->__append(__sz - __cs, __x);
2034 else if (__cs > __sz)
2035 this->__destruct_at_end(this->__begin_ + __sz);
2036}
2037
2038template <class _Tp, class _Allocator>
2039void
2040vector<_Tp, _Allocator>::swap(vector& __x)
2041#if _LIBCPP_STD_VER >= 14
2042 _NOEXCEPT
2043#else
2044 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2045 __is_nothrow_swappable<allocator_type>::value)
2046#endif
2047{
2048 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
2049 this->__alloc() == __x.__alloc(),
2050 "vector::swap: Either propagate_on_container_swap must be true"
2051 " or the allocators must compare equal");
2052 _VSTD::swap(this->__begin_, __x.__begin_);
2053 _VSTD::swap(this->__end_, __x.__end_);
2054 _VSTD::swap(this->__end_cap(), __x.__end_cap());
2055 __swap_allocator(this->__alloc(), __x.__alloc(),
2056 integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
2057#if _LIBCPP_DEBUG_LEVEL >= 2
2058 __get_db()->swap(this, &__x);
2059#endif // _LIBCPP_DEBUG_LEVEL >= 2
2060}
2061
2062template <class _Tp, class _Allocator>
2063bool
2064vector<_Tp, _Allocator>::__invariants() const
2065{
2066 if (this->__begin_ == nullptr)
2067 {
2068 if (this->__end_ != nullptr || this->__end_cap() != nullptr)
2069 return false;
2070 }
2071 else
2072 {
2073 if (this->__begin_ > this->__end_)
2074 return false;
2075 if (this->__begin_ == this->__end_cap())
2076 return false;
2077 if (this->__end_ > this->__end_cap())
2078 return false;
2079 }
2080 return true;
2081}
2082
2083#if _LIBCPP_DEBUG_LEVEL >= 2
2084
2085template <class _Tp, class _Allocator>
2086bool
2087vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
2088{
2089 return this->__begin_ <= __i->base() && __i->base() < this->__end_;
2090}
2091
2092template <class _Tp, class _Allocator>
2093bool
2094vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
2095{
2096 return this->__begin_ < __i->base() && __i->base() <= this->__end_;
2097}
2098
2099template <class _Tp, class _Allocator>
2100bool
2101vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2102{
2103 const_pointer __p = __i->base() + __n;
2104 return this->__begin_ <= __p && __p <= this->__end_;
2105}
2106
2107template <class _Tp, class _Allocator>
2108bool
2109vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2110{
2111 const_pointer __p = __i->base() + __n;
2112 return this->__begin_ <= __p && __p < this->__end_;
2113}
2114
2115#endif // _LIBCPP_DEBUG_LEVEL >= 2
2116
2117template <class _Tp, class _Allocator>
2118inline _LIBCPP_INLINE_VISIBILITY
2119void
2120vector<_Tp, _Allocator>::__invalidate_all_iterators()
2121{
2122#if _LIBCPP_DEBUG_LEVEL >= 2
2123 __get_db()->__invalidate_all(this);
2124#endif // _LIBCPP_DEBUG_LEVEL >= 2
2125}
2126
2127
2128template <class _Tp, class _Allocator>
2129inline _LIBCPP_INLINE_VISIBILITY
2130void
2131vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) {
2132#if _LIBCPP_DEBUG_LEVEL >= 2
2133 __c_node* __c = __get_db()->__find_c_and_lock(this);
2134 for (__i_node** __p = __c->end_; __p != __c->beg_; ) {
2135 --__p;
2136 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
2137 if (__i->base() > __new_last) {
2138 (*__p)->__c_ = nullptr;
2139 if (--__c->end_ != __p)
2140 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
2141 }
2142 }
2143 __get_db()->unlock();
2144#else
2145 ((void)__new_last);
2146#endif
2147}
2148
2149// vector<bool>
2150
2151template <class _Allocator> class vector<bool, _Allocator>;
2152
2153template <class _Allocator> struct hash<vector<bool, _Allocator> >;
2154
2155template <class _Allocator>
2156struct __has_storage_type<vector<bool, _Allocator> >
2157{
2158 static const bool value = true;
2159};
2160
2161template <class _Allocator>
2162class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
2163 : private __vector_base_common<true>
2164{
2165public:
2166 typedef vector __self;
2167 typedef bool value_type;
2168 typedef _Allocator allocator_type;
2169 typedef allocator_traits<allocator_type> __alloc_traits;
2170 typedef typename __alloc_traits::size_type size_type;
2171 typedef typename __alloc_traits::difference_type difference_type;
2172 typedef size_type __storage_type;
2173 typedef __bit_iterator<vector, false> pointer;
2174 typedef __bit_iterator<vector, true> const_pointer;
2175 typedef pointer iterator;
2176 typedef const_pointer const_iterator;
2177 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
2178 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
2179
2180private:
2181 typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
2182 typedef allocator_traits<__storage_allocator> __storage_traits;
2183 typedef typename __storage_traits::pointer __storage_pointer;
2184 typedef typename __storage_traits::const_pointer __const_storage_pointer;
2185
2186 __storage_pointer __begin_;
2187 size_type __size_;
2188 __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2189public:
2190 typedef __bit_reference<vector> reference;
2191 typedef __bit_const_reference<vector> const_reference;
2192private:
2193 _LIBCPP_INLINE_VISIBILITY
2194 size_type& __cap() _NOEXCEPT
2195 {return __cap_alloc_.first();}
2196 _LIBCPP_INLINE_VISIBILITY
2197 const size_type& __cap() const _NOEXCEPT
2198 {return __cap_alloc_.first();}
2199 _LIBCPP_INLINE_VISIBILITY
2200 __storage_allocator& __alloc() _NOEXCEPT
2201 {return __cap_alloc_.second();}
2202 _LIBCPP_INLINE_VISIBILITY
2203 const __storage_allocator& __alloc() const _NOEXCEPT
2204 {return __cap_alloc_.second();}
2205
2206 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2207
2208 _LIBCPP_INLINE_VISIBILITY
2209 static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2210 {return __n * __bits_per_word;}
2211 _LIBCPP_INLINE_VISIBILITY
2212 static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2213 {return (__n - 1) / __bits_per_word + 1;}
2214
2215public:
2216 _LIBCPP_INLINE_VISIBILITY
2217 vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2218
2219 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
2220#if _LIBCPP_STD_VER <= 14
2221 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
2222#else
2223 _NOEXCEPT;
2224#endif
2225 ~vector();
2226 explicit vector(size_type __n);
2227#if _LIBCPP_STD_VER > 11
2228 explicit vector(size_type __n, const allocator_type& __a);
2229#endif
2230 vector(size_type __n, const value_type& __v);
2231 vector(size_type __n, const value_type& __v, const allocator_type& __a);
2232 template <class _InputIterator>
2233 vector(_InputIterator __first, _InputIterator __last,
2234 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2235 !__is_cpp17_forward_iterator<_InputIterator>::value>::type* = 0);
2236 template <class _InputIterator>
2237 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2238 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2239 !__is_cpp17_forward_iterator<_InputIterator>::value>::type* = 0);
2240 template <class _ForwardIterator>
2241 vector(_ForwardIterator __first, _ForwardIterator __last,
2242 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
2243 template <class _ForwardIterator>
2244 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2245 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
2246
2247 vector(const vector& __v);
2248 vector(const vector& __v, const allocator_type& __a);
2249 vector& operator=(const vector& __v);
2250
2251#ifndef _LIBCPP_CXX03_LANG
2252 vector(initializer_list<value_type> __il);
2253 vector(initializer_list<value_type> __il, const allocator_type& __a);
2254
2255 _LIBCPP_INLINE_VISIBILITY
2256 vector(vector&& __v)
2257#if _LIBCPP_STD_VER > 14
2258 _NOEXCEPT;
2259#else
2260 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2261#endif
2262 vector(vector&& __v, const allocator_type& __a);
2263 _LIBCPP_INLINE_VISIBILITY
2264 vector& operator=(vector&& __v)
2265 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
2266
2267 _LIBCPP_INLINE_VISIBILITY
2268 vector& operator=(initializer_list<value_type> __il)
2269 {assign(__il.begin(), __il.end()); return *this;}
2270
2271#endif // !_LIBCPP_CXX03_LANG
2272
2273 template <class _InputIterator>
2274 typename enable_if
2275 <
2276 __is_cpp17_input_iterator<_InputIterator>::value &&
2277 !__is_cpp17_forward_iterator<_InputIterator>::value,
2278 void
2279 >::type
2280 assign(_InputIterator __first, _InputIterator __last);
2281 template <class _ForwardIterator>
2282 typename enable_if
2283 <
2284 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2285 void
2286 >::type
2287 assign(_ForwardIterator __first, _ForwardIterator __last);
2288
2289 void assign(size_type __n, const value_type& __x);
2290
2291#ifndef _LIBCPP_CXX03_LANG
2292 _LIBCPP_INLINE_VISIBILITY
2293 void assign(initializer_list<value_type> __il)
2294 {assign(__il.begin(), __il.end());}
2295#endif
2296
2297 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2298 {return allocator_type(this->__alloc());}
2299
2300 size_type max_size() const _NOEXCEPT;
2301 _LIBCPP_INLINE_VISIBILITY
2302 size_type capacity() const _NOEXCEPT
2303 {return __internal_cap_to_external(__cap());}
2304 _LIBCPP_INLINE_VISIBILITY
2305 size_type size() const _NOEXCEPT
2306 {return __size_;}
2307 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
2308 bool empty() const _NOEXCEPT
2309 {return __size_ == 0;}
2310 void reserve(size_type __n);
2311 void shrink_to_fit() _NOEXCEPT;
2312
2313 _LIBCPP_INLINE_VISIBILITY
2314 iterator begin() _NOEXCEPT
2315 {return __make_iter(0);}
2316 _LIBCPP_INLINE_VISIBILITY
2317 const_iterator begin() const _NOEXCEPT
2318 {return __make_iter(0);}
2319 _LIBCPP_INLINE_VISIBILITY
2320 iterator end() _NOEXCEPT
2321 {return __make_iter(__size_);}
2322 _LIBCPP_INLINE_VISIBILITY
2323 const_iterator end() const _NOEXCEPT
2324 {return __make_iter(__size_);}
2325
2326 _LIBCPP_INLINE_VISIBILITY
2327 reverse_iterator rbegin() _NOEXCEPT
2328 {return reverse_iterator(end());}
2329 _LIBCPP_INLINE_VISIBILITY
2330 const_reverse_iterator rbegin() const _NOEXCEPT
2331 {return const_reverse_iterator(end());}
2332 _LIBCPP_INLINE_VISIBILITY
2333 reverse_iterator rend() _NOEXCEPT
2334 {return reverse_iterator(begin());}
2335 _LIBCPP_INLINE_VISIBILITY
2336 const_reverse_iterator rend() const _NOEXCEPT
2337 {return const_reverse_iterator(begin());}
2338
2339 _LIBCPP_INLINE_VISIBILITY
2340 const_iterator cbegin() const _NOEXCEPT
2341 {return __make_iter(0);}
2342 _LIBCPP_INLINE_VISIBILITY
2343 const_iterator cend() const _NOEXCEPT
2344 {return __make_iter(__size_);}
2345 _LIBCPP_INLINE_VISIBILITY
2346 const_reverse_iterator crbegin() const _NOEXCEPT
2347 {return rbegin();}
2348 _LIBCPP_INLINE_VISIBILITY
2349 const_reverse_iterator crend() const _NOEXCEPT
2350 {return rend();}
2351
2352 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
2353 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2354 reference at(size_type __n);
2355 const_reference at(size_type __n) const;
2356
2357 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
2358 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2359 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
2360 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
2361
2362 void push_back(const value_type& __x);
2363#if _LIBCPP_STD_VER > 11
2364 template <class... _Args>
2365#if _LIBCPP_STD_VER > 14
2366 _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args)
2367#else
2368 _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
2369#endif
2370 {
2371 push_back ( value_type ( _VSTD::forward<_Args>(__args)... ));
2372#if _LIBCPP_STD_VER > 14
2373 return this->back();
2374#endif
2375 }
2376#endif
2377
2378 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2379
2380#if _LIBCPP_STD_VER > 11
2381 template <class... _Args>
2382 _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args)
2383 { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); }
2384#endif
2385
2386 iterator insert(const_iterator __position, const value_type& __x);
2387 iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2388 iterator insert(const_iterator __position, size_type __n, const_reference __x);
2389 template <class _InputIterator>
2390 typename enable_if
2391 <
2392 __is_cpp17_input_iterator <_InputIterator>::value &&
2393 !__is_cpp17_forward_iterator<_InputIterator>::value,
2394 iterator
2395 >::type
2396 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2397 template <class _ForwardIterator>
2398 typename enable_if
2399 <
2400 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2401 iterator
2402 >::type
2403 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2404
2405#ifndef _LIBCPP_CXX03_LANG
2406 _LIBCPP_INLINE_VISIBILITY
2407 iterator insert(const_iterator __position, initializer_list<value_type> __il)
2408 {return insert(__position, __il.begin(), __il.end());}
2409#endif
2410
2411 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2412 iterator erase(const_iterator __first, const_iterator __last);
2413
2414 _LIBCPP_INLINE_VISIBILITY
2415 void clear() _NOEXCEPT {__size_ = 0;}
2416
2417 void swap(vector&)
2418#if _LIBCPP_STD_VER >= 14
2419 _NOEXCEPT;
2420#else
2421 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2422 __is_nothrow_swappable<allocator_type>::value);
2423#endif
2424 static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); }
2425
2426 void resize(size_type __sz, value_type __x = false);
2427 void flip() _NOEXCEPT;
2428
2429 bool __invariants() const;
2430
2431private:
2432 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2433 void __vallocate(size_type __n);
2434 void __vdeallocate() _NOEXCEPT;
2435 _LIBCPP_INLINE_VISIBILITY
2436 static size_type __align_it(size_type __new_size) _NOEXCEPT
2437 {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}
2438 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
2439 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2440 template <class _ForwardIterator>
2441 typename enable_if
2442 <
2443 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2444 void
2445 >::type
2446 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2447 void __append(size_type __n, const_reference __x);
2448 _LIBCPP_INLINE_VISIBILITY
2449 reference __make_ref(size_type __pos) _NOEXCEPT
2450 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2451 _LIBCPP_INLINE_VISIBILITY
2452 const_reference __make_ref(size_type __pos) const _NOEXCEPT
2453 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2454 _LIBCPP_INLINE_VISIBILITY
2455 iterator __make_iter(size_type __pos) _NOEXCEPT
2456 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2457 _LIBCPP_INLINE_VISIBILITY
2458 const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2459 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2460 _LIBCPP_INLINE_VISIBILITY
2461 iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2462 {return begin() + (__p - cbegin());}
2463
2464 _LIBCPP_INLINE_VISIBILITY
2465 void __copy_assign_alloc(const vector& __v)
2466 {__copy_assign_alloc(__v, integral_constant<bool,
2467 __storage_traits::propagate_on_container_copy_assignment::value>());}
2468 _LIBCPP_INLINE_VISIBILITY
2469 void __copy_assign_alloc(const vector& __c, true_type)
2470 {
2471 if (__alloc() != __c.__alloc())
2472 __vdeallocate();
2473 __alloc() = __c.__alloc();
2474 }
2475
2476 _LIBCPP_INLINE_VISIBILITY
2477 void __copy_assign_alloc(const vector&, false_type)
2478 {}
2479
2480 void __move_assign(vector& __c, false_type);
2481 void __move_assign(vector& __c, true_type)
2482 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2483 _LIBCPP_INLINE_VISIBILITY
2484 void __move_assign_alloc(vector& __c)
2485 _NOEXCEPT_(
2486 !__storage_traits::propagate_on_container_move_assignment::value ||
2487 is_nothrow_move_assignable<allocator_type>::value)
2488 {__move_assign_alloc(__c, integral_constant<bool,
2489 __storage_traits::propagate_on_container_move_assignment::value>());}
2490 _LIBCPP_INLINE_VISIBILITY
2491 void __move_assign_alloc(vector& __c, true_type)
2492 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2493 {
2494 __alloc() = _VSTD::move(__c.__alloc());
2495 }
2496
2497 _LIBCPP_INLINE_VISIBILITY
2498 void __move_assign_alloc(vector&, false_type)
2499 _NOEXCEPT
2500 {}
2501
2502 size_t __hash_code() const _NOEXCEPT;
2503
2504 friend class __bit_reference<vector>;
2505 friend class __bit_const_reference<vector>;
2506 friend class __bit_iterator<vector, false>;
2507 friend class __bit_iterator<vector, true>;
2508 friend struct __bit_array<vector>;
2509 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
2510};
2511
2512template <class _Allocator>
2513inline _LIBCPP_INLINE_VISIBILITY
2514void
2515vector<bool, _Allocator>::__invalidate_all_iterators()
2516{
2517}
2518
2519// Allocate space for __n objects
2520// throws length_error if __n > max_size()
2521// throws (probably bad_alloc) if memory run out
2522// Precondition: __begin_ == __end_ == __cap() == 0
2523// Precondition: __n > 0
2524// Postcondition: capacity() == __n
2525// Postcondition: size() == 0
2526template <class _Allocator>
2527void
2528vector<bool, _Allocator>::__vallocate(size_type __n)
2529{
2530 if (__n > max_size())
2531 this->__throw_length_error();
2532 __n = __external_cap_to_internal(__n);
2533 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2534 this->__size_ = 0;
2535 this->__cap() = __n;
2536}
2537
2538template <class _Allocator>
2539void
2540vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
2541{
2542 if (this->__begin_ != nullptr)
2543 {
2544 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2545 __invalidate_all_iterators();
2546 this->__begin_ = nullptr;
2547 this->__size_ = this->__cap() = 0;
2548 }
2549}
2550
2551template <class _Allocator>
2552typename vector<bool, _Allocator>::size_type
2553vector<bool, _Allocator>::max_size() const _NOEXCEPT
2554{
2555 size_type __amax = __storage_traits::max_size(__alloc());
2556 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
2557 if (__nmax / __bits_per_word <= __amax)
2558 return __nmax;
2559 return __internal_cap_to_external(__amax);
2560}
2561
2562// Precondition: __new_size > capacity()
2563template <class _Allocator>
2564inline _LIBCPP_INLINE_VISIBILITY
2565typename vector<bool, _Allocator>::size_type
2566vector<bool, _Allocator>::__recommend(size_type __new_size) const
2567{
2568 const size_type __ms = max_size();
2569 if (__new_size > __ms)
2570 this->__throw_length_error();
2571 const size_type __cap = capacity();
2572 if (__cap >= __ms / 2)
2573 return __ms;
2574 return _VSTD::max(2*__cap, __align_it(__new_size));
2575}
2576
2577// Default constructs __n objects starting at __end_
2578// Precondition: __n > 0
2579// Precondition: size() + __n <= capacity()
2580// Postcondition: size() == size() + __n
2581template <class _Allocator>
2582inline _LIBCPP_INLINE_VISIBILITY
2583void
2584vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2585{
2586 size_type __old_size = this->__size_;
2587 this->__size_ += __n;
2588 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2589 {
2590 if (this->__size_ <= __bits_per_word)
2591 this->__begin_[0] = __storage_type(0);
2592 else
2593 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2594 }
2595 _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2596}
2597
2598template <class _Allocator>
2599template <class _ForwardIterator>
2600typename enable_if
2601<
2602 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2603 void
2604>::type
2605vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2606{
2607 size_type __old_size = this->__size_;
2608 this->__size_ += _VSTD::distance(__first, __last);
2609 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
2610 {
2611 if (this->__size_ <= __bits_per_word)
2612 this->__begin_[0] = __storage_type(0);
2613 else
2614 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
2615 }
2616 _VSTD::copy(__first, __last, __make_iter(__old_size));
2617}
2618
2619template <class _Allocator>
2620inline _LIBCPP_INLINE_VISIBILITY
2621vector<bool, _Allocator>::vector()
2622 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2623 : __begin_(nullptr),
2624 __size_(0),
2625 __cap_alloc_(0, __default_init_tag())
2626{
2627}
2628
2629template <class _Allocator>
2630inline _LIBCPP_INLINE_VISIBILITY
2631vector<bool, _Allocator>::vector(const allocator_type& __a)
2632#if _LIBCPP_STD_VER <= 14
2633 _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
2634#else
2635 _NOEXCEPT
2636#endif
2637 : __begin_(nullptr),
2638 __size_(0),
2639 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2640{
2641}
2642
2643template <class _Allocator>
2644vector<bool, _Allocator>::vector(size_type __n)
2645 : __begin_(nullptr),
2646 __size_(0),
2647 __cap_alloc_(0, __default_init_tag())
2648{
2649 if (__n > 0)
2650 {
2651 __vallocate(__n);
2652 __construct_at_end(__n, false);
2653 }
2654}
2655
2656#if _LIBCPP_STD_VER > 11
2657template <class _Allocator>
2658vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
2659 : __begin_(nullptr),
2660 __size_(0),
2661 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2662{
2663 if (__n > 0)
2664 {
2665 __vallocate(__n);
2666 __construct_at_end(__n, false);
2667 }
2668}
2669#endif
2670
2671template <class _Allocator>
2672vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2673 : __begin_(nullptr),
2674 __size_(0),
2675 __cap_alloc_(0, __default_init_tag())
2676{
2677 if (__n > 0)
2678 {
2679 __vallocate(__n);
2680 __construct_at_end(__n, __x);
2681 }
2682}
2683
2684template <class _Allocator>
2685vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2686 : __begin_(nullptr),
2687 __size_(0),
2688 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2689{
2690 if (__n > 0)
2691 {
2692 __vallocate(__n);
2693 __construct_at_end(__n, __x);
2694 }
2695}
2696
2697template <class _Allocator>
2698template <class _InputIterator>
2699vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2700 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2701 !__is_cpp17_forward_iterator<_InputIterator>::value>::type*)
2702 : __begin_(nullptr),
2703 __size_(0),
2704 __cap_alloc_(0, __default_init_tag())
2705{
2706#ifndef _LIBCPP_NO_EXCEPTIONS
2707 try
2708 {
2709#endif // _LIBCPP_NO_EXCEPTIONS
2710 for (; __first != __last; ++__first)
2711 push_back(*__first);
2712#ifndef _LIBCPP_NO_EXCEPTIONS
2713 }
2714 catch (...)
2715 {
2716 if (__begin_ != nullptr)
2717 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2718 __invalidate_all_iterators();
2719 throw;
2720 }
2721#endif // _LIBCPP_NO_EXCEPTIONS
2722}
2723
2724template <class _Allocator>
2725template <class _InputIterator>
2726vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2727 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&
2728 !__is_cpp17_forward_iterator<_InputIterator>::value>::type*)
2729 : __begin_(nullptr),
2730 __size_(0),
2731 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2732{
2733#ifndef _LIBCPP_NO_EXCEPTIONS
2734 try
2735 {
2736#endif // _LIBCPP_NO_EXCEPTIONS
2737 for (; __first != __last; ++__first)
2738 push_back(*__first);
2739#ifndef _LIBCPP_NO_EXCEPTIONS
2740 }
2741 catch (...)
2742 {
2743 if (__begin_ != nullptr)
2744 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2745 __invalidate_all_iterators();
2746 throw;
2747 }
2748#endif // _LIBCPP_NO_EXCEPTIONS
2749}
2750
2751template <class _Allocator>
2752template <class _ForwardIterator>
2753vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2754 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
2755 : __begin_(nullptr),
2756 __size_(0),
2757 __cap_alloc_(0, __default_init_tag())
2758{
2759 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2760 if (__n > 0)
2761 {
2762 __vallocate(__n);
2763 __construct_at_end(__first, __last);
2764 }
2765}
2766
2767template <class _Allocator>
2768template <class _ForwardIterator>
2769vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2770 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
2771 : __begin_(nullptr),
2772 __size_(0),
2773 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2774{
2775 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2776 if (__n > 0)
2777 {
2778 __vallocate(__n);
2779 __construct_at_end(__first, __last);
2780 }
2781}
2782
2783#ifndef _LIBCPP_CXX03_LANG
2784
2785template <class _Allocator>
2786vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2787 : __begin_(nullptr),
2788 __size_(0),
2789 __cap_alloc_(0, __default_init_tag())
2790{
2791 size_type __n = static_cast<size_type>(__il.size());
2792 if (__n > 0)
2793 {
2794 __vallocate(__n);
2795 __construct_at_end(__il.begin(), __il.end());
2796 }
2797}
2798
2799template <class _Allocator>
2800vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2801 : __begin_(nullptr),
2802 __size_(0),
2803 __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2804{
2805 size_type __n = static_cast<size_type>(__il.size());
2806 if (__n > 0)
2807 {
2808 __vallocate(__n);
2809 __construct_at_end(__il.begin(), __il.end());
2810 }
2811}
2812
2813#endif // _LIBCPP_CXX03_LANG
2814
2815template <class _Allocator>
2816vector<bool, _Allocator>::~vector()
2817{
2818 if (__begin_ != nullptr)
2819 __storage_traits::deallocate(__alloc(), __begin_, __cap());
2820 __invalidate_all_iterators();
2821}
2822
2823template <class _Allocator>
2824vector<bool, _Allocator>::vector(const vector& __v)
2825 : __begin_(nullptr),
2826 __size_(0),
2827 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2828{
2829 if (__v.size() > 0)
2830 {
2831 __vallocate(__v.size());
2832 __construct_at_end(__v.begin(), __v.end());
2833 }
2834}
2835
2836template <class _Allocator>
2837vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2838 : __begin_(nullptr),
2839 __size_(0),
2840 __cap_alloc_(0, __a)
2841{
2842 if (__v.size() > 0)
2843 {
2844 __vallocate(__v.size());
2845 __construct_at_end(__v.begin(), __v.end());
2846 }
2847}
2848
2849template <class _Allocator>
2850vector<bool, _Allocator>&
2851vector<bool, _Allocator>::operator=(const vector& __v)
2852{
2853 if (this != &__v)
2854 {
2855 __copy_assign_alloc(__v);
2856 if (__v.__size_)
2857 {
2858 if (__v.__size_ > capacity())
2859 {
2860 __vdeallocate();
2861 __vallocate(__v.__size_);
2862 }
2863 _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2864 }
2865 __size_ = __v.__size_;
2866 }
2867 return *this;
2868}
2869
2870#ifndef _LIBCPP_CXX03_LANG
2871
2872template <class _Allocator>
2873inline _LIBCPP_INLINE_VISIBILITY vector<bool, _Allocator>::vector(vector&& __v)
2874#if _LIBCPP_STD_VER > 14
2875 _NOEXCEPT
2876#else
2877 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2878#endif
2879 : __begin_(__v.__begin_),
2880 __size_(__v.__size_),
2881 __cap_alloc_(std::move(__v.__cap_alloc_)) {
2882 __v.__begin_ = nullptr;
2883 __v.__size_ = 0;
2884 __v.__cap() = 0;
2885}
2886
2887template <class _Allocator>
2888vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2889 : __begin_(nullptr),
2890 __size_(0),
2891 __cap_alloc_(0, __a)
2892{
2893 if (__a == allocator_type(__v.__alloc()))
2894 {
2895 this->__begin_ = __v.__begin_;
2896 this->__size_ = __v.__size_;
2897 this->__cap() = __v.__cap();
2898 __v.__begin_ = nullptr;
2899 __v.__cap() = __v.__size_ = 0;
2900 }
2901 else if (__v.size() > 0)
2902 {
2903 __vallocate(__v.size());
2904 __construct_at_end(__v.begin(), __v.end());
2905 }
2906}
2907
2908template <class _Allocator>
2909inline _LIBCPP_INLINE_VISIBILITY
2910vector<bool, _Allocator>&
2911vector<bool, _Allocator>::operator=(vector&& __v)
2912 _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
2913{
2914 __move_assign(__v, integral_constant<bool,
2915 __storage_traits::propagate_on_container_move_assignment::value>());
2916 return *this;
2917}
2918
2919template <class _Allocator>
2920void
2921vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2922{
2923 if (__alloc() != __c.__alloc())
2924 assign(__c.begin(), __c.end());
2925 else
2926 __move_assign(__c, true_type());
2927}
2928
2929template <class _Allocator>
2930void
2931vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2932 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2933{
2934 __vdeallocate();
2935 __move_assign_alloc(__c);
2936 this->__begin_ = __c.__begin_;
2937 this->__size_ = __c.__size_;
2938 this->__cap() = __c.__cap();
2939 __c.__begin_ = nullptr;
2940 __c.__cap() = __c.__size_ = 0;
2941}
2942
2943#endif // !_LIBCPP_CXX03_LANG
2944
2945template <class _Allocator>
2946void
2947vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2948{
2949 __size_ = 0;
2950 if (__n > 0)
2951 {
2952 size_type __c = capacity();
2953 if (__n <= __c)
2954 __size_ = __n;
2955 else
2956 {
2957 vector __v(__alloc());
2958 __v.reserve(__recommend(__n));
2959 __v.__size_ = __n;
2960 swap(__v);
2961 }
2962 _VSTD::fill_n(begin(), __n, __x);
2963 }
2964 __invalidate_all_iterators();
2965}
2966
2967template <class _Allocator>
2968template <class _InputIterator>
2969typename enable_if
2970<
2971 __is_cpp17_input_iterator<_InputIterator>::value &&
2972 !__is_cpp17_forward_iterator<_InputIterator>::value,
2973 void
2974>::type
2975vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2976{
2977 clear();
2978 for (; __first != __last; ++__first)
2979 push_back(*__first);
2980}
2981
2982template <class _Allocator>
2983template <class _ForwardIterator>
2984typename enable_if
2985<
2986 __is_cpp17_forward_iterator<_ForwardIterator>::value,
2987 void
2988>::type
2989vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2990{
2991 clear();
2992 difference_type __ns = _VSTD::distance(__first, __last);
2993 _LIBCPP_ASSERT(__ns >= 0, "invalid range specified");
2994 const size_t __n = static_cast<size_type>(__ns);
2995 if (__n)
2996 {
2997 if (__n > capacity())
2998 {
2999 __vdeallocate();
3000 __vallocate(__n);
3001 }
3002 __construct_at_end(__first, __last);
3003 }
3004}
3005
3006template <class _Allocator>
3007void
3008vector<bool, _Allocator>::reserve(size_type __n)
3009{
3010 if (__n > capacity())
3011 {
3012 vector __v(this->__alloc());
3013 __v.__vallocate(__n);
3014 __v.__construct_at_end(this->begin(), this->end());
3015 swap(__v);
3016 __invalidate_all_iterators();
3017 }
3018}
3019
3020template <class _Allocator>
3021void
3022vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
3023{
3024 if (__external_cap_to_internal(size()) > __cap())
3025 {
3026#ifndef _LIBCPP_NO_EXCEPTIONS
3027 try
3028 {
3029#endif // _LIBCPP_NO_EXCEPTIONS
3030 vector(*this, allocator_type(__alloc())).swap(*this);
3031#ifndef _LIBCPP_NO_EXCEPTIONS
3032 }
3033 catch (...)
3034 {
3035 }
3036#endif // _LIBCPP_NO_EXCEPTIONS
3037 }
3038}
3039
3040template <class _Allocator>
3041typename vector<bool, _Allocator>::reference
3042vector<bool, _Allocator>::at(size_type __n)
3043{
3044 if (__n >= size())
3045 this->__throw_out_of_range();
3046 return (*this)[__n];
3047}
3048
3049template <class _Allocator>
3050typename vector<bool, _Allocator>::const_reference
3051vector<bool, _Allocator>::at(size_type __n) const
3052{
3053 if (__n >= size())
3054 this->__throw_out_of_range();
3055 return (*this)[__n];
3056}
3057
3058template <class _Allocator>
3059void
3060vector<bool, _Allocator>::push_back(const value_type& __x)
3061{
3062 if (this->__size_ == this->capacity())
3063 reserve(__recommend(this->__size_ + 1));
3064 ++this->__size_;
3065 back() = __x;
3066}
3067
3068template <class _Allocator>
3069typename vector<bool, _Allocator>::iterator
3070vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
3071{
3072 iterator __r;
3073 if (size() < capacity())
3074 {
3075 const_iterator __old_end = end();
3076 ++__size_;
3077 _VSTD::copy_backward(__position, __old_end, end());
3078 __r = __const_iterator_cast(__position);
3079 }
3080 else
3081 {
3082 vector __v(__alloc());
3083 __v.reserve(__recommend(__size_ + 1));
3084 __v.__size_ = __size_ + 1;
3085 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3086 _VSTD::copy_backward(__position, cend(), __v.end());
3087 swap(__v);
3088 }
3089 *__r = __x;
3090 return __r;
3091}
3092
3093template <class _Allocator>
3094typename vector<bool, _Allocator>::iterator
3095vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
3096{
3097 iterator __r;
3098 size_type __c = capacity();
3099 if (__n <= __c && size() <= __c - __n)
3100 {
3101 const_iterator __old_end = end();
3102 __size_ += __n;
3103 _VSTD::copy_backward(__position, __old_end, end());
3104 __r = __const_iterator_cast(__position);
3105 }
3106 else
3107 {
3108 vector __v(__alloc());
3109 __v.reserve(__recommend(__size_ + __n));
3110 __v.__size_ = __size_ + __n;
3111 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3112 _VSTD::copy_backward(__position, cend(), __v.end());
3113 swap(__v);
3114 }
3115 _VSTD::fill_n(__r, __n, __x);
3116 return __r;
3117}
3118
3119template <class _Allocator>
3120template <class _InputIterator>
3121typename enable_if
3122<
3123 __is_cpp17_input_iterator <_InputIterator>::value &&
3124 !__is_cpp17_forward_iterator<_InputIterator>::value,
3125 typename vector<bool, _Allocator>::iterator
3126>::type
3127vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
3128{
3129 difference_type __off = __position - begin();
3130 iterator __p = __const_iterator_cast(__position);
3131 iterator __old_end = end();
3132 for (; size() != capacity() && __first != __last; ++__first)
3133 {
3134 ++this->__size_;
3135 back() = *__first;
3136 }
3137 vector __v(__alloc());
3138 if (__first != __last)
3139 {
3140#ifndef _LIBCPP_NO_EXCEPTIONS
3141 try
3142 {
3143#endif // _LIBCPP_NO_EXCEPTIONS
3144 __v.assign(__first, __last);
3145 difference_type __old_size = static_cast<difference_type>(__old_end - begin());
3146 difference_type __old_p = __p - begin();
3147 reserve(__recommend(size() + __v.size()));
3148 __p = begin() + __old_p;
3149 __old_end = begin() + __old_size;
3150#ifndef _LIBCPP_NO_EXCEPTIONS
3151 }
3152 catch (...)
3153 {
3154 erase(__old_end, end());
3155 throw;
3156 }
3157#endif // _LIBCPP_NO_EXCEPTIONS
3158 }
3159 __p = _VSTD::rotate(__p, __old_end, end());
3160 insert(__p, __v.begin(), __v.end());
3161 return begin() + __off;
3162}
3163
3164template <class _Allocator>
3165template <class _ForwardIterator>
3166typename enable_if
3167<
3168 __is_cpp17_forward_iterator<_ForwardIterator>::value,
3169 typename vector<bool, _Allocator>::iterator
3170>::type
3171vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
3172{
3173 const difference_type __n_signed = _VSTD::distance(__first, __last);
3174 _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified");
3175 const size_type __n = static_cast<size_type>(__n_signed);
3176 iterator __r;
3177 size_type __c = capacity();
3178 if (__n <= __c && size() <= __c - __n)
3179 {
3180 const_iterator __old_end = end();
3181 __size_ += __n;
3182 _VSTD::copy_backward(__position, __old_end, end());
3183 __r = __const_iterator_cast(__position);
3184 }
3185 else
3186 {
3187 vector __v(__alloc());
3188 __v.reserve(__recommend(__size_ + __n));
3189 __v.__size_ = __size_ + __n;
3190 __r = _VSTD::copy(cbegin(), __position, __v.begin());
3191 _VSTD::copy_backward(__position, cend(), __v.end());
3192 swap(__v);
3193 }
3194 _VSTD::copy(__first, __last, __r);
3195 return __r;
3196}
3197
3198template <class _Allocator>
3199inline _LIBCPP_INLINE_VISIBILITY
3200typename vector<bool, _Allocator>::iterator
3201vector<bool, _Allocator>::erase(const_iterator __position)
3202{
3203 iterator __r = __const_iterator_cast(__position);
3204 _VSTD::copy(__position + 1, this->cend(), __r);
3205 --__size_;
3206 return __r;
3207}
3208
3209template <class _Allocator>
3210typename vector<bool, _Allocator>::iterator
3211vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
3212{
3213 iterator __r = __const_iterator_cast(__first);
3214 difference_type __d = __last - __first;
3215 _VSTD::copy(__last, this->cend(), __r);
3216 __size_ -= __d;
3217 return __r;
3218}
3219
3220template <class _Allocator>
3221void
3222vector<bool, _Allocator>::swap(vector& __x)
3223#if _LIBCPP_STD_VER >= 14
3224 _NOEXCEPT
3225#else
3226 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3227 __is_nothrow_swappable<allocator_type>::value)
3228#endif
3229{
3230 _VSTD::swap(this->__begin_, __x.__begin_);
3231 _VSTD::swap(this->__size_, __x.__size_);
3232 _VSTD::swap(this->__cap(), __x.__cap());
3233 __swap_allocator(this->__alloc(), __x.__alloc(),
3234 integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
3235}
3236
3237template <class _Allocator>
3238void
3239vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3240{
3241 size_type __cs = size();
3242 if (__cs < __sz)
3243 {
3244 iterator __r;
3245 size_type __c = capacity();
3246 size_type __n = __sz - __cs;
3247 if (__n <= __c && __cs <= __c - __n)
3248 {
3249 __r = end();
3250 __size_ += __n;
3251 }
3252 else
3253 {
3254 vector __v(__alloc());
3255 __v.reserve(__recommend(__size_ + __n));
3256 __v.__size_ = __size_ + __n;
3257 __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3258 swap(__v);
3259 }
3260 _VSTD::fill_n(__r, __n, __x);
3261 }
3262 else
3263 __size_ = __sz;
3264}
3265
3266template <class _Allocator>
3267void
3268vector<bool, _Allocator>::flip() _NOEXCEPT
3269{
3270 // do middle whole words
3271 size_type __n = __size_;
3272 __storage_pointer __p = __begin_;
3273 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3274 *__p = ~*__p;
3275 // do last partial word
3276 if (__n > 0)
3277 {
3278 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3279 __storage_type __b = *__p & __m;
3280 *__p &= ~__m;
3281 *__p |= ~__b & __m;
3282 }
3283}
3284
3285template <class _Allocator>
3286bool
3287vector<bool, _Allocator>::__invariants() const
3288{
3289 if (this->__begin_ == nullptr)
3290 {
3291 if (this->__size_ != 0 || this->__cap() != 0)
3292 return false;
3293 }
3294 else
3295 {
3296 if (this->__cap() == 0)
3297 return false;
3298 if (this->__size_ > this->capacity())
3299 return false;
3300 }
3301 return true;
3302}
3303
3304template <class _Allocator>
3305size_t
3306vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3307{
3308 size_t __h = 0;
3309 // do middle whole words
3310 size_type __n = __size_;
3311 __storage_pointer __p = __begin_;
3312 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3313 __h ^= *__p;
3314 // do last partial word
3315 if (__n > 0)
3316 {
3317 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3318 __h ^= *__p & __m;
3319 }
3320 return __h;
3321}
3322
3323template <class _Allocator>
3324struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
3325 : public unary_function<vector<bool, _Allocator>, size_t>
3326{
3327 _LIBCPP_INLINE_VISIBILITY
3328 size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3329 {return __vec.__hash_code();}
3330};
3331
3332template <class _Tp, class _Allocator>
3333inline _LIBCPP_INLINE_VISIBILITY
3334bool
3335operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3336{
3337 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3338 return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3339}
3340
3341template <class _Tp, class _Allocator>
3342inline _LIBCPP_INLINE_VISIBILITY
3343bool
3344operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3345{
3346 return !(__x == __y);
3347}
3348
3349template <class _Tp, class _Allocator>
3350inline _LIBCPP_INLINE_VISIBILITY
3351bool
3352operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3353{
3354 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3355}
3356
3357template <class _Tp, class _Allocator>
3358inline _LIBCPP_INLINE_VISIBILITY
3359bool
3360operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3361{
3362 return __y < __x;
3363}
3364
3365template <class _Tp, class _Allocator>
3366inline _LIBCPP_INLINE_VISIBILITY
3367bool
3368operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3369{
3370 return !(__x < __y);
3371}
3372
3373template <class _Tp, class _Allocator>
3374inline _LIBCPP_INLINE_VISIBILITY
3375bool
3376operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3377{
3378 return !(__y < __x);
3379}
3380
3381template <class _Tp, class _Allocator>
3382inline _LIBCPP_INLINE_VISIBILITY
3383void
3384swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3385 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3386{
3387 __x.swap(__y);
3388}
3389
3390#if _LIBCPP_STD_VER > 17
3391template <class _Tp, class _Allocator, class _Up>
3392inline _LIBCPP_INLINE_VISIBILITY
3393void erase(vector<_Tp, _Allocator>& __c, const _Up& __v)
3394{ __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end()); }
3395
3396template <class _Tp, class _Allocator, class _Predicate>
3397inline _LIBCPP_INLINE_VISIBILITY
3398void erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred)
3399{ __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end()); }
3400#endif
3401
3402_LIBCPP_END_NAMESPACE_STD
3403
3404_LIBCPP_POP_MACROS
3405
3406#endif // _LIBCPP_VECTOR
3407