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