contrib/libc++/include/vector

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