contrib/libc++/include/vector

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