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