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