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