Second implementation of std::vector

Question

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

Answer 1

Double underscore is reserved.

# ifndef __VECTOR_H__
# define __VECTOR_H__

These are technically illegal identifers as they are reserved for the implementation. refrain from using "double underscore" anywhere or and a single underscore as a prefix. Even if you know the rules like me others (like you) don't so best to avoid them.

I don't think this is technically legal.

# include <memory>
# include <algorithm>

The directive is "#include". Not all pre-processors are going to support this. So get out of that habit. Remember that the pre-processor phase happens before the compiler is invoked (though modern compilers roll it all it to one).

Even if it was legal I would advice against it as it is non standard and makes people second guess that it is going to work.

Style:

Having a hard time reading your code

Your indentation style is making it hard to read the code.

template<typename T,
    typename A>
    class vector;

Hard to see the class part. Align the types if you think it is two long. But put the class back under the template.

template<typename T, typename A>
class vector;

// or

template< typename T, // I would use this style only if the number/size
          typename A> // of templates was going to overwhelm the line.
class vector;

Another example:

vector_base(allocator_type const &al)
: ms_begin(pointer()),
s_end(pointer()),
m_end(pointer()),
alloc(al)
    {
    }

Nothing really lines up so I find it hard to parse.

vector_base(allocator_type const &al)
    : ms_begin(pointer())
    , s_end(pointer())
    , m_end(pointer())
    , alloc(al) 
    {
    }

OK. Putting the braces {} indented is something I personally don't like. But that is an accepted standard style so; though I don't personally like it you should be OK with that as long as you are following the coding conventions of your office.

Be consistent with your indenting.

    if (is_unconstructed())
        {
        allocate(count * 1.5);
        }
    else
        {
        if (count > capacity())
            {
            reallocate(count * 1.5);
            }
        wipe_values(); 
        }

Argg. Poop. I just realized you were consistent. But just emphasis why I hate this style.

Members:

Having a hard time spotting your class members. You need to make those more abvious (and put them at the top). so I can validate that your constructor actually correctly initializes all members.

DRY your code

The code in these two function looks nearly identical.
You should try and put common code into a single location. So when you fix a bug you only have to fix a bug in one place (not in multiple places).

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);
    }

Not sure I like the fact you have different behavior for a newly constructed verses an old vector if (is_unconstructed()). Seems like the stuff for a new vector only belongs in the constructor.

Did not realize how much I disliked that brace style until now.

Sorry I can't keep going.