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