vector revision 249998
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); 41227825Stheraven vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); 42227825Stheraven template <class InputIterator> 43227825Stheraven vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 44227825Stheraven vector(const vector& x); 45227825Stheraven vector(vector&& x) 46227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 47227825Stheraven vector(initializer_list<value_type> il); 48227825Stheraven vector(initializer_list<value_type> il, const allocator_type& a); 49227825Stheraven ~vector(); 50227825Stheraven vector& operator=(const vector& x); 51227825Stheraven vector& operator=(vector&& x) 52227825Stheraven noexcept( 53227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 54227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 55227825Stheraven vector& operator=(initializer_list<value_type> il); 56227825Stheraven template <class InputIterator> 57227825Stheraven void assign(InputIterator first, InputIterator last); 58227825Stheraven void assign(size_type n, const value_type& u); 59227825Stheraven void assign(initializer_list<value_type> il); 60227825Stheraven 61227825Stheraven allocator_type get_allocator() const noexcept; 62227825Stheraven 63227825Stheraven iterator begin() noexcept; 64227825Stheraven const_iterator begin() const noexcept; 65227825Stheraven iterator end() noexcept; 66227825Stheraven const_iterator end() const noexcept; 67227825Stheraven 68227825Stheraven reverse_iterator rbegin() noexcept; 69227825Stheraven const_reverse_iterator rbegin() const noexcept; 70227825Stheraven reverse_iterator rend() noexcept; 71227825Stheraven const_reverse_iterator rend() const noexcept; 72227825Stheraven 73227825Stheraven const_iterator cbegin() const noexcept; 74227825Stheraven const_iterator cend() const noexcept; 75227825Stheraven const_reverse_iterator crbegin() const noexcept; 76227825Stheraven const_reverse_iterator crend() const noexcept; 77227825Stheraven 78227825Stheraven size_type size() const noexcept; 79227825Stheraven size_type max_size() const noexcept; 80227825Stheraven size_type capacity() const noexcept; 81227825Stheraven bool empty() const noexcept; 82227825Stheraven void reserve(size_type n); 83227825Stheraven void shrink_to_fit() noexcept; 84227825Stheraven 85227825Stheraven reference operator[](size_type n); 86227825Stheraven const_reference operator[](size_type n) const; 87227825Stheraven reference at(size_type n); 88227825Stheraven const_reference at(size_type n) const; 89227825Stheraven 90227825Stheraven reference front(); 91227825Stheraven const_reference front() const; 92227825Stheraven reference back(); 93227825Stheraven const_reference back() const; 94227825Stheraven 95227825Stheraven value_type* data() noexcept; 96227825Stheraven const value_type* data() const noexcept; 97227825Stheraven 98227825Stheraven void push_back(const value_type& x); 99227825Stheraven void push_back(value_type&& x); 100227825Stheraven template <class... Args> 101227825Stheraven void emplace_back(Args&&... args); 102227825Stheraven void pop_back(); 103227825Stheraven 104227825Stheraven template <class... Args> iterator emplace(const_iterator position, Args&&... args); 105227825Stheraven iterator insert(const_iterator position, const value_type& x); 106227825Stheraven iterator insert(const_iterator position, value_type&& x); 107227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 108227825Stheraven template <class InputIterator> 109227825Stheraven iterator insert(const_iterator position, InputIterator first, InputIterator last); 110227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 111227825Stheraven 112227825Stheraven iterator erase(const_iterator position); 113227825Stheraven iterator erase(const_iterator first, const_iterator last); 114227825Stheraven 115227825Stheraven void clear() noexcept; 116227825Stheraven 117227825Stheraven void resize(size_type sz); 118227825Stheraven void resize(size_type sz, const value_type& c); 119227825Stheraven 120227825Stheraven void swap(vector&) 121227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 122227825Stheraven __is_nothrow_swappable<allocator_type>::value); 123227825Stheraven 124227825Stheraven bool __invariants() const; 125227825Stheraven}; 126227825Stheraven 127227825Stheraventemplate <class Allocator = allocator<T> > 128227825Stheravenclass vector<bool, Allocator> 129227825Stheraven{ 130227825Stheravenpublic: 131227825Stheraven typedef bool value_type; 132227825Stheraven typedef Allocator allocator_type; 133227825Stheraven typedef implementation-defined iterator; 134227825Stheraven typedef implementation-defined const_iterator; 135227825Stheraven typedef typename allocator_type::size_type size_type; 136227825Stheraven typedef typename allocator_type::difference_type difference_type; 137227825Stheraven typedef iterator pointer; 138227825Stheraven typedef const_iterator const_pointer; 139227825Stheraven typedef std::reverse_iterator<iterator> reverse_iterator; 140227825Stheraven typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 141227825Stheraven 142227825Stheraven class reference 143227825Stheraven { 144227825Stheraven public: 145227825Stheraven reference(const reference&) noexcept; 146227825Stheraven operator bool() const noexcept; 147227825Stheraven reference& operator=(const bool x) noexcept; 148227825Stheraven reference& operator=(const reference& x) noexcept; 149227825Stheraven iterator operator&() const noexcept; 150227825Stheraven void flip() noexcept; 151227825Stheraven }; 152227825Stheraven 153227825Stheraven class const_reference 154227825Stheraven { 155227825Stheraven public: 156227825Stheraven const_reference(const reference&) noexcept; 157227825Stheraven operator bool() const noexcept; 158227825Stheraven const_iterator operator&() const noexcept; 159227825Stheraven }; 160227825Stheraven 161227825Stheraven vector() 162227825Stheraven noexcept(is_nothrow_default_constructible<allocator_type>::value); 163227825Stheraven explicit vector(const allocator_type&); 164227825Stheraven explicit vector(size_type n, const value_type& value = value_type(), const allocator_type& = allocator_type()); 165227825Stheraven template <class InputIterator> 166227825Stheraven vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); 167227825Stheraven vector(const vector& x); 168227825Stheraven vector(vector&& x) 169227825Stheraven noexcept(is_nothrow_move_constructible<allocator_type>::value); 170227825Stheraven vector(initializer_list<value_type> il); 171227825Stheraven vector(initializer_list<value_type> il, const allocator_type& a); 172227825Stheraven ~vector(); 173227825Stheraven vector& operator=(const vector& x); 174227825Stheraven vector& operator=(vector&& x) 175227825Stheraven noexcept( 176227825Stheraven allocator_type::propagate_on_container_move_assignment::value && 177227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 178227825Stheraven vector& operator=(initializer_list<value_type> il); 179227825Stheraven template <class InputIterator> 180227825Stheraven void assign(InputIterator first, InputIterator last); 181227825Stheraven void assign(size_type n, const value_type& u); 182227825Stheraven void assign(initializer_list<value_type> il); 183227825Stheraven 184227825Stheraven allocator_type get_allocator() const noexcept; 185227825Stheraven 186227825Stheraven iterator begin() noexcept; 187227825Stheraven const_iterator begin() const noexcept; 188227825Stheraven iterator end() noexcept; 189227825Stheraven const_iterator end() const noexcept; 190227825Stheraven 191227825Stheraven reverse_iterator rbegin() noexcept; 192227825Stheraven const_reverse_iterator rbegin() const noexcept; 193227825Stheraven reverse_iterator rend() noexcept; 194227825Stheraven const_reverse_iterator rend() const noexcept; 195227825Stheraven 196227825Stheraven const_iterator cbegin() const noexcept; 197227825Stheraven const_iterator cend() const noexcept; 198227825Stheraven const_reverse_iterator crbegin() const noexcept; 199227825Stheraven const_reverse_iterator crend() const noexcept; 200227825Stheraven 201227825Stheraven size_type size() const noexcept; 202227825Stheraven size_type max_size() const noexcept; 203227825Stheraven size_type capacity() const noexcept; 204227825Stheraven bool empty() const noexcept; 205227825Stheraven void reserve(size_type n); 206227825Stheraven void shrink_to_fit() noexcept; 207227825Stheraven 208227825Stheraven reference operator[](size_type n); 209227825Stheraven const_reference operator[](size_type n) const; 210227825Stheraven reference at(size_type n); 211227825Stheraven const_reference at(size_type n) const; 212227825Stheraven 213227825Stheraven reference front(); 214227825Stheraven const_reference front() const; 215227825Stheraven reference back(); 216227825Stheraven const_reference back() const; 217227825Stheraven 218227825Stheraven void push_back(const value_type& x); 219227825Stheraven void pop_back(); 220227825Stheraven 221227825Stheraven iterator insert(const_iterator position, const value_type& x); 222227825Stheraven iterator insert(const_iterator position, size_type n, const value_type& x); 223227825Stheraven template <class InputIterator> 224227825Stheraven iterator insert(const_iterator position, InputIterator first, InputIterator last); 225227825Stheraven iterator insert(const_iterator position, initializer_list<value_type> il); 226227825Stheraven 227227825Stheraven iterator erase(const_iterator position); 228227825Stheraven iterator erase(const_iterator first, const_iterator last); 229227825Stheraven 230227825Stheraven void clear() noexcept; 231227825Stheraven 232227825Stheraven void resize(size_type sz); 233227825Stheraven void resize(size_type sz, value_type x); 234227825Stheraven 235227825Stheraven void swap(vector&) 236227825Stheraven noexcept(!allocator_type::propagate_on_container_swap::value || 237227825Stheraven __is_nothrow_swappable<allocator_type>::value); 238227825Stheraven void flip() noexcept; 239227825Stheraven 240227825Stheraven bool __invariants() const; 241227825Stheraven}; 242227825Stheraven 243227825Stheraventemplate <class Allocator> struct hash<std::vector<bool, Allocator>>; 244227825Stheraven 245227825Stheraventemplate <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 246227825Stheraventemplate <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 247227825Stheraventemplate <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y); 248227825Stheraventemplate <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y); 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); 251227825Stheraven 252227825Stheraventemplate <class T, class Allocator> 253227825Stheravenvoid swap(vector<T,Allocator>& x, vector<T,Allocator>& y) 254227825Stheraven noexcept(noexcept(x.swap(y))); 255227825Stheraven 256227825Stheraven} // std 257227825Stheraven 258227825Stheraven*/ 259227825Stheraven 260227825Stheraven#include <__config> 261227825Stheraven#include <__bit_reference> 262227825Stheraven#include <type_traits> 263227825Stheraven#include <climits> 264227825Stheraven#include <limits> 265227825Stheraven#include <initializer_list> 266227825Stheraven#include <memory> 267227825Stheraven#include <stdexcept> 268227825Stheraven#include <algorithm> 269227825Stheraven#include <cstring> 270227825Stheraven#include <__split_buffer> 271227825Stheraven#include <__functional_base> 272227825Stheraven 273232950Stheraven#include <__undef_min_max> 274232950Stheraven 275227825Stheraven#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 276227825Stheraven#pragma GCC system_header 277227825Stheraven#endif 278227825Stheraven 279227825Stheraven_LIBCPP_BEGIN_NAMESPACE_STD 280227825Stheraven 281227825Stheraventemplate <bool> 282227825Stheravenclass __vector_base_common 283227825Stheraven{ 284227825Stheravenprotected: 285227825Stheraven _LIBCPP_ALWAYS_INLINE __vector_base_common() {} 286227825Stheraven void __throw_length_error() const; 287227825Stheraven void __throw_out_of_range() const; 288227825Stheraven}; 289227825Stheraven 290227825Stheraventemplate <bool __b> 291227825Stheravenvoid 292227825Stheraven__vector_base_common<__b>::__throw_length_error() const 293227825Stheraven{ 294227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 295227825Stheraven throw length_error("vector"); 296227825Stheraven#else 297227825Stheraven assert(!"vector length_error"); 298227825Stheraven#endif 299227825Stheraven} 300227825Stheraven 301227825Stheraventemplate <bool __b> 302227825Stheravenvoid 303227825Stheraven__vector_base_common<__b>::__throw_out_of_range() const 304227825Stheraven{ 305227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 306227825Stheraven throw out_of_range("vector"); 307227825Stheraven#else 308227825Stheraven assert(!"vector out_of_range"); 309227825Stheraven#endif 310227825Stheraven} 311227825Stheraven 312227825Stheraven#ifdef _MSC_VER 313227825Stheraven#pragma warning( push ) 314227825Stheraven#pragma warning( disable: 4231 ) 315227825Stheraven#endif // _MSC_VER 316242945Stheraven_LIBCPP_EXTERN_TEMPLATE(class __vector_base_common<true>) 317227825Stheraven#ifdef _MSC_VER 318227825Stheraven#pragma warning( pop ) 319227825Stheraven#endif // _MSC_VER 320227825Stheraven 321227825Stheraventemplate <class _Tp, class _Allocator> 322227825Stheravenclass __vector_base 323227825Stheraven : protected __vector_base_common<true> 324227825Stheraven{ 325227825Stheravenprotected: 326227825Stheraven typedef _Tp value_type; 327227825Stheraven typedef _Allocator allocator_type; 328227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 329227825Stheraven typedef value_type& reference; 330227825Stheraven typedef const value_type& const_reference; 331227825Stheraven typedef typename __alloc_traits::size_type size_type; 332227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 333227825Stheraven typedef typename __alloc_traits::pointer pointer; 334227825Stheraven typedef typename __alloc_traits::const_pointer const_pointer; 335227825Stheraven typedef pointer iterator; 336227825Stheraven typedef const_pointer const_iterator; 337227825Stheraven 338227825Stheraven pointer __begin_; 339227825Stheraven pointer __end_; 340227825Stheraven __compressed_pair<pointer, allocator_type> __end_cap_; 341227825Stheraven 342227825Stheraven _LIBCPP_INLINE_VISIBILITY 343227825Stheraven allocator_type& __alloc() _NOEXCEPT 344227825Stheraven {return __end_cap_.second();} 345227825Stheraven _LIBCPP_INLINE_VISIBILITY 346227825Stheraven const allocator_type& __alloc() const _NOEXCEPT 347227825Stheraven {return __end_cap_.second();} 348227825Stheraven _LIBCPP_INLINE_VISIBILITY 349227825Stheraven pointer& __end_cap() _NOEXCEPT 350227825Stheraven {return __end_cap_.first();} 351227825Stheraven _LIBCPP_INLINE_VISIBILITY 352227825Stheraven const pointer& __end_cap() const _NOEXCEPT 353227825Stheraven {return __end_cap_.first();} 354227825Stheraven 355227825Stheraven _LIBCPP_INLINE_VISIBILITY 356227825Stheraven __vector_base() 357227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 358227825Stheraven _LIBCPP_INLINE_VISIBILITY __vector_base(const allocator_type& __a); 359227825Stheraven ~__vector_base(); 360227825Stheraven 361227825Stheraven _LIBCPP_INLINE_VISIBILITY 362227825Stheraven void clear() _NOEXCEPT {__destruct_at_end(__begin_);} 363227825Stheraven _LIBCPP_INLINE_VISIBILITY 364227825Stheraven size_type capacity() const _NOEXCEPT 365227825Stheraven {return static_cast<size_type>(__end_cap() - __begin_);} 366227825Stheraven 367227825Stheraven _LIBCPP_INLINE_VISIBILITY 368227825Stheraven void __destruct_at_end(const_pointer __new_last) _NOEXCEPT 369232950Stheraven {__destruct_at_end(__new_last, false_type());} 370227825Stheraven _LIBCPP_INLINE_VISIBILITY 371227825Stheraven void __destruct_at_end(const_pointer __new_last, false_type) _NOEXCEPT; 372227825Stheraven _LIBCPP_INLINE_VISIBILITY 373227825Stheraven void __destruct_at_end(const_pointer __new_last, true_type) _NOEXCEPT; 374227825Stheraven 375227825Stheraven _LIBCPP_INLINE_VISIBILITY 376227825Stheraven void __copy_assign_alloc(const __vector_base& __c) 377227825Stheraven {__copy_assign_alloc(__c, integral_constant<bool, 378227825Stheraven __alloc_traits::propagate_on_container_copy_assignment::value>());} 379227825Stheraven 380227825Stheraven _LIBCPP_INLINE_VISIBILITY 381227825Stheraven void __move_assign_alloc(__vector_base& __c) 382227825Stheraven _NOEXCEPT_( 383227825Stheraven !__alloc_traits::propagate_on_container_move_assignment::value || 384227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 385227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 386227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>());} 387227825Stheraven 388227825Stheraven _LIBCPP_INLINE_VISIBILITY 389227825Stheraven static void __swap_alloc(allocator_type& __x, allocator_type& __y) 390227825Stheraven _NOEXCEPT_( 391227825Stheraven !__alloc_traits::propagate_on_container_swap::value || 392227825Stheraven __is_nothrow_swappable<allocator_type>::value) 393227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 394227825Stheraven __alloc_traits::propagate_on_container_swap::value>());} 395227825Stheravenprivate: 396227825Stheraven _LIBCPP_INLINE_VISIBILITY 397227825Stheraven void __copy_assign_alloc(const __vector_base& __c, true_type) 398227825Stheraven { 399227825Stheraven if (__alloc() != __c.__alloc()) 400227825Stheraven { 401227825Stheraven clear(); 402227825Stheraven __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 403227825Stheraven __begin_ = __end_ = __end_cap() = nullptr; 404227825Stheraven } 405227825Stheraven __alloc() = __c.__alloc(); 406227825Stheraven } 407227825Stheraven 408227825Stheraven _LIBCPP_INLINE_VISIBILITY 409232950Stheraven void __copy_assign_alloc(const __vector_base&, false_type) 410227825Stheraven {} 411227825Stheraven 412227825Stheraven _LIBCPP_INLINE_VISIBILITY 413227825Stheraven void __move_assign_alloc(__vector_base& __c, true_type) 414227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 415227825Stheraven { 416227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 417227825Stheraven } 418227825Stheraven 419227825Stheraven _LIBCPP_INLINE_VISIBILITY 420232950Stheraven void __move_assign_alloc(__vector_base&, false_type) 421227825Stheraven _NOEXCEPT 422227825Stheraven {} 423227825Stheraven 424227825Stheraven _LIBCPP_INLINE_VISIBILITY 425227825Stheraven static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type) 426227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 427227825Stheraven { 428227825Stheraven using _VSTD::swap; 429227825Stheraven swap(__x, __y); 430227825Stheraven } 431227825Stheraven _LIBCPP_INLINE_VISIBILITY 432232950Stheraven static void __swap_alloc(allocator_type&, allocator_type&, false_type) 433227825Stheraven _NOEXCEPT 434227825Stheraven {} 435227825Stheraven}; 436227825Stheraven 437227825Stheraventemplate <class _Tp, class _Allocator> 438227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 439227825Stheravenvoid 440227825Stheraven__vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, false_type) _NOEXCEPT 441227825Stheraven{ 442232950Stheraven while (__new_last != __end_) 443227825Stheraven __alloc_traits::destroy(__alloc(), const_cast<pointer>(--__end_)); 444227825Stheraven} 445227825Stheraven 446227825Stheraventemplate <class _Tp, class _Allocator> 447227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 448227825Stheravenvoid 449227825Stheraven__vector_base<_Tp, _Allocator>::__destruct_at_end(const_pointer __new_last, true_type) _NOEXCEPT 450227825Stheraven{ 451227825Stheraven __end_ = const_cast<pointer>(__new_last); 452227825Stheraven} 453227825Stheraven 454227825Stheraventemplate <class _Tp, class _Allocator> 455227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 456227825Stheraven__vector_base<_Tp, _Allocator>::__vector_base() 457227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 458227825Stheraven : __begin_(0), 459227825Stheraven __end_(0), 460227825Stheraven __end_cap_(0) 461227825Stheraven{ 462227825Stheraven} 463227825Stheraven 464227825Stheraventemplate <class _Tp, class _Allocator> 465227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 466227825Stheraven__vector_base<_Tp, _Allocator>::__vector_base(const allocator_type& __a) 467227825Stheraven : __begin_(0), 468227825Stheraven __end_(0), 469227825Stheraven __end_cap_(0, __a) 470227825Stheraven{ 471227825Stheraven} 472227825Stheraven 473227825Stheraventemplate <class _Tp, class _Allocator> 474227825Stheraven__vector_base<_Tp, _Allocator>::~__vector_base() 475227825Stheraven{ 476227825Stheraven if (__begin_ != 0) 477227825Stheraven { 478227825Stheraven clear(); 479227825Stheraven __alloc_traits::deallocate(__alloc(), __begin_, capacity()); 480227825Stheraven } 481227825Stheraven} 482227825Stheraven 483227825Stheraventemplate <class _Tp, class _Allocator = allocator<_Tp> > 484249998Sdimclass _LIBCPP_TYPE_VIS vector 485227825Stheraven : private __vector_base<_Tp, _Allocator> 486227825Stheraven{ 487227825Stheravenprivate: 488227825Stheraven typedef __vector_base<_Tp, _Allocator> __base; 489227825Stheravenpublic: 490227825Stheraven typedef vector __self; 491227825Stheraven typedef _Tp value_type; 492227825Stheraven typedef _Allocator allocator_type; 493227825Stheraven typedef typename __base::__alloc_traits __alloc_traits; 494227825Stheraven typedef typename __base::reference reference; 495227825Stheraven typedef typename __base::const_reference const_reference; 496227825Stheraven typedef typename __base::size_type size_type; 497227825Stheraven typedef typename __base::difference_type difference_type; 498227825Stheraven typedef typename __base::pointer pointer; 499227825Stheraven typedef typename __base::const_pointer const_pointer; 500227825Stheraven typedef __wrap_iter<pointer> iterator; 501227825Stheraven typedef __wrap_iter<const_pointer> const_iterator; 502227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 503227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 504227825Stheraven 505249998Sdim static_assert((is_same<typename allocator_type::value_type, value_type>::value), 506249998Sdim "Allocator::value_type must be same type as value_type"); 507249998Sdim 508227825Stheraven _LIBCPP_INLINE_VISIBILITY 509227825Stheraven vector() 510227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 511227825Stheraven { 512227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 513227825Stheraven __get_db()->__insert_c(this); 514227825Stheraven#endif 515227825Stheraven } 516227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) 517227825Stheraven : __base(__a) 518227825Stheraven { 519227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 520227825Stheraven __get_db()->__insert_c(this); 521227825Stheraven#endif 522227825Stheraven } 523227825Stheraven explicit vector(size_type __n); 524227825Stheraven vector(size_type __n, const_reference __x); 525227825Stheraven vector(size_type __n, const_reference __x, const allocator_type& __a); 526227825Stheraven template <class _InputIterator> 527227825Stheraven vector(_InputIterator __first, _InputIterator __last, 528227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 529249998Sdim !__is_forward_iterator<_InputIterator>::value && 530249998Sdim is_constructible< 531249998Sdim value_type, 532249998Sdim typename iterator_traits<_InputIterator>::reference>::value>::type* = 0); 533227825Stheraven template <class _InputIterator> 534227825Stheraven vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 535227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 536249998Sdim !__is_forward_iterator<_InputIterator>::value && 537249998Sdim is_constructible< 538249998Sdim value_type, 539249998Sdim typename iterator_traits<_InputIterator>::reference>::value>::type* = 0); 540227825Stheraven template <class _ForwardIterator> 541227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, 542249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 543249998Sdim is_constructible< 544249998Sdim value_type, 545249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0); 546227825Stheraven template <class _ForwardIterator> 547227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 548249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 549249998Sdim is_constructible< 550249998Sdim value_type, 551249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0); 552227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven vector(initializer_list<value_type> __il); 555227825Stheraven _LIBCPP_INLINE_VISIBILITY 556227825Stheraven vector(initializer_list<value_type> __il, const allocator_type& __a); 557227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 558227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 559227825Stheraven _LIBCPP_INLINE_VISIBILITY 560227825Stheraven ~vector() 561227825Stheraven { 562227825Stheraven __get_db()->__erase_c(this); 563227825Stheraven } 564227825Stheraven#endif 565227825Stheraven 566227825Stheraven vector(const vector& __x); 567227825Stheraven vector(const vector& __x, const allocator_type& __a); 568227825Stheraven _LIBCPP_INLINE_VISIBILITY 569227825Stheraven vector& operator=(const vector& __x); 570227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 571227825Stheraven _LIBCPP_INLINE_VISIBILITY 572227825Stheraven vector(vector&& __x) 573227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 574227825Stheraven _LIBCPP_INLINE_VISIBILITY 575227825Stheraven vector(vector&& __x, const allocator_type& __a); 576227825Stheraven _LIBCPP_INLINE_VISIBILITY 577227825Stheraven vector& operator=(vector&& __x) 578227825Stheraven _NOEXCEPT_( 579227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 580227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 581227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 582227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 583227825Stheraven _LIBCPP_INLINE_VISIBILITY 584227825Stheraven vector& operator=(initializer_list<value_type> __il) 585227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 586227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 587227825Stheraven 588227825Stheraven template <class _InputIterator> 589227825Stheraven typename enable_if 590227825Stheraven < 591227825Stheraven __is_input_iterator <_InputIterator>::value && 592249998Sdim !__is_forward_iterator<_InputIterator>::value && 593249998Sdim is_constructible< 594249998Sdim value_type, 595249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 596227825Stheraven void 597227825Stheraven >::type 598227825Stheraven assign(_InputIterator __first, _InputIterator __last); 599227825Stheraven template <class _ForwardIterator> 600227825Stheraven typename enable_if 601227825Stheraven < 602249998Sdim __is_forward_iterator<_ForwardIterator>::value && 603249998Sdim is_constructible< 604249998Sdim value_type, 605249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 606227825Stheraven void 607227825Stheraven >::type 608227825Stheraven assign(_ForwardIterator __first, _ForwardIterator __last); 609227825Stheraven 610227825Stheraven void assign(size_type __n, const_reference __u); 611227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 612227825Stheraven _LIBCPP_INLINE_VISIBILITY 613227825Stheraven void assign(initializer_list<value_type> __il) 614227825Stheraven {assign(__il.begin(), __il.end());} 615227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 616227825Stheraven 617227825Stheraven _LIBCPP_INLINE_VISIBILITY 618227825Stheraven allocator_type get_allocator() const _NOEXCEPT 619227825Stheraven {return this->__alloc();} 620227825Stheraven 621227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT; 622227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT; 623227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT; 624227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT; 625227825Stheraven 626227825Stheraven _LIBCPP_INLINE_VISIBILITY 627227825Stheraven reverse_iterator rbegin() _NOEXCEPT 628227825Stheraven {return reverse_iterator(end());} 629227825Stheraven _LIBCPP_INLINE_VISIBILITY 630227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 631227825Stheraven {return const_reverse_iterator(end());} 632227825Stheraven _LIBCPP_INLINE_VISIBILITY 633227825Stheraven reverse_iterator rend() _NOEXCEPT 634227825Stheraven {return reverse_iterator(begin());} 635227825Stheraven _LIBCPP_INLINE_VISIBILITY 636227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 637227825Stheraven {return const_reverse_iterator(begin());} 638227825Stheraven 639227825Stheraven _LIBCPP_INLINE_VISIBILITY 640227825Stheraven const_iterator cbegin() const _NOEXCEPT 641227825Stheraven {return begin();} 642227825Stheraven _LIBCPP_INLINE_VISIBILITY 643227825Stheraven const_iterator cend() const _NOEXCEPT 644227825Stheraven {return end();} 645227825Stheraven _LIBCPP_INLINE_VISIBILITY 646227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 647227825Stheraven {return rbegin();} 648227825Stheraven _LIBCPP_INLINE_VISIBILITY 649227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 650227825Stheraven {return rend();} 651227825Stheraven 652227825Stheraven _LIBCPP_INLINE_VISIBILITY 653227825Stheraven size_type size() const _NOEXCEPT 654227825Stheraven {return static_cast<size_type>(this->__end_ - this->__begin_);} 655227825Stheraven _LIBCPP_INLINE_VISIBILITY 656227825Stheraven size_type capacity() const _NOEXCEPT 657227825Stheraven {return __base::capacity();} 658227825Stheraven _LIBCPP_INLINE_VISIBILITY 659227825Stheraven bool empty() const _NOEXCEPT 660227825Stheraven {return this->__begin_ == this->__end_;} 661227825Stheraven size_type max_size() const _NOEXCEPT; 662227825Stheraven void reserve(size_type __n); 663227825Stheraven void shrink_to_fit() _NOEXCEPT; 664227825Stheraven 665227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); 666227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; 667227825Stheraven reference at(size_type __n); 668227825Stheraven const_reference at(size_type __n) const; 669227825Stheraven 670227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() 671227825Stheraven { 672227825Stheraven _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 673227825Stheraven return *this->__begin_; 674227825Stheraven } 675227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const 676227825Stheraven { 677227825Stheraven _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 678227825Stheraven return *this->__begin_; 679227825Stheraven } 680227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() 681227825Stheraven { 682227825Stheraven _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 683227825Stheraven return *(this->__end_ - 1); 684227825Stheraven } 685227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const 686227825Stheraven { 687227825Stheraven _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 688227825Stheraven return *(this->__end_ - 1); 689227825Stheraven } 690227825Stheraven 691227825Stheraven _LIBCPP_INLINE_VISIBILITY 692227825Stheraven value_type* data() _NOEXCEPT 693227825Stheraven {return _VSTD::__to_raw_pointer(this->__begin_);} 694227825Stheraven _LIBCPP_INLINE_VISIBILITY 695227825Stheraven const value_type* data() const _NOEXCEPT 696227825Stheraven {return _VSTD::__to_raw_pointer(this->__begin_);} 697227825Stheraven 698227825Stheraven _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 699227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 700232950Stheraven _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x); 701227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 702227825Stheraven template <class... _Args> 703227825Stheraven void emplace_back(_Args&&... __args); 704227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 705227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 706227825Stheraven void pop_back(); 707227825Stheraven 708227825Stheraven iterator insert(const_iterator __position, const_reference __x); 709227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 710227825Stheraven iterator insert(const_iterator __position, value_type&& __x); 711227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 712227825Stheraven template <class... _Args> 713227825Stheraven iterator emplace(const_iterator __position, _Args&&... __args); 714227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 715227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 716227825Stheraven iterator insert(const_iterator __position, size_type __n, const_reference __x); 717227825Stheraven template <class _InputIterator> 718227825Stheraven typename enable_if 719227825Stheraven < 720227825Stheraven __is_input_iterator <_InputIterator>::value && 721249998Sdim !__is_forward_iterator<_InputIterator>::value && 722249998Sdim is_constructible< 723249998Sdim value_type, 724249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 725227825Stheraven iterator 726227825Stheraven >::type 727227825Stheraven insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 728227825Stheraven template <class _ForwardIterator> 729227825Stheraven typename enable_if 730227825Stheraven < 731249998Sdim __is_forward_iterator<_ForwardIterator>::value && 732249998Sdim is_constructible< 733249998Sdim value_type, 734249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 735227825Stheraven iterator 736227825Stheraven >::type 737227825Stheraven insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 738227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 739227825Stheraven _LIBCPP_INLINE_VISIBILITY 740227825Stheraven iterator insert(const_iterator __position, initializer_list<value_type> __il) 741227825Stheraven {return insert(__position, __il.begin(), __il.end());} 742227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 743227825Stheraven 744227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 745227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 746227825Stheraven 747227825Stheraven _LIBCPP_INLINE_VISIBILITY 748227825Stheraven void clear() _NOEXCEPT 749227825Stheraven { 750227825Stheraven __base::clear(); 751227825Stheraven __invalidate_all_iterators(); 752227825Stheraven } 753227825Stheraven 754227825Stheraven void resize(size_type __sz); 755227825Stheraven void resize(size_type __sz, const_reference __x); 756227825Stheraven 757227825Stheraven void swap(vector&) 758227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 759227825Stheraven __is_nothrow_swappable<allocator_type>::value); 760227825Stheraven 761227825Stheraven bool __invariants() const; 762227825Stheraven 763227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 764227825Stheraven 765227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 766227825Stheraven bool __decrementable(const const_iterator* __i) const; 767227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 768227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 769227825Stheraven 770227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 771227825Stheraven 772227825Stheravenprivate: 773227825Stheraven _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 774227825Stheraven void allocate(size_type __n); 775227825Stheraven void deallocate() _NOEXCEPT; 776227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 777227825Stheraven void __construct_at_end(size_type __n); 778227825Stheraven void __construct_at_end(size_type __n, const_reference __x); 779227825Stheraven template <class _ForwardIterator> 780227825Stheraven typename enable_if 781227825Stheraven < 782227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 783227825Stheraven void 784227825Stheraven >::type 785227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 786227825Stheraven void __move_construct_at_end(pointer __first, pointer __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 800227825Stheraven void __destruct_at_end(const_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 817227825Stheraven __base::__destruct_at_end(__new_last); 818227825Stheraven } 819232950Stheraven template <class _Up> 820232950Stheraven void 821232950Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 822232950Stheraven __push_back_slow_path(_Up&& __x); 823232950Stheraven#else 824232950Stheraven __push_back_slow_path(_Up& __x); 825232950Stheraven#endif 826232950Stheraven#if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 827232950Stheraven template <class... _Args> 828232950Stheraven void 829232950Stheraven __emplace_back_slow_path(_Args&&... __args); 830232950Stheraven#endif 831227825Stheraven}; 832227825Stheraven 833227825Stheraventemplate <class _Tp, class _Allocator> 834227825Stheravenvoid 835227825Stheravenvector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) 836227825Stheraven{ 837232950Stheraven __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_); 838227825Stheraven _VSTD::swap(this->__begin_, __v.__begin_); 839227825Stheraven _VSTD::swap(this->__end_, __v.__end_); 840227825Stheraven _VSTD::swap(this->__end_cap(), __v.__end_cap()); 841227825Stheraven __v.__first_ = __v.__begin_; 842227825Stheraven __invalidate_all_iterators(); 843227825Stheraven} 844227825Stheraven 845227825Stheraventemplate <class _Tp, class _Allocator> 846227825Stheraventypename vector<_Tp, _Allocator>::pointer 847227825Stheravenvector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) 848227825Stheraven{ 849227825Stheraven pointer __r = __v.__begin_; 850232950Stheraven __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_); 851232950Stheraven __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_); 852227825Stheraven _VSTD::swap(this->__begin_, __v.__begin_); 853227825Stheraven _VSTD::swap(this->__end_, __v.__end_); 854227825Stheraven _VSTD::swap(this->__end_cap(), __v.__end_cap()); 855227825Stheraven __v.__first_ = __v.__begin_; 856227825Stheraven __invalidate_all_iterators(); 857227825Stheraven return __r; 858227825Stheraven} 859227825Stheraven 860227825Stheraven// Allocate space for __n objects 861227825Stheraven// throws length_error if __n > max_size() 862227825Stheraven// throws (probably bad_alloc) if memory run out 863227825Stheraven// Precondition: __begin_ == __end_ == __end_cap() == 0 864227825Stheraven// Precondition: __n > 0 865227825Stheraven// Postcondition: capacity() == __n 866227825Stheraven// Postcondition: size() == 0 867227825Stheraventemplate <class _Tp, class _Allocator> 868227825Stheravenvoid 869227825Stheravenvector<_Tp, _Allocator>::allocate(size_type __n) 870227825Stheraven{ 871227825Stheraven if (__n > max_size()) 872227825Stheraven this->__throw_length_error(); 873227825Stheraven this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); 874227825Stheraven this->__end_cap() = this->__begin_ + __n; 875227825Stheraven} 876227825Stheraven 877227825Stheraventemplate <class _Tp, class _Allocator> 878227825Stheravenvoid 879227825Stheravenvector<_Tp, _Allocator>::deallocate() _NOEXCEPT 880227825Stheraven{ 881227825Stheraven if (this->__begin_ != 0) 882227825Stheraven { 883227825Stheraven clear(); 884227825Stheraven __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); 885227825Stheraven this->__begin_ = this->__end_ = this->__end_cap() = 0; 886227825Stheraven } 887227825Stheraven} 888227825Stheraven 889227825Stheraventemplate <class _Tp, class _Allocator> 890227825Stheraventypename vector<_Tp, _Allocator>::size_type 891227825Stheravenvector<_Tp, _Allocator>::max_size() const _NOEXCEPT 892227825Stheraven{ 893227825Stheraven return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always 894227825Stheraven} 895227825Stheraven 896227825Stheraven// Precondition: __new_size > capacity() 897227825Stheraventemplate <class _Tp, class _Allocator> 898227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 899227825Stheraventypename vector<_Tp, _Allocator>::size_type 900227825Stheravenvector<_Tp, _Allocator>::__recommend(size_type __new_size) const 901227825Stheraven{ 902227825Stheraven const size_type __ms = max_size(); 903227825Stheraven if (__new_size > __ms) 904227825Stheraven this->__throw_length_error(); 905227825Stheraven const size_type __cap = capacity(); 906227825Stheraven if (__cap >= __ms / 2) 907227825Stheraven return __ms; 908227825Stheraven return _VSTD::max<size_type>(2*__cap, __new_size); 909227825Stheraven} 910227825Stheraven 911227825Stheraven// Default constructs __n objects starting at __end_ 912227825Stheraven// throws if construction throws 913227825Stheraven// Precondition: __n > 0 914227825Stheraven// Precondition: size() + __n <= capacity() 915227825Stheraven// Postcondition: size() == size() + __n 916227825Stheraventemplate <class _Tp, class _Allocator> 917227825Stheravenvoid 918227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(size_type __n) 919227825Stheraven{ 920227825Stheraven allocator_type& __a = this->__alloc(); 921227825Stheraven do 922227825Stheraven { 923227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 924227825Stheraven ++this->__end_; 925227825Stheraven --__n; 926227825Stheraven } while (__n > 0); 927227825Stheraven} 928227825Stheraven 929227825Stheraven// Copy constructs __n objects starting at __end_ from __x 930227825Stheraven// throws if construction throws 931227825Stheraven// Precondition: __n > 0 932227825Stheraven// Precondition: size() + __n <= capacity() 933227825Stheraven// Postcondition: size() == old size() + __n 934227825Stheraven// Postcondition: [i] == __x for all i in [size() - __n, __n) 935227825Stheraventemplate <class _Tp, class _Allocator> 936227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 937227825Stheravenvoid 938227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 939227825Stheraven{ 940227825Stheraven allocator_type& __a = this->__alloc(); 941227825Stheraven do 942227825Stheraven { 943227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 944227825Stheraven ++this->__end_; 945227825Stheraven --__n; 946227825Stheraven } while (__n > 0); 947227825Stheraven} 948227825Stheraven 949227825Stheraventemplate <class _Tp, class _Allocator> 950227825Stheraventemplate <class _ForwardIterator> 951227825Stheraventypename enable_if 952227825Stheraven< 953227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 954227825Stheraven void 955227825Stheraven>::type 956227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 957227825Stheraven{ 958227825Stheraven allocator_type& __a = this->__alloc(); 959227825Stheraven for (; __first != __last; ++__first) 960227825Stheraven { 961227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 962227825Stheraven ++this->__end_; 963227825Stheraven } 964227825Stheraven} 965227825Stheraven 966227825Stheraventemplate <class _Tp, class _Allocator> 967227825Stheravenvoid 968227825Stheravenvector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last) 969227825Stheraven{ 970227825Stheraven allocator_type& __a = this->__alloc(); 971227825Stheraven for (; __first != __last; ++__first) 972227825Stheraven { 973227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), 974227825Stheraven _VSTD::move(*__first)); 975227825Stheraven ++this->__end_; 976227825Stheraven } 977227825Stheraven} 978227825Stheraven 979227825Stheraven// Default constructs __n objects starting at __end_ 980227825Stheraven// throws if construction throws 981227825Stheraven// Postcondition: size() == size() + __n 982227825Stheraven// Exception safety: strong. 983227825Stheraventemplate <class _Tp, class _Allocator> 984227825Stheravenvoid 985227825Stheravenvector<_Tp, _Allocator>::__append(size_type __n) 986227825Stheraven{ 987227825Stheraven if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 988227825Stheraven this->__construct_at_end(__n); 989227825Stheraven else 990227825Stheraven { 991227825Stheraven allocator_type& __a = this->__alloc(); 992227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 993227825Stheraven __v.__construct_at_end(__n); 994227825Stheraven __swap_out_circular_buffer(__v); 995227825Stheraven } 996227825Stheraven} 997227825Stheraven 998227825Stheraven// Default constructs __n objects starting at __end_ 999227825Stheraven// throws if construction throws 1000227825Stheraven// Postcondition: size() == size() + __n 1001227825Stheraven// Exception safety: strong. 1002227825Stheraventemplate <class _Tp, class _Allocator> 1003227825Stheravenvoid 1004227825Stheravenvector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) 1005227825Stheraven{ 1006227825Stheraven if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 1007227825Stheraven this->__construct_at_end(__n, __x); 1008227825Stheraven else 1009227825Stheraven { 1010227825Stheraven allocator_type& __a = this->__alloc(); 1011227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 1012227825Stheraven __v.__construct_at_end(__n, __x); 1013227825Stheraven __swap_out_circular_buffer(__v); 1014227825Stheraven } 1015227825Stheraven} 1016227825Stheraven 1017227825Stheraventemplate <class _Tp, class _Allocator> 1018227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n) 1019227825Stheraven{ 1020227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1021227825Stheraven __get_db()->__insert_c(this); 1022227825Stheraven#endif 1023227825Stheraven if (__n > 0) 1024227825Stheraven { 1025227825Stheraven allocate(__n); 1026227825Stheraven __construct_at_end(__n); 1027227825Stheraven } 1028227825Stheraven} 1029227825Stheraven 1030227825Stheraventemplate <class _Tp, class _Allocator> 1031227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) 1032227825Stheraven{ 1033227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1034227825Stheraven __get_db()->__insert_c(this); 1035227825Stheraven#endif 1036227825Stheraven if (__n > 0) 1037227825Stheraven { 1038227825Stheraven allocate(__n); 1039227825Stheraven __construct_at_end(__n, __x); 1040227825Stheraven } 1041227825Stheraven} 1042227825Stheraven 1043227825Stheraventemplate <class _Tp, class _Allocator> 1044227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) 1045227825Stheraven : __base(__a) 1046227825Stheraven{ 1047227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1048227825Stheraven __get_db()->__insert_c(this); 1049227825Stheraven#endif 1050227825Stheraven if (__n > 0) 1051227825Stheraven { 1052227825Stheraven allocate(__n); 1053227825Stheraven __construct_at_end(__n, __x); 1054227825Stheraven } 1055227825Stheraven} 1056227825Stheraven 1057227825Stheraventemplate <class _Tp, class _Allocator> 1058227825Stheraventemplate <class _InputIterator> 1059227825Stheravenvector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 1060227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 1061249998Sdim !__is_forward_iterator<_InputIterator>::value && 1062249998Sdim is_constructible< 1063249998Sdim value_type, 1064249998Sdim typename iterator_traits<_InputIterator>::reference>::value>::type*) 1065227825Stheraven{ 1066227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1067227825Stheraven __get_db()->__insert_c(this); 1068227825Stheraven#endif 1069227825Stheraven for (; __first != __last; ++__first) 1070227825Stheraven push_back(*__first); 1071227825Stheraven} 1072227825Stheraven 1073227825Stheraventemplate <class _Tp, class _Allocator> 1074227825Stheraventemplate <class _InputIterator> 1075227825Stheravenvector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 1076227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 1077249998Sdim !__is_forward_iterator<_InputIterator>::value && 1078249998Sdim is_constructible< 1079249998Sdim value_type, 1080249998Sdim typename iterator_traits<_InputIterator>::reference>::value>::type*) 1081227825Stheraven : __base(__a) 1082227825Stheraven{ 1083227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1084227825Stheraven __get_db()->__insert_c(this); 1085227825Stheraven#endif 1086227825Stheraven for (; __first != __last; ++__first) 1087227825Stheraven push_back(*__first); 1088227825Stheraven} 1089227825Stheraven 1090227825Stheraventemplate <class _Tp, class _Allocator> 1091227825Stheraventemplate <class _ForwardIterator> 1092227825Stheravenvector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 1093249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 1094249998Sdim is_constructible< 1095249998Sdim value_type, 1096249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value>::type*) 1097227825Stheraven{ 1098227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1099227825Stheraven __get_db()->__insert_c(this); 1100227825Stheraven#endif 1101227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1102227825Stheraven if (__n > 0) 1103227825Stheraven { 1104227825Stheraven allocate(__n); 1105227825Stheraven __construct_at_end(__first, __last); 1106227825Stheraven } 1107227825Stheraven} 1108227825Stheraven 1109227825Stheraventemplate <class _Tp, class _Allocator> 1110227825Stheraventemplate <class _ForwardIterator> 1111227825Stheravenvector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 1112249998Sdim typename enable_if<__is_forward_iterator<_ForwardIterator>::value && 1113249998Sdim is_constructible< 1114249998Sdim value_type, 1115249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value>::type*) 1116227825Stheraven : __base(__a) 1117227825Stheraven{ 1118227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1119227825Stheraven __get_db()->__insert_c(this); 1120227825Stheraven#endif 1121227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1122227825Stheraven if (__n > 0) 1123227825Stheraven { 1124227825Stheraven allocate(__n); 1125227825Stheraven __construct_at_end(__first, __last); 1126227825Stheraven } 1127227825Stheraven} 1128227825Stheraven 1129227825Stheraventemplate <class _Tp, class _Allocator> 1130227825Stheravenvector<_Tp, _Allocator>::vector(const vector& __x) 1131227825Stheraven : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) 1132227825Stheraven{ 1133227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1134227825Stheraven __get_db()->__insert_c(this); 1135227825Stheraven#endif 1136227825Stheraven size_type __n = __x.size(); 1137227825Stheraven if (__n > 0) 1138227825Stheraven { 1139227825Stheraven allocate(__n); 1140227825Stheraven __construct_at_end(__x.__begin_, __x.__end_); 1141227825Stheraven } 1142227825Stheraven} 1143227825Stheraven 1144227825Stheraventemplate <class _Tp, class _Allocator> 1145227825Stheravenvector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) 1146227825Stheraven : __base(__a) 1147227825Stheraven{ 1148227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1149227825Stheraven __get_db()->__insert_c(this); 1150227825Stheraven#endif 1151227825Stheraven size_type __n = __x.size(); 1152227825Stheraven if (__n > 0) 1153227825Stheraven { 1154227825Stheraven allocate(__n); 1155227825Stheraven __construct_at_end(__x.__begin_, __x.__end_); 1156227825Stheraven } 1157227825Stheraven} 1158227825Stheraven 1159227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1160227825Stheraven 1161227825Stheraventemplate <class _Tp, class _Allocator> 1162227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1163227825Stheravenvector<_Tp, _Allocator>::vector(vector&& __x) 1164227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1165227825Stheraven : __base(_VSTD::move(__x.__alloc())) 1166227825Stheraven{ 1167227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1168227825Stheraven __get_db()->__insert_c(this); 1169227825Stheraven __get_db()->swap(this, &__x); 1170227825Stheraven#endif 1171227825Stheraven this->__begin_ = __x.__begin_; 1172227825Stheraven this->__end_ = __x.__end_; 1173227825Stheraven this->__end_cap() = __x.__end_cap(); 1174227825Stheraven __x.__begin_ = __x.__end_ = __x.__end_cap() = 0; 1175227825Stheraven} 1176227825Stheraven 1177227825Stheraventemplate <class _Tp, class _Allocator> 1178227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1179227825Stheravenvector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) 1180227825Stheraven : __base(__a) 1181227825Stheraven{ 1182227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1183227825Stheraven __get_db()->__insert_c(this); 1184227825Stheraven#endif 1185227825Stheraven if (__a == __x.__alloc()) 1186227825Stheraven { 1187227825Stheraven this->__begin_ = __x.__begin_; 1188227825Stheraven this->__end_ = __x.__end_; 1189227825Stheraven this->__end_cap() = __x.__end_cap(); 1190227825Stheraven __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1191227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1192227825Stheraven __get_db()->swap(this, &__x); 1193227825Stheraven#endif 1194227825Stheraven } 1195227825Stheraven else 1196227825Stheraven { 1197232950Stheraven typedef move_iterator<iterator> _Ip; 1198232950Stheraven assign(_Ip(__x.begin()), _Ip(__x.end())); 1199227825Stheraven } 1200227825Stheraven} 1201227825Stheraven 1202227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1203227825Stheraven 1204227825Stheraventemplate <class _Tp, class _Allocator> 1205227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1206227825Stheravenvector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) 1207227825Stheraven{ 1208227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1209227825Stheraven __get_db()->__insert_c(this); 1210227825Stheraven#endif 1211227825Stheraven if (__il.size() > 0) 1212227825Stheraven { 1213227825Stheraven allocate(__il.size()); 1214227825Stheraven __construct_at_end(__il.begin(), __il.end()); 1215227825Stheraven } 1216227825Stheraven} 1217227825Stheraven 1218227825Stheraventemplate <class _Tp, class _Allocator> 1219227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1220227825Stheravenvector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 1221227825Stheraven : __base(__a) 1222227825Stheraven{ 1223227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1224227825Stheraven __get_db()->__insert_c(this); 1225227825Stheraven#endif 1226227825Stheraven if (__il.size() > 0) 1227227825Stheraven { 1228227825Stheraven allocate(__il.size()); 1229227825Stheraven __construct_at_end(__il.begin(), __il.end()); 1230227825Stheraven } 1231227825Stheraven} 1232227825Stheraven 1233227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1234227825Stheraven 1235227825Stheraventemplate <class _Tp, class _Allocator> 1236227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1237227825Stheravenvector<_Tp, _Allocator>& 1238227825Stheravenvector<_Tp, _Allocator>::operator=(vector&& __x) 1239227825Stheraven _NOEXCEPT_( 1240227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 1241227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 1242227825Stheraven{ 1243227825Stheraven __move_assign(__x, integral_constant<bool, 1244227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>()); 1245227825Stheraven return *this; 1246227825Stheraven} 1247227825Stheraven 1248227825Stheraventemplate <class _Tp, class _Allocator> 1249227825Stheravenvoid 1250227825Stheravenvector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) 1251227825Stheraven{ 1252227825Stheraven if (__base::__alloc() != __c.__alloc()) 1253227825Stheraven { 1254232950Stheraven typedef move_iterator<iterator> _Ip; 1255232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1256227825Stheraven } 1257227825Stheraven else 1258227825Stheraven __move_assign(__c, true_type()); 1259227825Stheraven} 1260227825Stheraven 1261227825Stheraventemplate <class _Tp, class _Allocator> 1262227825Stheravenvoid 1263227825Stheravenvector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) 1264227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1265227825Stheraven{ 1266227825Stheraven deallocate(); 1267227825Stheraven this->__begin_ = __c.__begin_; 1268227825Stheraven this->__end_ = __c.__end_; 1269227825Stheraven this->__end_cap() = __c.__end_cap(); 1270227825Stheraven __base::__move_assign_alloc(__c); 1271227825Stheraven __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 1272227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1273227825Stheraven __get_db()->swap(this, &__c); 1274227825Stheraven#endif 1275227825Stheraven} 1276227825Stheraven 1277227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1278227825Stheraven 1279227825Stheraventemplate <class _Tp, class _Allocator> 1280227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1281227825Stheravenvector<_Tp, _Allocator>& 1282227825Stheravenvector<_Tp, _Allocator>::operator=(const vector& __x) 1283227825Stheraven{ 1284227825Stheraven if (this != &__x) 1285227825Stheraven { 1286227825Stheraven __base::__copy_assign_alloc(__x); 1287227825Stheraven assign(__x.__begin_, __x.__end_); 1288227825Stheraven } 1289227825Stheraven return *this; 1290227825Stheraven} 1291227825Stheraven 1292227825Stheraventemplate <class _Tp, class _Allocator> 1293227825Stheraventemplate <class _InputIterator> 1294227825Stheraventypename enable_if 1295227825Stheraven< 1296227825Stheraven __is_input_iterator <_InputIterator>::value && 1297249998Sdim !__is_forward_iterator<_InputIterator>::value && 1298249998Sdim is_constructible< 1299249998Sdim _Tp, 1300249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 1301227825Stheraven void 1302227825Stheraven>::type 1303227825Stheravenvector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 1304227825Stheraven{ 1305227825Stheraven clear(); 1306227825Stheraven for (; __first != __last; ++__first) 1307227825Stheraven push_back(*__first); 1308227825Stheraven} 1309227825Stheraven 1310227825Stheraventemplate <class _Tp, class _Allocator> 1311227825Stheraventemplate <class _ForwardIterator> 1312227825Stheraventypename enable_if 1313227825Stheraven< 1314249998Sdim __is_forward_iterator<_ForwardIterator>::value && 1315249998Sdim is_constructible< 1316249998Sdim _Tp, 1317249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 1318227825Stheraven void 1319227825Stheraven>::type 1320227825Stheravenvector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 1321227825Stheraven{ 1322227825Stheraven typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last); 1323227825Stheraven if (static_cast<size_type>(__new_size) <= capacity()) 1324227825Stheraven { 1325227825Stheraven _ForwardIterator __mid = __last; 1326227825Stheraven bool __growing = false; 1327227825Stheraven if (static_cast<size_type>(__new_size) > size()) 1328227825Stheraven { 1329227825Stheraven __growing = true; 1330227825Stheraven __mid = __first; 1331227825Stheraven _VSTD::advance(__mid, size()); 1332227825Stheraven } 1333227825Stheraven pointer __m = _VSTD::copy(__first, __mid, this->__begin_); 1334227825Stheraven if (__growing) 1335227825Stheraven __construct_at_end(__mid, __last); 1336227825Stheraven else 1337227825Stheraven this->__destruct_at_end(__m); 1338227825Stheraven } 1339227825Stheraven else 1340227825Stheraven { 1341227825Stheraven deallocate(); 1342227825Stheraven allocate(__recommend(static_cast<size_type>(__new_size))); 1343227825Stheraven __construct_at_end(__first, __last); 1344227825Stheraven } 1345227825Stheraven} 1346227825Stheraven 1347227825Stheraventemplate <class _Tp, class _Allocator> 1348227825Stheravenvoid 1349227825Stheravenvector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) 1350227825Stheraven{ 1351227825Stheraven if (__n <= capacity()) 1352227825Stheraven { 1353227825Stheraven size_type __s = size(); 1354227825Stheraven _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u); 1355227825Stheraven if (__n > __s) 1356227825Stheraven __construct_at_end(__n - __s, __u); 1357227825Stheraven else 1358227825Stheraven this->__destruct_at_end(this->__begin_ + __n); 1359227825Stheraven } 1360227825Stheraven else 1361227825Stheraven { 1362227825Stheraven deallocate(); 1363227825Stheraven allocate(__recommend(static_cast<size_type>(__n))); 1364227825Stheraven __construct_at_end(__n, __u); 1365227825Stheraven } 1366227825Stheraven} 1367227825Stheraven 1368227825Stheraventemplate <class _Tp, class _Allocator> 1369227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1370227825Stheraventypename vector<_Tp, _Allocator>::iterator 1371227825Stheravenvector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT 1372227825Stheraven{ 1373227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1374227825Stheraven return iterator(this, __p); 1375227825Stheraven#else 1376227825Stheraven return iterator(__p); 1377227825Stheraven#endif 1378227825Stheraven} 1379227825Stheraven 1380227825Stheraventemplate <class _Tp, class _Allocator> 1381227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1382227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1383227825Stheravenvector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT 1384227825Stheraven{ 1385227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1386227825Stheraven return const_iterator(this, __p); 1387227825Stheraven#else 1388227825Stheraven return const_iterator(__p); 1389227825Stheraven#endif 1390227825Stheraven} 1391227825Stheraven 1392227825Stheraventemplate <class _Tp, class _Allocator> 1393227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1394227825Stheraventypename vector<_Tp, _Allocator>::iterator 1395227825Stheravenvector<_Tp, _Allocator>::begin() _NOEXCEPT 1396227825Stheraven{ 1397227825Stheraven return __make_iter(this->__begin_); 1398227825Stheraven} 1399227825Stheraven 1400227825Stheraventemplate <class _Tp, class _Allocator> 1401227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1402227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1403227825Stheravenvector<_Tp, _Allocator>::begin() const _NOEXCEPT 1404227825Stheraven{ 1405227825Stheraven return __make_iter(this->__begin_); 1406227825Stheraven} 1407227825Stheraven 1408227825Stheraventemplate <class _Tp, class _Allocator> 1409227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1410227825Stheraventypename vector<_Tp, _Allocator>::iterator 1411227825Stheravenvector<_Tp, _Allocator>::end() _NOEXCEPT 1412227825Stheraven{ 1413227825Stheraven return __make_iter(this->__end_); 1414227825Stheraven} 1415227825Stheraven 1416227825Stheraventemplate <class _Tp, class _Allocator> 1417227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1418227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1419227825Stheravenvector<_Tp, _Allocator>::end() const _NOEXCEPT 1420227825Stheraven{ 1421227825Stheraven return __make_iter(this->__end_); 1422227825Stheraven} 1423227825Stheraven 1424227825Stheraventemplate <class _Tp, class _Allocator> 1425227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1426227825Stheraventypename vector<_Tp, _Allocator>::reference 1427227825Stheravenvector<_Tp, _Allocator>::operator[](size_type __n) 1428227825Stheraven{ 1429227825Stheraven _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1430227825Stheraven return this->__begin_[__n]; 1431227825Stheraven} 1432227825Stheraven 1433227825Stheraventemplate <class _Tp, class _Allocator> 1434227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1435227825Stheraventypename vector<_Tp, _Allocator>::const_reference 1436227825Stheravenvector<_Tp, _Allocator>::operator[](size_type __n) const 1437227825Stheraven{ 1438227825Stheraven _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1439227825Stheraven return this->__begin_[__n]; 1440227825Stheraven} 1441227825Stheraven 1442227825Stheraventemplate <class _Tp, class _Allocator> 1443227825Stheraventypename vector<_Tp, _Allocator>::reference 1444227825Stheravenvector<_Tp, _Allocator>::at(size_type __n) 1445227825Stheraven{ 1446227825Stheraven if (__n >= size()) 1447227825Stheraven this->__throw_out_of_range(); 1448227825Stheraven return this->__begin_[__n]; 1449227825Stheraven} 1450227825Stheraven 1451227825Stheraventemplate <class _Tp, class _Allocator> 1452227825Stheraventypename vector<_Tp, _Allocator>::const_reference 1453227825Stheravenvector<_Tp, _Allocator>::at(size_type __n) const 1454227825Stheraven{ 1455227825Stheraven if (__n >= size()) 1456227825Stheraven this->__throw_out_of_range(); 1457227825Stheraven return this->__begin_[__n]; 1458227825Stheraven} 1459227825Stheraven 1460227825Stheraventemplate <class _Tp, class _Allocator> 1461227825Stheravenvoid 1462227825Stheravenvector<_Tp, _Allocator>::reserve(size_type __n) 1463227825Stheraven{ 1464227825Stheraven if (__n > capacity()) 1465227825Stheraven { 1466227825Stheraven allocator_type& __a = this->__alloc(); 1467227825Stheraven __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); 1468227825Stheraven __swap_out_circular_buffer(__v); 1469227825Stheraven } 1470227825Stheraven} 1471227825Stheraven 1472227825Stheraventemplate <class _Tp, class _Allocator> 1473227825Stheravenvoid 1474227825Stheravenvector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1475227825Stheraven{ 1476227825Stheraven if (capacity() > size()) 1477227825Stheraven { 1478227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1479227825Stheraven try 1480227825Stheraven { 1481227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1482227825Stheraven allocator_type& __a = this->__alloc(); 1483227825Stheraven __split_buffer<value_type, allocator_type&> __v(size(), size(), __a); 1484227825Stheraven __swap_out_circular_buffer(__v); 1485227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1486227825Stheraven } 1487227825Stheraven catch (...) 1488227825Stheraven { 1489227825Stheraven } 1490227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1491227825Stheraven } 1492227825Stheraven} 1493227825Stheraven 1494227825Stheraventemplate <class _Tp, class _Allocator> 1495232950Stheraventemplate <class _Up> 1496227825Stheravenvoid 1497232950Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1498232950Stheravenvector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) 1499232950Stheraven#else 1500232950Stheravenvector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x) 1501232950Stheraven#endif 1502232950Stheraven{ 1503232950Stheraven allocator_type& __a = this->__alloc(); 1504232950Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1505232950Stheraven // __v.push_back(_VSTD::forward<_Up>(__x)); 1506246487Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x)); 1507246487Stheraven __v.__end_++; 1508232950Stheraven __swap_out_circular_buffer(__v); 1509232950Stheraven} 1510232950Stheraven 1511232950Stheraventemplate <class _Tp, class _Allocator> 1512232950Stheraven_LIBCPP_INLINE_VISIBILITY inline 1513232950Stheravenvoid 1514227825Stheravenvector<_Tp, _Allocator>::push_back(const_reference __x) 1515227825Stheraven{ 1516232950Stheraven if (this->__end_ != this->__end_cap()) 1517227825Stheraven { 1518227825Stheraven __alloc_traits::construct(this->__alloc(), 1519227825Stheraven _VSTD::__to_raw_pointer(this->__end_), __x); 1520227825Stheraven ++this->__end_; 1521227825Stheraven } 1522227825Stheraven else 1523232950Stheraven __push_back_slow_path(__x); 1524227825Stheraven} 1525227825Stheraven 1526227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1527227825Stheraven 1528227825Stheraventemplate <class _Tp, class _Allocator> 1529232950Stheraven_LIBCPP_INLINE_VISIBILITY inline 1530227825Stheravenvoid 1531227825Stheravenvector<_Tp, _Allocator>::push_back(value_type&& __x) 1532227825Stheraven{ 1533227825Stheraven if (this->__end_ < this->__end_cap()) 1534227825Stheraven { 1535227825Stheraven __alloc_traits::construct(this->__alloc(), 1536227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1537227825Stheraven _VSTD::move(__x)); 1538227825Stheraven ++this->__end_; 1539227825Stheraven } 1540227825Stheraven else 1541232950Stheraven __push_back_slow_path(_VSTD::move(__x)); 1542227825Stheraven} 1543227825Stheraven 1544227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1545227825Stheraven 1546227825Stheraventemplate <class _Tp, class _Allocator> 1547227825Stheraventemplate <class... _Args> 1548227825Stheravenvoid 1549232950Stheravenvector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) 1550232950Stheraven{ 1551232950Stheraven allocator_type& __a = this->__alloc(); 1552232950Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1553232950Stheraven// __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1554246487Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...); 1555246487Stheraven __v.__end_++; 1556232950Stheraven __swap_out_circular_buffer(__v); 1557232950Stheraven} 1558232950Stheraven 1559232950Stheraventemplate <class _Tp, class _Allocator> 1560232950Stheraventemplate <class... _Args> 1561232950Stheraven_LIBCPP_INLINE_VISIBILITY inline 1562232950Stheravenvoid 1563227825Stheravenvector<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1564227825Stheraven{ 1565227825Stheraven if (this->__end_ < this->__end_cap()) 1566227825Stheraven { 1567227825Stheraven __alloc_traits::construct(this->__alloc(), 1568227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1569227825Stheraven _VSTD::forward<_Args>(__args)...); 1570227825Stheraven ++this->__end_; 1571227825Stheraven } 1572227825Stheraven else 1573232950Stheraven __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); 1574227825Stheraven} 1575227825Stheraven 1576227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1577227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1578227825Stheraven 1579227825Stheraventemplate <class _Tp, class _Allocator> 1580227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1581227825Stheravenvoid 1582227825Stheravenvector<_Tp, _Allocator>::pop_back() 1583227825Stheraven{ 1584227825Stheraven _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector"); 1585227825Stheraven this->__destruct_at_end(this->__end_ - 1); 1586227825Stheraven} 1587227825Stheraven 1588227825Stheraventemplate <class _Tp, class _Allocator> 1589227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1590227825Stheraventypename vector<_Tp, _Allocator>::iterator 1591227825Stheravenvector<_Tp, _Allocator>::erase(const_iterator __position) 1592227825Stheraven{ 1593227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1594227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1595227825Stheraven "vector::erase(iterator) called with an iterator not" 1596227825Stheraven " referring to this vector"); 1597227825Stheraven#endif 1598249998Sdim _LIBCPP_ASSERT(__position != end(), 1599249998Sdim "vector::erase(iterator) called with a non-dereferenceable iterator"); 1600227825Stheraven pointer __p = const_cast<pointer>(&*__position); 1601227825Stheraven iterator __r = __make_iter(__p); 1602227825Stheraven this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); 1603227825Stheraven return __r; 1604227825Stheraven} 1605227825Stheraven 1606227825Stheraventemplate <class _Tp, class _Allocator> 1607227825Stheraventypename vector<_Tp, _Allocator>::iterator 1608227825Stheravenvector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) 1609227825Stheraven{ 1610227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1611227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 1612227825Stheraven "vector::erase(iterator, iterator) called with an iterator not" 1613227825Stheraven " referring to this vector"); 1614227825Stheraven#endif 1615227825Stheraven _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range"); 1616227825Stheraven pointer __p = this->__begin_ + (__first - begin()); 1617227825Stheraven iterator __r = __make_iter(__p); 1618249998Sdim if (__first != __last) 1619249998Sdim this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p)); 1620227825Stheraven return __r; 1621227825Stheraven} 1622227825Stheraven 1623227825Stheraventemplate <class _Tp, class _Allocator> 1624227825Stheravenvoid 1625227825Stheravenvector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) 1626227825Stheraven{ 1627227825Stheraven pointer __old_last = this->__end_; 1628227825Stheraven difference_type __n = __old_last - __to; 1629227825Stheraven for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_) 1630227825Stheraven __alloc_traits::construct(this->__alloc(), 1631227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1632227825Stheraven _VSTD::move(*__i)); 1633227825Stheraven _VSTD::move_backward(__from_s, __from_s + __n, __old_last); 1634227825Stheraven} 1635227825Stheraven 1636227825Stheraventemplate <class _Tp, class _Allocator> 1637227825Stheraventypename vector<_Tp, _Allocator>::iterator 1638227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) 1639227825Stheraven{ 1640227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1641227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1642227825Stheraven "vector::insert(iterator, x) called with an iterator not" 1643227825Stheraven " referring to this vector"); 1644227825Stheraven#endif 1645227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1646227825Stheraven if (this->__end_ < this->__end_cap()) 1647227825Stheraven { 1648227825Stheraven if (__p == this->__end_) 1649227825Stheraven { 1650227825Stheraven __alloc_traits::construct(this->__alloc(), 1651227825Stheraven _VSTD::__to_raw_pointer(this->__end_), __x); 1652227825Stheraven ++this->__end_; 1653227825Stheraven } 1654227825Stheraven else 1655227825Stheraven { 1656227825Stheraven __move_range(__p, this->__end_, __p + 1); 1657227825Stheraven const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1658227825Stheraven if (__p <= __xr && __xr < this->__end_) 1659227825Stheraven ++__xr; 1660227825Stheraven *__p = *__xr; 1661227825Stheraven } 1662227825Stheraven } 1663227825Stheraven else 1664227825Stheraven { 1665227825Stheraven allocator_type& __a = this->__alloc(); 1666227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1667227825Stheraven __v.push_back(__x); 1668227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1669227825Stheraven } 1670227825Stheraven return __make_iter(__p); 1671227825Stheraven} 1672227825Stheraven 1673227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1674227825Stheraven 1675227825Stheraventemplate <class _Tp, class _Allocator> 1676227825Stheraventypename vector<_Tp, _Allocator>::iterator 1677227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) 1678227825Stheraven{ 1679227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1680227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1681227825Stheraven "vector::insert(iterator, x) called with an iterator not" 1682227825Stheraven " referring to this vector"); 1683227825Stheraven#endif 1684227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1685227825Stheraven if (this->__end_ < this->__end_cap()) 1686227825Stheraven { 1687227825Stheraven if (__p == this->__end_) 1688227825Stheraven { 1689227825Stheraven __alloc_traits::construct(this->__alloc(), 1690227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1691227825Stheraven _VSTD::move(__x)); 1692227825Stheraven ++this->__end_; 1693227825Stheraven } 1694227825Stheraven else 1695227825Stheraven { 1696227825Stheraven __move_range(__p, this->__end_, __p + 1); 1697227825Stheraven *__p = _VSTD::move(__x); 1698227825Stheraven } 1699227825Stheraven } 1700227825Stheraven else 1701227825Stheraven { 1702227825Stheraven allocator_type& __a = this->__alloc(); 1703227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1704227825Stheraven __v.push_back(_VSTD::move(__x)); 1705227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1706227825Stheraven } 1707227825Stheraven return __make_iter(__p); 1708227825Stheraven} 1709227825Stheraven 1710227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1711227825Stheraven 1712227825Stheraventemplate <class _Tp, class _Allocator> 1713227825Stheraventemplate <class... _Args> 1714227825Stheraventypename vector<_Tp, _Allocator>::iterator 1715227825Stheravenvector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) 1716227825Stheraven{ 1717227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1718227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1719227825Stheraven "vector::emplace(iterator, x) called with an iterator not" 1720227825Stheraven " referring to this vector"); 1721227825Stheraven#endif 1722227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1723227825Stheraven if (this->__end_ < this->__end_cap()) 1724227825Stheraven { 1725227825Stheraven if (__p == this->__end_) 1726227825Stheraven { 1727227825Stheraven __alloc_traits::construct(this->__alloc(), 1728227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1729227825Stheraven _VSTD::forward<_Args>(__args)...); 1730227825Stheraven ++this->__end_; 1731227825Stheraven } 1732227825Stheraven else 1733227825Stheraven { 1734241903Sdim value_type __tmp(_VSTD::forward<_Args>(__args)...); 1735227825Stheraven __move_range(__p, this->__end_, __p + 1); 1736241903Sdim *__p = _VSTD::move(__tmp); 1737227825Stheraven } 1738227825Stheraven } 1739227825Stheraven else 1740227825Stheraven { 1741227825Stheraven allocator_type& __a = this->__alloc(); 1742227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1743227825Stheraven __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1744227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1745227825Stheraven } 1746227825Stheraven return __make_iter(__p); 1747227825Stheraven} 1748227825Stheraven 1749227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1750227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1751227825Stheraven 1752227825Stheraventemplate <class _Tp, class _Allocator> 1753227825Stheraventypename vector<_Tp, _Allocator>::iterator 1754227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) 1755227825Stheraven{ 1756227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1757227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1758227825Stheraven "vector::insert(iterator, n, x) called with an iterator not" 1759227825Stheraven " referring to this vector"); 1760227825Stheraven#endif 1761227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1762227825Stheraven if (__n > 0) 1763227825Stheraven { 1764227825Stheraven if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_)) 1765227825Stheraven { 1766227825Stheraven size_type __old_n = __n; 1767227825Stheraven pointer __old_last = this->__end_; 1768227825Stheraven if (__n > static_cast<size_type>(this->__end_ - __p)) 1769227825Stheraven { 1770227825Stheraven size_type __cx = __n - (this->__end_ - __p); 1771227825Stheraven __construct_at_end(__cx, __x); 1772227825Stheraven __n -= __cx; 1773227825Stheraven } 1774227825Stheraven if (__n > 0) 1775227825Stheraven { 1776227825Stheraven __move_range(__p, __old_last, __p + __old_n); 1777227825Stheraven const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1778227825Stheraven if (__p <= __xr && __xr < this->__end_) 1779227825Stheraven __xr += __old_n; 1780227825Stheraven _VSTD::fill_n(__p, __n, *__xr); 1781227825Stheraven } 1782227825Stheraven } 1783227825Stheraven else 1784227825Stheraven { 1785227825Stheraven allocator_type& __a = this->__alloc(); 1786227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1787227825Stheraven __v.__construct_at_end(__n, __x); 1788227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1789227825Stheraven } 1790227825Stheraven } 1791227825Stheraven return __make_iter(__p); 1792227825Stheraven} 1793227825Stheraven 1794227825Stheraventemplate <class _Tp, class _Allocator> 1795227825Stheraventemplate <class _InputIterator> 1796227825Stheraventypename enable_if 1797227825Stheraven< 1798227825Stheraven __is_input_iterator <_InputIterator>::value && 1799249998Sdim !__is_forward_iterator<_InputIterator>::value && 1800249998Sdim is_constructible< 1801249998Sdim _Tp, 1802249998Sdim typename iterator_traits<_InputIterator>::reference>::value, 1803227825Stheraven typename vector<_Tp, _Allocator>::iterator 1804227825Stheraven>::type 1805227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 1806227825Stheraven{ 1807227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1808227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1809227825Stheraven "vector::insert(iterator, range) called with an iterator not" 1810227825Stheraven " referring to this vector"); 1811227825Stheraven#endif 1812227825Stheraven difference_type __off = __position - begin(); 1813227825Stheraven pointer __p = this->__begin_ + __off; 1814227825Stheraven allocator_type& __a = this->__alloc(); 1815227825Stheraven pointer __old_last = this->__end_; 1816227825Stheraven for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) 1817227825Stheraven { 1818227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), 1819227825Stheraven *__first); 1820227825Stheraven ++this->__end_; 1821227825Stheraven } 1822227825Stheraven __split_buffer<value_type, allocator_type&> __v(__a); 1823227825Stheraven if (__first != __last) 1824227825Stheraven { 1825227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1826227825Stheraven try 1827227825Stheraven { 1828227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1829227825Stheraven __v.__construct_at_end(__first, __last); 1830227825Stheraven difference_type __old_size = __old_last - this->__begin_; 1831227825Stheraven difference_type __old_p = __p - this->__begin_; 1832227825Stheraven reserve(__recommend(size() + __v.size())); 1833227825Stheraven __p = this->__begin_ + __old_p; 1834227825Stheraven __old_last = this->__begin_ + __old_size; 1835227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1836227825Stheraven } 1837227825Stheraven catch (...) 1838227825Stheraven { 1839227825Stheraven erase(__make_iter(__old_last), end()); 1840227825Stheraven throw; 1841227825Stheraven } 1842227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1843227825Stheraven } 1844227825Stheraven __p = _VSTD::rotate(__p, __old_last, this->__end_); 1845227825Stheraven insert(__make_iter(__p), make_move_iterator(__v.begin()), 1846227825Stheraven make_move_iterator(__v.end())); 1847227825Stheraven return begin() + __off; 1848227825Stheraven} 1849227825Stheraven 1850227825Stheraventemplate <class _Tp, class _Allocator> 1851227825Stheraventemplate <class _ForwardIterator> 1852227825Stheraventypename enable_if 1853227825Stheraven< 1854249998Sdim __is_forward_iterator<_ForwardIterator>::value && 1855249998Sdim is_constructible< 1856249998Sdim _Tp, 1857249998Sdim typename iterator_traits<_ForwardIterator>::reference>::value, 1858227825Stheraven typename vector<_Tp, _Allocator>::iterator 1859227825Stheraven>::type 1860227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 1861227825Stheraven{ 1862227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1863227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1864227825Stheraven "vector::insert(iterator, range) called with an iterator not" 1865227825Stheraven " referring to this vector"); 1866227825Stheraven#endif 1867227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1868227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 1869227825Stheraven if (__n > 0) 1870227825Stheraven { 1871227825Stheraven if (__n <= this->__end_cap() - this->__end_) 1872227825Stheraven { 1873227825Stheraven size_type __old_n = __n; 1874227825Stheraven pointer __old_last = this->__end_; 1875227825Stheraven _ForwardIterator __m = __last; 1876227825Stheraven difference_type __dx = this->__end_ - __p; 1877227825Stheraven if (__n > __dx) 1878227825Stheraven { 1879227825Stheraven __m = __first; 1880227825Stheraven _VSTD::advance(__m, this->__end_ - __p); 1881227825Stheraven __construct_at_end(__m, __last); 1882227825Stheraven __n = __dx; 1883227825Stheraven } 1884227825Stheraven if (__n > 0) 1885227825Stheraven { 1886227825Stheraven __move_range(__p, __old_last, __p + __old_n); 1887227825Stheraven _VSTD::copy(__first, __m, __p); 1888227825Stheraven } 1889227825Stheraven } 1890227825Stheraven else 1891227825Stheraven { 1892227825Stheraven allocator_type& __a = this->__alloc(); 1893227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1894227825Stheraven __v.__construct_at_end(__first, __last); 1895227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1896227825Stheraven } 1897227825Stheraven } 1898227825Stheraven return __make_iter(__p); 1899227825Stheraven} 1900227825Stheraven 1901227825Stheraventemplate <class _Tp, class _Allocator> 1902227825Stheravenvoid 1903227825Stheravenvector<_Tp, _Allocator>::resize(size_type __sz) 1904227825Stheraven{ 1905227825Stheraven size_type __cs = size(); 1906227825Stheraven if (__cs < __sz) 1907227825Stheraven this->__append(__sz - __cs); 1908227825Stheraven else if (__cs > __sz) 1909227825Stheraven this->__destruct_at_end(this->__begin_ + __sz); 1910227825Stheraven} 1911227825Stheraven 1912227825Stheraventemplate <class _Tp, class _Allocator> 1913227825Stheravenvoid 1914227825Stheravenvector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) 1915227825Stheraven{ 1916227825Stheraven size_type __cs = size(); 1917227825Stheraven if (__cs < __sz) 1918227825Stheraven this->__append(__sz - __cs, __x); 1919227825Stheraven else if (__cs > __sz) 1920227825Stheraven this->__destruct_at_end(this->__begin_ + __sz); 1921227825Stheraven} 1922227825Stheraven 1923227825Stheraventemplate <class _Tp, class _Allocator> 1924227825Stheravenvoid 1925227825Stheravenvector<_Tp, _Allocator>::swap(vector& __x) 1926227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1927227825Stheraven __is_nothrow_swappable<allocator_type>::value) 1928227825Stheraven{ 1929227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 1930227825Stheraven this->__alloc() == __x.__alloc(), 1931227825Stheraven "vector::swap: Either propagate_on_container_swap must be true" 1932227825Stheraven " or the allocators must compare equal"); 1933227825Stheraven _VSTD::swap(this->__begin_, __x.__begin_); 1934227825Stheraven _VSTD::swap(this->__end_, __x.__end_); 1935227825Stheraven _VSTD::swap(this->__end_cap(), __x.__end_cap()); 1936227825Stheraven __base::__swap_alloc(this->__alloc(), __x.__alloc()); 1937227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1938227825Stheraven __get_db()->swap(this, &__x); 1939227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1940227825Stheraven} 1941227825Stheraven 1942227825Stheraventemplate <class _Tp, class _Allocator> 1943227825Stheravenbool 1944227825Stheravenvector<_Tp, _Allocator>::__invariants() const 1945227825Stheraven{ 1946227825Stheraven if (this->__begin_ == 0) 1947227825Stheraven { 1948227825Stheraven if (this->__end_ != 0 || this->__end_cap() != 0) 1949227825Stheraven return false; 1950227825Stheraven } 1951227825Stheraven else 1952227825Stheraven { 1953227825Stheraven if (this->__begin_ > this->__end_) 1954227825Stheraven return false; 1955227825Stheraven if (this->__begin_ == this->__end_cap()) 1956227825Stheraven return false; 1957227825Stheraven if (this->__end_ > this->__end_cap()) 1958227825Stheraven return false; 1959227825Stheraven } 1960227825Stheraven return true; 1961227825Stheraven} 1962227825Stheraven 1963227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1964227825Stheraven 1965227825Stheraventemplate <class _Tp, class _Allocator> 1966227825Stheravenbool 1967227825Stheravenvector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const 1968227825Stheraven{ 1969227825Stheraven return this->__begin_ <= __i->base() && __i->base() < this->__end_; 1970227825Stheraven} 1971227825Stheraven 1972227825Stheraventemplate <class _Tp, class _Allocator> 1973227825Stheravenbool 1974227825Stheravenvector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const 1975227825Stheraven{ 1976227825Stheraven return this->__begin_ < __i->base() && __i->base() <= this->__end_; 1977227825Stheraven} 1978227825Stheraven 1979227825Stheraventemplate <class _Tp, class _Allocator> 1980227825Stheravenbool 1981227825Stheravenvector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const 1982227825Stheraven{ 1983227825Stheraven const_pointer __p = __i->base() + __n; 1984227825Stheraven return this->__begin_ <= __p && __p <= this->__end_; 1985227825Stheraven} 1986227825Stheraven 1987227825Stheraventemplate <class _Tp, class _Allocator> 1988227825Stheravenbool 1989227825Stheravenvector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1990227825Stheraven{ 1991227825Stheraven const_pointer __p = __i->base() + __n; 1992227825Stheraven return this->__begin_ <= __p && __p < this->__end_; 1993227825Stheraven} 1994227825Stheraven 1995227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1996227825Stheraven 1997227825Stheraventemplate <class _Tp, class _Allocator> 1998227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1999227825Stheravenvoid 2000227825Stheravenvector<_Tp, _Allocator>::__invalidate_all_iterators() 2001227825Stheraven{ 2002227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 2003227825Stheraven __get_db()->__invalidate_all(this); 2004227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 2005227825Stheraven} 2006227825Stheraven 2007227825Stheraven// vector<bool> 2008227825Stheraven 2009227825Stheraventemplate <class _Allocator> class vector<bool, _Allocator>; 2010227825Stheraven 2011227825Stheraventemplate <class _Allocator> struct hash<vector<bool, _Allocator> >; 2012227825Stheraven 2013227825Stheraventemplate <class _Allocator> 2014227825Stheravenstruct __has_storage_type<vector<bool, _Allocator> > 2015227825Stheraven{ 2016227825Stheraven static const bool value = true; 2017227825Stheraven}; 2018227825Stheraven 2019227825Stheraventemplate <class _Allocator> 2020249998Sdimclass _LIBCPP_TYPE_VIS vector<bool, _Allocator> 2021227825Stheraven : private __vector_base_common<true> 2022227825Stheraven{ 2023227825Stheravenpublic: 2024227825Stheraven typedef vector __self; 2025227825Stheraven typedef bool value_type; 2026227825Stheraven typedef _Allocator allocator_type; 2027227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 2028227825Stheraven typedef typename __alloc_traits::size_type size_type; 2029227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 2030241903Sdim typedef size_type __storage_type; 2031227825Stheraven typedef __bit_iterator<vector, false> pointer; 2032227825Stheraven typedef __bit_iterator<vector, true> const_pointer; 2033227825Stheraven#ifdef _LIBCPP_DEBUG 2034227825Stheraven typedef __debug_iter<vector, pointer> iterator; 2035227825Stheraven typedef __debug_iter<vector, const_pointer> const_iterator; 2036227825Stheraven 2037227825Stheraven friend class __debug_iter<vector, pointer>; 2038227825Stheraven friend class __debug_iter<vector, const_pointer>; 2039227825Stheraven 2040227825Stheraven pair<iterator*, const_iterator*> __iterator_list_; 2041227825Stheraven 2042227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;} 2043227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;} 2044227825Stheraven#else // _LIBCPP_DEBUG 2045227825Stheraven typedef pointer iterator; 2046227825Stheraven typedef const_pointer const_iterator; 2047227825Stheraven#endif // _LIBCPP_DEBUG 2048227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 2049227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 2050227825Stheraven 2051227825Stheravenprivate: 2052227825Stheraven typedef typename __alloc_traits::template 2053227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 2054227825Stheraven rebind_alloc<__storage_type> 2055227825Stheraven#else 2056227825Stheraven rebind_alloc<__storage_type>::other 2057227825Stheraven#endif 2058227825Stheraven __storage_allocator; 2059227825Stheraven typedef allocator_traits<__storage_allocator> __storage_traits; 2060227825Stheraven typedef typename __storage_traits::pointer __storage_pointer; 2061227825Stheraven typedef typename __storage_traits::const_pointer __const_storage_pointer; 2062227825Stheraven 2063227825Stheraven __storage_pointer __begin_; 2064227825Stheraven size_type __size_; 2065227825Stheraven __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 2066227825Stheravenpublic: 2067227825Stheraven typedef __bit_reference<vector> reference; 2068227825Stheraven typedef __bit_const_reference<vector> const_reference; 2069227825Stheravenprivate: 2070227825Stheraven _LIBCPP_INLINE_VISIBILITY 2071227825Stheraven size_type& __cap() _NOEXCEPT 2072227825Stheraven {return __cap_alloc_.first();} 2073227825Stheraven _LIBCPP_INLINE_VISIBILITY 2074227825Stheraven const size_type& __cap() const _NOEXCEPT 2075227825Stheraven {return __cap_alloc_.first();} 2076227825Stheraven _LIBCPP_INLINE_VISIBILITY 2077227825Stheraven __storage_allocator& __alloc() _NOEXCEPT 2078227825Stheraven {return __cap_alloc_.second();} 2079227825Stheraven _LIBCPP_INLINE_VISIBILITY 2080227825Stheraven const __storage_allocator& __alloc() const _NOEXCEPT 2081227825Stheraven {return __cap_alloc_.second();} 2082227825Stheraven 2083227825Stheraven static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 2084227825Stheraven 2085227825Stheraven _LIBCPP_INLINE_VISIBILITY 2086227825Stheraven static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT 2087227825Stheraven {return __n * __bits_per_word;} 2088227825Stheraven _LIBCPP_INLINE_VISIBILITY 2089227825Stheraven static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT 2090227825Stheraven {return (__n - 1) / __bits_per_word + 1;} 2091227825Stheraven 2092227825Stheravenpublic: 2093227825Stheraven _LIBCPP_INLINE_VISIBILITY 2094227825Stheraven vector() 2095227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 2096227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a); 2097227825Stheraven ~vector(); 2098227825Stheraven explicit vector(size_type __n); 2099227825Stheraven vector(size_type __n, const value_type& __v); 2100227825Stheraven vector(size_type __n, const value_type& __v, const allocator_type& __a); 2101227825Stheraven template <class _InputIterator> 2102227825Stheraven vector(_InputIterator __first, _InputIterator __last, 2103227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2104227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2105227825Stheraven template <class _InputIterator> 2106227825Stheraven vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2107227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2108227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2109227825Stheraven template <class _ForwardIterator> 2110227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, 2111227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2112227825Stheraven template <class _ForwardIterator> 2113227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2114227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2115227825Stheraven 2116227825Stheraven vector(const vector& __v); 2117227825Stheraven vector(const vector& __v, const allocator_type& __a); 2118227825Stheraven vector& operator=(const vector& __v); 2119227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2120227825Stheraven vector(initializer_list<value_type> __il); 2121227825Stheraven vector(initializer_list<value_type> __il, const allocator_type& __a); 2122227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2123227825Stheraven 2124227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2125227825Stheraven _LIBCPP_INLINE_VISIBILITY 2126227825Stheraven vector(vector&& __v) 2127227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 2128227825Stheraven vector(vector&& __v, const allocator_type& __a); 2129227825Stheraven _LIBCPP_INLINE_VISIBILITY 2130227825Stheraven vector& operator=(vector&& __v) 2131227825Stheraven _NOEXCEPT_( 2132227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 2133227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 2134227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2135227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2136227825Stheraven _LIBCPP_INLINE_VISIBILITY 2137227825Stheraven vector& operator=(initializer_list<value_type> __il) 2138227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 2139227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2140227825Stheraven 2141227825Stheraven template <class _InputIterator> 2142227825Stheraven typename enable_if 2143227825Stheraven < 2144227825Stheraven __is_input_iterator<_InputIterator>::value && 2145227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2146227825Stheraven void 2147227825Stheraven >::type 2148227825Stheraven assign(_InputIterator __first, _InputIterator __last); 2149227825Stheraven template <class _ForwardIterator> 2150227825Stheraven typename enable_if 2151227825Stheraven < 2152227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2153227825Stheraven void 2154227825Stheraven >::type 2155227825Stheraven assign(_ForwardIterator __first, _ForwardIterator __last); 2156227825Stheraven 2157227825Stheraven void assign(size_type __n, const value_type& __x); 2158227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2159227825Stheraven _LIBCPP_INLINE_VISIBILITY 2160227825Stheraven void assign(initializer_list<value_type> __il) 2161227825Stheraven {assign(__il.begin(), __il.end());} 2162227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2163227825Stheraven 2164227825Stheraven _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT 2165227825Stheraven {return allocator_type(this->__alloc());} 2166227825Stheraven 2167227825Stheraven size_type max_size() const _NOEXCEPT; 2168227825Stheraven _LIBCPP_INLINE_VISIBILITY 2169227825Stheraven size_type capacity() const _NOEXCEPT 2170227825Stheraven {return __internal_cap_to_external(__cap());} 2171227825Stheraven _LIBCPP_INLINE_VISIBILITY 2172227825Stheraven size_type size() const _NOEXCEPT 2173227825Stheraven {return __size_;} 2174227825Stheraven _LIBCPP_INLINE_VISIBILITY 2175227825Stheraven bool empty() const _NOEXCEPT 2176227825Stheraven {return __size_ == 0;} 2177227825Stheraven void reserve(size_type __n); 2178227825Stheraven void shrink_to_fit() _NOEXCEPT; 2179227825Stheraven 2180227825Stheraven _LIBCPP_INLINE_VISIBILITY 2181227825Stheraven iterator begin() _NOEXCEPT 2182227825Stheraven {return __make_iter(0);} 2183227825Stheraven _LIBCPP_INLINE_VISIBILITY 2184227825Stheraven const_iterator begin() const _NOEXCEPT 2185227825Stheraven {return __make_iter(0);} 2186227825Stheraven _LIBCPP_INLINE_VISIBILITY 2187227825Stheraven iterator end() _NOEXCEPT 2188227825Stheraven {return __make_iter(__size_);} 2189227825Stheraven _LIBCPP_INLINE_VISIBILITY 2190227825Stheraven const_iterator end() const _NOEXCEPT 2191227825Stheraven {return __make_iter(__size_);} 2192227825Stheraven 2193227825Stheraven _LIBCPP_INLINE_VISIBILITY 2194227825Stheraven reverse_iterator rbegin() _NOEXCEPT 2195227825Stheraven {return reverse_iterator(end());} 2196227825Stheraven _LIBCPP_INLINE_VISIBILITY 2197227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 2198227825Stheraven {return const_reverse_iterator(end());} 2199227825Stheraven _LIBCPP_INLINE_VISIBILITY 2200227825Stheraven reverse_iterator rend() _NOEXCEPT 2201227825Stheraven {return reverse_iterator(begin());} 2202227825Stheraven _LIBCPP_INLINE_VISIBILITY 2203227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 2204227825Stheraven {return const_reverse_iterator(begin());} 2205227825Stheraven 2206227825Stheraven _LIBCPP_INLINE_VISIBILITY 2207227825Stheraven const_iterator cbegin() const _NOEXCEPT 2208227825Stheraven {return __make_iter(0);} 2209227825Stheraven _LIBCPP_INLINE_VISIBILITY 2210227825Stheraven const_iterator cend() const _NOEXCEPT 2211227825Stheraven {return __make_iter(__size_);} 2212227825Stheraven _LIBCPP_INLINE_VISIBILITY 2213227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 2214227825Stheraven {return rbegin();} 2215227825Stheraven _LIBCPP_INLINE_VISIBILITY 2216227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 2217227825Stheraven {return rend();} 2218227825Stheraven 2219227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);} 2220227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);} 2221227825Stheraven reference at(size_type __n); 2222227825Stheraven const_reference at(size_type __n) const; 2223227825Stheraven 2224227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);} 2225227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);} 2226227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);} 2227227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);} 2228227825Stheraven 2229227825Stheraven void push_back(const value_type& __x); 2230227825Stheraven _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;} 2231227825Stheraven 2232227825Stheraven iterator insert(const_iterator __position, const value_type& __x); 2233227825Stheraven iterator insert(const_iterator __position, size_type __n, const value_type& __x); 2234227825Stheraven iterator insert(const_iterator __position, size_type __n, const_reference __x); 2235227825Stheraven template <class _InputIterator> 2236227825Stheraven typename enable_if 2237227825Stheraven < 2238227825Stheraven __is_input_iterator <_InputIterator>::value && 2239227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2240227825Stheraven iterator 2241227825Stheraven >::type 2242227825Stheraven insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 2243227825Stheraven template <class _ForwardIterator> 2244227825Stheraven typename enable_if 2245227825Stheraven < 2246227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2247227825Stheraven iterator 2248227825Stheraven >::type 2249227825Stheraven insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 2250227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2251227825Stheraven _LIBCPP_INLINE_VISIBILITY 2252227825Stheraven iterator insert(const_iterator __position, initializer_list<value_type> __il) 2253227825Stheraven {return insert(__position, __il.begin(), __il.end());} 2254227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2255227825Stheraven 2256227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 2257227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 2258227825Stheraven 2259227825Stheraven _LIBCPP_INLINE_VISIBILITY 2260227825Stheraven void clear() _NOEXCEPT {__size_ = 0;} 2261227825Stheraven 2262227825Stheraven void swap(vector&) 2263227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2264227825Stheraven __is_nothrow_swappable<allocator_type>::value); 2265227825Stheraven 2266227825Stheraven void resize(size_type __sz, value_type __x = false); 2267227825Stheraven void flip() _NOEXCEPT; 2268227825Stheraven 2269227825Stheraven bool __invariants() const; 2270227825Stheraven 2271227825Stheravenprivate: 2272227825Stheraven _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 2273227825Stheraven void allocate(size_type __n); 2274227825Stheraven void deallocate() _NOEXCEPT; 2275227825Stheraven _LIBCPP_INLINE_VISIBILITY 2276227825Stheraven static size_type __align(size_type __new_size) _NOEXCEPT 2277227825Stheraven {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);}; 2278227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 2279227825Stheraven _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x); 2280227825Stheraven template <class _ForwardIterator> 2281227825Stheraven typename enable_if 2282227825Stheraven < 2283227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2284227825Stheraven void 2285227825Stheraven >::type 2286227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 2287227825Stheraven void __append(size_type __n, const_reference __x); 2288227825Stheraven _LIBCPP_INLINE_VISIBILITY 2289227825Stheraven reference __make_ref(size_type __pos) _NOEXCEPT 2290227825Stheraven {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2291227825Stheraven _LIBCPP_INLINE_VISIBILITY 2292227825Stheraven const_reference __make_ref(size_type __pos) const _NOEXCEPT 2293227825Stheraven {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2294227825Stheraven#ifdef _LIBCPP_DEBUG 2295227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos) 2296227825Stheraven {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));} 2297227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const 2298227825Stheraven {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));} 2299227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p) 2300227825Stheraven {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));} 2301227825Stheraven#else // _LIBCPP_DEBUG 2302227825Stheraven _LIBCPP_INLINE_VISIBILITY 2303227825Stheraven iterator __make_iter(size_type __pos) _NOEXCEPT 2304227825Stheraven {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2305227825Stheraven _LIBCPP_INLINE_VISIBILITY 2306227825Stheraven const_iterator __make_iter(size_type __pos) const _NOEXCEPT 2307227825Stheraven {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2308227825Stheraven _LIBCPP_INLINE_VISIBILITY 2309227825Stheraven iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT 2310227825Stheraven {return iterator(const_cast<__storage_pointer>(__p.__seg_), __p.__ctz_);} 2311227825Stheraven#endif // _LIBCPP_DEBUG 2312227825Stheraven 2313227825Stheraven _LIBCPP_INLINE_VISIBILITY 2314227825Stheraven void __copy_assign_alloc(const vector& __v) 2315227825Stheraven {__copy_assign_alloc(__v, integral_constant<bool, 2316227825Stheraven __storage_traits::propagate_on_container_copy_assignment::value>());} 2317227825Stheraven _LIBCPP_INLINE_VISIBILITY 2318227825Stheraven void __copy_assign_alloc(const vector& __c, true_type) 2319227825Stheraven { 2320227825Stheraven if (__alloc() != __c.__alloc()) 2321227825Stheraven deallocate(); 2322227825Stheraven __alloc() = __c.__alloc(); 2323227825Stheraven } 2324227825Stheraven 2325227825Stheraven _LIBCPP_INLINE_VISIBILITY 2326232950Stheraven void __copy_assign_alloc(const vector&, false_type) 2327227825Stheraven {} 2328227825Stheraven 2329227825Stheraven void __move_assign(vector& __c, false_type); 2330227825Stheraven void __move_assign(vector& __c, true_type) 2331227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 2332227825Stheraven _LIBCPP_INLINE_VISIBILITY 2333227825Stheraven void __move_assign_alloc(vector& __c) 2334227825Stheraven _NOEXCEPT_( 2335227825Stheraven !__storage_traits::propagate_on_container_move_assignment::value || 2336227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 2337227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 2338227825Stheraven __storage_traits::propagate_on_container_move_assignment::value>());} 2339227825Stheraven _LIBCPP_INLINE_VISIBILITY 2340227825Stheraven void __move_assign_alloc(vector& __c, true_type) 2341227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2342227825Stheraven { 2343227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 2344227825Stheraven } 2345227825Stheraven 2346227825Stheraven _LIBCPP_INLINE_VISIBILITY 2347232950Stheraven void __move_assign_alloc(vector&, false_type) 2348227825Stheraven _NOEXCEPT 2349227825Stheraven {} 2350227825Stheraven 2351227825Stheraven _LIBCPP_INLINE_VISIBILITY 2352227825Stheraven static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y) 2353227825Stheraven _NOEXCEPT_( 2354227825Stheraven !__storage_traits::propagate_on_container_swap::value || 2355227825Stheraven __is_nothrow_swappable<allocator_type>::value) 2356227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 2357227825Stheraven __storage_traits::propagate_on_container_swap::value>());} 2358227825Stheraven 2359227825Stheraven _LIBCPP_INLINE_VISIBILITY 2360227825Stheraven static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type) 2361227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value) 2362227825Stheraven { 2363227825Stheraven using _VSTD::swap; 2364227825Stheraven swap(__x, __y); 2365227825Stheraven } 2366227825Stheraven _LIBCPP_INLINE_VISIBILITY 2367232950Stheraven static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type) 2368227825Stheraven _NOEXCEPT 2369227825Stheraven {} 2370227825Stheraven 2371227825Stheraven size_t __hash_code() const _NOEXCEPT; 2372227825Stheraven 2373227825Stheraven friend class __bit_reference<vector>; 2374227825Stheraven friend class __bit_const_reference<vector>; 2375227825Stheraven friend class __bit_iterator<vector, false>; 2376227825Stheraven friend class __bit_iterator<vector, true>; 2377241903Sdim friend struct __bit_array<vector>; 2378249998Sdim friend struct _LIBCPP_TYPE_VIS hash<vector>; 2379227825Stheraven}; 2380227825Stheraven 2381227825Stheraventemplate <class _Allocator> 2382227825Stheraven#ifndef _LIBCPP_DEBUG 2383227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2384227825Stheraven#endif 2385227825Stheravenvoid 2386227825Stheravenvector<bool, _Allocator>::__invalidate_all_iterators() 2387227825Stheraven{ 2388227825Stheraven#ifdef _LIBCPP_DEBUG 2389227825Stheraven iterator::__remove_all(this); 2390227825Stheraven const_iterator::__remove_all(this); 2391227825Stheraven#endif // _LIBCPP_DEBUG 2392227825Stheraven} 2393227825Stheraven 2394227825Stheraven// Allocate space for __n objects 2395227825Stheraven// throws length_error if __n > max_size() 2396227825Stheraven// throws (probably bad_alloc) if memory run out 2397227825Stheraven// Precondition: __begin_ == __end_ == __cap() == 0 2398227825Stheraven// Precondition: __n > 0 2399227825Stheraven// Postcondition: capacity() == __n 2400227825Stheraven// Postcondition: size() == 0 2401227825Stheraventemplate <class _Allocator> 2402227825Stheravenvoid 2403227825Stheravenvector<bool, _Allocator>::allocate(size_type __n) 2404227825Stheraven{ 2405227825Stheraven if (__n > max_size()) 2406227825Stheraven this->__throw_length_error(); 2407227825Stheraven __n = __external_cap_to_internal(__n); 2408227825Stheraven this->__begin_ = __storage_traits::allocate(this->__alloc(), __n); 2409227825Stheraven this->__size_ = 0; 2410227825Stheraven this->__cap() = __n; 2411227825Stheraven} 2412227825Stheraven 2413227825Stheraventemplate <class _Allocator> 2414227825Stheravenvoid 2415227825Stheravenvector<bool, _Allocator>::deallocate() _NOEXCEPT 2416227825Stheraven{ 2417227825Stheraven if (this->__begin_ != 0) 2418227825Stheraven { 2419227825Stheraven __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 2420227825Stheraven __invalidate_all_iterators(); 2421227825Stheraven this->__begin_ = 0; 2422227825Stheraven this->__size_ = this->__cap() = 0; 2423227825Stheraven } 2424227825Stheraven} 2425227825Stheraven 2426227825Stheraventemplate <class _Allocator> 2427227825Stheraventypename vector<bool, _Allocator>::size_type 2428227825Stheravenvector<bool, _Allocator>::max_size() const _NOEXCEPT 2429227825Stheraven{ 2430227825Stheraven size_type __amax = __storage_traits::max_size(__alloc()); 2431227825Stheraven size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 2432227825Stheraven if (__nmax / __bits_per_word <= __amax) 2433227825Stheraven return __nmax; 2434227825Stheraven return __internal_cap_to_external(__amax); 2435227825Stheraven} 2436227825Stheraven 2437227825Stheraven// Precondition: __new_size > capacity() 2438227825Stheraventemplate <class _Allocator> 2439227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2440227825Stheraventypename vector<bool, _Allocator>::size_type 2441227825Stheravenvector<bool, _Allocator>::__recommend(size_type __new_size) const 2442227825Stheraven{ 2443227825Stheraven const size_type __ms = max_size(); 2444227825Stheraven if (__new_size > __ms) 2445227825Stheraven this->__throw_length_error(); 2446227825Stheraven const size_type __cap = capacity(); 2447227825Stheraven if (__cap >= __ms / 2) 2448227825Stheraven return __ms; 2449227825Stheraven return _VSTD::max(2*__cap, __align(__new_size)); 2450227825Stheraven} 2451227825Stheraven 2452227825Stheraven// Default constructs __n objects starting at __end_ 2453227825Stheraven// Precondition: __n > 0 2454227825Stheraven// Precondition: size() + __n <= capacity() 2455227825Stheraven// Postcondition: size() == size() + __n 2456227825Stheraventemplate <class _Allocator> 2457227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2458227825Stheravenvoid 2459227825Stheravenvector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) 2460227825Stheraven{ 2461227825Stheraven size_type __old_size = this->__size_; 2462227825Stheraven this->__size_ += __n; 2463227825Stheraven _VSTD::fill_n(__make_iter(__old_size), __n, __x); 2464227825Stheraven} 2465227825Stheraven 2466227825Stheraventemplate <class _Allocator> 2467227825Stheraventemplate <class _ForwardIterator> 2468227825Stheraventypename enable_if 2469227825Stheraven< 2470227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2471227825Stheraven void 2472227825Stheraven>::type 2473227825Stheravenvector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 2474227825Stheraven{ 2475227825Stheraven size_type __old_size = this->__size_; 2476227825Stheraven this->__size_ += _VSTD::distance(__first, __last); 2477227825Stheraven _VSTD::copy(__first, __last, __make_iter(__old_size)); 2478227825Stheraven} 2479227825Stheraven 2480227825Stheraventemplate <class _Allocator> 2481227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2482227825Stheravenvector<bool, _Allocator>::vector() 2483227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 2484227825Stheraven : __begin_(0), 2485227825Stheraven __size_(0), 2486227825Stheraven __cap_alloc_(0) 2487227825Stheraven{ 2488227825Stheraven} 2489227825Stheraven 2490227825Stheraventemplate <class _Allocator> 2491227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2492227825Stheravenvector<bool, _Allocator>::vector(const allocator_type& __a) 2493227825Stheraven : __begin_(0), 2494227825Stheraven __size_(0), 2495227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2496227825Stheraven{ 2497227825Stheraven} 2498227825Stheraven 2499227825Stheraventemplate <class _Allocator> 2500227825Stheravenvector<bool, _Allocator>::vector(size_type __n) 2501227825Stheraven : __begin_(0), 2502227825Stheraven __size_(0), 2503227825Stheraven __cap_alloc_(0) 2504227825Stheraven{ 2505227825Stheraven if (__n > 0) 2506227825Stheraven { 2507227825Stheraven allocate(__n); 2508227825Stheraven __construct_at_end(__n, false); 2509227825Stheraven } 2510227825Stheraven} 2511227825Stheraven 2512227825Stheraventemplate <class _Allocator> 2513227825Stheravenvector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 2514227825Stheraven : __begin_(0), 2515227825Stheraven __size_(0), 2516227825Stheraven __cap_alloc_(0) 2517227825Stheraven{ 2518227825Stheraven if (__n > 0) 2519227825Stheraven { 2520227825Stheraven allocate(__n); 2521227825Stheraven __construct_at_end(__n, __x); 2522227825Stheraven } 2523227825Stheraven} 2524227825Stheraven 2525227825Stheraventemplate <class _Allocator> 2526227825Stheravenvector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 2527227825Stheraven : __begin_(0), 2528227825Stheraven __size_(0), 2529227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2530227825Stheraven{ 2531227825Stheraven if (__n > 0) 2532227825Stheraven { 2533227825Stheraven allocate(__n); 2534227825Stheraven __construct_at_end(__n, __x); 2535227825Stheraven } 2536227825Stheraven} 2537227825Stheraven 2538227825Stheraventemplate <class _Allocator> 2539227825Stheraventemplate <class _InputIterator> 2540227825Stheravenvector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 2541227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2542227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 2543227825Stheraven : __begin_(0), 2544227825Stheraven __size_(0), 2545227825Stheraven __cap_alloc_(0) 2546227825Stheraven{ 2547227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2548227825Stheraven try 2549227825Stheraven { 2550227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2551227825Stheraven for (; __first != __last; ++__first) 2552227825Stheraven push_back(*__first); 2553227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2554227825Stheraven } 2555227825Stheraven catch (...) 2556227825Stheraven { 2557227825Stheraven if (__begin_ != 0) 2558227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2559227825Stheraven __invalidate_all_iterators(); 2560227825Stheraven throw; 2561227825Stheraven } 2562227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2563227825Stheraven} 2564227825Stheraven 2565227825Stheraventemplate <class _Allocator> 2566227825Stheraventemplate <class _InputIterator> 2567227825Stheravenvector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2568227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2569227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 2570227825Stheraven : __begin_(0), 2571227825Stheraven __size_(0), 2572227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2573227825Stheraven{ 2574227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2575227825Stheraven try 2576227825Stheraven { 2577227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2578227825Stheraven for (; __first != __last; ++__first) 2579227825Stheraven push_back(*__first); 2580227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2581227825Stheraven } 2582227825Stheraven catch (...) 2583227825Stheraven { 2584227825Stheraven if (__begin_ != 0) 2585227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2586227825Stheraven __invalidate_all_iterators(); 2587227825Stheraven throw; 2588227825Stheraven } 2589227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2590227825Stheraven} 2591227825Stheraven 2592227825Stheraventemplate <class _Allocator> 2593227825Stheraventemplate <class _ForwardIterator> 2594227825Stheravenvector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 2595227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2596227825Stheraven : __begin_(0), 2597227825Stheraven __size_(0), 2598227825Stheraven __cap_alloc_(0) 2599227825Stheraven{ 2600227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2601227825Stheraven if (__n > 0) 2602227825Stheraven { 2603227825Stheraven allocate(__n); 2604227825Stheraven __construct_at_end(__first, __last); 2605227825Stheraven } 2606227825Stheraven} 2607227825Stheraven 2608227825Stheraventemplate <class _Allocator> 2609227825Stheraventemplate <class _ForwardIterator> 2610227825Stheravenvector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2611227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2612227825Stheraven : __begin_(0), 2613227825Stheraven __size_(0), 2614227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2615227825Stheraven{ 2616227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2617227825Stheraven if (__n > 0) 2618227825Stheraven { 2619227825Stheraven allocate(__n); 2620227825Stheraven __construct_at_end(__first, __last); 2621227825Stheraven } 2622227825Stheraven} 2623227825Stheraven 2624227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2625227825Stheraven 2626227825Stheraventemplate <class _Allocator> 2627227825Stheravenvector<bool, _Allocator>::vector(initializer_list<value_type> __il) 2628227825Stheraven : __begin_(0), 2629227825Stheraven __size_(0), 2630227825Stheraven __cap_alloc_(0) 2631227825Stheraven{ 2632227825Stheraven size_type __n = static_cast<size_type>(__il.size()); 2633227825Stheraven if (__n > 0) 2634227825Stheraven { 2635227825Stheraven allocate(__n); 2636227825Stheraven __construct_at_end(__il.begin(), __il.end()); 2637227825Stheraven } 2638227825Stheraven} 2639227825Stheraven 2640227825Stheraventemplate <class _Allocator> 2641227825Stheravenvector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 2642227825Stheraven : __begin_(0), 2643227825Stheraven __size_(0), 2644227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2645227825Stheraven{ 2646227825Stheraven size_type __n = static_cast<size_type>(__il.size()); 2647227825Stheraven if (__n > 0) 2648227825Stheraven { 2649227825Stheraven allocate(__n); 2650227825Stheraven __construct_at_end(__il.begin(), __il.end()); 2651227825Stheraven } 2652227825Stheraven} 2653227825Stheraven 2654227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2655227825Stheraven 2656227825Stheraventemplate <class _Allocator> 2657227825Stheravenvector<bool, _Allocator>::~vector() 2658227825Stheraven{ 2659227825Stheraven if (__begin_ != 0) 2660227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2661227825Stheraven#ifdef _LIBCPP_DEBUG 2662227825Stheraven __invalidate_all_iterators(); 2663227825Stheraven#endif 2664227825Stheraven} 2665227825Stheraven 2666227825Stheraventemplate <class _Allocator> 2667227825Stheravenvector<bool, _Allocator>::vector(const vector& __v) 2668227825Stheraven : __begin_(0), 2669227825Stheraven __size_(0), 2670227825Stheraven __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) 2671227825Stheraven{ 2672227825Stheraven if (__v.size() > 0) 2673227825Stheraven { 2674227825Stheraven allocate(__v.size()); 2675227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2676227825Stheraven } 2677227825Stheraven} 2678227825Stheraven 2679227825Stheraventemplate <class _Allocator> 2680227825Stheravenvector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2681227825Stheraven : __begin_(0), 2682227825Stheraven __size_(0), 2683227825Stheraven __cap_alloc_(0, __a) 2684227825Stheraven{ 2685227825Stheraven if (__v.size() > 0) 2686227825Stheraven { 2687227825Stheraven allocate(__v.size()); 2688227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2689227825Stheraven } 2690227825Stheraven} 2691227825Stheraven 2692227825Stheraventemplate <class _Allocator> 2693227825Stheravenvector<bool, _Allocator>& 2694227825Stheravenvector<bool, _Allocator>::operator=(const vector& __v) 2695227825Stheraven{ 2696227825Stheraven if (this != &__v) 2697227825Stheraven { 2698227825Stheraven __copy_assign_alloc(__v); 2699227825Stheraven if (__v.__size_) 2700227825Stheraven { 2701227825Stheraven if (__v.__size_ > capacity()) 2702227825Stheraven { 2703227825Stheraven deallocate(); 2704227825Stheraven allocate(__v.__size_); 2705227825Stheraven } 2706227825Stheraven _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2707227825Stheraven } 2708227825Stheraven __size_ = __v.__size_; 2709227825Stheraven } 2710227825Stheraven return *this; 2711227825Stheraven} 2712227825Stheraven 2713227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2714227825Stheraven 2715227825Stheraventemplate <class _Allocator> 2716227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2717227825Stheravenvector<bool, _Allocator>::vector(vector&& __v) 2718227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 2719227825Stheraven : __begin_(__v.__begin_), 2720227825Stheraven __size_(__v.__size_), 2721227825Stheraven __cap_alloc_(__v.__cap_alloc_) 2722227825Stheraven{ 2723227825Stheraven __v.__begin_ = 0; 2724227825Stheraven __v.__size_ = 0; 2725227825Stheraven __v.__cap() = 0; 2726227825Stheraven} 2727227825Stheraven 2728227825Stheraventemplate <class _Allocator> 2729227825Stheravenvector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a) 2730227825Stheraven : __begin_(0), 2731227825Stheraven __size_(0), 2732227825Stheraven __cap_alloc_(0, __a) 2733227825Stheraven{ 2734227825Stheraven if (__a == allocator_type(__v.__alloc())) 2735227825Stheraven { 2736227825Stheraven this->__begin_ = __v.__begin_; 2737227825Stheraven this->__size_ = __v.__size_; 2738227825Stheraven this->__cap() = __v.__cap(); 2739227825Stheraven __v.__begin_ = nullptr; 2740227825Stheraven __v.__cap() = __v.__size_ = 0; 2741227825Stheraven } 2742227825Stheraven else if (__v.size() > 0) 2743227825Stheraven { 2744227825Stheraven allocate(__v.size()); 2745227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2746227825Stheraven } 2747227825Stheraven} 2748227825Stheraven 2749227825Stheraventemplate <class _Allocator> 2750227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2751227825Stheravenvector<bool, _Allocator>& 2752227825Stheravenvector<bool, _Allocator>::operator=(vector&& __v) 2753227825Stheraven _NOEXCEPT_( 2754227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 2755227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 2756227825Stheraven{ 2757227825Stheraven __move_assign(__v, integral_constant<bool, 2758227825Stheraven __storage_traits::propagate_on_container_move_assignment::value>()); 2759241903Sdim return *this; 2760227825Stheraven} 2761227825Stheraven 2762227825Stheraventemplate <class _Allocator> 2763227825Stheravenvoid 2764227825Stheravenvector<bool, _Allocator>::__move_assign(vector& __c, false_type) 2765227825Stheraven{ 2766227825Stheraven if (__alloc() != __c.__alloc()) 2767227825Stheraven assign(__c.begin(), __c.end()); 2768227825Stheraven else 2769227825Stheraven __move_assign(__c, true_type()); 2770227825Stheraven} 2771227825Stheraven 2772227825Stheraventemplate <class _Allocator> 2773227825Stheravenvoid 2774227825Stheravenvector<bool, _Allocator>::__move_assign(vector& __c, true_type) 2775227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2776227825Stheraven{ 2777227825Stheraven deallocate(); 2778227825Stheraven this->__begin_ = __c.__begin_; 2779227825Stheraven this->__size_ = __c.__size_; 2780227825Stheraven this->__cap() = __c.__cap(); 2781227825Stheraven __move_assign_alloc(__c); 2782227825Stheraven __c.__begin_ = nullptr; 2783227825Stheraven __c.__cap() = __c.__size_ = 0; 2784227825Stheraven} 2785227825Stheraven 2786227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2787227825Stheraven 2788227825Stheraventemplate <class _Allocator> 2789227825Stheravenvoid 2790227825Stheravenvector<bool, _Allocator>::assign(size_type __n, const value_type& __x) 2791227825Stheraven{ 2792227825Stheraven __size_ = 0; 2793227825Stheraven if (__n > 0) 2794227825Stheraven { 2795227825Stheraven size_type __c = capacity(); 2796227825Stheraven if (__n <= __c) 2797227825Stheraven __size_ = __n; 2798227825Stheraven else 2799227825Stheraven { 2800227825Stheraven vector __v(__alloc()); 2801227825Stheraven __v.reserve(__recommend(__n)); 2802227825Stheraven __v.__size_ = __n; 2803227825Stheraven swap(__v); 2804227825Stheraven } 2805227825Stheraven _VSTD::fill_n(begin(), __n, __x); 2806227825Stheraven } 2807227825Stheraven} 2808227825Stheraven 2809227825Stheraventemplate <class _Allocator> 2810227825Stheraventemplate <class _InputIterator> 2811227825Stheraventypename enable_if 2812227825Stheraven< 2813227825Stheraven __is_input_iterator<_InputIterator>::value && 2814227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2815227825Stheraven void 2816227825Stheraven>::type 2817227825Stheravenvector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2818227825Stheraven{ 2819227825Stheraven clear(); 2820227825Stheraven for (; __first != __last; ++__first) 2821227825Stheraven push_back(*__first); 2822227825Stheraven} 2823227825Stheraven 2824227825Stheraventemplate <class _Allocator> 2825227825Stheraventemplate <class _ForwardIterator> 2826227825Stheraventypename enable_if 2827227825Stheraven< 2828227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2829227825Stheraven void 2830227825Stheraven>::type 2831227825Stheravenvector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2832227825Stheraven{ 2833227825Stheraven clear(); 2834227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 2835227825Stheraven if (__n) 2836227825Stheraven { 2837227825Stheraven if (__n > capacity()) 2838227825Stheraven { 2839227825Stheraven deallocate(); 2840227825Stheraven allocate(__n); 2841227825Stheraven } 2842227825Stheraven __construct_at_end(__first, __last); 2843227825Stheraven } 2844227825Stheraven} 2845227825Stheraven 2846227825Stheraventemplate <class _Allocator> 2847227825Stheravenvoid 2848227825Stheravenvector<bool, _Allocator>::reserve(size_type __n) 2849227825Stheraven{ 2850227825Stheraven if (__n > capacity()) 2851227825Stheraven { 2852227825Stheraven vector __v(this->__alloc()); 2853227825Stheraven __v.allocate(__n); 2854227825Stheraven __v.__construct_at_end(this->begin(), this->end()); 2855227825Stheraven swap(__v); 2856227825Stheraven __invalidate_all_iterators(); 2857227825Stheraven } 2858227825Stheraven} 2859227825Stheraven 2860227825Stheraventemplate <class _Allocator> 2861227825Stheravenvoid 2862227825Stheravenvector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT 2863227825Stheraven{ 2864227825Stheraven if (__external_cap_to_internal(size()) > __cap()) 2865227825Stheraven { 2866227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2867227825Stheraven try 2868227825Stheraven { 2869227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2870227825Stheraven vector(*this, allocator_type(__alloc())).swap(*this); 2871227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2872227825Stheraven } 2873227825Stheraven catch (...) 2874227825Stheraven { 2875227825Stheraven } 2876227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2877227825Stheraven } 2878227825Stheraven} 2879227825Stheraven 2880227825Stheraventemplate <class _Allocator> 2881227825Stheraventypename vector<bool, _Allocator>::reference 2882227825Stheravenvector<bool, _Allocator>::at(size_type __n) 2883227825Stheraven{ 2884227825Stheraven if (__n >= size()) 2885227825Stheraven this->__throw_out_of_range(); 2886227825Stheraven return (*this)[__n]; 2887227825Stheraven} 2888227825Stheraven 2889227825Stheraventemplate <class _Allocator> 2890227825Stheraventypename vector<bool, _Allocator>::const_reference 2891227825Stheravenvector<bool, _Allocator>::at(size_type __n) const 2892227825Stheraven{ 2893227825Stheraven if (__n >= size()) 2894227825Stheraven this->__throw_out_of_range(); 2895227825Stheraven return (*this)[__n]; 2896227825Stheraven} 2897227825Stheraven 2898227825Stheraventemplate <class _Allocator> 2899227825Stheravenvoid 2900227825Stheravenvector<bool, _Allocator>::push_back(const value_type& __x) 2901227825Stheraven{ 2902227825Stheraven if (this->__size_ == this->capacity()) 2903227825Stheraven reserve(__recommend(this->__size_ + 1)); 2904227825Stheraven ++this->__size_; 2905227825Stheraven back() = __x; 2906227825Stheraven} 2907227825Stheraven 2908227825Stheraventemplate <class _Allocator> 2909227825Stheraventypename vector<bool, _Allocator>::iterator 2910227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) 2911227825Stheraven{ 2912227825Stheraven iterator __r; 2913227825Stheraven if (size() < capacity()) 2914227825Stheraven { 2915227825Stheraven const_iterator __old_end = end(); 2916227825Stheraven ++__size_; 2917227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 2918227825Stheraven __r = __const_iterator_cast(__position); 2919227825Stheraven } 2920227825Stheraven else 2921227825Stheraven { 2922227825Stheraven vector __v(__alloc()); 2923227825Stheraven __v.reserve(__recommend(__size_ + 1)); 2924227825Stheraven __v.__size_ = __size_ + 1; 2925227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 2926227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 2927227825Stheraven swap(__v); 2928227825Stheraven } 2929227825Stheraven *__r = __x; 2930227825Stheraven return __r; 2931227825Stheraven} 2932227825Stheraven 2933227825Stheraventemplate <class _Allocator> 2934227825Stheraventypename vector<bool, _Allocator>::iterator 2935227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) 2936227825Stheraven{ 2937227825Stheraven iterator __r; 2938227825Stheraven size_type __c = capacity(); 2939227825Stheraven if (__n <= __c && size() <= __c - __n) 2940227825Stheraven { 2941227825Stheraven const_iterator __old_end = end(); 2942227825Stheraven __size_ += __n; 2943227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 2944227825Stheraven __r = __const_iterator_cast(__position); 2945227825Stheraven } 2946227825Stheraven else 2947227825Stheraven { 2948227825Stheraven vector __v(__alloc()); 2949227825Stheraven __v.reserve(__recommend(__size_ + __n)); 2950227825Stheraven __v.__size_ = __size_ + __n; 2951227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 2952227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 2953227825Stheraven swap(__v); 2954227825Stheraven } 2955227825Stheraven _VSTD::fill_n(__r, __n, __x); 2956227825Stheraven return __r; 2957227825Stheraven} 2958227825Stheraven 2959227825Stheraventemplate <class _Allocator> 2960227825Stheraventemplate <class _InputIterator> 2961227825Stheraventypename enable_if 2962227825Stheraven< 2963227825Stheraven __is_input_iterator <_InputIterator>::value && 2964227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2965227825Stheraven typename vector<bool, _Allocator>::iterator 2966227825Stheraven>::type 2967227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 2968227825Stheraven{ 2969227825Stheraven difference_type __off = __position - begin(); 2970227825Stheraven iterator __p = __const_iterator_cast(__position); 2971227825Stheraven iterator __old_end = end(); 2972227825Stheraven for (; size() != capacity() && __first != __last; ++__first) 2973227825Stheraven { 2974227825Stheraven ++this->__size_; 2975227825Stheraven back() = *__first; 2976227825Stheraven } 2977227825Stheraven vector __v(__alloc()); 2978227825Stheraven if (__first != __last) 2979227825Stheraven { 2980227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2981227825Stheraven try 2982227825Stheraven { 2983227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2984227825Stheraven __v.assign(__first, __last); 2985227825Stheraven difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 2986227825Stheraven difference_type __old_p = __p - begin(); 2987227825Stheraven reserve(__recommend(size() + __v.size())); 2988227825Stheraven __p = begin() + __old_p; 2989227825Stheraven __old_end = begin() + __old_size; 2990227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2991227825Stheraven } 2992227825Stheraven catch (...) 2993227825Stheraven { 2994227825Stheraven erase(__old_end, end()); 2995227825Stheraven throw; 2996227825Stheraven } 2997227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2998227825Stheraven } 2999227825Stheraven __p = _VSTD::rotate(__p, __old_end, end()); 3000227825Stheraven insert(__p, __v.begin(), __v.end()); 3001227825Stheraven return begin() + __off; 3002227825Stheraven} 3003227825Stheraven 3004227825Stheraventemplate <class _Allocator> 3005227825Stheraventemplate <class _ForwardIterator> 3006227825Stheraventypename enable_if 3007227825Stheraven< 3008227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 3009227825Stheraven typename vector<bool, _Allocator>::iterator 3010227825Stheraven>::type 3011227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 3012227825Stheraven{ 3013227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 3014227825Stheraven iterator __r; 3015227825Stheraven size_type __c = capacity(); 3016227825Stheraven if (__n <= __c && size() <= __c - __n) 3017227825Stheraven { 3018227825Stheraven const_iterator __old_end = end(); 3019227825Stheraven __size_ += __n; 3020227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 3021227825Stheraven __r = __const_iterator_cast(__position); 3022227825Stheraven } 3023227825Stheraven else 3024227825Stheraven { 3025227825Stheraven vector __v(__alloc()); 3026227825Stheraven __v.reserve(__recommend(__size_ + __n)); 3027227825Stheraven __v.__size_ = __size_ + __n; 3028227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 3029227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 3030227825Stheraven swap(__v); 3031227825Stheraven } 3032227825Stheraven _VSTD::copy(__first, __last, __r); 3033227825Stheraven return __r; 3034227825Stheraven} 3035227825Stheraven 3036227825Stheraventemplate <class _Allocator> 3037227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3038227825Stheraventypename vector<bool, _Allocator>::iterator 3039227825Stheravenvector<bool, _Allocator>::erase(const_iterator __position) 3040227825Stheraven{ 3041227825Stheraven iterator __r = __const_iterator_cast(__position); 3042227825Stheraven _VSTD::copy(__position + 1, this->cend(), __r); 3043227825Stheraven --__size_; 3044227825Stheraven return __r; 3045227825Stheraven} 3046227825Stheraven 3047227825Stheraventemplate <class _Allocator> 3048227825Stheraventypename vector<bool, _Allocator>::iterator 3049227825Stheravenvector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) 3050227825Stheraven{ 3051227825Stheraven iterator __r = __const_iterator_cast(__first); 3052227825Stheraven difference_type __d = __last - __first; 3053227825Stheraven _VSTD::copy(__last, this->cend(), __r); 3054227825Stheraven __size_ -= __d; 3055227825Stheraven return __r; 3056227825Stheraven} 3057227825Stheraven 3058227825Stheraventemplate <class _Allocator> 3059227825Stheravenvoid 3060227825Stheravenvector<bool, _Allocator>::swap(vector& __x) 3061227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3062227825Stheraven __is_nothrow_swappable<allocator_type>::value) 3063227825Stheraven{ 3064227825Stheraven _VSTD::swap(this->__begin_, __x.__begin_); 3065227825Stheraven _VSTD::swap(this->__size_, __x.__size_); 3066227825Stheraven _VSTD::swap(this->__cap(), __x.__cap()); 3067227825Stheraven __swap_alloc(this->__alloc(), __x.__alloc()); 3068227825Stheraven#ifdef _LIBCPP_DEBUG 3069227825Stheraven iterator::swap(this, &__x); 3070227825Stheraven const_iterator::swap(this, &__x); 3071227825Stheraven#endif // _LIBCPP_DEBUG 3072227825Stheraven} 3073227825Stheraven 3074227825Stheraventemplate <class _Allocator> 3075227825Stheravenvoid 3076227825Stheravenvector<bool, _Allocator>::resize(size_type __sz, value_type __x) 3077227825Stheraven{ 3078227825Stheraven size_type __cs = size(); 3079227825Stheraven if (__cs < __sz) 3080227825Stheraven { 3081227825Stheraven iterator __r; 3082227825Stheraven size_type __c = capacity(); 3083227825Stheraven size_type __n = __sz - __cs; 3084227825Stheraven if (__n <= __c && __cs <= __c - __n) 3085227825Stheraven { 3086227825Stheraven __r = end(); 3087227825Stheraven __size_ += __n; 3088227825Stheraven } 3089227825Stheraven else 3090227825Stheraven { 3091227825Stheraven vector __v(__alloc()); 3092227825Stheraven __v.reserve(__recommend(__size_ + __n)); 3093227825Stheraven __v.__size_ = __size_ + __n; 3094227825Stheraven __r = _VSTD::copy(cbegin(), cend(), __v.begin()); 3095227825Stheraven swap(__v); 3096227825Stheraven } 3097227825Stheraven _VSTD::fill_n(__r, __n, __x); 3098227825Stheraven } 3099227825Stheraven else 3100227825Stheraven __size_ = __sz; 3101227825Stheraven} 3102227825Stheraven 3103227825Stheraventemplate <class _Allocator> 3104227825Stheravenvoid 3105227825Stheravenvector<bool, _Allocator>::flip() _NOEXCEPT 3106227825Stheraven{ 3107227825Stheraven // do middle whole words 3108227825Stheraven size_type __n = __size_; 3109227825Stheraven __storage_pointer __p = __begin_; 3110227825Stheraven for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3111227825Stheraven *__p = ~*__p; 3112227825Stheraven // do last partial word 3113227825Stheraven if (__n > 0) 3114227825Stheraven { 3115227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3116227825Stheraven __storage_type __b = *__p & __m; 3117227825Stheraven *__p &= ~__m; 3118227825Stheraven *__p |= ~__b & __m; 3119227825Stheraven } 3120227825Stheraven} 3121227825Stheraven 3122227825Stheraventemplate <class _Allocator> 3123227825Stheravenbool 3124227825Stheravenvector<bool, _Allocator>::__invariants() const 3125227825Stheraven{ 3126227825Stheraven if (this->__begin_ == 0) 3127227825Stheraven { 3128227825Stheraven if (this->__size_ != 0 || this->__cap() != 0) 3129227825Stheraven return false; 3130227825Stheraven } 3131227825Stheraven else 3132227825Stheraven { 3133227825Stheraven if (this->__cap() == 0) 3134227825Stheraven return false; 3135227825Stheraven if (this->__size_ > this->capacity()) 3136227825Stheraven return false; 3137227825Stheraven } 3138227825Stheraven return true; 3139227825Stheraven} 3140227825Stheraven 3141227825Stheraventemplate <class _Allocator> 3142227825Stheravensize_t 3143227825Stheravenvector<bool, _Allocator>::__hash_code() const _NOEXCEPT 3144227825Stheraven{ 3145227825Stheraven size_t __h = 0; 3146227825Stheraven // do middle whole words 3147227825Stheraven size_type __n = __size_; 3148227825Stheraven __storage_pointer __p = __begin_; 3149227825Stheraven for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3150227825Stheraven __h ^= *__p; 3151227825Stheraven // do last partial word 3152227825Stheraven if (__n > 0) 3153227825Stheraven { 3154227825Stheraven const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3155227825Stheraven __h ^= *__p & __m; 3156227825Stheraven } 3157227825Stheraven return __h; 3158227825Stheraven} 3159227825Stheraven 3160227825Stheraventemplate <class _Allocator> 3161249998Sdimstruct _LIBCPP_TYPE_VIS hash<vector<bool, _Allocator> > 3162227825Stheraven : public unary_function<vector<bool, _Allocator>, size_t> 3163227825Stheraven{ 3164227825Stheraven _LIBCPP_INLINE_VISIBILITY 3165227825Stheraven size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT 3166227825Stheraven {return __vec.__hash_code();} 3167227825Stheraven}; 3168227825Stheraven 3169227825Stheraventemplate <class _Tp, class _Allocator> 3170227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3171227825Stheravenbool 3172227825Stheravenoperator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3173227825Stheraven{ 3174227825Stheraven const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 3175227825Stheraven return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 3176227825Stheraven} 3177227825Stheraven 3178227825Stheraventemplate <class _Tp, class _Allocator> 3179227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3180227825Stheravenbool 3181227825Stheravenoperator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3182227825Stheraven{ 3183227825Stheraven return !(__x == __y); 3184227825Stheraven} 3185227825Stheraven 3186227825Stheraventemplate <class _Tp, class _Allocator> 3187227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3188227825Stheravenbool 3189227825Stheravenoperator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3190227825Stheraven{ 3191227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 3192227825Stheraven} 3193227825Stheraven 3194227825Stheraventemplate <class _Tp, class _Allocator> 3195227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3196227825Stheravenbool 3197227825Stheravenoperator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3198227825Stheraven{ 3199227825Stheraven return __y < __x; 3200227825Stheraven} 3201227825Stheraven 3202227825Stheraventemplate <class _Tp, class _Allocator> 3203227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3204227825Stheravenbool 3205227825Stheravenoperator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3206227825Stheraven{ 3207227825Stheraven return !(__x < __y); 3208227825Stheraven} 3209227825Stheraven 3210227825Stheraventemplate <class _Tp, class _Allocator> 3211227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3212227825Stheravenbool 3213227825Stheravenoperator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3214227825Stheraven{ 3215227825Stheraven return !(__y < __x); 3216227825Stheraven} 3217227825Stheraven 3218227825Stheraventemplate <class _Tp, class _Allocator> 3219227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3220227825Stheravenvoid 3221227825Stheravenswap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) 3222227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3223227825Stheraven{ 3224227825Stheraven __x.swap(__y); 3225227825Stheraven} 3226227825Stheraven 3227227825Stheraven_LIBCPP_END_NAMESPACE_STD 3228227825Stheraven 3229227825Stheraven#endif // _LIBCPP_VECTOR 3230