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