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