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 explicit vector(const allocator_type& = allocator_type()); 38 explicit vector(size_type n); 39 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 40 template <class InputIterator> 41 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 42 vector(const vector& x); 43 vector(vector&& x); 44 vector(initializer_list<value_type> il); 45 vector(initializer_list<value_type> il, const allocator_type& a); 46 ~vector(); 47 vector& operator=(const vector& x); 48 vector& operator=(vector&& x); 49 vector& operator=(initializer_list<value_type> il); 50 template <class InputIterator> 51 void assign(InputIterator first, InputIterator last); 52 void assign(size_type n, const value_type& u); 53 void assign(initializer_list<value_type> il); 54 55 allocator_type get_allocator() const; 56 57 iterator begin(); 58 const_iterator begin() const; 59 iterator end(); 60 const_iterator end() const; 61 62 reverse_iterator rbegin(); 63 const_reverse_iterator rbegin() const; 64 reverse_iterator rend(); 65 const_reverse_iterator rend() const; 66 67 const_iterator cbegin() const; 68 const_iterator cend() const; 69 const_reverse_iterator crbegin() const; 70 const_reverse_iterator crend() const; 71 72 size_type size() const; 73 size_type max_size() const; 74 size_type capacity() const; 75 bool empty() const; 76 void reserve(size_type n); 77 void shrink_to_fit(); 78 79 reference operator[](size_type n); 80 const_reference operator[](size_type n) const; 81 reference at(size_type n); 82 const_reference at(size_type n) const; 83 84 reference front(); 85 const_reference front() const; 86 reference back(); 87 const_reference back() const; 88 89 value_type* data(); 90 const value_type* data() const; 91 92 void push_back(const value_type& x); 93 void push_back(value_type&& x); 94 template <class... Args> 95 void emplace_back(Args&&... args); 96 void pop_back(); 97 98 template <class... Args> iterator emplace(const_iterator position, Args&&... args); 99 iterator insert(const_iterator position, const value_type& x); 100 iterator insert(const_iterator position, value_type&& x); 101 iterator insert(const_iterator position, size_type n, const value_type& x); 102 template <class InputIterator> 103 iterator insert(const_iterator position, InputIterator first, InputIterator last); 104 iterator insert(const_iterator position, initializer_list<value_type> il); 105 106 iterator erase(const_iterator position); 107 iterator erase(const_iterator first, const_iterator last); 108 109 void clear(); 110 111 void resize(size_type sz); 112 void resize(size_type sz, const value_type& c); 113 114 void swap(vector&); 115 116 bool __invariants() const; 117}; 118 119template <class Allocator = allocator<T> > 120class vector<bool, Allocator> 121{ 122public: 123 typedef bool value_type; 124 typedef Allocator allocator_type; 125 typedef implementation-defined iterator; 126 typedef implementation-defined const_iterator; 127 typedef typename allocator_type::size_type size_type; 128 typedef typename allocator_type::difference_type difference_type; 129 typedef iterator pointer; 130 typedef const_iterator const_pointer; 131 typedef std::reverse_iterator<iterator> reverse_iterator; 132 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 133 134 class reference 135 { 136 public: 137 reference(const reference&); 138 operator bool() const; 139 reference& operator=(const bool x); 140 reference& operator=(const reference& x); 141 iterator operator&() const; 142 void flip(); 143 }; 144 145 class const_reference 146 { 147 public: 148 const_reference(const reference&); 149 operator bool() const; 150 const_iterator operator&() const; 151 }; 152 153 explicit vector(const allocator_type& = allocator_type()); 154 explicit vector(size_type n, const value_type& value = value_type(), const allocator_type& = allocator_type()); 155 template <class InputIterator> 156 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 157 vector(const vector& x); 158 vector(vector&& x); 159 vector(initializer_list<value_type> il); 160 vector(initializer_list<value_type> il, const allocator_type& a); 161 ~vector(); 162 vector& operator=(const vector& x); 163 vector& operator=(vector&& x); 164 vector& operator=(initializer_list<value_type> il); 165 template <class InputIterator> 166 void assign(InputIterator first, InputIterator last); 167 void assign(size_type n, const value_type& u); 168 void assign(initializer_list<value_type> il); 169 170 allocator_type get_allocator() const; 171 172 iterator begin(); 173 const_iterator begin() const; 174 iterator end(); 175 const_iterator end() const; 176 177 reverse_iterator rbegin(); 178 const_reverse_iterator rbegin() const; 179 reverse_iterator rend(); 180 const_reverse_iterator rend() const; 181 182 const_iterator cbegin() const; 183 const_iterator cend() const; 184 const_reverse_iterator crbegin() const; 185 const_reverse_iterator crend() const; 186 187 size_type size() const; 188 size_type max_size() const; 189 size_type capacity() const; 190 bool empty() const; 191 void reserve(size_type n); 192 void shrink_to_fit(); 193 194 reference operator[](size_type n); 195 const_reference operator[](size_type n) const; 196 reference at(size_type n); 197 const_reference at(size_type n) const; 198 199 reference front(); 200 const_reference front() const; 201 reference back(); 202 const_reference back() const; 203 204 void push_back(const value_type& x); 205 void pop_back(); 206 207 iterator insert(const_iterator position, const value_type& x); 208 iterator insert(const_iterator position, size_type n, const value_type& x); 209 template <class InputIterator> 210 iterator insert(const_iterator position, InputIterator first, InputIterator last); 211 iterator insert(const_iterator position, initializer_list<value_type> il); 212 213 iterator erase(const_iterator position); 214 iterator erase(const_iterator first, const_iterator last); 215 216 void clear(); 217 218 void resize(size_type sz); 219 void resize(size_type sz, value_type x); 220 221 void swap(vector&); 222 void flip(); 223 224 bool __invariants() const; 225}; 226 227template <class Allocator> struct hash<std::vector<bool, Allocator>>; 228 229template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 230template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 231template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 232template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 233template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 234template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 235 236template <class T, class Allocator> void swap(vector<T,Allocator>& x, vector<T,Allocator>& y); 237 238} // std 239 240*/ 241 242#include <__config> 243#include <__bit_reference> 244#include <type_traits> 245#include <climits> 246#include <limits> 247#include <initializer_list> 248#include <memory> 249#include <stdexcept> 250#include <algorithm> 251#include <cstring> 252#include <__split_buffer> 253#include <__functional_base> 254#if defined(_LIBCPP_DEBUG) || defined(_LIBCPP_NO_EXCEPTIONS) 255 #include <cassert> 256#endif 257 258#pragma GCC system_header 259 260_LIBCPP_BEGIN_NAMESPACE_STD 261 262template <bool> 263class __vector_base_common 264{ 265protected: 266 _LIBCPP_ALWAYS_INLINE __vector_base_common() {} 267 void __throw_length_error() const; 268 void __throw_out_of_range() const; 269}; 270 271template <bool __b> 272void 273__vector_base_common<__b>::__throw_length_error() const 274{ 275#ifndef _LIBCPP_NO_EXCEPTIONS 276 throw length_error("vector"); 277#else 278 assert(!"vector length_error"); 279#endif 280} 281 282template <bool __b> 283void 284__vector_base_common<__b>::__throw_out_of_range() const 285{ 286#ifndef _LIBCPP_NO_EXCEPTIONS 287 throw out_of_range("vector"); 288#else 289 assert(!"vector out_of_range"); 290#endif 291} 292 293extern template class __vector_base_common<true>; 294 295template <class _Tp, class _Allocator> 296class __vector_base 297 : protected __vector_base_common<true> 298{ 299protected: 300 typedef _Tp value_type; 301 typedef _Allocator allocator_type; 302 typedef allocator_traits<allocator_type> __alloc_traits; 303 typedef value_type& reference; 304 typedef const value_type& const_reference; 305 typedef typename __alloc_traits::size_type size_type; 306 typedef typename __alloc_traits::difference_type difference_type; 307 typedef typename __alloc_traits::pointer pointer; 308 typedef typename __alloc_traits::const_pointer const_pointer; 309 typedef pointer iterator; 310 typedef const_pointer const_iterator; 311 312 pointer __begin_; 313 pointer __end_; 314 __compressed_pair<pointer, allocator_type> __end_cap_; 315 316 _LIBCPP_INLINE_VISIBILITY allocator_type& __alloc() {return __end_cap_.second();} 317 _LIBCPP_INLINE_VISIBILITY const allocator_type& __alloc() const {return __end_cap_.second();} 318 _LIBCPP_INLINE_VISIBILITY pointer& __end_cap() {return __end_cap_.first();} 319 _LIBCPP_INLINE_VISIBILITY const pointer& __end_cap() const {return __end_cap_.first();} 320 321 _LIBCPP_INLINE_VISIBILITY __vector_base(); 322 _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a); 323 ~__vector_base(); 324 325 _LIBCPP_INLINE_VISIBILITY void clear() {__destruct_at_end(__begin_);} 326 _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return static_cast<size_type>(__end_cap() - __begin_);} 327 328 _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(const_pointer __new_last) 329 {__destruct_at_end(__new_last, is_trivially_destructible<value_type>());} 330 _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(const_pointer __new_last, false_type); 331 _LIBCPP_INLINE_VISIBILITY void __destruct_at_end(const_pointer __new_last, true_type); 332 333 _LIBCPP_INLINE_VISIBILITY 334 void __copy_assign_alloc(const __vector_base& __c) 335 {__copy_assign_alloc(__c, integral_constant<bool, 336 __alloc_traits::propagate_on_container_copy_assignment::value>());} 337 338 _LIBCPP_INLINE_VISIBILITY 339 void __move_assign_alloc(__vector_base& __c) 340 {__move_assign_alloc(__c, integral_constant<bool, 341 __alloc_traits::propagate_on_container_move_assignment::value>());} 342 343 _LIBCPP_INLINE_VISIBILITY 344 static void __swap_alloc(allocator_type& __x, allocator_type& __y) 345 {__swap_alloc(__x, __y, integral_constant<bool, 346 __alloc_traits::propagate_on_container_swap::value>());} 347private: 348 _LIBCPP_INLINE_VISIBILITY 349 void __copy_assign_alloc(const __vector_base& __c, true_type) 350 { 351 if (__alloc() != __c.__alloc()) 352 { 353 clear(); 354 __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 355 __begin_ = __end_ = __end_cap() = nullptr; 356 } 357 __alloc() = __c.__alloc(); 358 } 359 360 _LIBCPP_INLINE_VISIBILITY 361 void __copy_assign_alloc(const __vector_base& __c, false_type) 362 {} 363 364 _LIBCPP_INLINE_VISIBILITY 365 void __move_assign_alloc(const __vector_base& __c, true_type) 366 { 367 __alloc() = _STD::move(__c.__alloc()); 368 } 369 370 _LIBCPP_INLINE_VISIBILITY 371 void __move_assign_alloc(const __vector_base& __c, false_type) 372 {} 373 374 _LIBCPP_INLINE_VISIBILITY 375 static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type) 376 { 377 using _STD::swap; 378 swap(__x, __y); 379 } 380 _LIBCPP_INLINE_VISIBILITY 381 static void __swap_alloc(allocator_type& __x, allocator_type& __y, false_type) 382 {} 383}; 384 385template <class _Tp, class _Allocator> 386_LIBCPP_INLINE_VISIBILITY inline 387void 388__vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, false_type) 389{ 390 while (__new_last < __end_) 391 __alloc_traits::destroy(__alloc(), const_cast<pointer>(--__end_)); 392} 393 394template <class _Tp, class _Allocator> 395_LIBCPP_INLINE_VISIBILITY inline 396void 397__vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, true_type) 398{ 399 __end_ = const_cast<pointer>(__new_last); 400} 401 402template <class _Tp, class _Allocator> 403_LIBCPP_INLINE_VISIBILITY inline 404__vector_base<_Tp, _Allocator>::__vector_base() 405 : __begin_(0), 406 __end_(0), 407 __end_cap_(0) 408{ 409} 410 411template <class _Tp, class _Allocator> 412_LIBCPP_INLINE_VISIBILITY inline 413__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a) 414 : __begin_(0), 415 __end_(0), 416 __end_cap_(0, __a) 417{ 418} 419 420template <class _Tp, class _Allocator> 421__vector_base<_Tp, _Allocator>::~__vector_base() 422{ 423 if (__begin_ != 0) 424 { 425 clear(); 426 __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 427 } 428} 429 430template <class _Tp, class _Allocator = allocator<_Tp> > 431class _LIBCPP_VISIBLE vector 432 : private __vector_base<_Tp, _Allocator> 433{ 434private: 435 typedef __vector_base<_Tp, _Allocator> __base; 436public: 437 typedef vector __self; 438 typedef _Tp value_type; 439 typedef _Allocator allocator_type; 440 typedef typename __base::__alloc_traits __alloc_traits; 441 typedef typename __base::reference reference; 442 typedef typename __base::const_reference const_reference; 443 typedef typename __base::size_type size_type; 444 typedef typename __base::difference_type difference_type; 445 typedef typename __base::pointer pointer; 446 typedef typename __base::const_pointer const_pointer; 447#ifdef _LIBCPP_DEBUG 448 typedef __debug_iter<vector, pointer> iterator; 449 typedef __debug_iter<vector, const_pointer> const_iterator; 450 451 friend class __debug_iter<vector, pointer>; 452 friend class __debug_iter<vector, const_pointer>; 453 454 pair<iterator*, const_iterator*> __iterator_list_; 455 456 _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;} 457 _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;} 458#elif defined(_LIBCPP_RAW_ITERATORS) 459 typedef pointer iterator; 460 typedef const_pointer const_iterator; 461#else // defined(_LIBCPP_RAW_ITERATORS) 462 typedef __wrap_iter<pointer> iterator; 463 typedef __wrap_iter<const_pointer> const_iterator; 464#endif // defined(_LIBCPP_RAW_ITERATORS) 465 typedef _STD::reverse_iterator<iterator> reverse_iterator; 466 typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator; 467 468 _LIBCPP_INLINE_VISIBILITY vector() {} 469 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) : __base(__a) {} 470 explicit vector(size_type __n); 471 vector(size_type __n, const_reference __x); 472 vector(size_type __n, const_reference __x, const allocator_type& __a); 473 template <class _InputIterator> 474 vector(_InputIterator __first, _InputIterator __last, 475 typename enable_if<__is_input_iterator <_InputIterator>::value && 476 !__is_forward_iterator<_InputIterator>::value>::type* = 0); 477 template <class _InputIterator> 478 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 479 typename enable_if<__is_input_iterator <_InputIterator>::value && 480 !__is_forward_iterator<_InputIterator>::value>::type* = 0); 481 template <class _ForwardIterator> 482 vector(_ForwardIterator __first, _ForwardIterator __last, 483 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 484 template <class _ForwardIterator> 485 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 486 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 487 _LIBCPP_INLINE_VISIBILITY 488 vector(initializer_list<value_type> __il); 489 _LIBCPP_INLINE_VISIBILITY 490 vector(initializer_list<value_type> __il, const allocator_type& __a); 491#ifdef _LIBCPP_DEBUG 492 _LIBCPP_INLINE_VISIBILITY 493 ~vector() {__invalidate_all_iterators();} 494#endif 495 496 vector(const vector& __x); 497 vector(const vector& __x, const allocator_type& __a); 498 _LIBCPP_INLINE_VISIBILITY 499 vector& operator=(const vector& __x); 500#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 501 _LIBCPP_INLINE_VISIBILITY 502 vector(vector&& __x); 503 _LIBCPP_INLINE_VISIBILITY 504 vector(vector&& __x, const allocator_type& __a); 505 _LIBCPP_INLINE_VISIBILITY 506 vector& operator=(vector&& __x); 507#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 508 _LIBCPP_INLINE_VISIBILITY 509 vector& operator=(initializer_list<value_type> __il) 510 {assign(__il.begin(), __il.end()); return *this;} 511 512 template <class _InputIterator> 513 typename enable_if 514 < 515 __is_input_iterator <_InputIterator>::value && 516 !__is_forward_iterator<_InputIterator>::value, 517 void 518 >::type 519 assign(_InputIterator __first, _InputIterator __last); 520 template <class _ForwardIterator> 521 typename enable_if 522 < 523 __is_forward_iterator<_ForwardIterator>::value, 524 void 525 >::type 526 assign(_ForwardIterator __first, _ForwardIterator __last); 527 528 void assign(size_type __n, const_reference __u); 529 _LIBCPP_INLINE_VISIBILITY 530 void assign(initializer_list<value_type> __il) 531 {assign(__il.begin(), __il.end());} 532 533 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const {return this->__alloc();} 534 535 _LIBCPP_INLINE_VISIBILITY iterator begin(); 536 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const; 537 _LIBCPP_INLINE_VISIBILITY iterator end(); 538 _LIBCPP_INLINE_VISIBILITY const_iterator end() const; 539 540 _LIBCPP_INLINE_VISIBILITY reverse_iterator rbegin() {return reverse_iterator(end());} 541 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rbegin() const {return const_reverse_iterator(end());} 542 _LIBCPP_INLINE_VISIBILITY reverse_iterator rend() {return reverse_iterator(begin());} 543 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rend() const {return const_reverse_iterator(begin());} 544 545 _LIBCPP_INLINE_VISIBILITY const_iterator cbegin() const {return begin();} 546 _LIBCPP_INLINE_VISIBILITY const_iterator cend() const {return end();} 547 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crbegin() const {return rbegin();} 548 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crend() const {return rend();} 549 550 _LIBCPP_INLINE_VISIBILITY size_type size() const {return static_cast<size_type>(this->__end_ - this->__begin_);} 551 _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return __base::capacity();} 552 _LIBCPP_INLINE_VISIBILITY bool empty() const {return this->__begin_ == this->__end_;} 553 size_type max_size() const; 554 void reserve(size_type __n); 555 void shrink_to_fit(); 556 557 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); 558 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; 559 reference at(size_type __n); 560 const_reference at(size_type __n) const; 561 562 _LIBCPP_INLINE_VISIBILITY reference front() {return *this->__begin_;} 563 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return *this->__begin_;} 564 _LIBCPP_INLINE_VISIBILITY reference back() {return *(this->__end_ - 1);} 565 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return *(this->__end_ - 1);} 566 567 _LIBCPP_INLINE_VISIBILITY value_type* data() 568 {return _STD::__to_raw_pointer(this->__begin_);} 569 _LIBCPP_INLINE_VISIBILITY const value_type* data() const 570 {return _STD::__to_raw_pointer(this->__begin_);} 571 572 _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 573#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 574 void push_back(value_type&& __x); 575#ifndef _LIBCPP_HAS_NO_VARIADICS 576 template <class... _Args> 577 void emplace_back(_Args&&... __args); 578#endif // _LIBCPP_HAS_NO_VARIADICS 579#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 580 void pop_back(); 581 582 iterator insert(const_iterator __position, const_reference __x); 583#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 584 iterator insert(const_iterator __position, value_type&& __x); 585#ifndef _LIBCPP_HAS_NO_VARIADICS 586 template <class... _Args> 587 iterator emplace(const_iterator __position, _Args&&... __args); 588#endif // _LIBCPP_HAS_NO_VARIADICS 589#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 590 iterator insert(const_iterator __position, size_type __n, const_reference __x); 591 template <class _InputIterator> 592 typename enable_if 593 < 594 __is_input_iterator <_InputIterator>::value && 595 !__is_forward_iterator<_InputIterator>::value, 596 iterator 597 >::type 598 insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 599 template <class _ForwardIterator> 600 typename enable_if 601 < 602 __is_forward_iterator<_ForwardIterator>::value, 603 iterator 604 >::type 605 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 606 _LIBCPP_INLINE_VISIBILITY 607 iterator insert(const_iterator __position, initializer_list<value_type> __il) 608 {return insert(__position, __il.begin(), __il.end());} 609 610 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 611 iterator erase(const_iterator __first, const_iterator __last); 612 613 _LIBCPP_INLINE_VISIBILITY void clear() {__base::clear();} 614 615 void resize(size_type __sz); 616 void resize(size_type __sz, const_reference __x); 617 618 void swap(vector&); 619 620 bool __invariants() const; 621 622private: 623 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 624 void allocate(size_type __n); 625 void deallocate(); 626 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 627 void __construct_at_end(size_type __n); 628 void __construct_at_end(size_type __n, const_reference __x); 629 template <class _ForwardIterator> 630 typename enable_if 631 < 632 __is_forward_iterator<_ForwardIterator>::value, 633 void 634 >::type 635 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 636 void __move_construct_at_end(pointer __first, pointer __last); 637 void __append(size_type __n); 638 void __append(size_type __n, const_reference __x); 639 _LIBCPP_INLINE_VISIBILITY 640 iterator __make_iter(pointer __p); 641 _LIBCPP_INLINE_VISIBILITY 642 const_iterator __make_iter(const_pointer __p) const; 643 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); 644 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); 645 void __move_range(pointer __from_s, pointer __from_e, pointer __to); 646 void __move_assign(vector& __c, true_type); 647 void __move_assign(vector& __c, false_type); 648}; 649 650template <class _Tp, class _Allocator> 651void 652vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) 653{ 654 for (pointer __p = this->__end_; this->__begin_ < __p;) 655 __v.push_front(_STD::move(*--__p)); 656 _STD::swap(this->__begin_, __v.__begin_); 657 _STD::swap(this->__end_, __v.__end_); 658 _STD::swap(this->__end_cap(), __v.__end_cap()); 659 __v.__first_ = __v.__begin_; 660 __invalidate_all_iterators(); 661} 662 663template <class _Tp, class _Allocator> 664typename vector<_Tp, _Allocator>::pointer 665vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) 666{ 667 pointer __r = __v.__begin_; 668 for (pointer __i = __p; this->__begin_ < __i;) 669 __v.push_front(_STD::move(*--__i)); 670 for (pointer __i = __p; __i < this->__end_; ++__i) 671 __v.push_back(_STD::move(*__i)); 672 _STD::swap(this->__begin_, __v.__begin_); 673 _STD::swap(this->__end_, __v.__end_); 674 _STD::swap(this->__end_cap(), __v.__end_cap()); 675 __v.__first_ = __v.__begin_; 676 __invalidate_all_iterators(); 677 return __r; 678} 679 680// Allocate space for __n objects 681// throws length_error if __n > max_size() 682// throws (probably bad_alloc) if memory run out 683// Precondition: __begin_ == __end_ == __end_cap() == 0 684// Precondition: __n > 0 685// Postcondition: capacity() == __n 686// Postcondition: size() == 0 687template <class _Tp, class _Allocator> 688void 689vector<_Tp, _Allocator>::allocate(size_type __n) 690{ 691 if (__n > max_size()) 692 this->__throw_length_error(); 693 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); 694 this->__end_cap() = this->__begin_ + __n; 695} 696 697template <class _Tp, class _Allocator> 698void 699vector<_Tp, _Allocator>::deallocate() 700{ 701 if (this->__begin_ != 0) 702 { 703 clear(); 704 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); 705 __invalidate_all_iterators(); 706 this->__begin_ = this->__end_ = this->__end_cap() = 0; 707 } 708} 709 710template <class _Tp, class _Allocator> 711typename vector<_Tp, _Allocator>::size_type 712vector<_Tp, _Allocator>::max_size() const 713{ 714 return _STD::min(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always 715} 716 717// Precondition: __new_size > capacity() 718template <class _Tp, class _Allocator> 719_LIBCPP_INLINE_VISIBILITY inline 720typename vector<_Tp, _Allocator>::size_type 721vector<_Tp, _Allocator>::__recommend(size_type __new_size) const 722{ 723 const size_type __ms = max_size(); 724 if (__new_size > __ms) 725 this->__throw_length_error(); 726 const size_type __cap = capacity(); 727 if (__cap >= __ms / 2) 728 return __ms; 729 return _STD::max(2*__cap, __new_size); 730} 731 732// Default constructs __n objects starting at __end_ 733// throws if construction throws 734// Precondition: __n > 0 735// Precondition: size() + __n <= capacity() 736// Postcondition: size() == size() + __n 737template <class _Tp, class _Allocator> 738void 739vector<_Tp, _Allocator>::__construct_at_end(size_type __n) 740{ 741 allocator_type& __a = this->__alloc(); 742 do 743 { 744 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_)); 745 ++this->__end_; 746 --__n; 747 } while (__n > 0); 748} 749 750// Copy constructs __n objects starting at __end_ from __x 751// throws if construction throws 752// Precondition: __n > 0 753// Precondition: size() + __n <= capacity() 754// Postcondition: size() == old size() + __n 755// Postcondition: [i] == __x for all i in [size() - __n, __n) 756template <class _Tp, class _Allocator> 757_LIBCPP_INLINE_VISIBILITY inline 758void 759vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 760{ 761 allocator_type& __a = this->__alloc(); 762 do 763 { 764 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), __x); 765 ++this->__end_; 766 --__n; 767 } while (__n > 0); 768} 769 770template <class _Tp, class _Allocator> 771template <class _ForwardIterator> 772typename enable_if 773< 774 __is_forward_iterator<_ForwardIterator>::value, 775 void 776>::type 777vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 778{ 779 allocator_type& __a = this->__alloc(); 780 for (; __first != __last; ++__first) 781 { 782 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), *__first); 783 ++this->__end_; 784 } 785} 786 787template <class _Tp, class _Allocator> 788void 789vector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last) 790{ 791 allocator_type& __a = this->__alloc(); 792 for (; __first != __last; ++__first) 793 { 794 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), 795 _STD::move(*__first)); 796 ++this->__end_; 797 } 798} 799 800// Default constructs __n objects starting at __end_ 801// throws if construction throws 802// Postcondition: size() == size() + __n 803// Exception safety: strong but assumes move ctor doesn't throw (copy ctor can) 804template <class _Tp, class _Allocator> 805void 806vector<_Tp, _Allocator>::__append(size_type __n) 807{ 808 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 809 this->__construct_at_end(__n); 810 else 811 { 812 allocator_type& __a = this->__alloc(); 813 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 814 __v.__construct_at_end(__n); 815 __swap_out_circular_buffer(__v); 816 } 817} 818 819// Default constructs __n objects starting at __end_ 820// throws if construction throws 821// Postcondition: size() == size() + __n 822// Exception safety: strong but assumes move ctor doesn't throw (copy ctor can) 823template <class _Tp, class _Allocator> 824void 825vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) 826{ 827 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 828 this->__construct_at_end(__n, __x); 829 else 830 { 831 allocator_type& __a = this->__alloc(); 832 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 833 __v.__construct_at_end(__n, __x); 834 __swap_out_circular_buffer(__v); 835 } 836} 837 838template <class _Tp, class _Allocator> 839vector<_Tp, _Allocator>::vector(size_type __n) 840{ 841 if (__n > 0) 842 { 843 allocate(__n); 844 __construct_at_end(__n); 845 } 846} 847 848template <class _Tp, class _Allocator> 849vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) 850{ 851 if (__n > 0) 852 { 853 allocate(__n); 854 __construct_at_end(__n, __x); 855 } 856} 857 858template <class _Tp, class _Allocator> 859vector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) 860 : __base(__a) 861{ 862 if (__n > 0) 863 { 864 allocate(__n); 865 __construct_at_end(__n, __x); 866 } 867} 868 869template <class _Tp, class _Allocator> 870template <class _InputIterator> 871vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 872 typename enable_if<__is_input_iterator <_InputIterator>::value && 873 !__is_forward_iterator<_InputIterator>::value>::type*) 874{ 875 for (; __first != __last; ++__first) 876 push_back(*__first); 877} 878 879template <class _Tp, class _Allocator> 880template <class _InputIterator> 881vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 882 typename enable_if<__is_input_iterator <_InputIterator>::value && 883 !__is_forward_iterator<_InputIterator>::value>::type*) 884 : __base(__a) 885{ 886 for (; __first != __last; ++__first) 887 push_back(*__first); 888} 889 890template <class _Tp, class _Allocator> 891template <class _ForwardIterator> 892vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 893 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 894{ 895 size_type __n = static_cast<size_type>(_STD::distance(__first, __last)); 896 if (__n > 0) 897 { 898 allocate(__n); 899 __construct_at_end(__first, __last); 900 } 901} 902 903template <class _Tp, class _Allocator> 904template <class _ForwardIterator> 905vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 906 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 907 : __base(__a) 908{ 909 size_type __n = static_cast<size_type>(_STD::distance(__first, __last)); 910 if (__n > 0) 911 { 912 allocate(__n); 913 __construct_at_end(__first, __last); 914 } 915} 916 917template <class _Tp, class _Allocator> 918vector<_Tp, _Allocator>::vector(const vector& __x) 919 : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) 920{ 921 size_type __n = __x.size(); 922 if (__n > 0) 923 { 924 allocate(__n); 925 __construct_at_end(__x.__begin_, __x.__end_); 926 } 927} 928 929template <class _Tp, class _Allocator> 930vector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) 931 : __base(__a) 932{ 933 size_type __n = __x.size(); 934 if (__n > 0) 935 { 936 allocate(__n); 937 __construct_at_end(__x.__begin_, __x.__end_); 938 } 939} 940 941#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 942 943template <class _Tp, class _Allocator> 944_LIBCPP_INLINE_VISIBILITY inline 945vector<_Tp, _Allocator>::vector(vector&& __x) 946 : __base(_STD::move(__x.__alloc())) 947{ 948 this->__begin_ = __x.__begin_; 949 this->__end_ = __x.__end_; 950 this->__end_cap() = __x.__end_cap(); 951 __x.__begin_ = __x.__end_ = __x.__end_cap() = 0; 952 __x.__invalidate_all_iterators(); 953} 954 955template <class _Tp, class _Allocator> 956_LIBCPP_INLINE_VISIBILITY inline 957vector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) 958 : __base(__a) 959{ 960 if (__a == __x.__alloc()) 961 { 962 this->__begin_ = __x.__begin_; 963 this->__end_ = __x.__end_; 964 this->__end_cap() = __x.__end_cap(); 965 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 966 __x.__invalidate_all_iterators(); 967 } 968 else 969 { 970 typedef move_iterator<iterator> _I; 971 assign(_I(__x.begin()), _I(__x.end())); 972 } 973} 974 975template <class _Tp, class _Allocator> 976_LIBCPP_INLINE_VISIBILITY inline 977vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) 978{ 979 if (__il.size() > 0) 980 { 981 allocate(__il.size()); 982 __construct_at_end(__il.begin(), __il.end()); 983 } 984} 985 986template <class _Tp, class _Allocator> 987_LIBCPP_INLINE_VISIBILITY inline 988vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 989 : __base(__a) 990{ 991 if (__il.size() > 0) 992 { 993 allocate(__il.size()); 994 __construct_at_end(__il.begin(), __il.end()); 995 } 996} 997 998template <class _Tp, class _Allocator> 999_LIBCPP_INLINE_VISIBILITY inline 1000vector<_Tp, _Allocator>& 1001vector<_Tp, _Allocator>::operator=(vector&& __x) 1002{ 1003 __move_assign(__x, integral_constant<bool, 1004 __alloc_traits::propagate_on_container_move_assignment::value>()); 1005 return *this; 1006} 1007 1008template <class _Tp, class _Allocator> 1009void 1010vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) 1011{ 1012 if (__base::__alloc() != __c.__alloc()) 1013 { 1014 typedef move_iterator<iterator> _I; 1015 assign(_I(__c.begin()), _I(__c.end())); 1016 } 1017 else 1018 __move_assign(__c, true_type()); 1019} 1020 1021template <class _Tp, class _Allocator> 1022void 1023vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) 1024{ 1025 deallocate(); 1026 this->__begin_ = __c.__begin_; 1027 this->__end_ = __c.__end_; 1028 this->__end_cap() = __c.__end_cap(); 1029 __base::__move_assign_alloc(__c); 1030 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 1031} 1032 1033#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1034 1035template <class _Tp, class _Allocator> 1036_LIBCPP_INLINE_VISIBILITY inline 1037vector<_Tp, _Allocator>& 1038vector<_Tp, _Allocator>::operator=(const vector& __x) 1039{ 1040 if (this != &__x) 1041 { 1042 __base::__copy_assign_alloc(__x); 1043 assign(__x.__begin_, __x.__end_); 1044 } 1045 return *this; 1046} 1047 1048template <class _Tp, class _Allocator> 1049template <class _InputIterator> 1050typename enable_if 1051< 1052 __is_input_iterator <_InputIterator>::value && 1053 !__is_forward_iterator<_InputIterator>::value, 1054 void 1055>::type 1056vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 1057{ 1058 clear(); 1059 for (; __first != __last; ++__first) 1060 push_back(*__first); 1061} 1062 1063template <class _Tp, class _Allocator> 1064template <class _ForwardIterator> 1065typename enable_if 1066< 1067 __is_forward_iterator<_ForwardIterator>::value, 1068 void 1069>::type 1070vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 1071{ 1072 typename iterator_traits<_ForwardIterator>::difference_type __new_size = _STD::distance(__first, __last); 1073 if (static_cast<size_type>(__new_size) <= capacity()) 1074 { 1075 _ForwardIterator __mid = __last; 1076 bool __growing = false; 1077 if (static_cast<size_type>(__new_size) > size()) 1078 { 1079 __growing = true; 1080 __mid = __first; 1081 _STD::advance(__mid, size()); 1082 } 1083 pointer __m = _STD::copy(__first, __mid, this->__begin_); 1084 if (__growing) 1085 __construct_at_end(__mid, __last); 1086 else 1087 this->__destruct_at_end(__m); 1088 } 1089 else 1090 { 1091 deallocate(); 1092 allocate(__recommend(static_cast<size_type>(__new_size))); 1093 __construct_at_end(__first, __last); 1094 } 1095} 1096 1097template <class _Tp, class _Allocator> 1098void 1099vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) 1100{ 1101 if (__n <= capacity()) 1102 { 1103 size_type __s = size(); 1104 _STD::fill_n(this->__begin_, min(__n, __s), __u); 1105 if (__n > __s) 1106 __construct_at_end(__n - __s, __u); 1107 else 1108 this->__destruct_at_end(this->__begin_ + __n); 1109 } 1110 else 1111 { 1112 deallocate(); 1113 allocate(__recommend(static_cast<size_type>(__n))); 1114 __construct_at_end(__n, __u); 1115 } 1116} 1117 1118template <class _Tp, class _Allocator> 1119_LIBCPP_INLINE_VISIBILITY inline 1120typename vector<_Tp, _Allocator>::iterator 1121vector<_Tp, _Allocator>::__make_iter(pointer __p) 1122{ 1123#ifdef _LIBCPP_DEBUG 1124 return iterator(this, __p); 1125#else 1126 return iterator(__p); 1127#endif 1128} 1129 1130template <class _Tp, class _Allocator> 1131_LIBCPP_INLINE_VISIBILITY inline 1132typename vector<_Tp, _Allocator>::const_iterator 1133vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const 1134{ 1135#ifdef _LIBCPP_DEBUG 1136 return const_iterator(this, __p); 1137#else 1138 return const_iterator(__p); 1139#endif 1140} 1141 1142template <class _Tp, class _Allocator> 1143_LIBCPP_INLINE_VISIBILITY inline 1144typename vector<_Tp, _Allocator>::iterator 1145vector<_Tp, _Allocator>::begin() 1146{ 1147 return __make_iter(this->__begin_); 1148} 1149 1150template <class _Tp, class _Allocator> 1151_LIBCPP_INLINE_VISIBILITY inline 1152typename vector<_Tp, _Allocator>::const_iterator 1153vector<_Tp, _Allocator>::begin() const 1154{ 1155 return __make_iter(this->__begin_); 1156} 1157 1158template <class _Tp, class _Allocator> 1159_LIBCPP_INLINE_VISIBILITY inline 1160typename vector<_Tp, _Allocator>::iterator 1161vector<_Tp, _Allocator>::end() 1162{ 1163 return __make_iter(this->__end_); 1164} 1165 1166template <class _Tp, class _Allocator> 1167_LIBCPP_INLINE_VISIBILITY inline 1168typename vector<_Tp, _Allocator>::const_iterator 1169vector<_Tp, _Allocator>::end() const 1170{ 1171 return __make_iter(this->__end_); 1172} 1173 1174template <class _Tp, class _Allocator> 1175_LIBCPP_INLINE_VISIBILITY inline 1176typename vector<_Tp, _Allocator>::reference 1177vector<_Tp, _Allocator>::operator[](size_type __n) 1178{ 1179#ifdef _LIBCPP_DEBUG 1180 assert(__n < size()); 1181#endif 1182 return this->__begin_[__n]; 1183} 1184 1185template <class _Tp, class _Allocator> 1186_LIBCPP_INLINE_VISIBILITY inline 1187typename vector<_Tp, _Allocator>::const_reference 1188vector<_Tp, _Allocator>::operator[](size_type __n) const 1189{ 1190#ifdef _LIBCPP_DEBUG 1191 assert(__n < size()); 1192#endif 1193 return this->__begin_[__n]; 1194} 1195 1196template <class _Tp, class _Allocator> 1197typename vector<_Tp, _Allocator>::reference 1198vector<_Tp, _Allocator>::at(size_type __n) 1199{ 1200 if (__n >= size()) 1201 this->__throw_out_of_range(); 1202 return this->__begin_[__n]; 1203} 1204 1205template <class _Tp, class _Allocator> 1206typename vector<_Tp, _Allocator>::const_reference 1207vector<_Tp, _Allocator>::at(size_type __n) const 1208{ 1209 if (__n >= size()) 1210 this->__throw_out_of_range(); 1211 return this->__begin_[__n]; 1212} 1213 1214template <class _Tp, class _Allocator> 1215void 1216vector<_Tp, _Allocator>::reserve(size_type __n) 1217{ 1218 if (__n > capacity()) 1219 { 1220 allocator_type& __a = this->__alloc(); 1221 __split_buffer<value_type, allocator_type&> __v(__n, 0, __a); 1222 __v.__construct_at_end(move_iterator<pointer>(this->__begin_), 1223 move_iterator<pointer>(this->__end_)); 1224 clear(); 1225 __swap_out_circular_buffer(__v); 1226 } 1227} 1228 1229template <class _Tp, class _Allocator> 1230void 1231vector<_Tp, _Allocator>::shrink_to_fit() 1232{ 1233 if (capacity() > size()) 1234 { 1235#ifndef _LIBCPP_NO_EXCEPTIONS 1236 try 1237 { 1238#endif // _LIBCPP_NO_EXCEPTIONS 1239 allocator_type& __a = this->__alloc(); 1240 __split_buffer<value_type, allocator_type&> __v(size(), 0, __a); 1241 __v.__construct_at_end(move_iterator<pointer>(this->__begin_), 1242 move_iterator<pointer>(this->__end_)); 1243 clear(); 1244 __swap_out_circular_buffer(__v); 1245#ifndef _LIBCPP_NO_EXCEPTIONS 1246 } 1247 catch (...) 1248 { 1249 } 1250#endif // _LIBCPP_NO_EXCEPTIONS 1251 } 1252} 1253 1254template <class _Tp, class _Allocator> 1255void 1256vector<_Tp, _Allocator>::push_back(const_reference __x) 1257{ 1258 if (this->__end_ < this->__end_cap()) 1259 { 1260 __alloc_traits::construct(this->__alloc(), 1261 _STD::__to_raw_pointer(this->__end_), __x); 1262 ++this->__end_; 1263 } 1264 else 1265 { 1266 allocator_type& __a = this->__alloc(); 1267 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1268 __v.push_back(__x); 1269 __swap_out_circular_buffer(__v); 1270 } 1271} 1272 1273#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1274 1275template <class _Tp, class _Allocator> 1276void 1277vector<_Tp, _Allocator>::push_back(value_type&& __x) 1278{ 1279 if (this->__end_ < this->__end_cap()) 1280 { 1281 __alloc_traits::construct(this->__alloc(), 1282 _STD::__to_raw_pointer(this->__end_), 1283 _STD::move(__x)); 1284 ++this->__end_; 1285 } 1286 else 1287 { 1288 allocator_type& __a = this->__alloc(); 1289 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1290 __v.push_back(_STD::move(__x)); 1291 __swap_out_circular_buffer(__v); 1292 } 1293} 1294 1295#ifndef _LIBCPP_HAS_NO_VARIADICS 1296 1297template <class _Tp, class _Allocator> 1298template <class... _Args> 1299void 1300vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1301{ 1302 if (this->__end_ < this->__end_cap()) 1303 { 1304 __alloc_traits::construct(this->__alloc(), 1305 _STD::__to_raw_pointer(this->__end_), 1306 _STD::forward<_Args>(__args)...); 1307 ++this->__end_; 1308 } 1309 else 1310 { 1311 allocator_type& __a = this->__alloc(); 1312 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1313 __v.emplace_back(_STD::forward<_Args>(__args)...); 1314 __swap_out_circular_buffer(__v); 1315 } 1316} 1317 1318#endif // _LIBCPP_HAS_NO_VARIADICS 1319#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1320 1321template <class _Tp, class _Allocator> 1322_LIBCPP_INLINE_VISIBILITY inline 1323void 1324vector<_Tp, _Allocator>::pop_back() 1325{ 1326 this->__destruct_at_end(this->__end_ - 1); 1327} 1328 1329template <class _Tp, class _Allocator> 1330_LIBCPP_INLINE_VISIBILITY inline 1331typename vector<_Tp, _Allocator>::iterator 1332vector<_Tp, _Allocator>::erase(const_iterator __position) 1333{ 1334 pointer __p = const_cast<pointer>(&*__position); 1335 iterator __r = __make_iter(__p); 1336 this->__destruct_at_end(_STD::move(__p + 1, this->__end_, __p)); 1337 return __r; 1338} 1339 1340template <class _Tp, class _Allocator> 1341typename vector<_Tp, _Allocator>::iterator 1342vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) 1343{ 1344 pointer __p = this->__begin_ + (__first - begin()); 1345 iterator __r = __make_iter(__p); 1346 this->__destruct_at_end(_STD::move(__p + (__last - __first), this->__end_, __p)); 1347 return __r; 1348} 1349 1350template <class _Tp, class _Allocator> 1351void 1352vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) 1353{ 1354 pointer __old_last = this->__end_; 1355 difference_type __n = __old_last - __to; 1356 for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_) 1357 __alloc_traits::construct(this->__alloc(), 1358 _STD::__to_raw_pointer(this->__end_), 1359 _STD::move(*__i)); 1360 _STD::move_backward(__from_s, __from_s + __n, __old_last); 1361} 1362 1363template <class _Tp, class _Allocator> 1364typename vector<_Tp, _Allocator>::iterator 1365vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) 1366{ 1367 pointer __p = this->__begin_ + (__position - begin()); 1368 if (this->__end_ < this->__end_cap()) 1369 { 1370 if (__p == this->__end_) 1371 { 1372 __alloc_traits::construct(this->__alloc(), 1373 _STD::__to_raw_pointer(this->__end_), __x); 1374 ++this->__end_; 1375 } 1376 else 1377 { 1378 __move_range(__p, this->__end_, __p + 1); 1379 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1380 if (__p <= __xr && __xr < this->__end_) 1381 ++__xr; 1382 *__p = *__xr; 1383 } 1384 } 1385 else 1386 { 1387 allocator_type& __a = this->__alloc(); 1388 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1389 __v.push_back(__x); 1390 __p = __swap_out_circular_buffer(__v, __p); 1391 } 1392 return __make_iter(__p); 1393} 1394 1395#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1396 1397template <class _Tp, class _Allocator> 1398typename vector<_Tp, _Allocator>::iterator 1399vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) 1400{ 1401 pointer __p = this->__begin_ + (__position - begin()); 1402 if (this->__end_ < this->__end_cap()) 1403 { 1404 if (__p == this->__end_) 1405 { 1406 __alloc_traits::construct(this->__alloc(), 1407 _STD::__to_raw_pointer(this->__end_), 1408 _STD::move(__x)); 1409 ++this->__end_; 1410 } 1411 else 1412 { 1413 __move_range(__p, this->__end_, __p + 1); 1414 *__p = _STD::move(__x); 1415 } 1416 } 1417 else 1418 { 1419 allocator_type& __a = this->__alloc(); 1420 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1421 __v.push_back(_STD::move(__x)); 1422 __p = __swap_out_circular_buffer(__v, __p); 1423 } 1424 return __make_iter(__p); 1425} 1426 1427#ifndef _LIBCPP_HAS_NO_VARIADICS 1428 1429template <class _Tp, class _Allocator> 1430template <class... _Args> 1431typename vector<_Tp, _Allocator>::iterator 1432vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) 1433{ 1434 pointer __p = this->__begin_ + (__position - begin()); 1435 if (this->__end_ < this->__end_cap()) 1436 { 1437 if (__p == this->__end_) 1438 { 1439 __alloc_traits::construct(this->__alloc(), 1440 _STD::__to_raw_pointer(this->__end_), 1441 _STD::forward<_Args>(__args)...); 1442 ++this->__end_; 1443 } 1444 else 1445 { 1446 __move_range(__p, this->__end_, __p + 1); 1447 *__p = value_type(_STD::forward<_Args>(__args)...); 1448 } 1449 } 1450 else 1451 { 1452 allocator_type& __a = this->__alloc(); 1453 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1454 __v.emplace_back(_STD::forward<_Args>(__args)...); 1455 __p = __swap_out_circular_buffer(__v, __p); 1456 } 1457 return __make_iter(__p); 1458} 1459 1460#endif // _LIBCPP_HAS_NO_VARIADICS 1461#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1462 1463template <class _Tp, class _Allocator> 1464typename vector<_Tp, _Allocator>::iterator 1465vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) 1466{ 1467 pointer __p = this->__begin_ + (__position - begin()); 1468 if (__n > 0) 1469 { 1470 if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_)) 1471 { 1472 size_type __old_n = __n; 1473 pointer __old_last = this->__end_; 1474 if (__n > static_cast<size_type>(this->__end_ - __p)) 1475 { 1476 size_type __cx = __n - (this->__end_ - __p); 1477 __construct_at_end(__cx, __x); 1478 __n -= __cx; 1479 } 1480 if (__n > 0) 1481 { 1482 __move_range(__p, __old_last, __p + __old_n); 1483 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1484 if (__p <= __xr && __xr < this->__end_) 1485 __xr += __old_n; 1486 _STD::fill_n(__p, __n, *__xr); 1487 } 1488 } 1489 else 1490 { 1491 allocator_type& __a = this->__alloc(); 1492 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1493 __v.__construct_at_end(__n, __x); 1494 __p = __swap_out_circular_buffer(__v, __p); 1495 } 1496 } 1497 return __make_iter(__p); 1498} 1499 1500template <class _Tp, class _Allocator> 1501template <class _InputIterator> 1502typename enable_if 1503< 1504 __is_input_iterator <_InputIterator>::value && 1505 !__is_forward_iterator<_InputIterator>::value, 1506 typename vector<_Tp, _Allocator>::iterator 1507>::type 1508vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 1509{ 1510 difference_type __off = __position - begin(); 1511 pointer __p = this->__begin_ + __off; 1512 allocator_type& __a = this->__alloc(); 1513 pointer __old_last = this->__end_; 1514 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) 1515 { 1516 __alloc_traits::construct(__a, _STD::__to_raw_pointer(this->__end_), 1517 *__first); 1518 ++this->__end_; 1519 } 1520 __split_buffer<value_type, allocator_type&> __v(__a); 1521 if (__first != __last) 1522 { 1523#ifndef _LIBCPP_NO_EXCEPTIONS 1524 try 1525 { 1526#endif // _LIBCPP_NO_EXCEPTIONS 1527 __v.__construct_at_end(__first, __last); 1528 difference_type __old_size = __old_last - this->__begin_; 1529 difference_type __old_p = __p - this->__begin_; 1530 reserve(__recommend(size() + __v.size())); 1531 __p = this->__begin_ + __old_p; 1532 __old_last = this->__begin_ + __old_size; 1533#ifndef _LIBCPP_NO_EXCEPTIONS 1534 } 1535 catch (...) 1536 { 1537 erase(__make_iter(__old_last), end()); 1538 throw; 1539 } 1540#endif // _LIBCPP_NO_EXCEPTIONS 1541 } 1542 __p = _STD::rotate(__p, __old_last, this->__end_); 1543 insert(__make_iter(__p), move_iterator<iterator>(__v.begin()), 1544 move_iterator<iterator>(__v.end())); 1545 return begin() + __off; 1546} 1547 1548template <class _Tp, class _Allocator> 1549template <class _ForwardIterator> 1550typename enable_if 1551< 1552 __is_forward_iterator<_ForwardIterator>::value, 1553 typename vector<_Tp, _Allocator>::iterator 1554>::type 1555vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 1556{ 1557 pointer __p = this->__begin_ + (__position - begin()); 1558 difference_type __n = _STD::distance(__first, __last); 1559 if (__n > 0) 1560 { 1561 if (__n <= this->__end_cap() - this->__end_) 1562 { 1563 size_type __old_n = __n; 1564 pointer __old_last = this->__end_; 1565 _ForwardIterator __m = __last; 1566 difference_type __dx = this->__end_ - __p; 1567 if (__n > __dx) 1568 { 1569 __m = __first; 1570 _STD::advance(__m, this->__end_ - __p); 1571 __construct_at_end(__m, __last); 1572 __n = __dx; 1573 } 1574 if (__n > 0) 1575 { 1576 __move_range(__p, __old_last, __p + __old_n); 1577 _STD::copy(__first, __m, __p); 1578 } 1579 } 1580 else 1581 { 1582 allocator_type& __a = this->__alloc(); 1583 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1584 __v.__construct_at_end(__first, __last); 1585 __p = __swap_out_circular_buffer(__v, __p); 1586 } 1587 } 1588 return __make_iter(__p); 1589} 1590 1591template <class _Tp, class _Allocator> 1592void 1593vector<_Tp, _Allocator>::resize(size_type __sz) 1594{ 1595 size_type __cs = size(); 1596 if (__cs < __sz) 1597 this->__append(__sz - __cs); 1598 else if (__cs > __sz) 1599 this->__destruct_at_end(this->__begin_ + __sz); 1600} 1601 1602template <class _Tp, class _Allocator> 1603void 1604vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) 1605{ 1606 size_type __cs = size(); 1607 if (__cs < __sz) 1608 this->__append(__sz - __cs, __x); 1609 else if (__cs > __sz) 1610 this->__destruct_at_end(this->__begin_ + __sz); 1611} 1612 1613template <class _Tp, class _Allocator> 1614void 1615vector<_Tp, _Allocator>::swap(vector& __x) 1616{ 1617 _STD::swap(this->__begin_, __x.__begin_); 1618 _STD::swap(this->__end_, __x.__end_); 1619 _STD::swap(this->__end_cap(), __x.__end_cap()); 1620 __base::__swap_alloc(this->__alloc(), __x.__alloc()); 1621#ifdef _LIBCPP_DEBUG 1622 iterator::swap(this, &__x); 1623 const_iterator::swap(this, &__x); 1624#endif // _LIBCPP_DEBUG 1625} 1626 1627template <class _Tp, class _Allocator> 1628bool 1629vector<_Tp, _Allocator>::__invariants() const 1630{ 1631 if (this->__begin_ == 0) 1632 { 1633 if (this->__end_ != 0 || this->__end_cap() != 0) 1634 return false; 1635 } 1636 else 1637 { 1638 if (this->__begin_ > this->__end_) 1639 return false; 1640 if (this->__begin_ == this->__end_cap()) 1641 return false; 1642 if (this->__end_ > this->__end_cap()) 1643 return false; 1644 } 1645 return true; 1646} 1647 1648template <class _Tp, class _Allocator> 1649#ifndef _LIBCPP_DEBUG 1650_LIBCPP_INLINE_VISIBILITY inline 1651#endif 1652void 1653vector<_Tp, _Allocator>::__invalidate_all_iterators() 1654{ 1655#ifdef _LIBCPP_DEBUG 1656 iterator::__remove_all(this); 1657 const_iterator::__remove_all(this); 1658#endif // _LIBCPP_DEBUG 1659} 1660 1661// vector<bool> 1662 1663template <class _Allocator> class vector<bool, _Allocator>; 1664 1665template <class _Allocator> struct hash<vector<bool, _Allocator> >; 1666 1667template <class _Allocator> 1668class _LIBCPP_VISIBLE vector<bool, _Allocator> 1669 : private __vector_base_common<true> 1670{ 1671public: 1672 typedef vector __self; 1673 typedef bool value_type; 1674 typedef _Allocator allocator_type; 1675 typedef allocator_traits<allocator_type> __alloc_traits; 1676 typedef __bit_reference<vector> reference; 1677 typedef __bit_const_reference<vector> const_reference; 1678 typedef typename __alloc_traits::size_type size_type; 1679 typedef typename __alloc_traits::difference_type difference_type; 1680 typedef __bit_iterator<vector, false> pointer; 1681 typedef __bit_iterator<vector, true> const_pointer; 1682#ifdef _LIBCPP_DEBUG 1683 typedef __debug_iter<vector, pointer> iterator; 1684 typedef __debug_iter<vector, const_pointer> const_iterator; 1685 1686 friend class __debug_iter<vector, pointer>; 1687 friend class __debug_iter<vector, const_pointer>; 1688 1689 pair<iterator*, const_iterator*> __iterator_list_; 1690 1691 _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;} 1692 _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;} 1693#else // _LIBCPP_DEBUG 1694 typedef pointer iterator; 1695 typedef const_pointer const_iterator; 1696#endif // _LIBCPP_DEBUG 1697 typedef _STD::reverse_iterator<iterator> reverse_iterator; 1698 typedef _STD::reverse_iterator<const_iterator> const_reverse_iterator; 1699 1700private: 1701 typedef size_type __storage_type; 1702 typedef typename __alloc_traits::template 1703#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 1704 rebind_alloc<__storage_type> 1705#else 1706 rebind_alloc<__storage_type>::other 1707#endif 1708 __storage_allocator; 1709 typedef allocator_traits<__storage_allocator> __storage_traits; 1710 typedef typename __storage_traits::pointer __storage_pointer; 1711 typedef typename __storage_traits::const_pointer __const_storage_pointer; 1712 1713 __storage_pointer __begin_; 1714 size_type __size_; 1715 __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 1716 1717 _LIBCPP_INLINE_VISIBILITY size_type& __cap() {return __cap_alloc_.first();} 1718 _LIBCPP_INLINE_VISIBILITY const size_type& __cap() const {return __cap_alloc_.first();} 1719 _LIBCPP_INLINE_VISIBILITY __storage_allocator& __alloc() {return __cap_alloc_.second();} 1720 _LIBCPP_INLINE_VISIBILITY const __storage_allocator& __alloc() const {return __cap_alloc_.second();} 1721 1722 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 1723 1724 _LIBCPP_INLINE_VISIBILITY static size_type __internal_cap_to_external(size_type __n) 1725 {return __n * __bits_per_word;} 1726 _LIBCPP_INLINE_VISIBILITY static size_type __external_cap_to_internal(size_type __n) 1727 {return (__n - 1) / __bits_per_word + 1;} 1728 1729public: 1730 _LIBCPP_INLINE_VISIBILITY vector(); 1731 _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a); 1732 ~vector(); 1733 explicit vector(size_type __n); 1734 vector(size_type __n, const value_type& __v); 1735 vector(size_type __n, const value_type& __v, const allocator_type& __a); 1736 template <class _InputIterator> 1737 vector(_InputIterator __first, _InputIterator __last, 1738 typename enable_if<__is_input_iterator <_InputIterator>::value && 1739 !__is_forward_iterator<_InputIterator>::value>::type* = 0); 1740 template <class _InputIterator> 1741 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 1742 typename enable_if<__is_input_iterator <_InputIterator>::value && 1743 !__is_forward_iterator<_InputIterator>::value>::type* = 0); 1744 template <class _ForwardIterator> 1745 vector(_ForwardIterator __first, _ForwardIterator __last, 1746 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 1747 template <class _ForwardIterator> 1748 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 1749 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 1750 1751 vector(const vector& __v); 1752 vector(const vector& __v, const allocator_type& __a); 1753 vector& operator=(const vector& __v); 1754 vector(initializer_list<value_type> __il); 1755 vector(initializer_list<value_type> __il, const allocator_type& __a); 1756 1757#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1758 _LIBCPP_INLINE_VISIBILITY vector(vector&& __v); 1759 vector(vector&& __v, const allocator_type& __a); 1760 _LIBCPP_INLINE_VISIBILITY vector& operator=(vector&& __v); 1761#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1762 _LIBCPP_INLINE_VISIBILITY 1763 vector& operator=(initializer_list<value_type> __il) 1764 {assign(__il.begin(), __il.end()); return *this;} 1765 1766 template <class _InputIterator> 1767 typename enable_if 1768 < 1769 __is_input_iterator<_InputIterator>::value && 1770 !__is_forward_iterator<_InputIterator>::value, 1771 void 1772 >::type 1773 assign(_InputIterator __first, _InputIterator __last); 1774 template <class _ForwardIterator> 1775 typename enable_if 1776 < 1777 __is_forward_iterator<_ForwardIterator>::value, 1778 void 1779 >::type 1780 assign(_ForwardIterator __first, _ForwardIterator __last); 1781 1782 void assign(size_type __n, const value_type& __x); 1783 _LIBCPP_INLINE_VISIBILITY 1784 void assign(initializer_list<value_type> __il) 1785 {assign(__il.begin(), __il.end());} 1786 1787 _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const 1788 {return allocator_type(this->__alloc());} 1789 1790 size_type max_size() const; 1791 _LIBCPP_INLINE_VISIBILITY size_type capacity() const {return __internal_cap_to_external(__cap());} 1792 _LIBCPP_INLINE_VISIBILITY size_type size() const {return __size_;} 1793 _LIBCPP_INLINE_VISIBILITY bool empty() const {return __size_ == 0;} 1794 void reserve(size_type __n); 1795 void shrink_to_fit(); 1796 1797 _LIBCPP_INLINE_VISIBILITY iterator begin() {return __make_iter(0);} 1798 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const {return __make_iter(0);} 1799 _LIBCPP_INLINE_VISIBILITY iterator end() {return __make_iter(__size_);} 1800 _LIBCPP_INLINE_VISIBILITY const_iterator end() const {return __make_iter(__size_);} 1801 1802 _LIBCPP_INLINE_VISIBILITY reverse_iterator rbegin() {return reverse_iterator(end());} 1803 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rbegin() const {return const_reverse_iterator(end());} 1804 _LIBCPP_INLINE_VISIBILITY reverse_iterator rend() {return reverse_iterator(begin());} 1805 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator rend() const {return const_reverse_iterator(begin());} 1806 1807 _LIBCPP_INLINE_VISIBILITY const_iterator cbegin() const {return __make_iter(0);} 1808 _LIBCPP_INLINE_VISIBILITY const_iterator cend() const {return __make_iter(__size_);} 1809 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crbegin() const {return rbegin();} 1810 _LIBCPP_INLINE_VISIBILITY const_reverse_iterator crend() const {return rend();} 1811 1812 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);} 1813 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);} 1814 reference at(size_type __n); 1815 const_reference at(size_type __n) const; 1816 1817 _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);} 1818 _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);} 1819 _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);} 1820 _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);} 1821 1822 void push_back(const value_type& __x); 1823 _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;} 1824 1825 iterator insert(const_iterator __position, const value_type& __x); 1826 iterator insert(const_iterator __position, size_type __n, const value_type& __x); 1827 iterator insert(const_iterator __position, size_type __n, const_reference __x); 1828 template <class _InputIterator> 1829 typename enable_if 1830 < 1831 __is_input_iterator <_InputIterator>::value && 1832 !__is_forward_iterator<_InputIterator>::value, 1833 iterator 1834 >::type 1835 insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 1836 template <class _ForwardIterator> 1837 typename enable_if 1838 < 1839 __is_forward_iterator<_ForwardIterator>::value, 1840 iterator 1841 >::type 1842 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 1843 _LIBCPP_INLINE_VISIBILITY 1844 iterator insert(const_iterator __position, initializer_list<value_type> __il) 1845 {return insert(__position, __il.begin(), __il.end());} 1846 1847 _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 1848 iterator erase(const_iterator __first, const_iterator __last); 1849 1850 _LIBCPP_INLINE_VISIBILITY void clear() {__size_ = 0;} 1851 1852 void swap(vector&); 1853 1854 void resize(size_type __sz, value_type __x = false); 1855 void flip(); 1856 1857 bool __invariants() const; 1858 1859private: 1860 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 1861 void allocate(size_type __n); 1862 void deallocate(); 1863 _LIBCPP_INLINE_VISIBILITY static size_type __align(size_type __new_size) 1864 {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);}; 1865 _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 1866 _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x); 1867 template <class _ForwardIterator> 1868 typename enable_if 1869 < 1870 __is_forward_iterator<_ForwardIterator>::value, 1871 void 1872 >::type 1873 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 1874 void __append(size_type __n, const_reference __x); 1875 _LIBCPP_INLINE_VISIBILITY reference __make_ref(size_type __pos) 1876 {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 1877 _LIBCPP_INLINE_VISIBILITY const_reference __make_ref(size_type __pos) const 1878 {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 1879#ifdef _LIBCPP_DEBUG 1880 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos) 1881 {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));} 1882 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const 1883 {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));} 1884 _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p) 1885 {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));} 1886#else // _LIBCPP_DEBUG 1887 _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos) 1888 {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 1889 _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const 1890 {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 1891 _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p) 1892 {return iterator(const_cast<__storage_pointer>(__p.__seg_), __p.__ctz_);} 1893#endif // _LIBCPP_DEBUG 1894 1895 _LIBCPP_INLINE_VISIBILITY 1896 void __copy_assign_alloc(const vector& __v) 1897 {__copy_assign_alloc(__v, integral_constant<bool, 1898 __storage_traits::propagate_on_container_copy_assignment::value>());} 1899 _LIBCPP_INLINE_VISIBILITY 1900 void __copy_assign_alloc(const vector& __c, true_type) 1901 { 1902 if (__alloc() != __c.__alloc()) 1903 deallocate(); 1904 __alloc() = __c.__alloc(); 1905 } 1906 1907 _LIBCPP_INLINE_VISIBILITY 1908 void __copy_assign_alloc(const vector& __c, false_type) 1909 {} 1910 1911 void __move_assign(vector& __c, false_type); 1912 void __move_assign(vector& __c, true_type); 1913 _LIBCPP_INLINE_VISIBILITY 1914 void __move_assign_alloc(vector& __c) 1915 {__move_assign_alloc(__c, integral_constant<bool, 1916 __storage_traits::propagate_on_container_move_assignment::value>());} 1917 _LIBCPP_INLINE_VISIBILITY 1918 void __move_assign_alloc(const vector& __c, true_type) 1919 { 1920 __alloc() = _STD::move(__c.__alloc()); 1921 } 1922 1923 _LIBCPP_INLINE_VISIBILITY 1924 void __move_assign_alloc(const vector& __c, false_type) 1925 {} 1926 1927 _LIBCPP_INLINE_VISIBILITY 1928 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y) 1929 {__swap_alloc(__x, __y, integral_constant<bool, 1930 __storage_traits::propagate_on_container_swap::value>());} 1931 1932 _LIBCPP_INLINE_VISIBILITY 1933 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type) 1934 { 1935 using _STD::swap; 1936 swap(__x, __y); 1937 } 1938 _LIBCPP_INLINE_VISIBILITY 1939 static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, false_type) 1940 {} 1941 1942 size_t __hash_code() const; 1943 1944 friend class __bit_reference<vector>; 1945 friend class __bit_const_reference<vector>; 1946 friend class __bit_iterator<vector, false>; 1947 friend class __bit_iterator<vector, true>; 1948 friend class __bit_array<vector>; 1949 friend struct _LIBCPP_VISIBLE hash<vector>; 1950}; 1951 1952template <class _Allocator> 1953#ifndef _LIBCPP_DEBUG 1954_LIBCPP_INLINE_VISIBILITY inline 1955#endif 1956void 1957vector<bool, _Allocator>::__invalidate_all_iterators() 1958{ 1959#ifdef _LIBCPP_DEBUG 1960 iterator::__remove_all(this); 1961 const_iterator::__remove_all(this); 1962#endif // _LIBCPP_DEBUG 1963} 1964 1965// Allocate space for __n objects 1966// throws length_error if __n > max_size() 1967// throws (probably bad_alloc) if memory run out 1968// Precondition: __begin_ == __end_ == __cap() == 0 1969// Precondition: __n > 0 1970// Postcondition: capacity() == __n 1971// Postcondition: size() == 0 1972template <class _Allocator> 1973void 1974vector<bool, _Allocator>::allocate(size_type __n) 1975{ 1976 if (__n > max_size()) 1977 this->__throw_length_error(); 1978 __n = __external_cap_to_internal(__n); 1979 this->__begin_ = __storage_traits::allocate(this->__alloc(), __n); 1980 this->__size_ = 0; 1981 this->__cap() = __n; 1982} 1983 1984template <class _Allocator> 1985void 1986vector<bool, _Allocator>::deallocate() 1987{ 1988 if (this->__begin_ != 0) 1989 { 1990 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 1991 __invalidate_all_iterators(); 1992 this->__begin_ = 0; 1993 this->__size_ = this->__cap() = 0; 1994 } 1995} 1996 1997template <class _Allocator> 1998typename vector<bool, _Allocator>::size_type 1999vector<bool, _Allocator>::max_size() const 2000{ 2001 size_type __amax = __storage_traits::max_size(__alloc()); 2002 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 2003 if (__nmax / __bits_per_word <= __amax) 2004 return __nmax; 2005 return __internal_cap_to_external(__amax); 2006} 2007 2008// Precondition: __new_size > capacity() 2009template <class _Allocator> 2010_LIBCPP_INLINE_VISIBILITY inline 2011typename vector<bool, _Allocator>::size_type 2012vector<bool, _Allocator>::__recommend(size_type __new_size) const 2013{ 2014 const size_type __ms = max_size(); 2015 if (__new_size > __ms) 2016 this->__throw_length_error(); 2017 const size_type __cap = capacity(); 2018 if (__cap >= __ms / 2) 2019 return __ms; 2020 return _STD::max(2*__cap, __align(__new_size)); 2021} 2022 2023// Default constructs __n objects starting at __end_ 2024// Precondition: __n > 0 2025// Precondition: size() + __n <= capacity() 2026// Postcondition: size() == size() + __n 2027template <class _Allocator> 2028_LIBCPP_INLINE_VISIBILITY inline 2029void 2030vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) 2031{ 2032 size_type __old_size = this->__size_; 2033 this->__size_ += __n; 2034 _STD::fill_n(__make_iter(__old_size), __n, __x); 2035} 2036 2037template <class _Allocator> 2038template <class _ForwardIterator> 2039typename enable_if 2040< 2041 __is_forward_iterator<_ForwardIterator>::value, 2042 void 2043>::type 2044vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 2045{ 2046 size_type __old_size = this->__size_; 2047 this->__size_ += _STD::distance(__first, __last); 2048 _STD::copy(__first, __last, __make_iter(__old_size)); 2049} 2050 2051template <class _Allocator> 2052_LIBCPP_INLINE_VISIBILITY inline 2053vector<bool, _Allocator>::vector() 2054 : __begin_(0), 2055 __size_(0), 2056 __cap_alloc_(0) 2057{ 2058} 2059 2060template <class _Allocator> 2061_LIBCPP_INLINE_VISIBILITY inline 2062vector<bool, _Allocator>::vector(const allocator_type& __a) 2063 : __begin_(0), 2064 __size_(0), 2065 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2066{ 2067} 2068 2069template <class _Allocator> 2070vector<bool, _Allocator>::vector(size_type __n) 2071 : __begin_(0), 2072 __size_(0), 2073 __cap_alloc_(0) 2074{ 2075 if (__n > 0) 2076 { 2077 allocate(__n); 2078 __construct_at_end(__n, false); 2079 } 2080} 2081 2082template <class _Allocator> 2083vector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 2084 : __begin_(0), 2085 __size_(0), 2086 __cap_alloc_(0) 2087{ 2088 if (__n > 0) 2089 { 2090 allocate(__n); 2091 __construct_at_end(__n, __x); 2092 } 2093} 2094 2095template <class _Allocator> 2096vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 2097 : __begin_(0), 2098 __size_(0), 2099 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2100{ 2101 if (__n > 0) 2102 { 2103 allocate(__n); 2104 __construct_at_end(__n, __x); 2105 } 2106} 2107 2108template <class _Allocator> 2109template <class _InputIterator> 2110vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 2111 typename enable_if<__is_input_iterator <_InputIterator>::value && 2112 !__is_forward_iterator<_InputIterator>::value>::type*) 2113 : __begin_(0), 2114 __size_(0), 2115 __cap_alloc_(0) 2116{ 2117#ifndef _LIBCPP_NO_EXCEPTIONS 2118 try 2119 { 2120#endif // _LIBCPP_NO_EXCEPTIONS 2121 for (; __first != __last; ++__first) 2122 push_back(*__first); 2123#ifndef _LIBCPP_NO_EXCEPTIONS 2124 } 2125 catch (...) 2126 { 2127 if (__begin_ != 0) 2128 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2129 __invalidate_all_iterators(); 2130 throw; 2131 } 2132#endif // _LIBCPP_NO_EXCEPTIONS 2133} 2134 2135template <class _Allocator> 2136template <class _InputIterator> 2137vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2138 typename enable_if<__is_input_iterator <_InputIterator>::value && 2139 !__is_forward_iterator<_InputIterator>::value>::type*) 2140 : __begin_(0), 2141 __size_(0), 2142 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2143{ 2144#ifndef _LIBCPP_NO_EXCEPTIONS 2145 try 2146 { 2147#endif // _LIBCPP_NO_EXCEPTIONS 2148 for (; __first != __last; ++__first) 2149 push_back(*__first); 2150#ifndef _LIBCPP_NO_EXCEPTIONS 2151 } 2152 catch (...) 2153 { 2154 if (__begin_ != 0) 2155 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2156 __invalidate_all_iterators(); 2157 throw; 2158 } 2159#endif // _LIBCPP_NO_EXCEPTIONS 2160} 2161 2162template <class _Allocator> 2163template <class _ForwardIterator> 2164vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 2165 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2166 : __begin_(0), 2167 __size_(0), 2168 __cap_alloc_(0) 2169{ 2170 size_type __n = static_cast<size_type>(_STD::distance(__first, __last)); 2171 if (__n > 0) 2172 { 2173 allocate(__n); 2174 __construct_at_end(__first, __last); 2175 } 2176} 2177 2178template <class _Allocator> 2179template <class _ForwardIterator> 2180vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2181 typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2182 : __begin_(0), 2183 __size_(0), 2184 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2185{ 2186 size_type __n = static_cast<size_type>(_STD::distance(__first, __last)); 2187 if (__n > 0) 2188 { 2189 allocate(__n); 2190 __construct_at_end(__first, __last); 2191 } 2192} 2193 2194template <class _Allocator> 2195vector<bool, _Allocator>::vector(initializer_list<value_type> __il) 2196 : __begin_(0), 2197 __size_(0), 2198 __cap_alloc_(0) 2199{ 2200 size_type __n = static_cast<size_type>(__il.size()); 2201 if (__n > 0) 2202 { 2203 allocate(__n); 2204 __construct_at_end(__il.begin(), __il.end()); 2205 } 2206} 2207 2208template <class _Allocator> 2209vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 2210 : __begin_(0), 2211 __size_(0), 2212 __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2213{ 2214 size_type __n = static_cast<size_type>(__il.size()); 2215 if (__n > 0) 2216 { 2217 allocate(__n); 2218 __construct_at_end(__il.begin(), __il.end()); 2219 } 2220} 2221 2222template <class _Allocator> 2223vector<bool, _Allocator>::~vector() 2224{ 2225 if (__begin_ != 0) 2226 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2227#ifdef _LIBCPP_DEBUG 2228 __invalidate_all_iterators(); 2229#endif 2230} 2231 2232template <class _Allocator> 2233vector<bool, _Allocator>::vector(const vector& __v) 2234 : __begin_(0), 2235 __size_(0), 2236 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) 2237{ 2238 if (__v.size() > 0) 2239 { 2240 allocate(__v.size()); 2241 __construct_at_end(__v.begin(), __v.end()); 2242 } 2243} 2244 2245template <class _Allocator> 2246vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2247 : __begin_(0), 2248 __size_(0), 2249 __cap_alloc_(0, __a) 2250{ 2251 if (__v.size() > 0) 2252 { 2253 allocate(__v.size()); 2254 __construct_at_end(__v.begin(), __v.end()); 2255 } 2256} 2257 2258template <class _Allocator> 2259vector<bool, _Allocator>& 2260vector<bool, _Allocator>::operator=(const vector& __v) 2261{ 2262 if (this != &__v) 2263 { 2264 __copy_assign_alloc(__v); 2265 if (__v.__size_) 2266 { 2267 if (__v.__size_ > capacity()) 2268 { 2269 deallocate(); 2270 allocate(__v.__size_); 2271 } 2272 _STD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2273 } 2274 __size_ = __v.__size_; 2275 } 2276 return *this; 2277} 2278 2279#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2280 2281template <class _Allocator> 2282_LIBCPP_INLINE_VISIBILITY inline 2283vector<bool, _Allocator>::vector(vector&& __v) 2284 : __begin_(__v.__begin_), 2285 __size_(__v.__size_), 2286 __cap_alloc_(__v.__cap_alloc_) 2287{ 2288 __v.__begin_ = 0; 2289 __v.__size_ = 0; 2290 __v.__cap() = 0; 2291} 2292 2293template <class _Allocator> 2294vector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a) 2295 : __begin_(0), 2296 __size_(0), 2297 __cap_alloc_(0, __a) 2298{ 2299 if (__a == allocator_type(__v.__alloc())) 2300 { 2301 this->__begin_ = __v.__begin_; 2302 this->__size_ = __v.__size_; 2303 this->__cap() = __v.__cap(); 2304 __v.__begin_ = nullptr; 2305 __v.__cap() = __v.__size_ = 0; 2306 } 2307 else if (__v.size() > 0) 2308 { 2309 allocate(__v.size()); 2310 __construct_at_end(__v.begin(), __v.end()); 2311 } 2312} 2313 2314template <class _Allocator> 2315_LIBCPP_INLINE_VISIBILITY inline 2316vector<bool, _Allocator>& 2317vector<bool, _Allocator>::operator=(vector&& __v) 2318{ 2319 __move_assign(__v, integral_constant<bool, 2320 __storage_traits::propagate_on_container_move_assignment::value>()); 2321} 2322 2323template <class _Allocator> 2324void 2325vector<bool, _Allocator>::__move_assign(vector& __c, false_type) 2326{ 2327 if (__alloc() != __c.__alloc()) 2328 assign(__c.begin(), __c.end()); 2329 else 2330 __move_assign(__c, true_type()); 2331} 2332 2333template <class _Allocator> 2334void 2335vector<bool, _Allocator>::__move_assign(vector& __c, true_type) 2336{ 2337 deallocate(); 2338 this->__begin_ = __c.__begin_; 2339 this->__size_ = __c.__size_; 2340 this->__cap() = __c.__cap(); 2341 __move_assign_alloc(__c); 2342 __c.__begin_ = nullptr; 2343 __c.__cap() = __c.__size_ = 0; 2344} 2345 2346#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2347 2348template <class _Allocator> 2349void 2350vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) 2351{ 2352 __size_ = 0; 2353 if (__n > 0) 2354 { 2355 size_type __c = capacity(); 2356 if (__n <= __c) 2357 __size_ = __n; 2358 else 2359 { 2360 vector __v(__alloc()); 2361 __v.reserve(__recommend(__n)); 2362 __v.__size_ = __n; 2363 swap(__v); 2364 } 2365 _STD::fill_n(begin(), __n, __x); 2366 } 2367} 2368 2369template <class _Allocator> 2370template <class _InputIterator> 2371typename enable_if 2372< 2373 __is_input_iterator<_InputIterator>::value && 2374 !__is_forward_iterator<_InputIterator>::value, 2375 void 2376>::type 2377vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2378{ 2379 clear(); 2380 for (; __first != __last; ++__first) 2381 push_back(*__first); 2382} 2383 2384template <class _Allocator> 2385template <class _ForwardIterator> 2386typename enable_if 2387< 2388 __is_forward_iterator<_ForwardIterator>::value, 2389 void 2390>::type 2391vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2392{ 2393 clear(); 2394 difference_type __n = _STD::distance(__first, __last); 2395 if (__n) 2396 { 2397 if (__n > capacity()) 2398 { 2399 deallocate(); 2400 allocate(__n); 2401 } 2402 __construct_at_end(__first, __last); 2403 } 2404} 2405 2406template <class _Allocator> 2407void 2408vector<bool, _Allocator>::reserve(size_type __n) 2409{ 2410 if (__n > capacity()) 2411 { 2412 vector __v(this->__alloc()); 2413 __v.allocate(__n); 2414 __v.__construct_at_end(this->begin(), this->end()); 2415 swap(__v); 2416 __invalidate_all_iterators(); 2417 } 2418} 2419 2420template <class _Allocator> 2421void 2422vector<bool, _Allocator>::shrink_to_fit() 2423{ 2424 if (__external_cap_to_internal(size()) > __cap()) 2425 { 2426#ifndef _LIBCPP_NO_EXCEPTIONS 2427 try 2428 { 2429#endif // _LIBCPP_NO_EXCEPTIONS 2430 vector(*this, allocator_type(__alloc())).swap(*this); 2431#ifndef _LIBCPP_NO_EXCEPTIONS 2432 } 2433 catch (...) 2434 { 2435 } 2436#endif // _LIBCPP_NO_EXCEPTIONS 2437 } 2438} 2439 2440template <class _Allocator> 2441typename vector<bool, _Allocator>::reference 2442vector<bool, _Allocator>::at(size_type __n) 2443{ 2444 if (__n >= size()) 2445 this->__throw_out_of_range(); 2446 return (*this)[__n]; 2447} 2448 2449template <class _Allocator> 2450typename vector<bool, _Allocator>::const_reference 2451vector<bool, _Allocator>::at(size_type __n) const 2452{ 2453 if (__n >= size()) 2454 this->__throw_out_of_range(); 2455 return (*this)[__n]; 2456} 2457 2458template <class _Allocator> 2459void 2460vector<bool, _Allocator>::push_back(const value_type& __x) 2461{ 2462 if (this->__size_ == this->capacity()) 2463 reserve(__recommend(this->__size_ + 1)); 2464 ++this->__size_; 2465 back() = __x; 2466} 2467 2468template <class _Allocator> 2469typename vector<bool, _Allocator>::iterator 2470vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) 2471{ 2472 iterator __r; 2473 if (size() < capacity()) 2474 { 2475 const_iterator __old_end = end(); 2476 ++__size_; 2477 _STD::copy_backward(__position, __old_end, end()); 2478 __r = __const_iterator_cast(__position); 2479 } 2480 else 2481 { 2482 vector __v(__alloc()); 2483 __v.reserve(__recommend(__size_ + 1)); 2484 __v.__size_ = __size_ + 1; 2485 __r = _STD::copy(cbegin(), __position, __v.begin()); 2486 _STD::copy_backward(__position, cend(), __v.end()); 2487 swap(__v); 2488 } 2489 *__r = __x; 2490 return __r; 2491} 2492 2493template <class _Allocator> 2494typename vector<bool, _Allocator>::iterator 2495vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) 2496{ 2497 iterator __r; 2498 size_type __c = capacity(); 2499 if (__n <= __c && size() <= __c - __n) 2500 { 2501 const_iterator __old_end = end(); 2502 __size_ += __n; 2503 _STD::copy_backward(__position, __old_end, end()); 2504 __r = __const_iterator_cast(__position); 2505 } 2506 else 2507 { 2508 vector __v(__alloc()); 2509 __v.reserve(__recommend(__size_ + __n)); 2510 __v.__size_ = __size_ + __n; 2511 __r = _STD::copy(cbegin(), __position, __v.begin()); 2512 _STD::copy_backward(__position, cend(), __v.end()); 2513 swap(__v); 2514 } 2515 _STD::fill_n(__r, __n, __x); 2516 return __r; 2517} 2518 2519template <class _Allocator> 2520template <class _InputIterator> 2521typename enable_if 2522< 2523 __is_input_iterator <_InputIterator>::value && 2524 !__is_forward_iterator<_InputIterator>::value, 2525 typename vector<bool, _Allocator>::iterator 2526>::type 2527vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 2528{ 2529 difference_type __off = __position - begin(); 2530 iterator __p = __const_iterator_cast(__position); 2531 iterator __old_end = end(); 2532 for (; size() != capacity() && __first != __last; ++__first) 2533 { 2534 ++this->__size_; 2535 back() = *__first; 2536 } 2537 vector __v(__alloc()); 2538 if (__first != __last) 2539 { 2540#ifndef _LIBCPP_NO_EXCEPTIONS 2541 try 2542 { 2543#endif // _LIBCPP_NO_EXCEPTIONS 2544 __v.assign(__first, __last); 2545 difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 2546 difference_type __old_p = __p - begin(); 2547 reserve(__recommend(size() + __v.size())); 2548 __p = begin() + __old_p; 2549 __old_end = begin() + __old_size; 2550#ifndef _LIBCPP_NO_EXCEPTIONS 2551 } 2552 catch (...) 2553 { 2554 erase(__old_end, end()); 2555 throw; 2556 } 2557#endif // _LIBCPP_NO_EXCEPTIONS 2558 } 2559 __p = _STD::rotate(__p, __old_end, end()); 2560 insert(__p, __v.begin(), __v.end()); 2561 return begin() + __off; 2562} 2563 2564template <class _Allocator> 2565template <class _ForwardIterator> 2566typename enable_if 2567< 2568 __is_forward_iterator<_ForwardIterator>::value, 2569 typename vector<bool, _Allocator>::iterator 2570>::type 2571vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 2572{ 2573 difference_type __n = _STD::distance(__first, __last); 2574 iterator __r; 2575 size_type __c = capacity(); 2576 if (__n <= __c && size() <= __c - __n) 2577 { 2578 const_iterator __old_end = end(); 2579 __size_ += __n; 2580 _STD::copy_backward(__position, __old_end, end()); 2581 __r = __const_iterator_cast(__position); 2582 } 2583 else 2584 { 2585 vector __v(__alloc()); 2586 __v.reserve(__recommend(__size_ + __n)); 2587 __v.__size_ = __size_ + __n; 2588 __r = _STD::copy(cbegin(), __position, __v.begin()); 2589 _STD::copy_backward(__position, cend(), __v.end()); 2590 swap(__v); 2591 } 2592 _STD::copy(__first, __last, __r); 2593 return __r; 2594} 2595 2596template <class _Allocator> 2597_LIBCPP_INLINE_VISIBILITY inline 2598typename vector<bool, _Allocator>::iterator 2599vector<bool, _Allocator>::erase(const_iterator __position) 2600{ 2601 iterator __r = __const_iterator_cast(__position); 2602 _STD::copy(__position + 1, this->cend(), __r); 2603 --__size_; 2604 return __r; 2605} 2606 2607template <class _Allocator> 2608typename vector<bool, _Allocator>::iterator 2609vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) 2610{ 2611 iterator __r = __const_iterator_cast(__first); 2612 difference_type __d = __last - __first; 2613 _STD::copy(__last, this->cend(), __r); 2614 __size_ -= __d; 2615 return __r; 2616} 2617 2618template <class _Allocator> 2619void 2620vector<bool, _Allocator>::swap(vector& __x) 2621{ 2622 _STD::swap(this->__begin_, __x.__begin_); 2623 _STD::swap(this->__size_, __x.__size_); 2624 _STD::swap(this->__cap(), __x.__cap()); 2625 __swap_alloc(this->__alloc(), __x.__alloc()); 2626#ifdef _LIBCPP_DEBUG 2627 iterator::swap(this, &__x); 2628 const_iterator::swap(this, &__x); 2629#endif // _LIBCPP_DEBUG 2630} 2631 2632template <class _Allocator> 2633void 2634vector<bool, _Allocator>::resize(size_type __sz, value_type __x) 2635{ 2636 size_type __cs = size(); 2637 if (__cs < __sz) 2638 { 2639 iterator __r; 2640 size_type __c = capacity(); 2641 size_type __n = __sz - __cs; 2642 if (__n <= __c && __cs <= __c - __n) 2643 { 2644 __r = end(); 2645 __size_ += __n; 2646 } 2647 else 2648 { 2649 vector __v(__alloc()); 2650 __v.reserve(__recommend(__size_ + __n)); 2651 __v.__size_ = __size_ + __n; 2652 __r = _STD::copy(cbegin(), cend(), __v.begin()); 2653 swap(__v); 2654 } 2655 _STD::fill_n(__r, __n, __x); 2656 } 2657 else 2658 __size_ = __sz; 2659} 2660 2661template <class _Allocator> 2662void 2663vector<bool, _Allocator>::flip() 2664{ 2665 // do middle whole words 2666 size_type __n = __size_; 2667 __storage_pointer __p = __begin_; 2668 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 2669 *__p = ~*__p; 2670 // do last partial word 2671 if (__n > 0) 2672 { 2673 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2674 __storage_type __b = *__p & __m; 2675 *__p &= ~__m; 2676 *__p |= ~__b & __m; 2677 } 2678} 2679 2680template <class _Allocator> 2681bool 2682vector<bool, _Allocator>::__invariants() const 2683{ 2684 if (this->__begin_ == 0) 2685 { 2686 if (this->__size_ != 0 || this->__cap() != 0) 2687 return false; 2688 } 2689 else 2690 { 2691 if (this->__cap() == 0) 2692 return false; 2693 if (this->__size_ > this->capacity()) 2694 return false; 2695 } 2696 return true; 2697} 2698 2699template <class _Allocator> 2700size_t 2701vector<bool, _Allocator>::__hash_code() const 2702{ 2703 size_t __h = 0; 2704 // do middle whole words 2705 size_type __n = __size_; 2706 __storage_pointer __p = __begin_; 2707 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 2708 __h ^= *__p; 2709 // do last partial word 2710 if (__n > 0) 2711 { 2712 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2713 __h ^= *__p & __m; 2714 } 2715 return __h; 2716} 2717 2718template <class _Allocator> 2719struct _LIBCPP_VISIBLE hash<vector<bool, _Allocator> > 2720 : public unary_function<vector<bool, _Allocator>, size_t> 2721{ 2722 _LIBCPP_INLINE_VISIBILITY 2723 size_t operator()(const vector<bool, _Allocator>& __vec) const 2724 {return __vec.__hash_code();} 2725}; 2726 2727template <class _Tp, class _Allocator> 2728_LIBCPP_INLINE_VISIBILITY inline 2729bool 2730operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 2731{ 2732 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 2733 return __sz == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin()); 2734} 2735 2736template <class _Tp, class _Allocator> 2737_LIBCPP_INLINE_VISIBILITY inline 2738bool 2739operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 2740{ 2741 return !(__x == __y); 2742} 2743 2744template <class _Tp, class _Allocator> 2745_LIBCPP_INLINE_VISIBILITY inline 2746bool 2747operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 2748{ 2749 return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2750} 2751 2752template <class _Tp, class _Allocator> 2753_LIBCPP_INLINE_VISIBILITY inline 2754bool 2755operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 2756{ 2757 return __y < __x; 2758} 2759 2760template <class _Tp, class _Allocator> 2761_LIBCPP_INLINE_VISIBILITY inline 2762bool 2763operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 2764{ 2765 return !(__x < __y); 2766} 2767 2768template <class _Tp, class _Allocator> 2769_LIBCPP_INLINE_VISIBILITY inline 2770bool 2771operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 2772{ 2773 return !(__y < __x); 2774} 2775 2776template <class _Tp, class _Allocator> 2777_LIBCPP_INLINE_VISIBILITY inline 2778void 2779swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) 2780{ 2781 __x.swap(__y); 2782} 2783 2784_LIBCPP_END_NAMESPACE_STD 2785 2786#endif // _LIBCPP_VECTOR 2787