vector revision 246487
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> > 484227825Stheravenclass _LIBCPP_VISIBLE 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 505227825Stheraven _LIBCPP_INLINE_VISIBILITY 506227825Stheraven vector() 507227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 508227825Stheraven { 509227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 510227825Stheraven __get_db()->__insert_c(this); 511227825Stheraven#endif 512227825Stheraven } 513227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a) 514227825Stheraven : __base(__a) 515227825Stheraven { 516227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 517227825Stheraven __get_db()->__insert_c(this); 518227825Stheraven#endif 519227825Stheraven } 520227825Stheraven explicit vector(size_type __n); 521227825Stheraven vector(size_type __n, const_reference __x); 522227825Stheraven vector(size_type __n, const_reference __x, const allocator_type& __a); 523227825Stheraven template <class _InputIterator> 524227825Stheraven vector(_InputIterator __first, _InputIterator __last, 525227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 526227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 527227825Stheraven template <class _InputIterator> 528227825Stheraven vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 529227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 530227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 531227825Stheraven template <class _ForwardIterator> 532227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, 533227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 534227825Stheraven template <class _ForwardIterator> 535227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 536227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 537227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 538227825Stheraven _LIBCPP_INLINE_VISIBILITY 539227825Stheraven vector(initializer_list<value_type> __il); 540227825Stheraven _LIBCPP_INLINE_VISIBILITY 541227825Stheraven vector(initializer_list<value_type> __il, const allocator_type& __a); 542227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 543227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 544227825Stheraven _LIBCPP_INLINE_VISIBILITY 545227825Stheraven ~vector() 546227825Stheraven { 547227825Stheraven __get_db()->__erase_c(this); 548227825Stheraven } 549227825Stheraven#endif 550227825Stheraven 551227825Stheraven vector(const vector& __x); 552227825Stheraven vector(const vector& __x, const allocator_type& __a); 553227825Stheraven _LIBCPP_INLINE_VISIBILITY 554227825Stheraven vector& operator=(const vector& __x); 555227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 556227825Stheraven _LIBCPP_INLINE_VISIBILITY 557227825Stheraven vector(vector&& __x) 558227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 559227825Stheraven _LIBCPP_INLINE_VISIBILITY 560227825Stheraven vector(vector&& __x, const allocator_type& __a); 561227825Stheraven _LIBCPP_INLINE_VISIBILITY 562227825Stheraven vector& operator=(vector&& __x) 563227825Stheraven _NOEXCEPT_( 564227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 565227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 566227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 567227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 568227825Stheraven _LIBCPP_INLINE_VISIBILITY 569227825Stheraven vector& operator=(initializer_list<value_type> __il) 570227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 571227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 572227825Stheraven 573227825Stheraven template <class _InputIterator> 574227825Stheraven typename enable_if 575227825Stheraven < 576227825Stheraven __is_input_iterator <_InputIterator>::value && 577227825Stheraven !__is_forward_iterator<_InputIterator>::value, 578227825Stheraven void 579227825Stheraven >::type 580227825Stheraven assign(_InputIterator __first, _InputIterator __last); 581227825Stheraven template <class _ForwardIterator> 582227825Stheraven typename enable_if 583227825Stheraven < 584227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 585227825Stheraven void 586227825Stheraven >::type 587227825Stheraven assign(_ForwardIterator __first, _ForwardIterator __last); 588227825Stheraven 589227825Stheraven void assign(size_type __n, const_reference __u); 590227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 591227825Stheraven _LIBCPP_INLINE_VISIBILITY 592227825Stheraven void assign(initializer_list<value_type> __il) 593227825Stheraven {assign(__il.begin(), __il.end());} 594227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 595227825Stheraven 596227825Stheraven _LIBCPP_INLINE_VISIBILITY 597227825Stheraven allocator_type get_allocator() const _NOEXCEPT 598227825Stheraven {return this->__alloc();} 599227825Stheraven 600227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT; 601227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT; 602227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT; 603227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT; 604227825Stheraven 605227825Stheraven _LIBCPP_INLINE_VISIBILITY 606227825Stheraven reverse_iterator rbegin() _NOEXCEPT 607227825Stheraven {return reverse_iterator(end());} 608227825Stheraven _LIBCPP_INLINE_VISIBILITY 609227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 610227825Stheraven {return const_reverse_iterator(end());} 611227825Stheraven _LIBCPP_INLINE_VISIBILITY 612227825Stheraven reverse_iterator rend() _NOEXCEPT 613227825Stheraven {return reverse_iterator(begin());} 614227825Stheraven _LIBCPP_INLINE_VISIBILITY 615227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 616227825Stheraven {return const_reverse_iterator(begin());} 617227825Stheraven 618227825Stheraven _LIBCPP_INLINE_VISIBILITY 619227825Stheraven const_iterator cbegin() const _NOEXCEPT 620227825Stheraven {return begin();} 621227825Stheraven _LIBCPP_INLINE_VISIBILITY 622227825Stheraven const_iterator cend() const _NOEXCEPT 623227825Stheraven {return end();} 624227825Stheraven _LIBCPP_INLINE_VISIBILITY 625227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 626227825Stheraven {return rbegin();} 627227825Stheraven _LIBCPP_INLINE_VISIBILITY 628227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 629227825Stheraven {return rend();} 630227825Stheraven 631227825Stheraven _LIBCPP_INLINE_VISIBILITY 632227825Stheraven size_type size() const _NOEXCEPT 633227825Stheraven {return static_cast<size_type>(this->__end_ - this->__begin_);} 634227825Stheraven _LIBCPP_INLINE_VISIBILITY 635227825Stheraven size_type capacity() const _NOEXCEPT 636227825Stheraven {return __base::capacity();} 637227825Stheraven _LIBCPP_INLINE_VISIBILITY 638227825Stheraven bool empty() const _NOEXCEPT 639227825Stheraven {return this->__begin_ == this->__end_;} 640227825Stheraven size_type max_size() const _NOEXCEPT; 641227825Stheraven void reserve(size_type __n); 642227825Stheraven void shrink_to_fit() _NOEXCEPT; 643227825Stheraven 644227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n); 645227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const; 646227825Stheraven reference at(size_type __n); 647227825Stheraven const_reference at(size_type __n) const; 648227825Stheraven 649227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() 650227825Stheraven { 651227825Stheraven _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 652227825Stheraven return *this->__begin_; 653227825Stheraven } 654227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const 655227825Stheraven { 656227825Stheraven _LIBCPP_ASSERT(!empty(), "front() called for empty vector"); 657227825Stheraven return *this->__begin_; 658227825Stheraven } 659227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() 660227825Stheraven { 661227825Stheraven _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 662227825Stheraven return *(this->__end_ - 1); 663227825Stheraven } 664227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const 665227825Stheraven { 666227825Stheraven _LIBCPP_ASSERT(!empty(), "back() called for empty vector"); 667227825Stheraven return *(this->__end_ - 1); 668227825Stheraven } 669227825Stheraven 670227825Stheraven _LIBCPP_INLINE_VISIBILITY 671227825Stheraven value_type* data() _NOEXCEPT 672227825Stheraven {return _VSTD::__to_raw_pointer(this->__begin_);} 673227825Stheraven _LIBCPP_INLINE_VISIBILITY 674227825Stheraven const value_type* data() const _NOEXCEPT 675227825Stheraven {return _VSTD::__to_raw_pointer(this->__begin_);} 676227825Stheraven 677227825Stheraven _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x); 678227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 679232950Stheraven _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x); 680227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 681227825Stheraven template <class... _Args> 682227825Stheraven void emplace_back(_Args&&... __args); 683227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 684227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 685227825Stheraven void pop_back(); 686227825Stheraven 687227825Stheraven iterator insert(const_iterator __position, const_reference __x); 688227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 689227825Stheraven iterator insert(const_iterator __position, value_type&& __x); 690227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 691227825Stheraven template <class... _Args> 692227825Stheraven iterator emplace(const_iterator __position, _Args&&... __args); 693227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 694227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 695227825Stheraven iterator insert(const_iterator __position, size_type __n, const_reference __x); 696227825Stheraven template <class _InputIterator> 697227825Stheraven typename enable_if 698227825Stheraven < 699227825Stheraven __is_input_iterator <_InputIterator>::value && 700227825Stheraven !__is_forward_iterator<_InputIterator>::value, 701227825Stheraven iterator 702227825Stheraven >::type 703227825Stheraven insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 704227825Stheraven template <class _ForwardIterator> 705227825Stheraven typename enable_if 706227825Stheraven < 707227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 708227825Stheraven iterator 709227825Stheraven >::type 710227825Stheraven insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 711227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 712227825Stheraven _LIBCPP_INLINE_VISIBILITY 713227825Stheraven iterator insert(const_iterator __position, initializer_list<value_type> __il) 714227825Stheraven {return insert(__position, __il.begin(), __il.end());} 715227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 716227825Stheraven 717227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 718227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 719227825Stheraven 720227825Stheraven _LIBCPP_INLINE_VISIBILITY 721227825Stheraven void clear() _NOEXCEPT 722227825Stheraven { 723227825Stheraven __base::clear(); 724227825Stheraven __invalidate_all_iterators(); 725227825Stheraven } 726227825Stheraven 727227825Stheraven void resize(size_type __sz); 728227825Stheraven void resize(size_type __sz, const_reference __x); 729227825Stheraven 730227825Stheraven void swap(vector&) 731227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 732227825Stheraven __is_nothrow_swappable<allocator_type>::value); 733227825Stheraven 734227825Stheraven bool __invariants() const; 735227825Stheraven 736227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 737227825Stheraven 738227825Stheraven bool __dereferenceable(const const_iterator* __i) const; 739227825Stheraven bool __decrementable(const const_iterator* __i) const; 740227825Stheraven bool __addable(const const_iterator* __i, ptrdiff_t __n) const; 741227825Stheraven bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const; 742227825Stheraven 743227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 744227825Stheraven 745227825Stheravenprivate: 746227825Stheraven _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 747227825Stheraven void allocate(size_type __n); 748227825Stheraven void deallocate() _NOEXCEPT; 749227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 750227825Stheraven void __construct_at_end(size_type __n); 751227825Stheraven void __construct_at_end(size_type __n, const_reference __x); 752227825Stheraven template <class _ForwardIterator> 753227825Stheraven typename enable_if 754227825Stheraven < 755227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 756227825Stheraven void 757227825Stheraven >::type 758227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 759227825Stheraven void __move_construct_at_end(pointer __first, pointer __last); 760227825Stheraven void __append(size_type __n); 761227825Stheraven void __append(size_type __n, const_reference __x); 762227825Stheraven _LIBCPP_INLINE_VISIBILITY 763227825Stheraven iterator __make_iter(pointer __p) _NOEXCEPT; 764227825Stheraven _LIBCPP_INLINE_VISIBILITY 765227825Stheraven const_iterator __make_iter(const_pointer __p) const _NOEXCEPT; 766227825Stheraven void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v); 767227825Stheraven pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p); 768227825Stheraven void __move_range(pointer __from_s, pointer __from_e, pointer __to); 769227825Stheraven void __move_assign(vector& __c, true_type) 770227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 771227825Stheraven void __move_assign(vector& __c, false_type); 772227825Stheraven _LIBCPP_INLINE_VISIBILITY 773227825Stheraven void __destruct_at_end(const_pointer __new_last) _NOEXCEPT 774227825Stheraven { 775227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 776227825Stheraven __c_node* __c = __get_db()->__find_c_and_lock(this); 777227825Stheraven for (__i_node** __p = __c->end_; __p != __c->beg_; ) 778227825Stheraven { 779227825Stheraven --__p; 780227825Stheraven const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_); 781227825Stheraven if (__i->base() > __new_last) 782227825Stheraven { 783227825Stheraven (*__p)->__c_ = nullptr; 784227825Stheraven if (--__c->end_ != __p) 785227825Stheraven memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*)); 786227825Stheraven } 787227825Stheraven } 788227825Stheraven __get_db()->unlock(); 789227825Stheraven#endif 790227825Stheraven __base::__destruct_at_end(__new_last); 791227825Stheraven } 792232950Stheraven template <class _Up> 793232950Stheraven void 794232950Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 795232950Stheraven __push_back_slow_path(_Up&& __x); 796232950Stheraven#else 797232950Stheraven __push_back_slow_path(_Up& __x); 798232950Stheraven#endif 799232950Stheraven#if !defined(_LIBCPP_HAS_NO_VARIADICS) && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) 800232950Stheraven template <class... _Args> 801232950Stheraven void 802232950Stheraven __emplace_back_slow_path(_Args&&... __args); 803232950Stheraven#endif 804227825Stheraven}; 805227825Stheraven 806227825Stheraventemplate <class _Tp, class _Allocator> 807227825Stheravenvoid 808227825Stheravenvector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) 809227825Stheraven{ 810232950Stheraven __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, this->__end_, __v.__begin_); 811227825Stheraven _VSTD::swap(this->__begin_, __v.__begin_); 812227825Stheraven _VSTD::swap(this->__end_, __v.__end_); 813227825Stheraven _VSTD::swap(this->__end_cap(), __v.__end_cap()); 814227825Stheraven __v.__first_ = __v.__begin_; 815227825Stheraven __invalidate_all_iterators(); 816227825Stheraven} 817227825Stheraven 818227825Stheraventemplate <class _Tp, class _Allocator> 819227825Stheraventypename vector<_Tp, _Allocator>::pointer 820227825Stheravenvector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) 821227825Stheraven{ 822227825Stheraven pointer __r = __v.__begin_; 823232950Stheraven __alloc_traits::__construct_backward(this->__alloc(), this->__begin_, __p, __v.__begin_); 824232950Stheraven __alloc_traits::__construct_forward(this->__alloc(), __p, this->__end_, __v.__end_); 825227825Stheraven _VSTD::swap(this->__begin_, __v.__begin_); 826227825Stheraven _VSTD::swap(this->__end_, __v.__end_); 827227825Stheraven _VSTD::swap(this->__end_cap(), __v.__end_cap()); 828227825Stheraven __v.__first_ = __v.__begin_; 829227825Stheraven __invalidate_all_iterators(); 830227825Stheraven return __r; 831227825Stheraven} 832227825Stheraven 833227825Stheraven// Allocate space for __n objects 834227825Stheraven// throws length_error if __n > max_size() 835227825Stheraven// throws (probably bad_alloc) if memory run out 836227825Stheraven// Precondition: __begin_ == __end_ == __end_cap() == 0 837227825Stheraven// Precondition: __n > 0 838227825Stheraven// Postcondition: capacity() == __n 839227825Stheraven// Postcondition: size() == 0 840227825Stheraventemplate <class _Tp, class _Allocator> 841227825Stheravenvoid 842227825Stheravenvector<_Tp, _Allocator>::allocate(size_type __n) 843227825Stheraven{ 844227825Stheraven if (__n > max_size()) 845227825Stheraven this->__throw_length_error(); 846227825Stheraven this->__begin_ = this->__end_ = __alloc_traits::allocate(this->__alloc(), __n); 847227825Stheraven this->__end_cap() = this->__begin_ + __n; 848227825Stheraven} 849227825Stheraven 850227825Stheraventemplate <class _Tp, class _Allocator> 851227825Stheravenvoid 852227825Stheravenvector<_Tp, _Allocator>::deallocate() _NOEXCEPT 853227825Stheraven{ 854227825Stheraven if (this->__begin_ != 0) 855227825Stheraven { 856227825Stheraven clear(); 857227825Stheraven __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity()); 858227825Stheraven this->__begin_ = this->__end_ = this->__end_cap() = 0; 859227825Stheraven } 860227825Stheraven} 861227825Stheraven 862227825Stheraventemplate <class _Tp, class _Allocator> 863227825Stheraventypename vector<_Tp, _Allocator>::size_type 864227825Stheravenvector<_Tp, _Allocator>::max_size() const _NOEXCEPT 865227825Stheraven{ 866227825Stheraven return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()), numeric_limits<size_type>::max() / 2); // end() >= begin(), always 867227825Stheraven} 868227825Stheraven 869227825Stheraven// Precondition: __new_size > capacity() 870227825Stheraventemplate <class _Tp, class _Allocator> 871227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 872227825Stheraventypename vector<_Tp, _Allocator>::size_type 873227825Stheravenvector<_Tp, _Allocator>::__recommend(size_type __new_size) const 874227825Stheraven{ 875227825Stheraven const size_type __ms = max_size(); 876227825Stheraven if (__new_size > __ms) 877227825Stheraven this->__throw_length_error(); 878227825Stheraven const size_type __cap = capacity(); 879227825Stheraven if (__cap >= __ms / 2) 880227825Stheraven return __ms; 881227825Stheraven return _VSTD::max<size_type>(2*__cap, __new_size); 882227825Stheraven} 883227825Stheraven 884227825Stheraven// Default constructs __n objects starting at __end_ 885227825Stheraven// throws if construction throws 886227825Stheraven// Precondition: __n > 0 887227825Stheraven// Precondition: size() + __n <= capacity() 888227825Stheraven// Postcondition: size() == size() + __n 889227825Stheraventemplate <class _Tp, class _Allocator> 890227825Stheravenvoid 891227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(size_type __n) 892227825Stheraven{ 893227825Stheraven allocator_type& __a = this->__alloc(); 894227825Stheraven do 895227825Stheraven { 896227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_)); 897227825Stheraven ++this->__end_; 898227825Stheraven --__n; 899227825Stheraven } while (__n > 0); 900227825Stheraven} 901227825Stheraven 902227825Stheraven// Copy constructs __n objects starting at __end_ from __x 903227825Stheraven// throws if construction throws 904227825Stheraven// Precondition: __n > 0 905227825Stheraven// Precondition: size() + __n <= capacity() 906227825Stheraven// Postcondition: size() == old size() + __n 907227825Stheraven// Postcondition: [i] == __x for all i in [size() - __n, __n) 908227825Stheraventemplate <class _Tp, class _Allocator> 909227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 910227825Stheravenvoid 911227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) 912227825Stheraven{ 913227825Stheraven allocator_type& __a = this->__alloc(); 914227825Stheraven do 915227825Stheraven { 916227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), __x); 917227825Stheraven ++this->__end_; 918227825Stheraven --__n; 919227825Stheraven } while (__n > 0); 920227825Stheraven} 921227825Stheraven 922227825Stheraventemplate <class _Tp, class _Allocator> 923227825Stheraventemplate <class _ForwardIterator> 924227825Stheraventypename enable_if 925227825Stheraven< 926227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 927227825Stheraven void 928227825Stheraven>::type 929227825Stheravenvector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 930227825Stheraven{ 931227825Stheraven allocator_type& __a = this->__alloc(); 932227825Stheraven for (; __first != __last; ++__first) 933227825Stheraven { 934227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), *__first); 935227825Stheraven ++this->__end_; 936227825Stheraven } 937227825Stheraven} 938227825Stheraven 939227825Stheraventemplate <class _Tp, class _Allocator> 940227825Stheravenvoid 941227825Stheravenvector<_Tp, _Allocator>::__move_construct_at_end(pointer __first, pointer __last) 942227825Stheraven{ 943227825Stheraven allocator_type& __a = this->__alloc(); 944227825Stheraven for (; __first != __last; ++__first) 945227825Stheraven { 946227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), 947227825Stheraven _VSTD::move(*__first)); 948227825Stheraven ++this->__end_; 949227825Stheraven } 950227825Stheraven} 951227825Stheraven 952227825Stheraven// Default constructs __n objects starting at __end_ 953227825Stheraven// throws if construction throws 954227825Stheraven// Postcondition: size() == size() + __n 955227825Stheraven// Exception safety: strong. 956227825Stheraventemplate <class _Tp, class _Allocator> 957227825Stheravenvoid 958227825Stheravenvector<_Tp, _Allocator>::__append(size_type __n) 959227825Stheraven{ 960227825Stheraven if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 961227825Stheraven this->__construct_at_end(__n); 962227825Stheraven else 963227825Stheraven { 964227825Stheraven allocator_type& __a = this->__alloc(); 965227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 966227825Stheraven __v.__construct_at_end(__n); 967227825Stheraven __swap_out_circular_buffer(__v); 968227825Stheraven } 969227825Stheraven} 970227825Stheraven 971227825Stheraven// Default constructs __n objects starting at __end_ 972227825Stheraven// throws if construction throws 973227825Stheraven// Postcondition: size() == size() + __n 974227825Stheraven// Exception safety: strong. 975227825Stheraventemplate <class _Tp, class _Allocator> 976227825Stheravenvoid 977227825Stheravenvector<_Tp, _Allocator>::__append(size_type __n, const_reference __x) 978227825Stheraven{ 979227825Stheraven if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) 980227825Stheraven this->__construct_at_end(__n, __x); 981227825Stheraven else 982227825Stheraven { 983227825Stheraven allocator_type& __a = this->__alloc(); 984227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a); 985227825Stheraven __v.__construct_at_end(__n, __x); 986227825Stheraven __swap_out_circular_buffer(__v); 987227825Stheraven } 988227825Stheraven} 989227825Stheraven 990227825Stheraventemplate <class _Tp, class _Allocator> 991227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n) 992227825Stheraven{ 993227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 994227825Stheraven __get_db()->__insert_c(this); 995227825Stheraven#endif 996227825Stheraven if (__n > 0) 997227825Stheraven { 998227825Stheraven allocate(__n); 999227825Stheraven __construct_at_end(__n); 1000227825Stheraven } 1001227825Stheraven} 1002227825Stheraven 1003227825Stheraventemplate <class _Tp, class _Allocator> 1004227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n, const_reference __x) 1005227825Stheraven{ 1006227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1007227825Stheraven __get_db()->__insert_c(this); 1008227825Stheraven#endif 1009227825Stheraven if (__n > 0) 1010227825Stheraven { 1011227825Stheraven allocate(__n); 1012227825Stheraven __construct_at_end(__n, __x); 1013227825Stheraven } 1014227825Stheraven} 1015227825Stheraven 1016227825Stheraventemplate <class _Tp, class _Allocator> 1017227825Stheravenvector<_Tp, _Allocator>::vector(size_type __n, const_reference __x, const allocator_type& __a) 1018227825Stheraven : __base(__a) 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, __x); 1027227825Stheraven } 1028227825Stheraven} 1029227825Stheraven 1030227825Stheraventemplate <class _Tp, class _Allocator> 1031227825Stheraventemplate <class _InputIterator> 1032227825Stheravenvector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 1033227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 1034227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 1035227825Stheraven{ 1036227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1037227825Stheraven __get_db()->__insert_c(this); 1038227825Stheraven#endif 1039227825Stheraven for (; __first != __last; ++__first) 1040227825Stheraven push_back(*__first); 1041227825Stheraven} 1042227825Stheraven 1043227825Stheraventemplate <class _Tp, class _Allocator> 1044227825Stheraventemplate <class _InputIterator> 1045227825Stheravenvector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 1046227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 1047227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 1048227825Stheraven : __base(__a) 1049227825Stheraven{ 1050227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1051227825Stheraven __get_db()->__insert_c(this); 1052227825Stheraven#endif 1053227825Stheraven for (; __first != __last; ++__first) 1054227825Stheraven push_back(*__first); 1055227825Stheraven} 1056227825Stheraven 1057227825Stheraventemplate <class _Tp, class _Allocator> 1058227825Stheraventemplate <class _ForwardIterator> 1059227825Stheravenvector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 1060227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 1061227825Stheraven{ 1062227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1063227825Stheraven __get_db()->__insert_c(this); 1064227825Stheraven#endif 1065227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1066227825Stheraven if (__n > 0) 1067227825Stheraven { 1068227825Stheraven allocate(__n); 1069227825Stheraven __construct_at_end(__first, __last); 1070227825Stheraven } 1071227825Stheraven} 1072227825Stheraven 1073227825Stheraventemplate <class _Tp, class _Allocator> 1074227825Stheraventemplate <class _ForwardIterator> 1075227825Stheravenvector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 1076227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 1077227825Stheraven : __base(__a) 1078227825Stheraven{ 1079227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1080227825Stheraven __get_db()->__insert_c(this); 1081227825Stheraven#endif 1082227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 1083227825Stheraven if (__n > 0) 1084227825Stheraven { 1085227825Stheraven allocate(__n); 1086227825Stheraven __construct_at_end(__first, __last); 1087227825Stheraven } 1088227825Stheraven} 1089227825Stheraven 1090227825Stheraventemplate <class _Tp, class _Allocator> 1091227825Stheravenvector<_Tp, _Allocator>::vector(const vector& __x) 1092227825Stheraven : __base(__alloc_traits::select_on_container_copy_construction(__x.__alloc())) 1093227825Stheraven{ 1094227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1095227825Stheraven __get_db()->__insert_c(this); 1096227825Stheraven#endif 1097227825Stheraven size_type __n = __x.size(); 1098227825Stheraven if (__n > 0) 1099227825Stheraven { 1100227825Stheraven allocate(__n); 1101227825Stheraven __construct_at_end(__x.__begin_, __x.__end_); 1102227825Stheraven } 1103227825Stheraven} 1104227825Stheraven 1105227825Stheraventemplate <class _Tp, class _Allocator> 1106227825Stheravenvector<_Tp, _Allocator>::vector(const vector& __x, const allocator_type& __a) 1107227825Stheraven : __base(__a) 1108227825Stheraven{ 1109227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1110227825Stheraven __get_db()->__insert_c(this); 1111227825Stheraven#endif 1112227825Stheraven size_type __n = __x.size(); 1113227825Stheraven if (__n > 0) 1114227825Stheraven { 1115227825Stheraven allocate(__n); 1116227825Stheraven __construct_at_end(__x.__begin_, __x.__end_); 1117227825Stheraven } 1118227825Stheraven} 1119227825Stheraven 1120227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1121227825Stheraven 1122227825Stheraventemplate <class _Tp, class _Allocator> 1123227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1124227825Stheravenvector<_Tp, _Allocator>::vector(vector&& __x) 1125227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 1126227825Stheraven : __base(_VSTD::move(__x.__alloc())) 1127227825Stheraven{ 1128227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1129227825Stheraven __get_db()->__insert_c(this); 1130227825Stheraven __get_db()->swap(this, &__x); 1131227825Stheraven#endif 1132227825Stheraven this->__begin_ = __x.__begin_; 1133227825Stheraven this->__end_ = __x.__end_; 1134227825Stheraven this->__end_cap() = __x.__end_cap(); 1135227825Stheraven __x.__begin_ = __x.__end_ = __x.__end_cap() = 0; 1136227825Stheraven} 1137227825Stheraven 1138227825Stheraventemplate <class _Tp, class _Allocator> 1139227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1140227825Stheravenvector<_Tp, _Allocator>::vector(vector&& __x, const allocator_type& __a) 1141227825Stheraven : __base(__a) 1142227825Stheraven{ 1143227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1144227825Stheraven __get_db()->__insert_c(this); 1145227825Stheraven#endif 1146227825Stheraven if (__a == __x.__alloc()) 1147227825Stheraven { 1148227825Stheraven this->__begin_ = __x.__begin_; 1149227825Stheraven this->__end_ = __x.__end_; 1150227825Stheraven this->__end_cap() = __x.__end_cap(); 1151227825Stheraven __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr; 1152227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1153227825Stheraven __get_db()->swap(this, &__x); 1154227825Stheraven#endif 1155227825Stheraven } 1156227825Stheraven else 1157227825Stheraven { 1158232950Stheraven typedef move_iterator<iterator> _Ip; 1159232950Stheraven assign(_Ip(__x.begin()), _Ip(__x.end())); 1160227825Stheraven } 1161227825Stheraven} 1162227825Stheraven 1163227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1164227825Stheraven 1165227825Stheraventemplate <class _Tp, class _Allocator> 1166227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1167227825Stheravenvector<_Tp, _Allocator>::vector(initializer_list<value_type> __il) 1168227825Stheraven{ 1169227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1170227825Stheraven __get_db()->__insert_c(this); 1171227825Stheraven#endif 1172227825Stheraven if (__il.size() > 0) 1173227825Stheraven { 1174227825Stheraven allocate(__il.size()); 1175227825Stheraven __construct_at_end(__il.begin(), __il.end()); 1176227825Stheraven } 1177227825Stheraven} 1178227825Stheraven 1179227825Stheraventemplate <class _Tp, class _Allocator> 1180227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1181227825Stheravenvector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 1182227825Stheraven : __base(__a) 1183227825Stheraven{ 1184227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1185227825Stheraven __get_db()->__insert_c(this); 1186227825Stheraven#endif 1187227825Stheraven if (__il.size() > 0) 1188227825Stheraven { 1189227825Stheraven allocate(__il.size()); 1190227825Stheraven __construct_at_end(__il.begin(), __il.end()); 1191227825Stheraven } 1192227825Stheraven} 1193227825Stheraven 1194227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 1195227825Stheraven 1196227825Stheraventemplate <class _Tp, class _Allocator> 1197227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1198227825Stheravenvector<_Tp, _Allocator>& 1199227825Stheravenvector<_Tp, _Allocator>::operator=(vector&& __x) 1200227825Stheraven _NOEXCEPT_( 1201227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 1202227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 1203227825Stheraven{ 1204227825Stheraven __move_assign(__x, integral_constant<bool, 1205227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value>()); 1206227825Stheraven return *this; 1207227825Stheraven} 1208227825Stheraven 1209227825Stheraventemplate <class _Tp, class _Allocator> 1210227825Stheravenvoid 1211227825Stheravenvector<_Tp, _Allocator>::__move_assign(vector& __c, false_type) 1212227825Stheraven{ 1213227825Stheraven if (__base::__alloc() != __c.__alloc()) 1214227825Stheraven { 1215232950Stheraven typedef move_iterator<iterator> _Ip; 1216232950Stheraven assign(_Ip(__c.begin()), _Ip(__c.end())); 1217227825Stheraven } 1218227825Stheraven else 1219227825Stheraven __move_assign(__c, true_type()); 1220227825Stheraven} 1221227825Stheraven 1222227825Stheraventemplate <class _Tp, class _Allocator> 1223227825Stheravenvoid 1224227825Stheravenvector<_Tp, _Allocator>::__move_assign(vector& __c, true_type) 1225227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 1226227825Stheraven{ 1227227825Stheraven deallocate(); 1228227825Stheraven this->__begin_ = __c.__begin_; 1229227825Stheraven this->__end_ = __c.__end_; 1230227825Stheraven this->__end_cap() = __c.__end_cap(); 1231227825Stheraven __base::__move_assign_alloc(__c); 1232227825Stheraven __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr; 1233227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1234227825Stheraven __get_db()->swap(this, &__c); 1235227825Stheraven#endif 1236227825Stheraven} 1237227825Stheraven 1238227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1239227825Stheraven 1240227825Stheraventemplate <class _Tp, class _Allocator> 1241227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1242227825Stheravenvector<_Tp, _Allocator>& 1243227825Stheravenvector<_Tp, _Allocator>::operator=(const vector& __x) 1244227825Stheraven{ 1245227825Stheraven if (this != &__x) 1246227825Stheraven { 1247227825Stheraven __base::__copy_assign_alloc(__x); 1248227825Stheraven assign(__x.__begin_, __x.__end_); 1249227825Stheraven } 1250227825Stheraven return *this; 1251227825Stheraven} 1252227825Stheraven 1253227825Stheraventemplate <class _Tp, class _Allocator> 1254227825Stheraventemplate <class _InputIterator> 1255227825Stheraventypename enable_if 1256227825Stheraven< 1257227825Stheraven __is_input_iterator <_InputIterator>::value && 1258227825Stheraven !__is_forward_iterator<_InputIterator>::value, 1259227825Stheraven void 1260227825Stheraven>::type 1261227825Stheravenvector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 1262227825Stheraven{ 1263227825Stheraven clear(); 1264227825Stheraven for (; __first != __last; ++__first) 1265227825Stheraven push_back(*__first); 1266227825Stheraven} 1267227825Stheraven 1268227825Stheraventemplate <class _Tp, class _Allocator> 1269227825Stheraventemplate <class _ForwardIterator> 1270227825Stheraventypename enable_if 1271227825Stheraven< 1272227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 1273227825Stheraven void 1274227825Stheraven>::type 1275227825Stheravenvector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 1276227825Stheraven{ 1277227825Stheraven typename iterator_traits<_ForwardIterator>::difference_type __new_size = _VSTD::distance(__first, __last); 1278227825Stheraven if (static_cast<size_type>(__new_size) <= capacity()) 1279227825Stheraven { 1280227825Stheraven _ForwardIterator __mid = __last; 1281227825Stheraven bool __growing = false; 1282227825Stheraven if (static_cast<size_type>(__new_size) > size()) 1283227825Stheraven { 1284227825Stheraven __growing = true; 1285227825Stheraven __mid = __first; 1286227825Stheraven _VSTD::advance(__mid, size()); 1287227825Stheraven } 1288227825Stheraven pointer __m = _VSTD::copy(__first, __mid, this->__begin_); 1289227825Stheraven if (__growing) 1290227825Stheraven __construct_at_end(__mid, __last); 1291227825Stheraven else 1292227825Stheraven this->__destruct_at_end(__m); 1293227825Stheraven } 1294227825Stheraven else 1295227825Stheraven { 1296227825Stheraven deallocate(); 1297227825Stheraven allocate(__recommend(static_cast<size_type>(__new_size))); 1298227825Stheraven __construct_at_end(__first, __last); 1299227825Stheraven } 1300227825Stheraven} 1301227825Stheraven 1302227825Stheraventemplate <class _Tp, class _Allocator> 1303227825Stheravenvoid 1304227825Stheravenvector<_Tp, _Allocator>::assign(size_type __n, const_reference __u) 1305227825Stheraven{ 1306227825Stheraven if (__n <= capacity()) 1307227825Stheraven { 1308227825Stheraven size_type __s = size(); 1309227825Stheraven _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u); 1310227825Stheraven if (__n > __s) 1311227825Stheraven __construct_at_end(__n - __s, __u); 1312227825Stheraven else 1313227825Stheraven this->__destruct_at_end(this->__begin_ + __n); 1314227825Stheraven } 1315227825Stheraven else 1316227825Stheraven { 1317227825Stheraven deallocate(); 1318227825Stheraven allocate(__recommend(static_cast<size_type>(__n))); 1319227825Stheraven __construct_at_end(__n, __u); 1320227825Stheraven } 1321227825Stheraven} 1322227825Stheraven 1323227825Stheraventemplate <class _Tp, class _Allocator> 1324227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1325227825Stheraventypename vector<_Tp, _Allocator>::iterator 1326227825Stheravenvector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT 1327227825Stheraven{ 1328227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1329227825Stheraven return iterator(this, __p); 1330227825Stheraven#else 1331227825Stheraven return iterator(__p); 1332227825Stheraven#endif 1333227825Stheraven} 1334227825Stheraven 1335227825Stheraventemplate <class _Tp, class _Allocator> 1336227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1337227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1338227825Stheravenvector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT 1339227825Stheraven{ 1340227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1341227825Stheraven return const_iterator(this, __p); 1342227825Stheraven#else 1343227825Stheraven return const_iterator(__p); 1344227825Stheraven#endif 1345227825Stheraven} 1346227825Stheraven 1347227825Stheraventemplate <class _Tp, class _Allocator> 1348227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1349227825Stheraventypename vector<_Tp, _Allocator>::iterator 1350227825Stheravenvector<_Tp, _Allocator>::begin() _NOEXCEPT 1351227825Stheraven{ 1352227825Stheraven return __make_iter(this->__begin_); 1353227825Stheraven} 1354227825Stheraven 1355227825Stheraventemplate <class _Tp, class _Allocator> 1356227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1357227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1358227825Stheravenvector<_Tp, _Allocator>::begin() const _NOEXCEPT 1359227825Stheraven{ 1360227825Stheraven return __make_iter(this->__begin_); 1361227825Stheraven} 1362227825Stheraven 1363227825Stheraventemplate <class _Tp, class _Allocator> 1364227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1365227825Stheraventypename vector<_Tp, _Allocator>::iterator 1366227825Stheravenvector<_Tp, _Allocator>::end() _NOEXCEPT 1367227825Stheraven{ 1368227825Stheraven return __make_iter(this->__end_); 1369227825Stheraven} 1370227825Stheraven 1371227825Stheraventemplate <class _Tp, class _Allocator> 1372227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1373227825Stheraventypename vector<_Tp, _Allocator>::const_iterator 1374227825Stheravenvector<_Tp, _Allocator>::end() const _NOEXCEPT 1375227825Stheraven{ 1376227825Stheraven return __make_iter(this->__end_); 1377227825Stheraven} 1378227825Stheraven 1379227825Stheraventemplate <class _Tp, class _Allocator> 1380227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1381227825Stheraventypename vector<_Tp, _Allocator>::reference 1382227825Stheravenvector<_Tp, _Allocator>::operator[](size_type __n) 1383227825Stheraven{ 1384227825Stheraven _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1385227825Stheraven return this->__begin_[__n]; 1386227825Stheraven} 1387227825Stheraven 1388227825Stheraventemplate <class _Tp, class _Allocator> 1389227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1390227825Stheraventypename vector<_Tp, _Allocator>::const_reference 1391227825Stheravenvector<_Tp, _Allocator>::operator[](size_type __n) const 1392227825Stheraven{ 1393227825Stheraven _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds"); 1394227825Stheraven return this->__begin_[__n]; 1395227825Stheraven} 1396227825Stheraven 1397227825Stheraventemplate <class _Tp, class _Allocator> 1398227825Stheraventypename vector<_Tp, _Allocator>::reference 1399227825Stheravenvector<_Tp, _Allocator>::at(size_type __n) 1400227825Stheraven{ 1401227825Stheraven if (__n >= size()) 1402227825Stheraven this->__throw_out_of_range(); 1403227825Stheraven return this->__begin_[__n]; 1404227825Stheraven} 1405227825Stheraven 1406227825Stheraventemplate <class _Tp, class _Allocator> 1407227825Stheraventypename vector<_Tp, _Allocator>::const_reference 1408227825Stheravenvector<_Tp, _Allocator>::at(size_type __n) const 1409227825Stheraven{ 1410227825Stheraven if (__n >= size()) 1411227825Stheraven this->__throw_out_of_range(); 1412227825Stheraven return this->__begin_[__n]; 1413227825Stheraven} 1414227825Stheraven 1415227825Stheraventemplate <class _Tp, class _Allocator> 1416227825Stheravenvoid 1417227825Stheravenvector<_Tp, _Allocator>::reserve(size_type __n) 1418227825Stheraven{ 1419227825Stheraven if (__n > capacity()) 1420227825Stheraven { 1421227825Stheraven allocator_type& __a = this->__alloc(); 1422227825Stheraven __split_buffer<value_type, allocator_type&> __v(__n, size(), __a); 1423227825Stheraven __swap_out_circular_buffer(__v); 1424227825Stheraven } 1425227825Stheraven} 1426227825Stheraven 1427227825Stheraventemplate <class _Tp, class _Allocator> 1428227825Stheravenvoid 1429227825Stheravenvector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT 1430227825Stheraven{ 1431227825Stheraven if (capacity() > size()) 1432227825Stheraven { 1433227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1434227825Stheraven try 1435227825Stheraven { 1436227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1437227825Stheraven allocator_type& __a = this->__alloc(); 1438227825Stheraven __split_buffer<value_type, allocator_type&> __v(size(), size(), __a); 1439227825Stheraven __swap_out_circular_buffer(__v); 1440227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1441227825Stheraven } 1442227825Stheraven catch (...) 1443227825Stheraven { 1444227825Stheraven } 1445227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1446227825Stheraven } 1447227825Stheraven} 1448227825Stheraven 1449227825Stheraventemplate <class _Tp, class _Allocator> 1450232950Stheraventemplate <class _Up> 1451227825Stheravenvoid 1452232950Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1453232950Stheravenvector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) 1454232950Stheraven#else 1455232950Stheravenvector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x) 1456232950Stheraven#endif 1457232950Stheraven{ 1458232950Stheraven allocator_type& __a = this->__alloc(); 1459232950Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1460232950Stheraven // __v.push_back(_VSTD::forward<_Up>(__x)); 1461246487Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Up>(__x)); 1462246487Stheraven __v.__end_++; 1463232950Stheraven __swap_out_circular_buffer(__v); 1464232950Stheraven} 1465232950Stheraven 1466232950Stheraventemplate <class _Tp, class _Allocator> 1467232950Stheraven_LIBCPP_INLINE_VISIBILITY inline 1468232950Stheravenvoid 1469227825Stheravenvector<_Tp, _Allocator>::push_back(const_reference __x) 1470227825Stheraven{ 1471232950Stheraven if (this->__end_ != this->__end_cap()) 1472227825Stheraven { 1473227825Stheraven __alloc_traits::construct(this->__alloc(), 1474227825Stheraven _VSTD::__to_raw_pointer(this->__end_), __x); 1475227825Stheraven ++this->__end_; 1476227825Stheraven } 1477227825Stheraven else 1478232950Stheraven __push_back_slow_path(__x); 1479227825Stheraven} 1480227825Stheraven 1481227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1482227825Stheraven 1483227825Stheraventemplate <class _Tp, class _Allocator> 1484232950Stheraven_LIBCPP_INLINE_VISIBILITY inline 1485227825Stheravenvoid 1486227825Stheravenvector<_Tp, _Allocator>::push_back(value_type&& __x) 1487227825Stheraven{ 1488227825Stheraven if (this->__end_ < this->__end_cap()) 1489227825Stheraven { 1490227825Stheraven __alloc_traits::construct(this->__alloc(), 1491227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1492227825Stheraven _VSTD::move(__x)); 1493227825Stheraven ++this->__end_; 1494227825Stheraven } 1495227825Stheraven else 1496232950Stheraven __push_back_slow_path(_VSTD::move(__x)); 1497227825Stheraven} 1498227825Stheraven 1499227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1500227825Stheraven 1501227825Stheraventemplate <class _Tp, class _Allocator> 1502227825Stheraventemplate <class... _Args> 1503227825Stheravenvoid 1504232950Stheravenvector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) 1505232950Stheraven{ 1506232950Stheraven allocator_type& __a = this->__alloc(); 1507232950Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a); 1508232950Stheraven// __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1509246487Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(__v.__end_), _VSTD::forward<_Args>(__args)...); 1510246487Stheraven __v.__end_++; 1511232950Stheraven __swap_out_circular_buffer(__v); 1512232950Stheraven} 1513232950Stheraven 1514232950Stheraventemplate <class _Tp, class _Allocator> 1515232950Stheraventemplate <class... _Args> 1516232950Stheraven_LIBCPP_INLINE_VISIBILITY inline 1517232950Stheravenvoid 1518227825Stheravenvector<_Tp, _Allocator>::emplace_back(_Args&&... __args) 1519227825Stheraven{ 1520227825Stheraven if (this->__end_ < this->__end_cap()) 1521227825Stheraven { 1522227825Stheraven __alloc_traits::construct(this->__alloc(), 1523227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1524227825Stheraven _VSTD::forward<_Args>(__args)...); 1525227825Stheraven ++this->__end_; 1526227825Stheraven } 1527227825Stheraven else 1528232950Stheraven __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); 1529227825Stheraven} 1530227825Stheraven 1531227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1532227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1533227825Stheraven 1534227825Stheraventemplate <class _Tp, class _Allocator> 1535227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1536227825Stheravenvoid 1537227825Stheravenvector<_Tp, _Allocator>::pop_back() 1538227825Stheraven{ 1539227825Stheraven _LIBCPP_ASSERT(!empty(), "vector::pop_back called for empty vector"); 1540227825Stheraven this->__destruct_at_end(this->__end_ - 1); 1541227825Stheraven} 1542227825Stheraven 1543227825Stheraventemplate <class _Tp, class _Allocator> 1544227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1545227825Stheraventypename vector<_Tp, _Allocator>::iterator 1546227825Stheravenvector<_Tp, _Allocator>::erase(const_iterator __position) 1547227825Stheraven{ 1548227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1549227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1550227825Stheraven "vector::erase(iterator) called with an iterator not" 1551227825Stheraven " referring to this vector"); 1552227825Stheraven#endif 1553227825Stheraven pointer __p = const_cast<pointer>(&*__position); 1554227825Stheraven iterator __r = __make_iter(__p); 1555227825Stheraven this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p)); 1556227825Stheraven return __r; 1557227825Stheraven} 1558227825Stheraven 1559227825Stheraventemplate <class _Tp, class _Allocator> 1560227825Stheraventypename vector<_Tp, _Allocator>::iterator 1561227825Stheravenvector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last) 1562227825Stheraven{ 1563227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1564227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__first) == this, 1565227825Stheraven "vector::erase(iterator, iterator) called with an iterator not" 1566227825Stheraven " referring to this vector"); 1567227825Stheraven#endif 1568227825Stheraven _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range"); 1569227825Stheraven pointer __p = this->__begin_ + (__first - begin()); 1570227825Stheraven iterator __r = __make_iter(__p); 1571227825Stheraven this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p)); 1572227825Stheraven return __r; 1573227825Stheraven} 1574227825Stheraven 1575227825Stheraventemplate <class _Tp, class _Allocator> 1576227825Stheravenvoid 1577227825Stheravenvector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to) 1578227825Stheraven{ 1579227825Stheraven pointer __old_last = this->__end_; 1580227825Stheraven difference_type __n = __old_last - __to; 1581227825Stheraven for (pointer __i = __from_s + __n; __i < __from_e; ++__i, ++this->__end_) 1582227825Stheraven __alloc_traits::construct(this->__alloc(), 1583227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1584227825Stheraven _VSTD::move(*__i)); 1585227825Stheraven _VSTD::move_backward(__from_s, __from_s + __n, __old_last); 1586227825Stheraven} 1587227825Stheraven 1588227825Stheraventemplate <class _Tp, class _Allocator> 1589227825Stheraventypename vector<_Tp, _Allocator>::iterator 1590227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x) 1591227825Stheraven{ 1592227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1593227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1594227825Stheraven "vector::insert(iterator, x) called with an iterator not" 1595227825Stheraven " referring to this vector"); 1596227825Stheraven#endif 1597227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1598227825Stheraven if (this->__end_ < this->__end_cap()) 1599227825Stheraven { 1600227825Stheraven if (__p == this->__end_) 1601227825Stheraven { 1602227825Stheraven __alloc_traits::construct(this->__alloc(), 1603227825Stheraven _VSTD::__to_raw_pointer(this->__end_), __x); 1604227825Stheraven ++this->__end_; 1605227825Stheraven } 1606227825Stheraven else 1607227825Stheraven { 1608227825Stheraven __move_range(__p, this->__end_, __p + 1); 1609227825Stheraven const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1610227825Stheraven if (__p <= __xr && __xr < this->__end_) 1611227825Stheraven ++__xr; 1612227825Stheraven *__p = *__xr; 1613227825Stheraven } 1614227825Stheraven } 1615227825Stheraven else 1616227825Stheraven { 1617227825Stheraven allocator_type& __a = this->__alloc(); 1618227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1619227825Stheraven __v.push_back(__x); 1620227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1621227825Stheraven } 1622227825Stheraven return __make_iter(__p); 1623227825Stheraven} 1624227825Stheraven 1625227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 1626227825Stheraven 1627227825Stheraventemplate <class _Tp, class _Allocator> 1628227825Stheraventypename vector<_Tp, _Allocator>::iterator 1629227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x) 1630227825Stheraven{ 1631227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1632227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1633227825Stheraven "vector::insert(iterator, x) called with an iterator not" 1634227825Stheraven " referring to this vector"); 1635227825Stheraven#endif 1636227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1637227825Stheraven if (this->__end_ < this->__end_cap()) 1638227825Stheraven { 1639227825Stheraven if (__p == this->__end_) 1640227825Stheraven { 1641227825Stheraven __alloc_traits::construct(this->__alloc(), 1642227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1643227825Stheraven _VSTD::move(__x)); 1644227825Stheraven ++this->__end_; 1645227825Stheraven } 1646227825Stheraven else 1647227825Stheraven { 1648227825Stheraven __move_range(__p, this->__end_, __p + 1); 1649227825Stheraven *__p = _VSTD::move(__x); 1650227825Stheraven } 1651227825Stheraven } 1652227825Stheraven else 1653227825Stheraven { 1654227825Stheraven allocator_type& __a = this->__alloc(); 1655227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1656227825Stheraven __v.push_back(_VSTD::move(__x)); 1657227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1658227825Stheraven } 1659227825Stheraven return __make_iter(__p); 1660227825Stheraven} 1661227825Stheraven 1662227825Stheraven#ifndef _LIBCPP_HAS_NO_VARIADICS 1663227825Stheraven 1664227825Stheraventemplate <class _Tp, class _Allocator> 1665227825Stheraventemplate <class... _Args> 1666227825Stheraventypename vector<_Tp, _Allocator>::iterator 1667227825Stheravenvector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args) 1668227825Stheraven{ 1669227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1670227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1671227825Stheraven "vector::emplace(iterator, x) called with an iterator not" 1672227825Stheraven " referring to this vector"); 1673227825Stheraven#endif 1674227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1675227825Stheraven if (this->__end_ < this->__end_cap()) 1676227825Stheraven { 1677227825Stheraven if (__p == this->__end_) 1678227825Stheraven { 1679227825Stheraven __alloc_traits::construct(this->__alloc(), 1680227825Stheraven _VSTD::__to_raw_pointer(this->__end_), 1681227825Stheraven _VSTD::forward<_Args>(__args)...); 1682227825Stheraven ++this->__end_; 1683227825Stheraven } 1684227825Stheraven else 1685227825Stheraven { 1686241903Sdim value_type __tmp(_VSTD::forward<_Args>(__args)...); 1687227825Stheraven __move_range(__p, this->__end_, __p + 1); 1688241903Sdim *__p = _VSTD::move(__tmp); 1689227825Stheraven } 1690227825Stheraven } 1691227825Stheraven else 1692227825Stheraven { 1693227825Stheraven allocator_type& __a = this->__alloc(); 1694227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a); 1695227825Stheraven __v.emplace_back(_VSTD::forward<_Args>(__args)...); 1696227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1697227825Stheraven } 1698227825Stheraven return __make_iter(__p); 1699227825Stheraven} 1700227825Stheraven 1701227825Stheraven#endif // _LIBCPP_HAS_NO_VARIADICS 1702227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 1703227825Stheraven 1704227825Stheraventemplate <class _Tp, class _Allocator> 1705227825Stheraventypename vector<_Tp, _Allocator>::iterator 1706227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x) 1707227825Stheraven{ 1708227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1709227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1710227825Stheraven "vector::insert(iterator, n, x) called with an iterator not" 1711227825Stheraven " referring to this vector"); 1712227825Stheraven#endif 1713227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1714227825Stheraven if (__n > 0) 1715227825Stheraven { 1716227825Stheraven if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_)) 1717227825Stheraven { 1718227825Stheraven size_type __old_n = __n; 1719227825Stheraven pointer __old_last = this->__end_; 1720227825Stheraven if (__n > static_cast<size_type>(this->__end_ - __p)) 1721227825Stheraven { 1722227825Stheraven size_type __cx = __n - (this->__end_ - __p); 1723227825Stheraven __construct_at_end(__cx, __x); 1724227825Stheraven __n -= __cx; 1725227825Stheraven } 1726227825Stheraven if (__n > 0) 1727227825Stheraven { 1728227825Stheraven __move_range(__p, __old_last, __p + __old_n); 1729227825Stheraven const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x); 1730227825Stheraven if (__p <= __xr && __xr < this->__end_) 1731227825Stheraven __xr += __old_n; 1732227825Stheraven _VSTD::fill_n(__p, __n, *__xr); 1733227825Stheraven } 1734227825Stheraven } 1735227825Stheraven else 1736227825Stheraven { 1737227825Stheraven allocator_type& __a = this->__alloc(); 1738227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1739227825Stheraven __v.__construct_at_end(__n, __x); 1740227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1741227825Stheraven } 1742227825Stheraven } 1743227825Stheraven return __make_iter(__p); 1744227825Stheraven} 1745227825Stheraven 1746227825Stheraventemplate <class _Tp, class _Allocator> 1747227825Stheraventemplate <class _InputIterator> 1748227825Stheraventypename enable_if 1749227825Stheraven< 1750227825Stheraven __is_input_iterator <_InputIterator>::value && 1751227825Stheraven !__is_forward_iterator<_InputIterator>::value, 1752227825Stheraven typename vector<_Tp, _Allocator>::iterator 1753227825Stheraven>::type 1754227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 1755227825Stheraven{ 1756227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1757227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1758227825Stheraven "vector::insert(iterator, range) called with an iterator not" 1759227825Stheraven " referring to this vector"); 1760227825Stheraven#endif 1761227825Stheraven difference_type __off = __position - begin(); 1762227825Stheraven pointer __p = this->__begin_ + __off; 1763227825Stheraven allocator_type& __a = this->__alloc(); 1764227825Stheraven pointer __old_last = this->__end_; 1765227825Stheraven for (; this->__end_ != this->__end_cap() && __first != __last; ++__first) 1766227825Stheraven { 1767227825Stheraven __alloc_traits::construct(__a, _VSTD::__to_raw_pointer(this->__end_), 1768227825Stheraven *__first); 1769227825Stheraven ++this->__end_; 1770227825Stheraven } 1771227825Stheraven __split_buffer<value_type, allocator_type&> __v(__a); 1772227825Stheraven if (__first != __last) 1773227825Stheraven { 1774227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1775227825Stheraven try 1776227825Stheraven { 1777227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1778227825Stheraven __v.__construct_at_end(__first, __last); 1779227825Stheraven difference_type __old_size = __old_last - this->__begin_; 1780227825Stheraven difference_type __old_p = __p - this->__begin_; 1781227825Stheraven reserve(__recommend(size() + __v.size())); 1782227825Stheraven __p = this->__begin_ + __old_p; 1783227825Stheraven __old_last = this->__begin_ + __old_size; 1784227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 1785227825Stheraven } 1786227825Stheraven catch (...) 1787227825Stheraven { 1788227825Stheraven erase(__make_iter(__old_last), end()); 1789227825Stheraven throw; 1790227825Stheraven } 1791227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 1792227825Stheraven } 1793227825Stheraven __p = _VSTD::rotate(__p, __old_last, this->__end_); 1794227825Stheraven insert(__make_iter(__p), make_move_iterator(__v.begin()), 1795227825Stheraven make_move_iterator(__v.end())); 1796227825Stheraven return begin() + __off; 1797227825Stheraven} 1798227825Stheraven 1799227825Stheraventemplate <class _Tp, class _Allocator> 1800227825Stheraventemplate <class _ForwardIterator> 1801227825Stheraventypename enable_if 1802227825Stheraven< 1803227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 1804227825Stheraven typename vector<_Tp, _Allocator>::iterator 1805227825Stheraven>::type 1806227825Stheravenvector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 1807227825Stheraven{ 1808227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1809227825Stheraven _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__position) == this, 1810227825Stheraven "vector::insert(iterator, range) called with an iterator not" 1811227825Stheraven " referring to this vector"); 1812227825Stheraven#endif 1813227825Stheraven pointer __p = this->__begin_ + (__position - begin()); 1814227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 1815227825Stheraven if (__n > 0) 1816227825Stheraven { 1817227825Stheraven if (__n <= this->__end_cap() - this->__end_) 1818227825Stheraven { 1819227825Stheraven size_type __old_n = __n; 1820227825Stheraven pointer __old_last = this->__end_; 1821227825Stheraven _ForwardIterator __m = __last; 1822227825Stheraven difference_type __dx = this->__end_ - __p; 1823227825Stheraven if (__n > __dx) 1824227825Stheraven { 1825227825Stheraven __m = __first; 1826227825Stheraven _VSTD::advance(__m, this->__end_ - __p); 1827227825Stheraven __construct_at_end(__m, __last); 1828227825Stheraven __n = __dx; 1829227825Stheraven } 1830227825Stheraven if (__n > 0) 1831227825Stheraven { 1832227825Stheraven __move_range(__p, __old_last, __p + __old_n); 1833227825Stheraven _VSTD::copy(__first, __m, __p); 1834227825Stheraven } 1835227825Stheraven } 1836227825Stheraven else 1837227825Stheraven { 1838227825Stheraven allocator_type& __a = this->__alloc(); 1839227825Stheraven __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); 1840227825Stheraven __v.__construct_at_end(__first, __last); 1841227825Stheraven __p = __swap_out_circular_buffer(__v, __p); 1842227825Stheraven } 1843227825Stheraven } 1844227825Stheraven return __make_iter(__p); 1845227825Stheraven} 1846227825Stheraven 1847227825Stheraventemplate <class _Tp, class _Allocator> 1848227825Stheravenvoid 1849227825Stheravenvector<_Tp, _Allocator>::resize(size_type __sz) 1850227825Stheraven{ 1851227825Stheraven size_type __cs = size(); 1852227825Stheraven if (__cs < __sz) 1853227825Stheraven this->__append(__sz - __cs); 1854227825Stheraven else if (__cs > __sz) 1855227825Stheraven this->__destruct_at_end(this->__begin_ + __sz); 1856227825Stheraven} 1857227825Stheraven 1858227825Stheraventemplate <class _Tp, class _Allocator> 1859227825Stheravenvoid 1860227825Stheravenvector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x) 1861227825Stheraven{ 1862227825Stheraven size_type __cs = size(); 1863227825Stheraven if (__cs < __sz) 1864227825Stheraven this->__append(__sz - __cs, __x); 1865227825Stheraven else if (__cs > __sz) 1866227825Stheraven this->__destruct_at_end(this->__begin_ + __sz); 1867227825Stheraven} 1868227825Stheraven 1869227825Stheraventemplate <class _Tp, class _Allocator> 1870227825Stheravenvoid 1871227825Stheravenvector<_Tp, _Allocator>::swap(vector& __x) 1872227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 1873227825Stheraven __is_nothrow_swappable<allocator_type>::value) 1874227825Stheraven{ 1875227825Stheraven _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value || 1876227825Stheraven this->__alloc() == __x.__alloc(), 1877227825Stheraven "vector::swap: Either propagate_on_container_swap must be true" 1878227825Stheraven " or the allocators must compare equal"); 1879227825Stheraven _VSTD::swap(this->__begin_, __x.__begin_); 1880227825Stheraven _VSTD::swap(this->__end_, __x.__end_); 1881227825Stheraven _VSTD::swap(this->__end_cap(), __x.__end_cap()); 1882227825Stheraven __base::__swap_alloc(this->__alloc(), __x.__alloc()); 1883227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1884227825Stheraven __get_db()->swap(this, &__x); 1885227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1886227825Stheraven} 1887227825Stheraven 1888227825Stheraventemplate <class _Tp, class _Allocator> 1889227825Stheravenbool 1890227825Stheravenvector<_Tp, _Allocator>::__invariants() const 1891227825Stheraven{ 1892227825Stheraven if (this->__begin_ == 0) 1893227825Stheraven { 1894227825Stheraven if (this->__end_ != 0 || this->__end_cap() != 0) 1895227825Stheraven return false; 1896227825Stheraven } 1897227825Stheraven else 1898227825Stheraven { 1899227825Stheraven if (this->__begin_ > this->__end_) 1900227825Stheraven return false; 1901227825Stheraven if (this->__begin_ == this->__end_cap()) 1902227825Stheraven return false; 1903227825Stheraven if (this->__end_ > this->__end_cap()) 1904227825Stheraven return false; 1905227825Stheraven } 1906227825Stheraven return true; 1907227825Stheraven} 1908227825Stheraven 1909227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1910227825Stheraven 1911227825Stheraventemplate <class _Tp, class _Allocator> 1912227825Stheravenbool 1913227825Stheravenvector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const 1914227825Stheraven{ 1915227825Stheraven return this->__begin_ <= __i->base() && __i->base() < this->__end_; 1916227825Stheraven} 1917227825Stheraven 1918227825Stheraventemplate <class _Tp, class _Allocator> 1919227825Stheravenbool 1920227825Stheravenvector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const 1921227825Stheraven{ 1922227825Stheraven return this->__begin_ < __i->base() && __i->base() <= this->__end_; 1923227825Stheraven} 1924227825Stheraven 1925227825Stheraventemplate <class _Tp, class _Allocator> 1926227825Stheravenbool 1927227825Stheravenvector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const 1928227825Stheraven{ 1929227825Stheraven const_pointer __p = __i->base() + __n; 1930227825Stheraven return this->__begin_ <= __p && __p <= this->__end_; 1931227825Stheraven} 1932227825Stheraven 1933227825Stheraventemplate <class _Tp, class _Allocator> 1934227825Stheravenbool 1935227825Stheravenvector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const 1936227825Stheraven{ 1937227825Stheraven const_pointer __p = __i->base() + __n; 1938227825Stheraven return this->__begin_ <= __p && __p < this->__end_; 1939227825Stheraven} 1940227825Stheraven 1941227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1942227825Stheraven 1943227825Stheraventemplate <class _Tp, class _Allocator> 1944227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 1945227825Stheravenvoid 1946227825Stheravenvector<_Tp, _Allocator>::__invalidate_all_iterators() 1947227825Stheraven{ 1948227825Stheraven#if _LIBCPP_DEBUG_LEVEL >= 2 1949227825Stheraven __get_db()->__invalidate_all(this); 1950227825Stheraven#endif // _LIBCPP_DEBUG_LEVEL >= 2 1951227825Stheraven} 1952227825Stheraven 1953227825Stheraven// vector<bool> 1954227825Stheraven 1955227825Stheraventemplate <class _Allocator> class vector<bool, _Allocator>; 1956227825Stheraven 1957227825Stheraventemplate <class _Allocator> struct hash<vector<bool, _Allocator> >; 1958227825Stheraven 1959227825Stheraventemplate <class _Allocator> 1960227825Stheravenstruct __has_storage_type<vector<bool, _Allocator> > 1961227825Stheraven{ 1962227825Stheraven static const bool value = true; 1963227825Stheraven}; 1964227825Stheraven 1965227825Stheraventemplate <class _Allocator> 1966227825Stheravenclass _LIBCPP_VISIBLE vector<bool, _Allocator> 1967227825Stheraven : private __vector_base_common<true> 1968227825Stheraven{ 1969227825Stheravenpublic: 1970227825Stheraven typedef vector __self; 1971227825Stheraven typedef bool value_type; 1972227825Stheraven typedef _Allocator allocator_type; 1973227825Stheraven typedef allocator_traits<allocator_type> __alloc_traits; 1974227825Stheraven typedef typename __alloc_traits::size_type size_type; 1975227825Stheraven typedef typename __alloc_traits::difference_type difference_type; 1976241903Sdim typedef size_type __storage_type; 1977227825Stheraven typedef __bit_iterator<vector, false> pointer; 1978227825Stheraven typedef __bit_iterator<vector, true> const_pointer; 1979227825Stheraven#ifdef _LIBCPP_DEBUG 1980227825Stheraven typedef __debug_iter<vector, pointer> iterator; 1981227825Stheraven typedef __debug_iter<vector, const_pointer> const_iterator; 1982227825Stheraven 1983227825Stheraven friend class __debug_iter<vector, pointer>; 1984227825Stheraven friend class __debug_iter<vector, const_pointer>; 1985227825Stheraven 1986227825Stheraven pair<iterator*, const_iterator*> __iterator_list_; 1987227825Stheraven 1988227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;} 1989227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;} 1990227825Stheraven#else // _LIBCPP_DEBUG 1991227825Stheraven typedef pointer iterator; 1992227825Stheraven typedef const_pointer const_iterator; 1993227825Stheraven#endif // _LIBCPP_DEBUG 1994227825Stheraven typedef _VSTD::reverse_iterator<iterator> reverse_iterator; 1995227825Stheraven typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator; 1996227825Stheraven 1997227825Stheravenprivate: 1998227825Stheraven typedef typename __alloc_traits::template 1999227825Stheraven#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES 2000227825Stheraven rebind_alloc<__storage_type> 2001227825Stheraven#else 2002227825Stheraven rebind_alloc<__storage_type>::other 2003227825Stheraven#endif 2004227825Stheraven __storage_allocator; 2005227825Stheraven typedef allocator_traits<__storage_allocator> __storage_traits; 2006227825Stheraven typedef typename __storage_traits::pointer __storage_pointer; 2007227825Stheraven typedef typename __storage_traits::const_pointer __const_storage_pointer; 2008227825Stheraven 2009227825Stheraven __storage_pointer __begin_; 2010227825Stheraven size_type __size_; 2011227825Stheraven __compressed_pair<size_type, __storage_allocator> __cap_alloc_; 2012227825Stheravenpublic: 2013227825Stheraven typedef __bit_reference<vector> reference; 2014227825Stheraven typedef __bit_const_reference<vector> const_reference; 2015227825Stheravenprivate: 2016227825Stheraven _LIBCPP_INLINE_VISIBILITY 2017227825Stheraven size_type& __cap() _NOEXCEPT 2018227825Stheraven {return __cap_alloc_.first();} 2019227825Stheraven _LIBCPP_INLINE_VISIBILITY 2020227825Stheraven const size_type& __cap() const _NOEXCEPT 2021227825Stheraven {return __cap_alloc_.first();} 2022227825Stheraven _LIBCPP_INLINE_VISIBILITY 2023227825Stheraven __storage_allocator& __alloc() _NOEXCEPT 2024227825Stheraven {return __cap_alloc_.second();} 2025227825Stheraven _LIBCPP_INLINE_VISIBILITY 2026227825Stheraven const __storage_allocator& __alloc() const _NOEXCEPT 2027227825Stheraven {return __cap_alloc_.second();} 2028227825Stheraven 2029227825Stheraven static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT); 2030227825Stheraven 2031227825Stheraven _LIBCPP_INLINE_VISIBILITY 2032227825Stheraven static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT 2033227825Stheraven {return __n * __bits_per_word;} 2034227825Stheraven _LIBCPP_INLINE_VISIBILITY 2035227825Stheraven static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT 2036227825Stheraven {return (__n - 1) / __bits_per_word + 1;} 2037227825Stheraven 2038227825Stheravenpublic: 2039227825Stheraven _LIBCPP_INLINE_VISIBILITY 2040227825Stheraven vector() 2041227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value); 2042227825Stheraven _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a); 2043227825Stheraven ~vector(); 2044227825Stheraven explicit vector(size_type __n); 2045227825Stheraven vector(size_type __n, const value_type& __v); 2046227825Stheraven vector(size_type __n, const value_type& __v, const allocator_type& __a); 2047227825Stheraven template <class _InputIterator> 2048227825Stheraven vector(_InputIterator __first, _InputIterator __last, 2049227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2050227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2051227825Stheraven template <class _InputIterator> 2052227825Stheraven vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2053227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2054227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type* = 0); 2055227825Stheraven template <class _ForwardIterator> 2056227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, 2057227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2058227825Stheraven template <class _ForwardIterator> 2059227825Stheraven vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2060227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type* = 0); 2061227825Stheraven 2062227825Stheraven vector(const vector& __v); 2063227825Stheraven vector(const vector& __v, const allocator_type& __a); 2064227825Stheraven vector& operator=(const vector& __v); 2065227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2066227825Stheraven vector(initializer_list<value_type> __il); 2067227825Stheraven vector(initializer_list<value_type> __il, const allocator_type& __a); 2068227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2069227825Stheraven 2070227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2071227825Stheraven _LIBCPP_INLINE_VISIBILITY 2072227825Stheraven vector(vector&& __v) 2073227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value); 2074227825Stheraven vector(vector&& __v, const allocator_type& __a); 2075227825Stheraven _LIBCPP_INLINE_VISIBILITY 2076227825Stheraven vector& operator=(vector&& __v) 2077227825Stheraven _NOEXCEPT_( 2078227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 2079227825Stheraven is_nothrow_move_assignable<allocator_type>::value); 2080227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2081227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2082227825Stheraven _LIBCPP_INLINE_VISIBILITY 2083227825Stheraven vector& operator=(initializer_list<value_type> __il) 2084227825Stheraven {assign(__il.begin(), __il.end()); return *this;} 2085227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2086227825Stheraven 2087227825Stheraven template <class _InputIterator> 2088227825Stheraven typename enable_if 2089227825Stheraven < 2090227825Stheraven __is_input_iterator<_InputIterator>::value && 2091227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2092227825Stheraven void 2093227825Stheraven >::type 2094227825Stheraven assign(_InputIterator __first, _InputIterator __last); 2095227825Stheraven template <class _ForwardIterator> 2096227825Stheraven typename enable_if 2097227825Stheraven < 2098227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2099227825Stheraven void 2100227825Stheraven >::type 2101227825Stheraven assign(_ForwardIterator __first, _ForwardIterator __last); 2102227825Stheraven 2103227825Stheraven void assign(size_type __n, const value_type& __x); 2104227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2105227825Stheraven _LIBCPP_INLINE_VISIBILITY 2106227825Stheraven void assign(initializer_list<value_type> __il) 2107227825Stheraven {assign(__il.begin(), __il.end());} 2108227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2109227825Stheraven 2110227825Stheraven _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT 2111227825Stheraven {return allocator_type(this->__alloc());} 2112227825Stheraven 2113227825Stheraven size_type max_size() const _NOEXCEPT; 2114227825Stheraven _LIBCPP_INLINE_VISIBILITY 2115227825Stheraven size_type capacity() const _NOEXCEPT 2116227825Stheraven {return __internal_cap_to_external(__cap());} 2117227825Stheraven _LIBCPP_INLINE_VISIBILITY 2118227825Stheraven size_type size() const _NOEXCEPT 2119227825Stheraven {return __size_;} 2120227825Stheraven _LIBCPP_INLINE_VISIBILITY 2121227825Stheraven bool empty() const _NOEXCEPT 2122227825Stheraven {return __size_ == 0;} 2123227825Stheraven void reserve(size_type __n); 2124227825Stheraven void shrink_to_fit() _NOEXCEPT; 2125227825Stheraven 2126227825Stheraven _LIBCPP_INLINE_VISIBILITY 2127227825Stheraven iterator begin() _NOEXCEPT 2128227825Stheraven {return __make_iter(0);} 2129227825Stheraven _LIBCPP_INLINE_VISIBILITY 2130227825Stheraven const_iterator begin() const _NOEXCEPT 2131227825Stheraven {return __make_iter(0);} 2132227825Stheraven _LIBCPP_INLINE_VISIBILITY 2133227825Stheraven iterator end() _NOEXCEPT 2134227825Stheraven {return __make_iter(__size_);} 2135227825Stheraven _LIBCPP_INLINE_VISIBILITY 2136227825Stheraven const_iterator end() const _NOEXCEPT 2137227825Stheraven {return __make_iter(__size_);} 2138227825Stheraven 2139227825Stheraven _LIBCPP_INLINE_VISIBILITY 2140227825Stheraven reverse_iterator rbegin() _NOEXCEPT 2141227825Stheraven {return reverse_iterator(end());} 2142227825Stheraven _LIBCPP_INLINE_VISIBILITY 2143227825Stheraven const_reverse_iterator rbegin() const _NOEXCEPT 2144227825Stheraven {return const_reverse_iterator(end());} 2145227825Stheraven _LIBCPP_INLINE_VISIBILITY 2146227825Stheraven reverse_iterator rend() _NOEXCEPT 2147227825Stheraven {return reverse_iterator(begin());} 2148227825Stheraven _LIBCPP_INLINE_VISIBILITY 2149227825Stheraven const_reverse_iterator rend() const _NOEXCEPT 2150227825Stheraven {return const_reverse_iterator(begin());} 2151227825Stheraven 2152227825Stheraven _LIBCPP_INLINE_VISIBILITY 2153227825Stheraven const_iterator cbegin() const _NOEXCEPT 2154227825Stheraven {return __make_iter(0);} 2155227825Stheraven _LIBCPP_INLINE_VISIBILITY 2156227825Stheraven const_iterator cend() const _NOEXCEPT 2157227825Stheraven {return __make_iter(__size_);} 2158227825Stheraven _LIBCPP_INLINE_VISIBILITY 2159227825Stheraven const_reverse_iterator crbegin() const _NOEXCEPT 2160227825Stheraven {return rbegin();} 2161227825Stheraven _LIBCPP_INLINE_VISIBILITY 2162227825Stheraven const_reverse_iterator crend() const _NOEXCEPT 2163227825Stheraven {return rend();} 2164227825Stheraven 2165227825Stheraven _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);} 2166227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);} 2167227825Stheraven reference at(size_type __n); 2168227825Stheraven const_reference at(size_type __n) const; 2169227825Stheraven 2170227825Stheraven _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);} 2171227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);} 2172227825Stheraven _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);} 2173227825Stheraven _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);} 2174227825Stheraven 2175227825Stheraven void push_back(const value_type& __x); 2176227825Stheraven _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;} 2177227825Stheraven 2178227825Stheraven iterator insert(const_iterator __position, const value_type& __x); 2179227825Stheraven iterator insert(const_iterator __position, size_type __n, const value_type& __x); 2180227825Stheraven iterator insert(const_iterator __position, size_type __n, const_reference __x); 2181227825Stheraven template <class _InputIterator> 2182227825Stheraven typename enable_if 2183227825Stheraven < 2184227825Stheraven __is_input_iterator <_InputIterator>::value && 2185227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2186227825Stheraven iterator 2187227825Stheraven >::type 2188227825Stheraven insert(const_iterator __position, _InputIterator __first, _InputIterator __last); 2189227825Stheraven template <class _ForwardIterator> 2190227825Stheraven typename enable_if 2191227825Stheraven < 2192227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2193227825Stheraven iterator 2194227825Stheraven >::type 2195227825Stheraven insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); 2196227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2197227825Stheraven _LIBCPP_INLINE_VISIBILITY 2198227825Stheraven iterator insert(const_iterator __position, initializer_list<value_type> __il) 2199227825Stheraven {return insert(__position, __il.begin(), __il.end());} 2200227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2201227825Stheraven 2202227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position); 2203227825Stheraven iterator erase(const_iterator __first, const_iterator __last); 2204227825Stheraven 2205227825Stheraven _LIBCPP_INLINE_VISIBILITY 2206227825Stheraven void clear() _NOEXCEPT {__size_ = 0;} 2207227825Stheraven 2208227825Stheraven void swap(vector&) 2209227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 2210227825Stheraven __is_nothrow_swappable<allocator_type>::value); 2211227825Stheraven 2212227825Stheraven void resize(size_type __sz, value_type __x = false); 2213227825Stheraven void flip() _NOEXCEPT; 2214227825Stheraven 2215227825Stheraven bool __invariants() const; 2216227825Stheraven 2217227825Stheravenprivate: 2218227825Stheraven _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators(); 2219227825Stheraven void allocate(size_type __n); 2220227825Stheraven void deallocate() _NOEXCEPT; 2221227825Stheraven _LIBCPP_INLINE_VISIBILITY 2222227825Stheraven static size_type __align(size_type __new_size) _NOEXCEPT 2223227825Stheraven {return __new_size + (__bits_per_word-1) & ~(__bits_per_word-1);}; 2224227825Stheraven _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; 2225227825Stheraven _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x); 2226227825Stheraven template <class _ForwardIterator> 2227227825Stheraven typename enable_if 2228227825Stheraven < 2229227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2230227825Stheraven void 2231227825Stheraven >::type 2232227825Stheraven __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); 2233227825Stheraven void __append(size_type __n, const_reference __x); 2234227825Stheraven _LIBCPP_INLINE_VISIBILITY 2235227825Stheraven reference __make_ref(size_type __pos) _NOEXCEPT 2236227825Stheraven {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2237227825Stheraven _LIBCPP_INLINE_VISIBILITY 2238227825Stheraven const_reference __make_ref(size_type __pos) const _NOEXCEPT 2239227825Stheraven {return const_reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);} 2240227825Stheraven#ifdef _LIBCPP_DEBUG 2241227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator __make_iter(size_type __pos) 2242227825Stheraven {return iterator(this, pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));} 2243227825Stheraven _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(size_type __pos) const 2244227825Stheraven {return const_iterator(this, const_pointer(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word)));} 2245227825Stheraven _LIBCPP_INLINE_VISIBILITY iterator __const_iterator_cast(const_iterator __p) 2246227825Stheraven {return iterator(this, pointer(const_cast<__storage_pointer>(__p.base().__seg_), __p.base().__ctz_));} 2247227825Stheraven#else // _LIBCPP_DEBUG 2248227825Stheraven _LIBCPP_INLINE_VISIBILITY 2249227825Stheraven iterator __make_iter(size_type __pos) _NOEXCEPT 2250227825Stheraven {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2251227825Stheraven _LIBCPP_INLINE_VISIBILITY 2252227825Stheraven const_iterator __make_iter(size_type __pos) const _NOEXCEPT 2253227825Stheraven {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));} 2254227825Stheraven _LIBCPP_INLINE_VISIBILITY 2255227825Stheraven iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT 2256227825Stheraven {return iterator(const_cast<__storage_pointer>(__p.__seg_), __p.__ctz_);} 2257227825Stheraven#endif // _LIBCPP_DEBUG 2258227825Stheraven 2259227825Stheraven _LIBCPP_INLINE_VISIBILITY 2260227825Stheraven void __copy_assign_alloc(const vector& __v) 2261227825Stheraven {__copy_assign_alloc(__v, integral_constant<bool, 2262227825Stheraven __storage_traits::propagate_on_container_copy_assignment::value>());} 2263227825Stheraven _LIBCPP_INLINE_VISIBILITY 2264227825Stheraven void __copy_assign_alloc(const vector& __c, true_type) 2265227825Stheraven { 2266227825Stheraven if (__alloc() != __c.__alloc()) 2267227825Stheraven deallocate(); 2268227825Stheraven __alloc() = __c.__alloc(); 2269227825Stheraven } 2270227825Stheraven 2271227825Stheraven _LIBCPP_INLINE_VISIBILITY 2272232950Stheraven void __copy_assign_alloc(const vector&, false_type) 2273227825Stheraven {} 2274227825Stheraven 2275227825Stheraven void __move_assign(vector& __c, false_type); 2276227825Stheraven void __move_assign(vector& __c, true_type) 2277227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value); 2278227825Stheraven _LIBCPP_INLINE_VISIBILITY 2279227825Stheraven void __move_assign_alloc(vector& __c) 2280227825Stheraven _NOEXCEPT_( 2281227825Stheraven !__storage_traits::propagate_on_container_move_assignment::value || 2282227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 2283227825Stheraven {__move_assign_alloc(__c, integral_constant<bool, 2284227825Stheraven __storage_traits::propagate_on_container_move_assignment::value>());} 2285227825Stheraven _LIBCPP_INLINE_VISIBILITY 2286227825Stheraven void __move_assign_alloc(vector& __c, true_type) 2287227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2288227825Stheraven { 2289227825Stheraven __alloc() = _VSTD::move(__c.__alloc()); 2290227825Stheraven } 2291227825Stheraven 2292227825Stheraven _LIBCPP_INLINE_VISIBILITY 2293232950Stheraven void __move_assign_alloc(vector&, false_type) 2294227825Stheraven _NOEXCEPT 2295227825Stheraven {} 2296227825Stheraven 2297227825Stheraven _LIBCPP_INLINE_VISIBILITY 2298227825Stheraven static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y) 2299227825Stheraven _NOEXCEPT_( 2300227825Stheraven !__storage_traits::propagate_on_container_swap::value || 2301227825Stheraven __is_nothrow_swappable<allocator_type>::value) 2302227825Stheraven {__swap_alloc(__x, __y, integral_constant<bool, 2303227825Stheraven __storage_traits::propagate_on_container_swap::value>());} 2304227825Stheraven 2305227825Stheraven _LIBCPP_INLINE_VISIBILITY 2306227825Stheraven static void __swap_alloc(__storage_allocator& __x, __storage_allocator& __y, true_type) 2307227825Stheraven _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value) 2308227825Stheraven { 2309227825Stheraven using _VSTD::swap; 2310227825Stheraven swap(__x, __y); 2311227825Stheraven } 2312227825Stheraven _LIBCPP_INLINE_VISIBILITY 2313232950Stheraven static void __swap_alloc(__storage_allocator&, __storage_allocator&, false_type) 2314227825Stheraven _NOEXCEPT 2315227825Stheraven {} 2316227825Stheraven 2317227825Stheraven size_t __hash_code() const _NOEXCEPT; 2318227825Stheraven 2319227825Stheraven friend class __bit_reference<vector>; 2320227825Stheraven friend class __bit_const_reference<vector>; 2321227825Stheraven friend class __bit_iterator<vector, false>; 2322227825Stheraven friend class __bit_iterator<vector, true>; 2323241903Sdim friend struct __bit_array<vector>; 2324227825Stheraven friend struct _LIBCPP_VISIBLE hash<vector>; 2325227825Stheraven}; 2326227825Stheraven 2327227825Stheraventemplate <class _Allocator> 2328227825Stheraven#ifndef _LIBCPP_DEBUG 2329227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2330227825Stheraven#endif 2331227825Stheravenvoid 2332227825Stheravenvector<bool, _Allocator>::__invalidate_all_iterators() 2333227825Stheraven{ 2334227825Stheraven#ifdef _LIBCPP_DEBUG 2335227825Stheraven iterator::__remove_all(this); 2336227825Stheraven const_iterator::__remove_all(this); 2337227825Stheraven#endif // _LIBCPP_DEBUG 2338227825Stheraven} 2339227825Stheraven 2340227825Stheraven// Allocate space for __n objects 2341227825Stheraven// throws length_error if __n > max_size() 2342227825Stheraven// throws (probably bad_alloc) if memory run out 2343227825Stheraven// Precondition: __begin_ == __end_ == __cap() == 0 2344227825Stheraven// Precondition: __n > 0 2345227825Stheraven// Postcondition: capacity() == __n 2346227825Stheraven// Postcondition: size() == 0 2347227825Stheraventemplate <class _Allocator> 2348227825Stheravenvoid 2349227825Stheravenvector<bool, _Allocator>::allocate(size_type __n) 2350227825Stheraven{ 2351227825Stheraven if (__n > max_size()) 2352227825Stheraven this->__throw_length_error(); 2353227825Stheraven __n = __external_cap_to_internal(__n); 2354227825Stheraven this->__begin_ = __storage_traits::allocate(this->__alloc(), __n); 2355227825Stheraven this->__size_ = 0; 2356227825Stheraven this->__cap() = __n; 2357227825Stheraven} 2358227825Stheraven 2359227825Stheraventemplate <class _Allocator> 2360227825Stheravenvoid 2361227825Stheravenvector<bool, _Allocator>::deallocate() _NOEXCEPT 2362227825Stheraven{ 2363227825Stheraven if (this->__begin_ != 0) 2364227825Stheraven { 2365227825Stheraven __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap()); 2366227825Stheraven __invalidate_all_iterators(); 2367227825Stheraven this->__begin_ = 0; 2368227825Stheraven this->__size_ = this->__cap() = 0; 2369227825Stheraven } 2370227825Stheraven} 2371227825Stheraven 2372227825Stheraventemplate <class _Allocator> 2373227825Stheraventypename vector<bool, _Allocator>::size_type 2374227825Stheravenvector<bool, _Allocator>::max_size() const _NOEXCEPT 2375227825Stheraven{ 2376227825Stheraven size_type __amax = __storage_traits::max_size(__alloc()); 2377227825Stheraven size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always 2378227825Stheraven if (__nmax / __bits_per_word <= __amax) 2379227825Stheraven return __nmax; 2380227825Stheraven return __internal_cap_to_external(__amax); 2381227825Stheraven} 2382227825Stheraven 2383227825Stheraven// Precondition: __new_size > capacity() 2384227825Stheraventemplate <class _Allocator> 2385227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2386227825Stheraventypename vector<bool, _Allocator>::size_type 2387227825Stheravenvector<bool, _Allocator>::__recommend(size_type __new_size) const 2388227825Stheraven{ 2389227825Stheraven const size_type __ms = max_size(); 2390227825Stheraven if (__new_size > __ms) 2391227825Stheraven this->__throw_length_error(); 2392227825Stheraven const size_type __cap = capacity(); 2393227825Stheraven if (__cap >= __ms / 2) 2394227825Stheraven return __ms; 2395227825Stheraven return _VSTD::max(2*__cap, __align(__new_size)); 2396227825Stheraven} 2397227825Stheraven 2398227825Stheraven// Default constructs __n objects starting at __end_ 2399227825Stheraven// Precondition: __n > 0 2400227825Stheraven// Precondition: size() + __n <= capacity() 2401227825Stheraven// Postcondition: size() == size() + __n 2402227825Stheraventemplate <class _Allocator> 2403227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2404227825Stheravenvoid 2405227825Stheravenvector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) 2406227825Stheraven{ 2407227825Stheraven size_type __old_size = this->__size_; 2408227825Stheraven this->__size_ += __n; 2409227825Stheraven _VSTD::fill_n(__make_iter(__old_size), __n, __x); 2410227825Stheraven} 2411227825Stheraven 2412227825Stheraventemplate <class _Allocator> 2413227825Stheraventemplate <class _ForwardIterator> 2414227825Stheraventypename enable_if 2415227825Stheraven< 2416227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2417227825Stheraven void 2418227825Stheraven>::type 2419227825Stheravenvector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) 2420227825Stheraven{ 2421227825Stheraven size_type __old_size = this->__size_; 2422227825Stheraven this->__size_ += _VSTD::distance(__first, __last); 2423227825Stheraven _VSTD::copy(__first, __last, __make_iter(__old_size)); 2424227825Stheraven} 2425227825Stheraven 2426227825Stheraventemplate <class _Allocator> 2427227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2428227825Stheravenvector<bool, _Allocator>::vector() 2429227825Stheraven _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) 2430227825Stheraven : __begin_(0), 2431227825Stheraven __size_(0), 2432227825Stheraven __cap_alloc_(0) 2433227825Stheraven{ 2434227825Stheraven} 2435227825Stheraven 2436227825Stheraventemplate <class _Allocator> 2437227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2438227825Stheravenvector<bool, _Allocator>::vector(const allocator_type& __a) 2439227825Stheraven : __begin_(0), 2440227825Stheraven __size_(0), 2441227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2442227825Stheraven{ 2443227825Stheraven} 2444227825Stheraven 2445227825Stheraventemplate <class _Allocator> 2446227825Stheravenvector<bool, _Allocator>::vector(size_type __n) 2447227825Stheraven : __begin_(0), 2448227825Stheraven __size_(0), 2449227825Stheraven __cap_alloc_(0) 2450227825Stheraven{ 2451227825Stheraven if (__n > 0) 2452227825Stheraven { 2453227825Stheraven allocate(__n); 2454227825Stheraven __construct_at_end(__n, false); 2455227825Stheraven } 2456227825Stheraven} 2457227825Stheraven 2458227825Stheraventemplate <class _Allocator> 2459227825Stheravenvector<bool, _Allocator>::vector(size_type __n, const value_type& __x) 2460227825Stheraven : __begin_(0), 2461227825Stheraven __size_(0), 2462227825Stheraven __cap_alloc_(0) 2463227825Stheraven{ 2464227825Stheraven if (__n > 0) 2465227825Stheraven { 2466227825Stheraven allocate(__n); 2467227825Stheraven __construct_at_end(__n, __x); 2468227825Stheraven } 2469227825Stheraven} 2470227825Stheraven 2471227825Stheraventemplate <class _Allocator> 2472227825Stheravenvector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a) 2473227825Stheraven : __begin_(0), 2474227825Stheraven __size_(0), 2475227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2476227825Stheraven{ 2477227825Stheraven if (__n > 0) 2478227825Stheraven { 2479227825Stheraven allocate(__n); 2480227825Stheraven __construct_at_end(__n, __x); 2481227825Stheraven } 2482227825Stheraven} 2483227825Stheraven 2484227825Stheraventemplate <class _Allocator> 2485227825Stheraventemplate <class _InputIterator> 2486227825Stheravenvector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, 2487227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2488227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 2489227825Stheraven : __begin_(0), 2490227825Stheraven __size_(0), 2491227825Stheraven __cap_alloc_(0) 2492227825Stheraven{ 2493227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2494227825Stheraven try 2495227825Stheraven { 2496227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2497227825Stheraven for (; __first != __last; ++__first) 2498227825Stheraven push_back(*__first); 2499227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2500227825Stheraven } 2501227825Stheraven catch (...) 2502227825Stheraven { 2503227825Stheraven if (__begin_ != 0) 2504227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2505227825Stheraven __invalidate_all_iterators(); 2506227825Stheraven throw; 2507227825Stheraven } 2508227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2509227825Stheraven} 2510227825Stheraven 2511227825Stheraventemplate <class _Allocator> 2512227825Stheraventemplate <class _InputIterator> 2513227825Stheravenvector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a, 2514227825Stheraven typename enable_if<__is_input_iterator <_InputIterator>::value && 2515227825Stheraven !__is_forward_iterator<_InputIterator>::value>::type*) 2516227825Stheraven : __begin_(0), 2517227825Stheraven __size_(0), 2518227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2519227825Stheraven{ 2520227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2521227825Stheraven try 2522227825Stheraven { 2523227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2524227825Stheraven for (; __first != __last; ++__first) 2525227825Stheraven push_back(*__first); 2526227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2527227825Stheraven } 2528227825Stheraven catch (...) 2529227825Stheraven { 2530227825Stheraven if (__begin_ != 0) 2531227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2532227825Stheraven __invalidate_all_iterators(); 2533227825Stheraven throw; 2534227825Stheraven } 2535227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2536227825Stheraven} 2537227825Stheraven 2538227825Stheraventemplate <class _Allocator> 2539227825Stheraventemplate <class _ForwardIterator> 2540227825Stheravenvector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, 2541227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2542227825Stheraven : __begin_(0), 2543227825Stheraven __size_(0), 2544227825Stheraven __cap_alloc_(0) 2545227825Stheraven{ 2546227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2547227825Stheraven if (__n > 0) 2548227825Stheraven { 2549227825Stheraven allocate(__n); 2550227825Stheraven __construct_at_end(__first, __last); 2551227825Stheraven } 2552227825Stheraven} 2553227825Stheraven 2554227825Stheraventemplate <class _Allocator> 2555227825Stheraventemplate <class _ForwardIterator> 2556227825Stheravenvector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, 2557227825Stheraven typename enable_if<__is_forward_iterator<_ForwardIterator>::value>::type*) 2558227825Stheraven : __begin_(0), 2559227825Stheraven __size_(0), 2560227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2561227825Stheraven{ 2562227825Stheraven size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last)); 2563227825Stheraven if (__n > 0) 2564227825Stheraven { 2565227825Stheraven allocate(__n); 2566227825Stheraven __construct_at_end(__first, __last); 2567227825Stheraven } 2568227825Stheraven} 2569227825Stheraven 2570227825Stheraven#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2571227825Stheraven 2572227825Stheraventemplate <class _Allocator> 2573227825Stheravenvector<bool, _Allocator>::vector(initializer_list<value_type> __il) 2574227825Stheraven : __begin_(0), 2575227825Stheraven __size_(0), 2576227825Stheraven __cap_alloc_(0) 2577227825Stheraven{ 2578227825Stheraven size_type __n = static_cast<size_type>(__il.size()); 2579227825Stheraven if (__n > 0) 2580227825Stheraven { 2581227825Stheraven allocate(__n); 2582227825Stheraven __construct_at_end(__il.begin(), __il.end()); 2583227825Stheraven } 2584227825Stheraven} 2585227825Stheraven 2586227825Stheraventemplate <class _Allocator> 2587227825Stheravenvector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a) 2588227825Stheraven : __begin_(0), 2589227825Stheraven __size_(0), 2590227825Stheraven __cap_alloc_(0, static_cast<__storage_allocator>(__a)) 2591227825Stheraven{ 2592227825Stheraven size_type __n = static_cast<size_type>(__il.size()); 2593227825Stheraven if (__n > 0) 2594227825Stheraven { 2595227825Stheraven allocate(__n); 2596227825Stheraven __construct_at_end(__il.begin(), __il.end()); 2597227825Stheraven } 2598227825Stheraven} 2599227825Stheraven 2600227825Stheraven#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS 2601227825Stheraven 2602227825Stheraventemplate <class _Allocator> 2603227825Stheravenvector<bool, _Allocator>::~vector() 2604227825Stheraven{ 2605227825Stheraven if (__begin_ != 0) 2606227825Stheraven __storage_traits::deallocate(__alloc(), __begin_, __cap()); 2607227825Stheraven#ifdef _LIBCPP_DEBUG 2608227825Stheraven __invalidate_all_iterators(); 2609227825Stheraven#endif 2610227825Stheraven} 2611227825Stheraven 2612227825Stheraventemplate <class _Allocator> 2613227825Stheravenvector<bool, _Allocator>::vector(const vector& __v) 2614227825Stheraven : __begin_(0), 2615227825Stheraven __size_(0), 2616227825Stheraven __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc())) 2617227825Stheraven{ 2618227825Stheraven if (__v.size() > 0) 2619227825Stheraven { 2620227825Stheraven allocate(__v.size()); 2621227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2622227825Stheraven } 2623227825Stheraven} 2624227825Stheraven 2625227825Stheraventemplate <class _Allocator> 2626227825Stheravenvector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) 2627227825Stheraven : __begin_(0), 2628227825Stheraven __size_(0), 2629227825Stheraven __cap_alloc_(0, __a) 2630227825Stheraven{ 2631227825Stheraven if (__v.size() > 0) 2632227825Stheraven { 2633227825Stheraven allocate(__v.size()); 2634227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2635227825Stheraven } 2636227825Stheraven} 2637227825Stheraven 2638227825Stheraventemplate <class _Allocator> 2639227825Stheravenvector<bool, _Allocator>& 2640227825Stheravenvector<bool, _Allocator>::operator=(const vector& __v) 2641227825Stheraven{ 2642227825Stheraven if (this != &__v) 2643227825Stheraven { 2644227825Stheraven __copy_assign_alloc(__v); 2645227825Stheraven if (__v.__size_) 2646227825Stheraven { 2647227825Stheraven if (__v.__size_ > capacity()) 2648227825Stheraven { 2649227825Stheraven deallocate(); 2650227825Stheraven allocate(__v.__size_); 2651227825Stheraven } 2652227825Stheraven _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_); 2653227825Stheraven } 2654227825Stheraven __size_ = __v.__size_; 2655227825Stheraven } 2656227825Stheraven return *this; 2657227825Stheraven} 2658227825Stheraven 2659227825Stheraven#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 2660227825Stheraven 2661227825Stheraventemplate <class _Allocator> 2662227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2663227825Stheravenvector<bool, _Allocator>::vector(vector&& __v) 2664227825Stheraven _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) 2665227825Stheraven : __begin_(__v.__begin_), 2666227825Stheraven __size_(__v.__size_), 2667227825Stheraven __cap_alloc_(__v.__cap_alloc_) 2668227825Stheraven{ 2669227825Stheraven __v.__begin_ = 0; 2670227825Stheraven __v.__size_ = 0; 2671227825Stheraven __v.__cap() = 0; 2672227825Stheraven} 2673227825Stheraven 2674227825Stheraventemplate <class _Allocator> 2675227825Stheravenvector<bool, _Allocator>::vector(vector&& __v, const allocator_type& __a) 2676227825Stheraven : __begin_(0), 2677227825Stheraven __size_(0), 2678227825Stheraven __cap_alloc_(0, __a) 2679227825Stheraven{ 2680227825Stheraven if (__a == allocator_type(__v.__alloc())) 2681227825Stheraven { 2682227825Stheraven this->__begin_ = __v.__begin_; 2683227825Stheraven this->__size_ = __v.__size_; 2684227825Stheraven this->__cap() = __v.__cap(); 2685227825Stheraven __v.__begin_ = nullptr; 2686227825Stheraven __v.__cap() = __v.__size_ = 0; 2687227825Stheraven } 2688227825Stheraven else if (__v.size() > 0) 2689227825Stheraven { 2690227825Stheraven allocate(__v.size()); 2691227825Stheraven __construct_at_end(__v.begin(), __v.end()); 2692227825Stheraven } 2693227825Stheraven} 2694227825Stheraven 2695227825Stheraventemplate <class _Allocator> 2696227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2697227825Stheravenvector<bool, _Allocator>& 2698227825Stheravenvector<bool, _Allocator>::operator=(vector&& __v) 2699227825Stheraven _NOEXCEPT_( 2700227825Stheraven __alloc_traits::propagate_on_container_move_assignment::value && 2701227825Stheraven is_nothrow_move_assignable<allocator_type>::value) 2702227825Stheraven{ 2703227825Stheraven __move_assign(__v, integral_constant<bool, 2704227825Stheraven __storage_traits::propagate_on_container_move_assignment::value>()); 2705241903Sdim return *this; 2706227825Stheraven} 2707227825Stheraven 2708227825Stheraventemplate <class _Allocator> 2709227825Stheravenvoid 2710227825Stheravenvector<bool, _Allocator>::__move_assign(vector& __c, false_type) 2711227825Stheraven{ 2712227825Stheraven if (__alloc() != __c.__alloc()) 2713227825Stheraven assign(__c.begin(), __c.end()); 2714227825Stheraven else 2715227825Stheraven __move_assign(__c, true_type()); 2716227825Stheraven} 2717227825Stheraven 2718227825Stheraventemplate <class _Allocator> 2719227825Stheravenvoid 2720227825Stheravenvector<bool, _Allocator>::__move_assign(vector& __c, true_type) 2721227825Stheraven _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) 2722227825Stheraven{ 2723227825Stheraven deallocate(); 2724227825Stheraven this->__begin_ = __c.__begin_; 2725227825Stheraven this->__size_ = __c.__size_; 2726227825Stheraven this->__cap() = __c.__cap(); 2727227825Stheraven __move_assign_alloc(__c); 2728227825Stheraven __c.__begin_ = nullptr; 2729227825Stheraven __c.__cap() = __c.__size_ = 0; 2730227825Stheraven} 2731227825Stheraven 2732227825Stheraven#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 2733227825Stheraven 2734227825Stheraventemplate <class _Allocator> 2735227825Stheravenvoid 2736227825Stheravenvector<bool, _Allocator>::assign(size_type __n, const value_type& __x) 2737227825Stheraven{ 2738227825Stheraven __size_ = 0; 2739227825Stheraven if (__n > 0) 2740227825Stheraven { 2741227825Stheraven size_type __c = capacity(); 2742227825Stheraven if (__n <= __c) 2743227825Stheraven __size_ = __n; 2744227825Stheraven else 2745227825Stheraven { 2746227825Stheraven vector __v(__alloc()); 2747227825Stheraven __v.reserve(__recommend(__n)); 2748227825Stheraven __v.__size_ = __n; 2749227825Stheraven swap(__v); 2750227825Stheraven } 2751227825Stheraven _VSTD::fill_n(begin(), __n, __x); 2752227825Stheraven } 2753227825Stheraven} 2754227825Stheraven 2755227825Stheraventemplate <class _Allocator> 2756227825Stheraventemplate <class _InputIterator> 2757227825Stheraventypename enable_if 2758227825Stheraven< 2759227825Stheraven __is_input_iterator<_InputIterator>::value && 2760227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2761227825Stheraven void 2762227825Stheraven>::type 2763227825Stheravenvector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) 2764227825Stheraven{ 2765227825Stheraven clear(); 2766227825Stheraven for (; __first != __last; ++__first) 2767227825Stheraven push_back(*__first); 2768227825Stheraven} 2769227825Stheraven 2770227825Stheraventemplate <class _Allocator> 2771227825Stheraventemplate <class _ForwardIterator> 2772227825Stheraventypename enable_if 2773227825Stheraven< 2774227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2775227825Stheraven void 2776227825Stheraven>::type 2777227825Stheravenvector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) 2778227825Stheraven{ 2779227825Stheraven clear(); 2780227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 2781227825Stheraven if (__n) 2782227825Stheraven { 2783227825Stheraven if (__n > capacity()) 2784227825Stheraven { 2785227825Stheraven deallocate(); 2786227825Stheraven allocate(__n); 2787227825Stheraven } 2788227825Stheraven __construct_at_end(__first, __last); 2789227825Stheraven } 2790227825Stheraven} 2791227825Stheraven 2792227825Stheraventemplate <class _Allocator> 2793227825Stheravenvoid 2794227825Stheravenvector<bool, _Allocator>::reserve(size_type __n) 2795227825Stheraven{ 2796227825Stheraven if (__n > capacity()) 2797227825Stheraven { 2798227825Stheraven vector __v(this->__alloc()); 2799227825Stheraven __v.allocate(__n); 2800227825Stheraven __v.__construct_at_end(this->begin(), this->end()); 2801227825Stheraven swap(__v); 2802227825Stheraven __invalidate_all_iterators(); 2803227825Stheraven } 2804227825Stheraven} 2805227825Stheraven 2806227825Stheraventemplate <class _Allocator> 2807227825Stheravenvoid 2808227825Stheravenvector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT 2809227825Stheraven{ 2810227825Stheraven if (__external_cap_to_internal(size()) > __cap()) 2811227825Stheraven { 2812227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2813227825Stheraven try 2814227825Stheraven { 2815227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2816227825Stheraven vector(*this, allocator_type(__alloc())).swap(*this); 2817227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2818227825Stheraven } 2819227825Stheraven catch (...) 2820227825Stheraven { 2821227825Stheraven } 2822227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2823227825Stheraven } 2824227825Stheraven} 2825227825Stheraven 2826227825Stheraventemplate <class _Allocator> 2827227825Stheraventypename vector<bool, _Allocator>::reference 2828227825Stheravenvector<bool, _Allocator>::at(size_type __n) 2829227825Stheraven{ 2830227825Stheraven if (__n >= size()) 2831227825Stheraven this->__throw_out_of_range(); 2832227825Stheraven return (*this)[__n]; 2833227825Stheraven} 2834227825Stheraven 2835227825Stheraventemplate <class _Allocator> 2836227825Stheraventypename vector<bool, _Allocator>::const_reference 2837227825Stheravenvector<bool, _Allocator>::at(size_type __n) const 2838227825Stheraven{ 2839227825Stheraven if (__n >= size()) 2840227825Stheraven this->__throw_out_of_range(); 2841227825Stheraven return (*this)[__n]; 2842227825Stheraven} 2843227825Stheraven 2844227825Stheraventemplate <class _Allocator> 2845227825Stheravenvoid 2846227825Stheravenvector<bool, _Allocator>::push_back(const value_type& __x) 2847227825Stheraven{ 2848227825Stheraven if (this->__size_ == this->capacity()) 2849227825Stheraven reserve(__recommend(this->__size_ + 1)); 2850227825Stheraven ++this->__size_; 2851227825Stheraven back() = __x; 2852227825Stheraven} 2853227825Stheraven 2854227825Stheraventemplate <class _Allocator> 2855227825Stheraventypename vector<bool, _Allocator>::iterator 2856227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x) 2857227825Stheraven{ 2858227825Stheraven iterator __r; 2859227825Stheraven if (size() < capacity()) 2860227825Stheraven { 2861227825Stheraven const_iterator __old_end = end(); 2862227825Stheraven ++__size_; 2863227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 2864227825Stheraven __r = __const_iterator_cast(__position); 2865227825Stheraven } 2866227825Stheraven else 2867227825Stheraven { 2868227825Stheraven vector __v(__alloc()); 2869227825Stheraven __v.reserve(__recommend(__size_ + 1)); 2870227825Stheraven __v.__size_ = __size_ + 1; 2871227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 2872227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 2873227825Stheraven swap(__v); 2874227825Stheraven } 2875227825Stheraven *__r = __x; 2876227825Stheraven return __r; 2877227825Stheraven} 2878227825Stheraven 2879227825Stheraventemplate <class _Allocator> 2880227825Stheraventypename vector<bool, _Allocator>::iterator 2881227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x) 2882227825Stheraven{ 2883227825Stheraven iterator __r; 2884227825Stheraven size_type __c = capacity(); 2885227825Stheraven if (__n <= __c && size() <= __c - __n) 2886227825Stheraven { 2887227825Stheraven const_iterator __old_end = end(); 2888227825Stheraven __size_ += __n; 2889227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 2890227825Stheraven __r = __const_iterator_cast(__position); 2891227825Stheraven } 2892227825Stheraven else 2893227825Stheraven { 2894227825Stheraven vector __v(__alloc()); 2895227825Stheraven __v.reserve(__recommend(__size_ + __n)); 2896227825Stheraven __v.__size_ = __size_ + __n; 2897227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 2898227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 2899227825Stheraven swap(__v); 2900227825Stheraven } 2901227825Stheraven _VSTD::fill_n(__r, __n, __x); 2902227825Stheraven return __r; 2903227825Stheraven} 2904227825Stheraven 2905227825Stheraventemplate <class _Allocator> 2906227825Stheraventemplate <class _InputIterator> 2907227825Stheraventypename enable_if 2908227825Stheraven< 2909227825Stheraven __is_input_iterator <_InputIterator>::value && 2910227825Stheraven !__is_forward_iterator<_InputIterator>::value, 2911227825Stheraven typename vector<bool, _Allocator>::iterator 2912227825Stheraven>::type 2913227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) 2914227825Stheraven{ 2915227825Stheraven difference_type __off = __position - begin(); 2916227825Stheraven iterator __p = __const_iterator_cast(__position); 2917227825Stheraven iterator __old_end = end(); 2918227825Stheraven for (; size() != capacity() && __first != __last; ++__first) 2919227825Stheraven { 2920227825Stheraven ++this->__size_; 2921227825Stheraven back() = *__first; 2922227825Stheraven } 2923227825Stheraven vector __v(__alloc()); 2924227825Stheraven if (__first != __last) 2925227825Stheraven { 2926227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2927227825Stheraven try 2928227825Stheraven { 2929227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2930227825Stheraven __v.assign(__first, __last); 2931227825Stheraven difference_type __old_size = static_cast<difference_type>(__old_end - begin()); 2932227825Stheraven difference_type __old_p = __p - begin(); 2933227825Stheraven reserve(__recommend(size() + __v.size())); 2934227825Stheraven __p = begin() + __old_p; 2935227825Stheraven __old_end = begin() + __old_size; 2936227825Stheraven#ifndef _LIBCPP_NO_EXCEPTIONS 2937227825Stheraven } 2938227825Stheraven catch (...) 2939227825Stheraven { 2940227825Stheraven erase(__old_end, end()); 2941227825Stheraven throw; 2942227825Stheraven } 2943227825Stheraven#endif // _LIBCPP_NO_EXCEPTIONS 2944227825Stheraven } 2945227825Stheraven __p = _VSTD::rotate(__p, __old_end, end()); 2946227825Stheraven insert(__p, __v.begin(), __v.end()); 2947227825Stheraven return begin() + __off; 2948227825Stheraven} 2949227825Stheraven 2950227825Stheraventemplate <class _Allocator> 2951227825Stheraventemplate <class _ForwardIterator> 2952227825Stheraventypename enable_if 2953227825Stheraven< 2954227825Stheraven __is_forward_iterator<_ForwardIterator>::value, 2955227825Stheraven typename vector<bool, _Allocator>::iterator 2956227825Stheraven>::type 2957227825Stheravenvector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) 2958227825Stheraven{ 2959227825Stheraven difference_type __n = _VSTD::distance(__first, __last); 2960227825Stheraven iterator __r; 2961227825Stheraven size_type __c = capacity(); 2962227825Stheraven if (__n <= __c && size() <= __c - __n) 2963227825Stheraven { 2964227825Stheraven const_iterator __old_end = end(); 2965227825Stheraven __size_ += __n; 2966227825Stheraven _VSTD::copy_backward(__position, __old_end, end()); 2967227825Stheraven __r = __const_iterator_cast(__position); 2968227825Stheraven } 2969227825Stheraven else 2970227825Stheraven { 2971227825Stheraven vector __v(__alloc()); 2972227825Stheraven __v.reserve(__recommend(__size_ + __n)); 2973227825Stheraven __v.__size_ = __size_ + __n; 2974227825Stheraven __r = _VSTD::copy(cbegin(), __position, __v.begin()); 2975227825Stheraven _VSTD::copy_backward(__position, cend(), __v.end()); 2976227825Stheraven swap(__v); 2977227825Stheraven } 2978227825Stheraven _VSTD::copy(__first, __last, __r); 2979227825Stheraven return __r; 2980227825Stheraven} 2981227825Stheraven 2982227825Stheraventemplate <class _Allocator> 2983227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 2984227825Stheraventypename vector<bool, _Allocator>::iterator 2985227825Stheravenvector<bool, _Allocator>::erase(const_iterator __position) 2986227825Stheraven{ 2987227825Stheraven iterator __r = __const_iterator_cast(__position); 2988227825Stheraven _VSTD::copy(__position + 1, this->cend(), __r); 2989227825Stheraven --__size_; 2990227825Stheraven return __r; 2991227825Stheraven} 2992227825Stheraven 2993227825Stheraventemplate <class _Allocator> 2994227825Stheraventypename vector<bool, _Allocator>::iterator 2995227825Stheravenvector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last) 2996227825Stheraven{ 2997227825Stheraven iterator __r = __const_iterator_cast(__first); 2998227825Stheraven difference_type __d = __last - __first; 2999227825Stheraven _VSTD::copy(__last, this->cend(), __r); 3000227825Stheraven __size_ -= __d; 3001227825Stheraven return __r; 3002227825Stheraven} 3003227825Stheraven 3004227825Stheraventemplate <class _Allocator> 3005227825Stheravenvoid 3006227825Stheravenvector<bool, _Allocator>::swap(vector& __x) 3007227825Stheraven _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || 3008227825Stheraven __is_nothrow_swappable<allocator_type>::value) 3009227825Stheraven{ 3010227825Stheraven _VSTD::swap(this->__begin_, __x.__begin_); 3011227825Stheraven _VSTD::swap(this->__size_, __x.__size_); 3012227825Stheraven _VSTD::swap(this->__cap(), __x.__cap()); 3013227825Stheraven __swap_alloc(this->__alloc(), __x.__alloc()); 3014227825Stheraven#ifdef _LIBCPP_DEBUG 3015227825Stheraven iterator::swap(this, &__x); 3016227825Stheraven const_iterator::swap(this, &__x); 3017227825Stheraven#endif // _LIBCPP_DEBUG 3018227825Stheraven} 3019227825Stheraven 3020227825Stheraventemplate <class _Allocator> 3021227825Stheravenvoid 3022227825Stheravenvector<bool, _Allocator>::resize(size_type __sz, value_type __x) 3023227825Stheraven{ 3024227825Stheraven size_type __cs = size(); 3025227825Stheraven if (__cs < __sz) 3026227825Stheraven { 3027227825Stheraven iterator __r; 3028227825Stheraven size_type __c = capacity(); 3029227825Stheraven size_type __n = __sz - __cs; 3030227825Stheraven if (__n <= __c && __cs <= __c - __n) 3031227825Stheraven { 3032227825Stheraven __r = end(); 3033227825Stheraven __size_ += __n; 3034227825Stheraven } 3035227825Stheraven else 3036227825Stheraven { 3037227825Stheraven vector __v(__alloc()); 3038227825Stheraven __v.reserve(__recommend(__size_ + __n)); 3039227825Stheraven __v.__size_ = __size_ + __n; 3040227825Stheraven __r = _VSTD::copy(cbegin(), cend(), __v.begin()); 3041227825Stheraven swap(__v); 3042227825Stheraven } 3043227825Stheraven _VSTD::fill_n(__r, __n, __x); 3044227825Stheraven } 3045227825Stheraven else 3046227825Stheraven __size_ = __sz; 3047227825Stheraven} 3048227825Stheraven 3049227825Stheraventemplate <class _Allocator> 3050227825Stheravenvoid 3051227825Stheravenvector<bool, _Allocator>::flip() _NOEXCEPT 3052227825Stheraven{ 3053227825Stheraven // do middle whole words 3054227825Stheraven size_type __n = __size_; 3055227825Stheraven __storage_pointer __p = __begin_; 3056227825Stheraven for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3057227825Stheraven *__p = ~*__p; 3058227825Stheraven // do last partial word 3059227825Stheraven if (__n > 0) 3060227825Stheraven { 3061227825Stheraven __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3062227825Stheraven __storage_type __b = *__p & __m; 3063227825Stheraven *__p &= ~__m; 3064227825Stheraven *__p |= ~__b & __m; 3065227825Stheraven } 3066227825Stheraven} 3067227825Stheraven 3068227825Stheraventemplate <class _Allocator> 3069227825Stheravenbool 3070227825Stheravenvector<bool, _Allocator>::__invariants() const 3071227825Stheraven{ 3072227825Stheraven if (this->__begin_ == 0) 3073227825Stheraven { 3074227825Stheraven if (this->__size_ != 0 || this->__cap() != 0) 3075227825Stheraven return false; 3076227825Stheraven } 3077227825Stheraven else 3078227825Stheraven { 3079227825Stheraven if (this->__cap() == 0) 3080227825Stheraven return false; 3081227825Stheraven if (this->__size_ > this->capacity()) 3082227825Stheraven return false; 3083227825Stheraven } 3084227825Stheraven return true; 3085227825Stheraven} 3086227825Stheraven 3087227825Stheraventemplate <class _Allocator> 3088227825Stheravensize_t 3089227825Stheravenvector<bool, _Allocator>::__hash_code() const _NOEXCEPT 3090227825Stheraven{ 3091227825Stheraven size_t __h = 0; 3092227825Stheraven // do middle whole words 3093227825Stheraven size_type __n = __size_; 3094227825Stheraven __storage_pointer __p = __begin_; 3095227825Stheraven for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word) 3096227825Stheraven __h ^= *__p; 3097227825Stheraven // do last partial word 3098227825Stheraven if (__n > 0) 3099227825Stheraven { 3100227825Stheraven const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); 3101227825Stheraven __h ^= *__p & __m; 3102227825Stheraven } 3103227825Stheraven return __h; 3104227825Stheraven} 3105227825Stheraven 3106227825Stheraventemplate <class _Allocator> 3107227825Stheravenstruct _LIBCPP_VISIBLE hash<vector<bool, _Allocator> > 3108227825Stheraven : public unary_function<vector<bool, _Allocator>, size_t> 3109227825Stheraven{ 3110227825Stheraven _LIBCPP_INLINE_VISIBILITY 3111227825Stheraven size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT 3112227825Stheraven {return __vec.__hash_code();} 3113227825Stheraven}; 3114227825Stheraven 3115227825Stheraventemplate <class _Tp, class _Allocator> 3116227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3117227825Stheravenbool 3118227825Stheravenoperator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3119227825Stheraven{ 3120227825Stheraven const typename vector<_Tp, _Allocator>::size_type __sz = __x.size(); 3121227825Stheraven return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin()); 3122227825Stheraven} 3123227825Stheraven 3124227825Stheraventemplate <class _Tp, class _Allocator> 3125227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3126227825Stheravenbool 3127227825Stheravenoperator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3128227825Stheraven{ 3129227825Stheraven return !(__x == __y); 3130227825Stheraven} 3131227825Stheraven 3132227825Stheraventemplate <class _Tp, class _Allocator> 3133227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3134227825Stheravenbool 3135227825Stheravenoperator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3136227825Stheraven{ 3137227825Stheraven return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end()); 3138227825Stheraven} 3139227825Stheraven 3140227825Stheraventemplate <class _Tp, class _Allocator> 3141227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3142227825Stheravenbool 3143227825Stheravenoperator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3144227825Stheraven{ 3145227825Stheraven return __y < __x; 3146227825Stheraven} 3147227825Stheraven 3148227825Stheraventemplate <class _Tp, class _Allocator> 3149227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3150227825Stheravenbool 3151227825Stheravenoperator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3152227825Stheraven{ 3153227825Stheraven return !(__x < __y); 3154227825Stheraven} 3155227825Stheraven 3156227825Stheraventemplate <class _Tp, class _Allocator> 3157227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3158227825Stheravenbool 3159227825Stheravenoperator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) 3160227825Stheraven{ 3161227825Stheraven return !(__y < __x); 3162227825Stheraven} 3163227825Stheraven 3164227825Stheraventemplate <class _Tp, class _Allocator> 3165227825Stheraven_LIBCPP_INLINE_VISIBILITY inline 3166227825Stheravenvoid 3167227825Stheravenswap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y) 3168227825Stheraven _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) 3169227825Stheraven{ 3170227825Stheraven __x.swap(__y); 3171227825Stheraven} 3172227825Stheraven 3173227825Stheraven_LIBCPP_END_NAMESPACE_STD 3174227825Stheraven 3175227825Stheraven#endif // _LIBCPP_VECTOR 3176