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