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             value_type __tmp(_VSTD::forward<_Args>(__args)...);
1685             __move_range(__p, this->__end_, __p + 1);
1686             *__p = _VSTD::move(__tmp);
1687         }
1688     }
1689     else
1690     {
1691         allocator_type& __a = this->__alloc();
1692         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1693         __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1694         __p = __swap_out_circular_buffer(__v, __p);
1695     }
1696     return __make_iter(__p);
1697 }
1698
1699 #endif  // _LIBCPP_HAS_NO_VARIADICS
1700 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1701
1702 template <class _Tp, class _Allocator>
1703 typename vector<_Tp, _Allocator>::iterator
1704 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1705 {
1706 #if _LIBCPP_DEBUG_LEVEL >= 2
1707     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1708         "vector::insert(iterator, n, x) called with an iterator not"
1709         " referring to this vector");
1710 #endif
1711     pointer __p = this->__begin_ + (__position - begin());
1712     if (__n > 0)
1713     {
1714         if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1715         {
1716             size_type __old_n = __n;
1717             pointer __old_last = this->__end_;
1718             if (__n > static_cast<size_type>(this->__end_ - __p))
1719             {
1720                 size_type __cx = __n - (this->__end_ - __p);
1721                 __construct_at_end(__cx, __x);
1722                 __n -= __cx;
1723             }
1724             if (__n > 0)
1725             {
1726                 __move_range(__p, __old_last, __p + __old_n);
1727                 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1728                 if (__p <= __xr && __xr < this->__end_)
1729                     __xr += __old_n;
1730                 _VSTD::fill_n(__p, __n, *__xr);
1731             }
1732         }
1733         else
1734         {
1735             allocator_type& __a = this->__alloc();
1736             __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1737             __v.__construct_at_end(__n, __x);
1738             __p = __swap_out_circular_buffer(__v, __p);
1739         }
1740     }
1741     return __make_iter(__p);
1742 }
1743
1744 template <class _Tp, class _Allocator>
1745 template <class _InputIterator>
1746 typename enable_if
1747 <
1748      __is_input_iterator  <_InputIterator>::value &&
1749     !__is_forward_iterator<_InputIterator>::value,
1750     typename vector<_Tp, _Allocator>::iterator
1751 >::type
1752 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1753 {
1754 #if _LIBCPP_DEBUG_LEVEL >= 2
1755     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1756         "vector::insert(iterator, range) called with an iterator not"
1757         " referring to this vector");
1758 #endif
1759     difference_type __off = __position - begin();
1760     pointer __p = this->__begin_ + __off;
1761     allocator_type& __a = this->__alloc();
1762     pointer __old_last = this->__end_;
1763     for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1764     {
1765         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
1766                                   *__first);
1767         ++this->__end_;
1768     }
1769     __split_buffer<value_type, allocator_type&> __v(__a);
1770     if (__first != __last)
1771     {
1772 #ifndef _LIBCPP_NO_EXCEPTIONS
1773         try
1774         {
1775 #endif  // _LIBCPP_NO_EXCEPTIONS
1776             __v.__construct_at_end(__first, __last);
1777             difference_type __old_size = __old_last - this->__begin_;
1778             difference_type __old_p = __p - this->__begin_;
1779             reserve(__recommend(size() + __v.size()));
1780             __p = this->__begin_ + __old_p;
1781             __old_last = this->__begin_ + __old_size;
1782 #ifndef _LIBCPP_NO_EXCEPTIONS
1783         }
1784         catch (...)
1785         {
1786             erase(__make_iter(__old_last), end());
1787             throw;
1788         }
1789 #endif  // _LIBCPP_NO_EXCEPTIONS
1790     }
1791     __p = _VSTD::rotate(__p, __old_last, this->__end_);
1792     insert(__make_iter(__p), make_move_iterator(__v.begin()),
1793                                     make_move_iterator(__v.end()));
1794     return begin() + __off;
1795 }
1796
1797 template <class _Tp, class _Allocator>
1798 template <class _ForwardIterator>
1799 typename enable_if
1800 <
1801     __is_forward_iterator<_ForwardIterator>::value,
1802     typename vector<_Tp, _Allocator>::iterator
1803 >::type
1804 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1805 {
1806 #if _LIBCPP_DEBUG_LEVEL >= 2
1807     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1808         "vector::insert(iterator, range) called with an iterator not"
1809         " referring to this vector");
1810 #endif
1811     pointer __p = this->__begin_ + (__position - begin());
1812     difference_type __n = _VSTD::distance(__first, __last);
1813     if (__n > 0)
1814     {
1815         if (__n <= this->__end_cap() - this->__end_)
1816         {
1817             size_type __old_n = __n;
1818             pointer __old_last = this->__end_;
1819             _ForwardIterator __m = __last;
1820             difference_type __dx = this->__end_ - __p;
1821             if (__n > __dx)
1822             {
1823                 __m = __first;
1824                 _VSTD::advance(__m, this->__end_ - __p);
1825                 __construct_at_end(__m, __last);
1826                 __n = __dx;
1827             }
1828             if (__n > 0)
1829             {
1830                 __move_range(__p, __old_last, __p + __old_n);
1831                 _VSTD::copy(__first, __m, __p);
1832             }
1833         }
1834         else
1835         {
1836             allocator_type& __a = this->__alloc();
1837             __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1838             __v.__construct_at_end(__first, __last);
1839             __p = __swap_out_circular_buffer(__v, __p);
1840         }
1841     }
1842     return __make_iter(__p);
1843 }
1844
1845 template <class _Tp, class _Allocator>
1846 void
1847 vector<_Tp, _Allocator>::resize(size_type __sz)
1848 {
1849     size_type __cs = size();
1850     if (__cs < __sz)
1851         this->__append(__sz - __cs);
1852     else if (__cs > __sz)
1853         this->__destruct_at_end(this->__begin_ + __sz);
1854 }
1855
1856 template <class _Tp, class _Allocator>
1857 void
1858 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
1859 {
1860     size_type __cs = size();
1861     if (__cs < __sz)
1862         this->__append(__sz - __cs, __x);
1863     else if (__cs > __sz)
1864         this->__destruct_at_end(this->__begin_ + __sz);
1865 }
1866
1867 template <class _Tp, class _Allocator>
1868 void
1869 vector<_Tp, _Allocator>::swap(vector& __x)
1870         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1871                    __is_nothrow_swappable<allocator_type>::value)
1872 {
1873     _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
1874                    this->__alloc() == __x.__alloc(),
1875                    "vector::swap: Either propagate_on_container_swap must be true"
1876                    " or the allocators must compare equal");
1877     _VSTD::swap(this->__begin_, __x.__begin_);
1878     _VSTD::swap(this->__end_, __x.__end_);
1879     _VSTD::swap(this->__end_cap(), __x.__end_cap());
1880     __base::__swap_alloc(this->__alloc(), __x.__alloc());
1881 #if _LIBCPP_DEBUG_LEVEL >= 2
1882     __get_db()->swap(this, &__x);
1883 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1884 }
1885
1886 template <class _Tp, class _Allocator>
1887 bool
1888 vector<_Tp, _Allocator>::__invariants() const
1889 {
1890     if (this->__begin_ == 0)
1891     {
1892         if (this->__end_ != 0 || this->__end_cap() != 0)
1893             return false;
1894     }
1895     else
1896     {
1897         if (this->__begin_ > this->__end_)
1898             return false;
1899         if (this->__begin_ == this->__end_cap())
1900             return false;
1901         if (this->__end_ > this->__end_cap())
1902             return false;
1903     }
1904     return true;
1905 }
1906
1907 #if _LIBCPP_DEBUG_LEVEL >= 2
1908
1909 template <class _Tp, class _Allocator>
1910 bool
1911 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
1912 {
1913     return this->__begin_ <= __i->base() && __i->base() < this->__end_;
1914 }
1915
1916 template <class _Tp, class _Allocator>
1917 bool
1918 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
1919 {
1920     return this->__begin_ < __i->base() && __i->base() <= this->__end_;
1921 }
1922
1923 template <class _Tp, class _Allocator>
1924 bool
1925 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
1926 {
1927     const_pointer __p = __i->base() + __n;
1928     return this->__begin_ <= __p && __p <= this->__end_;
1929 }
1930
1931 template <class _Tp, class _Allocator>
1932 bool
1933 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1934 {
1935     const_pointer __p = __i->base() + __n;
1936     return this->__begin_ <= __p && __p < this->__end_;
1937 }
1938
1939 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1940
1941 template <class _Tp, class _Allocator>
1942 _LIBCPP_INLINE_VISIBILITY inline
1943 void
1944 vector<_Tp, _Allocator>::__invalidate_all_iterators()
1945 {
1946 #if _LIBCPP_DEBUG_LEVEL >= 2
1947     __get_db()->__invalidate_all(this);
1948 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1949 }
1950
1951 // vector<bool>
1952
1953 template <class _Allocator> class vector<bool, _Allocator>;
1954
1955 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
1956
1957 template <class _Allocator>
1958 struct __has_storage_type<vector<bool, _Allocator> >
1959 {
1960     static const bool value = true;
1961 };
1962
1963 template <class _Allocator>
1964 class _LIBCPP_VISIBLE vector<bool, _Allocator>
1965     : private __vector_base_common<true>
1966 {
1967 public:
1968     typedef vector                                   __self;
1969     typedef bool                                     value_type;
1970     typedef _Allocator                               allocator_type;
1971     typedef allocator_traits<allocator_type>         __alloc_traits;
1972     typedef typename __alloc_traits::size_type       size_type;
1973     typedef typename __alloc_traits::difference_type difference_type;
1974     typedef size_type __storage_type;
1975     typedef __bit_iterator<vector, false>            pointer;
1976     typedef __bit_iterator<vector, true>             const_pointer;
1977 #ifdef _LIBCPP_DEBUG
1978     typedef __debug_iter<vector, pointer>            iterator;
1979     typedef __debug_iter<vector, const_pointer>      const_iterator;
1980
1981     friend class __debug_iter<vector, pointer>;
1982     friend class __debug_iter<vector, const_pointer>;
1983
1984     pair<iterator*, const_iterator*> __iterator_list_;
1985
1986     _LIBCPP_INLINE_VISIBILITY iterator*&       __get_iterator_list(iterator*)       {return __iterator_list_.first;}
1987     _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;}
1988 #else  // _LIBCPP_DEBUG
1989     typedef pointer                                  iterator;
1990     typedef const_pointer                            const_iterator;
1991 #endif  // _LIBCPP_DEBUG
1992     typedef _VSTD::reverse_iterator<iterator>         reverse_iterator;
1993     typedef _VSTD::reverse_iterator<const_iterator>   const_reverse_iterator;
1994
1995 private:
1996     typedef typename __alloc_traits::template
1997 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1998                 rebind_alloc<__storage_type>
1999 #else
2000                 rebind_alloc<__storage_type>::other
2001 #endif
2002                                                      __storage_allocator;
2003     typedef allocator_traits<__storage_allocator>    __storage_traits;
2004     typedef typename __storage_traits::pointer       __storage_pointer;
2005     typedef typename __storage_traits::const_pointer __const_storage_pointer;
2006
2007     __storage_pointer                                      __begin_;
2008     size_type                                              __size_;
2009     __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2010 public:
2011     typedef __bit_reference<vector>                  reference;
2012     typedef __bit_const_reference<vector>            const_reference;
2013 private:
2014     _LIBCPP_INLINE_VISIBILITY
2015     size_type& __cap() _NOEXCEPT
2016         {return __cap_alloc_.first();}
2017     _LIBCPP_INLINE_VISIBILITY
2018     const size_type& __cap() const _NOEXCEPT
2019         {return __cap_alloc_.first();}
2020     _LIBCPP_INLINE_VISIBILITY
2021     __storage_allocator& __alloc() _NOEXCEPT
2022         {return __cap_alloc_.second();}
2023     _LIBCPP_INLINE_VISIBILITY
2024     const __storage_allocator& __alloc() const _NOEXCEPT
2025         {return __cap_alloc_.second();}
2026
2027     static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2028
2029     _LIBCPP_INLINE_VISIBILITY
2030     static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2031         {return __n * __bits_per_word;}
2032     _LIBCPP_INLINE_VISIBILITY
2033     static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2034         {return (__n - 1) / __bits_per_word + 1;}
2035
2036 public:
2037     _LIBCPP_INLINE_VISIBILITY
2038     vector()
2039         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2040     _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a);
2041     ~vector();
2042     explicit vector(size_type __n);
2043     vector(size_type __n, const value_type& __v);
2044     vector(size_type __n, const value_type& __v, const allocator_type& __a);
2045     template <class _InputIterator>
2046         vector(_InputIterator __first, _InputIterator __last,
2047                typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2048                                  !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2049     template <class _InputIterator>
2050         vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2051                typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2052                                  !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2053     template <class _ForwardIterator>
2054         vector(_ForwardIterator __first, _ForwardIterator __last,
2055                typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2056     template <class _ForwardIterator>
2057         vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2058                typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2059
2060     vector(const vector& __v);
2061     vector(const vector& __v, const allocator_type& __a);
2062     vector& operator=(const vector& __v);
2063 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2064     vector(initializer_list<value_type> __il);
2065     vector(initializer_list<value_type> __il, const allocator_type& __a);
2066 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2067
2068 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2069     _LIBCPP_INLINE_VISIBILITY
2070     vector(vector&& __v)
2071         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2072     vector(vector&& __v, const allocator_type& __a);
2073     _LIBCPP_INLINE_VISIBILITY
2074     vector& operator=(vector&& __v)
2075         _NOEXCEPT_(
2076              __alloc_traits::propagate_on_container_move_assignment::value &&
2077              is_nothrow_move_assignable<allocator_type>::value);
2078 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2079 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2080     _LIBCPP_INLINE_VISIBILITY
2081     vector& operator=(initializer_list<value_type> __il)
2082         {assign(__il.begin(), __il.end()); return *this;}
2083 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2084
2085     template <class _InputIterator>
2086         typename enable_if
2087         <
2088             __is_input_iterator<_InputIterator>::value &&
2089            !__is_forward_iterator<_InputIterator>::value,
2090            void
2091         >::type
2092         assign(_InputIterator __first, _InputIterator __last);
2093     template <class _ForwardIterator>
2094         typename enable_if
2095         <
2096             __is_forward_iterator<_ForwardIterator>::value,
2097            void
2098         >::type
2099         assign(_ForwardIterator __first, _ForwardIterator __last);
2100
2101     void assign(size_type __n, const value_type& __x);
2102 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2103     _LIBCPP_INLINE_VISIBILITY
2104     void assign(initializer_list<value_type> __il)
2105         {assign(__il.begin(), __il.end());}
2106 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2107
2108     _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2109         {return allocator_type(this->__alloc());}
2110
2111     size_type max_size() const _NOEXCEPT;
2112     _LIBCPP_INLINE_VISIBILITY
2113     size_type capacity() const _NOEXCEPT
2114         {return __internal_cap_to_external(__cap());}
2115     _LIBCPP_INLINE_VISIBILITY
2116     size_type size() const _NOEXCEPT
2117         {return __size_;}
2118     _LIBCPP_INLINE_VISIBILITY
2119     bool empty() const _NOEXCEPT
2120         {return __size_ == 0;}
2121     void reserve(size_type __n);
2122     void shrink_to_fit() _NOEXCEPT;
2123
2124     _LIBCPP_INLINE_VISIBILITY
2125     iterator begin() _NOEXCEPT
2126         {return __make_iter(0);}
2127     _LIBCPP_INLINE_VISIBILITY
2128     const_iterator begin() const _NOEXCEPT
2129         {return __make_iter(0);}
2130     _LIBCPP_INLINE_VISIBILITY
2131     iterator end() _NOEXCEPT
2132         {return __make_iter(__size_);}
2133     _LIBCPP_INLINE_VISIBILITY
2134     const_iterator end()   const _NOEXCEPT
2135         {return __make_iter(__size_);}
2136
2137     _LIBCPP_INLINE_VISIBILITY
2138     reverse_iterator rbegin() _NOEXCEPT
2139         {return       reverse_iterator(end());}
2140     _LIBCPP_INLINE_VISIBILITY
2141     const_reverse_iterator rbegin() const _NOEXCEPT
2142         {return const_reverse_iterator(end());}
2143     _LIBCPP_INLINE_VISIBILITY
2144     reverse_iterator rend() _NOEXCEPT
2145         {return       reverse_iterator(begin());}
2146     _LIBCPP_INLINE_VISIBILITY
2147     const_reverse_iterator rend()   const _NOEXCEPT
2148         {return const_reverse_iterator(begin());}
2149
2150     _LIBCPP_INLINE_VISIBILITY
2151     const_iterator         cbegin()  const _NOEXCEPT
2152         {return __make_iter(0);}
2153     _LIBCPP_INLINE_VISIBILITY
2154     const_iterator         cend()    const _NOEXCEPT
2155         {return __make_iter(__size_);}
2156     _LIBCPP_INLINE_VISIBILITY
2157     const_reverse_iterator crbegin() const _NOEXCEPT
2158         {return rbegin();}
2159     _LIBCPP_INLINE_VISIBILITY
2160     const_reverse_iterator crend()   const _NOEXCEPT
2161         {return rend();}
2162
2163     _LIBCPP_INLINE_VISIBILITY reference       operator[](size_type __n)       {return __make_ref(__n);}
2164     _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2165     reference       at(size_type __n);
2166     const_reference at(size_type __n) const;
2167
2168     _LIBCPP_INLINE_VISIBILITY reference       front()       {return __make_ref(0);}
2169     _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2170     _LIBCPP_INLINE_VISIBILITY reference       back()        {return __make_ref(__size_ - 1);}
2171     _LIBCPP_INLINE_VISIBILITY const_reference back()  const {return __make_ref(__size_ - 1);}
2172
2173     void push_back(const value_type& __x);
2174     _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2175
2176     iterator insert(const_iterator __position, const value_type& __x);
2177     iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2178     iterator insert(const_iterator __position, size_type __n, const_reference __x);
2179     template <class _InputIterator>
2180         typename enable_if
2181         <
2182              __is_input_iterator  <_InputIterator>::value &&
2183             !__is_forward_iterator<_InputIterator>::value,
2184             iterator
2185         >::type
2186         insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2187     template <class _ForwardIterator>
2188         typename enable_if
2189         <
2190             __is_forward_iterator<_ForwardIterator>::value,
2191             iterator
2192         >::type
2193         insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2194 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2195     _LIBCPP_INLINE_VISIBILITY
2196     iterator insert(const_iterator __position, initializer_list<value_type> __il)
2197         {return insert(__position, __il.begin(), __il.end());}
2198 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2199
2200     _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2201     iterator erase(const_iterator __first, const_iterator __last);
2202
2203     _LIBCPP_INLINE_VISIBILITY
2204     void clear() _NOEXCEPT {__size_ = 0;}
2205
2206     void swap(vector&)
2207         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2208                    __is_nothrow_swappable<allocator_type>::value);
2209
2210     void resize(size_type __sz, value_type __x = false);
2211     void flip() _NOEXCEPT;
2212
2213     bool __invariants() const;
2214
2215 private:
2216     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2217     void allocate(size_type __n);
2218     void deallocate() _NOEXCEPT;
2219     _LIBCPP_INLINE_VISIBILITY
2220     static size_type __align(size_type __new_size) _NOEXCEPT
2221         {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);};
2222     _LIBCPP_INLINE_VISIBILITY  size_type __recommend(size_type __new_size) const;
2223     _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2224     template <class _ForwardIterator>
2225         typename enable_if
2226         <
2227             __is_forward_iterator<_ForwardIterator>::value,
2228             void
2229         >::type
2230         __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2231     void __append(size_type __n, const_reference __x);
2232     _LIBCPP_INLINE_VISIBILITY
2233     reference __make_ref(size_type __pos) _NOEXCEPT
2234         {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2235     _LIBCPP_INLINE_VISIBILITY
2236     const_reference __make_ref(size_type __pos) const _NOEXCEPT
2237         {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2238 #ifdef _LIBCPP_DEBUG
2239     _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos)
2240         {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2241     _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const
2242         {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2243     _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p)
2244         {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));}
2245 #else  // _LIBCPP_DEBUG
2246     _LIBCPP_INLINE_VISIBILITY
2247     iterator __make_iter(size_type __pos) _NOEXCEPT
2248         {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2249     _LIBCPP_INLINE_VISIBILITY
2250     const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2251         {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2252     _LIBCPP_INLINE_VISIBILITY
2253     iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2254         {return iterator(const_cast<__storage_pointer>(__p.__seg_), __p.__ctz_);}
2255 #endif  // _LIBCPP_DEBUG
2256
2257     _LIBCPP_INLINE_VISIBILITY
2258     void __copy_assign_alloc(const vector& __v)
2259         {__copy_assign_alloc(__v, integral_constant<bool,
2260                       __storage_traits::propagate_on_container_copy_assignment::value>());}
2261     _LIBCPP_INLINE_VISIBILITY
2262     void __copy_assign_alloc(const vector& __c, true_type)
2263         {
2264             if (__alloc() != __c.__alloc())
2265                 deallocate();
2266             __alloc() = __c.__alloc();
2267         }
2268
2269     _LIBCPP_INLINE_VISIBILITY
2270     void __copy_assign_alloc(const vector&, false_type)
2271         {}
2272
2273     void __move_assign(vector& __c, false_type);
2274     void __move_assign(vector& __c, true_type)
2275         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2276     _LIBCPP_INLINE_VISIBILITY
2277     void __move_assign_alloc(vector& __c)
2278         _NOEXCEPT_(
2279             !__storage_traits::propagate_on_container_move_assignment::value ||
2280             is_nothrow_move_assignable<allocator_type>::value)
2281         {__move_assign_alloc(__c, integral_constant<bool,
2282                       __storage_traits::propagate_on_container_move_assignment::value>());}
2283     _LIBCPP_INLINE_VISIBILITY
2284     void __move_assign_alloc(vector& __c, true_type)
2285         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2286         {
2287             __alloc() = _VSTD::move(__c.__alloc());
2288         }
2289
2290     _LIBCPP_INLINE_VISIBILITY
2291     void __move_assign_alloc(vector&, false_type)
2292         _NOEXCEPT
2293         {}
2294
2295     _LIBCPP_INLINE_VISIBILITY
2296     static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y)
2297         _NOEXCEPT_(
2298             !__storage_traits::propagate_on_container_swap::value ||
2299             __is_nothrow_swappable<allocator_type>::value)
2300         {__swap_alloc(__x, __y, integral_constant<bool,
2301                       __storage_traits::propagate_on_container_swap::value>());}
2302
2303     _LIBCPP_INLINE_VISIBILITY
2304     static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type)
2305         _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
2306         {
2307             using _VSTD::swap;
2308             swap(__x, __y);
2309         }
2310     _LIBCPP_INLINE_VISIBILITY
2311     static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type)
2312         _NOEXCEPT
2313         {}
2314
2315     size_t __hash_code() const _NOEXCEPT;
2316
2317     friend class __bit_reference<vector>;
2318     friend class __bit_const_reference<vector>;
2319     friend class __bit_iterator<vector, false>;
2320     friend class __bit_iterator<vector, true>;
2321     friend struct __bit_array<vector>;
2322     friend struct _LIBCPP_VISIBLE hash<vector>;
2323 };
2324
2325 template <class _Allocator>
2326 #ifndef _LIBCPP_DEBUG
2327 _LIBCPP_INLINE_VISIBILITY inline
2328 #endif
2329 void
2330 vector<bool, _Allocator>::__invalidate_all_iterators()
2331 {
2332 #ifdef _LIBCPP_DEBUG
2333     iterator::__remove_all(this);
2334     const_iterator::__remove_all(this);
2335 #endif  // _LIBCPP_DEBUG
2336 }
2337
2338 //  Allocate space for __n objects
2339 //  throws length_error if __n > max_size()
2340 //  throws (probably bad_alloc) if memory run out
2341 //  Precondition:  __begin_ == __end_ == __cap() == 0
2342 //  Precondition:  __n > 0
2343 //  Postcondition:  capacity() == __n
2344 //  Postcondition:  size() == 0
2345 template <class _Allocator>
2346 void
2347 vector<bool, _Allocator>::allocate(size_type __n)
2348 {
2349     if (__n > max_size())
2350         this->__throw_length_error();
2351     __n = __external_cap_to_internal(__n);
2352     this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2353     this->__size_ = 0;
2354     this->__cap() = __n;
2355 }
2356
2357 template <class _Allocator>
2358 void
2359 vector<bool, _Allocator>::deallocate() _NOEXCEPT
2360 {
2361     if (this->__begin_ != 0)
2362     {
2363         __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2364         __invalidate_all_iterators();
2365         this->__begin_ = 0;
2366         this->__size_ = this->__cap() = 0;
2367     }
2368 }
2369
2370 template <class _Allocator>
2371 typename vector<bool, _Allocator>::size_type
2372 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2373 {
2374     size_type __amax = __storage_traits::max_size(__alloc());
2375     size_type __nmax = numeric_limits<size_type>::max() / 2;  // end() >= begin(), always
2376     if (__nmax / __bits_per_word <= __amax)
2377         return __nmax;
2378     return __internal_cap_to_external(__amax);
2379 }
2380
2381 //  Precondition:  __new_size > capacity()
2382 template <class _Allocator>
2383 _LIBCPP_INLINE_VISIBILITY inline
2384 typename vector<bool, _Allocator>::size_type
2385 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2386 {
2387     const size_type __ms = max_size();
2388     if (__new_size > __ms)
2389         this->__throw_length_error();
2390     const size_type __cap = capacity();
2391     if (__cap >= __ms / 2)
2392         return __ms;
2393     return _VSTD::max(2*__cap, __align(__new_size));
2394 }
2395
2396 //  Default constructs __n objects starting at __end_
2397 //  Precondition:  __n > 0
2398 //  Precondition:  size() + __n <= capacity()
2399 //  Postcondition:  size() == size() + __n
2400 template <class _Allocator>
2401 _LIBCPP_INLINE_VISIBILITY inline
2402 void
2403 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2404 {
2405     size_type __old_size = this->__size_;
2406     this->__size_ += __n;
2407     _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2408 }
2409
2410 template <class _Allocator>
2411 template <class _ForwardIterator>
2412 typename enable_if
2413 <
2414     __is_forward_iterator<_ForwardIterator>::value,
2415     void
2416 >::type
2417 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2418 {
2419     size_type __old_size = this->__size_;
2420     this->__size_ += _VSTD::distance(__first, __last);
2421     _VSTD::copy(__first, __last, __make_iter(__old_size));
2422 }
2423
2424 template <class _Allocator>
2425 _LIBCPP_INLINE_VISIBILITY inline
2426 vector<bool, _Allocator>::vector()
2427         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2428     : __begin_(0),
2429       __size_(0),
2430       __cap_alloc_(0)
2431 {
2432 }
2433
2434 template <class _Allocator>
2435 _LIBCPP_INLINE_VISIBILITY inline
2436 vector<bool, _Allocator>::vector(const allocator_type& __a)
2437     : __begin_(0),
2438       __size_(0),
2439       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2440 {
2441 }
2442
2443 template <class _Allocator>
2444 vector<bool, _Allocator>::vector(size_type __n)
2445     : __begin_(0),
2446       __size_(0),
2447       __cap_alloc_(0)
2448 {
2449     if (__n > 0)
2450     {
2451         allocate(__n);
2452         __construct_at_end(__n, false);
2453     }
2454 }
2455
2456 template <class _Allocator>
2457 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2458     : __begin_(0),
2459       __size_(0),
2460       __cap_alloc_(0)
2461 {
2462     if (__n > 0)
2463     {
2464         allocate(__n);
2465         __construct_at_end(__n, __x);
2466     }
2467 }
2468
2469 template <class _Allocator>
2470 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2471     : __begin_(0),
2472       __size_(0),
2473       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2474 {
2475     if (__n > 0)
2476     {
2477         allocate(__n);
2478         __construct_at_end(__n, __x);
2479     }
2480 }
2481
2482 template <class _Allocator>
2483 template <class _InputIterator>
2484 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2485        typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2486                          !__is_forward_iterator<_InputIterator>::value>::type*)
2487     : __begin_(0),
2488       __size_(0),
2489       __cap_alloc_(0)
2490 {
2491 #ifndef _LIBCPP_NO_EXCEPTIONS
2492     try
2493     {
2494 #endif  // _LIBCPP_NO_EXCEPTIONS
2495         for (; __first != __last; ++__first)
2496             push_back(*__first);
2497 #ifndef _LIBCPP_NO_EXCEPTIONS
2498     }
2499     catch (...)
2500     {
2501         if (__begin_ != 0)
2502             __storage_traits::deallocate(__alloc(), __begin_, __cap());
2503         __invalidate_all_iterators();
2504         throw;
2505     }
2506 #endif  // _LIBCPP_NO_EXCEPTIONS
2507 }
2508
2509 template <class _Allocator>
2510 template <class _InputIterator>
2511 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2512        typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2513                          !__is_forward_iterator<_InputIterator>::value>::type*)
2514     : __begin_(0),
2515       __size_(0),
2516       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2517 {
2518 #ifndef _LIBCPP_NO_EXCEPTIONS
2519     try
2520     {
2521 #endif  // _LIBCPP_NO_EXCEPTIONS
2522         for (; __first != __last; ++__first)
2523             push_back(*__first);
2524 #ifndef _LIBCPP_NO_EXCEPTIONS
2525     }
2526     catch (...)
2527     {
2528         if (__begin_ != 0)
2529             __storage_traits::deallocate(__alloc(), __begin_, __cap());
2530         __invalidate_all_iterators();
2531         throw;
2532     }
2533 #endif  // _LIBCPP_NO_EXCEPTIONS
2534 }
2535
2536 template <class _Allocator>
2537 template <class _ForwardIterator>
2538 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2539                                 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2540     : __begin_(0),
2541       __size_(0),
2542       __cap_alloc_(0)
2543 {
2544     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2545     if (__n > 0)
2546     {
2547         allocate(__n);
2548         __construct_at_end(__first, __last);
2549     }
2550 }
2551
2552 template <class _Allocator>
2553 template <class _ForwardIterator>
2554 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2555                                 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2556     : __begin_(0),
2557       __size_(0),
2558       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2559 {
2560     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2561     if (__n > 0)
2562     {
2563         allocate(__n);
2564         __construct_at_end(__first, __last);
2565     }
2566 }
2567
2568 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2569
2570 template <class _Allocator>
2571 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2572     : __begin_(0),
2573       __size_(0),
2574       __cap_alloc_(0)
2575 {
2576     size_type __n = static_cast<size_type>(__il.size());
2577     if (__n > 0)
2578     {
2579         allocate(__n);
2580         __construct_at_end(__il.begin(), __il.end());
2581     }
2582 }
2583
2584 template <class _Allocator>
2585 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2586     : __begin_(0),
2587       __size_(0),
2588       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2589 {
2590     size_type __n = static_cast<size_type>(__il.size());
2591     if (__n > 0)
2592     {
2593         allocate(__n);
2594         __construct_at_end(__il.begin(), __il.end());
2595     }
2596 }
2597
2598 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2599
2600 template <class _Allocator>
2601 vector<bool, _Allocator>::~vector()
2602 {
2603     if (__begin_ != 0)
2604         __storage_traits::deallocate(__alloc(), __begin_, __cap());
2605 #ifdef _LIBCPP_DEBUG
2606     __invalidate_all_iterators();
2607 #endif
2608 }
2609
2610 template <class _Allocator>
2611 vector<bool, _Allocator>::vector(const vector& __v)
2612     : __begin_(0),
2613       __size_(0),
2614       __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2615 {
2616     if (__v.size() > 0)
2617     {
2618         allocate(__v.size());
2619         __construct_at_end(__v.begin(), __v.end());
2620     }
2621 }
2622
2623 template <class _Allocator>
2624 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2625     : __begin_(0),
2626       __size_(0),
2627       __cap_alloc_(0, __a)
2628 {
2629     if (__v.size() > 0)
2630     {
2631         allocate(__v.size());
2632         __construct_at_end(__v.begin(), __v.end());
2633     }
2634 }
2635
2636 template <class _Allocator>
2637 vector<bool, _Allocator>&
2638 vector<bool, _Allocator>::operator=(const vector& __v)
2639 {
2640     if (this != &__v)
2641     {
2642         __copy_assign_alloc(__v);
2643         if (__v.__size_)
2644         {
2645             if (__v.__size_ > capacity())
2646             {
2647                 deallocate();
2648                 allocate(__v.__size_);
2649             }
2650             _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2651         }
2652         __size_ = __v.__size_;
2653     }
2654     return *this;
2655 }
2656
2657 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2658
2659 template <class _Allocator>
2660 _LIBCPP_INLINE_VISIBILITY inline
2661 vector<bool, _Allocator>::vector(vector&& __v)
2662         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2663     : __begin_(__v.__begin_),
2664       __size_(__v.__size_),
2665       __cap_alloc_(__v.__cap_alloc_)
2666 {
2667     __v.__begin_ = 0;
2668     __v.__size_ = 0;
2669     __v.__cap() = 0;
2670 }
2671
2672 template <class _Allocator>
2673 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2674     : __begin_(0),
2675       __size_(0),
2676       __cap_alloc_(0, __a)
2677 {
2678     if (__a == allocator_type(__v.__alloc()))
2679     {
2680         this->__begin_ = __v.__begin_;
2681         this->__size_ = __v.__size_;
2682         this->__cap() = __v.__cap();
2683         __v.__begin_ = nullptr;
2684         __v.__cap() = __v.__size_ = 0;
2685     }
2686     else if (__v.size() > 0)
2687     {
2688         allocate(__v.size());
2689         __construct_at_end(__v.begin(), __v.end());
2690     }
2691 }
2692
2693 template <class _Allocator>
2694 _LIBCPP_INLINE_VISIBILITY inline
2695 vector<bool, _Allocator>&
2696 vector<bool, _Allocator>::operator=(vector&& __v)
2697         _NOEXCEPT_(
2698              __alloc_traits::propagate_on_container_move_assignment::value &&
2699              is_nothrow_move_assignable<allocator_type>::value)
2700 {
2701     __move_assign(__v, integral_constant<bool,
2702           __storage_traits::propagate_on_container_move_assignment::value>());
2703     return *this;
2704 }
2705
2706 template <class _Allocator>
2707 void
2708 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2709 {
2710     if (__alloc() != __c.__alloc())
2711         assign(__c.begin(), __c.end());
2712     else
2713         __move_assign(__c, true_type());
2714 }
2715
2716 template <class _Allocator>
2717 void
2718 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2719     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2720 {
2721     deallocate();
2722     this->__begin_ = __c.__begin_;
2723     this->__size_ = __c.__size_;
2724     this->__cap() = __c.__cap();
2725     __move_assign_alloc(__c);
2726     __c.__begin_ = nullptr;
2727     __c.__cap() = __c.__size_ = 0;
2728 }
2729
2730 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2731
2732 template <class _Allocator>
2733 void
2734 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2735 {
2736     __size_ = 0;
2737     if (__n > 0)
2738     {
2739         size_type __c = capacity();
2740         if (__n <= __c)
2741             __size_ = __n;
2742         else
2743         {
2744             vector __v(__alloc());
2745             __v.reserve(__recommend(__n));
2746             __v.__size_ = __n;
2747             swap(__v);
2748         }
2749         _VSTD::fill_n(begin(), __n, __x);
2750     }
2751 }
2752
2753 template <class _Allocator>
2754 template <class _InputIterator>
2755 typename enable_if
2756 <
2757     __is_input_iterator<_InputIterator>::value &&
2758    !__is_forward_iterator<_InputIterator>::value,
2759    void
2760 >::type
2761 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2762 {
2763     clear();
2764     for (; __first != __last; ++__first)
2765         push_back(*__first);
2766 }
2767
2768 template <class _Allocator>
2769 template <class _ForwardIterator>
2770 typename enable_if
2771 <
2772     __is_forward_iterator<_ForwardIterator>::value,
2773    void
2774 >::type
2775 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2776 {
2777     clear();
2778     difference_type __n = _VSTD::distance(__first, __last);
2779     if (__n)
2780     {
2781         if (__n > capacity())
2782         {
2783             deallocate();
2784             allocate(__n);
2785         }
2786         __construct_at_end(__first, __last);
2787     }
2788 }
2789
2790 template <class _Allocator>
2791 void
2792 vector<bool, _Allocator>::reserve(size_type __n)
2793 {
2794     if (__n > capacity())
2795     {
2796         vector __v(this->__alloc());
2797         __v.allocate(__n);
2798         __v.__construct_at_end(this->begin(), this->end());
2799         swap(__v);
2800         __invalidate_all_iterators();
2801     }
2802 }
2803
2804 template <class _Allocator>
2805 void
2806 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
2807 {
2808     if (__external_cap_to_internal(size()) > __cap())
2809     {
2810 #ifndef _LIBCPP_NO_EXCEPTIONS
2811         try
2812         {
2813 #endif  // _LIBCPP_NO_EXCEPTIONS
2814             vector(*this, allocator_type(__alloc())).swap(*this);
2815 #ifndef _LIBCPP_NO_EXCEPTIONS
2816         }
2817         catch (...)
2818         {
2819         }
2820 #endif  // _LIBCPP_NO_EXCEPTIONS
2821     }
2822 }
2823
2824 template <class _Allocator>
2825 typename vector<bool, _Allocator>::reference
2826 vector<bool, _Allocator>::at(size_type __n)
2827 {
2828     if (__n >= size())
2829         this->__throw_out_of_range();
2830     return (*this)[__n];
2831 }
2832
2833 template <class _Allocator>
2834 typename vector<bool, _Allocator>::const_reference
2835 vector<bool, _Allocator>::at(size_type __n) const
2836 {
2837     if (__n >= size())
2838         this->__throw_out_of_range();
2839     return (*this)[__n];
2840 }
2841
2842 template <class _Allocator>
2843 void
2844 vector<bool, _Allocator>::push_back(const value_type& __x)
2845 {
2846     if (this->__size_ == this->capacity())
2847         reserve(__recommend(this->__size_ + 1));
2848     ++this->__size_;
2849     back() = __x;
2850 }
2851
2852 template <class _Allocator>
2853 typename vector<bool, _Allocator>::iterator
2854 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
2855 {
2856     iterator __r;
2857     if (size() < capacity())
2858     {
2859         const_iterator __old_end = end();
2860         ++__size_;
2861         _VSTD::copy_backward(__position, __old_end, end());
2862         __r = __const_iterator_cast(__position);
2863     }
2864     else
2865     {
2866         vector __v(__alloc());
2867         __v.reserve(__recommend(__size_ + 1));
2868         __v.__size_ = __size_ + 1;
2869         __r = _VSTD::copy(cbegin(), __position, __v.begin());
2870         _VSTD::copy_backward(__position, cend(), __v.end());
2871         swap(__v);
2872     }
2873     *__r = __x;
2874     return __r;
2875 }
2876
2877 template <class _Allocator>
2878 typename vector<bool, _Allocator>::iterator
2879 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
2880 {
2881     iterator __r;
2882     size_type __c = capacity();
2883     if (__n <= __c && size() <= __c - __n)
2884     {
2885         const_iterator __old_end = end();
2886         __size_ += __n;
2887         _VSTD::copy_backward(__position, __old_end, end());
2888         __r = __const_iterator_cast(__position);
2889     }
2890     else
2891     {
2892         vector __v(__alloc());
2893         __v.reserve(__recommend(__size_ + __n));
2894         __v.__size_ = __size_ + __n;
2895         __r = _VSTD::copy(cbegin(), __position, __v.begin());
2896         _VSTD::copy_backward(__position, cend(), __v.end());
2897         swap(__v);
2898     }
2899     _VSTD::fill_n(__r, __n, __x);
2900     return __r;
2901 }
2902
2903 template <class _Allocator>
2904 template <class _InputIterator>
2905 typename enable_if
2906 <
2907      __is_input_iterator  <_InputIterator>::value &&
2908     !__is_forward_iterator<_InputIterator>::value,
2909     typename vector<bool, _Allocator>::iterator
2910 >::type
2911 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
2912 {
2913     difference_type __off = __position - begin();
2914     iterator __p = __const_iterator_cast(__position);
2915     iterator __old_end = end();
2916     for (; size() != capacity() && __first != __last; ++__first)
2917     {
2918         ++this->__size_;
2919         back() = *__first;
2920     }
2921     vector __v(__alloc());
2922     if (__first != __last)
2923     {
2924 #ifndef _LIBCPP_NO_EXCEPTIONS
2925         try
2926         {
2927 #endif  // _LIBCPP_NO_EXCEPTIONS
2928             __v.assign(__first, __last);
2929             difference_type __old_size = static_cast<difference_type>(__old_end - begin());
2930             difference_type __old_p = __p - begin();
2931             reserve(__recommend(size() + __v.size()));
2932             __p = begin() + __old_p;
2933             __old_end = begin() + __old_size;
2934 #ifndef _LIBCPP_NO_EXCEPTIONS
2935         }
2936         catch (...)
2937         {
2938             erase(__old_end, end());
2939             throw;
2940         }
2941 #endif  // _LIBCPP_NO_EXCEPTIONS
2942     }
2943     __p = _VSTD::rotate(__p, __old_end, end());
2944     insert(__p, __v.begin(), __v.end());
2945     return begin() + __off;
2946 }
2947
2948 template <class _Allocator>
2949 template <class _ForwardIterator>
2950 typename enable_if
2951 <
2952     __is_forward_iterator<_ForwardIterator>::value,
2953     typename vector<bool, _Allocator>::iterator
2954 >::type
2955 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
2956 {
2957     difference_type __n = _VSTD::distance(__first, __last);
2958     iterator __r;
2959     size_type __c = capacity();
2960     if (__n <= __c && size() <= __c - __n)
2961     {
2962         const_iterator __old_end = end();
2963         __size_ += __n;
2964         _VSTD::copy_backward(__position, __old_end, end());
2965         __r = __const_iterator_cast(__position);
2966     }
2967     else
2968     {
2969         vector __v(__alloc());
2970         __v.reserve(__recommend(__size_ + __n));
2971         __v.__size_ = __size_ + __n;
2972         __r = _VSTD::copy(cbegin(), __position, __v.begin());
2973         _VSTD::copy_backward(__position, cend(), __v.end());
2974         swap(__v);
2975     }
2976     _VSTD::copy(__first, __last, __r);
2977     return __r;
2978 }
2979
2980 template <class _Allocator>
2981 _LIBCPP_INLINE_VISIBILITY inline
2982 typename vector<bool, _Allocator>::iterator
2983 vector<bool, _Allocator>::erase(const_iterator __position)
2984 {
2985     iterator __r = __const_iterator_cast(__position);
2986     _VSTD::copy(__position + 1, this->cend(), __r);
2987     --__size_;
2988     return __r;
2989 }
2990
2991 template <class _Allocator>
2992 typename vector<bool, _Allocator>::iterator
2993 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
2994 {
2995     iterator __r = __const_iterator_cast(__first);
2996     difference_type __d = __last - __first;
2997     _VSTD::copy(__last, this->cend(), __r);
2998     __size_ -= __d;
2999     return __r;
3000 }
3001
3002 template <class _Allocator>
3003 void
3004 vector<bool, _Allocator>::swap(vector& __x)
3005         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3006                    __is_nothrow_swappable<allocator_type>::value)
3007 {
3008     _VSTD::swap(this->__begin_, __x.__begin_);
3009     _VSTD::swap(this->__size_, __x.__size_);
3010     _VSTD::swap(this->__cap(), __x.__cap());
3011     __swap_alloc(this->__alloc(), __x.__alloc());
3012 #ifdef _LIBCPP_DEBUG
3013     iterator::swap(this, &__x);
3014     const_iterator::swap(this, &__x);
3015 #endif  // _LIBCPP_DEBUG
3016 }
3017
3018 template <class _Allocator>
3019 void
3020 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3021 {
3022     size_type __cs = size();
3023     if (__cs < __sz)
3024     {
3025         iterator __r;
3026         size_type __c = capacity();
3027         size_type __n = __sz - __cs;
3028         if (__n <= __c && __cs <= __c - __n)
3029         {
3030             __r = end();
3031             __size_ += __n;
3032         }
3033         else
3034         {
3035             vector __v(__alloc());
3036             __v.reserve(__recommend(__size_ + __n));
3037             __v.__size_ = __size_ + __n;
3038             __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3039             swap(__v);
3040         }
3041         _VSTD::fill_n(__r, __n, __x);
3042     }
3043     else
3044         __size_ = __sz;
3045 }
3046
3047 template <class _Allocator>
3048 void
3049 vector<bool, _Allocator>::flip() _NOEXCEPT
3050 {
3051     // do middle whole words
3052     size_type __n = __size_;
3053     __storage_pointer __p = __begin_;
3054     for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3055         *__p = ~*__p;
3056     // do last partial word
3057     if (__n > 0)
3058     {
3059         __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3060         __storage_type __b = *__p & __m;
3061         *__p &= ~__m;
3062         *__p |= ~__b & __m;
3063     }
3064 }
3065
3066 template <class _Allocator>
3067 bool
3068 vector<bool, _Allocator>::__invariants() const
3069 {
3070     if (this->__begin_ == 0)
3071     {
3072         if (this->__size_ != 0 || this->__cap() != 0)
3073             return false;
3074     }
3075     else
3076     {
3077         if (this->__cap() == 0)
3078             return false;
3079         if (this->__size_ > this->capacity())
3080             return false;
3081     }
3082     return true;
3083 }
3084
3085 template <class _Allocator>
3086 size_t
3087 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3088 {
3089     size_t __h = 0;
3090     // do middle whole words
3091     size_type __n = __size_;
3092     __storage_pointer __p = __begin_;
3093     for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3094         __h ^= *__p;
3095     // do last partial word
3096     if (__n > 0)
3097     {
3098         const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3099         __h ^= *__p & __m;
3100     }
3101     return __h;
3102 }
3103
3104 template <class _Allocator>
3105 struct _LIBCPP_VISIBLE hash<vector<bool, _Allocator> >
3106     : public unary_function<vector<bool, _Allocator>, size_t>
3107 {
3108     _LIBCPP_INLINE_VISIBILITY
3109     size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3110         {return __vec.__hash_code();}
3111 };
3112
3113 template <class _Tp, class _Allocator>
3114 _LIBCPP_INLINE_VISIBILITY inline
3115 bool
3116 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3117 {
3118     const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3119     return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3120 }
3121
3122 template <class _Tp, class _Allocator>
3123 _LIBCPP_INLINE_VISIBILITY inline
3124 bool
3125 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3126 {
3127     return !(__x == __y);
3128 }
3129
3130 template <class _Tp, class _Allocator>
3131 _LIBCPP_INLINE_VISIBILITY inline
3132 bool
3133 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3134 {
3135     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3136 }
3137
3138 template <class _Tp, class _Allocator>
3139 _LIBCPP_INLINE_VISIBILITY inline
3140 bool
3141 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3142 {
3143     return __y < __x;
3144 }
3145
3146 template <class _Tp, class _Allocator>
3147 _LIBCPP_INLINE_VISIBILITY inline
3148 bool
3149 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3150 {
3151     return !(__x < __y);
3152 }
3153
3154 template <class _Tp, class _Allocator>
3155 _LIBCPP_INLINE_VISIBILITY inline
3156 bool
3157 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3158 {
3159     return !(__y < __x);
3160 }
3161
3162 template <class _Tp, class _Allocator>
3163 _LIBCPP_INLINE_VISIBILITY inline
3164 void
3165 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3166     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3167 {
3168     __x.swap(__y);
3169 }
3170
3171 _LIBCPP_END_NAMESPACE_STD
3172
3173 #endif  // _LIBCPP_VECTOR