1// -*- C++ -*- 2//===----------------------------------------------------------------------===// 3// 4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 5// See https://llvm.org/LICENSE.txt for license information. 6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7// 8//===----------------------------------------------------------------------===// 9 10#ifndef _LIBCPP___CXX03_VECTOR 11#define _LIBCPP___CXX03_VECTOR 12 13// clang-format off 14 15/* 16 vector synopsis 17 18namespace std 19{ 20 21template <class T, class Allocator = allocator<T> > 22class vector 23{ 24public: 25 typedef T value_type; 26 typedef Allocator allocator_type; 27 typedef typename allocator_type::reference reference; 28 typedef typename allocator_type::const_reference const_reference; 29 typedef implementation-defined iterator; 30 typedef implementation-defined const_iterator; 31 typedef typename allocator_type::size_type size_type; 32 typedef typename allocator_type::difference_type difference_type; 33 typedef typename allocator_type::pointer pointer; 34 typedef typename allocator_type::const_pointer const_pointer; 35 typedef std::reverse_iterator<iterator> reverse_iterator; 36 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 37 38 vector() 39 noexcept(is_nothrow_default_constructible<allocator_type>::value); 40 explicit vector(const allocator_type&); 41 explicit vector(size_type n); 42 explicit vector(size_type n, const allocator_type&); // C++14 43 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 44 template <class InputIterator> 45 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 46 template<container-compatible-range<T> R> 47 constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 48 vector(const vector& x); 49 vector(vector&& x) 50 noexcept(is_nothrow_move_constructible<allocator_type>::value); 51 vector(initializer_list<value_type> il); 52 vector(initializer_list<value_type> il, const allocator_type& a); 53 ~vector(); 54 vector& operator=(const vector& x); 55 vector& operator=(vector&& x) 56 noexcept( 57 allocator_type::propagate_on_container_move_assignment::value || 58 allocator_type::is_always_equal::value); // C++17 59 vector& operator=(initializer_list<value_type> il); 60 template <class InputIterator> 61 void assign(InputIterator first, InputIterator last); 62 template<container-compatible-range<T> R> 63 constexpr void assign_range(R&& rg); // C++23 64 void assign(size_type n, const value_type& u); 65 void assign(initializer_list<value_type> il); 66 67 allocator_type get_allocator() const noexcept; 68 69 iterator begin() noexcept; 70 const_iterator begin() const noexcept; 71 iterator end() noexcept; 72 const_iterator end() const noexcept; 73 74 reverse_iterator rbegin() noexcept; 75 const_reverse_iterator rbegin() const noexcept; 76 reverse_iterator rend() noexcept; 77 const_reverse_iterator rend() const noexcept; 78 79 const_iterator cbegin() const noexcept; 80 const_iterator cend() const noexcept; 81 const_reverse_iterator crbegin() const noexcept; 82 const_reverse_iterator crend() const noexcept; 83 84 size_type size() const noexcept; 85 size_type max_size() const noexcept; 86 size_type capacity() const noexcept; 87 bool empty() const noexcept; 88 void reserve(size_type n); 89 void shrink_to_fit() noexcept; 90 91 reference operator[](size_type n); 92 const_reference operator[](size_type n) const; 93 reference at(size_type n); 94 const_reference at(size_type n) const; 95 96 reference front(); 97 const_reference front() const; 98 reference back(); 99 const_reference back() const; 100 101 value_type* data() noexcept; 102 const value_type* data() const noexcept; 103 104 void push_back(const value_type& x); 105 void push_back(value_type&& x); 106 template <class... Args> 107 reference emplace_back(Args&&... args); // reference in C++17 108 template<container-compatible-range<T> R> 109 constexpr void append_range(R&& rg); // C++23 110 void pop_back(); 111 112 template <class... Args> iterator emplace(const_iterator position, Args&&... args); 113 iterator insert(const_iterator position, const value_type& x); 114 iterator insert(const_iterator position, value_type&& x); 115 iterator insert(const_iterator position, size_type n, const value_type& x); 116 template <class InputIterator> 117 iterator insert(const_iterator position, InputIterator first, InputIterator last); 118 template<container-compatible-range<T> R> 119 constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 120 iterator insert(const_iterator position, initializer_list<value_type> il); 121 122 iterator erase(const_iterator position); 123 iterator erase(const_iterator first, const_iterator last); 124 125 void clear() noexcept; 126 127 void resize(size_type sz); 128 void resize(size_type sz, const value_type& c); 129 130 void swap(vector&) 131 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value || 132 allocator_traits<allocator_type>::is_always_equal::value); // C++17 133 134 bool __invariants() const; 135}; 136 137template <class Allocator = allocator<T> > 138class vector<bool, Allocator> 139{ 140public: 141 typedef bool value_type; 142 typedef Allocator allocator_type; 143 typedef implementation-defined iterator; 144 typedef implementation-defined const_iterator; 145 typedef typename allocator_type::size_type size_type; 146 typedef typename allocator_type::difference_type difference_type; 147 typedef iterator pointer; 148 typedef const_iterator const_pointer; 149 typedef std::reverse_iterator<iterator> reverse_iterator; 150 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 151 152 class reference 153 { 154 public: 155 reference(const reference&) noexcept; 156 operator bool() const noexcept; 157 reference& operator=(bool x) noexcept; 158 reference& operator=(const reference& x) noexcept; 159 iterator operator&() const noexcept; 160 void flip() noexcept; 161 }; 162 163 class const_reference 164 { 165 public: 166 const_reference(const reference&) noexcept; 167 operator bool() const noexcept; 168 const_iterator operator&() const noexcept; 169 }; 170 171 vector() 172 noexcept(is_nothrow_default_constructible<allocator_type>::value); 173 explicit vector(const allocator_type&); 174 explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14 175 vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 176 template <class InputIterator> 177 vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 178 template<container-compatible-range<bool> R> 179 constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); 180 vector(const vector& x); 181 vector(vector&& x) 182 noexcept(is_nothrow_move_constructible<allocator_type>::value); 183 vector(initializer_list<value_type> il); 184 vector(initializer_list<value_type> il, const allocator_type& a); 185 ~vector(); 186 vector& operator=(const vector& x); 187 vector& operator=(vector&& x) 188 noexcept( 189 allocator_type::propagate_on_container_move_assignment::value || 190 allocator_type::is_always_equal::value); // C++17 191 vector& operator=(initializer_list<value_type> il); 192 template <class InputIterator> 193 void assign(InputIterator first, InputIterator last); 194 template<container-compatible-range<T> R> 195 constexpr void assign_range(R&& rg); // C++23 196 void assign(size_type n, const value_type& u); 197 void assign(initializer_list<value_type> il); 198 199 allocator_type get_allocator() const noexcept; 200 201 iterator begin() noexcept; 202 const_iterator begin() const noexcept; 203 iterator end() noexcept; 204 const_iterator end() const noexcept; 205 206 reverse_iterator rbegin() noexcept; 207 const_reverse_iterator rbegin() const noexcept; 208 reverse_iterator rend() noexcept; 209 const_reverse_iterator rend() const noexcept; 210 211 const_iterator cbegin() const noexcept; 212 const_iterator cend() const noexcept; 213 const_reverse_iterator crbegin() const noexcept; 214 const_reverse_iterator crend() const noexcept; 215 216 size_type size() const noexcept; 217 size_type max_size() const noexcept; 218 size_type capacity() const noexcept; 219 bool empty() const noexcept; 220 void reserve(size_type n); 221 void shrink_to_fit() noexcept; 222 223 reference operator[](size_type n); 224 const_reference operator[](size_type n) const; 225 reference at(size_type n); 226 const_reference at(size_type n) const; 227 228 reference front(); 229 const_reference front() const; 230 reference back(); 231 const_reference back() const; 232 233 void push_back(const value_type& x); 234 template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17 235 template<container-compatible-range<T> R> 236 constexpr void append_range(R&& rg); // C++23 237 void pop_back(); 238 239 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14 240 iterator insert(const_iterator position, const value_type& x); 241 iterator insert(const_iterator position, size_type n, const value_type& x); 242 template <class InputIterator> 243 iterator insert(const_iterator position, InputIterator first, InputIterator last); 244 template<container-compatible-range<T> R> 245 constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 246 iterator insert(const_iterator position, initializer_list<value_type> il); 247 248 iterator erase(const_iterator position); 249 iterator erase(const_iterator first, const_iterator last); 250 251 void clear() noexcept; 252 253 void resize(size_type sz); 254 void resize(size_type sz, value_type x); 255 256 void swap(vector&) 257 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value || 258 allocator_traits<allocator_type>::is_always_equal::value); // C++17 259 void flip() noexcept; 260 261 bool __invariants() const; 262}; 263 264template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>> 265 vector(InputIterator, InputIterator, Allocator = Allocator()) 266 -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 267 268template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> 269 vector(from_range_t, R&&, Allocator = Allocator()) 270 -> vector<ranges::range_value_t<R>, Allocator>; // C++23 271 272template <class Allocator> struct hash<std::vector<bool, Allocator>>; 273 274template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // constexpr since C++20 275template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20 276template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20 277template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20 278template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20 279template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); // removed in C++20 280template <class T, class Allocator> constexpr 281 constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x, 282 const vector<T, Allocator>& y); // since C++20 283 284template <class T, class Allocator> 285void swap(vector<T,Allocator>& x, vector<T,Allocator>& y) 286 noexcept(noexcept(x.swap(y))); 287 288template <class T, class Allocator, class U> 289typename vector<T, Allocator>::size_type 290erase(vector<T, Allocator>& c, const U& value); // since C++20 291template <class T, class Allocator, class Predicate> 292typename vector<T, Allocator>::size_type 293erase_if(vector<T, Allocator>& c, Predicate pred); // since C++20 294 295 296template<class T> 297 inline constexpr bool is-vector-bool-reference = see below; // exposition only, since C++23 298 299template<class T, class charT> requires is-vector-bool-reference<T> // Since C++23 300 struct formatter<T, charT>; 301 302} // std 303 304*/ 305 306// clang-format on 307 308#include <__cxx03/__algorithm/copy.h> 309#include <__cxx03/__algorithm/equal.h> 310#include <__cxx03/__algorithm/fill_n.h> 311#include <__cxx03/__algorithm/iterator_operations.h> 312#include <__cxx03/__algorithm/lexicographical_compare.h> 313#include <__cxx03/__algorithm/remove.h> 314#include <__cxx03/__algorithm/remove_if.h> 315#include <__cxx03/__algorithm/rotate.h> 316#include <__cxx03/__algorithm/unwrap_iter.h> 317#include <__cxx03/__assert> 318#include <__cxx03/__bit_reference> 319#include <__cxx03/__config> 320#include <__cxx03/__debug_utils/sanitizers.h> 321#include <__cxx03/__functional/hash.h> 322#include <__cxx03/__functional/unary_function.h> 323#include <__cxx03/__fwd/vector.h> 324#include <__cxx03/__iterator/advance.h> 325#include <__cxx03/__iterator/bounded_iter.h> 326#include <__cxx03/__iterator/distance.h> 327#include <__cxx03/__iterator/iterator_traits.h> 328#include <__cxx03/__iterator/reverse_iterator.h> 329#include <__cxx03/__iterator/wrap_iter.h> 330#include <__cxx03/__memory/addressof.h> 331#include <__cxx03/__memory/allocate_at_least.h> 332#include <__cxx03/__memory/allocator_traits.h> 333#include <__cxx03/__memory/pointer_traits.h> 334#include <__cxx03/__memory/swap_allocator.h> 335#include <__cxx03/__memory/temp_value.h> 336#include <__cxx03/__memory/uninitialized_algorithms.h> 337#include <__cxx03/__split_buffer> 338#include <__cxx03/__type_traits/is_allocator.h> 339#include <__cxx03/__type_traits/is_constructible.h> 340#include <__cxx03/__type_traits/is_nothrow_assignable.h> 341#include <__cxx03/__type_traits/noexcept_move_assign_container.h> 342#include <__cxx03/__type_traits/type_identity.h> 343#include <__cxx03/__utility/exception_guard.h> 344#include <__cxx03/__utility/forward.h> 345#include <__cxx03/__utility/is_pointer_in_range.h> 346#include <__cxx03/__utility/move.h> 347#include <__cxx03/__utility/pair.h> 348#include <__cxx03/__utility/swap.h> 349#include <__cxx03/climits> 350#include <__cxx03/cstring> 351#include <__cxx03/limits> 352#include <__cxx03/stdexcept> 353#include <__cxx03/version> 354 355// standard-mandated includes 356 357// [iterator.range] 358#include <__cxx03/__iterator/access.h> 359 360#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 361# pragma GCC system_header 362#endif 363 364_LIBCPP_PUSH_MACROS 365#include <__cxx03/__undef_macros> 366 367_LIBCPP_BEGIN_NAMESPACE_STD 368 369template <class _Tp, class _Allocator /* = allocator<_Tp> */> 370class _LIBCPP_TEMPLATE_VIS vector { 371private: 372 typedef allocator<_Tp> __default_allocator_type; 373 374public: 375 typedef vector __self; 376 typedef _Tp value_type; 377 typedef _Allocator allocator_type; 378 typedef allocator_traits<allocator_type> __alloc_traits; 379 typedef value_type& reference; 380 typedef const value_type& const_reference; 381 typedef typename __alloc_traits::size_type size_type; 382 typedef typename __alloc_traits::difference_type difference_type; 383 typedef typename __alloc_traits::pointer pointer; 384 typedef typename __alloc_traits::const_pointer const_pointer; 385#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR 386 // Users might provide custom allocators, and prior to C++20 we have no existing way to detect whether the allocator's 387 // pointer type is contiguous (though it has to be by the Standard). Using the wrapper type ensures the iterator is 388 // considered contiguous. 389 typedef __bounded_iter<__wrap_iter<pointer>> iterator; 390 typedef __bounded_iter<__wrap_iter<const_pointer>> const_iterator; 391#else 392 typedef __wrap_iter<pointer> iterator; 393 typedef __wrap_iter<const_pointer> const_iterator; 394#endif 395 typedef std::reverse_iterator<iterator> reverse_iterator; 396 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 397 398 // A vector containers the following members which may be trivially relocatable: 399 // - pointer: may be trivially relocatable, so it's checked 400 // - allocator_type: may be trivially relocatable, so it's checked 401 // vector doesn't contain any self-references, so it's trivially relocatable if its members are. 402 using __trivially_relocatable = __conditional_t< 403 __libcpp_is_trivially_relocatable<pointer>::value && __libcpp_is_trivially_relocatable<allocator_type>::value, 404 vector, 405 void>; 406 407 static_assert(__check_valid_allocator<allocator_type>::value, ""); 408 static_assert(is_same<typename allocator_type::value_type, value_type>::value, 409 "Allocator::value_type must be same type as value_type"); 410 411 _LIBCPP_HIDE_FROM_ABI vector() {} 412 _LIBCPP_HIDE_FROM_ABI explicit vector(const allocator_type& __a) : __end_cap_(nullptr, __a) {} 413 414 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n) { 415 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 416 if (__n > 0) { 417 __vallocate(__n); 418 __construct_at_end(__n); 419 } 420 __guard.__complete(); 421 } 422 423 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __x) { 424 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 425 if (__n > 0) { 426 __vallocate(__n); 427 __construct_at_end(__n, __x); 428 } 429 __guard.__complete(); 430 } 431 432 template <__enable_if_t<__is_allocator<_Allocator>::value, int> = 0> 433 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __x, const allocator_type& __a) 434 : __end_cap_(nullptr, __a) { 435 if (__n > 0) { 436 __vallocate(__n); 437 __construct_at_end(__n, __x); 438 } 439 } 440 441 template <class _InputIterator, 442 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 443 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value, 444 int> = 0> 445 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last); 446 template <class _InputIterator, 447 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 448 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value, 449 int> = 0> 450 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a); 451 452 template < 453 class _ForwardIterator, 454 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 455 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value, 456 int> = 0> 457 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last); 458 459 template < 460 class _ForwardIterator, 461 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 462 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value, 463 int> = 0> 464 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a); 465 466private: 467 class __destroy_vector { 468 public: 469 _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {} 470 471 _LIBCPP_HIDE_FROM_ABI void operator()() { 472 if (__vec_.__begin_ != nullptr) { 473 __vec_.__clear(); 474 __vec_.__annotate_delete(); 475 __alloc_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.capacity()); 476 } 477 } 478 479 private: 480 vector& __vec_; 481 }; 482 483public: 484 _LIBCPP_HIDE_FROM_ABI ~vector() { __destroy_vector (*this)(); } 485 486 _LIBCPP_HIDE_FROM_ABI vector(const vector& __x); 487 _LIBCPP_HIDE_FROM_ABI vector(const vector& __x, const __type_identity_t<allocator_type>& __a); 488 _LIBCPP_HIDE_FROM_ABI vector& operator=(const vector& __x); 489 490 _LIBCPP_HIDE_FROM_ABI vector(vector&& __x); 491 492 _LIBCPP_HIDE_FROM_ABI vector(vector&& __x, const __type_identity_t<allocator_type>& __a); 493 _LIBCPP_HIDE_FROM_ABI vector& operator=(vector&& __x); 494 495 template <class _InputIterator, 496 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 497 is_constructible<value_type, typename iterator_traits<_InputIterator>::reference>::value, 498 int> = 0> 499 _LIBCPP_HIDE_FROM_ABI void assign(_InputIterator __first, _InputIterator __last); 500 template < 501 class _ForwardIterator, 502 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 503 is_constructible<value_type, typename iterator_traits<_ForwardIterator>::reference>::value, 504 int> = 0> 505 _LIBCPP_HIDE_FROM_ABI void assign(_ForwardIterator __first, _ForwardIterator __last); 506 507 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const_reference __u); 508 509 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return this->__alloc(); } 510 511 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT; 512 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT; 513 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT; 514 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT; 515 516 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 517 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 518 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 519 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 520 521 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); } 522 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); } 523 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 524 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 525 526 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { 527 return static_cast<size_type>(this->__end_ - this->__begin_); 528 } 529 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT { 530 return static_cast<size_type>(__end_cap() - this->__begin_); 531 } 532 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return this->__begin_ == this->__end_; } 533 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT; 534 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n); 535 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT; 536 537 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) _NOEXCEPT; 538 _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __n) const _NOEXCEPT; 539 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n); 540 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const; 541 542 _LIBCPP_HIDE_FROM_ABI reference front() _NOEXCEPT { 543 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector"); 544 return *this->__begin_; 545 } 546 _LIBCPP_HIDE_FROM_ABI const_reference front() const _NOEXCEPT { 547 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "front() called on an empty vector"); 548 return *this->__begin_; 549 } 550 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { 551 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector"); 552 return *(this->__end_ - 1); 553 } 554 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT { 555 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "back() called on an empty vector"); 556 return *(this->__end_ - 1); 557 } 558 559 _LIBCPP_HIDE_FROM_ABI value_type* data() _NOEXCEPT { return std::__to_address(this->__begin_); } 560 _LIBCPP_HIDE_FROM_ABI const value_type* data() const _NOEXCEPT { return std::__to_address(this->__begin_); } 561 562 _LIBCPP_HIDE_FROM_ABI void push_back(const_reference __x); 563 564 _LIBCPP_HIDE_FROM_ABI void push_back(value_type&& __x); 565 566 template <class... _Args> 567 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args); 568 569 _LIBCPP_HIDE_FROM_ABI void pop_back(); 570 571 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, const_reference __x); 572 573 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, value_type&& __x); 574 template <class... _Args> 575 _LIBCPP_HIDE_FROM_ABI iterator emplace(const_iterator __position, _Args&&... __args); 576 577 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, size_type __n, const_reference __x); 578 579 template <class _InputIterator, 580 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 581 is_constructible< value_type, typename iterator_traits<_InputIterator>::reference>::value, 582 int> = 0> 583 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 584 585 template < 586 class _ForwardIterator, 587 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 588 is_constructible< value_type, typename iterator_traits<_ForwardIterator>::reference>::value, 589 int> = 0> 590 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 591 592 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position); 593 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last); 594 595 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { 596 size_type __old_size = size(); 597 __clear(); 598 __annotate_shrink(__old_size); 599 } 600 601 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz); 602 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz, const_reference __x); 603 604 _LIBCPP_HIDE_FROM_ABI void swap(vector&); 605 606 _LIBCPP_HIDE_FROM_ABI bool __invariants() const; 607 608private: 609 pointer __begin_ = nullptr; 610 pointer __end_ = nullptr; 611 __compressed_pair<pointer, allocator_type> __end_cap_ = 612 __compressed_pair<pointer, allocator_type>(nullptr, __default_init_tag()); 613 614 // Allocate space for __n objects 615 // throws length_error if __n > max_size() 616 // throws (probably bad_alloc) if memory run out 617 // Precondition: __begin_ == __end_ == __end_cap() == 0 618 // Precondition: __n > 0 619 // Postcondition: capacity() >= __n 620 // Postcondition: size() == 0 621 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) { 622 if (__n > max_size()) 623 __throw_length_error(); 624 auto __allocation = std::__allocate_at_least(__alloc(), __n); 625 __begin_ = __allocation.ptr; 626 __end_ = __allocation.ptr; 627 __end_cap() = __begin_ + __allocation.count; 628 __annotate_new(0); 629 } 630 631 _LIBCPP_HIDE_FROM_ABI void __vdeallocate() _NOEXCEPT; 632 _LIBCPP_HIDE_FROM_ABI size_type __recommend(size_type __new_size) const; 633 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n); 634 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x); 635 636 template <class _InputIterator, class _Sentinel> 637 _LIBCPP_HIDE_FROM_ABI void __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) { 638 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 639 640 if (__n > 0) { 641 __vallocate(__n); 642 __construct_at_end(__first, __last, __n); 643 } 644 645 __guard.__complete(); 646 } 647 648 template <class _InputIterator, class _Sentinel> 649 _LIBCPP_HIDE_FROM_ABI void __init_with_sentinel(_InputIterator __first, _Sentinel __last) { 650 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 651 652 for (; __first != __last; ++__first) 653 emplace_back(*__first); 654 655 __guard.__complete(); 656 } 657 658 template <class _Iterator, class _Sentinel> 659 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last); 660 661 template <class _ForwardIterator, class _Sentinel> 662 _LIBCPP_HIDE_FROM_ABI void __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n); 663 664 template <class _InputIterator, class _Sentinel> 665 _LIBCPP_HIDE_FROM_ABI iterator 666 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); 667 668 template <class _Iterator, class _Sentinel> 669 _LIBCPP_HIDE_FROM_ABI iterator 670 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); 671 672 template <class _InputIterator, class _Sentinel> 673 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n); 674 675 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n); 676 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const_reference __x); 677 678 _LIBCPP_HIDE_FROM_ABI iterator __make_iter(pointer __p) _NOEXCEPT { 679#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR 680 // Bound the iterator according to the capacity, rather than the size. 681 // 682 // Vector guarantees that iterators stay valid as long as no reallocation occurs even if new elements are inserted 683 // into the container; for these cases, we need to make sure that the newly-inserted elements can be accessed 684 // through the bounded iterator without failing checks. The downside is that the bounded iterator won't catch 685 // access that is logically out-of-bounds, i.e., goes beyond the size, but is still within the capacity. With the 686 // current implementation, there is no connection between a bounded iterator and its associated container, so we 687 // don't have a way to update existing valid iterators when the container is resized and thus have to go with 688 // a laxer approach. 689 return std::__make_bounded_iter( 690 std::__wrap_iter<pointer>(__p), 691 std::__wrap_iter<pointer>(this->__begin_), 692 std::__wrap_iter<pointer>(this->__end_cap())); 693#else 694 return iterator(__p); 695#endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR 696 } 697 698 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(const_pointer __p) const _NOEXCEPT { 699#ifdef _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR 700 // Bound the iterator according to the capacity, rather than the size. 701 return std::__make_bounded_iter( 702 std::__wrap_iter<const_pointer>(__p), 703 std::__wrap_iter<const_pointer>(this->__begin_), 704 std::__wrap_iter<const_pointer>(this->__end_cap())); 705#else 706 return const_iterator(__p); 707#endif // _LIBCPP_ABI_BOUNDED_ITERATORS_IN_VECTOR 708 } 709 710 _LIBCPP_HIDE_FROM_ABI void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); 711 _LIBCPP_HIDE_FROM_ABI pointer 712 __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); 713 _LIBCPP_HIDE_FROM_ABI void __move_range(pointer __from_s, pointer __from_e, pointer __to); 714 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, true_type); 715 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, false_type); 716 _LIBCPP_HIDE_FROM_ABI void __destruct_at_end(pointer __new_last) _NOEXCEPT { 717 size_type __old_size = size(); 718 __base_destruct_at_end(__new_last); 719 __annotate_shrink(__old_size); 720 } 721 722 template <class _Up> 723 _LIBCPP_HIDE_FROM_ABI inline pointer __push_back_slow_path(_Up&& __x); 724 725 template <class... _Args> 726 _LIBCPP_HIDE_FROM_ABI inline pointer __emplace_back_slow_path(_Args&&... __args); 727 728 // The following functions are no-ops outside of AddressSanitizer mode. 729 // We call annotations for every allocator, unless explicitly disabled. 730 // 731 // To disable annotations for a particular allocator, change value of 732 // __asan_annotate_container_with_allocator to false. 733 // For more details, see the "Using libc++" documentation page or 734 // the documentation for __sanitizer_annotate_contiguous_container. 735 736 _LIBCPP_HIDE_FROM_ABI void __annotate_contiguous_container(const void* __old_mid, const void* __new_mid) const { 737 std::__annotate_contiguous_container<_Allocator>(data(), data() + capacity(), __old_mid, __new_mid); 738 } 739 740 _LIBCPP_HIDE_FROM_ABI void __annotate_new(size_type __current_size) const _NOEXCEPT { 741 (void)__current_size; 742#ifndef _LIBCPP_HAS_NO_ASAN 743 __annotate_contiguous_container(data() + capacity(), data() + __current_size); 744#endif 745 } 746 747 _LIBCPP_HIDE_FROM_ABI void __annotate_delete() const _NOEXCEPT { 748#ifndef _LIBCPP_HAS_NO_ASAN 749 __annotate_contiguous_container(data() + size(), data() + capacity()); 750#endif 751 } 752 753 _LIBCPP_HIDE_FROM_ABI void __annotate_increase(size_type __n) const _NOEXCEPT { 754 (void)__n; 755#ifndef _LIBCPP_HAS_NO_ASAN 756 __annotate_contiguous_container(data() + size(), data() + size() + __n); 757#endif 758 } 759 760 _LIBCPP_HIDE_FROM_ABI void __annotate_shrink(size_type __old_size) const _NOEXCEPT { 761 (void)__old_size; 762#ifndef _LIBCPP_HAS_NO_ASAN 763 __annotate_contiguous_container(data() + __old_size, data() + size()); 764#endif 765 } 766 767 struct _ConstructTransaction { 768 _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(vector& __v, size_type __n) 769 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) { 770#ifndef _LIBCPP_HAS_NO_ASAN 771 __v_.__annotate_increase(__n); 772#endif 773 } 774 775 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { 776 __v_.__end_ = __pos_; 777#ifndef _LIBCPP_HAS_NO_ASAN 778 if (__pos_ != __new_end_) { 779 __v_.__annotate_shrink(__new_end_ - __v_.__begin_); 780 } 781#endif 782 } 783 784 vector& __v_; 785 pointer __pos_; 786 const_pointer const __new_end_; 787 788 _ConstructTransaction(_ConstructTransaction const&) = delete; 789 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete; 790 }; 791 792 template <class... _Args> 793 _LIBCPP_HIDE_FROM_ABI void __construct_one_at_end(_Args&&... __args) { 794 _ConstructTransaction __tx(*this, 1); 795 __alloc_traits::construct(this->__alloc(), std::__to_address(__tx.__pos_), std::forward<_Args>(__args)...); 796 ++__tx.__pos_; 797 } 798 799 _LIBCPP_HIDE_FROM_ABI allocator_type& __alloc() _NOEXCEPT { return this->__end_cap_.second(); } 800 _LIBCPP_HIDE_FROM_ABI const allocator_type& __alloc() const _NOEXCEPT { return this->__end_cap_.second(); } 801 _LIBCPP_HIDE_FROM_ABI pointer& __end_cap() _NOEXCEPT { return this->__end_cap_.first(); } 802 _LIBCPP_HIDE_FROM_ABI const pointer& __end_cap() const _NOEXCEPT { return this->__end_cap_.first(); } 803 804 _LIBCPP_HIDE_FROM_ABI void __clear() _NOEXCEPT { __base_destruct_at_end(this->__begin_); } 805 806 _LIBCPP_HIDE_FROM_ABI void __base_destruct_at_end(pointer __new_last) _NOEXCEPT { 807 pointer __soon_to_be_end = this->__end_; 808 while (__new_last != __soon_to_be_end) 809 __alloc_traits::destroy(__alloc(), std::__to_address(--__soon_to_be_end)); 810 this->__end_ = __new_last; 811 } 812 813 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c) { 814 __copy_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_copy_assignment::value>()); 815 } 816 817 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c) { 818 __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>()); 819 } 820 821 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { std::__throw_length_error("vector"); } 822 823 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { std::__throw_out_of_range("vector"); } 824 825 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c, true_type) { 826 if (__alloc() != __c.__alloc()) { 827 __clear(); 828 __annotate_delete(); 829 __alloc_traits::deallocate(__alloc(), this->__begin_, capacity()); 830 this->__begin_ = this->__end_ = __end_cap() = nullptr; 831 } 832 __alloc() = __c.__alloc(); 833 } 834 835 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector&, false_type) {} 836 837 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c, true_type) { __alloc() = std::move(__c.__alloc()); } 838 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector&, false_type) _NOEXCEPT {} 839}; 840 841// __swap_out_circular_buffer relocates the objects in [__begin_, __end_) into the front of __v and swaps the buffers of 842// *this and __v. It is assumed that __v provides space for exactly (__end_ - __begin_) objects in the front. This 843// function has a strong exception guarantee. 844template <class _Tp, class _Allocator> 845void vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) { 846 __annotate_delete(); 847 auto __new_begin = __v.__begin_ - (__end_ - __begin_); 848 std::__uninitialized_allocator_relocate( 849 __alloc(), std::__to_address(__begin_), std::__to_address(__end_), std::__to_address(__new_begin)); 850 __v.__begin_ = __new_begin; 851 __end_ = __begin_; // All the objects have been destroyed by relocating them. 852 std::swap(this->__begin_, __v.__begin_); 853 std::swap(this->__end_, __v.__end_); 854 std::swap(this->__end_cap(), __v.__end_cap()); 855 __v.__first_ = __v.__begin_; 856 __annotate_new(size()); 857} 858 859// __swap_out_circular_buffer relocates the objects in [__begin_, __p) into the front of __v, the objects in 860// [__p, __end_) into the back of __v and swaps the buffers of *this and __v. It is assumed that __v provides space for 861// exactly (__p - __begin_) objects in the front and space for at least (__end_ - __p) objects in the back. This 862// function has a strong exception guarantee if __begin_ == __p || __end_ == __p. 863template <class _Tp, class _Allocator> 864typename vector<_Tp, _Allocator>::pointer 865vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) { 866 __annotate_delete(); 867 pointer __ret = __v.__begin_; 868 869 // Relocate [__p, __end_) first to avoid having a hole in [__begin_, __end_) 870 // in case something in [__begin_, __p) throws. 871 std::__uninitialized_allocator_relocate( 872 __alloc(), std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.__end_)); 873 __v.__end_ += (__end_ - __p); 874 __end_ = __p; // The objects in [__p, __end_) have been destroyed by relocating them. 875 auto __new_begin = __v.__begin_ - (__p - __begin_); 876 877 std::__uninitialized_allocator_relocate( 878 __alloc(), std::__to_address(__begin_), std::__to_address(__p), std::__to_address(__new_begin)); 879 __v.__begin_ = __new_begin; 880 __end_ = __begin_; // All the objects have been destroyed by relocating them. 881 882 std::swap(this->__begin_, __v.__begin_); 883 std::swap(this->__end_, __v.__end_); 884 std::swap(this->__end_cap(), __v.__end_cap()); 885 __v.__first_ = __v.__begin_; 886 __annotate_new(size()); 887 return __ret; 888} 889 890template <class _Tp, class _Allocator> 891void vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT { 892 if (this->__begin_ != nullptr) { 893 clear(); 894 __annotate_delete(); 895 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); 896 this->__begin_ = this->__end_ = this->__end_cap() = nullptr; 897 } 898} 899 900template <class _Tp, class _Allocator> 901typename vector<_Tp, _Allocator>::size_type vector<_Tp, _Allocator>::max_size() const _NOEXCEPT { 902 return std::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<difference_type>::max()); 903} 904 905// Precondition: __new_size > capacity() 906template <class _Tp, class _Allocator> 907inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::size_type 908vector<_Tp, _Allocator>::__recommend(size_type __new_size) const { 909 const size_type __ms = max_size(); 910 if (__new_size > __ms) 911 this->__throw_length_error(); 912 const size_type __cap = capacity(); 913 if (__cap >= __ms / 2) 914 return __ms; 915 return std::max<size_type>(2 * __cap, __new_size); 916} 917 918// Default constructs __n objects starting at __end_ 919// throws if construction throws 920// Precondition: __n > 0 921// Precondition: size() + __n <= capacity() 922// Postcondition: size() == size() + __n 923template <class _Tp, class _Allocator> 924void vector<_Tp, _Allocator>::__construct_at_end(size_type __n) { 925 _ConstructTransaction __tx(*this, __n); 926 const_pointer __new_end = __tx.__new_end_; 927 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) { 928 __alloc_traits::construct(this->__alloc(), std::__to_address(__pos)); 929 } 930} 931 932// Copy constructs __n objects starting at __end_ from __x 933// throws if construction throws 934// Precondition: __n > 0 935// Precondition: size() + __n <= capacity() 936// Postcondition: size() == old size() + __n 937// Postcondition: [i] == __x for all i in [size() - __n, __n) 938template <class _Tp, class _Allocator> 939inline void vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) { 940 _ConstructTransaction __tx(*this, __n); 941 const_pointer __new_end = __tx.__new_end_; 942 for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) { 943 __alloc_traits::construct(this->__alloc(), std::__to_address(__pos), __x); 944 } 945} 946 947template <class _Tp, class _Allocator> 948template <class _InputIterator, class _Sentinel> 949void vector<_Tp, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) { 950 _ConstructTransaction __tx(*this, __n); 951 __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_); 952} 953 954// Default constructs __n objects starting at __end_ 955// throws if construction throws 956// Postcondition: size() == size() + __n 957// Exception safety: strong. 958template <class _Tp, class _Allocator> 959void vector<_Tp, _Allocator>::__append(size_type __n) { 960 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 961 this->__construct_at_end(__n); 962 else { 963 allocator_type& __a = this->__alloc(); 964 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 965 __v.__construct_at_end(__n); 966 __swap_out_circular_buffer(__v); 967 } 968} 969 970// Default constructs __n objects starting at __end_ 971// throws if construction throws 972// Postcondition: size() == size() + __n 973// Exception safety: strong. 974template <class _Tp, class _Allocator> 975void vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) { 976 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 977 this->__construct_at_end(__n, __x); 978 else { 979 allocator_type& __a = this->__alloc(); 980 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 981 __v.__construct_at_end(__n, __x); 982 __swap_out_circular_buffer(__v); 983 } 984} 985 986template <class _Tp, class _Allocator> 987template <class _InputIterator, 988 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 989 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, 990 int> > 991vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last) { 992 __init_with_sentinel(__first, __last); 993} 994 995template <class _Tp, class _Allocator> 996template <class _InputIterator, 997 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 998 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, 999 int> > 1000vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a) 1001 : __end_cap_(nullptr, __a) { 1002 __init_with_sentinel(__first, __last); 1003} 1004 1005template <class _Tp, class _Allocator> 1006template <class _ForwardIterator, 1007 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 1008 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value, 1009 int> > 1010vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last) { 1011 size_type __n = static_cast<size_type>(std::distance(__first, __last)); 1012 __init_with_size(__first, __last, __n); 1013} 1014 1015template <class _Tp, class _Allocator> 1016template <class _ForwardIterator, 1017 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 1018 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value, 1019 int> > 1020vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a) 1021 : __end_cap_(nullptr, __a) { 1022 size_type __n = static_cast<size_type>(std::distance(__first, __last)); 1023 __init_with_size(__first, __last, __n); 1024} 1025 1026template <class _Tp, class _Allocator> 1027vector<_Tp, _Allocator>::vector(const vector& __x) 1028 : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc())) { 1029 __init_with_size(__x.__begin_, __x.__end_, __x.size()); 1030} 1031 1032template <class _Tp, class _Allocator> 1033vector<_Tp, _Allocator>::vector(const vector& __x, const __type_identity_t<allocator_type>& __a) 1034 : __end_cap_(nullptr, __a) { 1035 __init_with_size(__x.__begin_, __x.__end_, __x.size()); 1036} 1037 1038template <class _Tp, class _Allocator> 1039inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>::vector(vector&& __x) 1040 : __end_cap_(nullptr, std::move(__x.__alloc())) { 1041 this->__begin_ = __x.__begin_; 1042 this->__end_ = __x.__end_; 1043 this->__end_cap() = __x.__end_cap(); 1044 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1045} 1046 1047template <class _Tp, class _Allocator> 1048inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t<allocator_type>& __a) 1049 : __end_cap_(nullptr, __a) { 1050 if (__a == __x.__alloc()) { 1051 this->__begin_ = __x.__begin_; 1052 this->__end_ = __x.__end_; 1053 this->__end_cap() = __x.__end_cap(); 1054 __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1055 } else { 1056 typedef move_iterator<iterator> _Ip; 1057 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 1058 assign(_Ip(__x.begin()), _Ip(__x.end())); 1059 __guard.__complete(); 1060 } 1061} 1062 1063template <class _Tp, class _Allocator> 1064inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>& vector<_Tp, _Allocator>::operator=(vector&& __x) { 1065 __move_assign(__x, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>()); 1066 return *this; 1067} 1068 1069template <class _Tp, class _Allocator> 1070void vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) { 1071 if (__alloc() != __c.__alloc()) { 1072 typedef move_iterator<iterator> _Ip; 1073 assign(_Ip(__c.begin()), _Ip(__c.end())); 1074 } else 1075 __move_assign(__c, true_type()); 1076} 1077 1078template <class _Tp, class _Allocator> 1079void vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) { 1080 __vdeallocate(); 1081 __move_assign_alloc(__c); // this can throw 1082 this->__begin_ = __c.__begin_; 1083 this->__end_ = __c.__end_; 1084 this->__end_cap() = __c.__end_cap(); 1085 __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 1086} 1087 1088template <class _Tp, class _Allocator> 1089inline _LIBCPP_HIDE_FROM_ABI vector<_Tp, _Allocator>& vector<_Tp, _Allocator>::operator=(const vector& __x) { 1090 if (this != std::addressof(__x)) { 1091 __copy_assign_alloc(__x); 1092 assign(__x.__begin_, __x.__end_); 1093 } 1094 return *this; 1095} 1096 1097template <class _Tp, class _Allocator> 1098template <class _InputIterator, 1099 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 1100 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, 1101 int> > 1102void vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { 1103 __assign_with_sentinel(__first, __last); 1104} 1105 1106template <class _Tp, class _Allocator> 1107template <class _Iterator, class _Sentinel> 1108_LIBCPP_HIDE_FROM_ABI void vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { 1109 clear(); 1110 for (; __first != __last; ++__first) 1111 emplace_back(*__first); 1112} 1113 1114template <class _Tp, class _Allocator> 1115template <class _ForwardIterator, 1116 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 1117 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value, 1118 int> > 1119void vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { 1120 __assign_with_size(__first, __last, std::distance(__first, __last)); 1121} 1122 1123template <class _Tp, class _Allocator> 1124template <class _ForwardIterator, class _Sentinel> 1125_LIBCPP_HIDE_FROM_ABI void 1126vector<_Tp, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n) { 1127 size_type __new_size = static_cast<size_type>(__n); 1128 if (__new_size <= capacity()) { 1129 if (__new_size > size()) { 1130 _ForwardIterator __mid = std::next(__first, size()); 1131 std::copy(__first, __mid, this->__begin_); 1132 __construct_at_end(__mid, __last, __new_size - size()); 1133 } else { 1134 pointer __m = std::__copy<_ClassicAlgPolicy>(__first, __last, this->__begin_).second; 1135 this->__destruct_at_end(__m); 1136 } 1137 } else { 1138 __vdeallocate(); 1139 __vallocate(__recommend(__new_size)); 1140 __construct_at_end(__first, __last, __new_size); 1141 } 1142} 1143 1144template <class _Tp, class _Allocator> 1145void vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) { 1146 if (__n <= capacity()) { 1147 size_type __s = size(); 1148 std::fill_n(this->__begin_, std::min(__n, __s), __u); 1149 if (__n > __s) 1150 __construct_at_end(__n - __s, __u); 1151 else 1152 this->__destruct_at_end(this->__begin_ + __n); 1153 } else { 1154 __vdeallocate(); 1155 __vallocate(__recommend(static_cast<size_type>(__n))); 1156 __construct_at_end(__n, __u); 1157 } 1158} 1159 1160template <class _Tp, class _Allocator> 1161inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::begin() _NOEXCEPT { 1162 return __make_iter(this->__begin_); 1163} 1164 1165template <class _Tp, class _Allocator> 1166inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_iterator 1167vector<_Tp, _Allocator>::begin() const _NOEXCEPT { 1168 return __make_iter(this->__begin_); 1169} 1170 1171template <class _Tp, class _Allocator> 1172inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::end() _NOEXCEPT { 1173 return __make_iter(this->__end_); 1174} 1175 1176template <class _Tp, class _Allocator> 1177inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_iterator 1178vector<_Tp, _Allocator>::end() const _NOEXCEPT { 1179 return __make_iter(this->__end_); 1180} 1181 1182template <class _Tp, class _Allocator> 1183inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::reference 1184vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT { 1185 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds"); 1186 return this->__begin_[__n]; 1187} 1188 1189template <class _Tp, class _Allocator> 1190inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::const_reference 1191vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT { 1192 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__n < size(), "vector[] index out of bounds"); 1193 return this->__begin_[__n]; 1194} 1195 1196template <class _Tp, class _Allocator> 1197typename vector<_Tp, _Allocator>::reference vector<_Tp, _Allocator>::at(size_type __n) { 1198 if (__n >= size()) 1199 this->__throw_out_of_range(); 1200 return this->__begin_[__n]; 1201} 1202 1203template <class _Tp, class _Allocator> 1204typename vector<_Tp, _Allocator>::const_reference vector<_Tp, _Allocator>::at(size_type __n) const { 1205 if (__n >= size()) 1206 this->__throw_out_of_range(); 1207 return this->__begin_[__n]; 1208} 1209 1210template <class _Tp, class _Allocator> 1211void vector<_Tp, _Allocator>::reserve(size_type __n) { 1212 if (__n > capacity()) { 1213 if (__n > max_size()) 1214 this->__throw_length_error(); 1215 allocator_type& __a = this->__alloc(); 1216 __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); 1217 __swap_out_circular_buffer(__v); 1218 } 1219} 1220 1221template <class _Tp, class _Allocator> 1222void vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT { 1223 if (capacity() > size()) { 1224#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1225 try { 1226#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1227 allocator_type& __a = this->__alloc(); 1228 __split_buffer<value_type, allocator_type&> __v(size(), size(), __a); 1229 // The Standard mandates shrink_to_fit() does not increase the capacity. 1230 // With equal capacity keep the existing buffer. This avoids extra work 1231 // due to swapping the elements. 1232 if (__v.capacity() < capacity()) 1233 __swap_out_circular_buffer(__v); 1234#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1235 } catch (...) { 1236 } 1237#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1238 } 1239} 1240 1241template <class _Tp, class _Allocator> 1242template <class _Up> 1243typename vector<_Tp, _Allocator>::pointer vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) { 1244 allocator_type& __a = this->__alloc(); 1245 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1246 // __v.push_back(std::forward<_Up>(__x)); 1247 __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Up>(__x)); 1248 __v.__end_++; 1249 __swap_out_circular_buffer(__v); 1250 return this->__end_; 1251} 1252 1253template <class _Tp, class _Allocator> 1254inline _LIBCPP_HIDE_FROM_ABI void vector<_Tp, _Allocator>::push_back(const_reference __x) { 1255 pointer __end = this->__end_; 1256 if (__end < this->__end_cap()) { 1257 __construct_one_at_end(__x); 1258 ++__end; 1259 } else { 1260 __end = __push_back_slow_path(__x); 1261 } 1262 this->__end_ = __end; 1263} 1264 1265template <class _Tp, class _Allocator> 1266inline _LIBCPP_HIDE_FROM_ABI void vector<_Tp, _Allocator>::push_back(value_type&& __x) { 1267 pointer __end = this->__end_; 1268 if (__end < this->__end_cap()) { 1269 __construct_one_at_end(std::move(__x)); 1270 ++__end; 1271 } else { 1272 __end = __push_back_slow_path(std::move(__x)); 1273 } 1274 this->__end_ = __end; 1275} 1276 1277template <class _Tp, class _Allocator> 1278template <class... _Args> 1279typename vector<_Tp, _Allocator>::pointer vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) { 1280 allocator_type& __a = this->__alloc(); 1281 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1282 // __v.emplace_back(std::forward<_Args>(__args)...); 1283 __alloc_traits::construct(__a, std::__to_address(__v.__end_), std::forward<_Args>(__args)...); 1284 __v.__end_++; 1285 __swap_out_circular_buffer(__v); 1286 return this->__end_; 1287} 1288 1289template <class _Tp, class _Allocator> 1290template <class... _Args> 1291inline void vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) { 1292 pointer __end = this->__end_; 1293 if (__end < this->__end_cap()) { 1294 __construct_one_at_end(std::forward<_Args>(__args)...); 1295 ++__end; 1296 } else { 1297 __end = __emplace_back_slow_path(std::forward<_Args>(__args)...); 1298 } 1299 this->__end_ = __end; 1300} 1301 1302template <class _Tp, class _Allocator> 1303inline void vector<_Tp, _Allocator>::pop_back() { 1304 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(!empty(), "vector::pop_back called on an empty vector"); 1305 this->__destruct_at_end(this->__end_ - 1); 1306} 1307 1308template <class _Tp, class _Allocator> 1309inline _LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator 1310vector<_Tp, _Allocator>::erase(const_iterator __position) { 1311 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS( 1312 __position != end(), "vector::erase(iterator) called with a non-dereferenceable iterator"); 1313 difference_type __ps = __position - cbegin(); 1314 pointer __p = this->__begin_ + __ps; 1315 this->__destruct_at_end(std::move(__p + 1, this->__end_, __p)); 1316 return __make_iter(__p); 1317} 1318 1319template <class _Tp, class _Allocator> 1320typename vector<_Tp, _Allocator>::iterator 1321vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) { 1322 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__first <= __last, "vector::erase(first, last) called with invalid range"); 1323 pointer __p = this->__begin_ + (__first - begin()); 1324 if (__first != __last) { 1325 this->__destruct_at_end(std::move(__p + (__last - __first), this->__end_, __p)); 1326 } 1327 return __make_iter(__p); 1328} 1329 1330template <class _Tp, class _Allocator> 1331void vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) { 1332 pointer __old_last = this->__end_; 1333 difference_type __n = __old_last - __to; 1334 { 1335 pointer __i = __from_s + __n; 1336 _ConstructTransaction __tx(*this, __from_e - __i); 1337 for (pointer __pos = __tx.__pos_; __i < __from_e; ++__i, (void)++__pos, __tx.__pos_ = __pos) { 1338 __alloc_traits::construct(this->__alloc(), std::__to_address(__pos), std::move(*__i)); 1339 } 1340 } 1341 std::move_backward(__from_s, __from_s + __n, __old_last); 1342} 1343 1344template <class _Tp, class _Allocator> 1345typename vector<_Tp, _Allocator>::iterator 1346vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) { 1347 pointer __p = this->__begin_ + (__position - begin()); 1348 if (this->__end_ < this->__end_cap()) { 1349 if (__p == this->__end_) { 1350 __construct_one_at_end(__x); 1351 } else { 1352 __move_range(__p, this->__end_, __p + 1); 1353 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1354 if (std::__is_pointer_in_range(std::__to_address(__p), std::__to_address(__end_), std::addressof(__x))) 1355 ++__xr; 1356 *__p = *__xr; 1357 } 1358 } else { 1359 allocator_type& __a = this->__alloc(); 1360 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1361 __v.push_back(__x); 1362 __p = __swap_out_circular_buffer(__v, __p); 1363 } 1364 return __make_iter(__p); 1365} 1366 1367template <class _Tp, class _Allocator> 1368typename vector<_Tp, _Allocator>::iterator 1369vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) { 1370 pointer __p = this->__begin_ + (__position - begin()); 1371 if (this->__end_ < this->__end_cap()) { 1372 if (__p == this->__end_) { 1373 __construct_one_at_end(std::move(__x)); 1374 } else { 1375 __move_range(__p, this->__end_, __p + 1); 1376 *__p = std::move(__x); 1377 } 1378 } else { 1379 allocator_type& __a = this->__alloc(); 1380 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1381 __v.push_back(std::move(__x)); 1382 __p = __swap_out_circular_buffer(__v, __p); 1383 } 1384 return __make_iter(__p); 1385} 1386 1387template <class _Tp, class _Allocator> 1388template <class... _Args> 1389typename vector<_Tp, _Allocator>::iterator 1390vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) { 1391 pointer __p = this->__begin_ + (__position - begin()); 1392 if (this->__end_ < this->__end_cap()) { 1393 if (__p == this->__end_) { 1394 __construct_one_at_end(std::forward<_Args>(__args)...); 1395 } else { 1396 __temp_value<value_type, _Allocator> __tmp(this->__alloc(), std::forward<_Args>(__args)...); 1397 __move_range(__p, this->__end_, __p + 1); 1398 *__p = std::move(__tmp.get()); 1399 } 1400 } else { 1401 allocator_type& __a = this->__alloc(); 1402 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1403 __v.emplace_back(std::forward<_Args>(__args)...); 1404 __p = __swap_out_circular_buffer(__v, __p); 1405 } 1406 return __make_iter(__p); 1407} 1408 1409template <class _Tp, class _Allocator> 1410typename vector<_Tp, _Allocator>::iterator 1411vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) { 1412 pointer __p = this->__begin_ + (__position - begin()); 1413 if (__n > 0) { 1414 // We can't compare unrelated pointers inside constant expressions 1415 if (!__libcpp_is_constant_evaluated() && __n <= static_cast<size_type>(this->__end_cap() - this->__end_)) { 1416 size_type __old_n = __n; 1417 pointer __old_last = this->__end_; 1418 if (__n > static_cast<size_type>(this->__end_ - __p)) { 1419 size_type __cx = __n - (this->__end_ - __p); 1420 __construct_at_end(__cx, __x); 1421 __n -= __cx; 1422 } 1423 if (__n > 0) { 1424 __move_range(__p, __old_last, __p + __old_n); 1425 const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1426 if (__p <= __xr && __xr < this->__end_) 1427 __xr += __old_n; 1428 std::fill_n(__p, __n, *__xr); 1429 } 1430 } else { 1431 allocator_type& __a = this->__alloc(); 1432 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1433 __v.__construct_at_end(__n, __x); 1434 __p = __swap_out_circular_buffer(__v, __p); 1435 } 1436 } 1437 return __make_iter(__p); 1438} 1439template <class _Tp, class _Allocator> 1440template <class _InputIterator, 1441 __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value && 1442 is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, 1443 int> > 1444typename vector<_Tp, _Allocator>::iterator 1445vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { 1446 return __insert_with_sentinel(__position, __first, __last); 1447} 1448 1449template <class _Tp, class _Allocator> 1450template <class _InputIterator, class _Sentinel> 1451_LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator 1452vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { 1453 difference_type __off = __position - begin(); 1454 pointer __p = this->__begin_ + __off; 1455 allocator_type& __a = this->__alloc(); 1456 pointer __old_last = this->__end_; 1457 for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) { 1458 __construct_one_at_end(*__first); 1459 } 1460 __split_buffer<value_type, allocator_type&> __v(__a); 1461 if (__first != __last) { 1462#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1463 try { 1464#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1465 __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last)); 1466 difference_type __old_size = __old_last - this->__begin_; 1467 difference_type __old_p = __p - this->__begin_; 1468 reserve(__recommend(size() + __v.size())); 1469 __p = this->__begin_ + __old_p; 1470 __old_last = this->__begin_ + __old_size; 1471#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1472 } catch (...) { 1473 erase(__make_iter(__old_last), end()); 1474 throw; 1475 } 1476#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1477 } 1478 __p = std::rotate(__p, __old_last, this->__end_); 1479 insert(__make_iter(__p), std::make_move_iterator(__v.begin()), std::make_move_iterator(__v.end())); 1480 return begin() + __off; 1481} 1482 1483template <class _Tp, class _Allocator> 1484template <class _ForwardIterator, 1485 __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value && 1486 is_constructible<_Tp, typename iterator_traits<_ForwardIterator>::reference>::value, 1487 int> > 1488typename vector<_Tp, _Allocator>::iterator 1489vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { 1490 return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); 1491} 1492 1493template <class _Tp, class _Allocator> 1494template <class _Iterator, class _Sentinel> 1495_LIBCPP_HIDE_FROM_ABI typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::__insert_with_size( 1496 const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n) { 1497 auto __insertion_size = __n; 1498 pointer __p = this->__begin_ + (__position - begin()); 1499 if (__n > 0) { 1500 if (__n <= this->__end_cap() - this->__end_) { 1501 size_type __old_n = __n; 1502 pointer __old_last = this->__end_; 1503 _Iterator __m = std::next(__first, __n); 1504 difference_type __dx = this->__end_ - __p; 1505 if (__n > __dx) { 1506 __m = __first; 1507 difference_type __diff = this->__end_ - __p; 1508 std::advance(__m, __diff); 1509 __construct_at_end(__m, __last, __n - __diff); 1510 __n = __dx; 1511 } 1512 if (__n > 0) { 1513 __move_range(__p, __old_last, __p + __old_n); 1514 std::copy(__first, __m, __p); 1515 } 1516 } else { 1517 allocator_type& __a = this->__alloc(); 1518 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1519 __v.__construct_at_end_with_size(__first, __insertion_size); 1520 __p = __swap_out_circular_buffer(__v, __p); 1521 } 1522 } 1523 return __make_iter(__p); 1524} 1525 1526template <class _Tp, class _Allocator> 1527void vector<_Tp, _Allocator>::resize(size_type __sz) { 1528 size_type __cs = size(); 1529 if (__cs < __sz) 1530 this->__append(__sz - __cs); 1531 else if (__cs > __sz) 1532 this->__destruct_at_end(this->__begin_ + __sz); 1533} 1534 1535template <class _Tp, class _Allocator> 1536void vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) { 1537 size_type __cs = size(); 1538 if (__cs < __sz) 1539 this->__append(__sz - __cs, __x); 1540 else if (__cs > __sz) 1541 this->__destruct_at_end(this->__begin_ + __sz); 1542} 1543 1544template <class _Tp, class _Allocator> 1545void vector<_Tp, _Allocator>::swap(vector& __x) { 1546 _LIBCPP_ASSERT_COMPATIBLE_ALLOCATOR( 1547 __alloc_traits::propagate_on_container_swap::value || this->__alloc() == __x.__alloc(), 1548 "vector::swap: Either propagate_on_container_swap must be true" 1549 " or the allocators must compare equal"); 1550 std::swap(this->__begin_, __x.__begin_); 1551 std::swap(this->__end_, __x.__end_); 1552 std::swap(this->__end_cap(), __x.__end_cap()); 1553 std::__swap_allocator( 1554 this->__alloc(), __x.__alloc(), integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>()); 1555} 1556 1557template <class _Tp, class _Allocator> 1558bool vector<_Tp, _Allocator>::__invariants() const { 1559 if (this->__begin_ == nullptr) { 1560 if (this->__end_ != nullptr || this->__end_cap() != nullptr) 1561 return false; 1562 } else { 1563 if (this->__begin_ > this->__end_) 1564 return false; 1565 if (this->__begin_ == this->__end_cap()) 1566 return false; 1567 if (this->__end_ > this->__end_cap()) 1568 return false; 1569 } 1570 return true; 1571} 1572 1573// vector<bool> 1574 1575template <class _Allocator> 1576class vector<bool, _Allocator>; 1577 1578template <class _Allocator> 1579struct hash<vector<bool, _Allocator> >; 1580 1581template <class _Allocator> 1582struct __has_storage_type<vector<bool, _Allocator> > { 1583 static const bool value = true; 1584}; 1585 1586template <class _Allocator> 1587class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator> { 1588public: 1589 typedef vector __self; 1590 typedef bool value_type; 1591 typedef _Allocator allocator_type; 1592 typedef allocator_traits<allocator_type> __alloc_traits; 1593 typedef typename __alloc_traits::size_type size_type; 1594 typedef typename __alloc_traits::difference_type difference_type; 1595 typedef size_type __storage_type; 1596 typedef __bit_iterator<vector, false> pointer; 1597 typedef __bit_iterator<vector, true> const_pointer; 1598 typedef pointer iterator; 1599 typedef const_pointer const_iterator; 1600 typedef std::reverse_iterator<iterator> reverse_iterator; 1601 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 1602 1603private: 1604 typedef __rebind_alloc<__alloc_traits, __storage_type> __storage_allocator; 1605 typedef allocator_traits<__storage_allocator> __storage_traits; 1606 typedef typename __storage_traits::pointer __storage_pointer; 1607 typedef typename __storage_traits::const_pointer __const_storage_pointer; 1608 1609 __storage_pointer __begin_; 1610 size_type __size_; 1611 __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 1612 1613public: 1614 typedef __bit_reference<vector> reference; 1615#ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL 1616 using const_reference = bool; 1617#else 1618 typedef __bit_const_reference<vector> const_reference; 1619#endif 1620 1621private: 1622 _LIBCPP_HIDE_FROM_ABI size_type& __cap() _NOEXCEPT { return __cap_alloc_.first(); } 1623 _LIBCPP_HIDE_FROM_ABI const size_type& __cap() const _NOEXCEPT { return __cap_alloc_.first(); } 1624 _LIBCPP_HIDE_FROM_ABI __storage_allocator& __alloc() _NOEXCEPT { return __cap_alloc_.second(); } 1625 _LIBCPP_HIDE_FROM_ABI const __storage_allocator& __alloc() const _NOEXCEPT { return __cap_alloc_.second(); } 1626 1627 static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 1628 1629 _LIBCPP_HIDE_FROM_ABI static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT { 1630 return __n * __bits_per_word; 1631 } 1632 _LIBCPP_HIDE_FROM_ABI static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT { 1633 return (__n - 1) / __bits_per_word + 1; 1634 } 1635 1636public: 1637 _LIBCPP_HIDE_FROM_ABI vector(); 1638 1639 _LIBCPP_HIDE_FROM_ABI explicit vector(const allocator_type& __a); 1640 1641private: 1642 class __destroy_vector { 1643 public: 1644 _LIBCPP_HIDE_FROM_ABI __destroy_vector(vector& __vec) : __vec_(__vec) {} 1645 1646 _LIBCPP_HIDE_FROM_ABI void operator()() { 1647 if (__vec_.__begin_ != nullptr) 1648 __storage_traits::deallocate(__vec_.__alloc(), __vec_.__begin_, __vec_.__cap()); 1649 } 1650 1651 private: 1652 vector& __vec_; 1653 }; 1654 1655public: 1656 _LIBCPP_HIDE_FROM_ABI ~vector() { __destroy_vector (*this)(); } 1657 1658 _LIBCPP_HIDE_FROM_ABI explicit vector(size_type __n); 1659 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __v); 1660 _LIBCPP_HIDE_FROM_ABI vector(size_type __n, const value_type& __v, const allocator_type& __a); 1661 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 1662 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last); 1663 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 1664 _LIBCPP_HIDE_FROM_ABI vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a); 1665 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 1666 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last); 1667 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 1668 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a); 1669 1670 _LIBCPP_HIDE_FROM_ABI vector(const vector& __v); 1671 _LIBCPP_HIDE_FROM_ABI vector(const vector& __v, const allocator_type& __a); 1672 _LIBCPP_HIDE_FROM_ABI vector& operator=(const vector& __v); 1673 1674 _LIBCPP_HIDE_FROM_ABI vector(vector&& __v); 1675 _LIBCPP_HIDE_FROM_ABI vector(vector&& __v, const __type_identity_t<allocator_type>& __a); 1676 _LIBCPP_HIDE_FROM_ABI vector& operator=(vector&& __v); 1677 1678 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 1679 void _LIBCPP_HIDE_FROM_ABI assign(_InputIterator __first, _InputIterator __last); 1680 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 1681 void _LIBCPP_HIDE_FROM_ABI assign(_ForwardIterator __first, _ForwardIterator __last); 1682 1683 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const value_type& __x); 1684 1685 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(this->__alloc()); } 1686 1687 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT; 1688 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT { return __internal_cap_to_external(__cap()); } 1689 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; } 1690 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __size_ == 0; } 1691 _LIBCPP_HIDE_FROM_ABI void reserve(size_type __n); 1692 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT; 1693 1694 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __make_iter(0); } 1695 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __make_iter(0); } 1696 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __make_iter(__size_); } 1697 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __make_iter(__size_); } 1698 1699 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); } 1700 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); } 1701 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); } 1702 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); } 1703 1704 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return __make_iter(0); } 1705 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return __make_iter(__size_); } 1706 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); } 1707 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); } 1708 1709 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) { return __make_ref(__n); } 1710 _LIBCPP_HIDE_FROM_ABI const_reference operator[](size_type __n) const { return __make_ref(__n); } 1711 _LIBCPP_HIDE_FROM_ABI reference at(size_type __n); 1712 _LIBCPP_HIDE_FROM_ABI const_reference at(size_type __n) const; 1713 1714 _LIBCPP_HIDE_FROM_ABI reference front() { return __make_ref(0); } 1715 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return __make_ref(0); } 1716 _LIBCPP_HIDE_FROM_ABI reference back() { return __make_ref(__size_ - 1); } 1717 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return __make_ref(__size_ - 1); } 1718 1719 _LIBCPP_HIDE_FROM_ABI void push_back(const value_type& __x); 1720 _LIBCPP_HIDE_FROM_ABI void pop_back() { --__size_; } 1721 1722 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, const value_type& __x); 1723 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, size_type __n, const value_type& __x); 1724 template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> = 0> 1725 iterator _LIBCPP_HIDE_FROM_ABI insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 1726 template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> = 0> 1727 iterator _LIBCPP_HIDE_FROM_ABI insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 1728 1729 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __position); 1730 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __first, const_iterator __last); 1731 1732 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __size_ = 0; } 1733 1734 _LIBCPP_HIDE_FROM_ABI void swap(vector&); 1735 _LIBCPP_HIDE_FROM_ABI static void swap(reference __x, reference __y) _NOEXCEPT { std::swap(__x, __y); } 1736 1737 _LIBCPP_HIDE_FROM_ABI void resize(size_type __sz, value_type __x = false); 1738 _LIBCPP_HIDE_FROM_ABI void flip() _NOEXCEPT; 1739 1740 _LIBCPP_HIDE_FROM_ABI bool __invariants() const; 1741 1742private: 1743 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_length_error() const { std::__throw_length_error("vector"); } 1744 1745 _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI void __throw_out_of_range() const { std::__throw_out_of_range("vector"); } 1746 1747 template <class _InputIterator, class _Sentinel> 1748 _LIBCPP_HIDE_FROM_ABI void __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) { 1749 auto __guard = std::__make_exception_guard(__destroy_vector(*this)); 1750 1751 if (__n > 0) { 1752 __vallocate(__n); 1753 __construct_at_end(std::move(__first), std::move(__last), __n); 1754 } 1755 1756 __guard.__complete(); 1757 } 1758 1759 template <class _InputIterator, class _Sentinel> 1760 _LIBCPP_HIDE_FROM_ABI void __init_with_sentinel(_InputIterator __first, _Sentinel __last) { 1761#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1762 try { 1763#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1764 for (; __first != __last; ++__first) 1765 push_back(*__first); 1766#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 1767 } catch (...) { 1768 if (__begin_ != nullptr) 1769 __storage_traits::deallocate(__alloc(), __begin_, __cap()); 1770 throw; 1771 } 1772#endif // _LIBCPP_HAS_NO_EXCEPTIONS 1773 } 1774 1775 template <class _Iterator, class _Sentinel> 1776 _LIBCPP_HIDE_FROM_ABI void __assign_with_sentinel(_Iterator __first, _Sentinel __last); 1777 1778 template <class _ForwardIterator, class _Sentinel> 1779 _LIBCPP_HIDE_FROM_ABI void __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns); 1780 1781 template <class _InputIterator, class _Sentinel> 1782 _LIBCPP_HIDE_FROM_ABI iterator 1783 __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); 1784 1785 template <class _Iterator, class _Sentinel> 1786 _LIBCPP_HIDE_FROM_ABI iterator 1787 __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); 1788 1789 // Allocate space for __n objects 1790 // throws length_error if __n > max_size() 1791 // throws (probably bad_alloc) if memory run out 1792 // Precondition: __begin_ == __end_ == __cap() == 0 1793 // Precondition: __n > 0 1794 // Postcondition: capacity() >= __n 1795 // Postcondition: size() == 0 1796 _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) { 1797 if (__n > max_size()) 1798 __throw_length_error(); 1799 auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n)); 1800 __begin_ = __allocation.ptr; 1801 __size_ = 0; 1802 __cap() = __allocation.count; 1803 if (__libcpp_is_constant_evaluated()) { 1804 for (size_type __i = 0; __i != __cap(); ++__i) 1805 std::__construct_at(std::__to_address(__begin_) + __i); 1806 } 1807 } 1808 1809 _LIBCPP_HIDE_FROM_ABI void __vdeallocate() _NOEXCEPT; 1810 _LIBCPP_HIDE_FROM_ABI static size_type __align_it(size_type __new_size) _NOEXCEPT { 1811 return (__new_size + (__bits_per_word - 1)) & ~((size_type)__bits_per_word - 1); 1812 } 1813 _LIBCPP_HIDE_FROM_ABI size_type __recommend(size_type __new_size) const; 1814 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, bool __x); 1815 template <class _InputIterator, class _Sentinel> 1816 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n); 1817 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const_reference __x); 1818 _LIBCPP_HIDE_FROM_ABI reference __make_ref(size_type __pos) _NOEXCEPT { 1819 return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); 1820 } 1821 _LIBCPP_HIDE_FROM_ABI const_reference __make_ref(size_type __pos) const _NOEXCEPT { 1822 return __bit_const_reference<vector>( 1823 __begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word); 1824 } 1825 _LIBCPP_HIDE_FROM_ABI iterator __make_iter(size_type __pos) _NOEXCEPT { 1826 return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)); 1827 } 1828 _LIBCPP_HIDE_FROM_ABI const_iterator __make_iter(size_type __pos) const _NOEXCEPT { 1829 return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)); 1830 } 1831 _LIBCPP_HIDE_FROM_ABI iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT { 1832 return begin() + (__p - cbegin()); 1833 } 1834 1835 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __v) { 1836 __copy_assign_alloc( 1837 __v, integral_constant<bool, __storage_traits::propagate_on_container_copy_assignment::value>()); 1838 } 1839 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector& __c, true_type) { 1840 if (__alloc() != __c.__alloc()) 1841 __vdeallocate(); 1842 __alloc() = __c.__alloc(); 1843 } 1844 1845 _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const vector&, false_type) {} 1846 1847 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, false_type); 1848 _LIBCPP_HIDE_FROM_ABI void __move_assign(vector& __c, true_type); 1849 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c) { 1850 __move_assign_alloc( 1851 __c, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>()); 1852 } 1853 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector& __c, true_type) { __alloc() = std::move(__c.__alloc()); } 1854 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(vector&, false_type) _NOEXCEPT {} 1855 1856 _LIBCPP_HIDE_FROM_ABI size_t __hash_code() const _NOEXCEPT; 1857 1858 friend class __bit_reference<vector>; 1859 friend class __bit_const_reference<vector>; 1860 friend class __bit_iterator<vector, false>; 1861 friend class __bit_iterator<vector, true>; 1862 friend struct __bit_array<vector>; 1863 friend struct _LIBCPP_TEMPLATE_VIS hash<vector>; 1864}; 1865 1866template <class _Allocator> 1867void vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT { 1868 if (this->__begin_ != nullptr) { 1869 __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 1870 this->__begin_ = nullptr; 1871 this->__size_ = this->__cap() = 0; 1872 } 1873} 1874 1875template <class _Allocator> 1876typename vector<bool, _Allocator>::size_type vector<bool, _Allocator>::max_size() const _NOEXCEPT { 1877 size_type __amax = __storage_traits::max_size(__alloc()); 1878 size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 1879 if (__nmax / __bits_per_word <= __amax) 1880 return __nmax; 1881 return __internal_cap_to_external(__amax); 1882} 1883 1884// Precondition: __new_size > capacity() 1885template <class _Allocator> 1886inline _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::size_type 1887vector<bool, _Allocator>::__recommend(size_type __new_size) const { 1888 const size_type __ms = max_size(); 1889 if (__new_size > __ms) 1890 this->__throw_length_error(); 1891 const size_type __cap = capacity(); 1892 if (__cap >= __ms / 2) 1893 return __ms; 1894 return std::max(2 * __cap, __align_it(__new_size)); 1895} 1896 1897// Default constructs __n objects starting at __end_ 1898// Precondition: __n > 0 1899// Precondition: size() + __n <= capacity() 1900// Postcondition: size() == size() + __n 1901template <class _Allocator> 1902inline _LIBCPP_HIDE_FROM_ABI void vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) { 1903 size_type __old_size = this->__size_; 1904 this->__size_ += __n; 1905 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) { 1906 if (this->__size_ <= __bits_per_word) 1907 this->__begin_[0] = __storage_type(0); 1908 else 1909 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); 1910 } 1911 std::fill_n(__make_iter(__old_size), __n, __x); 1912} 1913 1914template <class _Allocator> 1915template <class _InputIterator, class _Sentinel> 1916void vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) { 1917 size_type __old_size = this->__size_; 1918 this->__size_ += __n; 1919 if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) { 1920 if (this->__size_ <= __bits_per_word) 1921 this->__begin_[0] = __storage_type(0); 1922 else 1923 this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); 1924 } 1925 std::__copy<_ClassicAlgPolicy>(__first, __last, __make_iter(__old_size)); 1926} 1927 1928template <class _Allocator> 1929inline _LIBCPP_HIDE_FROM_ABI vector<bool, _Allocator>::vector() 1930 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) {} 1931 1932template <class _Allocator> 1933inline _LIBCPP_HIDE_FROM_ABI vector<bool, _Allocator>::vector(const allocator_type& __a) 1934 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) {} 1935 1936template <class _Allocator> 1937vector<bool, _Allocator>::vector(size_type __n) : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { 1938 if (__n > 0) { 1939 __vallocate(__n); 1940 __construct_at_end(__n, false); 1941 } 1942} 1943 1944template <class _Allocator> 1945vector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 1946 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { 1947 if (__n > 0) { 1948 __vallocate(__n); 1949 __construct_at_end(__n, __x); 1950 } 1951} 1952 1953template <class _Allocator> 1954vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 1955 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { 1956 if (__n > 0) { 1957 __vallocate(__n); 1958 __construct_at_end(__n, __x); 1959 } 1960} 1961 1962template <class _Allocator> 1963template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 1964vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last) 1965 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { 1966 __init_with_sentinel(__first, __last); 1967} 1968 1969template <class _Allocator> 1970template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 1971vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a) 1972 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { 1973 __init_with_sentinel(__first, __last); 1974} 1975 1976template <class _Allocator> 1977template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 1978vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last) 1979 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __default_init_tag()) { 1980 auto __n = static_cast<size_type>(std::distance(__first, __last)); 1981 __init_with_size(__first, __last, __n); 1982} 1983 1984template <class _Allocator> 1985template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 1986vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a) 1987 : __begin_(nullptr), __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { 1988 auto __n = static_cast<size_type>(std::distance(__first, __last)); 1989 __init_with_size(__first, __last, __n); 1990} 1991 1992template <class _Allocator> 1993vector<bool, _Allocator>::vector(const vector& __v) 1994 : __begin_(nullptr), 1995 __size_(0), 1996 __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) { 1997 if (__v.size() > 0) { 1998 __vallocate(__v.size()); 1999 __construct_at_end(__v.begin(), __v.end(), __v.size()); 2000 } 2001} 2002 2003template <class _Allocator> 2004vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2005 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) { 2006 if (__v.size() > 0) { 2007 __vallocate(__v.size()); 2008 __construct_at_end(__v.begin(), __v.end(), __v.size()); 2009 } 2010} 2011 2012template <class _Allocator> 2013vector<bool, _Allocator>& vector<bool, _Allocator>::operator=(const vector& __v) { 2014 if (this != std::addressof(__v)) { 2015 __copy_assign_alloc(__v); 2016 if (__v.__size_) { 2017 if (__v.__size_ > capacity()) { 2018 __vdeallocate(); 2019 __vallocate(__v.__size_); 2020 } 2021 std::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2022 } 2023 __size_ = __v.__size_; 2024 } 2025 return *this; 2026} 2027 2028template <class _Allocator> 2029inline _LIBCPP_HIDE_FROM_ABI vector<bool, _Allocator>::vector(vector&& __v) 2030 : __begin_(__v.__begin_), __size_(__v.__size_), __cap_alloc_(std::move(__v.__cap_alloc_)) { 2031 __v.__begin_ = nullptr; 2032 __v.__size_ = 0; 2033 __v.__cap() = 0; 2034} 2035 2036template <class _Allocator> 2037vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a) 2038 : __begin_(nullptr), __size_(0), __cap_alloc_(0, __a) { 2039 if (__a == allocator_type(__v.__alloc())) { 2040 this->__begin_ = __v.__begin_; 2041 this->__size_ = __v.__size_; 2042 this->__cap() = __v.__cap(); 2043 __v.__begin_ = nullptr; 2044 __v.__cap() = __v.__size_ = 0; 2045 } else if (__v.size() > 0) { 2046 __vallocate(__v.size()); 2047 __construct_at_end(__v.begin(), __v.end(), __v.size()); 2048 } 2049} 2050 2051template <class _Allocator> 2052inline _LIBCPP_HIDE_FROM_ABI vector<bool, _Allocator>& vector<bool, _Allocator>::operator=(vector&& __v) { 2053 __move_assign(__v, integral_constant<bool, __storage_traits::propagate_on_container_move_assignment::value>()); 2054 return *this; 2055} 2056 2057template <class _Allocator> 2058void vector<bool, _Allocator>::__move_assign(vector& __c, false_type) { 2059 if (__alloc() != __c.__alloc()) 2060 assign(__c.begin(), __c.end()); 2061 else 2062 __move_assign(__c, true_type()); 2063} 2064 2065template <class _Allocator> 2066void vector<bool, _Allocator>::__move_assign(vector& __c, true_type) { 2067 __vdeallocate(); 2068 __move_assign_alloc(__c); 2069 this->__begin_ = __c.__begin_; 2070 this->__size_ = __c.__size_; 2071 this->__cap() = __c.__cap(); 2072 __c.__begin_ = nullptr; 2073 __c.__cap() = __c.__size_ = 0; 2074} 2075 2076template <class _Allocator> 2077void vector<bool, _Allocator>::assign(size_type __n, const value_type& __x) { 2078 __size_ = 0; 2079 if (__n > 0) { 2080 size_type __c = capacity(); 2081 if (__n <= __c) 2082 __size_ = __n; 2083 else { 2084 vector __v(get_allocator()); 2085 __v.reserve(__recommend(__n)); 2086 __v.__size_ = __n; 2087 swap(__v); 2088 } 2089 std::fill_n(begin(), __n, __x); 2090 } 2091} 2092 2093template <class _Allocator> 2094template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 2095void vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { 2096 __assign_with_sentinel(__first, __last); 2097} 2098 2099template <class _Allocator> 2100template <class _Iterator, class _Sentinel> 2101_LIBCPP_HIDE_FROM_ABI void vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { 2102 clear(); 2103 for (; __first != __last; ++__first) 2104 push_back(*__first); 2105} 2106 2107template <class _Allocator> 2108template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 2109void vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { 2110 __assign_with_size(__first, __last, std::distance(__first, __last)); 2111} 2112 2113template <class _Allocator> 2114template <class _ForwardIterator, class _Sentinel> 2115_LIBCPP_HIDE_FROM_ABI void 2116vector<bool, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns) { 2117 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__ns >= 0, "invalid range specified"); 2118 2119 clear(); 2120 2121 const size_t __n = static_cast<size_type>(__ns); 2122 if (__n) { 2123 if (__n > capacity()) { 2124 __vdeallocate(); 2125 __vallocate(__n); 2126 } 2127 __construct_at_end(__first, __last, __n); 2128 } 2129} 2130 2131template <class _Allocator> 2132void vector<bool, _Allocator>::reserve(size_type __n) { 2133 if (__n > capacity()) { 2134 if (__n > max_size()) 2135 this->__throw_length_error(); 2136 vector __v(this->get_allocator()); 2137 __v.__vallocate(__n); 2138 __v.__construct_at_end(this->begin(), this->end(), this->size()); 2139 swap(__v); 2140 } 2141} 2142 2143template <class _Allocator> 2144void vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT { 2145 if (__external_cap_to_internal(size()) > __cap()) { 2146#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2147 try { 2148#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2149 vector(*this, allocator_type(__alloc())).swap(*this); 2150#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2151 } catch (...) { 2152 } 2153#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2154 } 2155} 2156 2157template <class _Allocator> 2158typename vector<bool, _Allocator>::reference vector<bool, _Allocator>::at(size_type __n) { 2159 if (__n >= size()) 2160 this->__throw_out_of_range(); 2161 return (*this)[__n]; 2162} 2163 2164template <class _Allocator> 2165typename vector<bool, _Allocator>::const_reference vector<bool, _Allocator>::at(size_type __n) const { 2166 if (__n >= size()) 2167 this->__throw_out_of_range(); 2168 return (*this)[__n]; 2169} 2170 2171template <class _Allocator> 2172void vector<bool, _Allocator>::push_back(const value_type& __x) { 2173 if (this->__size_ == this->capacity()) 2174 reserve(__recommend(this->__size_ + 1)); 2175 ++this->__size_; 2176 back() = __x; 2177} 2178 2179template <class _Allocator> 2180typename vector<bool, _Allocator>::iterator 2181vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) { 2182 iterator __r; 2183 if (size() < capacity()) { 2184 const_iterator __old_end = end(); 2185 ++__size_; 2186 std::copy_backward(__position, __old_end, end()); 2187 __r = __const_iterator_cast(__position); 2188 } else { 2189 vector __v(get_allocator()); 2190 __v.reserve(__recommend(__size_ + 1)); 2191 __v.__size_ = __size_ + 1; 2192 __r = std::copy(cbegin(), __position, __v.begin()); 2193 std::copy_backward(__position, cend(), __v.end()); 2194 swap(__v); 2195 } 2196 *__r = __x; 2197 return __r; 2198} 2199 2200template <class _Allocator> 2201typename vector<bool, _Allocator>::iterator 2202vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) { 2203 iterator __r; 2204 size_type __c = capacity(); 2205 if (__n <= __c && size() <= __c - __n) { 2206 const_iterator __old_end = end(); 2207 __size_ += __n; 2208 std::copy_backward(__position, __old_end, end()); 2209 __r = __const_iterator_cast(__position); 2210 } else { 2211 vector __v(get_allocator()); 2212 __v.reserve(__recommend(__size_ + __n)); 2213 __v.__size_ = __size_ + __n; 2214 __r = std::copy(cbegin(), __position, __v.begin()); 2215 std::copy_backward(__position, cend(), __v.end()); 2216 swap(__v); 2217 } 2218 std::fill_n(__r, __n, __x); 2219 return __r; 2220} 2221 2222template <class _Allocator> 2223template <class _InputIterator, __enable_if_t<__has_exactly_input_iterator_category<_InputIterator>::value, int> > 2224typename vector<bool, _Allocator>::iterator 2225vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { 2226 return __insert_with_sentinel(__position, __first, __last); 2227} 2228 2229template <class _Allocator> 2230template <class _InputIterator, class _Sentinel> 2231_LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator 2232vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { 2233 difference_type __off = __position - begin(); 2234 iterator __p = __const_iterator_cast(__position); 2235 iterator __old_end = end(); 2236 for (; size() != capacity() && __first != __last; ++__first) { 2237 ++this->__size_; 2238 back() = *__first; 2239 } 2240 vector __v(get_allocator()); 2241 if (__first != __last) { 2242#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2243 try { 2244#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2245 __v.__assign_with_sentinel(std::move(__first), std::move(__last)); 2246 difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 2247 difference_type __old_p = __p - begin(); 2248 reserve(__recommend(size() + __v.size())); 2249 __p = begin() + __old_p; 2250 __old_end = begin() + __old_size; 2251#ifndef _LIBCPP_HAS_NO_EXCEPTIONS 2252 } catch (...) { 2253 erase(__old_end, end()); 2254 throw; 2255 } 2256#endif // _LIBCPP_HAS_NO_EXCEPTIONS 2257 } 2258 __p = std::rotate(__p, __old_end, end()); 2259 insert(__p, __v.begin(), __v.end()); 2260 return begin() + __off; 2261} 2262 2263template <class _Allocator> 2264template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > 2265typename vector<bool, _Allocator>::iterator 2266vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { 2267 return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); 2268} 2269 2270template <class _Allocator> 2271template <class _ForwardIterator, class _Sentinel> 2272_LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator vector<bool, _Allocator>::__insert_with_size( 2273 const_iterator __position, _ForwardIterator __first, _Sentinel __last, difference_type __n_signed) { 2274 _LIBCPP_ASSERT_VALID_INPUT_RANGE(__n_signed >= 0, "invalid range specified"); 2275 const size_type __n = static_cast<size_type>(__n_signed); 2276 iterator __r; 2277 size_type __c = capacity(); 2278 if (__n <= __c && size() <= __c - __n) { 2279 const_iterator __old_end = end(); 2280 __size_ += __n; 2281 std::copy_backward(__position, __old_end, end()); 2282 __r = __const_iterator_cast(__position); 2283 } else { 2284 vector __v(get_allocator()); 2285 __v.reserve(__recommend(__size_ + __n)); 2286 __v.__size_ = __size_ + __n; 2287 __r = std::copy(cbegin(), __position, __v.begin()); 2288 std::copy_backward(__position, cend(), __v.end()); 2289 swap(__v); 2290 } 2291 std::__copy<_ClassicAlgPolicy>(__first, __last, __r); 2292 return __r; 2293} 2294 2295template <class _Allocator> 2296inline _LIBCPP_HIDE_FROM_ABI typename vector<bool, _Allocator>::iterator 2297vector<bool, _Allocator>::erase(const_iterator __position) { 2298 iterator __r = __const_iterator_cast(__position); 2299 std::copy(__position + 1, this->cend(), __r); 2300 --__size_; 2301 return __r; 2302} 2303 2304template <class _Allocator> 2305typename vector<bool, _Allocator>::iterator 2306vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) { 2307 iterator __r = __const_iterator_cast(__first); 2308 difference_type __d = __last - __first; 2309 std::copy(__last, this->cend(), __r); 2310 __size_ -= __d; 2311 return __r; 2312} 2313 2314template <class _Allocator> 2315void vector<bool, _Allocator>::swap(vector& __x) { 2316 std::swap(this->__begin_, __x.__begin_); 2317 std::swap(this->__size_, __x.__size_); 2318 std::swap(this->__cap(), __x.__cap()); 2319 std::__swap_allocator( 2320 this->__alloc(), __x.__alloc(), integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>()); 2321} 2322 2323template <class _Allocator> 2324void vector<bool, _Allocator>::resize(size_type __sz, value_type __x) { 2325 size_type __cs = size(); 2326 if (__cs < __sz) { 2327 iterator __r; 2328 size_type __c = capacity(); 2329 size_type __n = __sz - __cs; 2330 if (__n <= __c && __cs <= __c - __n) { 2331 __r = end(); 2332 __size_ += __n; 2333 } else { 2334 vector __v(get_allocator()); 2335 __v.reserve(__recommend(__size_ + __n)); 2336 __v.__size_ = __size_ + __n; 2337 __r = std::copy(cbegin(), cend(), __v.begin()); 2338 swap(__v); 2339 } 2340 std::fill_n(__r, __n, __x); 2341 } else 2342 __size_ = __sz; 2343} 2344 2345template <class _Allocator> 2346void vector<bool, _Allocator>::flip() _NOEXCEPT { 2347 // do middle whole words 2348 size_type __n = __size_; 2349 __storage_pointer __p = __begin_; 2350 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 2351 *__p = ~*__p; 2352 // do last partial word 2353 if (__n > 0) { 2354 __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2355 __storage_type __b = *__p & __m; 2356 *__p &= ~__m; 2357 *__p |= ~__b & __m; 2358 } 2359} 2360 2361template <class _Allocator> 2362bool vector<bool, _Allocator>::__invariants() const { 2363 if (this->__begin_ == nullptr) { 2364 if (this->__size_ != 0 || this->__cap() != 0) 2365 return false; 2366 } else { 2367 if (this->__cap() == 0) 2368 return false; 2369 if (this->__size_ > this->capacity()) 2370 return false; 2371 } 2372 return true; 2373} 2374 2375template <class _Allocator> 2376size_t vector<bool, _Allocator>::__hash_code() const _NOEXCEPT { 2377 size_t __h = 0; 2378 // do middle whole words 2379 size_type __n = __size_; 2380 __storage_pointer __p = __begin_; 2381 for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 2382 __h ^= *__p; 2383 // do last partial word 2384 if (__n > 0) { 2385 const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 2386 __h ^= *__p & __m; 2387 } 2388 return __h; 2389} 2390 2391template <class _Allocator> 2392struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> > 2393 : public __unary_function<vector<bool, _Allocator>, size_t> { 2394 _LIBCPP_HIDE_FROM_ABI size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT { 2395 return __vec.__hash_code(); 2396 } 2397}; 2398 2399template <class _Tp, class _Allocator> 2400inline _LIBCPP_HIDE_FROM_ABI bool operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 2401 const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 2402 return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin()); 2403} 2404 2405template <class _Tp, class _Allocator> 2406inline _LIBCPP_HIDE_FROM_ABI bool operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 2407 return !(__x == __y); 2408} 2409 2410template <class _Tp, class _Allocator> 2411inline _LIBCPP_HIDE_FROM_ABI bool operator<(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 2412 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 2413} 2414 2415template <class _Tp, class _Allocator> 2416inline _LIBCPP_HIDE_FROM_ABI bool operator>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 2417 return __y < __x; 2418} 2419 2420template <class _Tp, class _Allocator> 2421inline _LIBCPP_HIDE_FROM_ABI bool operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 2422 return !(__x < __y); 2423} 2424 2425template <class _Tp, class _Allocator> 2426inline _LIBCPP_HIDE_FROM_ABI bool operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) { 2427 return !(__y < __x); 2428} 2429 2430template <class _Tp, class _Allocator> 2431inline _LIBCPP_HIDE_FROM_ABI void swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) { 2432 __x.swap(__y); 2433} 2434 2435_LIBCPP_END_NAMESPACE_STD 2436 2437_LIBCPP_POP_MACROS 2438 2439#if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) 2440# include <__cxx03/algorithm> 2441# include <__cxx03/atomic> 2442# include <__cxx03/cstdlib> 2443# include <__cxx03/iosfwd> 2444# if !defined(_LIBCPP_HAS_NO_LOCALIZATION) 2445# include <__cxx03/locale> 2446# endif 2447# include <__cxx03/type_traits> 2448# include <__cxx03/typeinfo> 2449# include <__cxx03/utility> 2450#endif 2451 2452#endif // _LIBCPP___CXX03_VECTOR 2453