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