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