3 * - By John Hodge (thePowersGang)
6 * - C++'s vector (dynamic array) type
8 #ifndef _LIBCXX_VECTOR_
9 #define _LIBCXX_VECTOR_
13 #include <initializer_list>
15 extern "C" void _SysDebug(const char *, ...);
20 template <class VectorType, class T>
21 class vector_iterator//:
22 //public random_acess_iterator_tag
26 typedef typename VectorType::size_type size_type;
27 typedef typename VectorType::difference_type difference_type;
34 vector_iterator(0,0,0)
37 vector_iterator(const vector_iterator& x):
42 vector_iterator(T* array, size_type start, size_type max):
48 vector_iterator& operator=(const vector_iterator& x)
55 bool operator==(const vector_iterator& other) const {
56 return m_pos == other.m_pos;
58 bool operator!=(const vector_iterator& other) const {
59 return !(*this == other);
61 T& operator*() const {
62 return m_array[m_pos];
64 T& operator->() const {
65 return m_array[m_pos];
67 T& operator[](difference_type n) {
70 vector_iterator& operator++() {
76 const vector_iterator operator++(int) {
77 vector_iterator ret(*this);
81 vector_iterator& operator--() {
87 const vector_iterator operator--(int) {
88 vector_iterator ret(*this);
92 vector_iterator& operator+=(difference_type n) {
96 m_pos = (m_pos + n < m_max ? m_pos + n : m_max);
99 vector_iterator& operator-=(difference_type n) {
101 return (*this += -n);
103 m_pos = (m_pos >= n ? m_pos - n : 0);
106 const difference_type operator-(const vector_iterator& it2) const {
107 //_libcxx_assert(m_array == it2.m_array);
108 return m_pos - it2.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; }
113 bool operator>=(const vector_iterator& o) const { return m_pos >= o.m_pos; }
115 #define vector_iterator_tpl class VectorType, class T
116 #define vector_iterator vector_iterator<VectorType, T>
117 template <vector_iterator_tpl>
118 const vector_iterator operator+(const vector_iterator& it, typename VectorType::difference_type n) {
119 return vector_iterator(it) += n;
121 template <vector_iterator_tpl>
122 const vector_iterator operator+(typename VectorType::difference_type n, const vector_iterator& it) {
123 return vector_iterator(it) += n;
125 template <vector_iterator_tpl>
126 const vector_iterator operator-(const vector_iterator& it, typename VectorType::difference_type n) {
127 return vector_iterator(it) -= n;
129 #undef vector_iterator_tpl
130 #undef vector_iterator
134 template <class T, class Alloc = allocator<T> >
138 typedef T value_type;
139 typedef Alloc allocator_type;
140 typedef typename allocator_type::reference reference;
141 typedef typename allocator_type::const_reference const_reference;
142 typedef typename allocator_type::pointer pointer;
143 typedef typename allocator_type::const_pointer const_pointer;
144 typedef int difference_type;
145 typedef size_t size_type;
146 typedef ::std::_bits::vector_iterator<vector,T> iterator;
147 typedef ::std::_bits::vector_iterator<vector,const T> const_iterator;
150 allocator_type m_alloc;
152 size_type m_capacity;
156 vector(const allocator_type& alloc = allocator_type()):
163 vector(size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()):
168 template <class InputIterator>
169 vector(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()):
172 insert(begin(), first, last);
174 vector(const vector& x):
183 m_capacity(x.m_capacity),
190 vector(vector&& x, const allocator_type& alloc):
193 m_capacity(x.m_capacity),
200 vector(std::initializer_list<value_type> il, const allocator_type& alloc = allocator_type()):
204 insert(begin(), il.begin(), il.end());
207 vector& operator=(const vector& x)
210 m_alloc.deallocate(m_data, m_capacity);
215 for( size_type i = 0; i < x.size(); i ++ )
224 m_alloc.deallocate(m_data, m_capacity);
230 iterator begin() { return iterator_to(0); }
231 const_iterator begin() const { return iterator_to(0); }
232 iterator end() { return iterator_to(m_size); }
233 const_iterator end() const { return iterator_to(m_size); }
236 size_type size() const {
239 size_type max_size() const {
240 return -1 / sizeof(value_type);
242 void resize(size_type new_cap, value_type val = value_type()) {
244 if( new_cap > m_size )
246 for( size_type i = m_size; i < new_cap; i ++ ) {
247 m_alloc.construct( &m_data[i], val );
252 for( size_type i = new_cap; i < m_size; i ++ )
253 m_alloc.destroy( &m_data[i] );
257 size_type capacity() const {
263 void reserve(size_type n) {
265 throw ::std::length_error("::std::vector::reserve");
268 size_type size = (n + 0x1F) & ~0x1F;
269 auto new_area = m_alloc.allocate(size);
270 for( size_type i = 0; i < m_size; i ++ )
271 new_area[i] = m_data[i];
272 m_alloc.deallocate(m_data, m_capacity);
275 //::_SysDebug("::std::vector::resize - m_capacity=%i for n=%i", m_capacity, n);
278 void shrink_to_fit() {
282 reference operator[] (size_type n) {
285 const_reference operator[] (size_type n) const {
288 reference at(size_type n) {
290 _throw_out_of_range("::std::vector - at");
293 const_reference at(size_type n) const {
295 _throw_out_of_range("::std::vector - at");
301 const_reference front() const {
305 return m_data[size()-1];
307 const_reference back() const {
308 return m_data[size()-1];
310 pointer data() noexcept {
313 const_pointer data() const noexcept {
318 void assign(size_type n, const value_type& val) {
322 void push_back(const value_type& val) {
323 resize(size()+1, val);
330 iterator insert(iterator position, const value_type& val) {
331 insert(position, 1, val);
332 return iterator_to(position.m_pos);
334 void insert(iterator position, size_type n, const value_type& val) {
336 if( position != end() ) {
337 ::_sys::debug("TODO: vector::insert within vector (%i!=%i)",
338 position-begin(), end()-begin());
341 size_type pos = m_size;
344 //::_sys::debug("vector::insert - %x at %i", val, pos);
345 m_alloc.construct( &m_data[pos], val );
350 template <class InputIterator>
351 void insert(iterator position, InputIterator first, InputIterator last) {
352 InputIterator it = first;
358 reserve(m_size + len);
363 //::_sys::debug("vector::insert - to %i, from %p:%i",
364 // position.m_pos, it.m_array, it.m_pos);
365 position = insert(position, *it) + 1;
369 iterator erase(iterator position);
370 iterator erase(iterator first, iterator last);
371 //void swap(vector& x) {
372 // ::std::swap(m_size, x.m_size);
373 // ::std::swap(m_capacity, x.m_capacity);
374 // ::std::swap(m_data, x.m_data);
377 for( size_type i = 0; i < m_size; i ++ ) {
378 m_alloc.destroy( &m_data[i] );
383 iterator iterator_to(size_type index) {
384 _libcxx_assert(index <= m_size);
385 return iterator(m_data, index, m_size);
387 const_iterator iterator_to(size_type index) const {
388 _libcxx_assert(index <= m_size);
389 return const_iterator(m_data, index, m_size);