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