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