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