contrib/libc++/include/vector

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