diff options
Diffstat (limited to 'Vector.hpp')
| -rw-r--r-- | Vector.hpp | 294 |
1 files changed, 153 insertions, 141 deletions
@@ -6,22 +6,25 @@ /* By: charles <charles.cabergs@gmail.com> +#+ +:+ +#+ */ /* +#+#+#+#+#+ +#+ */ /* Created: 2020/04/24 16:19:04 by charles #+# #+# */ -/* Updated: 2020/04/24 19:16:17 by charles ### ########.fr */ +/* Updated: 2020/04/25 19:04:33 by charles ### ########.fr */ /* */ /* ************************************************************************** */ #ifndef VECTOR_HPP # define VECTOR_HPP +# include <climits> +# include <cstddef> # include <stdexcept> # define FT_VECTOR_GROWTH_FACTOR 1.5 namespace ft { - template < typename T, typename Alloc = allocator<T> > - class vector + template < typename T, typename Alloc = std::allocator<T> > + class Vector { + typedef Vector<T, Alloc> m_type; public: typedef T value_type; typedef Alloc allocator_type; @@ -33,13 +36,13 @@ namespace ft typedef size_t size_type; explicit Vector(const allocator_type& alloc = allocator_type()) - : m_under(new value_type[0]), m_size(0), m_capacity(0) + : m_under(new value_type[0]), m_size(0), m_capacity(0), m_alloc(alloc) {} explicit Vector(size_type n, const value_type& val = value_type(), const allocator_type& alloc = allocator_type()) - : m_under(new value_type[n]), m_size(n), m_capacity(n) + : m_under(new value_type[n]), m_size(n), m_capacity(n), m_alloc(alloc) { for (size_type i = 0; i < n; i++) m_under[i] = val; @@ -49,16 +52,13 @@ namespace ft Vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type()) - : m_under(new value_type[0]), m_size(0), m_capacity(0) + : m_under(new value_type[0]), m_size(0), m_capacity(0), m_alloc(alloc) { - for (; first != last; first++) + for (; first != last; ++first) push_back(*first); } - Vector (const Vector& x) - { - *this = x; - } + ~Vector() { delete [] m_under; } Vector& operator=(const Vector& x) { @@ -73,20 +73,88 @@ namespace ft return *this; } - ~Vector() + Vector (const Vector& x) + : m_under(new value_type[x.m_capacity]), + m_size(x.m_size), + m_capacity(x.m_capacity), + m_alloc(x.m_alloc) { - delete [] m_under; + for (size_type i = 0; i < m_size; i++) + m_under[i] = x.m_under[i]; } - iterator begin() { return iterator(*this, 0, 1); } - const_iterator begin() const { return iterator(*this, 0, 1); } - iterator end() { return const_iterator(*this, m_size, 1); } - const_iterator end() const { return const_iterator(*this, m_size, 1); } - iterator rbegin() { return iterator(*this, m_size - 1, -1); } - const_iterator rbegin() const { return iterator(*this, m_size - 1, -1); } - iterator rend() { return const_iterator(*this, -1, -1); } - const_iterator rend() const { return const_iterator(*this, -1, -1); } + class iterator + { + friend class Vector; + public: + iterator() : m_ptr(NULL), m_pos(-1), m_inc(0) {} + + iterator(const iterator& other) + : m_ptr(other.m_ptr), m_pos(other.m_pos), m_inc(other.m_inc) + {} + + iterator& operator=(const iterator& other) + { + if (this == &other) + return *this; + m_ptr = other.m_ptr; + m_pos = other.m_pos; + m_inc = other.m_inc; + return *this; + } + + ~iterator() {} + + value_type& operator*() { return (*m_ptr)[m_pos]; } + value_type* operator->() { return &(*m_ptr)[m_pos]; } + + bool operator==(const iterator& other) const { return m_pos == other.m_pos; } + bool operator!=(const iterator& other) const { return !(operator==(other)); } + bool operator<(const iterator& other) const { return m_pos < other.m_pos; } + bool operator>(const iterator& other) const { return other < *this; } + bool operator<=(const iterator& other) const { return !(other < *this); } + bool operator>=(const iterator& other) const { return !(*this < other); } + + iterator& operator++() { m_pos += m_inc; return *this; } + iterator& operator--() { m_pos -= m_inc; return *this; } + iterator operator++(int) { iterator copy(*this); m_pos += m_inc; return copy; } + iterator operator--(int) { iterator copy(*this); m_pos -= m_inc; return copy; } + + iterator operator+(int n) { iterator copy(*this); return copy += m_inc * n; } + iterator operator-(int n) { iterator copy(*this); return copy -= m_inc * n; } + iterator operator+(iterator& it) { iterator copy(*this); return copy += m_inc * it.m_pos; } + iterator operator-(iterator& it) { iterator copy(*this); return copy -= m_inc * it.m_pos; } + + iterator& operator+=(int n) { m_pos += n; return *this; } + iterator& operator-=(int n) { m_pos -= n; return *this; } + + value_type& operator[](size_type n) { return (*m_ptr)[m_pos + m_inc * n]; } + + // tmp + iterator(Vector* ptr, size_type pos, int inc) + : m_ptr(ptr), m_pos(pos), m_inc(inc) {} + protected: + + Vector* m_ptr; + size_type m_pos; + int m_inc; + }; + + class const_iterator : public iterator + { + // const value_type& operator*() { return m_ptr[m_pos]; } + // const value_type& operator->() { return m_ptr[m_pos]; } + }; + + iterator begin() { return m_type::iterator(this, 0, 1); } + iterator end() { return m_type::iterator(this, m_size, 1); } + iterator rbegin() { return m_type::iterator(this, m_size - 1, -1); } + iterator rend() { return m_type::iterator(this, -1, -1); } + const_iterator begin() const { return m_type::const_iterator(this, 0, 1); } + const_iterator end() const { return m_type::const_iterator(this, m_size, 1); } + const_iterator rbegin() const { return m_type::const_iterator(this, m_size - 1, -1); } + const_iterator rend() const { return m_type::const_iterator(this, -1, -1); } size_type size() const { return m_size; } size_type max_size() const { return UINT_MAX; } @@ -117,6 +185,8 @@ namespace ft void reserve(size_type n) { + if (n <= m_capacity) + return ; if (m_capacity < 2) m_capacity = 2; while (m_capacity < n) @@ -153,42 +223,43 @@ namespace ft template <typename InputIterator> void assign(InputIterator first, InputIterator last) { - size_type count; + size_type count; InputIterator copy(first); - for (count = 0; copy != last; copy++) + for (count = 0; copy != last; ++copy) count++; - reserve(count); - for (size_type i = 0; first != last; first++, i++) + resize(count); + for (size_type i = 0; first != last; ++first, i++) m_under[i] = *first; } void assign(size_type n, const value_type& val) { - reserve(n); - for (size_type i = 0; i < n; ++) + resize(n); + for (size_type i = 0; i < n; i++) m_under[i] = val; } void push_back(const value_type& val) { + reserve(m_size + 1); + m_under[m_size] = val; m_size++; - reserve(m_size); - m_under[m_size - 1] = val; } - void pop_back() + void pop_back() // call destructor with m_alloc ? { m_size--; - ~value_type(m_under[m_size]); } iterator insert(iterator position, const value_type& val) { m_size++; reserve(m_size); - for (iterator it = rbegin(); it != position; ++it) - *it = *(it - 1); + if (position != end()) + for (iterator it = rbegin(); it != position; ++it) + *it = *(it + 1); *position = val; + return position; } void insert(iterator position, size_type n, const value_type& val) @@ -201,30 +272,44 @@ namespace ft template <typename InputIterator> void insert(iterator position, InputIterator first, InputIterator last) { - for (; first != last; ++first) - insert(position, *first); + if (first == last) + return; + --last; + for (; last != first; --last) + insert(position, *last); + insert(position, *last); } iterator erase(iterator position) { + iterator ret(position); + for (; position != end(); ++position) *position = *(position + 1); m_size--; + return ret; } iterator erase(iterator first, iterator last) { size_type i; + size_type count; + iterator copy(first); + iterator ret(first); + + for (count = 0; copy != last; ++copy) + count++; for (i = 0; first != last && last + i != end(); ++first, i++) *first = *(last + i); - m_size -= i; + m_size -= count; + return ret; } void swap(Vector& x) { value_type* tmpUnder = m_under; - size_type* tmpSize = m_size; - size_type* tmpCapacity = m_capacity; + size_type tmpSize = m_size; + size_type tmpCapacity = m_capacity; m_under = x.m_under; m_size = x.m_size; @@ -243,121 +328,48 @@ namespace ft m_capacity = 0; } - class iterator + bool operator==(const Vector& rhs) const { - public: - iterator() : m_pos(-1) {} - - iterator(const iterator& other) { *this = other; } - - iterator& operator=(const iterator& other) - { - if (this == &other) - return *this; - m_ref = other.m_ref; - m_pos = other.m_pos; - m_inc = other.m_inc; - return *this; - } - - ~iterator() {} - - value_type& operator*() { return m_ref[m_pos]; } - value_type& operator->() { return m_ref[m_pos]; } - - bool operator==(const iterator& other) { return m_pos == other.m_pos; } - bool operator!=(const iterator& other) { return !(operator==(other)); } - - bool operator<(const iterator& other) { return m_pos < other.m_pos; } - bool operator>(const iterator& other) { return !(this <= other); } - bool operator<=(const iterator& other) { return !(this > other); } - bool operator>=(const iterator& other) { return !(this < other); } - - iterator& operator++() { m_pos += m_inc; return *this; } - iterator& operator--() { m_pos -= m_inc; return *this; } - iterator& operator++(int) { iterator copy(this); m_pos += m_inc; return copy; } - iterator& operator--(int) { iterator copy(this); m_pos -= m_inc; return copy; } - - iterator operator+(int n) { iterator copy(this); return copy += n; } - iterator operator-(int n) { iterator copy(this); return copy -= n; } - iterator operator+(iterator& it) { iterator copy(this); return copy += it.m_pos; } - iterator operator-(iterator& it) { iterator copy(this); return copy -= it.m_pos; } - - iterator& operator+=(int n) { m_pos += n; return *this; } - iterator& operator-=(int n) { m_pos -= n; return *this; } - - value_type& operator[](size_type n) { return m_ref[m_pos + n]; } - - private: - iterator(Vector* ref, size_type pos, int inc) - : m_pos(pos), m_ref(ref), m_inc(int) {} - - Vector& m_ref; - size_type m_pos; - int inc; + if (size() != rhs.size()) + return false; + for (size_type i = 0; i < size(); i++) + if (!((*this)[i] == rhs[i])) + return false; + return true; } - class const_iterator : public iterator + bool operator!=(const Vector& rhs) const { return !(*this == rhs); } + + bool operator<(const m_type& rhs) const { - const value_type& operator*() { return m_ref[m_pos]; } - const value_type& operator->() { return m_ref[m_pos]; } + size_type i = 0; + while (i < size() && i < rhs.size() && (*this)[i] == rhs[i]) + i++; + if (i == size() && i == rhs.size()) + return false; + if (i == size() || i == rhs.size()) + return i == size(); + return (*this)[i] < rhs[i]; } + bool operator>(const m_type& rhs) const { return rhs < *this; } + bool operator<=(const m_type& rhs) const { return !(rhs < *this); } + bool operator>=(const m_type& rhs) const { return !(*this < rhs); } + + private: value_type* m_under; size_type m_size; size_type m_capacity; + allocator_type m_alloc; }; } -template <typename T, typename Alloc> -bool operator==(const Vector<T, Alloc>& lhs, const Vector<T, Alloc>& rhs) -{ - if (lhs.size() != rhs.size()) - return false; - for (Vector::size_type i = 0; i < lhs.size(); i++) - if (!(lhs[i] == rhs[i])) - return false; - return true; -} - -template <typename T, typename Alloc> -bool operator!=(const Vector<T, Alloc>& lhs, const Vector<T, Alloc>& rhs) -{ - return !(lhs == rhs); -} - -template <typename T, typename Alloc> -bool operator<const Vector<T, Alloc>& lhs, const Vector<T, Alloc>& rhs) -{ - for (Vector::size_type i = 0; i < lhs.size() && i < rhs.size(); i++) - if (lhs[i] < rhs[i] && !(rhs[i] < lhs[i])) - return true; - return false; -} - -template <typename T, typename Alloc> -bool operator<=const Vector<T, Alloc>& lhs, const Vector<T, Alloc>& rhs) -{ - return !(rhs < lhs); -} - -template <typename T, typename Alloc> -bool operator>const Vector<T, Alloc>& lhs, const Vector<T, Alloc>& rhs) -{ - return rhs < lhs; -} - -template <typename T, typename Alloc> -bool operator>=const Vector<T, Alloc>& lhs, const Vector<T, Alloc>& rhs) -{ - return !(lhs < rhs); -} - -template <typename T, typename Alloc> -void swap(Vector<T, Alloc>& x, Vector<T, Alloc>& y) -{ - x.swap(y); -} +// automatic ? +// template <typename T, typename Alloc> +// void swap(ft::Vector<T, Alloc>& x, ft::Vector<T, Alloc>& y) +// { +// x.swap(y); +// } #endif |