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