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