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