contrib/libc++/include/vector

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