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