contrib/libc++/include/vector

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