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