Having already attempted an implementation of the std::vector class here, I decided to take the comments on board and also do some new bits myself (mainly the algorithms for allocation and insert).
I have a commented version, but it exceeded the character limit so I had to add the non-commented version. However, I can provide specific commented functions if you would like in the comment section.
The main reason for doing this was to check that I am doing everything safely, which I am more confident about this time, as I have never had errors during the process, while in my previous implementation, I had some errors when testing it and had to fix those a few times, but also to check the efficiency of the code and if I could make some algorithms/functions better.
# ifndef __VECTOR_H__ # define __VECTOR_H__ # include <memory> # include <algorithm> template<typename T, typename A> class vector; template<typename B, typename R> class vector_iterator; template<typename I> class vector_reverse_iterator; template<typename A> class vector_base { public: typedef vector_base<A> base_type; typedef typename A allocator_type; typedef typename A::pointer pointer; friend class vector<typename A::value_type, A>; friend class vector_iterator<base_type, typename A::reference>; friend class vector_iterator<base_type, typename A::const_reference>; friend class vector_reverse_iterator<vector_iterator<base_type, typename A::reference> >; friend class vector_reverse_iterator<vector_iterator<base_type, typename A::const_reference> >; private: vector_base(allocator_type const &al) : ms_begin(pointer()), s_end(pointer()), m_end(pointer()), alloc(al) { } ~vector_base() { } base_type *get_base() { return (this); } pointer ms_begin, s_end, m_end; allocator_type alloc; }; # ifndef VECTOR_ITERATOR_CHECK_LEVEL # define VECTOR_ITERATOR_CHECK_LEVEL 1 # endif template<typename B, typename R = typename B::allocator_type::reference> class vector_iterator { public: typedef vector_iterator<B, R> this_t; typedef B base_type; typedef typename B::allocator_type::pointer pointer; typedef typename R reference; typedef typename B::allocator_type::const_reference const_reference; typedef typename B::allocator_type::value_type value_type; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef std::random_access_iterator_tag iterator_category; friend class vector<value_type, typename B::allocator_type>; friend class vector_reverse_iterator<this_t>; friend class vector_reverse_iterator<vector_iterator<B, const_reference> >; friend class vector_iterator<B, const_reference>; vector_iterator(base_type *b, pointer p) : base(b), ptr(p) { } template<typename R = reference> vector_iterator(vector_iterator<B, R> const &rhs) : base(rhs.base), ptr(rhs.ptr) { } ~vector_iterator() { } this_t &operator=(this_t const &rhs) { base = rhs.base; ptr = rhs.ptr; return (*this); } this_t &operator++() { ++ptr; return (*this); } this_t operator++(int) { this_t temp(*this); ++ptr; return (temp); } this_t &operator--() { --ptr; return (*this); } this_t operator--(int) { this_t temp(*this); --ptr; return (temp); } this_t operator+(size_type offset) const { return (this_t(base, ptr + offset)); } this_t operator-(size_type offset) const { return (this_t(base, ptr - offset)); } difference_type operator-(this_t const &rhs) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_compatible(rhs); # endif return (ptr - rhs.ptr); } this_t &operator+=(size_type offset) { ptr += offset; return (*this); } this_t &operator-=(size_type offset) { ptr -= offset; return (*this); } reference operator*() const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_validity(*this, ptr_in_seq); # endif return (*ptr); } reference operator[](size_type offset) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_validity(this_t(base, ptr + offset), ptr_in_seq); # endif return (*(ptr + offset)); } pointer operator->() const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_validity(*this, ptr_in_seq); # endif return (ptr); } bool operator==(this_t const &rhs) const { return (ptr == rhs.ptr); } bool operator!=(this_t const &rhs) const { return (!((*this) == rhs)); } bool operator<(this_t const &rhs) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_compatible(rhs); # endif return (ptr < rhs.ptr); } bool operator>(this_t const &rhs) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_compatible(rhs); # endif return (ptr > rhs.ptr); } bool operator<=(this_t const &rhs) const { return (!(ptr > rhs.ptr)); } bool operator>=(this_t const &rhs) const { return (!(ptr < rhs.ptr)); } private: pointer ptr; base_type *base; static void check_validity(this_t const &it, bool (*test)(this_t const &)) { if (!test(it)) { throw std::exception("iterator out of range"); } } void check_compatible(this_t const &it) const { if (it.base != base) { throw std::exception("iterators incompatible (not in same container)"); } } static bool ptr_in_seq(this_t const &it) { return (it.ptr >= it.base->ms_begin && it.ptr < it.base->s_end); } static bool ptr_in_seq_or_end(this_t const &it) { return (it.ptr >= it.base->ms_begin && it.ptr <= it.base->s_end); } }; template<typename I> class vector_reverse_iterator { public: typedef vector_reverse_iterator<I> this_t; typedef typename I::base_type base_type; typedef typename I::pointer pointer; typedef typename I::reference reference; typedef typename I::const_reference const_reference; typedef typename I::size_type size_type; typedef typename I::difference_type difference_type; friend class vector_reverse_iterator<vector_iterator<base_type, const_reference> >; vector_reverse_iterator(I const &it) : base(it.base) { size_type from_begin = (it.ptr - it.base->ms_begin) + 1; ptr = (it.base->s_end - from_begin); } template<typename R = reference> vector_reverse_iterator(vector_reverse_iterator< vector_iterator<base_type, R> > const &rhs) : base(rhs.base), ptr(rhs.ptr) { } ~vector_reverse_iterator() { } this_t &operator=(this_t const &rhs) { base = rhs.base; ptr = rhs.ptr; return (*this); } this_t &operator++() { --ptr; return (*this); } this_t operator++(int) { this_t temp(*this); --ptr; return (temp); } this_t &operator--() { ++ptr; return (*this); } this_t operator--(int) { this_t temp(*this); ++ptr; return (temp); } this_t operator+(size_type offset) const { return (this_t(base, ptr - offset)); } this_t operator-(size_type offset) const { return (this_t(base, ptr + offset)); } difference_type operator-(this_t const &rhs) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_compatible(rhs); # endif return (rhs.ptr - ptr); } this_t &operator+=(size_type offset) { ptr -= offset; return (*this); } this_t &operator-=(size_type offset) { ptr += offset; return (*this); } reference operator*() const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_validity(*this, ptr_in_seq); # endif return (*ptr); } reference operator[](size_type offset) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_validity(this_t(base, ptr - offset), ptr_in_seq); # endif return (*(ptr + offset)); } pointer operator->() const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_validity(*this, ptr_in_seq); # endif return (ptr); } bool operator==(this_t const &rhs) const { return (ptr == rhs.ptr); } bool operator!=(this_t const &rhs) const { return (!((*this) == rhs)); } bool operator<(this_t const &rhs) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_compatible(rhs); # endif return (ptr > rhs.ptr); } bool operator>(this_t const &rhs) const { # if VECTOR_ITERATOR_CHECK_LEVEL >= 1 check_compatible(rhs); # endif return (ptr < rhs.ptr); } bool operator<=(this_t const &rhs) const { return (!(ptr < rhs.ptr)); } bool operator>=(this_t const &rhs) const { return (!(ptr > rhs.ptr)); } private: pointer ptr; base_type *base; static void check_validity(this_t const &it, bool (*test)(this_t const &)) { if (!test(it)) { throw std::exception("iterator out of range"); } } void check_compatible(this_t const &it) const { if (it.base != base) { throw std::exception("iterators incompatible (not in same container)"); } } static bool ptr_in_seq(this_t const &it) { return (it.ptr > (it.base->ms_begin - 1) && it.ptr <= (it.base->s_end - 1)); } static bool ptr_in_seq_or_end(this_t const &it) { return (it.ptr >= (it.base->ms_begin - 1) && it.ptr <= (it.base->s_end - 1)); } }; template<typename T, typename A = std::allocator<T> > class vector : public vector_base<A> { public: typedef typename A::value_type value_type; typedef typename A::const_pointer const_pointer; typedef typename A::reference reference; typedef typename A::const_reference const_reference; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef vector_iterator<base_type> iterator; typedef vector_iterator<base_type, const_reference> const_iterator; typedef vector_reverse_iterator<iterator> reverse_iterator; typedef vector_reverse_iterator<const_iterator> const_reverse_iterator; typedef vector<T, A> this_t; explicit vector(allocator_type const &al = allocator_type()) : base_type(al) { } explicit vector(size_type count, const_reference value = value_type(), allocator_type const &al = allocator_type()) : base_type(al) { assign(count, value); } template<typename InIt> vector(typename std::enable_if<!std::is_integral<InIt>::value, InIt> first, typename std::enable_if<!std::is_integral<InIt>::value, InIt> last, allocator_type const &al = allocator_type()) : base_type(al) { assign(first, last); } vector(this_t const &rhs) : base_type(rhs.alloc) { if (&rhs != this) { assign(rhs.ms_begin, rhs.s_end); } } void assign(size_type count, value_type const &value = value_type()) { if (is_unconstructed()) { allocate(count * 1.5); } else { if (count > capacity()) { reallocate(count * 1.5); } wipe_values(); } this->s_end = std::uninitialized_fill_n( this->ms_begin, count, value); } template<typename InIt> typename std::enable_if<!std::is_integral<InIt>::value, void>::type assign(InIt first, InIt last) { difference_type count = (last - first); if (is_unconstructed()) { allocate(count * 1.5); } else { if (count > capacity()) { reallocate(count * 1.5); } wipe_values(); } this->s_end = std::uninitialized_copy( first, last, this->ms_begin); } this_t &operator=(this_t const &rhs) { if (&rhs != this) { assign(rhs.ms_begin, rhs.s_end); } return (*this); } iterator erase(iterator where) { return (erase(where, where + 1)); } iterator erase(iterator first, iterator last) { iterator::check_validity(first, iterator::ptr_in_seq); iterator::check_validity(last, iterator::ptr_in_seq_or_end); difference_type diff = (last - first); size_type fpos = (first.ptr - this->ms_begin), lpos = (last.ptr - this->ms_begin); std::rotate(this->ms_begin + fpos, this->ms_begin + lpos, this->s_end); while (diff--) { this->alloc.destroy(--this->s_end); } return (iterator(this->get_base(), this->ms_begin + (lpos - (last - first)))); } void insert(iterator where, const value_type &value = value_type()) { insert(where, 1, value); } void insert(iterator where, unsigned count, const value_type &value = value_type()) { iterator::check_validity(where, iterator::ptr_in_seq_or_end); size_type wpos = (where.ptr - this->ms_begin); if (is_unconstructed()) { allocate(count * 1.5); } else { if (size() + count > capacity()) { reallocate((size() + count) * 1.5); } } size_type c2 = count; while (c2--) { this->alloc.construct(this->s_end++, value); } std::rotate(this->ms_begin + wpos, this->s_end - count, this->s_end); } template<typename InIt> typename std::enable_if<!std::is_integral<InIt>::value, void>::type insert(iterator where, InIt first, InIt last) { iterator::check_validity(where, iterator::ptr_in_seq_or_end); size_type wpos = (where.ptr - this->ms_begin); difference_type diff = (last - first); if (is_unconstructed()) { allocate(diff * 1.5); } else { if (size() + diff > capacity()) { reallocate((size() + diff) * 1.5); } } while (first != last) { this->alloc.construct(this->s_end++, first++); } std::rotate(this->ms_begin + wpos, this->s_end - diff, this->s_end); } void push_back(value_type const &value) { insert(end(), value); } void pop_back() { erase(end() - 1); } void clear() { erase(begin(), end()); } iterator begin() { return (iterator(this->get_base(), this->ms_begin)); } iterator end() { return (iterator(this->get_base(), this->s_end)); } const_iterator begin() const { return (const_iterator(this->get_base(), this->ms_begin)); } const_iterator end() const { return (const_iterator(this->get_base(), this->s_end)); } reverse_iterator rbegin() { return (reverse_iterator(begin())); } reverse_iterator rend() { return (reverse_iterator(end())); } const_reverse_iterator rbegin() const { return (const_reverse_iterator(begin())); } const_reverse_iterator rend() const { return (const_reverse_iterator(end())); } reference operator[](size_type offset) { return (*(this->ms_begin + offset)); } const_reference operator[](size_type offset) const { return (*(this->ms_begin + offset)); } reference front() { return (*this->ms_begin); } const_reference front() const { return (*this->ms_begin); } reference back() { return (*(this->s_end - 1)); } const_reference back() const { return (*(this->s_end - 1)); } reference at(size_type offset) { if (offset >= size()) { throw std::exception("offset out of bounds"); } return (*(this->ms_begin + offset)); } const_reference at(size_type offset) const { if (offset >= size()) { throw std::exception("offset out of bounds"); } return (*(this->ms_begin + offset)); } void reserve(size_type count) { if (count > capacity()) { reallocate(count); } } void resize(size_type count, value_type value = value_type()) { if (count < size()) { erase(begin() + count, end()); } else { reserve(count); insert(end(), count - size(), value); } } void swap(this_t &rhs) { base_type b = *(this->get_base()); *(this->get_base()) = *(rhs.get_base()); *(rhs.get_base()) = b; } size_type size() const { return (this->s_end - this->ms_begin); } size_type capacity() const { return (this->m_end - this->ms_begin); } allocator_type get_allocator() const { return (this->alloc); } bool empty() const { return (this->ms_begin == this->s_end); } private: void allocate(size_type count) { if (count > this->alloc.max_size()) { throw std::exception("unable to allocate memory"); } this->ms_begin = this->alloc.allocate(count); this->s_end = this->ms_begin; this->m_end = this->ms_begin + count; } void reallocate(size_type count) { if (count > this->alloc.max_size()) { throw std::exception("unable to allocate memory"); } pointer nbegin = this->alloc.allocate(count); std::uninitialized_copy(this->ms_begin, this->s_end, nbegin); size_type sz = size(); wipe_all(); this->ms_begin = nbegin; this->s_end = nbegin + sz; this->m_end = nbegin + count; } void wipe_values() { if (!is_unconstructed()) { size_type sz = size(); while (this->ms_begin != this->s_end) { this->alloc.destroy(this->ms_begin++); } this->ms_begin -= sz; } } void wipe_all() { if (!is_unconstructed()) { wipe_values(); this->alloc.deallocate(this->ms_begin, capacity()); this->ms_begin = pointer(); this->s_end = pointer(); this->m_end = pointer(); } } bool is_unconstructed() const { return (this->ms_begin == pointer()); } }; # endif 
