codekingpro/portable-devtools
114k
1// -*- C++ -*-2//===------------------------------ vector --------------------------------===//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-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCUDACXX_VECTOR11#define _LIBCUDACXX_VECTOR12 13/*14 vector synopsis15 16namespace std17{18 19template <class T, class Allocator = allocator<T> >20class vector21{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++1441 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++1755 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++17102 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++17123 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 reference143 {144 public:145 reference(const reference&) noexcept;146 operator bool() const noexcept;147 reference& operator=(const bool x) noexcept;148 reference& operator=(const reference& x) noexcept;149 iterator operator&() const noexcept;150 void flip() noexcept;151 };152 153 class const_reference154 {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++14165 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++17179 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++17221 void pop_back();222 223 template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14224 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++17241 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>;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>264 void erase(vector<T, Allocator>& c, const U& value); // C++20265template <class T, class Allocator, class Predicate>266 void erase_if(vector<T, Allocator>& c, Predicate pred); // C++20267 268} // std269 270*/271 272#include <__config>273#include <iosfwd> // for forward declaration of vector274#include <__bit_reference>275#include <type_traits>276#include <climits>277#include <limits>278#include <initializer_list>279#include <memory>280#include <stdexcept>281#include <algorithm>282#include <cstring>283#include <version>284#include <__split_buffer>285#include <__functional_base>286 287#include <__debug>288 289#if defined(_CCCL_IMPLICIT_SYSTEM_HEADER_GCC)290# pragma GCC system_header291#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_CLANG)292# pragma clang system_header293#elif defined(_CCCL_IMPLICIT_SYSTEM_HEADER_MSVC)294# pragma system_header295#endif // no system header296 297_LIBCUDACXX_PUSH_MACROS298#include <__undef_macros>299 300 301_LIBCUDACXX_BEGIN_NAMESPACE_STD302 303template <bool>304class _LIBCUDACXX_TEMPLATE_VIS __vector_base_common305{306protected:307 _LIBCUDACXX_INLINE_VISIBILITY __vector_base_common() {}308 _LIBCUDACXX_NORETURN void __throw_length_error() const;309 _LIBCUDACXX_NORETURN void __throw_out_of_range() const;310};311 312template <bool __b>313void314__vector_base_common<__b>::__throw_length_error() const315{316 _CUDA_VSTD::__throw_length_error("vector");317}318 319template <bool __b>320void321__vector_base_common<__b>::__throw_out_of_range() const322{323 _CUDA_VSTD::__throw_out_of_range("vector");324}325 326_LIBCUDACXX_EXTERN_TEMPLATE(class _LIBCUDACXX_EXTERN_TEMPLATE_TYPE_VIS __vector_base_common<true>)327 328template <class _Tp, class _Allocator>329class __vector_base330 : protected __vector_base_common<true>331{332public:333 typedef _Allocator allocator_type;334 typedef allocator_traits<allocator_type> __alloc_traits;335 typedef typename __alloc_traits::size_type size_type;336protected:337 typedef _Tp value_type;338 typedef value_type& reference;339 typedef const value_type& const_reference;340 typedef typename __alloc_traits::difference_type difference_type;341 typedef typename __alloc_traits::pointer pointer;342 typedef typename __alloc_traits::const_pointer const_pointer;343 typedef pointer iterator;344 typedef const_pointer const_iterator;345 346 pointer __begin_;347 pointer __end_;348 __compressed_pair<pointer, allocator_type> __end_cap_;349 350 _LIBCUDACXX_INLINE_VISIBILITY351 allocator_type& __alloc() noexcept352 {return __end_cap_.second();}353 _LIBCUDACXX_INLINE_VISIBILITY354 const allocator_type& __alloc() const noexcept355 {return __end_cap_.second();}356 _LIBCUDACXX_INLINE_VISIBILITY357 pointer& __end_cap() noexcept358 {return __end_cap_.first();}359 _LIBCUDACXX_INLINE_VISIBILITY360 const pointer& __end_cap() const noexcept361 {return __end_cap_.first();}362 363 _LIBCUDACXX_INLINE_VISIBILITY364 __vector_base()365 noexcept(is_nothrow_default_constructible<allocator_type>::value);366 _LIBCUDACXX_INLINE_VISIBILITY __vector_base(const allocator_type& __a);367 _LIBCUDACXX_INLINE_VISIBILITY __vector_base(allocator_type&& __a) noexcept;368 ~__vector_base();369 370 _LIBCUDACXX_INLINE_VISIBILITY371 void clear() noexcept {__destruct_at_end(__begin_);}372 _LIBCUDACXX_INLINE_VISIBILITY373 size_type capacity() const noexcept374 {return static_cast<size_type>(__end_cap() - __begin_);}375 376 _LIBCUDACXX_INLINE_VISIBILITY377 void __destruct_at_end(pointer __new_last) noexcept;378 379 _LIBCUDACXX_INLINE_VISIBILITY380 void __copy_assign_alloc(const __vector_base& __c)381 {__copy_assign_alloc(__c, integral_constant<bool,382 __alloc_traits::propagate_on_container_copy_assignment::value>());}383 384 _LIBCUDACXX_INLINE_VISIBILITY385 void __move_assign_alloc(__vector_base& __c)386 noexcept(387 !__alloc_traits::propagate_on_container_move_assignment::value ||388 is_nothrow_move_assignable<allocator_type>::value)389 {__move_assign_alloc(__c, integral_constant<bool,390 __alloc_traits::propagate_on_container_move_assignment::value>());}391private:392 _LIBCUDACXX_INLINE_VISIBILITY393 void __copy_assign_alloc(const __vector_base& __c, true_type)394 {395 if (__alloc() != __c.__alloc())396 {397 clear();398 __alloc_traits::deallocate(__alloc(), __begin_, capacity());399 __begin_ = __end_ = __end_cap() = nullptr;400 }401 __alloc() = __c.__alloc();402 }403 404 _LIBCUDACXX_INLINE_VISIBILITY405 void __copy_assign_alloc(const __vector_base&, false_type)406 {}407 408 _LIBCUDACXX_INLINE_VISIBILITY409 void __move_assign_alloc(__vector_base& __c, true_type)410 noexcept(is_nothrow_move_assignable<allocator_type>::value)411 {412 __alloc() = _CUDA_VSTD::move(__c.__alloc());413 }414 415 _LIBCUDACXX_INLINE_VISIBILITY416 void __move_assign_alloc(__vector_base&, false_type)417 noexcept418 {}419};420 421template <class _Tp, class _Allocator>422inline _LIBCUDACXX_INLINE_VISIBILITY423void424__vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) noexcept425{426 pointer __soon_to_be_end = __end_;427 while (__new_last != __soon_to_be_end)428 __alloc_traits::destroy(__alloc(), _CUDA_VSTD::__to_raw_pointer(--__soon_to_be_end));429 __end_ = __new_last;430}431 432template <class _Tp, class _Allocator>433inline _LIBCUDACXX_INLINE_VISIBILITY434__vector_base<_Tp, _Allocator>::__vector_base()435 noexcept(is_nothrow_default_constructible<allocator_type>::value)436 : __begin_(nullptr),437 __end_(nullptr),438 __end_cap_(nullptr)439{440}441 442template <class _Tp, class _Allocator>443inline _LIBCUDACXX_INLINE_VISIBILITY444__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a)445 : __begin_(nullptr),446 __end_(nullptr),447 __end_cap_(nullptr, __a)448{449}450 451template <class _Tp, class _Allocator>452inline _LIBCUDACXX_INLINE_VISIBILITY453__vector_base<_Tp, _Allocator>::__vector_base(allocator_type&& __a) noexcept454 : __begin_(nullptr),455 __end_(nullptr),456 __end_cap_(nullptr, std::move(__a)) {}457 458template <class _Tp, class _Allocator>459__vector_base<_Tp, _Allocator>::~__vector_base()460{461 if (__begin_ != nullptr)462 {463 clear();464 __alloc_traits::deallocate(__alloc(), __begin_, capacity());465 }466}467 468template <class _Tp, class _Allocator /* = allocator<_Tp> */>469class _LIBCUDACXX_TEMPLATE_VIS vector470 : private __vector_base<_Tp, _Allocator>471{472private:473 typedef __vector_base<_Tp, _Allocator> __base;474 typedef allocator<_Tp> __default_allocator_type;475public:476 typedef vector __self;477 typedef _Tp value_type;478 typedef _Allocator allocator_type;479 typedef typename __base::__alloc_traits __alloc_traits;480 typedef typename __base::reference reference;481 typedef typename __base::const_reference const_reference;482 typedef typename __base::size_type size_type;483 typedef typename __base::difference_type difference_type;484 typedef typename __base::pointer pointer;485 typedef typename __base::const_pointer const_pointer;486 typedef __wrap_iter<pointer> iterator;487 typedef __wrap_iter<const_pointer> const_iterator;488 typedef _CUDA_VSTD::reverse_iterator<iterator> reverse_iterator;489 typedef _CUDA_VSTD::reverse_iterator<const_iterator> const_reverse_iterator;490 491 static_assert((is_same<typename allocator_type::value_type, value_type>::value),492 "Allocator::value_type must be same type as value_type");493 494 _LIBCUDACXX_INLINE_VISIBILITY495 vector() noexcept(is_nothrow_default_constructible<allocator_type>::value)496 {497#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE498 __get_db()->__insert_c(this);499#endif500 }501 _LIBCUDACXX_INLINE_VISIBILITY explicit vector(const allocator_type& __a)502#if _LIBCUDACXX_STD_VER <= 14503 noexcept(is_nothrow_copy_constructible<allocator_type>::value)504#else505 noexcept506#endif507 : __base(__a)508 {509#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE510 __get_db()->__insert_c(this);511#endif512 }513 explicit vector(size_type __n);514#if _LIBCUDACXX_STD_VER > 11515 explicit vector(size_type __n, const allocator_type& __a);516#endif517 vector(size_type __n, const value_type& __x);518 vector(size_type __n, const value_type& __x, const allocator_type& __a);519 template <class _InputIterator>520 vector(_InputIterator __first,521 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&522 !__is_cpp17_forward_iterator<_InputIterator>::value &&523 is_constructible<524 value_type,525 typename iterator_traits<_InputIterator>::reference>::value,526 _InputIterator>::type __last);527 template <class _InputIterator>528 vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,529 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&530 !__is_cpp17_forward_iterator<_InputIterator>::value &&531 is_constructible<532 value_type,533 typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);534 template <class _ForwardIterator>535 vector(_ForwardIterator __first,536 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&537 is_constructible<538 value_type,539 typename iterator_traits<_ForwardIterator>::reference>::value,540 _ForwardIterator>::type __last);541 template <class _ForwardIterator>542 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,543 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&544 is_constructible<545 value_type,546 typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);547 548 _LIBCUDACXX_INLINE_VISIBILITY549 ~vector()550 {551 __annotate_delete();552#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE553 __get_db()->__erase_c(this);554#endif555 }556 557 vector(const vector& __x);558 vector(const vector& __x, const allocator_type& __a);559 _LIBCUDACXX_INLINE_VISIBILITY560 vector& operator=(const vector& __x);561 562 _LIBCUDACXX_INLINE_VISIBILITY563 vector(initializer_list<value_type> __il);564 565 _LIBCUDACXX_INLINE_VISIBILITY566 vector(initializer_list<value_type> __il, const allocator_type& __a);567 568 _LIBCUDACXX_INLINE_VISIBILITY569 vector(vector&& __x)570#if _LIBCUDACXX_STD_VER > 14571 noexcept;572#else573 noexcept(is_nothrow_move_constructible<allocator_type>::value);574#endif575 576 _LIBCUDACXX_INLINE_VISIBILITY577 vector(vector&& __x, const allocator_type& __a);578 _LIBCUDACXX_INLINE_VISIBILITY579 vector& operator=(vector&& __x)580 noexcept((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));581 582 _LIBCUDACXX_INLINE_VISIBILITY583 vector& operator=(initializer_list<value_type> __il)584 {assign(__il.begin(), __il.end()); return *this;}585 586 template <class _InputIterator>587 typename enable_if588 <589 __is_cpp17_input_iterator <_InputIterator>::value &&590 !__is_cpp17_forward_iterator<_InputIterator>::value &&591 is_constructible<592 value_type,593 typename iterator_traits<_InputIterator>::reference>::value,594 void595 >::type596 assign(_InputIterator __first, _InputIterator __last);597 template <class _ForwardIterator>598 typename enable_if599 <600 __is_cpp17_forward_iterator<_ForwardIterator>::value &&601 is_constructible<602 value_type,603 typename iterator_traits<_ForwardIterator>::reference>::value,604 void605 >::type606 assign(_ForwardIterator __first, _ForwardIterator __last);607 608 void assign(size_type __n, const_reference __u);609 610 _LIBCUDACXX_INLINE_VISIBILITY611 void assign(initializer_list<value_type> __il)612 {assign(__il.begin(), __il.end());}613 614 _LIBCUDACXX_INLINE_VISIBILITY615 allocator_type get_allocator() const noexcept616 {return this->__alloc();}617 618 _LIBCUDACXX_INLINE_VISIBILITY iterator begin() noexcept;619 _LIBCUDACXX_INLINE_VISIBILITY const_iterator begin() const noexcept;620 _LIBCUDACXX_INLINE_VISIBILITY iterator end() noexcept;621 _LIBCUDACXX_INLINE_VISIBILITY const_iterator end() const noexcept;622 623 _LIBCUDACXX_INLINE_VISIBILITY624 reverse_iterator rbegin() noexcept625 {return reverse_iterator(end());}626 _LIBCUDACXX_INLINE_VISIBILITY627 const_reverse_iterator rbegin() const noexcept628 {return const_reverse_iterator(end());}629 _LIBCUDACXX_INLINE_VISIBILITY630 reverse_iterator rend() noexcept631 {return reverse_iterator(begin());}632 _LIBCUDACXX_INLINE_VISIBILITY633 const_reverse_iterator rend() const noexcept634 {return const_reverse_iterator(begin());}635 636 _LIBCUDACXX_INLINE_VISIBILITY637 const_iterator cbegin() const noexcept638 {return begin();}639 _LIBCUDACXX_INLINE_VISIBILITY640 const_iterator cend() const noexcept641 {return end();}642 _LIBCUDACXX_INLINE_VISIBILITY643 const_reverse_iterator crbegin() const noexcept644 {return rbegin();}645 _LIBCUDACXX_INLINE_VISIBILITY646 const_reverse_iterator crend() const noexcept647 {return rend();}648 649 _LIBCUDACXX_INLINE_VISIBILITY650 size_type size() const noexcept651 {return static_cast<size_type>(this->__end_ - this->__begin_);}652 _LIBCUDACXX_INLINE_VISIBILITY653 size_type capacity() const noexcept654 {return __base::capacity();}655 _LIBCUDACXX_NODISCARD_AFTER_CXX17 _LIBCUDACXX_INLINE_VISIBILITY656 bool empty() const noexcept657 {return this->__begin_ == this->__end_;}658 size_type max_size() const noexcept;659 void reserve(size_type __n);660 void shrink_to_fit() noexcept;661 662 _LIBCUDACXX_INLINE_VISIBILITY reference operator[](size_type __n) noexcept;663 _LIBCUDACXX_INLINE_VISIBILITY const_reference operator[](size_type __n) const noexcept;664 reference at(size_type __n);665 const_reference at(size_type __n) const;666 667 _LIBCUDACXX_INLINE_VISIBILITY reference front() noexcept668 {669 _LIBCUDACXX_ASSERT(!empty(), "front() called for empty vector");670 return *this->__begin_;671 }672 _LIBCUDACXX_INLINE_VISIBILITY const_reference front() const noexcept673 {674 _LIBCUDACXX_ASSERT(!empty(), "front() called for empty vector");675 return *this->__begin_;676 }677 _LIBCUDACXX_INLINE_VISIBILITY reference back() noexcept678 {679 _LIBCUDACXX_ASSERT(!empty(), "back() called for empty vector");680 return *(this->__end_ - 1);681 }682 _LIBCUDACXX_INLINE_VISIBILITY const_reference back() const noexcept683 {684 _LIBCUDACXX_ASSERT(!empty(), "back() called for empty vector");685 return *(this->__end_ - 1);686 }687 688 _LIBCUDACXX_INLINE_VISIBILITY689 value_type* data() noexcept690 {return _CUDA_VSTD::__to_raw_pointer(this->__begin_);}691 _LIBCUDACXX_INLINE_VISIBILITY692 const value_type* data() const noexcept693 {return _CUDA_VSTD::__to_raw_pointer(this->__begin_);}694 695 template <class _Arg>696 _LIBCUDACXX_INLINE_VISIBILITY697 void __emplace_back(_Arg&& __arg) {698 emplace_back(_CUDA_VSTD::forward<_Arg>(__arg));699 }700 701 _LIBCUDACXX_INLINE_VISIBILITY void push_back(const_reference __x);702 703 _LIBCUDACXX_INLINE_VISIBILITY void push_back(value_type&& __x);704 705 template <class... _Args>706 _LIBCUDACXX_INLINE_VISIBILITY707#if _LIBCUDACXX_STD_VER > 14708 reference emplace_back(_Args&&... __args);709#else710 void emplace_back(_Args&&... __args);711#endif712 713 _LIBCUDACXX_INLINE_VISIBILITY714 void pop_back();715 716 iterator insert(const_iterator __position, const_reference __x);717 718 iterator insert(const_iterator __position, value_type&& __x);719 template <class... _Args>720 iterator emplace(const_iterator __position, _Args&&... __args);721 722 iterator insert(const_iterator __position, size_type __n, const_reference __x);723 template <class _InputIterator>724 typename enable_if725 <726 __is_cpp17_input_iterator <_InputIterator>::value &&727 !__is_cpp17_forward_iterator<_InputIterator>::value &&728 is_constructible<729 value_type,730 typename iterator_traits<_InputIterator>::reference>::value,731 iterator732 >::type733 insert(const_iterator __position, _InputIterator __first, _InputIterator __last);734 template <class _ForwardIterator>735 typename enable_if736 <737 __is_cpp17_forward_iterator<_ForwardIterator>::value &&738 is_constructible<739 value_type,740 typename iterator_traits<_ForwardIterator>::reference>::value,741 iterator742 >::type743 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);744 745 _LIBCUDACXX_INLINE_VISIBILITY746 iterator insert(const_iterator __position, initializer_list<value_type> __il)747 {return insert(__position, __il.begin(), __il.end());}748 749 _LIBCUDACXX_INLINE_VISIBILITY iterator erase(const_iterator __position);750 iterator erase(const_iterator __first, const_iterator __last);751 752 _LIBCUDACXX_INLINE_VISIBILITY753 void clear() noexcept754 {755 size_type __old_size = size();756 __base::clear();757 __annotate_shrink(__old_size);758 __invalidate_all_iterators();759 }760 761 void resize(size_type __sz);762 void resize(size_type __sz, const_reference __x);763 764 void swap(vector&)765#if _LIBCUDACXX_STD_VER >= 14766 noexcept;767#else768 noexcept(!__alloc_traits::propagate_on_container_swap::value ||769 __is_nothrow_swappable<allocator_type>::value);770#endif771 772 bool __invariants() const;773 774#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE775 776 bool __dereferenceable(const const_iterator* __i) const;777 bool __decrementable(const const_iterator* __i) const;778 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;779 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;780 781#endif // _LIBCUDACXX_ENABLE_DEBUG_MODE782 783private:784 _LIBCUDACXX_INLINE_VISIBILITY void __invalidate_all_iterators();785 _LIBCUDACXX_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);786 void __vallocate(size_type __n);787 void __vdeallocate() noexcept;788 _LIBCUDACXX_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;789 void __construct_at_end(size_type __n);790 _LIBCUDACXX_INLINE_VISIBILITY791 void __construct_at_end(size_type __n, const_reference __x);792 template <class _ForwardIterator>793 typename enable_if794 <795 __is_cpp17_forward_iterator<_ForwardIterator>::value,796 void797 >::type798 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);799 void __append(size_type __n);800 void __append(size_type __n, const_reference __x);801 _LIBCUDACXX_INLINE_VISIBILITY802 iterator __make_iter(pointer __p) noexcept;803 _LIBCUDACXX_INLINE_VISIBILITY804 const_iterator __make_iter(const_pointer __p) const noexcept;805 void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);806 pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);807 void __move_range(pointer __from_s, pointer __from_e, pointer __to);808 void __move_assign(vector& __c, true_type)809 noexcept(is_nothrow_move_assignable<allocator_type>::value);810 void __move_assign(vector& __c, false_type)811 noexcept(__alloc_traits::is_always_equal::value);812 _LIBCUDACXX_INLINE_VISIBILITY813 void __destruct_at_end(pointer __new_last) noexcept814 {815 __invalidate_iterators_past(__new_last);816 size_type __old_size = size();817 __base::__destruct_at_end(__new_last);818 __annotate_shrink(__old_size);819 }820 821 template <class _Up>822 _LIBCUDACXX_INLINE_VISIBILITY823 inline void __push_back_slow_path(_Up&& __x);824 825 template <class... _Args>826 _LIBCUDACXX_INLINE_VISIBILITY827 inline void __emplace_back_slow_path(_Args&&... __args);828 829 // The following functions are no-ops outside of AddressSanitizer mode.830 // We call annotatations only for the default Allocator because other allocators831 // may not meet the AddressSanitizer alignment constraints.832 // See the documentation for __sanitizer_annotate_contiguous_container for more details.833#ifndef _LIBCUDACXX_HAS_NO_ASAN834 void __annotate_contiguous_container(const void *__beg, const void *__end,835 const void *__old_mid,836 const void *__new_mid) const837 {838 839 if (__beg && is_same<allocator_type, __default_allocator_type>::value)840 __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);841 }842#else843 _LIBCUDACXX_INLINE_VISIBILITY844 void __annotate_contiguous_container(const void*, const void*, const void*,845 const void*) const noexcept {}846#endif847 _LIBCUDACXX_INLINE_VISIBILITY848 void __annotate_new(size_type __current_size) const noexcept {849 __annotate_contiguous_container(data(), data() + capacity(),850 data() + capacity(), data() + __current_size);851 }852 853 _LIBCUDACXX_INLINE_VISIBILITY854 void __annotate_delete() const noexcept {855 __annotate_contiguous_container(data(), data() + capacity(),856 data() + size(), data() + capacity());857 }858 859 _LIBCUDACXX_INLINE_VISIBILITY860 void __annotate_increase(size_type __n) const noexcept861 {862 __annotate_contiguous_container(data(), data() + capacity(),863 data() + size(), data() + size() + __n);864 }865 866 _LIBCUDACXX_INLINE_VISIBILITY867 void __annotate_shrink(size_type __old_size) const noexcept868 {869 __annotate_contiguous_container(data(), data() + capacity(),870 data() + __old_size, data() + size());871 }872 873 struct _ConstructTransaction {874 explicit _ConstructTransaction(vector &__v, size_type __n)875 : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {876#ifndef _LIBCUDACXX_HAS_NO_ASAN877 __v_.__annotate_increase(__n);878#endif879 }880 ~_ConstructTransaction() {881 __v_.__end_ = __pos_;882#ifndef _LIBCUDACXX_HAS_NO_ASAN883 if (__pos_ != __new_end_) {884 __v_.__annotate_shrink(__new_end_ - __v_.__begin_);885 }886#endif887 }888 889 vector &__v_;890 pointer __pos_;891 const_pointer const __new_end_;892 893 private:894 _ConstructTransaction(_ConstructTransaction const&) = delete;895 _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;896 };897 898 template <class ..._Args>899 _LIBCUDACXX_INLINE_VISIBILITY900 void __construct_one_at_end(_Args&& ...__args) {901 _ConstructTransaction __tx(*this, 1);902 __alloc_traits::construct(this->__alloc(), _CUDA_VSTD::__to_raw_pointer(__tx.__pos_),903 _CUDA_VSTD::forward<_Args>(__args)...);904 ++__tx.__pos_;905 }906};907 908#ifndef _LIBCUDACXX_HAS_NO_DEDUCTION_GUIDES909template<class _InputIterator,910 class _Alloc = typename std::allocator<typename iterator_traits<_InputIterator>::value_type>,911 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type912 >913vector(_InputIterator, _InputIterator)914 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;915 916template<class _InputIterator,917 class _Alloc,918 class = typename enable_if<__is_allocator<_Alloc>::value, void>::type919 >920vector(_InputIterator, _InputIterator, _Alloc)921 -> vector<typename iterator_traits<_InputIterator>::value_type, _Alloc>;922#endif923 924template <class _Tp, class _Allocator>925void926vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)927{928 929 __annotate_delete();930 __alloc_traits::__construct_backward_with_exception_guarantees(931 this->__alloc(), this->__begin_, this->__end_, __v.__begin_);932 _CUDA_VSTD::swap(this->__begin_, __v.__begin_);933 _CUDA_VSTD::swap(this->__end_, __v.__end_);934 _CUDA_VSTD::swap(this->__end_cap(), __v.__end_cap());935 __v.__first_ = __v.__begin_;936 __annotate_new(size());937 __invalidate_all_iterators();938}939 940template <class _Tp, class _Allocator>941typename vector<_Tp, _Allocator>::pointer942vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)943{944 __annotate_delete();945 pointer __r = __v.__begin_;946 __alloc_traits::__construct_backward_with_exception_guarantees(947 this->__alloc(), this->__begin_, __p, __v.__begin_);948 __alloc_traits::__construct_forward_with_exception_guarantees(949 this->__alloc(), __p, this->__end_, __v.__end_);950 _CUDA_VSTD::swap(this->__begin_, __v.__begin_);951 _CUDA_VSTD::swap(this->__end_, __v.__end_);952 _CUDA_VSTD::swap(this->__end_cap(), __v.__end_cap());953 __v.__first_ = __v.__begin_;954 __annotate_new(size());955 __invalidate_all_iterators();956 return __r;957}958 959// Allocate space for __n objects960// throws length_error if __n > max_size()961// throws (probably bad_alloc) if memory run out962// Precondition: __begin_ == __end_ == __end_cap() == 0963// Precondition: __n > 0964// Postcondition: capacity() == __n965// Postcondition: size() == 0966template <class _Tp, class _Allocator>967void968vector<_Tp, _Allocator>::__vallocate(size_type __n)969{970 if (__n > max_size())971 this->__throw_length_error();972 this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n);973 this->__end_cap() = this->__begin_ + __n;974 __annotate_new(0);975}976 977template <class _Tp, class _Allocator>978void979vector<_Tp, _Allocator>::__vdeallocate() noexcept980{981 if (this->__begin_ != nullptr)982 {983 clear();984 __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());985 this->__begin_ = this->__end_ = this->__end_cap() = nullptr;986 }987}988 989template <class _Tp, class _Allocator>990typename vector<_Tp, _Allocator>::size_type991vector<_Tp, _Allocator>::max_size() const noexcept992{993 return _CUDA_VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),994 numeric_limits<difference_type>::max());995}996 997// Precondition: __new_size > capacity()998template <class _Tp, class _Allocator>999inline _LIBCUDACXX_INLINE_VISIBILITY1000typename vector<_Tp, _Allocator>::size_type1001vector<_Tp, _Allocator>::__recommend(size_type __new_size) const1002{1003 const size_type __ms = max_size();1004 if (__new_size > __ms)1005 this->__throw_length_error();1006 const size_type __cap = capacity();1007 if (__cap >= __ms / 2)1008 return __ms;1009 return _CUDA_VSTD::max<size_type>(2*__cap, __new_size);1010}1011 1012// Default constructs __n objects starting at __end_1013// throws if construction throws1014// Precondition: __n > 01015// Precondition: size() + __n <= capacity()1016// Postcondition: size() == size() + __n1017template <class _Tp, class _Allocator>1018void1019vector<_Tp, _Allocator>::__construct_at_end(size_type __n)1020{1021 _ConstructTransaction __tx(*this, __n);1022 for (; __tx.__pos_ != __tx.__new_end_; ++__tx.__pos_) {1023 __alloc_traits::construct(this->__alloc(), _CUDA_VSTD::__to_raw_pointer(__tx.__pos_));1024 }1025}1026 1027// Copy constructs __n objects starting at __end_ from __x1028// throws if construction throws1029// Precondition: __n > 01030// Precondition: size() + __n <= capacity()1031// Postcondition: size() == old size() + __n1032// Postcondition: [i] == __x for all i in [size() - __n, __n)1033template <class _Tp, class _Allocator>1034inline1035void1036vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)1037{1038 _ConstructTransaction __tx(*this, __n);1039 for (; __tx.__pos_ != __tx.__new_end_; ++__tx.__pos_) {1040 __alloc_traits::construct(this->__alloc(), _CUDA_VSTD::__to_raw_pointer(__tx.__pos_), __x);1041 }1042}1043 1044template <class _Tp, class _Allocator>1045template <class _ForwardIterator>1046typename enable_if1047<1048 __is_cpp17_forward_iterator<_ForwardIterator>::value,1049 void1050>::type1051vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)1052{1053 _ConstructTransaction __tx(*this, __n);1054 __alloc_traits::__construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_);1055}1056 1057// Default constructs __n objects starting at __end_1058// throws if construction throws1059// Postcondition: size() == size() + __n1060// Exception safety: strong.1061template <class _Tp, class _Allocator>1062void1063vector<_Tp, _Allocator>::__append(size_type __n)1064{1065 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)1066 this->__construct_at_end(__n);1067 else1068 {1069 allocator_type& __a = this->__alloc();1070 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);1071 __v.__construct_at_end(__n);1072 __swap_out_circular_buffer(__v);1073 }1074}1075 1076// Default constructs __n objects starting at __end_1077// throws if construction throws1078// Postcondition: size() == size() + __n1079// Exception safety: strong.1080template <class _Tp, class _Allocator>1081void1082vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)1083{1084 if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)1085 this->__construct_at_end(__n, __x);1086 else1087 {1088 allocator_type& __a = this->__alloc();1089 __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);1090 __v.__construct_at_end(__n, __x);1091 __swap_out_circular_buffer(__v);1092 }1093}1094 1095template <class _Tp, class _Allocator>1096vector<_Tp, _Allocator>::vector(size_type __n)1097{1098#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1099 __get_db()->__insert_c(this);1100#endif1101 if (__n > 0)1102 {1103 __vallocate(__n);1104 __construct_at_end(__n);1105 }1106}1107 1108#if _LIBCUDACXX_STD_VER > 111109template <class _Tp, class _Allocator>1110vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)1111 : __base(__a)1112{1113#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1114 __get_db()->__insert_c(this);1115#endif1116 if (__n > 0)1117 {1118 __vallocate(__n);1119 __construct_at_end(__n);1120 }1121}1122#endif1123 1124template <class _Tp, class _Allocator>1125vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)1126{1127#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1128 __get_db()->__insert_c(this);1129#endif1130 if (__n > 0)1131 {1132 __vallocate(__n);1133 __construct_at_end(__n, __x);1134 }1135}1136 1137template <class _Tp, class _Allocator>1138vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)1139 : __base(__a)1140{1141#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1142 __get_db()->__insert_c(this);1143#endif1144 if (__n > 0)1145 {1146 __vallocate(__n);1147 __construct_at_end(__n, __x);1148 }1149}1150 1151template <class _Tp, class _Allocator>1152template <class _InputIterator>1153vector<_Tp, _Allocator>::vector(_InputIterator __first,1154 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&1155 !__is_cpp17_forward_iterator<_InputIterator>::value &&1156 is_constructible<1157 value_type,1158 typename iterator_traits<_InputIterator>::reference>::value,1159 _InputIterator>::type __last)1160{1161#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1162 __get_db()->__insert_c(this);1163#endif1164 for (; __first != __last; ++__first)1165 __emplace_back(*__first);1166}1167 1168template <class _Tp, class _Allocator>1169template <class _InputIterator>1170vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,1171 typename enable_if<__is_cpp17_input_iterator <_InputIterator>::value &&1172 !__is_cpp17_forward_iterator<_InputIterator>::value &&1173 is_constructible<1174 value_type,1175 typename iterator_traits<_InputIterator>::reference>::value>::type*)1176 : __base(__a)1177{1178#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1179 __get_db()->__insert_c(this);1180#endif1181 for (; __first != __last; ++__first)1182 __emplace_back(*__first);1183}1184 1185template <class _Tp, class _Allocator>1186template <class _ForwardIterator>1187vector<_Tp, _Allocator>::vector(_ForwardIterator __first,1188 typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&1189 is_constructible<1190 value_type,1191 typename iterator_traits<_ForwardIterator>::reference>::value,1192 _ForwardIterator>::type __last)1193{1194#ifdef _LIBCUDACXX_ENABLE_DEBUG_MODE1195 __get_db()->__insert_c(this);1196#endif1197 size_type __n = static_cast<size_type>(_CUDA_VSTD::distance(__first, __last));1198 if (__n > 0)1199 {1200 __vallocate(__n);