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