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