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