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