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