libcxx/include/vector

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