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