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