Remaking the C++ std::vector class

Question

I haven't really programmed in C++ for about a year, and realised that I should get back into it, and tried my abilities out by remaking the STD vector class. However, my C++ is a bit rusty at the moment, and was wondering if I have made many mistakes in my implementation.

# ifndef VECTOR_H
# define VECTOR_H
# include <memory>

namespace test
    {
    template
        <class T,
    class A>
    class vector;

    template
        <class A>
        class vector_alloc_types
        {
    public:
        typedef typename A::value_type value_type;
        typedef typename A::size_type size_type;
        typedef typename A::reference reference;
        typedef typename A::const_reference const_reference;
        typedef typename A::pointer iterator;
        typedef typename A::const_pointer const_iterator;
        typedef typename A::const_pointer const_pointer;
        typedef A allocator_type;
        };

    template
        <class T,
        class A>
        class vector_base
        {
        friend class vector<T, A>;
    public:
        typedef typename A::pointer pointer;
        vector_base()
            {
            vm_begin = pointer();
            value_end = pointer();
            memory_end = pointer();
            }
    private:
        pointer vm_begin, value_end, memory_end;
        };

    template 
        <class T,
        class A = std::allocator<T> >
        class vector
            : public vector_alloc_types<A>,
            public vector_base<T, A>
        {
    public:
        typedef vector<T, A> my_T;
        typedef vector_base<T, A> my_base;

        vector()
            : my_base()
            {
            }

        vector(my_T const &rhs)
            {
            if (allocate(rhs.size()))
                {
                try
                    {
                    this->value_end = std::uninitialized_copy(rhs.vm_begin, rhs.value_end, this->vm_begin);
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                }
            }

        vector(pointer first, pointer last)
            : my_base()
            {
            if (allocate(std::distance(first, last)))
                {
                try
                    {
                    this->value_end = std::uninitialized_copy(first, last, this->vm_begin);
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                }
            }

        template<size_type sz>
        vector(T arr[sz])
            {
            if (allocate(sz))
                {
                try
                    {
                    this->value_end = std::uninitialized_copy_n(arr, sz, this->vm_begin);
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                }
            }

        vector(size_type sz)
            {
            if (allocate(sz))
                {
                try
                    {
                    this->value_end = std::uninitialized_fill_n(this->vm_begin, sz, T());
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                }
            }

        vector(size_type sz, T const &val)
            {
            if (allocate(sz))
                {
                try
                    {
                    this->value_end = std::uninitialized_fill_n(this->vm_begin, sz, val);
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                }
            }

        ~vector()
            {
            kill();
            }

        void operator=(my_T &rhs)
            {
            if (this != &rhs)
                {
                assign(rhs);
                }
            }

        template<unsigned sz>
        void operator=(T (&arr)[sz])
            {
            assign(&arr[0], &arr[sz]);
            }

        void clear()
            {
            wipe(this->vm_begin, this->value_end);
            }

        iterator begin()
            {
            return (this->vm_begin);
            }

        const_iterator cbegin() const
            {
            return ((const_iterator)this->vm_begin);
            }

        iterator end()
            {
            return (this->value_end);
            }

        const_iterator cend() const
            {
            return ((const_iterator)this->value_end);
            }

        void swap(my_T &rhs)
            {
            std::swap(this->vm_begin, rhs.vm_begin);
            std::swap(this->value_end, rhs.value_end);
            std::swap(this->memory_end, rhs.memory_end);
            }

        void shrink_to_fit()
            {
            if (has_spare_capacity())
                {
                my_T tmp(*this);
                swap(tmp);
                }
            }

        void erase(iterator iter)
            {
            pointer tmp;
            if (iter == (this->value_end - 1))
                {
                pop_back();
                }
            else if (iter == this->vm_begin)
                {
                pop_front();
                }
            else if (iterator_in_range(iter))
                {
                tmp = allocator_type().allocate(size() - 1);
                pointer tmp2 = std::uninitialized_copy(this->vm_begin, iter, tmp);
                tmp2 = std::uninitialized_copy((iter + 1), this->value_end, tmp2);
                assign(tmp, tmp2);
                }
            }

        void erase(iterator first, iterator last)
            {
            if (last == (this->value_end - 1))
                {
                while (last-- != first)
                    {
                    pop_back();
                    }
                pop_back();
                }
            else if (first == this->vm_begin)
                {
                while (first++ != last)
                    {
                    pop_front();
                    }
                pop_front();
                }
            else if (iterator_in_range(first) && iterator_in_range(last))
                {
                pointer tmp = allocator_type().allocate(size() - std::distance(first, last));
                pointer tmp2 = std::uninitialized_copy(this->vm_begin, first, tmp);
                tmp2 = std::uninitialized_copy((last + 1), this->value_end, tmp2);
                assign(tmp, tmp2);
                }
            }

        void insert(iterator iter, T const &val)
            {
            T v1 = val;
            if (iter == this->vm_begin)
                {
                push_front(v1);
                }
            else if (iter == (this->value_end - 1))
                {
                push_back(v1);
                }
            else if (iterator_in_range(iter))
                {
                allocator_type alloc;
                pointer tmp = alloc.allocate(realloc_size(size() + 1));
                pointer tmp2 = std::uninitialized_copy(this->vm_begin, iter, tmp);
                alloc.construct(tmp2++, v1);
                tmp2 = std::uninitialized_copy(iter, this->value_end, tmp2);
                assign(tmp, tmp2);
                }
            }

        void insert(iterator iter, int count, T const &val)
            {
            T v1 = val;
            if (iter == this->vm_begin)
                {
                while (count--)
                    {
                    push_front(v1);
                    }
                }
            else if (iter == (this->value_end - 1))
                {
                while (count--)
                    {
                    push_back(v1);
                    }
                }
            else if (iterator_in_range(iter))
                {
                allocator_type alloc;
                pointer tmp = alloc.allocate(realloc_size(size() + 1));
                pointer tmp2 = std::uninitialized_copy(this->vm_begin, iter, tmp);
                while (count--)
                    {
                    alloc.construct(tmp2++, v1);
                    }
                tmp2 = std::uninitialized_copy(iter, this->value_end, tmp2);
                assign(tmp, tmp2);
                }
            }

        void insert(iterator iter, iterator first, iterator last)
            {
            if (iter == this->vm_begin)
                {
                while (first != last)
                    {
                    push_front(*(first++));
                    }
                }
            else if (iter == (this->value_end - 1))
                {
                while (first != last)
                    {
                    push_back(*(first++));
                    }
                }
            else if (iterator_in_range(iter))
                {   
                allocator_type alloc;
                pointer tmp = alloc.allocate(realloc_size(size() + 1));
                pointer tmp2 = std::uninitialized_copy(this->vm_begin, iter, tmp);
                while (first != last)
                    {
                    alloc.construct(tmp2++, *(first++));
                    }
                tmp2 = std::uninitialized_copy(iter, this->value_end, tmp2);
                assign(tmp, tmp2);
                }
            }

        void push_back(T const &val)
            {
            allocator_type alloc;
            T v1 = val;
            if (has_spare_capacity())
                {
                this->value_end++;
                alloc.construct(this->value_end - 1, v1);
                }
            else if (reallocate(realloc_size(size() + 1)))
                {
                this->value_end++;
                alloc.construct(this->value_end - 1, v1);
                }
            }

        void pop_back()
            {
            pointer tmp = allocator_type().allocate(size() - 1);
            pointer tmp2 = std::uninitialized_copy(this->vm_begin, this->value_end - 1, tmp);
            assign(tmp, tmp2);
            }

        void push_front(T const &val)
            {
            allocator_type alloc;
            T v1 = val;
            vector tmp;
            tmp.push_back(v1);
            for (iterator it = this->vm_begin; it != this->value_end; ++it)
                {
                tmp.push_back(*it);
                }
            swap(tmp);
            }

        void pop_front()
            {
            pointer tmp = allocator_type().allocate(size() - 1);
            pointer tmp2 = std::uninitialized_copy(this->vm_begin + 1, this->value_end, tmp);
            assign(tmp, tmp2);
            }

        size_type size() const
            {
            return (this->value_end - this->vm_begin);
            }

        reference operator[](size_type pos)
            {
            return (*(this->vm_begin + pos));
            }

        const_reference operator[](size_type pos) const
            {
            return (*(this->vm_begin + pos));
            }

    private:
        bool allocate(size_type sz)
            {
            allocator_type alloc;
            if (alloc.max_size() > sz)
                {
                try
                    {
                    this->vm_begin = alloc.allocate(sz);
                    this->value_end = this->vm_begin;
                    this->memory_end = this->vm_begin + sz;
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                return (true);
                }
            return (false);
            }

        bool reallocate(size_type sz)
            {
            allocator_type alloc;
            if (alloc.max_size() > sz)
                {
                try
                    {
                    pointer nbegin, nvend, nmend;
                    nbegin = alloc.allocate(sz);
                    nmend = nbegin + sz;
                    nvend = std::uninitialized_copy(this->vm_begin, this->value_end, nbegin);
                    this->vm_begin = nbegin;
                    this->value_end = nvend;
                    this->memory_end = nmend;
                    }
                catch (...)
                    {
                    kill();
                    throw;
                    }
                return (true);
                }
            return (false);
            }

        size_type realloc_size(size_type sz) const
            {
            return ((allocator_type().max_size() > (sz * 1.5)) ? (sz * 1.5) : sz);
            }

        bool iterator_in_range(const_iterator iter) const
            {
            return (iter >= this->vm_begin && iter < this->value_end);
            }

        void assign(my_T &rhs)
            {
            assign(rhs.vm_begin, rhs.value_end);
            }

        void assign(pointer first, pointer last)
            {
            size_type sz = std::distance(first, last);
            if (sz > capacity())
                {
                if (reallocate(realloc_size(sz)))
                    {
                    wipe(this->vm_begin, this->value_end);
                    this->value_end = std::uninitialized_copy(first, last, this->vm_begin);
                    }
                }
            else
                {
                wipe(this->vm_begin, this->value_end);
                this->value_end = std::uninitialized_copy(first, last, this->vm_begin);
                }
            }

        void wipe(pointer ptr)
            {
            allocator_type().destroy(ptr);
            }

        void wipe(pointer first, pointer last)
            {
            allocator_type alloc;
            while (first != last)
                {
                alloc.destroy(first++);
                }
            }

        void wipe(pointer ptr, size_type dist)
            {
            allocator_type alloc;
            while (dist-- != 0)
                {
                alloc.destroy(ptr);
                }
            }

        void kill()
            {
            if (this->vm_begin != pointer())
                {
                wipe(this->vm_begin, this->value_end);
                allocator_type().deallocate(this->vm_begin, capacity());
                }
            }

        inline size_type capacity() const
            {
            return (this->memory_end - this->vm_begin);
            }

        inline size_type spare_capacity() const
            {
            return (this->memory_end - this->value_end);
            }

        bool has_spare_capacity() const
            {
            return (spare_capacity() > 0);
            }
        };
    }

# endif

Answer 1

This is certainly not a bad attempt at all. I especially appreciate the detail to the correct use of uninitialized memory.

Indentation

It is great that you are using a consistent indentation style. However, it is an uncommon one, which I think will be off-putting for many C++ developers. A more common style would be:

template <class T, class A>
class vector_base
{
    friend class vector<T, A>;
public:
    typedef typename A::pointer pointer;
    …
};

Prefer using over typedef

using has some advantages over typedef, in particular:

• The name is clearly separated from the type it aliases (which is especially nice if the type is an array, a function pointer, or combination thereof).
• You can also use it without assigning a new name to something, in which case you bring a name from one namespace into another.

It allows you to write:

template <class A>
struct vector_alloc_types
{
    using typename A::value_type;
    …
    using typename A::const_pointer;
    using allocator_type = A;
};

Don't use inheritance

I fail to see why you are defining vector_alloc_types and vector_base, and have vector inherit from it. Nothing is gained from it, and now you have to worry about:

• Making vector_base a friend of vector.
• Does public inheritance expose any members from the base classes that you don't want exposed in vector?
• Does an empty class like vector_alloc_types take up space? See empty base optimization.

I would avoid all that by just keeping everything in a single class.

Make use of default member initialization

You can avoid having to explicitly initialize member variables in the constructors if you use default member initialization instead, like so:

template <class T, class A = std::allocator<T>>
class vector
{
    using pointer = …;
    …
    pointer vm_begin{};
    pointer value_end{};
    pointer memory_end{};

public:
    vector() = default;
    vector(pointer first, pointer last)
    {
        if (allocate(std::distance(first, last))) {
            …
        }
    }
    …
};

Pay closer attention to the interface of std::vector

If you want to remake std::vector, pay close attention to its interface and copy it exactly. Your vector differs in several cases, including:

• Missing constructor overloads. Especially since you did add a template parameter for the allocator, it is weird to not see a constructor that takes an allocator object as a parameter.
• Missing move constructor and assignment operator. These can easily be implemented in terms of swap().
• Assignment operators should return a reference to *this when possible. Almost any class in the standard library does this, and allows you to write code like a = b = c and if ((a = b)).
• Missing empty(), max_size(), emplace_back() and relational operators.
• Incorrect type aliases. For example your value_type is equal to A::value_type, but in std::vector it is equal to T. Don't assume those are the same; this is only guaranteed for the default allocator.

Unnecessary use of this->

It is almost never necessary to use this-> in C++. Omit it where possible, it just adds noise to the code.

Don't kill() in the constructors

Your kill() will try to destroy the objects in the vector when functions like std::uninitialized_copy() fail. However, if the latter fails, it is likely one or more objects were not constructed. Calling a destructor on an object that was not properly constructed has undefined behavior. Also, std::uninitialized_copy() and friends will already destroy any objects they constructed for you if they throw an exception.

Memory leaks

In erase(), if you erase an element from the middle, you will make a copy of the whole vector minus the erased element, and then you assign() that copy to the current vector. However, you never free the memory from the copy. You make the same mistake in more functions.

A simple fix would be to use the same technique as you used in push_front(): create a temporary vector, copy things into that, and then swap() it.

Inefficient operations

Erasing an element should not require you to copy all of the other elements; you only need to move the elements after the erased element one position towards the front.

The exact amount of optimizations you can do here depends on the exception safety guarantees you want to have. If calling erase() throws, should the contents of the vector be the same as before the call to erase()? If so, then if T doesn't make any guarantees about exception safety of coping or moving its elements, then you have no option but to make a full copy of the vector first, and then swap()ing.

But pop_back() is a special case where you know you don't need to copy anything at all; you just need to destroy the last element.

In push_back(), if there was no spare capacity, you only resize the storage to hold one more element. This is very inefficient: consider filling a vector by repeatedly calling push_back(): each time it has to allocate new memory and copy the existing elements. This results in \$O(N^2)\$ copies just to add \$N\$ elements. The usual solution here is to double the capacity every time it gets full; this amortizes the cost of the copies to \$O(N)\$.

Missing noexcept and constexpr specifiers

While you did make member functions const where appropriate, you can go even further and makes some member functions constexpr and/or noexcept.