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