contrib/libc++/include/vector

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