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