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