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