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