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