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