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