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