contrib/llvm-project/libcxx/include/vector

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