3 * - By John Hodge (thePowersGang)
6 * - C++'s vector (dynamic array) type
8 #ifndef _LIBCXX_VECTOR_
9 #define _LIBCXX_VECTOR_
14 extern "C" void _SysDebug(const char *, ...);
19 template <class VectorType, class T>
20 class vector_iterator//:
21 //public random_acess_iterator_tag
25 typedef typename VectorType::size_type size_type;
26 typedef typename VectorType::difference_type difference_type;
33 vector_iterator(0,0,0)
36 vector_iterator(const vector_iterator& x):
41 vector_iterator(T* array, size_type start, size_type max):
47 vector_iterator& operator=(const vector_iterator& x)
54 bool operator==(const vector_iterator& other) const {
55 return m_pos == other.m_pos;
57 bool operator!=(const vector_iterator& other) const {
58 return !(*this == other);
60 T& operator*() const {
61 return m_array[m_pos];
63 T& operator->() const {
64 return m_array[m_pos];
66 T& operator[](difference_type n) {
69 vector_iterator& operator++() {
75 const vector_iterator operator++(int) {
76 vector_iterator ret(*this);
80 vector_iterator& operator--() {
86 const vector_iterator operator--(int) {
87 vector_iterator ret(*this);
91 vector_iterator& operator+=(difference_type n) {
95 m_pos = (m_pos + n < m_max ? m_pos + n : m_max);
98 vector_iterator& operator-=(difference_type n) {
100 return (*this += -n);
102 m_pos = (m_pos >= n ? m_pos - n : 0);
105 const difference_type operator-(const vector_iterator& it2) const {
106 //_libcxx_assert(m_array == it2.m_array);
107 return m_pos - it2.m_pos;
109 bool operator<(const vector_iterator& o) const { return m_pos < o.m_pos; }
110 bool operator>(const vector_iterator& o) const { return m_pos > o.m_pos; }
111 bool operator<=(const vector_iterator& o) const { return m_pos <= o.m_pos; }
112 bool operator>=(const vector_iterator& o) const { return m_pos >= o.m_pos; }
114 #define vector_iterator_tpl class VectorType, class T
115 #define vector_iterator vector_iterator<VectorType, T>
116 template <vector_iterator_tpl>
117 const vector_iterator operator+(const vector_iterator& it, typename VectorType::difference_type n) {
118 return vector_iterator(it) += n;
120 template <vector_iterator_tpl>
121 const vector_iterator operator+(typename VectorType::difference_type n, const vector_iterator& it) {
122 return vector_iterator(it) += n;
124 template <vector_iterator_tpl>
125 const vector_iterator operator-(const vector_iterator& it, typename VectorType::difference_type n) {
126 return vector_iterator(it) -= n;
128 #undef vector_iterator_tpl
129 #undef vector_iterator
133 template <class T, class Alloc = allocator<T> >
137 typedef T value_type;
138 typedef Alloc allocator_type;
139 typedef typename allocator_type::reference reference;
140 typedef typename allocator_type::const_reference const_reference;
141 typedef typename allocator_type::pointer pointer;
142 typedef typename allocator_type::const_pointer const_pointer;
143 typedef int difference_type;
144 typedef size_t size_type;
145 typedef ::std::_bits::vector_iterator<vector,T> iterator;
146 typedef ::std::_bits::vector_iterator<vector,const T> const_iterator;
149 allocator_type m_alloc;
151 size_type m_capacity;
155 vector(const allocator_type& alloc = allocator_type()):
162 vector(size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
167 template <class InputIterator>
168 vector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()):
171 insert(begin(), first, last);
173 vector(const vector& x):
182 m_capacity(x.m_capacity),
190 vector& operator=(const vector& x)
193 m_alloc.deallocate(m_data, m_capacity);
197 for( size_type i = 0; i < x.size(); i ++ )
206 m_alloc.deallocate(m_data, m_capacity);
211 iterator begin() { return iterator_to(0); }
212 const_iterator begin() const { return iterator_to(0); }
213 iterator end() { return iterator_to(m_size); }
214 const_iterator end() const { return iterator_to(m_size); }
217 size_type size() const {
220 size_type max_size() const {
221 return -1 / sizeof(value_type);
223 void resize(size_type new_cap, value_type val = value_type()) {
225 if( new_cap > m_size )
227 for( size_type i = m_size; i < new_cap; i ++ ) {
228 m_alloc.construct( &m_data[i], val );
233 for( size_type i = new_cap; i < m_size; i ++ )
234 m_alloc.destroy( &m_data[i] );
238 size_type capacity() const {
244 void reserve(size_type n) {
246 throw ::std::length_error("::std::vector::reserve");
249 size_type size = (n + 0x1F) & ~0x1F;
250 auto new_area = m_alloc.allocate(size);
251 for( size_type i = 0; i < m_size; i ++ )
252 new_area[i] = m_data[i];
253 m_alloc.deallocate(m_data, m_capacity);
256 //::_SysDebug("::std::vector::resize - m_capacity=%i for n=%i", m_capacity, n);
259 void shrink_to_fit() {
263 reference operator[] (size_type n) {
266 const_reference operator[] (size_type n) const {
269 reference at(size_type n) {
271 _throw_out_of_range("::std::vector - at");
274 const_reference at(size_type n) const {
276 _throw_out_of_range("::std::vector - at");
282 const_reference front() const {
286 return m_data[size()-1];
288 const_reference back() const {
289 return m_data[size()-1];
291 pointer data() noexcept {
294 const_pointer data() const noexcept {
299 void assign(size_type n, const value_type& val) {
303 void push_back(const value_type& val) {
304 resize(size()+1, val);
311 iterator insert(iterator position, const value_type& val) {
312 insert(position, 1, val);
313 return iterator_to(position.m_pos);
315 void insert(iterator position, size_type n, const value_type& val) {
317 if( position != end() ) {
318 ::_sys::debug("TODO: vector::insert within vector (%i!=%i)",
319 position-begin(), end()-begin());
322 size_type pos = m_size;
325 //::_sys::debug("vector::insert - %x at %i", val, pos);
326 m_alloc.construct( &m_data[pos], val );
331 template <class InputIterator>
332 void insert(iterator position, InputIterator first, InputIterator last) {
333 InputIterator it = first;
339 reserve(m_size + len);
344 //::_sys::debug("vector::insert - to %i, from %p:%i",
345 // position.m_pos, it.m_array, it.m_pos);
346 position = insert(position, *it) + 1;
350 iterator erase(iterator position);
351 iterator erase(iterator first, iterator last);
352 //void swap(vector& x) {
353 // ::std::swap(m_size, x.m_size);
354 // ::std::swap(m_capacity, x.m_capacity);
355 // ::std::swap(m_data, x.m_data);
358 for( size_type i = 0; i < m_size; i ++ ) {
359 m_alloc.destroy( &m_data[i] );
364 iterator iterator_to(size_type index) {
365 _libcxx_assert(index <= m_size);
366 return iterator(m_data, index, m_size);
368 const_iterator iterator_to(size_type index) const {
369 _libcxx_assert(index <= m_size);
370 return const_iterator(m_data, index, m_size);