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