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