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