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