vector revision 278724
1227825Stheraven// -*- C++ -*- 2227825Stheraven//===------------------------------ vector --------------------------------===// 3227825Stheraven// 4227825Stheraven// The LLVM Compiler Infrastructure 5227825Stheraven// 6227825Stheraven// This file is dual licensed under the MIT and the University of Illinois Open 7227825Stheraven// Source Licenses. See LICENSE.TXT for details. 8227825Stheraven// 9227825Stheraven//===----------------------------------------------------------------------===// 10227825Stheraven 11227825Stheraven#ifndef _LIBCPP_VECTOR 12227825Stheraven#define _LIBCPP_VECTOR 13227825Stheraven 14227825Stheraven/* 15227825Stheraven vector synopsis 16227825Stheraven 17227825Stheravennamespace std 18227825Stheraven{ 19227825Stheraven 20227825Stheraventemplate <class T, class Allocator = allocator<T> > 21227825Stheravenclass vector 22227825Stheraven{ 23227825Stheravenpublic: 24227825Stheraven typedef T value_type; 25227825Stheraven typedef Allocator allocator_type; 26227825Stheraven typedef typename allocator_type::reference reference; 27227825Stheraven typedef typename allocator_type::const_reference const_reference; 28227825Stheraven typedef implementation-defined iterator; 29227825Stheraven typedef implementation-defined const_iterator; 30227825Stheraven typedef typename allocator_type::size_type size_type; 31227825Stheraven typedef typename allocator_type::difference_type difference_type; 32227825Stheraven typedef typename allocator_type::pointer pointer; 33227825Stheraven typedef typename allocator_type::const_pointer const_pointer; 34227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 35227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 36227825Stheraven 37227825Stheraven vector() 38227825Stheraven noexcept(is_nothrow_default_constructible<allocator_type>::value); 39227825Stheraven explicit vector(const allocator_type&); 40227825Stheraven explicit vector(size_type n); 41262801Sdim explicit vector(size_type n, const allocator_type&); // C++14 42227825Stheraven vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 43227825Stheraven template <class InputIterator> 44227825Stheraven vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 45227825Stheraven vector(const vector& x); 46227825Stheraven vector(vector&& x) 47227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 48227825Stheraven vector(initializer_list<value_type> il); 49227825Stheraven vector(initializer_list<value_type> il, const allocator_type& a); 50227825Stheraven ~vector(); 51227825Stheraven vector& operator=(const vector& x); 52227825Stheraven vector& operator=(vector&& x) 53227825Stheraven noexcept( 54227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 55227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 56227825Stheraven vector& operator=(initializer_list<value_type> il); 57227825Stheraven template <class InputIterator> 58227825Stheraven void assign(InputIterator first, InputIterator last); 59227825Stheraven void assign(size_type n, const value_type& u); 60227825Stheraven void assign(initializer_list<value_type> il); 61227825Stheraven 62227825Stheraven allocator_type get_allocator() const noexcept; 63227825Stheraven 64227825Stheraven iterator begin() noexcept; 65227825Stheraven const_iterator begin() const noexcept; 66227825Stheraven iterator end() noexcept; 67227825Stheraven const_iterator end() const noexcept; 68227825Stheraven 69227825Stheraven reverse_iterator rbegin() noexcept; 70227825Stheraven const_reverse_iterator rbegin() const noexcept; 71227825Stheraven reverse_iterator rend() noexcept; 72227825Stheraven const_reverse_iterator rend() const noexcept; 73227825Stheraven 74227825Stheraven const_iterator cbegin() const noexcept; 75227825Stheraven const_iterator cend() const noexcept; 76227825Stheraven const_reverse_iterator crbegin() const noexcept; 77227825Stheraven const_reverse_iterator crend() const noexcept; 78227825Stheraven 79227825Stheraven size_type size() const noexcept; 80227825Stheraven size_type max_size() const noexcept; 81227825Stheraven size_type capacity() const noexcept; 82227825Stheraven bool empty() const noexcept; 83227825Stheraven void reserve(size_type n); 84227825Stheraven void shrink_to_fit() noexcept; 85227825Stheraven 86227825Stheraven reference operator[](size_type n); 87227825Stheraven const_reference operator[](size_type n) const; 88227825Stheraven reference at(size_type n); 89227825Stheraven const_reference at(size_type n) const; 90227825Stheraven 91227825Stheraven reference front(); 92227825Stheraven const_reference front() const; 93227825Stheraven reference back(); 94227825Stheraven const_reference back() const; 95227825Stheraven 96227825Stheraven value_type* data() noexcept; 97227825Stheraven const value_type* data() const noexcept; 98227825Stheraven 99227825Stheraven void push_back(const value_type& x); 100227825Stheraven void push_back(value_type&& x); 101227825Stheraven template <class... Args> 102227825Stheraven void emplace_back(Args&&... args); 103227825Stheraven void pop_back(); 104227825Stheraven 105227825Stheraven template <class... Args> iterator emplace(const_iterator position, Args&&... args); 106227825Stheraven iterator insert(const_iterator position, const value_type& x); 107227825Stheraven iterator insert(const_iterator position, value_type&& x); 108227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 109227825Stheraven template <class InputIterator> 110227825Stheraven iterator insert(const_iterator position, InputIterator first, InputIterator last); 111227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 112227825Stheraven 113227825Stheraven iterator erase(const_iterator position); 114227825Stheraven iterator erase(const_iterator first, const_iterator last); 115227825Stheraven 116227825Stheraven void clear() noexcept; 117227825Stheraven 118227825Stheraven void resize(size_type sz); 119227825Stheraven void resize(size_type sz, const value_type& c); 120227825Stheraven 121227825Stheraven void swap(vector&) 122227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 123227825Stheraven __is_nothrow_swappable<allocator_type>::value); 124227825Stheraven 125227825Stheraven bool __invariants() const; 126227825Stheraven}; 127227825Stheraven 128227825Stheraventemplate <class Allocator = allocator<T> > 129227825Stheravenclass vector<bool, Allocator> 130227825Stheraven{ 131227825Stheravenpublic: 132227825Stheraven typedef bool value_type; 133227825Stheraven typedef Allocator allocator_type; 134227825Stheraven typedef implementation-defined iterator; 135227825Stheraven typedef implementation-defined const_iterator; 136227825Stheraven typedef typename allocator_type::size_type size_type; 137227825Stheraven typedef typename allocator_type::difference_type difference_type; 138227825Stheraven typedef iterator pointer; 139227825Stheraven typedef const_iterator const_pointer; 140227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 141227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 142227825Stheraven 143227825Stheraven class reference 144227825Stheraven { 145227825Stheraven public: 146227825Stheraven reference(const reference&) noexcept; 147227825Stheraven operator bool() const noexcept; 148227825Stheraven reference& operator=(const bool x) noexcept; 149227825Stheraven reference& operator=(const reference& x) noexcept; 150227825Stheraven iterator operator&() const noexcept; 151227825Stheraven void flip() noexcept; 152227825Stheraven }; 153227825Stheraven 154227825Stheraven class const_reference 155227825Stheraven { 156227825Stheraven public: 157227825Stheraven const_reference(const reference&) noexcept; 158227825Stheraven operator bool() const noexcept; 159227825Stheraven const_iterator operator&() const noexcept; 160227825Stheraven }; 161227825Stheraven 162227825Stheraven vector() 163227825Stheraven noexcept(is_nothrow_default_constructible<allocator_type>::value); 164227825Stheraven explicit vector(const allocator_type&); 165262801Sdim explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14 166262801Sdim vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 167227825Stheraven template <class InputIterator> 168227825Stheraven vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 169227825Stheraven vector(const vector& x); 170227825Stheraven vector(vector&& x) 171227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 172227825Stheraven vector(initializer_list<value_type> il); 173227825Stheraven vector(initializer_list<value_type> il, const allocator_type& a); 174227825Stheraven ~vector(); 175227825Stheraven vector& operator=(const vector& x); 176227825Stheraven vector& operator=(vector&& x) 177227825Stheraven noexcept( 178227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 179227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 180227825Stheraven vector& operator=(initializer_list<value_type> il); 181227825Stheraven template <class InputIterator> 182227825Stheraven void assign(InputIterator first, InputIterator last); 183227825Stheraven void assign(size_type n, const value_type& u); 184227825Stheraven void assign(initializer_list<value_type> il); 185227825Stheraven 186227825Stheraven allocator_type get_allocator() const noexcept; 187227825Stheraven 188227825Stheraven iterator begin() noexcept; 189227825Stheraven const_iterator begin() const noexcept; 190227825Stheraven iterator end() noexcept; 191227825Stheraven const_iterator end() const noexcept; 192227825Stheraven 193227825Stheraven reverse_iterator rbegin() noexcept; 194227825Stheraven const_reverse_iterator rbegin() const noexcept; 195227825Stheraven reverse_iterator rend() noexcept; 196227825Stheraven const_reverse_iterator rend() const noexcept; 197227825Stheraven 198227825Stheraven const_iterator cbegin() const noexcept; 199227825Stheraven const_iterator cend() const noexcept; 200227825Stheraven const_reverse_iterator crbegin() const noexcept; 201227825Stheraven const_reverse_iterator crend() const noexcept; 202227825Stheraven 203227825Stheraven size_type size() const noexcept; 204227825Stheraven size_type max_size() const noexcept; 205227825Stheraven size_type capacity() const noexcept; 206227825Stheraven bool empty() const noexcept; 207227825Stheraven void reserve(size_type n); 208227825Stheraven void shrink_to_fit() noexcept; 209227825Stheraven 210227825Stheraven reference operator[](size_type n); 211227825Stheraven const_reference operator[](size_type n) const; 212227825Stheraven reference at(size_type n); 213227825Stheraven const_reference at(size_type n) const; 214227825Stheraven 215227825Stheraven reference front(); 216227825Stheraven const_reference front() const; 217227825Stheraven reference back(); 218227825Stheraven const_reference back() const; 219227825Stheraven 220227825Stheraven void push_back(const value_type& x); 221262801Sdim template <class... Args> void emplace_back(Args&&... args); // C++14 222227825Stheraven void pop_back(); 223227825Stheraven 224262801Sdim template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14 225227825Stheraven iterator insert(const_iterator position, const value_type& x); 226227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 227227825Stheraven template <class InputIterator> 228227825Stheraven iterator insert(const_iterator position, InputIterator first, InputIterator last); 229227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 230227825Stheraven 231227825Stheraven iterator erase(const_iterator position); 232227825Stheraven iterator erase(const_iterator first, const_iterator last); 233227825Stheraven 234227825Stheraven void clear() noexcept; 235227825Stheraven 236227825Stheraven void resize(size_type sz); 237227825Stheraven void resize(size_type sz, value_type x); 238227825Stheraven 239227825Stheraven void swap(vector&) 240227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 241227825Stheraven __is_nothrow_swappable<allocator_type>::value); 242227825Stheraven void flip() noexcept; 243227825Stheraven 244227825Stheraven bool __invariants() const; 245227825Stheraven}; 246227825Stheraven 247227825Stheraventemplate <class Allocator> struct hash<std::vector<bool, Allocator>>; 248227825Stheraven 249227825Stheraventemplate <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 250227825Stheraventemplate <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 251227825Stheraventemplate <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 252227825Stheraventemplate <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 253227825Stheraventemplate <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 254227825Stheraventemplate <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 255227825Stheraven 256227825Stheraventemplate <class T, class Allocator> 257227825Stheravenvoid swap(vector<T,Allocator>& x, vector<T,Allocator>& y) 258227825Stheraven noexcept(noexcept(x.swap(y))); 259227825Stheraven 260227825Stheraven} // std 261227825Stheraven 262227825Stheraven*/ 263227825Stheraven 264227825Stheraven#include <__config> 265227825Stheraven#include <__bit_reference> 266227825Stheraven#include <type_traits> 267227825Stheraven#include <climits> 268227825Stheraven#include <limits> 269227825Stheraven#include <initializer_list> 270227825Stheraven#include <memory> 271227825Stheraven#include <stdexcept> 272227825Stheraven#include <algorithm> 273227825Stheraven#include <cstring> 274227825Stheraven#include <__split_buffer> 275227825Stheraven#include <__functional_base> 276227825Stheraven 277232950Stheraven#include <__undef_min_max> 278232950Stheraven 279278724Sdim#include <__debug> 280262801Sdim 281227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 282227825Stheraven#pragma GCC system_header 283227825Stheraven#endif 284227825Stheraven 285227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 286227825Stheraven 287227825Stheraventemplate <bool> 288227825Stheravenclass __vector_base_common 289227825Stheraven{ 290227825Stheravenprotected: 291227825Stheraven _LIBCPP_ALWAYS_INLINE __vector_base_common() {} 292227825Stheraven void __throw_length_error() const; 293227825Stheraven void __throw_out_of_range() const; 294227825Stheraven}; 295227825Stheraven 296227825Stheraventemplate <bool __b> 297227825Stheravenvoid 298227825Stheraven__vector_base_common<__b>::__throw_length_error() const 299227825Stheraven{ 300227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 301227825Stheraven throw length_error("vector"); 302227825Stheraven#else 303227825Stheraven assert(!"vector length_error"); 304227825Stheraven#endif 305227825Stheraven} 306227825Stheraven 307227825Stheraventemplate <bool __b> 308227825Stheravenvoid 309227825Stheraven__vector_base_common<__b>::__throw_out_of_range() const 310227825Stheraven{ 311227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 312227825Stheraven throw out_of_range("vector"); 313227825Stheraven#else 314227825Stheraven assert(!"vector out_of_range"); 315227825Stheraven#endif 316227825Stheraven} 317227825Stheraven 318262801Sdim#ifdef _LIBCPP_MSVC 319227825Stheraven#pragma warning( push ) 320227825Stheraven#pragma warning( disable: 4231 ) 321262801Sdim#endif // _LIBCPP_MSVC 322262801Sdim_LIBCPP_EXTERN_TEMPLATE(class _LIBCPP_TYPE_VIS __vector_base_common<true>) 323262801Sdim#ifdef _LIBCPP_MSVC 324227825Stheraven#pragma warning( pop ) 325262801Sdim#endif // _LIBCPP_MSVC 326227825Stheraven 327227825Stheraventemplate <class _Tp, class _Allocator> 328227825Stheravenclass __vector_base 329227825Stheraven : protected __vector_base_common<true> 330227825Stheraven{ 331227825Stheravenprotected: 332227825Stheraven typedef _Tp value_type; 333227825Stheraven typedef _Allocator allocator_type; 334227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 335227825Stheraven typedef value_type& reference; 336227825Stheraven typedef const value_type& const_reference; 337227825Stheraven typedef typename __alloc_traits::size_type size_type; 338227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 339227825Stheraven typedef typename __alloc_traits::pointer pointer; 340227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 341227825Stheraven typedef pointer iterator; 342227825Stheraven typedef const_pointer const_iterator; 343227825Stheraven 344227825Stheraven pointer __begin_; 345227825Stheraven pointer __end_; 346227825Stheraven __compressed_pair<pointer, allocator_type> __end_cap_; 347227825Stheraven 348227825Stheraven _LIBCPP_INLINE_VISIBILITY 349227825Stheraven allocator_type& __alloc() _NOEXCEPT 350227825Stheraven {return __end_cap_.second();} 351227825Stheraven _LIBCPP_INLINE_VISIBILITY 352227825Stheraven const allocator_type& __alloc() const _NOEXCEPT 353227825Stheraven {return __end_cap_.second();} 354227825Stheraven _LIBCPP_INLINE_VISIBILITY 355227825Stheraven pointer& __end_cap() _NOEXCEPT 356227825Stheraven {return __end_cap_.first();} 357227825Stheraven _LIBCPP_INLINE_VISIBILITY 358227825Stheraven const pointer& __end_cap() const _NOEXCEPT 359227825Stheraven {return __end_cap_.first();} 360227825Stheraven 361227825Stheraven _LIBCPP_INLINE_VISIBILITY 362227825Stheraven __vector_base() 363227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 364227825Stheraven _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a); 365227825Stheraven ~__vector_base(); 366227825Stheraven 367227825Stheraven _LIBCPP_INLINE_VISIBILITY 368227825Stheraven void clear() _NOEXCEPT {__destruct_at_end(__begin_);} 369227825Stheraven _LIBCPP_INLINE_VISIBILITY 370227825Stheraven size_type capacity() const _NOEXCEPT 371227825Stheraven {return static_cast<size_type>(__end_cap() - __begin_);} 372227825Stheraven 373227825Stheraven _LIBCPP_INLINE_VISIBILITY 374253159Stheraven void __destruct_at_end(pointer __new_last) _NOEXCEPT; 375227825Stheraven 376227825Stheraven _LIBCPP_INLINE_VISIBILITY 377227825Stheraven void __copy_assign_alloc(const __vector_base& __c) 378227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 379227825Stheraven __alloc_traits::propagate_on_container_copy_assignment::value>());} 380227825Stheraven 381227825Stheraven _LIBCPP_INLINE_VISIBILITY 382227825Stheraven void __move_assign_alloc(__vector_base& __c) 383227825Stheraven _NOEXCEPT_( 384227825Stheraven !__alloc_traits::propagate_on_container_move_assignment::value || 385227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 386227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 387227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>());} 388227825Stheraven 389227825Stheraven _LIBCPP_INLINE_VISIBILITY 390227825Stheraven static void __swap_alloc(allocator_type& __x, allocator_type& __y) 391227825Stheraven _NOEXCEPT_( 392227825Stheraven !__alloc_traits::propagate_on_container_swap::value || 393227825Stheraven __is_nothrow_swappable<allocator_type>::value) 394227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 395227825Stheraven __alloc_traits::propagate_on_container_swap::value>());} 396227825Stheravenprivate: 397227825Stheraven _LIBCPP_INLINE_VISIBILITY 398227825Stheraven void __copy_assign_alloc(const __vector_base& __c, true_type) 399227825Stheraven { 400227825Stheraven if (__alloc() != __c.__alloc()) 401227825Stheraven { 402227825Stheraven clear(); 403227825Stheraven __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 404227825Stheraven __begin_ = __end_ = __end_cap() = nullptr; 405227825Stheraven } 406227825Stheraven __alloc() = __c.__alloc(); 407227825Stheraven } 408227825Stheraven 409227825Stheraven _LIBCPP_INLINE_VISIBILITY 410232950Stheraven void __copy_assign_alloc(const __vector_base&, false_type) 411227825Stheraven {} 412227825Stheraven 413227825Stheraven _LIBCPP_INLINE_VISIBILITY 414227825Stheraven void __move_assign_alloc(__vector_base& __c, true_type) 415227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 416227825Stheraven { 417227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 418227825Stheraven } 419227825Stheraven 420227825Stheraven _LIBCPP_INLINE_VISIBILITY 421232950Stheraven void __move_assign_alloc(__vector_base&, false_type) 422227825Stheraven _NOEXCEPT 423227825Stheraven {} 424227825Stheraven 425227825Stheraven _LIBCPP_INLINE_VISIBILITY 426227825Stheraven static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type) 427227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 428227825Stheraven { 429227825Stheraven using _VSTD::swap; 430227825Stheraven swap(__x, __y); 431227825Stheraven } 432227825Stheraven _LIBCPP_INLINE_VISIBILITY 433232950Stheraven static void __swap_alloc(allocator_type&, allocator_type&, false_type) 434227825Stheraven _NOEXCEPT 435227825Stheraven {} 436227825Stheraven}; 437227825Stheraven 438227825Stheraventemplate <class _Tp, class _Allocator> 439262801Sdiminline _LIBCPP_INLINE_VISIBILITY 440227825Stheravenvoid 441253159Stheraven__vector_base<_Tp, _Allocator>::__destruct_at_end(pointer __new_last) _NOEXCEPT 442227825Stheraven{ 443232950Stheraven while (__new_last != __end_) 444253159Stheraven __alloc_traits::destroy(__alloc(), _VSTD::__to_raw_pointer(--__end_)); 445227825Stheraven} 446227825Stheraven 447227825Stheraventemplate <class _Tp, class _Allocator> 448262801Sdiminline _LIBCPP_INLINE_VISIBILITY 449227825Stheraven__vector_base<_Tp, _Allocator>::__vector_base() 450227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 451253159Stheraven : __begin_(nullptr), 452253159Stheraven __end_(nullptr), 453253159Stheraven __end_cap_(nullptr) 454227825Stheraven{ 455227825Stheraven} 456227825Stheraven 457227825Stheraventemplate <class _Tp, class _Allocator> 458262801Sdiminline _LIBCPP_INLINE_VISIBILITY 459227825Stheraven__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a) 460253159Stheraven : __begin_(nullptr), 461253159Stheraven __end_(nullptr), 462253159Stheraven __end_cap_(nullptr, __a) 463227825Stheraven{ 464227825Stheraven} 465227825Stheraven 466227825Stheraventemplate <class _Tp, class _Allocator> 467227825Stheraven__vector_base<_Tp, _Allocator>::~__vector_base() 468227825Stheraven{ 469253159Stheraven if (__begin_ != nullptr) 470227825Stheraven { 471227825Stheraven clear(); 472227825Stheraven __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 473227825Stheraven } 474227825Stheraven} 475227825Stheraven 476227825Stheraventemplate <class _Tp, class _Allocator = allocator<_Tp> > 477262801Sdimclass _LIBCPP_TYPE_VIS_ONLY vector 478227825Stheraven : private __vector_base<_Tp, _Allocator> 479227825Stheraven{ 480227825Stheravenprivate: 481227825Stheraven typedef __vector_base<_Tp, _Allocator> __base; 482278724Sdim typedef allocator<_Tp> __default_allocator_type; 483227825Stheravenpublic: 484227825Stheraven typedef vector __self; 485227825Stheraven typedef _Tp value_type; 486227825Stheraven typedef _Allocator allocator_type; 487227825Stheraven typedef typename __base::__alloc_traits __alloc_traits; 488227825Stheraven typedef typename __base::reference reference; 489227825Stheraven typedef typename __base::const_reference const_reference; 490227825Stheraven typedef typename __base::size_type size_type; 491227825Stheraven typedef typename __base::difference_type difference_type; 492227825Stheraven typedef typename __base::pointer pointer; 493227825Stheraven typedef typename __base::const_pointer const_pointer; 494227825Stheraven typedef __wrap_iter<pointer> iterator; 495227825Stheraven typedef __wrap_iter<const_pointer> const_iterator; 496227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 497227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 498227825Stheraven 499249998Sdim static_assert((is_same<typename allocator_type::value_type, value_type>::value), 500249998Sdim "Allocator::value_type must be same type as value_type"); 501249998Sdim 502227825Stheraven _LIBCPP_INLINE_VISIBILITY 503227825Stheraven vector() 504227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 505227825Stheraven { 506227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 507227825Stheraven __get_db()->__insert_c(this); 508227825Stheraven#endif 509227825Stheraven } 510227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) 511227825Stheraven : __base(__a) 512227825Stheraven { 513227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 514227825Stheraven __get_db()->__insert_c(this); 515227825Stheraven#endif 516227825Stheraven } 517227825Stheraven explicit vector(size_type __n); 518262801Sdim#if _LIBCPP_STD_VER > 11 519262801Sdim explicit vector(size_type __n, const allocator_type& __a); 520262801Sdim#endif 521227825Stheraven vector(size_type __n, const_reference __x); 522227825Stheraven vector(size_type __n, const_reference __x, const allocator_type& __a); 523227825Stheraven template <class _InputIterator> 524262801Sdim vector(_InputIterator __first, 525227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 526249998Sdim !__is_forward_iterator<_InputIterator>::value && 527249998Sdim is_constructible< 528249998Sdim value_type, 529262801Sdim typename iterator_traits<_InputIterator>::reference>::value, 530262801Sdim _InputIterator>::type __last); 531227825Stheraven template <class _InputIterator> 532227825Stheraven vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 533227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 534249998Sdim !__is_forward_iterator<_InputIterator>::value && 535249998Sdim is_constructible< 536249998Sdim value_type, 537249998Sdim typename iterator_traits<_InputIterator>::reference>::value>::type* = 0); 538227825Stheraven template <class _ForwardIterator> 539262801Sdim vector(_ForwardIterator __first, 540249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 541249998Sdim is_constructible< 542249998Sdim value_type, 543262801Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 544262801Sdim _ForwardIterator>::type __last); 545227825Stheraven template <class _ForwardIterator> 546227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 547249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 548249998Sdim is_constructible< 549249998Sdim value_type, 550249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0); 551227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 552227825Stheraven _LIBCPP_INLINE_VISIBILITY 553227825Stheraven vector(initializer_list<value_type> __il); 554227825Stheraven _LIBCPP_INLINE_VISIBILITY 555227825Stheraven vector(initializer_list<value_type> __il, const allocator_type& __a); 556227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 557227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 558227825Stheraven _LIBCPP_INLINE_VISIBILITY 559227825Stheraven ~vector() 560227825Stheraven { 561227825Stheraven __get_db()->__erase_c(this); 562227825Stheraven } 563227825Stheraven#endif 564227825Stheraven 565227825Stheraven vector(const vector& __x); 566227825Stheraven vector(const vector& __x, const allocator_type& __a); 567227825Stheraven _LIBCPP_INLINE_VISIBILITY 568227825Stheraven vector& operator=(const vector& __x); 569227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 570227825Stheraven _LIBCPP_INLINE_VISIBILITY 571227825Stheraven vector(vector&& __x) 572227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 573227825Stheraven _LIBCPP_INLINE_VISIBILITY 574227825Stheraven vector(vector&& __x, const allocator_type& __a); 575227825Stheraven _LIBCPP_INLINE_VISIBILITY 576227825Stheraven vector& operator=(vector&& __x) 577227825Stheraven _NOEXCEPT_( 578227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 579227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 580227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 581227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 582227825Stheraven _LIBCPP_INLINE_VISIBILITY 583227825Stheraven vector& operator=(initializer_list<value_type> __il) 584227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 585227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 586227825Stheraven 587227825Stheraven template <class _InputIterator> 588227825Stheraven typename enable_if 589227825Stheraven < 590227825Stheraven __is_input_iterator <_InputIterator>::value && 591249998Sdim !__is_forward_iterator<_InputIterator>::value && 592249998Sdim is_constructible< 593249998Sdim value_type, 594249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 595227825Stheraven void 596227825Stheraven >::type 597227825Stheraven assign(_InputIterator __first, _InputIterator __last); 598227825Stheraven template <class _ForwardIterator> 599227825Stheraven typename enable_if 600227825Stheraven < 601249998Sdim __is_forward_iterator<_ForwardIterator>::value && 602249998Sdim is_constructible< 603249998Sdim value_type, 604249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 605227825Stheraven void 606227825Stheraven >::type 607227825Stheraven assign(_ForwardIterator __first, _ForwardIterator __last); 608227825Stheraven 609227825Stheraven void assign(size_type __n, const_reference __u); 610227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 611227825Stheraven _LIBCPP_INLINE_VISIBILITY 612227825Stheraven void assign(initializer_list<value_type> __il) 613227825Stheraven {assign(__il.begin(), __il.end());} 614227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 615227825Stheraven 616227825Stheraven _LIBCPP_INLINE_VISIBILITY 617227825Stheraven allocator_type get_allocator() const _NOEXCEPT 618227825Stheraven {return this->__alloc();} 619227825Stheraven 620227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT; 621227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT; 622227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT; 623227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT; 624227825Stheraven 625227825Stheraven _LIBCPP_INLINE_VISIBILITY 626227825Stheraven reverse_iterator rbegin() _NOEXCEPT 627227825Stheraven {return reverse_iterator(end());} 628227825Stheraven _LIBCPP_INLINE_VISIBILITY 629227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 630227825Stheraven {return const_reverse_iterator(end());} 631227825Stheraven _LIBCPP_INLINE_VISIBILITY 632227825Stheraven reverse_iterator rend() _NOEXCEPT 633227825Stheraven {return reverse_iterator(begin());} 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 636227825Stheraven {return const_reverse_iterator(begin());} 637227825Stheraven 638227825Stheraven _LIBCPP_INLINE_VISIBILITY 639227825Stheraven const_iterator cbegin() const _NOEXCEPT 640227825Stheraven {return begin();} 641227825Stheraven _LIBCPP_INLINE_VISIBILITY 642227825Stheraven const_iterator cend() const _NOEXCEPT 643227825Stheraven {return end();} 644227825Stheraven _LIBCPP_INLINE_VISIBILITY 645227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 646227825Stheraven {return rbegin();} 647227825Stheraven _LIBCPP_INLINE_VISIBILITY 648227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 649227825Stheraven {return rend();} 650227825Stheraven 651227825Stheraven _LIBCPP_INLINE_VISIBILITY 652227825Stheraven size_type size() const _NOEXCEPT 653227825Stheraven {return static_cast<size_type>(this->__end_ - this->__begin_);} 654227825Stheraven _LIBCPP_INLINE_VISIBILITY 655227825Stheraven size_type capacity() const _NOEXCEPT 656227825Stheraven {return __base::capacity();} 657227825Stheraven _LIBCPP_INLINE_VISIBILITY 658227825Stheraven bool empty() const _NOEXCEPT 659227825Stheraven {return this->__begin_ == this->__end_;} 660227825Stheraven size_type max_size() const _NOEXCEPT; 661227825Stheraven void reserve(size_type __n); 662227825Stheraven void shrink_to_fit() _NOEXCEPT; 663227825Stheraven 664227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); 665227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; 666227825Stheraven reference at(size_type __n); 667227825Stheraven const_reference at(size_type __n) const; 668227825Stheraven 669227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() 670227825Stheraven { 671227825Stheraven _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 672227825Stheraven return *this->__begin_; 673227825Stheraven } 674227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const 675227825Stheraven { 676227825Stheraven _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 677227825Stheraven return *this->__begin_; 678227825Stheraven } 679227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() 680227825Stheraven { 681227825Stheraven _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 682227825Stheraven return *(this->__end_ - 1); 683227825Stheraven } 684227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const 685227825Stheraven { 686227825Stheraven _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 687227825Stheraven return *(this->__end_ - 1); 688227825Stheraven } 689227825Stheraven 690227825Stheraven _LIBCPP_INLINE_VISIBILITY 691227825Stheraven value_type* data() _NOEXCEPT 692227825Stheraven {return _VSTD::__to_raw_pointer(this->__begin_);} 693227825Stheraven _LIBCPP_INLINE_VISIBILITY 694227825Stheraven const value_type* data() const _NOEXCEPT 695227825Stheraven {return _VSTD::__to_raw_pointer(this->__begin_);} 696227825Stheraven 697227825Stheraven _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 698227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 699232950Stheraven _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x); 700227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 701227825Stheraven template <class... _Args> 702227825Stheraven void emplace_back(_Args&&... __args); 703227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 704227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 705227825Stheraven void pop_back(); 706227825Stheraven 707227825Stheraven iterator insert(const_iterator __position, const_reference __x); 708227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 709227825Stheraven iterator insert(const_iterator __position, value_type&& __x); 710227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 711227825Stheraven template <class... _Args> 712227825Stheraven iterator emplace(const_iterator __position, _Args&&... __args); 713227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 714227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 715227825Stheraven iterator insert(const_iterator __position, size_type __n, const_reference __x); 716227825Stheraven template <class _InputIterator> 717227825Stheraven typename enable_if 718227825Stheraven < 719227825Stheraven __is_input_iterator <_InputIterator>::value && 720249998Sdim !__is_forward_iterator<_InputIterator>::value && 721249998Sdim is_constructible< 722249998Sdim value_type, 723249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 724227825Stheraven iterator 725227825Stheraven >::type 726227825Stheraven insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 727227825Stheraven template <class _ForwardIterator> 728227825Stheraven typename enable_if 729227825Stheraven < 730249998Sdim __is_forward_iterator<_ForwardIterator>::value && 731249998Sdim is_constructible< 732249998Sdim value_type, 733249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 734227825Stheraven iterator 735227825Stheraven >::type 736227825Stheraven insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 737227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 738227825Stheraven _LIBCPP_INLINE_VISIBILITY 739227825Stheraven iterator insert(const_iterator __position, initializer_list<value_type> __il) 740227825Stheraven {return insert(__position, __il.begin(), __il.end());} 741227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 742227825Stheraven 743227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 744227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 745227825Stheraven 746227825Stheraven _LIBCPP_INLINE_VISIBILITY 747227825Stheraven void clear() _NOEXCEPT 748227825Stheraven { 749278724Sdim size_type __old_size = size(); 750227825Stheraven __base::clear(); 751278724Sdim __annotate_shrink(__old_size); 752227825Stheraven __invalidate_all_iterators(); 753227825Stheraven } 754227825Stheraven 755227825Stheraven void resize(size_type __sz); 756227825Stheraven void resize(size_type __sz, const_reference __x); 757227825Stheraven 758227825Stheraven void swap(vector&) 759227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 760227825Stheraven __is_nothrow_swappable<allocator_type>::value); 761227825Stheraven 762227825Stheraven bool __invariants() const; 763227825Stheraven 764227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 765227825Stheraven 766227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 767227825Stheraven bool __decrementable(const const_iterator* __i) const; 768227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 769227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 770227825Stheraven 771227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 772227825Stheraven 773227825Stheravenprivate: 774227825Stheraven _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 775227825Stheraven void allocate(size_type __n); 776227825Stheraven void deallocate() _NOEXCEPT; 777227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 778227825Stheraven void __construct_at_end(size_type __n); 779227825Stheraven void __construct_at_end(size_type __n, const_reference __x); 780227825Stheraven template <class _ForwardIterator> 781227825Stheraven typename enable_if 782227825Stheraven < 783227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 784227825Stheraven void 785227825Stheraven >::type 786227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 787227825Stheraven void __append(size_type __n); 788227825Stheraven void __append(size_type __n, const_reference __x); 789227825Stheraven _LIBCPP_INLINE_VISIBILITY 790227825Stheraven iterator __make_iter(pointer __p) _NOEXCEPT; 791227825Stheraven _LIBCPP_INLINE_VISIBILITY 792227825Stheraven const_iterator __make_iter(const_pointer __p) const _NOEXCEPT; 793227825Stheraven void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); 794227825Stheraven pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); 795227825Stheraven void __move_range(pointer __from_s, pointer __from_e, pointer __to); 796227825Stheraven void __move_assign(vector& __c, true_type) 797227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 798227825Stheraven void __move_assign(vector& __c, false_type); 799227825Stheraven _LIBCPP_INLINE_VISIBILITY 800253159Stheraven void __destruct_at_end(pointer __new_last) _NOEXCEPT 801227825Stheraven { 802227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 803227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 804227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 805227825Stheraven { 806227825Stheraven --__p; 807227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 808227825Stheraven if (__i->base() > __new_last) 809227825Stheraven { 810227825Stheraven (*__p)->__c_ = nullptr; 811227825Stheraven if (--__c->end_ != __p) 812227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 813227825Stheraven } 814227825Stheraven } 815227825Stheraven __get_db()->unlock(); 816227825Stheraven#endif 817278724Sdim size_type __old_size = size(); 818227825Stheraven __base::__destruct_at_end(__new_last); 819278724Sdim __annotate_shrink(__old_size); 820227825Stheraven } 821232950Stheraven template <class _Up> 822232950Stheraven void 823232950Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 824232950Stheraven __push_back_slow_path(_Up&& __x); 825232950Stheraven#else 826232950Stheraven __push_back_slow_path(_Up& __x); 827232950Stheraven#endif 828232950Stheraven#if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 829232950Stheraven template <class... _Args> 830232950Stheraven void 831232950Stheraven __emplace_back_slow_path(_Args&&... __args); 832232950Stheraven#endif 833278724Sdim // The following functions are no-ops outside of AddressSanitizer mode. 834278724Sdim // We call annotatations only for the default Allocator because other allocators 835278724Sdim // may not meet the AddressSanitizer alignment constraints. 836278724Sdim // See the documentation for __sanitizer_annotate_contiguous_container for more details. 837278724Sdim void __annotate_contiguous_container 838278724Sdim (const void *__beg, const void *__end, const void *__old_mid, const void *__new_mid) const 839278724Sdim { 840278724Sdim#ifndef _LIBCPP_HAS_NO_ASAN 841278724Sdim if (__beg && is_same<allocator_type, __default_allocator_type>::value) 842278724Sdim __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid); 843278724Sdim#endif 844278724Sdim } 845278724Sdim 846278724Sdim void __annotate_new(size_type __current_size) const 847278724Sdim { 848278724Sdim __annotate_contiguous_container(data(), data() + capacity(), 849278724Sdim data() + capacity(), data() + __current_size); 850278724Sdim } 851278724Sdim void __annotate_delete() const 852278724Sdim { 853278724Sdim __annotate_contiguous_container(data(), data() + capacity(), 854278724Sdim data() + size(), data() + capacity()); 855278724Sdim } 856278724Sdim void __annotate_increase(size_type __n) const 857278724Sdim { 858278724Sdim __annotate_contiguous_container(data(), data() + capacity(), 859278724Sdim data() + size(), data() + size() + __n); 860278724Sdim } 861278724Sdim void __annotate_shrink(size_type __old_size) const 862278724Sdim { 863278724Sdim __annotate_contiguous_container(data(), data() + capacity(), 864278724Sdim data() + __old_size, data() + size()); 865278724Sdim } 866278724Sdim#ifndef _LIBCPP_HAS_NO_ASAN 867278724Sdim // The annotation for size increase should happen before the actual increase, 868278724Sdim // but if an exception is thrown after that the annotation has to be undone. 869278724Sdim struct __RAII_IncreaseAnnotator { 870278724Sdim __RAII_IncreaseAnnotator(const vector &__v, size_type __n = 1) 871278724Sdim : __commit(false), __v(__v), __n(__n) { 872278724Sdim __v.__annotate_increase(__n); 873278724Sdim } 874278724Sdim void __done() { __commit = true; } 875278724Sdim ~__RAII_IncreaseAnnotator() { 876278724Sdim if (__commit) return; 877278724Sdim __v.__annotate_shrink(__v.size() + __n); 878278724Sdim } 879278724Sdim bool __commit; 880278724Sdim size_type __n; 881278724Sdim const vector &__v; 882278724Sdim }; 883278724Sdim#else 884278724Sdim struct __RAII_IncreaseAnnotator { 885278724Sdim inline __RAII_IncreaseAnnotator(const vector &, size_type __n = 1) {} 886278724Sdim inline void __done() {} 887278724Sdim }; 888278724Sdim#endif 889278724Sdim 890227825Stheraven}; 891227825Stheraven 892227825Stheraventemplate <class _Tp, class _Allocator> 893227825Stheravenvoid 894227825Stheravenvector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) 895227825Stheraven{ 896278724Sdim __annotate_delete(); 897232950Stheraven __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_); 898227825Stheraven _VSTD::swap(this->__begin_, __v.__begin_); 899227825Stheraven _VSTD::swap(this->__end_, __v.__end_); 900227825Stheraven _VSTD::swap(this->__end_cap(), __v.__end_cap()); 901227825Stheraven __v.__first_ = __v.__begin_; 902278724Sdim __annotate_new(size()); 903227825Stheraven __invalidate_all_iterators(); 904227825Stheraven} 905227825Stheraven 906227825Stheraventemplate <class _Tp, class _Allocator> 907227825Stheraventypename vector<_Tp, _Allocator>::pointer 908227825Stheravenvector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) 909227825Stheraven{ 910278724Sdim __annotate_delete(); 911227825Stheraven pointer __r = __v.__begin_; 912232950Stheraven __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_); 913232950Stheraven __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_); 914227825Stheraven _VSTD::swap(this->__begin_, __v.__begin_); 915227825Stheraven _VSTD::swap(this->__end_, __v.__end_); 916227825Stheraven _VSTD::swap(this->__end_cap(), __v.__end_cap()); 917227825Stheraven __v.__first_ = __v.__begin_; 918278724Sdim __annotate_new(size()); 919227825Stheraven __invalidate_all_iterators(); 920227825Stheraven return __r; 921227825Stheraven} 922227825Stheraven 923227825Stheraven// Allocate space for __n objects 924227825Stheraven// throws length_error if __n > max_size() 925227825Stheraven// throws (probably bad_alloc) if memory run out 926227825Stheraven// Precondition: __begin_ == __end_ == __end_cap() == 0 927227825Stheraven// Precondition: __n > 0 928227825Stheraven// Postcondition: capacity() == __n 929227825Stheraven// Postcondition: size() == 0 930227825Stheraventemplate <class _Tp, class _Allocator> 931227825Stheravenvoid 932227825Stheravenvector<_Tp, _Allocator>::allocate(size_type __n) 933227825Stheraven{ 934227825Stheraven if (__n > max_size()) 935227825Stheraven this->__throw_length_error(); 936227825Stheraven this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); 937227825Stheraven this->__end_cap() = this->__begin_ + __n; 938278724Sdim __annotate_new(0); 939227825Stheraven} 940227825Stheraven 941227825Stheraventemplate <class _Tp, class _Allocator> 942227825Stheravenvoid 943227825Stheravenvector<_Tp, _Allocator>::deallocate() _NOEXCEPT 944227825Stheraven{ 945253159Stheraven if (this->__begin_ != nullptr) 946227825Stheraven { 947227825Stheraven clear(); 948227825Stheraven __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); 949253159Stheraven this->__begin_ = this->__end_ = this->__end_cap() = nullptr; 950227825Stheraven } 951227825Stheraven} 952227825Stheraven 953227825Stheraventemplate <class _Tp, class _Allocator> 954227825Stheraventypename vector<_Tp, _Allocator>::size_type 955227825Stheravenvector<_Tp, _Allocator>::max_size() const _NOEXCEPT 956227825Stheraven{ 957227825Stheraven return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always 958227825Stheraven} 959227825Stheraven 960227825Stheraven// Precondition: __new_size > capacity() 961227825Stheraventemplate <class _Tp, class _Allocator> 962262801Sdiminline _LIBCPP_INLINE_VISIBILITY 963227825Stheraventypename vector<_Tp, _Allocator>::size_type 964227825Stheravenvector<_Tp, _Allocator>::__recommend(size_type __new_size) const 965227825Stheraven{ 966227825Stheraven const size_type __ms = max_size(); 967227825Stheraven if (__new_size > __ms) 968227825Stheraven this->__throw_length_error(); 969227825Stheraven const size_type __cap = capacity(); 970227825Stheraven if (__cap >= __ms / 2) 971227825Stheraven return __ms; 972227825Stheraven return _VSTD::max<size_type>(2*__cap, __new_size); 973227825Stheraven} 974227825Stheraven 975227825Stheraven// Default constructs __n objects starting at __end_ 976227825Stheraven// throws if construction throws 977227825Stheraven// Precondition: __n > 0 978227825Stheraven// Precondition: size() + __n <= capacity() 979227825Stheraven// Postcondition: size() == size() + __n 980227825Stheraventemplate <class _Tp, class _Allocator> 981227825Stheravenvoid 982227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(size_type __n) 983227825Stheraven{ 984227825Stheraven allocator_type& __a = this->__alloc(); 985227825Stheraven do 986227825Stheraven { 987278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 988227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 989227825Stheraven ++this->__end_; 990227825Stheraven --__n; 991278724Sdim __annotator.__done(); 992227825Stheraven } while (__n > 0); 993227825Stheraven} 994227825Stheraven 995227825Stheraven// Copy constructs __n objects starting at __end_ from __x 996227825Stheraven// throws if construction throws 997227825Stheraven// Precondition: __n > 0 998227825Stheraven// Precondition: size() + __n <= capacity() 999227825Stheraven// Postcondition: size() == old size() + __n 1000227825Stheraven// Postcondition: [i] == __x for all i in [size() - __n, __n) 1001227825Stheraventemplate <class _Tp, class _Allocator> 1002262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1003227825Stheravenvoid 1004227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 1005227825Stheraven{ 1006227825Stheraven allocator_type& __a = this->__alloc(); 1007227825Stheraven do 1008227825Stheraven { 1009278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1010227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 1011227825Stheraven ++this->__end_; 1012227825Stheraven --__n; 1013278724Sdim __annotator.__done(); 1014227825Stheraven } while (__n > 0); 1015227825Stheraven} 1016227825Stheraven 1017227825Stheraventemplate <class _Tp, class _Allocator> 1018227825Stheraventemplate <class _ForwardIterator> 1019227825Stheraventypename enable_if 1020227825Stheraven< 1021227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 1022227825Stheraven void 1023227825Stheraven>::type 1024227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 1025227825Stheraven{ 1026227825Stheraven allocator_type& __a = this->__alloc(); 1027227825Stheraven for (; __first != __last; ++__first) 1028227825Stheraven { 1029278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1030227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 1031278724Sdim __annotator.__done(); 1032227825Stheraven ++this->__end_; 1033227825Stheraven } 1034227825Stheraven} 1035227825Stheraven 1036227825Stheraven// Default constructs __n objects starting at __end_ 1037227825Stheraven// throws if construction throws 1038227825Stheraven// Postcondition: size() == size() + __n 1039227825Stheraven// Exception safety: strong. 1040227825Stheraventemplate <class _Tp, class _Allocator> 1041227825Stheravenvoid 1042227825Stheravenvector<_Tp, _Allocator>::__append(size_type __n) 1043227825Stheraven{ 1044227825Stheraven if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 1045227825Stheraven this->__construct_at_end(__n); 1046227825Stheraven else 1047227825Stheraven { 1048227825Stheraven allocator_type& __a = this->__alloc(); 1049227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 1050227825Stheraven __v.__construct_at_end(__n); 1051227825Stheraven __swap_out_circular_buffer(__v); 1052227825Stheraven } 1053227825Stheraven} 1054227825Stheraven 1055227825Stheraven// Default constructs __n objects starting at __end_ 1056227825Stheraven// throws if construction throws 1057227825Stheraven// Postcondition: size() == size() + __n 1058227825Stheraven// Exception safety: strong. 1059227825Stheraventemplate <class _Tp, class _Allocator> 1060227825Stheravenvoid 1061227825Stheravenvector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) 1062227825Stheraven{ 1063227825Stheraven if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 1064227825Stheraven this->__construct_at_end(__n, __x); 1065227825Stheraven else 1066227825Stheraven { 1067227825Stheraven allocator_type& __a = this->__alloc(); 1068227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 1069227825Stheraven __v.__construct_at_end(__n, __x); 1070227825Stheraven __swap_out_circular_buffer(__v); 1071227825Stheraven } 1072227825Stheraven} 1073227825Stheraven 1074227825Stheraventemplate <class _Tp, class _Allocator> 1075227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n) 1076227825Stheraven{ 1077227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1078227825Stheraven __get_db()->__insert_c(this); 1079227825Stheraven#endif 1080227825Stheraven if (__n > 0) 1081227825Stheraven { 1082227825Stheraven allocate(__n); 1083227825Stheraven __construct_at_end(__n); 1084227825Stheraven } 1085227825Stheraven} 1086227825Stheraven 1087262801Sdim#if _LIBCPP_STD_VER > 11 1088227825Stheraventemplate <class _Tp, class _Allocator> 1089262801Sdimvector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a) 1090262801Sdim : __base(__a) 1091262801Sdim{ 1092262801Sdim#if _LIBCPP_DEBUG_LEVEL >= 2 1093262801Sdim __get_db()->__insert_c(this); 1094262801Sdim#endif 1095262801Sdim if (__n > 0) 1096262801Sdim { 1097262801Sdim allocate(__n); 1098262801Sdim __construct_at_end(__n); 1099262801Sdim } 1100262801Sdim} 1101262801Sdim#endif 1102262801Sdim 1103262801Sdimtemplate <class _Tp, class _Allocator> 1104227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) 1105227825Stheraven{ 1106227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1107227825Stheraven __get_db()->__insert_c(this); 1108227825Stheraven#endif 1109227825Stheraven if (__n > 0) 1110227825Stheraven { 1111227825Stheraven allocate(__n); 1112227825Stheraven __construct_at_end(__n, __x); 1113227825Stheraven } 1114227825Stheraven} 1115227825Stheraven 1116227825Stheraventemplate <class _Tp, class _Allocator> 1117227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) 1118227825Stheraven : __base(__a) 1119227825Stheraven{ 1120227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1121227825Stheraven __get_db()->__insert_c(this); 1122227825Stheraven#endif 1123227825Stheraven if (__n > 0) 1124227825Stheraven { 1125227825Stheraven allocate(__n); 1126227825Stheraven __construct_at_end(__n, __x); 1127227825Stheraven } 1128227825Stheraven} 1129227825Stheraven 1130227825Stheraventemplate <class _Tp, class _Allocator> 1131227825Stheraventemplate <class _InputIterator> 1132262801Sdimvector<_Tp, _Allocator>::vector(_InputIterator __first, 1133227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 1134249998Sdim !__is_forward_iterator<_InputIterator>::value && 1135249998Sdim is_constructible< 1136249998Sdim value_type, 1137262801Sdim typename iterator_traits<_InputIterator>::reference>::value, 1138262801Sdim _InputIterator>::type __last) 1139227825Stheraven{ 1140227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1141227825Stheraven __get_db()->__insert_c(this); 1142227825Stheraven#endif 1143227825Stheraven for (; __first != __last; ++__first) 1144227825Stheraven push_back(*__first); 1145227825Stheraven} 1146227825Stheraven 1147227825Stheraventemplate <class _Tp, class _Allocator> 1148227825Stheraventemplate <class _InputIterator> 1149227825Stheravenvector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 1150227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 1151249998Sdim !__is_forward_iterator<_InputIterator>::value && 1152249998Sdim is_constructible< 1153249998Sdim value_type, 1154249998Sdim typename iterator_traits<_InputIterator>::reference>::value>::type*) 1155227825Stheraven : __base(__a) 1156227825Stheraven{ 1157227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1158227825Stheraven __get_db()->__insert_c(this); 1159227825Stheraven#endif 1160227825Stheraven for (; __first != __last; ++__first) 1161227825Stheraven push_back(*__first); 1162227825Stheraven} 1163227825Stheraven 1164227825Stheraventemplate <class _Tp, class _Allocator> 1165227825Stheraventemplate <class _ForwardIterator> 1166262801Sdimvector<_Tp, _Allocator>::vector(_ForwardIterator __first, 1167249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 1168249998Sdim is_constructible< 1169249998Sdim value_type, 1170262801Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 1171262801Sdim _ForwardIterator>::type __last) 1172227825Stheraven{ 1173227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1174227825Stheraven __get_db()->__insert_c(this); 1175227825Stheraven#endif 1176227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1177227825Stheraven if (__n > 0) 1178227825Stheraven { 1179227825Stheraven allocate(__n); 1180227825Stheraven __construct_at_end(__first, __last); 1181227825Stheraven } 1182227825Stheraven} 1183227825Stheraven 1184227825Stheraventemplate <class _Tp, class _Allocator> 1185227825Stheraventemplate <class _ForwardIterator> 1186227825Stheravenvector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 1187249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 1188249998Sdim is_constructible< 1189249998Sdim value_type, 1190249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value>::type*) 1191227825Stheraven : __base(__a) 1192227825Stheraven{ 1193227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1194227825Stheraven __get_db()->__insert_c(this); 1195227825Stheraven#endif 1196227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1197227825Stheraven if (__n > 0) 1198227825Stheraven { 1199227825Stheraven allocate(__n); 1200227825Stheraven __construct_at_end(__first, __last); 1201227825Stheraven } 1202227825Stheraven} 1203227825Stheraven 1204227825Stheraventemplate <class _Tp, class _Allocator> 1205227825Stheravenvector<_Tp, _Allocator>::vector(const vector& __x) 1206227825Stheraven : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) 1207227825Stheraven{ 1208227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1209227825Stheraven __get_db()->__insert_c(this); 1210227825Stheraven#endif 1211227825Stheraven size_type __n = __x.size(); 1212227825Stheraven if (__n > 0) 1213227825Stheraven { 1214227825Stheraven allocate(__n); 1215227825Stheraven __construct_at_end(__x.__begin_, __x.__end_); 1216227825Stheraven } 1217227825Stheraven} 1218227825Stheraven 1219227825Stheraventemplate <class _Tp, class _Allocator> 1220227825Stheravenvector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) 1221227825Stheraven : __base(__a) 1222227825Stheraven{ 1223227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1224227825Stheraven __get_db()->__insert_c(this); 1225227825Stheraven#endif 1226227825Stheraven size_type __n = __x.size(); 1227227825Stheraven if (__n > 0) 1228227825Stheraven { 1229227825Stheraven allocate(__n); 1230227825Stheraven __construct_at_end(__x.__begin_, __x.__end_); 1231227825Stheraven } 1232227825Stheraven} 1233227825Stheraven 1234227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1235227825Stheraven 1236227825Stheraventemplate <class _Tp, class _Allocator> 1237262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1238227825Stheravenvector<_Tp, _Allocator>::vector(vector&& __x) 1239227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1240227825Stheraven : __base(_VSTD::move(__x.__alloc())) 1241227825Stheraven{ 1242227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1243227825Stheraven __get_db()->__insert_c(this); 1244227825Stheraven __get_db()->swap(this, &__x); 1245227825Stheraven#endif 1246227825Stheraven this->__begin_ = __x.__begin_; 1247227825Stheraven this->__end_ = __x.__end_; 1248227825Stheraven this->__end_cap() = __x.__end_cap(); 1249253159Stheraven __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1250227825Stheraven} 1251227825Stheraven 1252227825Stheraventemplate <class _Tp, class _Allocator> 1253262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1254227825Stheravenvector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) 1255227825Stheraven : __base(__a) 1256227825Stheraven{ 1257227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1258227825Stheraven __get_db()->__insert_c(this); 1259227825Stheraven#endif 1260227825Stheraven if (__a == __x.__alloc()) 1261227825Stheraven { 1262227825Stheraven this->__begin_ = __x.__begin_; 1263227825Stheraven this->__end_ = __x.__end_; 1264227825Stheraven this->__end_cap() = __x.__end_cap(); 1265227825Stheraven __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1266227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1267227825Stheraven __get_db()->swap(this, &__x); 1268227825Stheraven#endif 1269227825Stheraven } 1270227825Stheraven else 1271227825Stheraven { 1272232950Stheraven typedef move_iterator<iterator> _Ip; 1273232950Stheraven assign(_Ip(__x.begin()), _Ip(__x.end())); 1274227825Stheraven } 1275227825Stheraven} 1276227825Stheraven 1277227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1278227825Stheraven 1279227825Stheraventemplate <class _Tp, class _Allocator> 1280262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1281227825Stheravenvector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) 1282227825Stheraven{ 1283227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1284227825Stheraven __get_db()->__insert_c(this); 1285227825Stheraven#endif 1286227825Stheraven if (__il.size() > 0) 1287227825Stheraven { 1288227825Stheraven allocate(__il.size()); 1289227825Stheraven __construct_at_end(__il.begin(), __il.end()); 1290227825Stheraven } 1291227825Stheraven} 1292227825Stheraven 1293227825Stheraventemplate <class _Tp, class _Allocator> 1294262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1295227825Stheravenvector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 1296227825Stheraven : __base(__a) 1297227825Stheraven{ 1298227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1299227825Stheraven __get_db()->__insert_c(this); 1300227825Stheraven#endif 1301227825Stheraven if (__il.size() > 0) 1302227825Stheraven { 1303227825Stheraven allocate(__il.size()); 1304227825Stheraven __construct_at_end(__il.begin(), __il.end()); 1305227825Stheraven } 1306227825Stheraven} 1307227825Stheraven 1308227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1309227825Stheraven 1310227825Stheraventemplate <class _Tp, class _Allocator> 1311262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1312227825Stheravenvector<_Tp, _Allocator>& 1313227825Stheravenvector<_Tp, _Allocator>::operator=(vector&& __x) 1314227825Stheraven _NOEXCEPT_( 1315227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 1316227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 1317227825Stheraven{ 1318227825Stheraven __move_assign(__x, integral_constant<bool, 1319227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>()); 1320227825Stheraven return *this; 1321227825Stheraven} 1322227825Stheraven 1323227825Stheraventemplate <class _Tp, class _Allocator> 1324227825Stheravenvoid 1325227825Stheravenvector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) 1326227825Stheraven{ 1327227825Stheraven if (__base::__alloc() != __c.__alloc()) 1328227825Stheraven { 1329232950Stheraven typedef move_iterator<iterator> _Ip; 1330232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1331227825Stheraven } 1332227825Stheraven else 1333227825Stheraven __move_assign(__c, true_type()); 1334227825Stheraven} 1335227825Stheraven 1336227825Stheraventemplate <class _Tp, class _Allocator> 1337227825Stheravenvoid 1338227825Stheravenvector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) 1339227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1340227825Stheraven{ 1341227825Stheraven deallocate(); 1342278724Sdim __base::__move_assign_alloc(__c); // this can throw 1343227825Stheraven this->__begin_ = __c.__begin_; 1344227825Stheraven this->__end_ = __c.__end_; 1345227825Stheraven this->__end_cap() = __c.__end_cap(); 1346227825Stheraven __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 1347227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1348227825Stheraven __get_db()->swap(this, &__c); 1349227825Stheraven#endif 1350227825Stheraven} 1351227825Stheraven 1352227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1353227825Stheraven 1354227825Stheraventemplate <class _Tp, class _Allocator> 1355262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1356227825Stheravenvector<_Tp, _Allocator>& 1357227825Stheravenvector<_Tp, _Allocator>::operator=(const vector& __x) 1358227825Stheraven{ 1359227825Stheraven if (this != &__x) 1360227825Stheraven { 1361227825Stheraven __base::__copy_assign_alloc(__x); 1362227825Stheraven assign(__x.__begin_, __x.__end_); 1363227825Stheraven } 1364227825Stheraven return *this; 1365227825Stheraven} 1366227825Stheraven 1367227825Stheraventemplate <class _Tp, class _Allocator> 1368227825Stheraventemplate <class _InputIterator> 1369227825Stheraventypename enable_if 1370227825Stheraven< 1371227825Stheraven __is_input_iterator <_InputIterator>::value && 1372249998Sdim !__is_forward_iterator<_InputIterator>::value && 1373249998Sdim is_constructible< 1374249998Sdim _Tp, 1375249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 1376227825Stheraven void 1377227825Stheraven>::type 1378227825Stheravenvector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 1379227825Stheraven{ 1380227825Stheraven clear(); 1381227825Stheraven for (; __first != __last; ++__first) 1382227825Stheraven push_back(*__first); 1383227825Stheraven} 1384227825Stheraven 1385227825Stheraventemplate <class _Tp, class _Allocator> 1386227825Stheraventemplate <class _ForwardIterator> 1387227825Stheraventypename enable_if 1388227825Stheraven< 1389249998Sdim __is_forward_iterator<_ForwardIterator>::value && 1390249998Sdim is_constructible< 1391249998Sdim _Tp, 1392249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 1393227825Stheraven void 1394227825Stheraven>::type 1395227825Stheravenvector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 1396227825Stheraven{ 1397227825Stheraven typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last); 1398227825Stheraven if (static_cast<size_type>(__new_size) <= capacity()) 1399227825Stheraven { 1400227825Stheraven _ForwardIterator __mid = __last; 1401227825Stheraven bool __growing = false; 1402227825Stheraven if (static_cast<size_type>(__new_size) > size()) 1403227825Stheraven { 1404227825Stheraven __growing = true; 1405227825Stheraven __mid = __first; 1406227825Stheraven _VSTD::advance(__mid, size()); 1407227825Stheraven } 1408227825Stheraven pointer __m = _VSTD::copy(__first, __mid, this->__begin_); 1409227825Stheraven if (__growing) 1410227825Stheraven __construct_at_end(__mid, __last); 1411227825Stheraven else 1412227825Stheraven this->__destruct_at_end(__m); 1413227825Stheraven } 1414227825Stheraven else 1415227825Stheraven { 1416227825Stheraven deallocate(); 1417227825Stheraven allocate(__recommend(static_cast<size_type>(__new_size))); 1418227825Stheraven __construct_at_end(__first, __last); 1419227825Stheraven } 1420227825Stheraven} 1421227825Stheraven 1422227825Stheraventemplate <class _Tp, class _Allocator> 1423227825Stheravenvoid 1424227825Stheravenvector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) 1425227825Stheraven{ 1426227825Stheraven if (__n <= capacity()) 1427227825Stheraven { 1428227825Stheraven size_type __s = size(); 1429227825Stheraven _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u); 1430227825Stheraven if (__n > __s) 1431227825Stheraven __construct_at_end(__n - __s, __u); 1432227825Stheraven else 1433227825Stheraven this->__destruct_at_end(this->__begin_ + __n); 1434227825Stheraven } 1435227825Stheraven else 1436227825Stheraven { 1437227825Stheraven deallocate(); 1438227825Stheraven allocate(__recommend(static_cast<size_type>(__n))); 1439227825Stheraven __construct_at_end(__n, __u); 1440227825Stheraven } 1441227825Stheraven} 1442227825Stheraven 1443227825Stheraventemplate <class _Tp, class _Allocator> 1444262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1445227825Stheraventypename vector<_Tp, _Allocator>::iterator 1446227825Stheravenvector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT 1447227825Stheraven{ 1448227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1449227825Stheraven return iterator(this, __p); 1450227825Stheraven#else 1451227825Stheraven return iterator(__p); 1452227825Stheraven#endif 1453227825Stheraven} 1454227825Stheraven 1455227825Stheraventemplate <class _Tp, class _Allocator> 1456262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1457227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1458227825Stheravenvector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT 1459227825Stheraven{ 1460227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1461227825Stheraven return const_iterator(this, __p); 1462227825Stheraven#else 1463227825Stheraven return const_iterator(__p); 1464227825Stheraven#endif 1465227825Stheraven} 1466227825Stheraven 1467227825Stheraventemplate <class _Tp, class _Allocator> 1468262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1469227825Stheraventypename vector<_Tp, _Allocator>::iterator 1470227825Stheravenvector<_Tp, _Allocator>::begin() _NOEXCEPT 1471227825Stheraven{ 1472227825Stheraven return __make_iter(this->__begin_); 1473227825Stheraven} 1474227825Stheraven 1475227825Stheraventemplate <class _Tp, class _Allocator> 1476262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1477227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1478227825Stheravenvector<_Tp, _Allocator>::begin() const _NOEXCEPT 1479227825Stheraven{ 1480227825Stheraven return __make_iter(this->__begin_); 1481227825Stheraven} 1482227825Stheraven 1483227825Stheraventemplate <class _Tp, class _Allocator> 1484262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1485227825Stheraventypename vector<_Tp, _Allocator>::iterator 1486227825Stheravenvector<_Tp, _Allocator>::end() _NOEXCEPT 1487227825Stheraven{ 1488227825Stheraven return __make_iter(this->__end_); 1489227825Stheraven} 1490227825Stheraven 1491227825Stheraventemplate <class _Tp, class _Allocator> 1492262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1493227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1494227825Stheravenvector<_Tp, _Allocator>::end() const _NOEXCEPT 1495227825Stheraven{ 1496227825Stheraven return __make_iter(this->__end_); 1497227825Stheraven} 1498227825Stheraven 1499227825Stheraventemplate <class _Tp, class _Allocator> 1500262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1501227825Stheraventypename vector<_Tp, _Allocator>::reference 1502227825Stheravenvector<_Tp, _Allocator>::operator[](size_type __n) 1503227825Stheraven{ 1504227825Stheraven _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1505227825Stheraven return this->__begin_[__n]; 1506227825Stheraven} 1507227825Stheraven 1508227825Stheraventemplate <class _Tp, class _Allocator> 1509262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1510227825Stheraventypename vector<_Tp, _Allocator>::const_reference 1511227825Stheravenvector<_Tp, _Allocator>::operator[](size_type __n) const 1512227825Stheraven{ 1513227825Stheraven _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1514227825Stheraven return this->__begin_[__n]; 1515227825Stheraven} 1516227825Stheraven 1517227825Stheraventemplate <class _Tp, class _Allocator> 1518227825Stheraventypename vector<_Tp, _Allocator>::reference 1519227825Stheravenvector<_Tp, _Allocator>::at(size_type __n) 1520227825Stheraven{ 1521227825Stheraven if (__n >= size()) 1522227825Stheraven this->__throw_out_of_range(); 1523227825Stheraven return this->__begin_[__n]; 1524227825Stheraven} 1525227825Stheraven 1526227825Stheraventemplate <class _Tp, class _Allocator> 1527227825Stheraventypename vector<_Tp, _Allocator>::const_reference 1528227825Stheravenvector<_Tp, _Allocator>::at(size_type __n) const 1529227825Stheraven{ 1530227825Stheraven if (__n >= size()) 1531227825Stheraven this->__throw_out_of_range(); 1532227825Stheraven return this->__begin_[__n]; 1533227825Stheraven} 1534227825Stheraven 1535227825Stheraventemplate <class _Tp, class _Allocator> 1536227825Stheravenvoid 1537227825Stheravenvector<_Tp, _Allocator>::reserve(size_type __n) 1538227825Stheraven{ 1539227825Stheraven if (__n > capacity()) 1540227825Stheraven { 1541227825Stheraven allocator_type& __a = this->__alloc(); 1542227825Stheraven __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); 1543227825Stheraven __swap_out_circular_buffer(__v); 1544227825Stheraven } 1545227825Stheraven} 1546227825Stheraven 1547227825Stheraventemplate <class _Tp, class _Allocator> 1548227825Stheravenvoid 1549227825Stheravenvector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1550227825Stheraven{ 1551227825Stheraven if (capacity() > size()) 1552227825Stheraven { 1553227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1554227825Stheraven try 1555227825Stheraven { 1556227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1557227825Stheraven allocator_type& __a = this->__alloc(); 1558227825Stheraven __split_buffer<value_type, allocator_type&> __v(size(), size(), __a); 1559227825Stheraven __swap_out_circular_buffer(__v); 1560227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1561227825Stheraven } 1562227825Stheraven catch (...) 1563227825Stheraven { 1564227825Stheraven } 1565227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1566227825Stheraven } 1567227825Stheraven} 1568227825Stheraven 1569227825Stheraventemplate <class _Tp, class _Allocator> 1570232950Stheraventemplate <class _Up> 1571227825Stheravenvoid 1572232950Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1573232950Stheravenvector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) 1574232950Stheraven#else 1575232950Stheravenvector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x) 1576232950Stheraven#endif 1577232950Stheraven{ 1578232950Stheraven allocator_type& __a = this->__alloc(); 1579232950Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1580232950Stheraven // __v.push_back(_VSTD::forward<_Up>(__x)); 1581246487Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x)); 1582246487Stheraven __v.__end_++; 1583232950Stheraven __swap_out_circular_buffer(__v); 1584232950Stheraven} 1585232950Stheraven 1586232950Stheraventemplate <class _Tp, class _Allocator> 1587262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1588232950Stheravenvoid 1589227825Stheravenvector<_Tp, _Allocator>::push_back(const_reference __x) 1590227825Stheraven{ 1591232950Stheraven if (this->__end_ != this->__end_cap()) 1592227825Stheraven { 1593278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1594227825Stheraven __alloc_traits::construct(this->__alloc(), 1595227825Stheraven _VSTD::__to_raw_pointer(this->__end_), __x); 1596278724Sdim __annotator.__done(); 1597227825Stheraven ++this->__end_; 1598227825Stheraven } 1599227825Stheraven else 1600232950Stheraven __push_back_slow_path(__x); 1601227825Stheraven} 1602227825Stheraven 1603227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1604227825Stheraven 1605227825Stheraventemplate <class _Tp, class _Allocator> 1606262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1607227825Stheravenvoid 1608227825Stheravenvector<_Tp, _Allocator>::push_back(value_type&& __x) 1609227825Stheraven{ 1610227825Stheraven if (this->__end_ < this->__end_cap()) 1611227825Stheraven { 1612278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1613227825Stheraven __alloc_traits::construct(this->__alloc(), 1614227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1615227825Stheraven _VSTD::move(__x)); 1616278724Sdim __annotator.__done(); 1617227825Stheraven ++this->__end_; 1618227825Stheraven } 1619227825Stheraven else 1620232950Stheraven __push_back_slow_path(_VSTD::move(__x)); 1621227825Stheraven} 1622227825Stheraven 1623227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1624227825Stheraven 1625227825Stheraventemplate <class _Tp, class _Allocator> 1626227825Stheraventemplate <class... _Args> 1627227825Stheravenvoid 1628232950Stheravenvector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) 1629232950Stheraven{ 1630232950Stheraven allocator_type& __a = this->__alloc(); 1631232950Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1632232950Stheraven// __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1633246487Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...); 1634246487Stheraven __v.__end_++; 1635232950Stheraven __swap_out_circular_buffer(__v); 1636232950Stheraven} 1637232950Stheraven 1638232950Stheraventemplate <class _Tp, class _Allocator> 1639232950Stheraventemplate <class... _Args> 1640262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1641232950Stheravenvoid 1642227825Stheravenvector<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1643227825Stheraven{ 1644227825Stheraven if (this->__end_ < this->__end_cap()) 1645227825Stheraven { 1646278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1647227825Stheraven __alloc_traits::construct(this->__alloc(), 1648227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1649227825Stheraven _VSTD::forward<_Args>(__args)...); 1650278724Sdim __annotator.__done(); 1651227825Stheraven ++this->__end_; 1652227825Stheraven } 1653227825Stheraven else 1654232950Stheraven __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); 1655227825Stheraven} 1656227825Stheraven 1657227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1658227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1659227825Stheraven 1660227825Stheraventemplate <class _Tp, class _Allocator> 1661262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1662227825Stheravenvoid 1663227825Stheravenvector<_Tp, _Allocator>::pop_back() 1664227825Stheraven{ 1665227825Stheraven _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector"); 1666227825Stheraven this->__destruct_at_end(this->__end_ - 1); 1667227825Stheraven} 1668227825Stheraven 1669227825Stheraventemplate <class _Tp, class _Allocator> 1670262801Sdiminline _LIBCPP_INLINE_VISIBILITY 1671227825Stheraventypename vector<_Tp, _Allocator>::iterator 1672227825Stheravenvector<_Tp, _Allocator>::erase(const_iterator __position) 1673227825Stheraven{ 1674227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1675227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1676227825Stheraven "vector::erase(iterator) called with an iterator not" 1677227825Stheraven " referring to this vector"); 1678227825Stheraven#endif 1679249998Sdim _LIBCPP_ASSERT(__position != end(), 1680249998Sdim "vector::erase(iterator) called with a non-dereferenceable iterator"); 1681253159Stheraven difference_type __ps = __position - cbegin(); 1682253159Stheraven pointer __p = this->__begin_ + __ps; 1683227825Stheraven iterator __r = __make_iter(__p); 1684227825Stheraven this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); 1685227825Stheraven return __r; 1686227825Stheraven} 1687227825Stheraven 1688227825Stheraventemplate <class _Tp, class _Allocator> 1689227825Stheraventypename vector<_Tp, _Allocator>::iterator 1690227825Stheravenvector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) 1691227825Stheraven{ 1692227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1693227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 1694227825Stheraven "vector::erase(iterator, iterator) called with an iterator not" 1695227825Stheraven " referring to this vector"); 1696227825Stheraven#endif 1697227825Stheraven _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range"); 1698227825Stheraven pointer __p = this->__begin_ + (__first - begin()); 1699227825Stheraven iterator __r = __make_iter(__p); 1700249998Sdim if (__first != __last) 1701249998Sdim this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p)); 1702227825Stheraven return __r; 1703227825Stheraven} 1704227825Stheraven 1705227825Stheraventemplate <class _Tp, class _Allocator> 1706227825Stheravenvoid 1707227825Stheravenvector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) 1708227825Stheraven{ 1709227825Stheraven pointer __old_last = this->__end_; 1710227825Stheraven difference_type __n = __old_last - __to; 1711227825Stheraven for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_) 1712227825Stheraven __alloc_traits::construct(this->__alloc(), 1713227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1714227825Stheraven _VSTD::move(*__i)); 1715227825Stheraven _VSTD::move_backward(__from_s, __from_s + __n, __old_last); 1716227825Stheraven} 1717227825Stheraven 1718227825Stheraventemplate <class _Tp, class _Allocator> 1719227825Stheraventypename vector<_Tp, _Allocator>::iterator 1720227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) 1721227825Stheraven{ 1722227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1723227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1724227825Stheraven "vector::insert(iterator, x) called with an iterator not" 1725227825Stheraven " referring to this vector"); 1726227825Stheraven#endif 1727227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1728227825Stheraven if (this->__end_ < this->__end_cap()) 1729227825Stheraven { 1730278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1731227825Stheraven if (__p == this->__end_) 1732227825Stheraven { 1733227825Stheraven __alloc_traits::construct(this->__alloc(), 1734227825Stheraven _VSTD::__to_raw_pointer(this->__end_), __x); 1735227825Stheraven ++this->__end_; 1736227825Stheraven } 1737227825Stheraven else 1738227825Stheraven { 1739227825Stheraven __move_range(__p, this->__end_, __p + 1); 1740227825Stheraven const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1741227825Stheraven if (__p <= __xr && __xr < this->__end_) 1742227825Stheraven ++__xr; 1743227825Stheraven *__p = *__xr; 1744227825Stheraven } 1745278724Sdim __annotator.__done(); 1746227825Stheraven } 1747227825Stheraven else 1748227825Stheraven { 1749227825Stheraven allocator_type& __a = this->__alloc(); 1750227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1751227825Stheraven __v.push_back(__x); 1752227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1753227825Stheraven } 1754227825Stheraven return __make_iter(__p); 1755227825Stheraven} 1756227825Stheraven 1757227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1758227825Stheraven 1759227825Stheraventemplate <class _Tp, class _Allocator> 1760227825Stheraventypename vector<_Tp, _Allocator>::iterator 1761227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) 1762227825Stheraven{ 1763227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1764227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1765227825Stheraven "vector::insert(iterator, x) called with an iterator not" 1766227825Stheraven " referring to this vector"); 1767227825Stheraven#endif 1768227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1769227825Stheraven if (this->__end_ < this->__end_cap()) 1770227825Stheraven { 1771278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1772227825Stheraven if (__p == this->__end_) 1773227825Stheraven { 1774227825Stheraven __alloc_traits::construct(this->__alloc(), 1775227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1776227825Stheraven _VSTD::move(__x)); 1777227825Stheraven ++this->__end_; 1778227825Stheraven } 1779227825Stheraven else 1780227825Stheraven { 1781227825Stheraven __move_range(__p, this->__end_, __p + 1); 1782227825Stheraven *__p = _VSTD::move(__x); 1783227825Stheraven } 1784278724Sdim __annotator.__done(); 1785227825Stheraven } 1786227825Stheraven else 1787227825Stheraven { 1788227825Stheraven allocator_type& __a = this->__alloc(); 1789227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1790227825Stheraven __v.push_back(_VSTD::move(__x)); 1791227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1792227825Stheraven } 1793227825Stheraven return __make_iter(__p); 1794227825Stheraven} 1795227825Stheraven 1796227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1797227825Stheraven 1798227825Stheraventemplate <class _Tp, class _Allocator> 1799227825Stheraventemplate <class... _Args> 1800227825Stheraventypename vector<_Tp, _Allocator>::iterator 1801227825Stheravenvector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) 1802227825Stheraven{ 1803227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1804227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1805227825Stheraven "vector::emplace(iterator, x) called with an iterator not" 1806227825Stheraven " referring to this vector"); 1807227825Stheraven#endif 1808227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1809227825Stheraven if (this->__end_ < this->__end_cap()) 1810227825Stheraven { 1811278724Sdim __RAII_IncreaseAnnotator __annotator(*this); 1812227825Stheraven if (__p == this->__end_) 1813227825Stheraven { 1814227825Stheraven __alloc_traits::construct(this->__alloc(), 1815227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1816227825Stheraven _VSTD::forward<_Args>(__args)...); 1817227825Stheraven ++this->__end_; 1818227825Stheraven } 1819227825Stheraven else 1820227825Stheraven { 1821241903Sdim value_type __tmp(_VSTD::forward<_Args>(__args)...); 1822227825Stheraven __move_range(__p, this->__end_, __p + 1); 1823241903Sdim *__p = _VSTD::move(__tmp); 1824227825Stheraven } 1825278724Sdim __annotator.__done(); 1826227825Stheraven } 1827227825Stheraven else 1828227825Stheraven { 1829227825Stheraven allocator_type& __a = this->__alloc(); 1830227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1831227825Stheraven __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1832227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1833227825Stheraven } 1834227825Stheraven return __make_iter(__p); 1835227825Stheraven} 1836227825Stheraven 1837227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1838227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1839227825Stheraven 1840227825Stheraventemplate <class _Tp, class _Allocator> 1841227825Stheraventypename vector<_Tp, _Allocator>::iterator 1842227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) 1843227825Stheraven{ 1844227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1845227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1846227825Stheraven "vector::insert(iterator, n, x) called with an iterator not" 1847227825Stheraven " referring to this vector"); 1848227825Stheraven#endif 1849227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1850227825Stheraven if (__n > 0) 1851227825Stheraven { 1852227825Stheraven if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_)) 1853227825Stheraven { 1854227825Stheraven size_type __old_n = __n; 1855227825Stheraven pointer __old_last = this->__end_; 1856227825Stheraven if (__n > static_cast<size_type>(this->__end_ - __p)) 1857227825Stheraven { 1858227825Stheraven size_type __cx = __n - (this->__end_ - __p); 1859227825Stheraven __construct_at_end(__cx, __x); 1860227825Stheraven __n -= __cx; 1861227825Stheraven } 1862227825Stheraven if (__n > 0) 1863227825Stheraven { 1864278724Sdim __RAII_IncreaseAnnotator __annotator(*this, __n); 1865227825Stheraven __move_range(__p, __old_last, __p + __old_n); 1866278724Sdim __annotator.__done(); 1867227825Stheraven const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1868227825Stheraven if (__p <= __xr && __xr < this->__end_) 1869227825Stheraven __xr += __old_n; 1870227825Stheraven _VSTD::fill_n(__p, __n, *__xr); 1871227825Stheraven } 1872227825Stheraven } 1873227825Stheraven else 1874227825Stheraven { 1875227825Stheraven allocator_type& __a = this->__alloc(); 1876227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1877227825Stheraven __v.__construct_at_end(__n, __x); 1878227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1879227825Stheraven } 1880227825Stheraven } 1881227825Stheraven return __make_iter(__p); 1882227825Stheraven} 1883227825Stheraven 1884227825Stheraventemplate <class _Tp, class _Allocator> 1885227825Stheraventemplate <class _InputIterator> 1886227825Stheraventypename enable_if 1887227825Stheraven< 1888227825Stheraven __is_input_iterator <_InputIterator>::value && 1889249998Sdim !__is_forward_iterator<_InputIterator>::value && 1890249998Sdim is_constructible< 1891249998Sdim _Tp, 1892249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 1893227825Stheraven typename vector<_Tp, _Allocator>::iterator 1894227825Stheraven>::type 1895227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 1896227825Stheraven{ 1897227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1898227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1899227825Stheraven "vector::insert(iterator, range) called with an iterator not" 1900227825Stheraven " referring to this vector"); 1901227825Stheraven#endif 1902227825Stheraven difference_type __off = __position - begin(); 1903227825Stheraven pointer __p = this->__begin_ + __off; 1904227825Stheraven allocator_type& __a = this->__alloc(); 1905227825Stheraven pointer __old_last = this->__end_; 1906227825Stheraven for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) 1907227825Stheraven { 1908227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), 1909227825Stheraven *__first); 1910227825Stheraven ++this->__end_; 1911227825Stheraven } 1912227825Stheraven __split_buffer<value_type, allocator_type&> __v(__a); 1913227825Stheraven if (__first != __last) 1914227825Stheraven { 1915227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1916227825Stheraven try 1917227825Stheraven { 1918227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1919227825Stheraven __v.__construct_at_end(__first, __last); 1920227825Stheraven difference_type __old_size = __old_last - this->__begin_; 1921227825Stheraven difference_type __old_p = __p - this->__begin_; 1922227825Stheraven reserve(__recommend(size() + __v.size())); 1923227825Stheraven __p = this->__begin_ + __old_p; 1924227825Stheraven __old_last = this->__begin_ + __old_size; 1925227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1926227825Stheraven } 1927227825Stheraven catch (...) 1928227825Stheraven { 1929227825Stheraven erase(__make_iter(__old_last), end()); 1930227825Stheraven throw; 1931227825Stheraven } 1932227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1933227825Stheraven } 1934227825Stheraven __p = _VSTD::rotate(__p, __old_last, this->__end_); 1935227825Stheraven insert(__make_iter(__p), make_move_iterator(__v.begin()), 1936227825Stheraven make_move_iterator(__v.end())); 1937227825Stheraven return begin() + __off; 1938227825Stheraven} 1939227825Stheraven 1940227825Stheraventemplate <class _Tp, class _Allocator> 1941227825Stheraventemplate <class _ForwardIterator> 1942227825Stheraventypename enable_if 1943227825Stheraven< 1944249998Sdim __is_forward_iterator<_ForwardIterator>::value && 1945249998Sdim is_constructible< 1946249998Sdim _Tp, 1947249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 1948227825Stheraven typename vector<_Tp, _Allocator>::iterator 1949227825Stheraven>::type 1950227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 1951227825Stheraven{ 1952227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1953227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1954227825Stheraven "vector::insert(iterator, range) called with an iterator not" 1955227825Stheraven " referring to this vector"); 1956227825Stheraven#endif 1957227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1958227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 1959227825Stheraven if (__n > 0) 1960227825Stheraven { 1961227825Stheraven if (__n <= this->__end_cap() - this->__end_) 1962227825Stheraven { 1963227825Stheraven size_type __old_n = __n; 1964227825Stheraven pointer __old_last = this->__end_; 1965227825Stheraven _ForwardIterator __m = __last; 1966227825Stheraven difference_type __dx = this->__end_ - __p; 1967227825Stheraven if (__n > __dx) 1968227825Stheraven { 1969227825Stheraven __m = __first; 1970227825Stheraven _VSTD::advance(__m, this->__end_ - __p); 1971227825Stheraven __construct_at_end(__m, __last); 1972227825Stheraven __n = __dx; 1973227825Stheraven } 1974227825Stheraven if (__n > 0) 1975227825Stheraven { 1976278724Sdim __RAII_IncreaseAnnotator __annotator(*this, __n); 1977227825Stheraven __move_range(__p, __old_last, __p + __old_n); 1978278724Sdim __annotator.__done(); 1979227825Stheraven _VSTD::copy(__first, __m, __p); 1980227825Stheraven } 1981227825Stheraven } 1982227825Stheraven else 1983227825Stheraven { 1984227825Stheraven allocator_type& __a = this->__alloc(); 1985227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1986227825Stheraven __v.__construct_at_end(__first, __last); 1987227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1988227825Stheraven } 1989227825Stheraven } 1990227825Stheraven return __make_iter(__p); 1991227825Stheraven} 1992227825Stheraven 1993227825Stheraventemplate <class _Tp, class _Allocator> 1994227825Stheravenvoid 1995227825Stheravenvector<_Tp, _Allocator>::resize(size_type __sz) 1996227825Stheraven{ 1997227825Stheraven size_type __cs = size(); 1998227825Stheraven if (__cs < __sz) 1999227825Stheraven this->__append(__sz - __cs); 2000227825Stheraven else if (__cs > __sz) 2001227825Stheraven this->__destruct_at_end(this->__begin_ + __sz); 2002227825Stheraven} 2003227825Stheraven 2004227825Stheraventemplate <class _Tp, class _Allocator> 2005227825Stheravenvoid 2006227825Stheravenvector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) 2007227825Stheraven{ 2008227825Stheraven size_type __cs = size(); 2009227825Stheraven if (__cs < __sz) 2010227825Stheraven this->__append(__sz - __cs, __x); 2011227825Stheraven else if (__cs > __sz) 2012227825Stheraven this->__destruct_at_end(this->__begin_ + __sz); 2013227825Stheraven} 2014227825Stheraven 2015227825Stheraventemplate <class _Tp, class _Allocator> 2016227825Stheravenvoid 2017227825Stheravenvector<_Tp, _Allocator>::swap(vector& __x) 2018227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2019227825Stheraven __is_nothrow_swappable<allocator_type>::value) 2020227825Stheraven{ 2021227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 2022227825Stheraven this->__alloc() == __x.__alloc(), 2023227825Stheraven "vector::swap: Either propagate_on_container_swap must be true" 2024227825Stheraven " or the allocators must compare equal"); 2025227825Stheraven _VSTD::swap(this->__begin_, __x.__begin_); 2026227825Stheraven _VSTD::swap(this->__end_, __x.__end_); 2027227825Stheraven _VSTD::swap(this->__end_cap(), __x.__end_cap()); 2028227825Stheraven __base::__swap_alloc(this->__alloc(), __x.__alloc()); 2029227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2030227825Stheraven __get_db()->swap(this, &__x); 2031227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2032227825Stheraven} 2033227825Stheraven 2034227825Stheraventemplate <class _Tp, class _Allocator> 2035227825Stheravenbool 2036227825Stheravenvector<_Tp, _Allocator>::__invariants() const 2037227825Stheraven{ 2038253159Stheraven if (this->__begin_ == nullptr) 2039227825Stheraven { 2040253159Stheraven if (this->__end_ != nullptr || this->__end_cap() != nullptr) 2041227825Stheraven return false; 2042227825Stheraven } 2043227825Stheraven else 2044227825Stheraven { 2045227825Stheraven if (this->__begin_ > this->__end_) 2046227825Stheraven return false; 2047227825Stheraven if (this->__begin_ == this->__end_cap()) 2048227825Stheraven return false; 2049227825Stheraven if (this->__end_ > this->__end_cap()) 2050227825Stheraven return false; 2051227825Stheraven } 2052227825Stheraven return true; 2053227825Stheraven} 2054227825Stheraven 2055227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2056227825Stheraven 2057227825Stheraventemplate <class _Tp, class _Allocator> 2058227825Stheravenbool 2059227825Stheravenvector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const 2060227825Stheraven{ 2061227825Stheraven return this->__begin_ <= __i->base() && __i->base() < this->__end_; 2062227825Stheraven} 2063227825Stheraven 2064227825Stheraventemplate <class _Tp, class _Allocator> 2065227825Stheravenbool 2066227825Stheravenvector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const 2067227825Stheraven{ 2068227825Stheraven return this->__begin_ < __i->base() && __i->base() <= this->__end_; 2069227825Stheraven} 2070227825Stheraven 2071227825Stheraventemplate <class _Tp, class _Allocator> 2072227825Stheravenbool 2073227825Stheravenvector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const 2074227825Stheraven{ 2075227825Stheraven const_pointer __p = __i->base() + __n; 2076227825Stheraven return this->__begin_ <= __p && __p <= this->__end_; 2077227825Stheraven} 2078227825Stheraven 2079227825Stheraventemplate <class _Tp, class _Allocator> 2080227825Stheravenbool 2081227825Stheravenvector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 2082227825Stheraven{ 2083227825Stheraven const_pointer __p = __i->base() + __n; 2084227825Stheraven return this->__begin_ <= __p && __p < this->__end_; 2085227825Stheraven} 2086227825Stheraven 2087227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2088227825Stheraven 2089227825Stheraventemplate <class _Tp, class _Allocator> 2090262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2091227825Stheravenvoid 2092227825Stheravenvector<_Tp, _Allocator>::__invalidate_all_iterators() 2093227825Stheraven{ 2094227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2095227825Stheraven __get_db()->__invalidate_all(this); 2096227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2097227825Stheraven} 2098227825Stheraven 2099227825Stheraven// vector<bool> 2100227825Stheraven 2101227825Stheraventemplate <class _Allocator> class vector<bool, _Allocator>; 2102227825Stheraven 2103227825Stheraventemplate <class _Allocator> struct hash<vector<bool, _Allocator> >; 2104227825Stheraven 2105227825Stheraventemplate <class _Allocator> 2106227825Stheravenstruct __has_storage_type<vector<bool, _Allocator> > 2107227825Stheraven{ 2108227825Stheraven static const bool value = true; 2109227825Stheraven}; 2110227825Stheraven 2111227825Stheraventemplate <class _Allocator> 2112262801Sdimclass _LIBCPP_TYPE_VIS_ONLY vector<bool, _Allocator> 2113227825Stheraven : private __vector_base_common<true> 2114227825Stheraven{ 2115227825Stheravenpublic: 2116227825Stheraven typedef vector __self; 2117227825Stheraven typedef bool value_type; 2118227825Stheraven typedef _Allocator allocator_type; 2119227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 2120227825Stheraven typedef typename __alloc_traits::size_type size_type; 2121227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 2122241903Sdim typedef size_type __storage_type; 2123227825Stheraven typedef __bit_iterator<vector, false> pointer; 2124227825Stheraven typedef __bit_iterator<vector, true> const_pointer; 2125227825Stheraven typedef pointer iterator; 2126227825Stheraven typedef const_pointer const_iterator; 2127227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 2128227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 2129227825Stheraven 2130227825Stheravenprivate: 2131227825Stheraven typedef typename __alloc_traits::template 2132227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 2133227825Stheraven rebind_alloc<__storage_type> 2134227825Stheraven#else 2135227825Stheraven rebind_alloc<__storage_type>::other 2136227825Stheraven#endif 2137227825Stheraven __storage_allocator; 2138227825Stheraven typedef allocator_traits<__storage_allocator> __storage_traits; 2139227825Stheraven typedef typename __storage_traits::pointer __storage_pointer; 2140227825Stheraven typedef typename __storage_traits::const_pointer __const_storage_pointer; 2141227825Stheraven 2142227825Stheraven __storage_pointer __begin_; 2143227825Stheraven size_type __size_; 2144227825Stheraven __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 2145227825Stheravenpublic: 2146227825Stheraven typedef __bit_reference<vector> reference; 2147227825Stheraven typedef __bit_const_reference<vector> const_reference; 2148227825Stheravenprivate: 2149227825Stheraven _LIBCPP_INLINE_VISIBILITY 2150227825Stheraven size_type& __cap() _NOEXCEPT 2151227825Stheraven {return __cap_alloc_.first();} 2152227825Stheraven _LIBCPP_INLINE_VISIBILITY 2153227825Stheraven const size_type& __cap() const _NOEXCEPT 2154227825Stheraven {return __cap_alloc_.first();} 2155227825Stheraven _LIBCPP_INLINE_VISIBILITY 2156227825Stheraven __storage_allocator& __alloc() _NOEXCEPT 2157227825Stheraven {return __cap_alloc_.second();} 2158227825Stheraven _LIBCPP_INLINE_VISIBILITY 2159227825Stheraven const __storage_allocator& __alloc() const _NOEXCEPT 2160227825Stheraven {return __cap_alloc_.second();} 2161227825Stheraven 2162227825Stheraven static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 2163227825Stheraven 2164227825Stheraven _LIBCPP_INLINE_VISIBILITY 2165227825Stheraven static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT 2166227825Stheraven {return __n * __bits_per_word;} 2167227825Stheraven _LIBCPP_INLINE_VISIBILITY 2168227825Stheraven static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT 2169227825Stheraven {return (__n - 1) / __bits_per_word + 1;} 2170227825Stheraven 2171227825Stheravenpublic: 2172227825Stheraven _LIBCPP_INLINE_VISIBILITY 2173227825Stheraven vector() 2174227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 2175227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a); 2176227825Stheraven ~vector(); 2177227825Stheraven explicit vector(size_type __n); 2178262801Sdim#if _LIBCPP_STD_VER > 11 2179262801Sdim explicit vector(size_type __n, const allocator_type& __a); 2180262801Sdim#endif 2181227825Stheraven vector(size_type __n, const value_type& __v); 2182227825Stheraven vector(size_type __n, const value_type& __v, const allocator_type& __a); 2183227825Stheraven template <class _InputIterator> 2184227825Stheraven vector(_InputIterator __first, _InputIterator __last, 2185227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2186227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2187227825Stheraven template <class _InputIterator> 2188227825Stheraven vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2189227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2190227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2191227825Stheraven template <class _ForwardIterator> 2192227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, 2193227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2194227825Stheraven template <class _ForwardIterator> 2195227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2196227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2197227825Stheraven 2198227825Stheraven vector(const vector& __v); 2199227825Stheraven vector(const vector& __v, const allocator_type& __a); 2200227825Stheraven vector& operator=(const vector& __v); 2201227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2202227825Stheraven vector(initializer_list<value_type> __il); 2203227825Stheraven vector(initializer_list<value_type> __il, const allocator_type& __a); 2204227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2205227825Stheraven 2206227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2207227825Stheraven _LIBCPP_INLINE_VISIBILITY 2208227825Stheraven vector(vector&& __v) 2209227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 2210227825Stheraven vector(vector&& __v, const allocator_type& __a); 2211227825Stheraven _LIBCPP_INLINE_VISIBILITY 2212227825Stheraven vector& operator=(vector&& __v) 2213227825Stheraven _NOEXCEPT_( 2214227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 2215227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 2216227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2217227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2218227825Stheraven _LIBCPP_INLINE_VISIBILITY 2219227825Stheraven vector& operator=(initializer_list<value_type> __il) 2220227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 2221227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2222227825Stheraven 2223227825Stheraven template <class _InputIterator> 2224227825Stheraven typename enable_if 2225227825Stheraven < 2226227825Stheraven __is_input_iterator<_InputIterator>::value && 2227227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2228227825Stheraven void 2229227825Stheraven >::type 2230227825Stheraven assign(_InputIterator __first, _InputIterator __last); 2231227825Stheraven template <class _ForwardIterator> 2232227825Stheraven typename enable_if 2233227825Stheraven < 2234227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2235227825Stheraven void 2236227825Stheraven >::type 2237227825Stheraven assign(_ForwardIterator __first, _ForwardIterator __last); 2238227825Stheraven 2239227825Stheraven void assign(size_type __n, const value_type& __x); 2240227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2241227825Stheraven _LIBCPP_INLINE_VISIBILITY 2242227825Stheraven void assign(initializer_list<value_type> __il) 2243227825Stheraven {assign(__il.begin(), __il.end());} 2244227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2245227825Stheraven 2246227825Stheraven _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT 2247227825Stheraven {return allocator_type(this->__alloc());} 2248227825Stheraven 2249227825Stheraven size_type max_size() const _NOEXCEPT; 2250227825Stheraven _LIBCPP_INLINE_VISIBILITY 2251227825Stheraven size_type capacity() const _NOEXCEPT 2252227825Stheraven {return __internal_cap_to_external(__cap());} 2253227825Stheraven _LIBCPP_INLINE_VISIBILITY 2254227825Stheraven size_type size() const _NOEXCEPT 2255227825Stheraven {return __size_;} 2256227825Stheraven _LIBCPP_INLINE_VISIBILITY 2257227825Stheraven bool empty() const _NOEXCEPT 2258227825Stheraven {return __size_ == 0;} 2259227825Stheraven void reserve(size_type __n); 2260227825Stheraven void shrink_to_fit() _NOEXCEPT; 2261227825Stheraven 2262227825Stheraven _LIBCPP_INLINE_VISIBILITY 2263227825Stheraven iterator begin() _NOEXCEPT 2264227825Stheraven {return __make_iter(0);} 2265227825Stheraven _LIBCPP_INLINE_VISIBILITY 2266227825Stheraven const_iterator begin() const _NOEXCEPT 2267227825Stheraven {return __make_iter(0);} 2268227825Stheraven _LIBCPP_INLINE_VISIBILITY 2269227825Stheraven iterator end() _NOEXCEPT 2270227825Stheraven {return __make_iter(__size_);} 2271227825Stheraven _LIBCPP_INLINE_VISIBILITY 2272227825Stheraven const_iterator end() const _NOEXCEPT 2273227825Stheraven {return __make_iter(__size_);} 2274227825Stheraven 2275227825Stheraven _LIBCPP_INLINE_VISIBILITY 2276227825Stheraven reverse_iterator rbegin() _NOEXCEPT 2277227825Stheraven {return reverse_iterator(end());} 2278227825Stheraven _LIBCPP_INLINE_VISIBILITY 2279227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 2280227825Stheraven {return const_reverse_iterator(end());} 2281227825Stheraven _LIBCPP_INLINE_VISIBILITY 2282227825Stheraven reverse_iterator rend() _NOEXCEPT 2283227825Stheraven {return reverse_iterator(begin());} 2284227825Stheraven _LIBCPP_INLINE_VISIBILITY 2285227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 2286227825Stheraven {return const_reverse_iterator(begin());} 2287227825Stheraven 2288227825Stheraven _LIBCPP_INLINE_VISIBILITY 2289227825Stheraven const_iterator cbegin() const _NOEXCEPT 2290227825Stheraven {return __make_iter(0);} 2291227825Stheraven _LIBCPP_INLINE_VISIBILITY 2292227825Stheraven const_iterator cend() const _NOEXCEPT 2293227825Stheraven {return __make_iter(__size_);} 2294227825Stheraven _LIBCPP_INLINE_VISIBILITY 2295227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 2296227825Stheraven {return rbegin();} 2297227825Stheraven _LIBCPP_INLINE_VISIBILITY 2298227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 2299227825Stheraven {return rend();} 2300227825Stheraven 2301227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);} 2302227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);} 2303227825Stheraven reference at(size_type __n); 2304227825Stheraven const_reference at(size_type __n) const; 2305227825Stheraven 2306227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);} 2307227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);} 2308227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);} 2309227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);} 2310227825Stheraven 2311227825Stheraven void push_back(const value_type& __x); 2312262801Sdim#if _LIBCPP_STD_VER > 11 2313262801Sdim template <class... _Args> 2314262801Sdim _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args) 2315262801Sdim { push_back ( value_type ( _VSTD::forward<_Args>(__args)... )); } 2316262801Sdim#endif 2317262801Sdim 2318227825Stheraven _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;} 2319227825Stheraven 2320262801Sdim#if _LIBCPP_STD_VER > 11 2321262801Sdim template <class... _Args> 2322262801Sdim _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator position, _Args&&... __args) 2323262801Sdim { return insert ( position, value_type ( _VSTD::forward<_Args>(__args)... )); } 2324262801Sdim#endif 2325262801Sdim 2326227825Stheraven iterator insert(const_iterator __position, const value_type& __x); 2327227825Stheraven iterator insert(const_iterator __position, size_type __n, const value_type& __x); 2328227825Stheraven iterator insert(const_iterator __position, size_type __n, const_reference __x); 2329227825Stheraven template <class _InputIterator> 2330227825Stheraven typename enable_if 2331227825Stheraven < 2332227825Stheraven __is_input_iterator <_InputIterator>::value && 2333227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2334227825Stheraven iterator 2335227825Stheraven >::type 2336227825Stheraven insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 2337227825Stheraven template <class _ForwardIterator> 2338227825Stheraven typename enable_if 2339227825Stheraven < 2340227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2341227825Stheraven iterator 2342227825Stheraven >::type 2343227825Stheraven insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 2344227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2345227825Stheraven _LIBCPP_INLINE_VISIBILITY 2346227825Stheraven iterator insert(const_iterator __position, initializer_list<value_type> __il) 2347227825Stheraven {return insert(__position, __il.begin(), __il.end());} 2348227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2349227825Stheraven 2350227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 2351227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 2352227825Stheraven 2353227825Stheraven _LIBCPP_INLINE_VISIBILITY 2354227825Stheraven void clear() _NOEXCEPT {__size_ = 0;} 2355227825Stheraven 2356227825Stheraven void swap(vector&) 2357227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2358227825Stheraven __is_nothrow_swappable<allocator_type>::value); 2359227825Stheraven 2360227825Stheraven void resize(size_type __sz, value_type __x = false); 2361227825Stheraven void flip() _NOEXCEPT; 2362227825Stheraven 2363227825Stheraven bool __invariants() const; 2364227825Stheraven 2365227825Stheravenprivate: 2366227825Stheraven _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 2367227825Stheraven void allocate(size_type __n); 2368227825Stheraven void deallocate() _NOEXCEPT; 2369227825Stheraven _LIBCPP_INLINE_VISIBILITY 2370262801Sdim static size_type __align_it(size_type __new_size) _NOEXCEPT 2371278724Sdim {return __new_size + (__bits_per_word-1) & ~((size_type)__bits_per_word-1);}; 2372227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 2373227825Stheraven _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x); 2374227825Stheraven template <class _ForwardIterator> 2375227825Stheraven typename enable_if 2376227825Stheraven < 2377227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2378227825Stheraven void 2379227825Stheraven >::type 2380227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 2381227825Stheraven void __append(size_type __n, const_reference __x); 2382227825Stheraven _LIBCPP_INLINE_VISIBILITY 2383227825Stheraven reference __make_ref(size_type __pos) _NOEXCEPT 2384227825Stheraven {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2385227825Stheraven _LIBCPP_INLINE_VISIBILITY 2386227825Stheraven const_reference __make_ref(size_type __pos) const _NOEXCEPT 2387227825Stheraven {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2388227825Stheraven _LIBCPP_INLINE_VISIBILITY 2389227825Stheraven iterator __make_iter(size_type __pos) _NOEXCEPT 2390227825Stheraven {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2391227825Stheraven _LIBCPP_INLINE_VISIBILITY 2392227825Stheraven const_iterator __make_iter(size_type __pos) const _NOEXCEPT 2393227825Stheraven {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2394227825Stheraven _LIBCPP_INLINE_VISIBILITY 2395227825Stheraven iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT 2396253159Stheraven {return begin() + (__p - cbegin());} 2397227825Stheraven 2398227825Stheraven _LIBCPP_INLINE_VISIBILITY 2399227825Stheraven void __copy_assign_alloc(const vector& __v) 2400227825Stheraven {__copy_assign_alloc(__v, integral_constant<bool, 2401227825Stheraven __storage_traits::propagate_on_container_copy_assignment::value>());} 2402227825Stheraven _LIBCPP_INLINE_VISIBILITY 2403227825Stheraven void __copy_assign_alloc(const vector& __c, true_type) 2404227825Stheraven { 2405227825Stheraven if (__alloc() != __c.__alloc()) 2406227825Stheraven deallocate(); 2407227825Stheraven __alloc() = __c.__alloc(); 2408227825Stheraven } 2409227825Stheraven 2410227825Stheraven _LIBCPP_INLINE_VISIBILITY 2411232950Stheraven void __copy_assign_alloc(const vector&, false_type) 2412227825Stheraven {} 2413227825Stheraven 2414227825Stheraven void __move_assign(vector& __c, false_type); 2415227825Stheraven void __move_assign(vector& __c, true_type) 2416227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 2417227825Stheraven _LIBCPP_INLINE_VISIBILITY 2418227825Stheraven void __move_assign_alloc(vector& __c) 2419227825Stheraven _NOEXCEPT_( 2420227825Stheraven !__storage_traits::propagate_on_container_move_assignment::value || 2421227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 2422227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 2423227825Stheraven __storage_traits::propagate_on_container_move_assignment::value>());} 2424227825Stheraven _LIBCPP_INLINE_VISIBILITY 2425227825Stheraven void __move_assign_alloc(vector& __c, true_type) 2426227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2427227825Stheraven { 2428227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 2429227825Stheraven } 2430227825Stheraven 2431227825Stheraven _LIBCPP_INLINE_VISIBILITY 2432232950Stheraven void __move_assign_alloc(vector&, false_type) 2433227825Stheraven _NOEXCEPT 2434227825Stheraven {} 2435227825Stheraven 2436227825Stheraven _LIBCPP_INLINE_VISIBILITY 2437227825Stheraven static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y) 2438227825Stheraven _NOEXCEPT_( 2439227825Stheraven !__storage_traits::propagate_on_container_swap::value || 2440227825Stheraven __is_nothrow_swappable<allocator_type>::value) 2441227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 2442227825Stheraven __storage_traits::propagate_on_container_swap::value>());} 2443227825Stheraven 2444227825Stheraven _LIBCPP_INLINE_VISIBILITY 2445227825Stheraven static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type) 2446227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value) 2447227825Stheraven { 2448227825Stheraven using _VSTD::swap; 2449227825Stheraven swap(__x, __y); 2450227825Stheraven } 2451227825Stheraven _LIBCPP_INLINE_VISIBILITY 2452232950Stheraven static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type) 2453227825Stheraven _NOEXCEPT 2454227825Stheraven {} 2455227825Stheraven 2456227825Stheraven size_t __hash_code() const _NOEXCEPT; 2457227825Stheraven 2458227825Stheraven friend class __bit_reference<vector>; 2459227825Stheraven friend class __bit_const_reference<vector>; 2460227825Stheraven friend class __bit_iterator<vector, false>; 2461227825Stheraven friend class __bit_iterator<vector, true>; 2462241903Sdim friend struct __bit_array<vector>; 2463262801Sdim friend struct _LIBCPP_TYPE_VIS_ONLY hash<vector>; 2464227825Stheraven}; 2465227825Stheraven 2466227825Stheraventemplate <class _Allocator> 2467262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2468227825Stheravenvoid 2469227825Stheravenvector<bool, _Allocator>::__invalidate_all_iterators() 2470227825Stheraven{ 2471227825Stheraven} 2472227825Stheraven 2473227825Stheraven// Allocate space for __n objects 2474227825Stheraven// throws length_error if __n > max_size() 2475227825Stheraven// throws (probably bad_alloc) if memory run out 2476227825Stheraven// Precondition: __begin_ == __end_ == __cap() == 0 2477227825Stheraven// Precondition: __n > 0 2478227825Stheraven// Postcondition: capacity() == __n 2479227825Stheraven// Postcondition: size() == 0 2480227825Stheraventemplate <class _Allocator> 2481227825Stheravenvoid 2482227825Stheravenvector<bool, _Allocator>::allocate(size_type __n) 2483227825Stheraven{ 2484227825Stheraven if (__n > max_size()) 2485227825Stheraven this->__throw_length_error(); 2486227825Stheraven __n = __external_cap_to_internal(__n); 2487227825Stheraven this->__begin_ = __storage_traits::allocate(this->__alloc(), __n); 2488227825Stheraven this->__size_ = 0; 2489227825Stheraven this->__cap() = __n; 2490227825Stheraven} 2491227825Stheraven 2492227825Stheraventemplate <class _Allocator> 2493227825Stheravenvoid 2494227825Stheravenvector<bool, _Allocator>::deallocate() _NOEXCEPT 2495227825Stheraven{ 2496253159Stheraven if (this->__begin_ != nullptr) 2497227825Stheraven { 2498227825Stheraven __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 2499227825Stheraven __invalidate_all_iterators(); 2500253159Stheraven this->__begin_ = nullptr; 2501227825Stheraven this->__size_ = this->__cap() = 0; 2502227825Stheraven } 2503227825Stheraven} 2504227825Stheraven 2505227825Stheraventemplate <class _Allocator> 2506227825Stheraventypename vector<bool, _Allocator>::size_type 2507227825Stheravenvector<bool, _Allocator>::max_size() const _NOEXCEPT 2508227825Stheraven{ 2509227825Stheraven size_type __amax = __storage_traits::max_size(__alloc()); 2510227825Stheraven size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 2511227825Stheraven if (__nmax / __bits_per_word <= __amax) 2512227825Stheraven return __nmax; 2513227825Stheraven return __internal_cap_to_external(__amax); 2514227825Stheraven} 2515227825Stheraven 2516227825Stheraven// Precondition: __new_size > capacity() 2517227825Stheraventemplate <class _Allocator> 2518262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2519227825Stheraventypename vector<bool, _Allocator>::size_type 2520227825Stheravenvector<bool, _Allocator>::__recommend(size_type __new_size) const 2521227825Stheraven{ 2522227825Stheraven const size_type __ms = max_size(); 2523227825Stheraven if (__new_size > __ms) 2524227825Stheraven this->__throw_length_error(); 2525227825Stheraven const size_type __cap = capacity(); 2526227825Stheraven if (__cap >= __ms / 2) 2527227825Stheraven return __ms; 2528262801Sdim return _VSTD::max(2*__cap, __align_it(__new_size)); 2529227825Stheraven} 2530227825Stheraven 2531227825Stheraven// Default constructs __n objects starting at __end_ 2532227825Stheraven// Precondition: __n > 0 2533227825Stheraven// Precondition: size() + __n <= capacity() 2534227825Stheraven// Postcondition: size() == size() + __n 2535227825Stheraventemplate <class _Allocator> 2536262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2537227825Stheravenvoid 2538227825Stheravenvector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) 2539227825Stheraven{ 2540227825Stheraven size_type __old_size = this->__size_; 2541227825Stheraven this->__size_ += __n; 2542227825Stheraven _VSTD::fill_n(__make_iter(__old_size), __n, __x); 2543227825Stheraven} 2544227825Stheraven 2545227825Stheraventemplate <class _Allocator> 2546227825Stheraventemplate <class _ForwardIterator> 2547227825Stheraventypename enable_if 2548227825Stheraven< 2549227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2550227825Stheraven void 2551227825Stheraven>::type 2552227825Stheravenvector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 2553227825Stheraven{ 2554227825Stheraven size_type __old_size = this->__size_; 2555227825Stheraven this->__size_ += _VSTD::distance(__first, __last); 2556227825Stheraven _VSTD::copy(__first, __last, __make_iter(__old_size)); 2557227825Stheraven} 2558227825Stheraven 2559227825Stheraventemplate <class _Allocator> 2560262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2561227825Stheravenvector<bool, _Allocator>::vector() 2562227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 2563253159Stheraven : __begin_(nullptr), 2564227825Stheraven __size_(0), 2565227825Stheraven __cap_alloc_(0) 2566227825Stheraven{ 2567227825Stheraven} 2568227825Stheraven 2569227825Stheraventemplate <class _Allocator> 2570262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2571227825Stheravenvector<bool, _Allocator>::vector(const allocator_type& __a) 2572253159Stheraven : __begin_(nullptr), 2573227825Stheraven __size_(0), 2574227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2575227825Stheraven{ 2576227825Stheraven} 2577227825Stheraven 2578227825Stheraventemplate <class _Allocator> 2579227825Stheravenvector<bool, _Allocator>::vector(size_type __n) 2580253159Stheraven : __begin_(nullptr), 2581227825Stheraven __size_(0), 2582227825Stheraven __cap_alloc_(0) 2583227825Stheraven{ 2584227825Stheraven if (__n > 0) 2585227825Stheraven { 2586227825Stheraven allocate(__n); 2587227825Stheraven __construct_at_end(__n, false); 2588227825Stheraven } 2589227825Stheraven} 2590227825Stheraven 2591262801Sdim#if _LIBCPP_STD_VER > 11 2592227825Stheraventemplate <class _Allocator> 2593262801Sdimvector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a) 2594262801Sdim : __begin_(nullptr), 2595262801Sdim __size_(0), 2596262801Sdim __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2597262801Sdim{ 2598262801Sdim if (__n > 0) 2599262801Sdim { 2600262801Sdim allocate(__n); 2601262801Sdim __construct_at_end(__n, false); 2602262801Sdim } 2603262801Sdim} 2604262801Sdim#endif 2605262801Sdim 2606262801Sdimtemplate <class _Allocator> 2607227825Stheravenvector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 2608253159Stheraven : __begin_(nullptr), 2609227825Stheraven __size_(0), 2610227825Stheraven __cap_alloc_(0) 2611227825Stheraven{ 2612227825Stheraven if (__n > 0) 2613227825Stheraven { 2614227825Stheraven allocate(__n); 2615227825Stheraven __construct_at_end(__n, __x); 2616227825Stheraven } 2617227825Stheraven} 2618227825Stheraven 2619227825Stheraventemplate <class _Allocator> 2620227825Stheravenvector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 2621253159Stheraven : __begin_(nullptr), 2622227825Stheraven __size_(0), 2623227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2624227825Stheraven{ 2625227825Stheraven if (__n > 0) 2626227825Stheraven { 2627227825Stheraven allocate(__n); 2628227825Stheraven __construct_at_end(__n, __x); 2629227825Stheraven } 2630227825Stheraven} 2631227825Stheraven 2632227825Stheraventemplate <class _Allocator> 2633227825Stheraventemplate <class _InputIterator> 2634227825Stheravenvector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 2635227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2636227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 2637253159Stheraven : __begin_(nullptr), 2638227825Stheraven __size_(0), 2639227825Stheraven __cap_alloc_(0) 2640227825Stheraven{ 2641227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2642227825Stheraven try 2643227825Stheraven { 2644227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2645227825Stheraven for (; __first != __last; ++__first) 2646227825Stheraven push_back(*__first); 2647227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2648227825Stheraven } 2649227825Stheraven catch (...) 2650227825Stheraven { 2651253159Stheraven if (__begin_ != nullptr) 2652227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2653227825Stheraven __invalidate_all_iterators(); 2654227825Stheraven throw; 2655227825Stheraven } 2656227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2657227825Stheraven} 2658227825Stheraven 2659227825Stheraventemplate <class _Allocator> 2660227825Stheraventemplate <class _InputIterator> 2661227825Stheravenvector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2662227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2663227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 2664253159Stheraven : __begin_(nullptr), 2665227825Stheraven __size_(0), 2666227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2667227825Stheraven{ 2668227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2669227825Stheraven try 2670227825Stheraven { 2671227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2672227825Stheraven for (; __first != __last; ++__first) 2673227825Stheraven push_back(*__first); 2674227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2675227825Stheraven } 2676227825Stheraven catch (...) 2677227825Stheraven { 2678253159Stheraven if (__begin_ != nullptr) 2679227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2680227825Stheraven __invalidate_all_iterators(); 2681227825Stheraven throw; 2682227825Stheraven } 2683227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2684227825Stheraven} 2685227825Stheraven 2686227825Stheraventemplate <class _Allocator> 2687227825Stheraventemplate <class _ForwardIterator> 2688227825Stheravenvector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 2689227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2690253159Stheraven : __begin_(nullptr), 2691227825Stheraven __size_(0), 2692227825Stheraven __cap_alloc_(0) 2693227825Stheraven{ 2694227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2695227825Stheraven if (__n > 0) 2696227825Stheraven { 2697227825Stheraven allocate(__n); 2698227825Stheraven __construct_at_end(__first, __last); 2699227825Stheraven } 2700227825Stheraven} 2701227825Stheraven 2702227825Stheraventemplate <class _Allocator> 2703227825Stheraventemplate <class _ForwardIterator> 2704227825Stheravenvector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2705227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2706253159Stheraven : __begin_(nullptr), 2707227825Stheraven __size_(0), 2708227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2709227825Stheraven{ 2710227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2711227825Stheraven if (__n > 0) 2712227825Stheraven { 2713227825Stheraven allocate(__n); 2714227825Stheraven __construct_at_end(__first, __last); 2715227825Stheraven } 2716227825Stheraven} 2717227825Stheraven 2718227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2719227825Stheraven 2720227825Stheraventemplate <class _Allocator> 2721227825Stheravenvector<bool, _Allocator>::vector(initializer_list<value_type> __il) 2722253159Stheraven : __begin_(nullptr), 2723227825Stheraven __size_(0), 2724227825Stheraven __cap_alloc_(0) 2725227825Stheraven{ 2726227825Stheraven size_type __n = static_cast<size_type>(__il.size()); 2727227825Stheraven if (__n > 0) 2728227825Stheraven { 2729227825Stheraven allocate(__n); 2730227825Stheraven __construct_at_end(__il.begin(), __il.end()); 2731227825Stheraven } 2732227825Stheraven} 2733227825Stheraven 2734227825Stheraventemplate <class _Allocator> 2735227825Stheravenvector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 2736253159Stheraven : __begin_(nullptr), 2737227825Stheraven __size_(0), 2738227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2739227825Stheraven{ 2740227825Stheraven size_type __n = static_cast<size_type>(__il.size()); 2741227825Stheraven if (__n > 0) 2742227825Stheraven { 2743227825Stheraven allocate(__n); 2744227825Stheraven __construct_at_end(__il.begin(), __il.end()); 2745227825Stheraven } 2746227825Stheraven} 2747227825Stheraven 2748227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2749227825Stheraven 2750227825Stheraventemplate <class _Allocator> 2751227825Stheravenvector<bool, _Allocator>::~vector() 2752227825Stheraven{ 2753253159Stheraven if (__begin_ != nullptr) 2754227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2755227825Stheraven __invalidate_all_iterators(); 2756227825Stheraven} 2757227825Stheraven 2758227825Stheraventemplate <class _Allocator> 2759227825Stheravenvector<bool, _Allocator>::vector(const vector& __v) 2760253159Stheraven : __begin_(nullptr), 2761227825Stheraven __size_(0), 2762227825Stheraven __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) 2763227825Stheraven{ 2764227825Stheraven if (__v.size() > 0) 2765227825Stheraven { 2766227825Stheraven allocate(__v.size()); 2767227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2768227825Stheraven } 2769227825Stheraven} 2770227825Stheraven 2771227825Stheraventemplate <class _Allocator> 2772227825Stheravenvector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2773253159Stheraven : __begin_(nullptr), 2774227825Stheraven __size_(0), 2775227825Stheraven __cap_alloc_(0, __a) 2776227825Stheraven{ 2777227825Stheraven if (__v.size() > 0) 2778227825Stheraven { 2779227825Stheraven allocate(__v.size()); 2780227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2781227825Stheraven } 2782227825Stheraven} 2783227825Stheraven 2784227825Stheraventemplate <class _Allocator> 2785227825Stheravenvector<bool, _Allocator>& 2786227825Stheravenvector<bool, _Allocator>::operator=(const vector& __v) 2787227825Stheraven{ 2788227825Stheraven if (this != &__v) 2789227825Stheraven { 2790227825Stheraven __copy_assign_alloc(__v); 2791227825Stheraven if (__v.__size_) 2792227825Stheraven { 2793227825Stheraven if (__v.__size_ > capacity()) 2794227825Stheraven { 2795227825Stheraven deallocate(); 2796227825Stheraven allocate(__v.__size_); 2797227825Stheraven } 2798227825Stheraven _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2799227825Stheraven } 2800227825Stheraven __size_ = __v.__size_; 2801227825Stheraven } 2802227825Stheraven return *this; 2803227825Stheraven} 2804227825Stheraven 2805227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2806227825Stheraven 2807227825Stheraventemplate <class _Allocator> 2808262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2809227825Stheravenvector<bool, _Allocator>::vector(vector&& __v) 2810227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 2811227825Stheraven : __begin_(__v.__begin_), 2812227825Stheraven __size_(__v.__size_), 2813227825Stheraven __cap_alloc_(__v.__cap_alloc_) 2814227825Stheraven{ 2815253159Stheraven __v.__begin_ = nullptr; 2816227825Stheraven __v.__size_ = 0; 2817227825Stheraven __v.__cap() = 0; 2818227825Stheraven} 2819227825Stheraven 2820227825Stheraventemplate <class _Allocator> 2821227825Stheravenvector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a) 2822253159Stheraven : __begin_(nullptr), 2823227825Stheraven __size_(0), 2824227825Stheraven __cap_alloc_(0, __a) 2825227825Stheraven{ 2826227825Stheraven if (__a == allocator_type(__v.__alloc())) 2827227825Stheraven { 2828227825Stheraven this->__begin_ = __v.__begin_; 2829227825Stheraven this->__size_ = __v.__size_; 2830227825Stheraven this->__cap() = __v.__cap(); 2831227825Stheraven __v.__begin_ = nullptr; 2832227825Stheraven __v.__cap() = __v.__size_ = 0; 2833227825Stheraven } 2834227825Stheraven else if (__v.size() > 0) 2835227825Stheraven { 2836227825Stheraven allocate(__v.size()); 2837227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2838227825Stheraven } 2839227825Stheraven} 2840227825Stheraven 2841227825Stheraventemplate <class _Allocator> 2842262801Sdiminline _LIBCPP_INLINE_VISIBILITY 2843227825Stheravenvector<bool, _Allocator>& 2844227825Stheravenvector<bool, _Allocator>::operator=(vector&& __v) 2845227825Stheraven _NOEXCEPT_( 2846227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 2847227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 2848227825Stheraven{ 2849227825Stheraven __move_assign(__v, integral_constant<bool, 2850227825Stheraven __storage_traits::propagate_on_container_move_assignment::value>()); 2851241903Sdim return *this; 2852227825Stheraven} 2853227825Stheraven 2854227825Stheraventemplate <class _Allocator> 2855227825Stheravenvoid 2856227825Stheravenvector<bool, _Allocator>::__move_assign(vector& __c, false_type) 2857227825Stheraven{ 2858227825Stheraven if (__alloc() != __c.__alloc()) 2859227825Stheraven assign(__c.begin(), __c.end()); 2860227825Stheraven else 2861227825Stheraven __move_assign(__c, true_type()); 2862227825Stheraven} 2863227825Stheraven 2864227825Stheraventemplate <class _Allocator> 2865227825Stheravenvoid 2866227825Stheravenvector<bool, _Allocator>::__move_assign(vector& __c, true_type) 2867227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2868227825Stheraven{ 2869227825Stheraven deallocate(); 2870278724Sdim __move_assign_alloc(__c); 2871227825Stheraven this->__begin_ = __c.__begin_; 2872227825Stheraven this->__size_ = __c.__size_; 2873227825Stheraven this->__cap() = __c.__cap(); 2874227825Stheraven __c.__begin_ = nullptr; 2875227825Stheraven __c.__cap() = __c.__size_ = 0; 2876227825Stheraven} 2877227825Stheraven 2878227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2879227825Stheraven 2880227825Stheraventemplate <class _Allocator> 2881227825Stheravenvoid 2882227825Stheravenvector<bool, _Allocator>::assign(size_type __n, const value_type& __x) 2883227825Stheraven{ 2884227825Stheraven __size_ = 0; 2885227825Stheraven if (__n > 0) 2886227825Stheraven { 2887227825Stheraven size_type __c = capacity(); 2888227825Stheraven if (__n <= __c) 2889227825Stheraven __size_ = __n; 2890227825Stheraven else 2891227825Stheraven { 2892227825Stheraven vector __v(__alloc()); 2893227825Stheraven __v.reserve(__recommend(__n)); 2894227825Stheraven __v.__size_ = __n; 2895227825Stheraven swap(__v); 2896227825Stheraven } 2897227825Stheraven _VSTD::fill_n(begin(), __n, __x); 2898227825Stheraven } 2899227825Stheraven} 2900227825Stheraven 2901227825Stheraventemplate <class _Allocator> 2902227825Stheraventemplate <class _InputIterator> 2903227825Stheraventypename enable_if 2904227825Stheraven< 2905227825Stheraven __is_input_iterator<_InputIterator>::value && 2906227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2907227825Stheraven void 2908227825Stheraven>::type 2909227825Stheravenvector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2910227825Stheraven{ 2911227825Stheraven clear(); 2912227825Stheraven for (; __first != __last; ++__first) 2913227825Stheraven push_back(*__first); 2914227825Stheraven} 2915227825Stheraven 2916227825Stheraventemplate <class _Allocator> 2917227825Stheraventemplate <class _ForwardIterator> 2918227825Stheraventypename enable_if 2919227825Stheraven< 2920227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2921227825Stheraven void 2922227825Stheraven>::type 2923227825Stheravenvector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2924227825Stheraven{ 2925227825Stheraven clear(); 2926227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 2927227825Stheraven if (__n) 2928227825Stheraven { 2929227825Stheraven if (__n > capacity()) 2930227825Stheraven { 2931227825Stheraven deallocate(); 2932227825Stheraven allocate(__n); 2933227825Stheraven } 2934227825Stheraven __construct_at_end(__first, __last); 2935227825Stheraven } 2936227825Stheraven} 2937227825Stheraven 2938227825Stheraventemplate <class _Allocator> 2939227825Stheravenvoid 2940227825Stheravenvector<bool, _Allocator>::reserve(size_type __n) 2941227825Stheraven{ 2942227825Stheraven if (__n > capacity()) 2943227825Stheraven { 2944227825Stheraven vector __v(this->__alloc()); 2945227825Stheraven __v.allocate(__n); 2946227825Stheraven __v.__construct_at_end(this->begin(), this->end()); 2947227825Stheraven swap(__v); 2948227825Stheraven __invalidate_all_iterators(); 2949227825Stheraven } 2950227825Stheraven} 2951227825Stheraven 2952227825Stheraventemplate <class _Allocator> 2953227825Stheravenvoid 2954227825Stheravenvector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT 2955227825Stheraven{ 2956227825Stheraven if (__external_cap_to_internal(size()) > __cap()) 2957227825Stheraven { 2958227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2959227825Stheraven try 2960227825Stheraven { 2961227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2962227825Stheraven vector(*this, allocator_type(__alloc())).swap(*this); 2963227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2964227825Stheraven } 2965227825Stheraven catch (...) 2966227825Stheraven { 2967227825Stheraven } 2968227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2969227825Stheraven } 2970227825Stheraven} 2971227825Stheraven 2972227825Stheraventemplate <class _Allocator> 2973227825Stheraventypename vector<bool, _Allocator>::reference 2974227825Stheravenvector<bool, _Allocator>::at(size_type __n) 2975227825Stheraven{ 2976227825Stheraven if (__n >= size()) 2977227825Stheraven this->__throw_out_of_range(); 2978227825Stheraven return (*this)[__n]; 2979227825Stheraven} 2980227825Stheraven 2981227825Stheraventemplate <class _Allocator> 2982227825Stheraventypename vector<bool, _Allocator>::const_reference 2983227825Stheravenvector<bool, _Allocator>::at(size_type __n) const 2984227825Stheraven{ 2985227825Stheraven if (__n >= size()) 2986227825Stheraven this->__throw_out_of_range(); 2987227825Stheraven return (*this)[__n]; 2988227825Stheraven} 2989227825Stheraven 2990227825Stheraventemplate <class _Allocator> 2991227825Stheravenvoid 2992227825Stheravenvector<bool, _Allocator>::push_back(const value_type& __x) 2993227825Stheraven{ 2994227825Stheraven if (this->__size_ == this->capacity()) 2995227825Stheraven reserve(__recommend(this->__size_ + 1)); 2996227825Stheraven ++this->__size_; 2997227825Stheraven back() = __x; 2998227825Stheraven} 2999227825Stheraven 3000227825Stheraventemplate <class _Allocator> 3001227825Stheraventypename vector<bool, _Allocator>::iterator 3002227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) 3003227825Stheraven{ 3004227825Stheraven iterator __r; 3005227825Stheraven if (size() < capacity()) 3006227825Stheraven { 3007227825Stheraven const_iterator __old_end = end(); 3008227825Stheraven ++__size_; 3009227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 3010227825Stheraven __r = __const_iterator_cast(__position); 3011227825Stheraven } 3012227825Stheraven else 3013227825Stheraven { 3014227825Stheraven vector __v(__alloc()); 3015227825Stheraven __v.reserve(__recommend(__size_ + 1)); 3016227825Stheraven __v.__size_ = __size_ + 1; 3017227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3018227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 3019227825Stheraven swap(__v); 3020227825Stheraven } 3021227825Stheraven *__r = __x; 3022227825Stheraven return __r; 3023227825Stheraven} 3024227825Stheraven 3025227825Stheraventemplate <class _Allocator> 3026227825Stheraventypename vector<bool, _Allocator>::iterator 3027227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) 3028227825Stheraven{ 3029227825Stheraven iterator __r; 3030227825Stheraven size_type __c = capacity(); 3031227825Stheraven if (__n <= __c && size() <= __c - __n) 3032227825Stheraven { 3033227825Stheraven const_iterator __old_end = end(); 3034227825Stheraven __size_ += __n; 3035227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 3036227825Stheraven __r = __const_iterator_cast(__position); 3037227825Stheraven } 3038227825Stheraven else 3039227825Stheraven { 3040227825Stheraven vector __v(__alloc()); 3041227825Stheraven __v.reserve(__recommend(__size_ + __n)); 3042227825Stheraven __v.__size_ = __size_ + __n; 3043227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3044227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 3045227825Stheraven swap(__v); 3046227825Stheraven } 3047227825Stheraven _VSTD::fill_n(__r, __n, __x); 3048227825Stheraven return __r; 3049227825Stheraven} 3050227825Stheraven 3051227825Stheraventemplate <class _Allocator> 3052227825Stheraventemplate <class _InputIterator> 3053227825Stheraventypename enable_if 3054227825Stheraven< 3055227825Stheraven __is_input_iterator <_InputIterator>::value && 3056227825Stheraven !__is_forward_iterator<_InputIterator>::value, 3057227825Stheraven typename vector<bool, _Allocator>::iterator 3058227825Stheraven>::type 3059227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 3060227825Stheraven{ 3061227825Stheraven difference_type __off = __position - begin(); 3062227825Stheraven iterator __p = __const_iterator_cast(__position); 3063227825Stheraven iterator __old_end = end(); 3064227825Stheraven for (; size() != capacity() && __first != __last; ++__first) 3065227825Stheraven { 3066227825Stheraven ++this->__size_; 3067227825Stheraven back() = *__first; 3068227825Stheraven } 3069227825Stheraven vector __v(__alloc()); 3070227825Stheraven if (__first != __last) 3071227825Stheraven { 3072227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 3073227825Stheraven try 3074227825Stheraven { 3075227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 3076227825Stheraven __v.assign(__first, __last); 3077227825Stheraven difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 3078227825Stheraven difference_type __old_p = __p - begin(); 3079227825Stheraven reserve(__recommend(size() + __v.size())); 3080227825Stheraven __p = begin() + __old_p; 3081227825Stheraven __old_end = begin() + __old_size; 3082227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 3083227825Stheraven } 3084227825Stheraven catch (...) 3085227825Stheraven { 3086227825Stheraven erase(__old_end, end()); 3087227825Stheraven throw; 3088227825Stheraven } 3089227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 3090227825Stheraven } 3091227825Stheraven __p = _VSTD::rotate(__p, __old_end, end()); 3092227825Stheraven insert(__p, __v.begin(), __v.end()); 3093227825Stheraven return begin() + __off; 3094227825Stheraven} 3095227825Stheraven 3096227825Stheraventemplate <class _Allocator> 3097227825Stheraventemplate <class _ForwardIterator> 3098227825Stheraventypename enable_if 3099227825Stheraven< 3100227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 3101227825Stheraven typename vector<bool, _Allocator>::iterator 3102227825Stheraven>::type 3103227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 3104227825Stheraven{ 3105227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 3106227825Stheraven iterator __r; 3107227825Stheraven size_type __c = capacity(); 3108227825Stheraven if (__n <= __c && size() <= __c - __n) 3109227825Stheraven { 3110227825Stheraven const_iterator __old_end = end(); 3111227825Stheraven __size_ += __n; 3112227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 3113227825Stheraven __r = __const_iterator_cast(__position); 3114227825Stheraven } 3115227825Stheraven else 3116227825Stheraven { 3117227825Stheraven vector __v(__alloc()); 3118227825Stheraven __v.reserve(__recommend(__size_ + __n)); 3119227825Stheraven __v.__size_ = __size_ + __n; 3120227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3121227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 3122227825Stheraven swap(__v); 3123227825Stheraven } 3124227825Stheraven _VSTD::copy(__first, __last, __r); 3125227825Stheraven return __r; 3126227825Stheraven} 3127227825Stheraven 3128227825Stheraventemplate <class _Allocator> 3129262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3130227825Stheraventypename vector<bool, _Allocator>::iterator 3131227825Stheravenvector<bool, _Allocator>::erase(const_iterator __position) 3132227825Stheraven{ 3133227825Stheraven iterator __r = __const_iterator_cast(__position); 3134227825Stheraven _VSTD::copy(__position + 1, this->cend(), __r); 3135227825Stheraven --__size_; 3136227825Stheraven return __r; 3137227825Stheraven} 3138227825Stheraven 3139227825Stheraventemplate <class _Allocator> 3140227825Stheraventypename vector<bool, _Allocator>::iterator 3141227825Stheravenvector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) 3142227825Stheraven{ 3143227825Stheraven iterator __r = __const_iterator_cast(__first); 3144227825Stheraven difference_type __d = __last - __first; 3145227825Stheraven _VSTD::copy(__last, this->cend(), __r); 3146227825Stheraven __size_ -= __d; 3147227825Stheraven return __r; 3148227825Stheraven} 3149227825Stheraven 3150227825Stheraventemplate <class _Allocator> 3151227825Stheravenvoid 3152227825Stheravenvector<bool, _Allocator>::swap(vector& __x) 3153227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3154227825Stheraven __is_nothrow_swappable<allocator_type>::value) 3155227825Stheraven{ 3156227825Stheraven _VSTD::swap(this->__begin_, __x.__begin_); 3157227825Stheraven _VSTD::swap(this->__size_, __x.__size_); 3158227825Stheraven _VSTD::swap(this->__cap(), __x.__cap()); 3159227825Stheraven __swap_alloc(this->__alloc(), __x.__alloc()); 3160227825Stheraven} 3161227825Stheraven 3162227825Stheraventemplate <class _Allocator> 3163227825Stheravenvoid 3164227825Stheravenvector<bool, _Allocator>::resize(size_type __sz, value_type __x) 3165227825Stheraven{ 3166227825Stheraven size_type __cs = size(); 3167227825Stheraven if (__cs < __sz) 3168227825Stheraven { 3169227825Stheraven iterator __r; 3170227825Stheraven size_type __c = capacity(); 3171227825Stheraven size_type __n = __sz - __cs; 3172227825Stheraven if (__n <= __c && __cs <= __c - __n) 3173227825Stheraven { 3174227825Stheraven __r = end(); 3175227825Stheraven __size_ += __n; 3176227825Stheraven } 3177227825Stheraven else 3178227825Stheraven { 3179227825Stheraven vector __v(__alloc()); 3180227825Stheraven __v.reserve(__recommend(__size_ + __n)); 3181227825Stheraven __v.__size_ = __size_ + __n; 3182227825Stheraven __r = _VSTD::copy(cbegin(), cend(), __v.begin()); 3183227825Stheraven swap(__v); 3184227825Stheraven } 3185227825Stheraven _VSTD::fill_n(__r, __n, __x); 3186227825Stheraven } 3187227825Stheraven else 3188227825Stheraven __size_ = __sz; 3189227825Stheraven} 3190227825Stheraven 3191227825Stheraventemplate <class _Allocator> 3192227825Stheravenvoid 3193227825Stheravenvector<bool, _Allocator>::flip() _NOEXCEPT 3194227825Stheraven{ 3195227825Stheraven // do middle whole words 3196227825Stheraven size_type __n = __size_; 3197227825Stheraven __storage_pointer __p = __begin_; 3198227825Stheraven for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3199227825Stheraven *__p = ~*__p; 3200227825Stheraven // do last partial word 3201227825Stheraven if (__n > 0) 3202227825Stheraven { 3203227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3204227825Stheraven __storage_type __b = *__p & __m; 3205227825Stheraven *__p &= ~__m; 3206227825Stheraven *__p |= ~__b & __m; 3207227825Stheraven } 3208227825Stheraven} 3209227825Stheraven 3210227825Stheraventemplate <class _Allocator> 3211227825Stheravenbool 3212227825Stheravenvector<bool, _Allocator>::__invariants() const 3213227825Stheraven{ 3214253159Stheraven if (this->__begin_ == nullptr) 3215227825Stheraven { 3216227825Stheraven if (this->__size_ != 0 || this->__cap() != 0) 3217227825Stheraven return false; 3218227825Stheraven } 3219227825Stheraven else 3220227825Stheraven { 3221227825Stheraven if (this->__cap() == 0) 3222227825Stheraven return false; 3223227825Stheraven if (this->__size_ > this->capacity()) 3224227825Stheraven return false; 3225227825Stheraven } 3226227825Stheraven return true; 3227227825Stheraven} 3228227825Stheraven 3229227825Stheraventemplate <class _Allocator> 3230227825Stheravensize_t 3231227825Stheravenvector<bool, _Allocator>::__hash_code() const _NOEXCEPT 3232227825Stheraven{ 3233227825Stheraven size_t __h = 0; 3234227825Stheraven // do middle whole words 3235227825Stheraven size_type __n = __size_; 3236227825Stheraven __storage_pointer __p = __begin_; 3237227825Stheraven for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3238227825Stheraven __h ^= *__p; 3239227825Stheraven // do last partial word 3240227825Stheraven if (__n > 0) 3241227825Stheraven { 3242227825Stheraven const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3243227825Stheraven __h ^= *__p & __m; 3244227825Stheraven } 3245227825Stheraven return __h; 3246227825Stheraven} 3247227825Stheraven 3248227825Stheraventemplate <class _Allocator> 3249262801Sdimstruct _LIBCPP_TYPE_VIS_ONLY hash<vector<bool, _Allocator> > 3250227825Stheraven : public unary_function<vector<bool, _Allocator>, size_t> 3251227825Stheraven{ 3252227825Stheraven _LIBCPP_INLINE_VISIBILITY 3253227825Stheraven size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT 3254227825Stheraven {return __vec.__hash_code();} 3255227825Stheraven}; 3256227825Stheraven 3257227825Stheraventemplate <class _Tp, class _Allocator> 3258262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3259227825Stheravenbool 3260227825Stheravenoperator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3261227825Stheraven{ 3262227825Stheraven const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 3263227825Stheraven return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 3264227825Stheraven} 3265227825Stheraven 3266227825Stheraventemplate <class _Tp, class _Allocator> 3267262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3268227825Stheravenbool 3269227825Stheravenoperator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3270227825Stheraven{ 3271227825Stheraven return !(__x == __y); 3272227825Stheraven} 3273227825Stheraven 3274227825Stheraventemplate <class _Tp, class _Allocator> 3275262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3276227825Stheravenbool 3277227825Stheravenoperator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3278227825Stheraven{ 3279227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 3280227825Stheraven} 3281227825Stheraven 3282227825Stheraventemplate <class _Tp, class _Allocator> 3283262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3284227825Stheravenbool 3285227825Stheravenoperator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3286227825Stheraven{ 3287227825Stheraven return __y < __x; 3288227825Stheraven} 3289227825Stheraven 3290227825Stheraventemplate <class _Tp, class _Allocator> 3291262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3292227825Stheravenbool 3293227825Stheravenoperator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3294227825Stheraven{ 3295227825Stheraven return !(__x < __y); 3296227825Stheraven} 3297227825Stheraven 3298227825Stheraventemplate <class _Tp, class _Allocator> 3299262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3300227825Stheravenbool 3301227825Stheravenoperator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3302227825Stheraven{ 3303227825Stheraven return !(__y < __x); 3304227825Stheraven} 3305227825Stheraven 3306227825Stheraventemplate <class _Tp, class _Allocator> 3307262801Sdiminline _LIBCPP_INLINE_VISIBILITY 3308227825Stheravenvoid 3309227825Stheravenswap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) 3310227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3311227825Stheraven{ 3312227825Stheraven __x.swap(__y); 3313227825Stheraven} 3314227825Stheraven 3315227825Stheraven_LIBCPP_END_NAMESPACE_STD 3316227825Stheraven 3317227825Stheraven#endif // _LIBCPP_VECTOR 3318