4
\$\begingroup\$

I've developed a custom vector class in C++, complete with functionalities like assignment, push_back(), emplace_back(), pop_back(), clear(), and size(). I would greatly appreciate any feedback on design or implementation details to ensure the class is as robust as possible.

#include <iostream>
template<typename T>
class Vector {
private:
    T* m_Data = nullptr;
    size_t m_Size = 0;
    size_t m_Capacity = 0;

    void ReAlloc(size_t newCapacity) {
        T* newBlock = new T[newCapacity];
        for(size_t i = 0; i < m_Size; i++)
            newBlock[i] = std::move(m_Data[i]);
        m_Capacity = newCapacity;
        std::swap(newBlock, m_Data);
        delete[] newBlock;
    }


public:
    Vector();
    Vector(size_t size);
    Vector(size_t size, const T& initial);
    Vector(const Vector& v);
    Vector(Vector&& v);
    void Push_Back(const T& value);

    const T& operator[](size_t index) const;
    T& operator[](size_t index);

    template<typename... Args>
    T& EmplaceBack(Args&&... args);

    void PopBack();

    void Clear();
    size_t Size() const {return m_Size;}
};

template<class T>
Vector<T>::Vector() {
    ReAlloc(2);
    m_Size = 0;
}

template<class T>
Vector<T>::Vector(size_t size) {
    ReAlloc(size * 2 + 1);
    m_Size = size;
}

template<class T>
Vector<T>::Vector(size_t size, const T& initial) {
    ReAlloc(size * 2 + 1);
    for(size_t i = 0; i < size; i++) m_Data[i] = initial;
    m_Size = size;
}

template<class T>
Vector<T>::Vector(const Vector& v) {
    ReAlloc(v.m_Capacity);
    for(size_t i = 0; i < m_Size; i++) m_Data[i] = v.m_Data[i];
    m_Size = v.m_Size;
}

template<class T>
Vector<T>::Vector(Vector&& v) {
    ReAlloc(v.m_Capacity);
    for(size_t i = 0; i < m_Size; i++) m_Data[i] = v.m_Data[i];
    m_Size = v.m_Size;
}

template<class T>
void Vector<T>:: Push_Back(const T& value) {
    if(m_Size >= m_Capacity) ReAlloc(m_Capacity * 2 + 1);
    m_Data[m_Size] = value;
    m_Size++;
}

template<class T>
const T& Vector<T>:: operator[](size_t index) const
{
    return m_Data[index];
}

template<class T>
T& Vector<T>:: operator[](size_t index)
{
    return m_Data[index];
}

template<class T>
template<typename... Args>
T& Vector<T>:: EmplaceBack(Args&&... args) {
    if(m_Size >= m_Capacity) ReAlloc(m_Capacity * 2 + 1);
    new(&m_Data[m_Size])  T(std::forward<Args>(args)...);
    return m_Data[m_Size++];
}

template<class T>
void Vector<T>:: PopBack() {
    if(m_Size > 0) {
        m_Size--;
        m_Data[m_Size].~T();
    }
}

template<class T>
void Vector<T>:: Clear() {
    for(size_t i = 0; i < m_Size; i++) m_Data.~T();
    m_Size = 0;
}
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

This is already quite good, and implementing this much yourself will have given you a deeper understanding of C++ and how containers work. We will of course compare this to the gold standard, which is std::vector itself.

Naming things

When naming things, the most important thing is to be consistent. I see you used capitalized names for all member functions, but some contain underscores between words (Push_Back()), others don't (EmplaceBack()). Also, reallocate is one word, so I would expect Realloc() instead of ReAlloc().

However, in this case you can make your class much more useful if you simply follow the exact naming scheme that std::vector does, so: push_back(), emplace_back(), clear() and so on. The huge benefit from this is that your class can then be used as a drop-in replacement for std::vector, and that the standard library algorithms that work on std::vector will now also be able to work with your Vector.

Missing functionality

If you compare std::vector with Vector you will see that the former has quite a bit more member functions. In particular, you can get iterators using begin() and end(). If you implement those, then even more algorithms will work with Vector, and you can then also use them in range-based for loops.

Even if you don't want to implement all of that (yet), you should at least implement a destructor that will delete the allocated memory, otherwise your class will become a memory leak.

If you want to implement the rest of std::vector's interface, also pay attention to noexcept and constexpr annotations, and note that std::vector has more than one template parameter.

ReAlloc() does not handle exceptions correctly

There are two things that can throw exceptions inside ReAlloc():

  1. new itself can fail if you run out of memory. This is fine though, you don't handle the exception but it will be propagated to the caller, which can then try to handle it if they want.

  2. Copying/moving data from the old to the new array can throw, depending on whether T's copy/move assignment operators throw. This could happen at any point in the for loop. When this happens, you have some problems:

    • There are now two memory allocations.
    • Some of the values from the old allocation have been moved to the new one.

    If you don't handle this, you'll end up with another memory leak, and an undefined state of the values in m_Data. You should catch the exception, undo the moves of anything you have moved so far, then delete newBlock, and then rethrow the exception so the caller knows something went wrong.

The move constructor doesn't move

Your move constructor is exactly the same as the copy constructor. The whole point of this is that you can move the data much more efficiently than copying it: you can just std::swap() all the member variables.

Placement new and (un)initialized memory

For non-trivial types T, you have to be careful how you allocate and deallocate memory. If you use new T[newCapacity], then the new operator will already default-construct newCapacity elements. So there will then already be valid objects in m_Data. However, when you Push_Back(), you do a placement-new right on top of those valid objects. Consider that I write:

Vector<Vector<int>> foo;
foo.EmplaceBack();

The default constructor of foo in that first line will ReAlloc(2), so this in turn will default-construct two Vector<int>s, which each allocate and default-construct two ints.

In the second line, a placement new on the first element of foo's m_Data will be done. This will ignore the Vector<int> that's already there, and will construct a new one without destructing the old one. So even assuming you did implement a proper destructor, this will have caused a memory leak.

So either you accept that there are already live objects, in which case your EmplaceBack() should not do a placement-new, but just do:

m_Data[m_Size] = T(std::forward<Args>(args)...);

Or you should allocate uninitialized memory in ReAlloc() (for example, using new char[newCapacity * sizeof(T)], but you also need to take the alignment restrictions of T into account), and then use placement-new everywhere (also when moving data in ReAlloc()).

The latter is harder to do, but it avoids unnecessary construction and destruction of objects, and is also what std::vector does.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.