contrib/libc++/include/vector

   1 // -*- C++ -*-
   2 //===------------------------------ vector --------------------------------===//
   3 //
   4 //                     The LLVM Compiler Infrastructure
   5 //
   6 // This file is dual licensed under the MIT and the University of Illinois Open
   7 // Source Licenses. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #ifndef _LIBCPP_VECTOR
  12 #define _LIBCPP_VECTOR
  13
  14 /*
  15     vector synopsis
  16
  17 namespace std
  18 {
  19
  20 template <class T, class Allocator = allocator<T> >
  21 class vector
  22 {
  23 public:
  24     typedef T                                        value_type;
  25     typedef Allocator                                allocator_type;
  26     typedef typename allocator_type::reference       reference;
  27     typedef typename allocator_type::const_reference const_reference;
  28     typedef implementation-defined                   iterator;
  29     typedef implementation-defined                   const_iterator;
  30     typedef typename allocator_type::size_type       size_type;
  31     typedef typename allocator_type::difference_type difference_type;
  32     typedef typename allocator_type::pointer         pointer;
  33     typedef typename allocator_type::const_pointer   const_pointer;
  34     typedef std::reverse_iterator<iterator>          reverse_iterator;
  35     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
  36
  37     vector()
  38         noexcept(is_nothrow_default_constructible<allocator_type>::value);
  39     explicit vector(const allocator_type&);
  40     explicit vector(size_type n);
  41     vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
  42     template <class InputIterator>
  43         vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
  44     vector(const vector& x);
  45     vector(vector&& x)
  46         noexcept(is_nothrow_move_constructible<allocator_type>::value);
  47     vector(initializer_list<value_type> il);
  48     vector(initializer_list<value_type> il, const allocator_type& a);
  49     ~vector();
  50     vector& operator=(const vector& x);
  51     vector& operator=(vector&& x)
  52         noexcept(
  53              allocator_type::propagate_on_container_move_assignment::value &&
  54              is_nothrow_move_assignable<allocator_type>::value);
  55     vector& operator=(initializer_list<value_type> il);
  56     template <class InputIterator>
  57         void assign(InputIterator first, InputIterator last);
  58     void assign(size_type n, const value_type& u);
  59     void assign(initializer_list<value_type> il);
  60
  61     allocator_type get_allocator() const noexcept;
  62
  63     iterator               begin() noexcept;
  64     const_iterator         begin()   const noexcept;
  65     iterator               end() noexcept;
  66     const_iterator         end()     const noexcept;
  67
  68     reverse_iterator       rbegin() noexcept;
  69     const_reverse_iterator rbegin()  const noexcept;
  70     reverse_iterator       rend() noexcept;
  71     const_reverse_iterator rend()    const noexcept;
  72
  73     const_iterator         cbegin()  const noexcept;
  74     const_iterator         cend()    const noexcept;
  75     const_reverse_iterator crbegin() const noexcept;
  76     const_reverse_iterator crend()   const noexcept;
  77
  78     size_type size() const noexcept;
  79     size_type max_size() const noexcept;
  80     size_type capacity() const noexcept;
  81     bool empty() const noexcept;
  82     void reserve(size_type n);
  83     void shrink_to_fit() noexcept;
  84
  85     reference       operator[](size_type n);
  86     const_reference operator[](size_type n) const;
  87     reference       at(size_type n);
  88     const_reference at(size_type n) const;
  89
  90     reference       front();
  91     const_reference front() const;
  92     reference       back();
  93     const_reference back() const;
  94
  95     value_type*       data() noexcept;
  96     const value_type* data() const noexcept;
  97
  98     void push_back(const value_type& x);
  99     void push_back(value_type&& x);
 100     template <class... Args>
 101         void emplace_back(Args&&... args);
 102     void pop_back();
 103
 104     template <class... Args> iterator emplace(const_iterator position, Args&&... args);
 105     iterator insert(const_iterator position, const value_type& x);
 106     iterator insert(const_iterator position, value_type&& x);
 107     iterator insert(const_iterator position, size_type n, const value_type& x);
 108     template <class InputIterator>
 109         iterator insert(const_iterator position, InputIterator first, InputIterator last);
 110     iterator insert(const_iterator position, initializer_list<value_type> il);
 111
 112     iterator erase(const_iterator position);
 113     iterator erase(const_iterator first, const_iterator last);
 114
 115     void clear() noexcept;
 116
 117     void resize(size_type sz);
 118     void resize(size_type sz, const value_type& c);
 119
 120     void swap(vector&)
 121         noexcept(!allocator_type::propagate_on_container_swap::value ||
 122                  __is_nothrow_swappable<allocator_type>::value);
 123
 124     bool __invariants() const;
 125 };
 126
 127 template <class Allocator = allocator<T> >
 128 class vector<bool, Allocator>
 129 {
 130 public:
 131     typedef bool                                     value_type;
 132     typedef Allocator                                allocator_type;
 133     typedef implementation-defined                   iterator;
 134     typedef implementation-defined                   const_iterator;
 135     typedef typename allocator_type::size_type       size_type;
 136     typedef typename allocator_type::difference_type difference_type;
 137     typedef iterator                                 pointer;
 138     typedef const_iterator                           const_pointer;
 139     typedef std::reverse_iterator<iterator>          reverse_iterator;
 140     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 141
 142     class reference
 143     {
 144     public:
 145         reference(const reference&) noexcept;
 146         operator bool() const noexcept;
 147         reference& operator=(const bool x) noexcept;
 148         reference& operator=(const reference& x) noexcept;
 149         iterator operator&() const noexcept;
 150         void flip() noexcept;
 151     };
 152
 153     class const_reference
 154     {
 155     public:
 156         const_reference(const reference&) noexcept;
 157         operator bool() const noexcept;
 158         const_iterator operator&() const noexcept;
 159     };
 160
 161     vector()
 162         noexcept(is_nothrow_default_constructible<allocator_type>::value);
 163     explicit vector(const allocator_type&);
 164     explicit vector(size_type n, const value_type& value = value_type(), const allocator_type& = allocator_type());
 165     template <class InputIterator>
 166         vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
 167     vector(const vector& x);
 168     vector(vector&& x)
 169         noexcept(is_nothrow_move_constructible<allocator_type>::value);
 170     vector(initializer_list<value_type> il);
 171     vector(initializer_list<value_type> il, const allocator_type& a);
 172     ~vector();
 173     vector& operator=(const vector& x);
 174     vector& operator=(vector&& x)
 175         noexcept(
 176              allocator_type::propagate_on_container_move_assignment::value &&
 177              is_nothrow_move_assignable<allocator_type>::value);
 178     vector& operator=(initializer_list<value_type> il);
 179     template <class InputIterator>
 180         void assign(InputIterator first, InputIterator last);
 181     void assign(size_type n, const value_type& u);
 182     void assign(initializer_list<value_type> il);
 183
 184     allocator_type get_allocator() const noexcept;
 185
 186     iterator               begin() noexcept;
 187     const_iterator         begin()   const noexcept;
 188     iterator               end() noexcept;
 189     const_iterator         end()     const noexcept;
 190
 191     reverse_iterator       rbegin() noexcept;
 192     const_reverse_iterator rbegin()  const noexcept;
 193     reverse_iterator       rend() noexcept;
 194     const_reverse_iterator rend()    const noexcept;
 195
 196     const_iterator         cbegin()  const noexcept;
 197     const_iterator         cend()    const noexcept;
 198     const_reverse_iterator crbegin() const noexcept;
 199     const_reverse_iterator crend()   const noexcept;
 200
 201     size_type size() const noexcept;
 202     size_type max_size() const noexcept;
 203     size_type capacity() const noexcept;
 204     bool empty() const noexcept;
 205     void reserve(size_type n);
 206     void shrink_to_fit() noexcept;
 207
 208     reference       operator[](size_type n);
 209     const_reference operator[](size_type n) const;
 210     reference       at(size_type n);
 211     const_reference at(size_type n) const;
 212
 213     reference       front();
 214     const_reference front() const;
 215     reference       back();
 216     const_reference back() const;
 217
 218     void push_back(const value_type& x);
 219     void pop_back();
 220
 221     iterator insert(const_iterator position, const value_type& x);
 222     iterator insert(const_iterator position, size_type n, const value_type& x);
 223     template <class InputIterator>
 224         iterator insert(const_iterator position, InputIterator first, InputIterator last);
 225     iterator insert(const_iterator position, initializer_list<value_type> il);
 226
 227     iterator erase(const_iterator position);
 228     iterator erase(const_iterator first, const_iterator last);
 229
 230     void clear() noexcept;
 231
 232     void resize(size_type sz);
 233     void resize(size_type sz, value_type x);
 234
 235     void swap(vector&)
 236         noexcept(!allocator_type::propagate_on_container_swap::value ||
 237                  __is_nothrow_swappable<allocator_type>::value);
 238     void flip() noexcept;
 239
 240     bool __invariants() const;
 241 };
 242
 243 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
 244
 245 template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
 246 template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
 247 template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
 248 template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
 249 template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
 250 template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
 251
 252 template <class T, class Allocator>
 253 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
 254     noexcept(noexcept(x.swap(y)));
 255
 256 }  // std
 257
 258 */
 259
 260 #include <__config>
 261 #include <__bit_reference>
 262 #include <type_traits>
 263 #include <climits>
 264 #include <limits>
 265 #include <initializer_list>
 266 #include <memory>
 267 #include <stdexcept>
 268 #include <algorithm>
 269 #include <cstring>
 270 #include <__split_buffer>
 271 #include <__functional_base>
 272
 273 #include <__undef_min_max>
 274
 275 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 276 #pragma GCC system_header
 277 #endif
 278
 279 _LIBCPP_BEGIN_NAMESPACE_STD
 280
 281 template <bool>
 282 class __vector_base_common
 283 {
 284 protected:
 285     _LIBCPP_ALWAYS_INLINE __vector_base_common() {}
 286     void __throw_length_error() const;
 287     void __throw_out_of_range() const;
 288 };
 289
 290 template <bool __b>
 291 void
 292 __vector_base_common<__b>::__throw_length_error() const
 293 {
 294 #ifndef _LIBCPP_NO_EXCEPTIONS
 295     throw length_error("vector");
 296 #else
 297     assert(!"vector length_error");
 298 #endif
 299 }
 300
 301 template <bool __b>
 302 void
 303 __vector_base_common<__b>::__throw_out_of_range() const
 304 {
 305 #ifndef _LIBCPP_NO_EXCEPTIONS
 306     throw out_of_range("vector");
 307 #else
 308     assert(!"vector out_of_range");
 309 #endif
 310 }
 311
 312 #ifdef _MSC_VER
 313 #pragma warning( push )
 314 #pragma warning( disable: 4231 )
 315 #endif // _MSC_VER
 316 _LIBCPP_EXTERN_TEMPLATE(class __vector_base_common<true>)
 317 #ifdef _MSC_VER
 318 #pragma warning( pop )
 319 #endif // _MSC_VER
 320
 321 template <class _Tp, class _Allocator>
 322 class __vector_base
 323     : protected __vector_base_common<true>
 324 {
 325 protected:
 326     typedef _Tp                                      value_type;
 327     typedef _Allocator                               allocator_type;
 328     typedef allocator_traits<allocator_type>         __alloc_traits;
 329     typedef value_type&                              reference;
 330     typedef const value_type&                        const_reference;
 331     typedef typename __alloc_traits::size_type       size_type;
 332     typedef typename __alloc_traits::difference_type difference_type;
 333     typedef typename __alloc_traits::pointer         pointer;
 334     typedef typename __alloc_traits::const_pointer   const_pointer;
 335     typedef pointer                                  iterator;
 336     typedef const_pointer                            const_iterator;
 337
 338     pointer                                         __begin_;
 339     pointer                                         __end_;
 340     __compressed_pair<pointer, allocator_type> __end_cap_;
 341
 342     _LIBCPP_INLINE_VISIBILITY
 343     allocator_type& __alloc() _NOEXCEPT
 344         {return __end_cap_.second();}
 345     _LIBCPP_INLINE_VISIBILITY
 346     const allocator_type& __alloc() const _NOEXCEPT
 347         {return __end_cap_.second();}
 348     _LIBCPP_INLINE_VISIBILITY
 349     pointer& __end_cap() _NOEXCEPT
 350         {return __end_cap_.first();}
 351     _LIBCPP_INLINE_VISIBILITY
 352     const pointer& __end_cap() const _NOEXCEPT
 353         {return __end_cap_.first();}
 354
 355     _LIBCPP_INLINE_VISIBILITY
 356     __vector_base()
 357         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
 358     _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a);
 359     ~__vector_base();
 360
 361     _LIBCPP_INLINE_VISIBILITY
 362     void clear() _NOEXCEPT {__destruct_at_end(__begin_);}
 363     _LIBCPP_INLINE_VISIBILITY
 364     size_type capacity() const _NOEXCEPT
 365         {return static_cast<size_type>(__end_cap() - __begin_);}
 366
 367     _LIBCPP_INLINE_VISIBILITY
 368     void __destruct_at_end(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     __v.__end_++;
1463     __swap_out_circular_buffer(__v);
1464 }
1465
1466 template <class _Tp, class _Allocator>
1467 _LIBCPP_INLINE_VISIBILITY inline
1468 void
1469 vector<_Tp, _Allocator>::push_back(const_reference __x)
1470 {
1471     if (this->__end_ != this->__end_cap())
1472     {
1473         __alloc_traits::construct(this->__alloc(),
1474                                   _VSTD::__to_raw_pointer(this->__end_), __x);
1475         ++this->__end_;
1476     }
1477     else
1478         __push_back_slow_path(__x);
1479 }
1480
1481 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1482
1483 template <class _Tp, class _Allocator>
1484 _LIBCPP_INLINE_VISIBILITY inline
1485 void
1486 vector<_Tp, _Allocator>::push_back(value_type&& __x)
1487 {
1488     if (this->__end_ < this->__end_cap())
1489     {
1490         __alloc_traits::construct(this->__alloc(),
1491                                   _VSTD::__to_raw_pointer(this->__end_),
1492                                   _VSTD::move(__x));
1493         ++this->__end_;
1494     }
1495     else
1496         __push_back_slow_path(_VSTD::move(__x));
1497 }
1498
1499 #ifndef _LIBCPP_HAS_NO_VARIADICS
1500
1501 template <class _Tp, class _Allocator>
1502 template <class... _Args>
1503 void
1504 vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
1505 {
1506     allocator_type& __a = this->__alloc();
1507     __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
1508 //    __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1509     __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...);
1510     __v.__end_++;
1511     __swap_out_circular_buffer(__v);
1512 }
1513
1514 template <class _Tp, class _Allocator>
1515 template <class... _Args>
1516 _LIBCPP_INLINE_VISIBILITY inline
1517 void
1518 vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
1519 {
1520     if (this->__end_ < this->__end_cap())
1521     {
1522         __alloc_traits::construct(this->__alloc(),
1523                                   _VSTD::__to_raw_pointer(this->__end_),
1524                                   _VSTD::forward<_Args>(__args)...);
1525         ++this->__end_;
1526     }
1527     else
1528         __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
1529 }
1530
1531 #endif  // _LIBCPP_HAS_NO_VARIADICS
1532 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1533
1534 template <class _Tp, class _Allocator>
1535 _LIBCPP_INLINE_VISIBILITY inline
1536 void
1537 vector<_Tp, _Allocator>::pop_back()
1538 {
1539     _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector");
1540     this->__destruct_at_end(this->__end_ - 1);
1541 }
1542
1543 template <class _Tp, class _Allocator>
1544 _LIBCPP_INLINE_VISIBILITY inline
1545 typename vector<_Tp, _Allocator>::iterator
1546 vector<_Tp, _Allocator>::erase(const_iterator __position)
1547 {
1548 #if _LIBCPP_DEBUG_LEVEL >= 2
1549     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1550         "vector::erase(iterator) called with an iterator not"
1551         " referring to this vector");
1552 #endif
1553     pointer __p = const_cast<pointer>(&*__position);
1554     iterator __r = __make_iter(__p);
1555     this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
1556     return __r;
1557 }
1558
1559 template <class _Tp, class _Allocator>
1560 typename vector<_Tp, _Allocator>::iterator
1561 vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
1562 {
1563 #if _LIBCPP_DEBUG_LEVEL >= 2
1564     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this,
1565         "vector::erase(iterator,  iterator) called with an iterator not"
1566         " referring to this vector");
1567 #endif
1568     _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
1569     pointer __p = this->__begin_ + (__first - begin());
1570     iterator __r = __make_iter(__p);
1571     this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
1572     return __r;
1573 }
1574
1575 template <class _Tp, class _Allocator>
1576 void
1577 vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
1578 {
1579     pointer __old_last = this->__end_;
1580     difference_type __n = __old_last - __to;
1581     for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_)
1582         __alloc_traits::construct(this->__alloc(),
1583                                   _VSTD::__to_raw_pointer(this->__end_),
1584                                   _VSTD::move(*__i));
1585     _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
1586 }
1587
1588 template <class _Tp, class _Allocator>
1589 typename vector<_Tp, _Allocator>::iterator
1590 vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
1591 {
1592 #if _LIBCPP_DEBUG_LEVEL >= 2
1593     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1594         "vector::insert(iterator, x) called with an iterator not"
1595         " referring to this vector");
1596 #endif
1597     pointer __p = this->__begin_ + (__position - begin());
1598     if (this->__end_ < this->__end_cap())
1599     {
1600         if (__p == this->__end_)
1601         {
1602             __alloc_traits::construct(this->__alloc(),
1603                                       _VSTD::__to_raw_pointer(this->__end_), __x);
1604             ++this->__end_;
1605         }
1606         else
1607         {
1608             __move_range(__p, this->__end_, __p + 1);
1609             const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1610             if (__p <= __xr && __xr < this->__end_)
1611                 ++__xr;
1612             *__p = *__xr;
1613         }
1614     }
1615     else
1616     {
1617         allocator_type& __a = this->__alloc();
1618         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1619         __v.push_back(__x);
1620         __p = __swap_out_circular_buffer(__v, __p);
1621     }
1622     return __make_iter(__p);
1623 }
1624
1625 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1626
1627 template <class _Tp, class _Allocator>
1628 typename vector<_Tp, _Allocator>::iterator
1629 vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
1630 {
1631 #if _LIBCPP_DEBUG_LEVEL >= 2
1632     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1633         "vector::insert(iterator, x) called with an iterator not"
1634         " referring to this vector");
1635 #endif
1636     pointer __p = this->__begin_ + (__position - begin());
1637     if (this->__end_ < this->__end_cap())
1638     {
1639         if (__p == this->__end_)
1640         {
1641             __alloc_traits::construct(this->__alloc(),
1642                                       _VSTD::__to_raw_pointer(this->__end_),
1643                                       _VSTD::move(__x));
1644             ++this->__end_;
1645         }
1646         else
1647         {
1648             __move_range(__p, this->__end_, __p + 1);
1649             *__p = _VSTD::move(__x);
1650         }
1651     }
1652     else
1653     {
1654         allocator_type& __a = this->__alloc();
1655         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1656         __v.push_back(_VSTD::move(__x));
1657         __p = __swap_out_circular_buffer(__v, __p);
1658     }
1659     return __make_iter(__p);
1660 }
1661
1662 #ifndef _LIBCPP_HAS_NO_VARIADICS
1663
1664 template <class _Tp, class _Allocator>
1665 template <class... _Args>
1666 typename vector<_Tp, _Allocator>::iterator
1667 vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
1668 {
1669 #if _LIBCPP_DEBUG_LEVEL >= 2
1670     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1671         "vector::emplace(iterator, x) called with an iterator not"
1672         " referring to this vector");
1673 #endif
1674     pointer __p = this->__begin_ + (__position - begin());
1675     if (this->__end_ < this->__end_cap())
1676     {
1677         if (__p == this->__end_)
1678         {
1679             __alloc_traits::construct(this->__alloc(),
1680                                       _VSTD::__to_raw_pointer(this->__end_),
1681                                       _VSTD::forward<_Args>(__args)...);
1682             ++this->__end_;
1683         }
1684         else
1685         {
1686             value_type __tmp(_VSTD::forward<_Args>(__args)...);
1687             __move_range(__p, this->__end_, __p + 1);
1688             *__p = _VSTD::move(__tmp);
1689         }
1690     }
1691     else
1692     {
1693         allocator_type& __a = this->__alloc();
1694         __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
1695         __v.emplace_back(_VSTD::forward<_Args>(__args)...);
1696         __p = __swap_out_circular_buffer(__v, __p);
1697     }
1698     return __make_iter(__p);
1699 }
1700
1701 #endif  // _LIBCPP_HAS_NO_VARIADICS
1702 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1703
1704 template <class _Tp, class _Allocator>
1705 typename vector<_Tp, _Allocator>::iterator
1706 vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
1707 {
1708 #if _LIBCPP_DEBUG_LEVEL >= 2
1709     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1710         "vector::insert(iterator, n, x) called with an iterator not"
1711         " referring to this vector");
1712 #endif
1713     pointer __p = this->__begin_ + (__position - begin());
1714     if (__n > 0)
1715     {
1716         if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
1717         {
1718             size_type __old_n = __n;
1719             pointer __old_last = this->__end_;
1720             if (__n > static_cast<size_type>(this->__end_ - __p))
1721             {
1722                 size_type __cx = __n - (this->__end_ - __p);
1723                 __construct_at_end(__cx, __x);
1724                 __n -= __cx;
1725             }
1726             if (__n > 0)
1727             {
1728                 __move_range(__p, __old_last, __p + __old_n);
1729                 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
1730                 if (__p <= __xr && __xr < this->__end_)
1731                     __xr += __old_n;
1732                 _VSTD::fill_n(__p, __n, *__xr);
1733             }
1734         }
1735         else
1736         {
1737             allocator_type& __a = this->__alloc();
1738             __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1739             __v.__construct_at_end(__n, __x);
1740             __p = __swap_out_circular_buffer(__v, __p);
1741         }
1742     }
1743     return __make_iter(__p);
1744 }
1745
1746 template <class _Tp, class _Allocator>
1747 template <class _InputIterator>
1748 typename enable_if
1749 <
1750      __is_input_iterator  <_InputIterator>::value &&
1751     !__is_forward_iterator<_InputIterator>::value,
1752     typename vector<_Tp, _Allocator>::iterator
1753 >::type
1754 vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
1755 {
1756 #if _LIBCPP_DEBUG_LEVEL >= 2
1757     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1758         "vector::insert(iterator, range) called with an iterator not"
1759         " referring to this vector");
1760 #endif
1761     difference_type __off = __position - begin();
1762     pointer __p = this->__begin_ + __off;
1763     allocator_type& __a = this->__alloc();
1764     pointer __old_last = this->__end_;
1765     for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
1766     {
1767         __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_),
1768                                   *__first);
1769         ++this->__end_;
1770     }
1771     __split_buffer<value_type, allocator_type&> __v(__a);
1772     if (__first != __last)
1773     {
1774 #ifndef _LIBCPP_NO_EXCEPTIONS
1775         try
1776         {
1777 #endif  // _LIBCPP_NO_EXCEPTIONS
1778             __v.__construct_at_end(__first, __last);
1779             difference_type __old_size = __old_last - this->__begin_;
1780             difference_type __old_p = __p - this->__begin_;
1781             reserve(__recommend(size() + __v.size()));
1782             __p = this->__begin_ + __old_p;
1783             __old_last = this->__begin_ + __old_size;
1784 #ifndef _LIBCPP_NO_EXCEPTIONS
1785         }
1786         catch (...)
1787         {
1788             erase(__make_iter(__old_last), end());
1789             throw;
1790         }
1791 #endif  // _LIBCPP_NO_EXCEPTIONS
1792     }
1793     __p = _VSTD::rotate(__p, __old_last, this->__end_);
1794     insert(__make_iter(__p), make_move_iterator(__v.begin()),
1795                                     make_move_iterator(__v.end()));
1796     return begin() + __off;
1797 }
1798
1799 template <class _Tp, class _Allocator>
1800 template <class _ForwardIterator>
1801 typename enable_if
1802 <
1803     __is_forward_iterator<_ForwardIterator>::value,
1804     typename vector<_Tp, _Allocator>::iterator
1805 >::type
1806 vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
1807 {
1808 #if _LIBCPP_DEBUG_LEVEL >= 2
1809     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this,
1810         "vector::insert(iterator, range) called with an iterator not"
1811         " referring to this vector");
1812 #endif
1813     pointer __p = this->__begin_ + (__position - begin());
1814     difference_type __n = _VSTD::distance(__first, __last);
1815     if (__n > 0)
1816     {
1817         if (__n <= this->__end_cap() - this->__end_)
1818         {
1819             size_type __old_n = __n;
1820             pointer __old_last = this->__end_;
1821             _ForwardIterator __m = __last;
1822             difference_type __dx = this->__end_ - __p;
1823             if (__n > __dx)
1824             {
1825                 __m = __first;
1826                 _VSTD::advance(__m, this->__end_ - __p);
1827                 __construct_at_end(__m, __last);
1828                 __n = __dx;
1829             }
1830             if (__n > 0)
1831             {
1832                 __move_range(__p, __old_last, __p + __old_n);
1833                 _VSTD::copy(__first, __m, __p);
1834             }
1835         }
1836         else
1837         {
1838             allocator_type& __a = this->__alloc();
1839             __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
1840             __v.__construct_at_end(__first, __last);
1841             __p = __swap_out_circular_buffer(__v, __p);
1842         }
1843     }
1844     return __make_iter(__p);
1845 }
1846
1847 template <class _Tp, class _Allocator>
1848 void
1849 vector<_Tp, _Allocator>::resize(size_type __sz)
1850 {
1851     size_type __cs = size();
1852     if (__cs < __sz)
1853         this->__append(__sz - __cs);
1854     else if (__cs > __sz)
1855         this->__destruct_at_end(this->__begin_ + __sz);
1856 }
1857
1858 template <class _Tp, class _Allocator>
1859 void
1860 vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
1861 {
1862     size_type __cs = size();
1863     if (__cs < __sz)
1864         this->__append(__sz - __cs, __x);
1865     else if (__cs > __sz)
1866         this->__destruct_at_end(this->__begin_ + __sz);
1867 }
1868
1869 template <class _Tp, class _Allocator>
1870 void
1871 vector<_Tp, _Allocator>::swap(vector& __x)
1872         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1873                    __is_nothrow_swappable<allocator_type>::value)
1874 {
1875     _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
1876                    this->__alloc() == __x.__alloc(),
1877                    "vector::swap: Either propagate_on_container_swap must be true"
1878                    " or the allocators must compare equal");
1879     _VSTD::swap(this->__begin_, __x.__begin_);
1880     _VSTD::swap(this->__end_, __x.__end_);
1881     _VSTD::swap(this->__end_cap(), __x.__end_cap());
1882     __base::__swap_alloc(this->__alloc(), __x.__alloc());
1883 #if _LIBCPP_DEBUG_LEVEL >= 2
1884     __get_db()->swap(this, &__x);
1885 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1886 }
1887
1888 template <class _Tp, class _Allocator>
1889 bool
1890 vector<_Tp, _Allocator>::__invariants() const
1891 {
1892     if (this->__begin_ == 0)
1893     {
1894         if (this->__end_ != 0 || this->__end_cap() != 0)
1895             return false;
1896     }
1897     else
1898     {
1899         if (this->__begin_ > this->__end_)
1900             return false;
1901         if (this->__begin_ == this->__end_cap())
1902             return false;
1903         if (this->__end_ > this->__end_cap())
1904             return false;
1905     }
1906     return true;
1907 }
1908
1909 #if _LIBCPP_DEBUG_LEVEL >= 2
1910
1911 template <class _Tp, class _Allocator>
1912 bool
1913 vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
1914 {
1915     return this->__begin_ <= __i->base() && __i->base() < this->__end_;
1916 }
1917
1918 template <class _Tp, class _Allocator>
1919 bool
1920 vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
1921 {
1922     return this->__begin_ < __i->base() && __i->base() <= this->__end_;
1923 }
1924
1925 template <class _Tp, class _Allocator>
1926 bool
1927 vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
1928 {
1929     const_pointer __p = __i->base() + __n;
1930     return this->__begin_ <= __p && __p <= this->__end_;
1931 }
1932
1933 template <class _Tp, class _Allocator>
1934 bool
1935 vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
1936 {
1937     const_pointer __p = __i->base() + __n;
1938     return this->__begin_ <= __p && __p < this->__end_;
1939 }
1940
1941 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1942
1943 template <class _Tp, class _Allocator>
1944 _LIBCPP_INLINE_VISIBILITY inline
1945 void
1946 vector<_Tp, _Allocator>::__invalidate_all_iterators()
1947 {
1948 #if _LIBCPP_DEBUG_LEVEL >= 2
1949     __get_db()->__invalidate_all(this);
1950 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
1951 }
1952
1953 // vector<bool>
1954
1955 template <class _Allocator> class vector<bool, _Allocator>;
1956
1957 template <class _Allocator> struct hash<vector<bool, _Allocator> >;
1958
1959 template <class _Allocator>
1960 struct __has_storage_type<vector<bool, _Allocator> >
1961 {
1962     static const bool value = true;
1963 };
1964
1965 template <class _Allocator>
1966 class _LIBCPP_VISIBLE vector<bool, _Allocator>
1967     : private __vector_base_common<true>
1968 {
1969 public:
1970     typedef vector                                   __self;
1971     typedef bool                                     value_type;
1972     typedef _Allocator                               allocator_type;
1973     typedef allocator_traits<allocator_type>         __alloc_traits;
1974     typedef typename __alloc_traits::size_type       size_type;
1975     typedef typename __alloc_traits::difference_type difference_type;
1976     typedef size_type __storage_type;
1977     typedef __bit_iterator<vector, false>            pointer;
1978     typedef __bit_iterator<vector, true>             const_pointer;
1979 #ifdef _LIBCPP_DEBUG
1980     typedef __debug_iter<vector, pointer>            iterator;
1981     typedef __debug_iter<vector, const_pointer>      const_iterator;
1982
1983     friend class __debug_iter<vector, pointer>;
1984     friend class __debug_iter<vector, const_pointer>;
1985
1986     pair<iterator*, const_iterator*> __iterator_list_;
1987
1988     _LIBCPP_INLINE_VISIBILITY iterator*&       __get_iterator_list(iterator*)       {return __iterator_list_.first;}
1989     _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;}
1990 #else  // _LIBCPP_DEBUG
1991     typedef pointer                                  iterator;
1992     typedef const_pointer                            const_iterator;
1993 #endif  // _LIBCPP_DEBUG
1994     typedef _VSTD::reverse_iterator<iterator>         reverse_iterator;
1995     typedef _VSTD::reverse_iterator<const_iterator>   const_reverse_iterator;
1996
1997 private:
1998     typedef typename __alloc_traits::template
1999 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
2000                 rebind_alloc<__storage_type>
2001 #else
2002                 rebind_alloc<__storage_type>::other
2003 #endif
2004                                                      __storage_allocator;
2005     typedef allocator_traits<__storage_allocator>    __storage_traits;
2006     typedef typename __storage_traits::pointer       __storage_pointer;
2007     typedef typename __storage_traits::const_pointer __const_storage_pointer;
2008
2009     __storage_pointer                                      __begin_;
2010     size_type                                              __size_;
2011     __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
2012 public:
2013     typedef __bit_reference<vector>                  reference;
2014     typedef __bit_const_reference<vector>            const_reference;
2015 private:
2016     _LIBCPP_INLINE_VISIBILITY
2017     size_type& __cap() _NOEXCEPT
2018         {return __cap_alloc_.first();}
2019     _LIBCPP_INLINE_VISIBILITY
2020     const size_type& __cap() const _NOEXCEPT
2021         {return __cap_alloc_.first();}
2022     _LIBCPP_INLINE_VISIBILITY
2023     __storage_allocator& __alloc() _NOEXCEPT
2024         {return __cap_alloc_.second();}
2025     _LIBCPP_INLINE_VISIBILITY
2026     const __storage_allocator& __alloc() const _NOEXCEPT
2027         {return __cap_alloc_.second();}
2028
2029     static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
2030
2031     _LIBCPP_INLINE_VISIBILITY
2032     static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
2033         {return __n * __bits_per_word;}
2034     _LIBCPP_INLINE_VISIBILITY
2035     static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
2036         {return (__n - 1) / __bits_per_word + 1;}
2037
2038 public:
2039     _LIBCPP_INLINE_VISIBILITY
2040     vector()
2041         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
2042     _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a);
2043     ~vector();
2044     explicit vector(size_type __n);
2045     vector(size_type __n, const value_type& __v);
2046     vector(size_type __n, const value_type& __v, const allocator_type& __a);
2047     template <class _InputIterator>
2048         vector(_InputIterator __first, _InputIterator __last,
2049                typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2050                                  !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2051     template <class _InputIterator>
2052         vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2053                typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2054                                  !__is_forward_iterator<_InputIterator>::value>::type* = 0);
2055     template <class _ForwardIterator>
2056         vector(_ForwardIterator __first, _ForwardIterator __last,
2057                typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2058     template <class _ForwardIterator>
2059         vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2060                typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0);
2061
2062     vector(const vector& __v);
2063     vector(const vector& __v, const allocator_type& __a);
2064     vector& operator=(const vector& __v);
2065 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2066     vector(initializer_list<value_type> __il);
2067     vector(initializer_list<value_type> __il, const allocator_type& __a);
2068 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2069
2070 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2071     _LIBCPP_INLINE_VISIBILITY
2072     vector(vector&& __v)
2073         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
2074     vector(vector&& __v, const allocator_type& __a);
2075     _LIBCPP_INLINE_VISIBILITY
2076     vector& operator=(vector&& __v)
2077         _NOEXCEPT_(
2078              __alloc_traits::propagate_on_container_move_assignment::value &&
2079              is_nothrow_move_assignable<allocator_type>::value);
2080 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2081 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2082     _LIBCPP_INLINE_VISIBILITY
2083     vector& operator=(initializer_list<value_type> __il)
2084         {assign(__il.begin(), __il.end()); return *this;}
2085 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2086
2087     template <class _InputIterator>
2088         typename enable_if
2089         <
2090             __is_input_iterator<_InputIterator>::value &&
2091            !__is_forward_iterator<_InputIterator>::value,
2092            void
2093         >::type
2094         assign(_InputIterator __first, _InputIterator __last);
2095     template <class _ForwardIterator>
2096         typename enable_if
2097         <
2098             __is_forward_iterator<_ForwardIterator>::value,
2099            void
2100         >::type
2101         assign(_ForwardIterator __first, _ForwardIterator __last);
2102
2103     void assign(size_type __n, const value_type& __x);
2104 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2105     _LIBCPP_INLINE_VISIBILITY
2106     void assign(initializer_list<value_type> __il)
2107         {assign(__il.begin(), __il.end());}
2108 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2109
2110     _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
2111         {return allocator_type(this->__alloc());}
2112
2113     size_type max_size() const _NOEXCEPT;
2114     _LIBCPP_INLINE_VISIBILITY
2115     size_type capacity() const _NOEXCEPT
2116         {return __internal_cap_to_external(__cap());}
2117     _LIBCPP_INLINE_VISIBILITY
2118     size_type size() const _NOEXCEPT
2119         {return __size_;}
2120     _LIBCPP_INLINE_VISIBILITY
2121     bool empty() const _NOEXCEPT
2122         {return __size_ == 0;}
2123     void reserve(size_type __n);
2124     void shrink_to_fit() _NOEXCEPT;
2125
2126     _LIBCPP_INLINE_VISIBILITY
2127     iterator begin() _NOEXCEPT
2128         {return __make_iter(0);}
2129     _LIBCPP_INLINE_VISIBILITY
2130     const_iterator begin() const _NOEXCEPT
2131         {return __make_iter(0);}
2132     _LIBCPP_INLINE_VISIBILITY
2133     iterator end() _NOEXCEPT
2134         {return __make_iter(__size_);}
2135     _LIBCPP_INLINE_VISIBILITY
2136     const_iterator end()   const _NOEXCEPT
2137         {return __make_iter(__size_);}
2138
2139     _LIBCPP_INLINE_VISIBILITY
2140     reverse_iterator rbegin() _NOEXCEPT
2141         {return       reverse_iterator(end());}
2142     _LIBCPP_INLINE_VISIBILITY
2143     const_reverse_iterator rbegin() const _NOEXCEPT
2144         {return const_reverse_iterator(end());}
2145     _LIBCPP_INLINE_VISIBILITY
2146     reverse_iterator rend() _NOEXCEPT
2147         {return       reverse_iterator(begin());}
2148     _LIBCPP_INLINE_VISIBILITY
2149     const_reverse_iterator rend()   const _NOEXCEPT
2150         {return const_reverse_iterator(begin());}
2151
2152     _LIBCPP_INLINE_VISIBILITY
2153     const_iterator         cbegin()  const _NOEXCEPT
2154         {return __make_iter(0);}
2155     _LIBCPP_INLINE_VISIBILITY
2156     const_iterator         cend()    const _NOEXCEPT
2157         {return __make_iter(__size_);}
2158     _LIBCPP_INLINE_VISIBILITY
2159     const_reverse_iterator crbegin() const _NOEXCEPT
2160         {return rbegin();}
2161     _LIBCPP_INLINE_VISIBILITY
2162     const_reverse_iterator crend()   const _NOEXCEPT
2163         {return rend();}
2164
2165     _LIBCPP_INLINE_VISIBILITY reference       operator[](size_type __n)       {return __make_ref(__n);}
2166     _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
2167     reference       at(size_type __n);
2168     const_reference at(size_type __n) const;
2169
2170     _LIBCPP_INLINE_VISIBILITY reference       front()       {return __make_ref(0);}
2171     _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
2172     _LIBCPP_INLINE_VISIBILITY reference       back()        {return __make_ref(__size_ - 1);}
2173     _LIBCPP_INLINE_VISIBILITY const_reference back()  const {return __make_ref(__size_ - 1);}
2174
2175     void push_back(const value_type& __x);
2176     _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
2177
2178     iterator insert(const_iterator __position, const value_type& __x);
2179     iterator insert(const_iterator __position, size_type __n, const value_type& __x);
2180     iterator insert(const_iterator __position, size_type __n, const_reference __x);
2181     template <class _InputIterator>
2182         typename enable_if
2183         <
2184              __is_input_iterator  <_InputIterator>::value &&
2185             !__is_forward_iterator<_InputIterator>::value,
2186             iterator
2187         >::type
2188         insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
2189     template <class _ForwardIterator>
2190         typename enable_if
2191         <
2192             __is_forward_iterator<_ForwardIterator>::value,
2193             iterator
2194         >::type
2195         insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
2196 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2197     _LIBCPP_INLINE_VISIBILITY
2198     iterator insert(const_iterator __position, initializer_list<value_type> __il)
2199         {return insert(__position, __il.begin(), __il.end());}
2200 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2201
2202     _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
2203     iterator erase(const_iterator __first, const_iterator __last);
2204
2205     _LIBCPP_INLINE_VISIBILITY
2206     void clear() _NOEXCEPT {__size_ = 0;}
2207
2208     void swap(vector&)
2209         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
2210                    __is_nothrow_swappable<allocator_type>::value);
2211
2212     void resize(size_type __sz, value_type __x = false);
2213     void flip() _NOEXCEPT;
2214
2215     bool __invariants() const;
2216
2217 private:
2218     _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
2219     void allocate(size_type __n);
2220     void deallocate() _NOEXCEPT;
2221     _LIBCPP_INLINE_VISIBILITY
2222     static size_type __align(size_type __new_size) _NOEXCEPT
2223         {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);};
2224     _LIBCPP_INLINE_VISIBILITY  size_type __recommend(size_type __new_size) const;
2225     _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
2226     template <class _ForwardIterator>
2227         typename enable_if
2228         <
2229             __is_forward_iterator<_ForwardIterator>::value,
2230             void
2231         >::type
2232         __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
2233     void __append(size_type __n, const_reference __x);
2234     _LIBCPP_INLINE_VISIBILITY
2235     reference __make_ref(size_type __pos) _NOEXCEPT
2236         {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2237     _LIBCPP_INLINE_VISIBILITY
2238     const_reference __make_ref(size_type __pos) const _NOEXCEPT
2239         {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
2240 #ifdef _LIBCPP_DEBUG
2241     _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos)
2242         {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2243     _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const
2244         {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));}
2245     _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p)
2246         {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));}
2247 #else  // _LIBCPP_DEBUG
2248     _LIBCPP_INLINE_VISIBILITY
2249     iterator __make_iter(size_type __pos) _NOEXCEPT
2250         {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2251     _LIBCPP_INLINE_VISIBILITY
2252     const_iterator __make_iter(size_type __pos) const _NOEXCEPT
2253         {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
2254     _LIBCPP_INLINE_VISIBILITY
2255     iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
2256         {return iterator(const_cast<__storage_pointer>(__p.__seg_), __p.__ctz_);}
2257 #endif  // _LIBCPP_DEBUG
2258
2259     _LIBCPP_INLINE_VISIBILITY
2260     void __copy_assign_alloc(const vector& __v)
2261         {__copy_assign_alloc(__v, integral_constant<bool,
2262                       __storage_traits::propagate_on_container_copy_assignment::value>());}
2263     _LIBCPP_INLINE_VISIBILITY
2264     void __copy_assign_alloc(const vector& __c, true_type)
2265         {
2266             if (__alloc() != __c.__alloc())
2267                 deallocate();
2268             __alloc() = __c.__alloc();
2269         }
2270
2271     _LIBCPP_INLINE_VISIBILITY
2272     void __copy_assign_alloc(const vector&, false_type)
2273         {}
2274
2275     void __move_assign(vector& __c, false_type);
2276     void __move_assign(vector& __c, true_type)
2277         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
2278     _LIBCPP_INLINE_VISIBILITY
2279     void __move_assign_alloc(vector& __c)
2280         _NOEXCEPT_(
2281             !__storage_traits::propagate_on_container_move_assignment::value ||
2282             is_nothrow_move_assignable<allocator_type>::value)
2283         {__move_assign_alloc(__c, integral_constant<bool,
2284                       __storage_traits::propagate_on_container_move_assignment::value>());}
2285     _LIBCPP_INLINE_VISIBILITY
2286     void __move_assign_alloc(vector& __c, true_type)
2287         _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2288         {
2289             __alloc() = _VSTD::move(__c.__alloc());
2290         }
2291
2292     _LIBCPP_INLINE_VISIBILITY
2293     void __move_assign_alloc(vector&, false_type)
2294         _NOEXCEPT
2295         {}
2296
2297     _LIBCPP_INLINE_VISIBILITY
2298     static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y)
2299         _NOEXCEPT_(
2300             !__storage_traits::propagate_on_container_swap::value ||
2301             __is_nothrow_swappable<allocator_type>::value)
2302         {__swap_alloc(__x, __y, integral_constant<bool,
2303                       __storage_traits::propagate_on_container_swap::value>());}
2304
2305     _LIBCPP_INLINE_VISIBILITY
2306     static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type)
2307         _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
2308         {
2309             using _VSTD::swap;
2310             swap(__x, __y);
2311         }
2312     _LIBCPP_INLINE_VISIBILITY
2313     static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type)
2314         _NOEXCEPT
2315         {}
2316
2317     size_t __hash_code() const _NOEXCEPT;
2318
2319     friend class __bit_reference<vector>;
2320     friend class __bit_const_reference<vector>;
2321     friend class __bit_iterator<vector, false>;
2322     friend class __bit_iterator<vector, true>;
2323     friend struct __bit_array<vector>;
2324     friend struct _LIBCPP_VISIBLE hash<vector>;
2325 };
2326
2327 template <class _Allocator>
2328 #ifndef _LIBCPP_DEBUG
2329 _LIBCPP_INLINE_VISIBILITY inline
2330 #endif
2331 void
2332 vector<bool, _Allocator>::__invalidate_all_iterators()
2333 {
2334 #ifdef _LIBCPP_DEBUG
2335     iterator::__remove_all(this);
2336     const_iterator::__remove_all(this);
2337 #endif  // _LIBCPP_DEBUG
2338 }
2339
2340 //  Allocate space for __n objects
2341 //  throws length_error if __n > max_size()
2342 //  throws (probably bad_alloc) if memory run out
2343 //  Precondition:  __begin_ == __end_ == __cap() == 0
2344 //  Precondition:  __n > 0
2345 //  Postcondition:  capacity() == __n
2346 //  Postcondition:  size() == 0
2347 template <class _Allocator>
2348 void
2349 vector<bool, _Allocator>::allocate(size_type __n)
2350 {
2351     if (__n > max_size())
2352         this->__throw_length_error();
2353     __n = __external_cap_to_internal(__n);
2354     this->__begin_ = __storage_traits::allocate(this->__alloc(), __n);
2355     this->__size_ = 0;
2356     this->__cap() = __n;
2357 }
2358
2359 template <class _Allocator>
2360 void
2361 vector<bool, _Allocator>::deallocate() _NOEXCEPT
2362 {
2363     if (this->__begin_ != 0)
2364     {
2365         __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
2366         __invalidate_all_iterators();
2367         this->__begin_ = 0;
2368         this->__size_ = this->__cap() = 0;
2369     }
2370 }
2371
2372 template <class _Allocator>
2373 typename vector<bool, _Allocator>::size_type
2374 vector<bool, _Allocator>::max_size() const _NOEXCEPT
2375 {
2376     size_type __amax = __storage_traits::max_size(__alloc());
2377     size_type __nmax = numeric_limits<size_type>::max() / 2;  // end() >= begin(), always
2378     if (__nmax / __bits_per_word <= __amax)
2379         return __nmax;
2380     return __internal_cap_to_external(__amax);
2381 }
2382
2383 //  Precondition:  __new_size > capacity()
2384 template <class _Allocator>
2385 _LIBCPP_INLINE_VISIBILITY inline
2386 typename vector<bool, _Allocator>::size_type
2387 vector<bool, _Allocator>::__recommend(size_type __new_size) const
2388 {
2389     const size_type __ms = max_size();
2390     if (__new_size > __ms)
2391         this->__throw_length_error();
2392     const size_type __cap = capacity();
2393     if (__cap >= __ms / 2)
2394         return __ms;
2395     return _VSTD::max(2*__cap, __align(__new_size));
2396 }
2397
2398 //  Default constructs __n objects starting at __end_
2399 //  Precondition:  __n > 0
2400 //  Precondition:  size() + __n <= capacity()
2401 //  Postcondition:  size() == size() + __n
2402 template <class _Allocator>
2403 _LIBCPP_INLINE_VISIBILITY inline
2404 void
2405 vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
2406 {
2407     size_type __old_size = this->__size_;
2408     this->__size_ += __n;
2409     _VSTD::fill_n(__make_iter(__old_size), __n, __x);
2410 }
2411
2412 template <class _Allocator>
2413 template <class _ForwardIterator>
2414 typename enable_if
2415 <
2416     __is_forward_iterator<_ForwardIterator>::value,
2417     void
2418 >::type
2419 vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
2420 {
2421     size_type __old_size = this->__size_;
2422     this->__size_ += _VSTD::distance(__first, __last);
2423     _VSTD::copy(__first, __last, __make_iter(__old_size));
2424 }
2425
2426 template <class _Allocator>
2427 _LIBCPP_INLINE_VISIBILITY inline
2428 vector<bool, _Allocator>::vector()
2429         _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
2430     : __begin_(0),
2431       __size_(0),
2432       __cap_alloc_(0)
2433 {
2434 }
2435
2436 template <class _Allocator>
2437 _LIBCPP_INLINE_VISIBILITY inline
2438 vector<bool, _Allocator>::vector(const allocator_type& __a)
2439     : __begin_(0),
2440       __size_(0),
2441       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2442 {
2443 }
2444
2445 template <class _Allocator>
2446 vector<bool, _Allocator>::vector(size_type __n)
2447     : __begin_(0),
2448       __size_(0),
2449       __cap_alloc_(0)
2450 {
2451     if (__n > 0)
2452     {
2453         allocate(__n);
2454         __construct_at_end(__n, false);
2455     }
2456 }
2457
2458 template <class _Allocator>
2459 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
2460     : __begin_(0),
2461       __size_(0),
2462       __cap_alloc_(0)
2463 {
2464     if (__n > 0)
2465     {
2466         allocate(__n);
2467         __construct_at_end(__n, __x);
2468     }
2469 }
2470
2471 template <class _Allocator>
2472 vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
2473     : __begin_(0),
2474       __size_(0),
2475       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2476 {
2477     if (__n > 0)
2478     {
2479         allocate(__n);
2480         __construct_at_end(__n, __x);
2481     }
2482 }
2483
2484 template <class _Allocator>
2485 template <class _InputIterator>
2486 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
2487        typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2488                          !__is_forward_iterator<_InputIterator>::value>::type*)
2489     : __begin_(0),
2490       __size_(0),
2491       __cap_alloc_(0)
2492 {
2493 #ifndef _LIBCPP_NO_EXCEPTIONS
2494     try
2495     {
2496 #endif  // _LIBCPP_NO_EXCEPTIONS
2497         for (; __first != __last; ++__first)
2498             push_back(*__first);
2499 #ifndef _LIBCPP_NO_EXCEPTIONS
2500     }
2501     catch (...)
2502     {
2503         if (__begin_ != 0)
2504             __storage_traits::deallocate(__alloc(), __begin_, __cap());
2505         __invalidate_all_iterators();
2506         throw;
2507     }
2508 #endif  // _LIBCPP_NO_EXCEPTIONS
2509 }
2510
2511 template <class _Allocator>
2512 template <class _InputIterator>
2513 vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
2514        typename enable_if<__is_input_iterator  <_InputIterator>::value &&
2515                          !__is_forward_iterator<_InputIterator>::value>::type*)
2516     : __begin_(0),
2517       __size_(0),
2518       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2519 {
2520 #ifndef _LIBCPP_NO_EXCEPTIONS
2521     try
2522     {
2523 #endif  // _LIBCPP_NO_EXCEPTIONS
2524         for (; __first != __last; ++__first)
2525             push_back(*__first);
2526 #ifndef _LIBCPP_NO_EXCEPTIONS
2527     }
2528     catch (...)
2529     {
2530         if (__begin_ != 0)
2531             __storage_traits::deallocate(__alloc(), __begin_, __cap());
2532         __invalidate_all_iterators();
2533         throw;
2534     }
2535 #endif  // _LIBCPP_NO_EXCEPTIONS
2536 }
2537
2538 template <class _Allocator>
2539 template <class _ForwardIterator>
2540 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
2541                                 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2542     : __begin_(0),
2543       __size_(0),
2544       __cap_alloc_(0)
2545 {
2546     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2547     if (__n > 0)
2548     {
2549         allocate(__n);
2550         __construct_at_end(__first, __last);
2551     }
2552 }
2553
2554 template <class _Allocator>
2555 template <class _ForwardIterator>
2556 vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
2557                                 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*)
2558     : __begin_(0),
2559       __size_(0),
2560       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2561 {
2562     size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
2563     if (__n > 0)
2564     {
2565         allocate(__n);
2566         __construct_at_end(__first, __last);
2567     }
2568 }
2569
2570 #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2571
2572 template <class _Allocator>
2573 vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
2574     : __begin_(0),
2575       __size_(0),
2576       __cap_alloc_(0)
2577 {
2578     size_type __n = static_cast<size_type>(__il.size());
2579     if (__n > 0)
2580     {
2581         allocate(__n);
2582         __construct_at_end(__il.begin(), __il.end());
2583     }
2584 }
2585
2586 template <class _Allocator>
2587 vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
2588     : __begin_(0),
2589       __size_(0),
2590       __cap_alloc_(0, static_cast<__storage_allocator>(__a))
2591 {
2592     size_type __n = static_cast<size_type>(__il.size());
2593     if (__n > 0)
2594     {
2595         allocate(__n);
2596         __construct_at_end(__il.begin(), __il.end());
2597     }
2598 }
2599
2600 #endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
2601
2602 template <class _Allocator>
2603 vector<bool, _Allocator>::~vector()
2604 {
2605     if (__begin_ != 0)
2606         __storage_traits::deallocate(__alloc(), __begin_, __cap());
2607 #ifdef _LIBCPP_DEBUG
2608     __invalidate_all_iterators();
2609 #endif
2610 }
2611
2612 template <class _Allocator>
2613 vector<bool, _Allocator>::vector(const vector& __v)
2614     : __begin_(0),
2615       __size_(0),
2616       __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
2617 {
2618     if (__v.size() > 0)
2619     {
2620         allocate(__v.size());
2621         __construct_at_end(__v.begin(), __v.end());
2622     }
2623 }
2624
2625 template <class _Allocator>
2626 vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
2627     : __begin_(0),
2628       __size_(0),
2629       __cap_alloc_(0, __a)
2630 {
2631     if (__v.size() > 0)
2632     {
2633         allocate(__v.size());
2634         __construct_at_end(__v.begin(), __v.end());
2635     }
2636 }
2637
2638 template <class _Allocator>
2639 vector<bool, _Allocator>&
2640 vector<bool, _Allocator>::operator=(const vector& __v)
2641 {
2642     if (this != &__v)
2643     {
2644         __copy_assign_alloc(__v);
2645         if (__v.__size_)
2646         {
2647             if (__v.__size_ > capacity())
2648             {
2649                 deallocate();
2650                 allocate(__v.__size_);
2651             }
2652             _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
2653         }
2654         __size_ = __v.__size_;
2655     }
2656     return *this;
2657 }
2658
2659 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2660
2661 template <class _Allocator>
2662 _LIBCPP_INLINE_VISIBILITY inline
2663 vector<bool, _Allocator>::vector(vector&& __v)
2664         _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
2665     : __begin_(__v.__begin_),
2666       __size_(__v.__size_),
2667       __cap_alloc_(__v.__cap_alloc_)
2668 {
2669     __v.__begin_ = 0;
2670     __v.__size_ = 0;
2671     __v.__cap() = 0;
2672 }
2673
2674 template <class _Allocator>
2675 vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a)
2676     : __begin_(0),
2677       __size_(0),
2678       __cap_alloc_(0, __a)
2679 {
2680     if (__a == allocator_type(__v.__alloc()))
2681     {
2682         this->__begin_ = __v.__begin_;
2683         this->__size_ = __v.__size_;
2684         this->__cap() = __v.__cap();
2685         __v.__begin_ = nullptr;
2686         __v.__cap() = __v.__size_ = 0;
2687     }
2688     else if (__v.size() > 0)
2689     {
2690         allocate(__v.size());
2691         __construct_at_end(__v.begin(), __v.end());
2692     }
2693 }
2694
2695 template <class _Allocator>
2696 _LIBCPP_INLINE_VISIBILITY inline
2697 vector<bool, _Allocator>&
2698 vector<bool, _Allocator>::operator=(vector&& __v)
2699         _NOEXCEPT_(
2700              __alloc_traits::propagate_on_container_move_assignment::value &&
2701              is_nothrow_move_assignable<allocator_type>::value)
2702 {
2703     __move_assign(__v, integral_constant<bool,
2704           __storage_traits::propagate_on_container_move_assignment::value>());
2705     return *this;
2706 }
2707
2708 template <class _Allocator>
2709 void
2710 vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
2711 {
2712     if (__alloc() != __c.__alloc())
2713         assign(__c.begin(), __c.end());
2714     else
2715         __move_assign(__c, true_type());
2716 }
2717
2718 template <class _Allocator>
2719 void
2720 vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
2721     _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
2722 {
2723     deallocate();
2724     this->__begin_ = __c.__begin_;
2725     this->__size_ = __c.__size_;
2726     this->__cap() = __c.__cap();
2727     __move_assign_alloc(__c);
2728     __c.__begin_ = nullptr;
2729     __c.__cap() = __c.__size_ = 0;
2730 }
2731
2732 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
2733
2734 template <class _Allocator>
2735 void
2736 vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
2737 {
2738     __size_ = 0;
2739     if (__n > 0)
2740     {
2741         size_type __c = capacity();
2742         if (__n <= __c)
2743             __size_ = __n;
2744         else
2745         {
2746             vector __v(__alloc());
2747             __v.reserve(__recommend(__n));
2748             __v.__size_ = __n;
2749             swap(__v);
2750         }
2751         _VSTD::fill_n(begin(), __n, __x);
2752     }
2753 }
2754
2755 template <class _Allocator>
2756 template <class _InputIterator>
2757 typename enable_if
2758 <
2759     __is_input_iterator<_InputIterator>::value &&
2760    !__is_forward_iterator<_InputIterator>::value,
2761    void
2762 >::type
2763 vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2764 {
2765     clear();
2766     for (; __first != __last; ++__first)
2767         push_back(*__first);
2768 }
2769
2770 template <class _Allocator>
2771 template <class _ForwardIterator>
2772 typename enable_if
2773 <
2774     __is_forward_iterator<_ForwardIterator>::value,
2775    void
2776 >::type
2777 vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2778 {
2779     clear();
2780     difference_type __n = _VSTD::distance(__first, __last);
2781     if (__n)
2782     {
2783         if (__n > capacity())
2784         {
2785             deallocate();
2786             allocate(__n);
2787         }
2788         __construct_at_end(__first, __last);
2789     }
2790 }
2791
2792 template <class _Allocator>
2793 void
2794 vector<bool, _Allocator>::reserve(size_type __n)
2795 {
2796     if (__n > capacity())
2797     {
2798         vector __v(this->__alloc());
2799         __v.allocate(__n);
2800         __v.__construct_at_end(this->begin(), this->end());
2801         swap(__v);
2802         __invalidate_all_iterators();
2803     }
2804 }
2805
2806 template <class _Allocator>
2807 void
2808 vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
2809 {
2810     if (__external_cap_to_internal(size()) > __cap())
2811     {
2812 #ifndef _LIBCPP_NO_EXCEPTIONS
2813         try
2814         {
2815 #endif  // _LIBCPP_NO_EXCEPTIONS
2816             vector(*this, allocator_type(__alloc())).swap(*this);
2817 #ifndef _LIBCPP_NO_EXCEPTIONS
2818         }
2819         catch (...)
2820         {
2821         }
2822 #endif  // _LIBCPP_NO_EXCEPTIONS
2823     }
2824 }
2825
2826 template <class _Allocator>
2827 typename vector<bool, _Allocator>::reference
2828 vector<bool, _Allocator>::at(size_type __n)
2829 {
2830     if (__n >= size())
2831         this->__throw_out_of_range();
2832     return (*this)[__n];
2833 }
2834
2835 template <class _Allocator>
2836 typename vector<bool, _Allocator>::const_reference
2837 vector<bool, _Allocator>::at(size_type __n) const
2838 {
2839     if (__n >= size())
2840         this->__throw_out_of_range();
2841     return (*this)[__n];
2842 }
2843
2844 template <class _Allocator>
2845 void
2846 vector<bool, _Allocator>::push_back(const value_type& __x)
2847 {
2848     if (this->__size_ == this->capacity())
2849         reserve(__recommend(this->__size_ + 1));
2850     ++this->__size_;
2851     back() = __x;
2852 }
2853
2854 template <class _Allocator>
2855 typename vector<bool, _Allocator>::iterator
2856 vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
2857 {
2858     iterator __r;
2859     if (size() < capacity())
2860     {
2861         const_iterator __old_end = end();
2862         ++__size_;
2863         _VSTD::copy_backward(__position, __old_end, end());
2864         __r = __const_iterator_cast(__position);
2865     }
2866     else
2867     {
2868         vector __v(__alloc());
2869         __v.reserve(__recommend(__size_ + 1));
2870         __v.__size_ = __size_ + 1;
2871         __r = _VSTD::copy(cbegin(), __position, __v.begin());
2872         _VSTD::copy_backward(__position, cend(), __v.end());
2873         swap(__v);
2874     }
2875     *__r = __x;
2876     return __r;
2877 }
2878
2879 template <class _Allocator>
2880 typename vector<bool, _Allocator>::iterator
2881 vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
2882 {
2883     iterator __r;
2884     size_type __c = capacity();
2885     if (__n <= __c && size() <= __c - __n)
2886     {
2887         const_iterator __old_end = end();
2888         __size_ += __n;
2889         _VSTD::copy_backward(__position, __old_end, end());
2890         __r = __const_iterator_cast(__position);
2891     }
2892     else
2893     {
2894         vector __v(__alloc());
2895         __v.reserve(__recommend(__size_ + __n));
2896         __v.__size_ = __size_ + __n;
2897         __r = _VSTD::copy(cbegin(), __position, __v.begin());
2898         _VSTD::copy_backward(__position, cend(), __v.end());
2899         swap(__v);
2900     }
2901     _VSTD::fill_n(__r, __n, __x);
2902     return __r;
2903 }
2904
2905 template <class _Allocator>
2906 template <class _InputIterator>
2907 typename enable_if
2908 <
2909      __is_input_iterator  <_InputIterator>::value &&
2910     !__is_forward_iterator<_InputIterator>::value,
2911     typename vector<bool, _Allocator>::iterator
2912 >::type
2913 vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
2914 {
2915     difference_type __off = __position - begin();
2916     iterator __p = __const_iterator_cast(__position);
2917     iterator __old_end = end();
2918     for (; size() != capacity() && __first != __last; ++__first)
2919     {
2920         ++this->__size_;
2921         back() = *__first;
2922     }
2923     vector __v(__alloc());
2924     if (__first != __last)
2925     {
2926 #ifndef _LIBCPP_NO_EXCEPTIONS
2927         try
2928         {
2929 #endif  // _LIBCPP_NO_EXCEPTIONS
2930             __v.assign(__first, __last);
2931             difference_type __old_size = static_cast<difference_type>(__old_end - begin());
2932             difference_type __old_p = __p - begin();
2933             reserve(__recommend(size() + __v.size()));
2934             __p = begin() + __old_p;
2935             __old_end = begin() + __old_size;
2936 #ifndef _LIBCPP_NO_EXCEPTIONS
2937         }
2938         catch (...)
2939         {
2940             erase(__old_end, end());
2941             throw;
2942         }
2943 #endif  // _LIBCPP_NO_EXCEPTIONS
2944     }
2945     __p = _VSTD::rotate(__p, __old_end, end());
2946     insert(__p, __v.begin(), __v.end());
2947     return begin() + __off;
2948 }
2949
2950 template <class _Allocator>
2951 template <class _ForwardIterator>
2952 typename enable_if
2953 <
2954     __is_forward_iterator<_ForwardIterator>::value,
2955     typename vector<bool, _Allocator>::iterator
2956 >::type
2957 vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
2958 {
2959     difference_type __n = _VSTD::distance(__first, __last);
2960     iterator __r;
2961     size_type __c = capacity();
2962     if (__n <= __c && size() <= __c - __n)
2963     {
2964         const_iterator __old_end = end();
2965         __size_ += __n;
2966         _VSTD::copy_backward(__position, __old_end, end());
2967         __r = __const_iterator_cast(__position);
2968     }
2969     else
2970     {
2971         vector __v(__alloc());
2972         __v.reserve(__recommend(__size_ + __n));
2973         __v.__size_ = __size_ + __n;
2974         __r = _VSTD::copy(cbegin(), __position, __v.begin());
2975         _VSTD::copy_backward(__position, cend(), __v.end());
2976         swap(__v);
2977     }
2978     _VSTD::copy(__first, __last, __r);
2979     return __r;
2980 }
2981
2982 template <class _Allocator>
2983 _LIBCPP_INLINE_VISIBILITY inline
2984 typename vector<bool, _Allocator>::iterator
2985 vector<bool, _Allocator>::erase(const_iterator __position)
2986 {
2987     iterator __r = __const_iterator_cast(__position);
2988     _VSTD::copy(__position + 1, this->cend(), __r);
2989     --__size_;
2990     return __r;
2991 }
2992
2993 template <class _Allocator>
2994 typename vector<bool, _Allocator>::iterator
2995 vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
2996 {
2997     iterator __r = __const_iterator_cast(__first);
2998     difference_type __d = __last - __first;
2999     _VSTD::copy(__last, this->cend(), __r);
3000     __size_ -= __d;
3001     return __r;
3002 }
3003
3004 template <class _Allocator>
3005 void
3006 vector<bool, _Allocator>::swap(vector& __x)
3007         _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3008                    __is_nothrow_swappable<allocator_type>::value)
3009 {
3010     _VSTD::swap(this->__begin_, __x.__begin_);
3011     _VSTD::swap(this->__size_, __x.__size_);
3012     _VSTD::swap(this->__cap(), __x.__cap());
3013     __swap_alloc(this->__alloc(), __x.__alloc());
3014 #ifdef _LIBCPP_DEBUG
3015     iterator::swap(this, &__x);
3016     const_iterator::swap(this, &__x);
3017 #endif  // _LIBCPP_DEBUG
3018 }
3019
3020 template <class _Allocator>
3021 void
3022 vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
3023 {
3024     size_type __cs = size();
3025     if (__cs < __sz)
3026     {
3027         iterator __r;
3028         size_type __c = capacity();
3029         size_type __n = __sz - __cs;
3030         if (__n <= __c && __cs <= __c - __n)
3031         {
3032             __r = end();
3033             __size_ += __n;
3034         }
3035         else
3036         {
3037             vector __v(__alloc());
3038             __v.reserve(__recommend(__size_ + __n));
3039             __v.__size_ = __size_ + __n;
3040             __r = _VSTD::copy(cbegin(), cend(), __v.begin());
3041             swap(__v);
3042         }
3043         _VSTD::fill_n(__r, __n, __x);
3044     }
3045     else
3046         __size_ = __sz;
3047 }
3048
3049 template <class _Allocator>
3050 void
3051 vector<bool, _Allocator>::flip() _NOEXCEPT
3052 {
3053     // do middle whole words
3054     size_type __n = __size_;
3055     __storage_pointer __p = __begin_;
3056     for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3057         *__p = ~*__p;
3058     // do last partial word
3059     if (__n > 0)
3060     {
3061         __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3062         __storage_type __b = *__p & __m;
3063         *__p &= ~__m;
3064         *__p |= ~__b & __m;
3065     }
3066 }
3067
3068 template <class _Allocator>
3069 bool
3070 vector<bool, _Allocator>::__invariants() const
3071 {
3072     if (this->__begin_ == 0)
3073     {
3074         if (this->__size_ != 0 || this->__cap() != 0)
3075             return false;
3076     }
3077     else
3078     {
3079         if (this->__cap() == 0)
3080             return false;
3081         if (this->__size_ > this->capacity())
3082             return false;
3083     }
3084     return true;
3085 }
3086
3087 template <class _Allocator>
3088 size_t
3089 vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
3090 {
3091     size_t __h = 0;
3092     // do middle whole words
3093     size_type __n = __size_;
3094     __storage_pointer __p = __begin_;
3095     for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
3096         __h ^= *__p;
3097     // do last partial word
3098     if (__n > 0)
3099     {
3100         const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
3101         __h ^= *__p & __m;
3102     }
3103     return __h;
3104 }
3105
3106 template <class _Allocator>
3107 struct _LIBCPP_VISIBLE hash<vector<bool, _Allocator> >
3108     : public unary_function<vector<bool, _Allocator>, size_t>
3109 {
3110     _LIBCPP_INLINE_VISIBILITY
3111     size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
3112         {return __vec.__hash_code();}
3113 };
3114
3115 template <class _Tp, class _Allocator>
3116 _LIBCPP_INLINE_VISIBILITY inline
3117 bool
3118 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3119 {
3120     const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
3121     return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
3122 }
3123
3124 template <class _Tp, class _Allocator>
3125 _LIBCPP_INLINE_VISIBILITY inline
3126 bool
3127 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3128 {
3129     return !(__x == __y);
3130 }
3131
3132 template <class _Tp, class _Allocator>
3133 _LIBCPP_INLINE_VISIBILITY inline
3134 bool
3135 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3136 {
3137     return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
3138 }
3139
3140 template <class _Tp, class _Allocator>
3141 _LIBCPP_INLINE_VISIBILITY inline
3142 bool
3143 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3144 {
3145     return __y < __x;
3146 }
3147
3148 template <class _Tp, class _Allocator>
3149 _LIBCPP_INLINE_VISIBILITY inline
3150 bool
3151 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3152 {
3153     return !(__x < __y);
3154 }
3155
3156 template <class _Tp, class _Allocator>
3157 _LIBCPP_INLINE_VISIBILITY inline
3158 bool
3159 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
3160 {
3161     return !(__y < __x);
3162 }
3163
3164 template <class _Tp, class _Allocator>
3165 _LIBCPP_INLINE_VISIBILITY inline
3166 void
3167 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
3168     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
3169 {
3170     __x.swap(__y);
3171 }
3172
3173 _LIBCPP_END_NAMESPACE_STD
3174
3175 #endif  // _LIBCPP_VECTOR