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