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