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