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