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