vector revision 227983
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 17namespace std 18{ 19 20template <class T, class Allocator = allocator<T> > 21class vector 22{ 23public: 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 127template <class Allocator = allocator<T> > 128class vector<bool, Allocator> 129{ 130public: 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 243template <class Allocator> struct hash<std::vector<bool, Allocator>>; 244 245template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 246template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 247template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 248template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 249template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 250template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 251 252template <class T, class Allocator> 253void 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 279template <bool> 280class __vector_base_common 281{ 282protected: 283 _LIBCPP_ALWAYS_INLINE __vector_base_common() {} 284 void __throw_length_error() const; 285 void __throw_out_of_range() const; 286}; 287 288template <bool __b> 289void 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 299template <bool __b> 300void 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 314extern template class __vector_base_common<true>; 315#ifdef _MSC_VER 316#pragma warning( pop ) 317#endif // _MSC_VER 318 319template <class _Tp, class _Allocator> 320class __vector_base 321 : protected __vector_base_common<true> 322{ 323protected: 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>());} 393private: 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 435template <class _Tp, class _Allocator> 436_LIBCPP_INLINE_VISIBILITY inline 437void 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 444template <class _Tp, class _Allocator> 445_LIBCPP_INLINE_VISIBILITY inline 446void 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 452template <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 462template <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 471template <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 481template <class _Tp, class _Allocator = allocator<_Tp> > 482class _LIBCPP_VISIBLE vector 483 : private __vector_base<_Tp, _Allocator> 484{ 485private: 486 typedef __vector_base<_Tp, _Allocator> __base; 487public: 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 743private: 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 792template <class _Tp, class _Allocator> 793void 794vector<_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 805template <class _Tp, class _Allocator> 806typename vector<_Tp, _Allocator>::pointer 807vector<_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 829template <class _Tp, class _Allocator> 830void 831vector<_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 839template <class _Tp, class _Allocator> 840void 841vector<_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 851template <class _Tp, class _Allocator> 852typename vector<_Tp, _Allocator>::size_type 853vector<_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() 859template <class _Tp, class _Allocator> 860_LIBCPP_INLINE_VISIBILITY inline 861typename vector<_Tp, _Allocator>::size_type 862vector<_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 878template <class _Tp, class _Allocator> 879void 880vector<_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) 897template <class _Tp, class _Allocator> 898_LIBCPP_INLINE_VISIBILITY inline 899void 900vector<_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 911template <class _Tp, class _Allocator> 912template <class _ForwardIterator> 913typename enable_if 914< 915 __is_forward_iterator<_ForwardIterator>::value, 916 void 917>::type 918vector<_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 928template <class _Tp, class _Allocator> 929void 930vector<_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. 945template <class _Tp, class _Allocator> 946void 947vector<_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. 964template <class _Tp, class _Allocator> 965void 966vector<_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 979template <class _Tp, class _Allocator> 980vector<_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 992template <class _Tp, class _Allocator> 993vector<_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 1005template <class _Tp, class _Allocator> 1006vector<_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 1019template <class _Tp, class _Allocator> 1020template <class _InputIterator> 1021vector<_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 1032template <class _Tp, class _Allocator> 1033template <class _InputIterator> 1034vector<_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 1046template <class _Tp, class _Allocator> 1047template <class _ForwardIterator> 1048vector<_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 1062template <class _Tp, class _Allocator> 1063template <class _ForwardIterator> 1064vector<_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 1079template <class _Tp, class _Allocator> 1080vector<_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 1094template <class _Tp, class _Allocator> 1095vector<_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 1111template <class _Tp, class _Allocator> 1112_LIBCPP_INLINE_VISIBILITY inline 1113vector<_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 1127template <class _Tp, class _Allocator> 1128_LIBCPP_INLINE_VISIBILITY inline 1129vector<_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 1154template <class _Tp, class _Allocator> 1155_LIBCPP_INLINE_VISIBILITY inline 1156vector<_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 1168template <class _Tp, class _Allocator> 1169_LIBCPP_INLINE_VISIBILITY inline 1170vector<_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 1185template <class _Tp, class _Allocator> 1186_LIBCPP_INLINE_VISIBILITY inline 1187vector<_Tp, _Allocator>& 1188vector<_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 1198template <class _Tp, class _Allocator> 1199void 1200vector<_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 1211template <class _Tp, class _Allocator> 1212void 1213vector<_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 1229template <class _Tp, class _Allocator> 1230_LIBCPP_INLINE_VISIBILITY inline 1231vector<_Tp, _Allocator>& 1232vector<_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 1242template <class _Tp, class _Allocator> 1243template <class _InputIterator> 1244typename enable_if 1245< 1246 __is_input_iterator <_InputIterator>::value && 1247 !__is_forward_iterator<_InputIterator>::value, 1248 void 1249>::type 1250vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 1251{ 1252 clear(); 1253 for (; __first != __last; ++__first) 1254 push_back(*__first); 1255} 1256 1257template <class _Tp, class _Allocator> 1258template <class _ForwardIterator> 1259typename enable_if 1260< 1261 __is_forward_iterator<_ForwardIterator>::value, 1262 void 1263>::type 1264vector<_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 1291template <class _Tp, class _Allocator> 1292void 1293vector<_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 1312template <class _Tp, class _Allocator> 1313_LIBCPP_INLINE_VISIBILITY inline 1314typename vector<_Tp, _Allocator>::iterator 1315vector<_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 1324template <class _Tp, class _Allocator> 1325_LIBCPP_INLINE_VISIBILITY inline 1326typename vector<_Tp, _Allocator>::const_iterator 1327vector<_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 1336template <class _Tp, class _Allocator> 1337_LIBCPP_INLINE_VISIBILITY inline 1338typename vector<_Tp, _Allocator>::iterator 1339vector<_Tp, _Allocator>::begin() _NOEXCEPT 1340{ 1341 return __make_iter(this->__begin_); 1342} 1343 1344template <class _Tp, class _Allocator> 1345_LIBCPP_INLINE_VISIBILITY inline 1346typename vector<_Tp, _Allocator>::const_iterator 1347vector<_Tp, _Allocator>::begin() const _NOEXCEPT 1348{ 1349 return __make_iter(this->__begin_); 1350} 1351 1352template <class _Tp, class _Allocator> 1353_LIBCPP_INLINE_VISIBILITY inline 1354typename vector<_Tp, _Allocator>::iterator 1355vector<_Tp, _Allocator>::end() _NOEXCEPT 1356{ 1357 return __make_iter(this->__end_); 1358} 1359 1360template <class _Tp, class _Allocator> 1361_LIBCPP_INLINE_VISIBILITY inline 1362typename vector<_Tp, _Allocator>::const_iterator 1363vector<_Tp, _Allocator>::end() const _NOEXCEPT 1364{ 1365 return __make_iter(this->__end_); 1366} 1367 1368template <class _Tp, class _Allocator> 1369_LIBCPP_INLINE_VISIBILITY inline 1370typename vector<_Tp, _Allocator>::reference 1371vector<_Tp, _Allocator>::operator[](size_type __n) 1372{ 1373 _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1374 return this->__begin_[__n]; 1375} 1376 1377template <class _Tp, class _Allocator> 1378_LIBCPP_INLINE_VISIBILITY inline 1379typename vector<_Tp, _Allocator>::const_reference 1380vector<_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 1386template <class _Tp, class _Allocator> 1387typename vector<_Tp, _Allocator>::reference 1388vector<_Tp, _Allocator>::at(size_type __n) 1389{ 1390 if (__n >= size()) 1391 this->__throw_out_of_range(); 1392 return this->__begin_[__n]; 1393} 1394 1395template <class _Tp, class _Allocator> 1396typename vector<_Tp, _Allocator>::const_reference 1397vector<_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 1404template <class _Tp, class _Allocator> 1405void 1406vector<_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 1416template <class _Tp, class _Allocator> 1417void 1418vector<_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 1438template <class _Tp, class _Allocator> 1439void 1440vector<_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 1459template <class _Tp, class _Allocator> 1460void 1461vector<_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 1481template <class _Tp, class _Allocator> 1482template <class... _Args> 1483void 1484vector<_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 1505template <class _Tp, class _Allocator> 1506_LIBCPP_INLINE_VISIBILITY inline 1507void 1508vector<_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 1514template <class _Tp, class _Allocator> 1515_LIBCPP_INLINE_VISIBILITY inline 1516typename vector<_Tp, _Allocator>::iterator 1517vector<_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 1530template <class _Tp, class _Allocator> 1531typename vector<_Tp, _Allocator>::iterator 1532vector<_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 1546template <class _Tp, class _Allocator> 1547void 1548vector<_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 1559template <class _Tp, class _Allocator> 1560typename vector<_Tp, _Allocator>::iterator 1561vector<_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 1598template <class _Tp, class _Allocator> 1599typename vector<_Tp, _Allocator>::iterator 1600vector<_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 1635template <class _Tp, class _Allocator> 1636template <class... _Args> 1637typename vector<_Tp, _Allocator>::iterator 1638vector<_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 1674template <class _Tp, class _Allocator> 1675typename vector<_Tp, _Allocator>::iterator 1676vector<_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 1716template <class _Tp, class _Allocator> 1717template <class _InputIterator> 1718typename enable_if 1719< 1720 __is_input_iterator <_InputIterator>::value && 1721 !__is_forward_iterator<_InputIterator>::value, 1722 typename vector<_Tp, _Allocator>::iterator 1723>::type 1724vector<_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 1769template <class _Tp, class _Allocator> 1770template <class _ForwardIterator> 1771typename enable_if 1772< 1773 __is_forward_iterator<_ForwardIterator>::value, 1774 typename vector<_Tp, _Allocator>::iterator 1775>::type 1776vector<_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 1817template <class _Tp, class _Allocator> 1818void 1819vector<_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 1828template <class _Tp, class _Allocator> 1829void 1830vector<_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 1839template <class _Tp, class _Allocator> 1840void 1841vector<_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 1858template <class _Tp, class _Allocator> 1859bool 1860vector<_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 1881template <class _Tp, class _Allocator> 1882bool 1883vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const 1884{ 1885 return this->__begin_ <= __i->base() && __i->base() < this->__end_; 1886} 1887 1888template <class _Tp, class _Allocator> 1889bool 1890vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const 1891{ 1892 return this->__begin_ < __i->base() && __i->base() <= this->__end_; 1893} 1894 1895template <class _Tp, class _Allocator> 1896bool 1897vector<_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 1903template <class _Tp, class _Allocator> 1904bool 1905vector<_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 1913template <class _Tp, class _Allocator> 1914_LIBCPP_INLINE_VISIBILITY inline 1915void 1916vector<_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 1925template <class _Allocator> class vector<bool, _Allocator>; 1926 1927template <class _Allocator> struct hash<vector<bool, _Allocator> >; 1928 1929template <class _Allocator> 1930struct __has_storage_type<vector<bool, _Allocator> > 1931{ 1932 static const bool value = true; 1933}; 1934 1935template <class _Allocator> 1936class _LIBCPP_VISIBLE vector<bool, _Allocator> 1937 : private __vector_base_common<true> 1938{ 1939public: 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 1966private: 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_; 1982public: 1983 typedef __bit_reference<vector> reference; 1984 typedef __bit_const_reference<vector> const_reference; 1985private: 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 2008public: 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 2187private: 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 2297template <class _Allocator> 2298#ifndef _LIBCPP_DEBUG 2299_LIBCPP_INLINE_VISIBILITY inline 2300#endif 2301void 2302vector<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 2317template <class _Allocator> 2318void 2319vector<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 2329template <class _Allocator> 2330void 2331vector<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 2342template <class _Allocator> 2343typename vector<bool, _Allocator>::size_type 2344vector<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() 2354template <class _Allocator> 2355_LIBCPP_INLINE_VISIBILITY inline 2356typename vector<bool, _Allocator>::size_type 2357vector<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 2372template <class _Allocator> 2373_LIBCPP_INLINE_VISIBILITY inline 2374void 2375vector<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 2382template <class _Allocator> 2383template <class _ForwardIterator> 2384typename enable_if 2385< 2386 __is_forward_iterator<_ForwardIterator>::value, 2387 void 2388>::type 2389vector<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 2396template <class _Allocator> 2397_LIBCPP_INLINE_VISIBILITY inline 2398vector<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 2406template <class _Allocator> 2407_LIBCPP_INLINE_VISIBILITY inline 2408vector<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 2415template <class _Allocator> 2416vector<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 2428template <class _Allocator> 2429vector<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 2441template <class _Allocator> 2442vector<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 2454template <class _Allocator> 2455template <class _InputIterator> 2456vector<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 2481template <class _Allocator> 2482template <class _InputIterator> 2483vector<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 2508template <class _Allocator> 2509template <class _ForwardIterator> 2510vector<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 2524template <class _Allocator> 2525template <class _ForwardIterator> 2526vector<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 2542template <class _Allocator> 2543vector<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 2556template <class _Allocator> 2557vector<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 2572template <class _Allocator> 2573vector<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 2582template <class _Allocator> 2583vector<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 2595template <class _Allocator> 2596vector<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 2608template <class _Allocator> 2609vector<bool, _Allocator>& 2610vector<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 2631template <class _Allocator> 2632_LIBCPP_INLINE_VISIBILITY inline 2633vector<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 2644template <class _Allocator> 2645vector<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 2665template <class _Allocator> 2666_LIBCPP_INLINE_VISIBILITY inline 2667vector<bool, _Allocator>& 2668vector<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 2677template <class _Allocator> 2678void 2679vector<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 2687template <class _Allocator> 2688void 2689vector<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 2703template <class _Allocator> 2704void 2705vector<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 2724template <class _Allocator> 2725template <class _InputIterator> 2726typename enable_if 2727< 2728 __is_input_iterator<_InputIterator>::value && 2729 !__is_forward_iterator<_InputIterator>::value, 2730 void 2731>::type 2732vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2733{ 2734 clear(); 2735 for (; __first != __last; ++__first) 2736 push_back(*__first); 2737} 2738 2739template <class _Allocator> 2740template <class _ForwardIterator> 2741typename enable_if 2742< 2743 __is_forward_iterator<_ForwardIterator>::value, 2744 void 2745>::type 2746vector<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 2761template <class _Allocator> 2762void 2763vector<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 2775template <class _Allocator> 2776void 2777vector<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 2795template <class _Allocator> 2796typename vector<bool, _Allocator>::reference 2797vector<bool, _Allocator>::at(size_type __n) 2798{ 2799 if (__n >= size()) 2800 this->__throw_out_of_range(); 2801 return (*this)[__n]; 2802} 2803 2804template <class _Allocator> 2805typename vector<bool, _Allocator>::const_reference 2806vector<bool, _Allocator>::at(size_type __n) const 2807{ 2808 if (__n >= size()) 2809 this->__throw_out_of_range(); 2810 return (*this)[__n]; 2811} 2812 2813template <class _Allocator> 2814void 2815vector<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 2823template <class _Allocator> 2824typename vector<bool, _Allocator>::iterator 2825vector<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 2848template <class _Allocator> 2849typename vector<bool, _Allocator>::iterator 2850vector<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 2874template <class _Allocator> 2875template <class _InputIterator> 2876typename enable_if 2877< 2878 __is_input_iterator <_InputIterator>::value && 2879 !__is_forward_iterator<_InputIterator>::value, 2880 typename vector<bool, _Allocator>::iterator 2881>::type 2882vector<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 2919template <class _Allocator> 2920template <class _ForwardIterator> 2921typename enable_if 2922< 2923 __is_forward_iterator<_ForwardIterator>::value, 2924 typename vector<bool, _Allocator>::iterator 2925>::type 2926vector<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 2951template <class _Allocator> 2952_LIBCPP_INLINE_VISIBILITY inline 2953typename vector<bool, _Allocator>::iterator 2954vector<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 2962template <class _Allocator> 2963typename vector<bool, _Allocator>::iterator 2964vector<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 2973template <class _Allocator> 2974void 2975vector<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 2989template <class _Allocator> 2990void 2991vector<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 3018template <class _Allocator> 3019void 3020vector<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 3037template <class _Allocator> 3038bool 3039vector<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 3056template <class _Allocator> 3057size_t 3058vector<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 3075template <class _Allocator> 3076struct _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 3084template <class _Tp, class _Allocator> 3085_LIBCPP_INLINE_VISIBILITY inline 3086bool 3087operator==(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 3093template <class _Tp, class _Allocator> 3094_LIBCPP_INLINE_VISIBILITY inline 3095bool 3096operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3097{ 3098 return !(__x == __y); 3099} 3100 3101template <class _Tp, class _Allocator> 3102_LIBCPP_INLINE_VISIBILITY inline 3103bool 3104operator< (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 3109template <class _Tp, class _Allocator> 3110_LIBCPP_INLINE_VISIBILITY inline 3111bool 3112operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3113{ 3114 return __y < __x; 3115} 3116 3117template <class _Tp, class _Allocator> 3118_LIBCPP_INLINE_VISIBILITY inline 3119bool 3120operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3121{ 3122 return !(__x < __y); 3123} 3124 3125template <class _Tp, class _Allocator> 3126_LIBCPP_INLINE_VISIBILITY inline 3127bool 3128operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3129{ 3130 return !(__y < __x); 3131} 3132 3133template <class _Tp, class _Allocator> 3134_LIBCPP_INLINE_VISIBILITY inline 3135void 3136swap(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 3145