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