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