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