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