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