Simplified implementation of std::vector in C++

By Posted on

Problem

I implemented a simplified version of a C++ std::vector/ArrayList learning from this link. From it, I tried to write an ArrayList class rather than a Vector. In my ArrayList implementation, I didn’t add iterators, operator[], emplace and a lot of other stuff because my main focus is to practice the following aspects:

  1. My ArrayList class guarantees strong exception safety, using the copy and swap idiom
  2. The container still works if T passed in is not default-constructible
  3. Correctness of the implementation of the Rule of Five
  4. General correctness and efficiency (i.e: No memory leaks, dangling pointers, etc.)

Because of those 4 areas I’d like to focus on practicing, I only had extra add and remove method in the class.

Please focus on those 4 areas I mentioned for reviewing my code, and any other important style choice errors or any other problems that I missed.

using namespace std;

template <typename T>
class ArrayList
{
    public:
        ArrayList();
        ArrayList(int size);
        ArrayList(const ArrayList<T>& other);
        ArrayList(ArrayList&& other);
        ~ArrayList();

        ArrayList<T>& operator= (const ArrayList<T>& other);
        ArrayList<T>& operator= (ArrayList&& other);

        void add(const T& item);
        void add(T&& item);
        void remove(int index);

        friend void swap(ArrayList& A, ArrayList& B)
        {
            using std::swap;
            swap(A.actualSize, B.actualSize);
            swap(A.allocatedSize, B.allocatedSize);
            swap(A.arr, B.arr);
        }

    private:
        T* arr;
        size_t allocatedSize;
        size_t actualSize;

        void resize();
        void addInternal(const T& item);
        void addInternalMove(T&& item);
};

template <typename T>
ArrayList<T>::ArrayList()
{
    arr = static_cast<T*>(::operator new(sizeof(T)*100));
    actualSize = 0;
    allocatedSize = 100;
}

template <typename T>
ArrayList<T>::ArrayList(int size)
{
    if(size < 0)
        throw;

    arr = static_cast<T*>(::operator new(sizeof(T)*size));
    actualSize = 0;
    allocatedSize = size;
}

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
{
    arr = static_cast<T*>(::operator new(sizeof(T)*size));
    allocatedSize = other.allocatedSize;
    actualSize = actualSize;

    for(size_t i = 0; i<other.actualSize; i++)
        add(other.arr[i]);
}

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other)
{
    swap(*this, other);
}

template <typename T>
ArrayList<T>::~ArrayList()
{
    for(size_t i = 0; i<actualSize; i++)
    {
        arr[i].~T();
    }::operator delete(arr);
}

template <typename T>
ArrayList& ArrayList<T>::operator =(const ArrayList<T>& other)
{
    ArrayList tmp(other);
    swap(*this, tmp);
    return *this;
}

template <typename T>
ArrayList& ArrayList<T>::operator =(ArrayList<T>&& other)
{
    swap(*this, other);
}

template <typename T>
void ArrayList<T>::resize()
{
    allocatedSize *= 2;
    ArrayList tmp(allocatedSize);

    for(size_t i=0; i<actualSize; i++)
        addInternal(arr[i]);

    swap(*this, tmp);
}

template <typename T>
void ArrayList<T>::add(const T& item)
{
    if(actualSize >= allocatedSize)
        resize();

    addInternal(item);
}

template <typename T>
void ArrayList<T>::add(T&& item)
{
    if(actualSize >= allocatedSize)
        resize();

    addInternalMove(move(item));
}

template <typename T>
void ArrayList<T>::addInternal(const T& item)
{
    new (arr+actualSize)T(item);
    actualSize++;
}

template <typename T>
void ArrayList<T>::addInternalMove(T&& item)
{
    new (arr+actualSize)T(move(item));
    actualSize++;
}

template <typename T>
void ArrayList<T>::remove(int index)
{
    if(index<0 || index>actualSize - 1)
        throw;

    for(size_t i=0; i<actualSize; i++)
    {
        if(index==i)
        {
            arr[i].~T();
            arr[i+1] = arr[i];
        }
        else if(index > i)
            arr[i+1] = arr[i];
    }
}

Solution

Thanks for reading my article. 🙂

Three Syntax Errors:

template <typename T>
ArrayList<T>& ArrayList<T>::operator =(const ArrayList<T>& other)
   //    ^^^ Missing

template <typename T>
ArrayList<T>& ArrayList<T>::operator =(ArrayList<T>&& other)
   //    ^^^ Missing

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
{
    arr = static_cast<T*>(::operator new(sizeof(T)*size));
                                          //       ^^^^ not defined in scope
                                                    (did you mean actualSize)

Stop doing this

using namespace std;

Doing this is a header file will pollute the namespace for all other applications that include your header file. This will piss other people off to no end (it can also break other people’s code).

Doing it in the source file (for anything larger than a 10 line program is dangerous). The potential for name conflicts are high and just because there is a conflict does not mean there will be an error (as the compiler has leeway to do auto conversion).

See Why is “using namespace std” in C++ considered bad practice?

Default constructor

You don’t need a default and a version that takes an integer.

        ArrayList();
        ArrayList(int size);

This can be achieved by a single constructor that has a defaulted size parameter.

        ArrayList(int size = 100);

Move Semantics

You should mark your move constructor/assignment as none throwing (unless they can actually throw)

        ArrayList(ArrayList&& other)                 noexcept;
        ArrayList<T>& operator= (ArrayList&& other)  noexcept;
                                              //     ^^^^^^^^

Doing so allows for better compiler optimizations. The standard library is designed in a way that certain optimizations are possible if the move operations are non throwing. As this allows the strong exception guarantee on their containers when objects are moved (thus allowing move over copy).

Swap as a member

I write swap as a member function. So I can mark it as noexcept. This then allows you to call it from your noexcept move constructor/assignment. Your friend version of swap can then call the member function.

        friend void swap(ArrayList& A, ArrayList& B)
        {
            using std::swap;
            swap(A.actualSize, B.actualSize);
            swap(A.allocatedSize, B.allocatedSize);
            swap(A.arr, B.arr);
        }

I would have done:

        void swap(ArrayList& rhs) noexcept
        {
            using std::swap;
            swap(actualSize,    rhs.actualSize);
            swap(allocatedSize, rhs.allocatedSize);
            swap(arr,           rhs.arr);
        } 
        friend void swap(ArrayList& lhs, ArrayList& rhs)
        {
            lhs.swap(rhs);
        }

Throwing

    if(size < 0)
        throw;

This is valid syntactically. But semantically it is only allowed when there is a propagating exception that has been caught (at which point it re-throws the current exception).

You need to throw an explicit exception object here.

    if(size < 0)
    {
        throw std::runtime_error("Size out of range");
    }

Prefer to use initializer lists

template <typename T>
ArrayList<T>::ArrayList()
{
    arr = static_cast<T*>(::operator new(sizeof(T)*100));
    actualSize = 0;
    allocatedSize = 100;
}

In this case it makes no difference. BUT it can so it is a good habit to get into. Prefer to use initializer lists to prevent objects being initialized twice during construction.

template <typename T>
ArrayList<T>::ArrayList(int size = 100)
    : ar(allocMemory(size))
    , actualSize(0)
    , allocatedSize(size);
{}

Copying can throw.

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
{
    arr = static_cast<T*>(::operator new(sizeof(T)*size));
    allocatedSize = other.allocatedSize;

    // If you set `actual Size` here.
    // Then call `add()` will this not increase the actual
    // size even more? (you also probably ment actualSize = other.actualSize;)
    actualSize = actualSize;


    // If any of these copies throws.
    // Then you leak all previous copies and
    // and the array `arr`. 
    for(size_t i = 0; i<other.actualSize; i++)
        add(other.arr[i]);

    // Note the destructor of the object is only called if
    // if the constructor completes.
}

You need to add some more checking here to make this safe:

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
    : ArrayList(other.allocatedSize)
{
    try
    {
        for(size_t i = 0; i<other.actualSize; ++i)
        {
            add(other.arr[i]);
        }
    }
    catch(...)
    {
        for(size_t i = actualSize; i > 0; --i)
        {
            arr[i-1].~T();
        }
        ::operator delete(arr);
        throw;
    }
}

Move Constructor

You don’t initialize the members in the constructor. Since POD members don’t be default get zero initialized (as an automatic object) they will have random values in them.

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other)
{
    // So you are swapping the random values of this
    // object into other.
    swap(*this, other);
}

You should do this:

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other) noexcept
    : arr(nullptr)
    , actualSize(0)
    , allocatedSize(0);
{
    swap(*this, other);
}

Move Assignment

Needs a return.

template <typename T>
ArrayList& ArrayList<T>::operator =(ArrayList<T>&& other) noexcept
{                                                      // ^^^^^^^^
    swap(*this, other);
    return *this;       // Add this line.
}

Destructor

When you create objects in an array. When the array is destroyed the objects are destructed in reverse order of creation. You should probably mimic that in your destructor.

template <typename T>
ArrayList<T>::~ArrayList()
{
    for(size_t i = 0; i<actualSize; i++)
    {
        arr[i].~T();    // I would use arr[actualSize - i - 1].~T();
    }::operator delete(arr);
//  ^^^^  You probably want a new line
}

Resize size:

The value of 2 sounds good. But 1.5 is better.

http://lokiastari.com/blog/2016/03/25/resizemaths/

    // This looks exactly like a copy constructor.
    // So why not create a private copy constructor that
    // allows an increased pre-allocated size.
    ArrayList tmp(allocatedSize);

    for(size_t i=0; i<actualSize; i++)
        addInternal(arr[i]);

Something like this:

private:
template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other, int allocatedSize)
    : ArrayList(allocatedSize)
{
    try
    {
        for(size_t i = 0; i<other.actualSize; ++i)
        {
            add(other.arr[i]);
        }
    }
    catch(...)
    {
        for(size_t i = actualSize; i > 0; --i)
        {
            arr[i-1].~T();
        }
        ::operator delete(arr);
        throw;
    }
}
public:
// public copy constructor uses the private version
// just passing a couple of parameters forward.
template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
    : ArrayList(other, other.allocatedSize)
{}

template <typename T>
void ArrayList<T>::resize()
{
    // resize() uses the private copy constructor
    // but passes an increased size through.
    ArrayList tmp(*this, std::max(allocatedSize * 1.5, 2));
    swap(*this, tmp);
}

Remove is incorrect.

template <typename T>
void ArrayList<T>::remove(int index)
{
    if(index<0 || index>actualSize - 1)
        throw; // need an exception object

    for(size_t i=0; i<actualSize; i++)
    {
        if(index==i)
        {
            // Once the object is destroyed you can not use it.
            // You can not copy into or out of this object as
            // it no longer exists.
            arr[i].~T();

            // You are moving the elements in the wrong direction.
            // And you just copied from a destroyed object.
            arr[i+1] = arr[i];
        }
        else if(index > i)
            arr[i+1] = arr[i];
    }
}

What you want to do is move the object all down a position. Then destroy the one that is at the end of the array.

template <typename T>
void ArrayList<T>::remove(int index)
{
    if(index<0 || index >= actualSize)
    {
        throw std::runtime_error("Invalid Range");
    }

    for(i = index + 1; i < actualSize; ++i)
    {
        arr[i-1] = std::move(arr[i]);
    }

    // Once you have moved all the items down one place
    // Then destroy the last item.
    --actualSize;
    arr[actualSize].~T();
}

Here’s the original code with comments inserted:

Change this constructor to use size_t:

        ArrayList(int size);

Should be:

        ArrayList(size_t size);

Change parameter of remove to be a size_t.

        void remove(int index);

Should be:

        void remove(size_t index);

Eliminate redundant using

        friend void swap(ArrayList& A, ArrayList& B)
        {
            using std::swap;
            // --snip--
        }

Include named constant for 100:

    private:
        // --snip--
        const size_t defaultSize = 100;
};

Avoid repetitive code, implement ArrayList<T>::ArrayList() in terms of
ArrayList<T>::ArrayList(size_t).

template <typename T>
ArrayList<T>::ArrayList()
    : ArrayList<T>::ArrayList(ArrayList<T>::defaultSize)
{
}

Avoid ::operator new(0) and allocatedSize == 0

template <typename T>
ArrayList<T>::ArrayList(int size)
{
    if(size < 0)
        throw;

    // --snip--
}

Should be:

template <typename T>
ArrayList<T>::ArrayList(size_t size)
{
    if(size < 1)
        throw;

    // --snip--
}

Syntax error: size is undefined. You mean to use other.actualSize when
setting actualSize, but really, you need to use 0 since add/addInternal
will increment actualSize. You can safely use addInternal since
allocatedSize is set appropriately large.

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
{
    arr = static_cast<T*>(::operator new(sizeof(T)*size));
    allocatedSize = other.allocatedSize;
    actualSize = actualSize;

    for(size_t i = 0; i<other.actualSize; i++)
        add(other.arr[i]);
}

Should be:

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
{
    arr = static_cast<T*>(::operator new(sizeof(T)*other.allocatedSize));
    // --snip--
    actualSize = 0;
    // --snip--
        addInternal(other.arr[i]);
}

Really, I’d delegate to ArrayList(size_t)

template <typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
    : ArrayList<T>::ArrayList(other.allocatedSize)
{
    for(size_t i = 0; i<other.actualSize; i++)
        addInternal(other.arr[i]);
}

Syntax error: method should return a value. other will be uninitialized at
the exit to the method and destructor won’t work.

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other)
{
    swap(*this, other);
}

Could be:

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other)
    : ArrayList<T>::ArrayList(1)
{
    swap(*this, other);
    return *this;
}

But this is more efficient:

template <typename T>
ArrayList<T>::ArrayList(ArrayList&& other)
{
    actualSize = other.actualSize;
    allocatedSize = other.allocatedSize;
    arr = other.arr;

    // set other.arr to a value that doesn't incur the
    // cost of a new, but can be deleted without heap
    // corruption.
    other.arr = nullptr;

    // avoid calling destuctor on elements of the array
    // in destructor call on other.
    other.actualSize = 0;

    return *this;
}

Add a line break after for loop.

template <typename T>
ArrayList<T>::~ArrayList()
{
    for(size_t i = 0; i<actualSize; i++)
    {
        arr[i].~T();
    }::operator delete(arr);
}

Should be:

template <typename T>
ArrayList<T>::~ArrayList()
{
    for(size_t i = 0; i<actualSize; i++)
        arr[i].~T();

    ::operator delete(arr);
}

Add return *this;:

template <typename T>
ArrayList& ArrayList<T>::operator =(ArrayList<T>&& other)
{
    swap(*this, other);
    return *this;
}

If you hit an exception in the for loop, this is corrupt since you mutate
allocatedSize.

template <typename T>
void ArrayList<T>::resize()
{
    allocatedSize *= 2;
    ArrayList tmp(allocatedSize);
    // --snip--
}

Should be:

template <typename T>
void ArrayList<T>::resize()
{
    ArrayList tmp(allocatedSize * 2);
    // --snip--
}

move is redundant; item is already a T&& so the cast done by move is a
no-op.

template <typename T>
void ArrayList<T>::add(T&& item)
{
    // --snip--
    addInternalMove(move(item));
}

Should be:

template <typename T>
void ArrayList<T>::add(T&& item)
{
    // --snip--
    addInternalMove(item);
}

If T does not define T::T(T&& other), addInternalMove won’t work and the
compiler will not be able to implicitly fall back to the version of
addInternal with copy semantics. Consider renaming addInternalMove to
just addInternal.

This code has a bunch of flaws. actualSize is not decremented. It’s not
exception safe. You call the detructor on arr[i], but then assign it. You’re
moving things “up” rather than “down”. It’s inefficient to loop from 0 to
index doing a no-op. actualSize-1 has interger underflow if actualSize is 0.

I’d rewrite:

template <typename T>
void ArrayList<T>::remove(int index)
{
    if(index<0 || index>actualSize - 1)
        throw;

    for(size_t i=0; i<actualSize; i++)
    {
        if(index==i)
        {
            arr[i].~T();
            arr[i+1] = arr[i];
        }
        else if(index > i)
            arr[i+1] = arr[i];
    }
}

As:

template <typename T>
void ArrayList<T>::remove(size_t index)
{
    // Allow array to shrink. It's possible this is not desired.
    size_t newSize = allocatedSize / 2;

    if (newSize < actualSize - 1)
        newSize *= 2;

    ArrayList<T> tmp(newSize);

    if(index + 1>actualSize)
        throw;

    for(size_t i=0; i<index; i++)
        tmp.addInternal(arr[i]);

    for(size_t i=index + 1; i<actualSize; i++)
        tmp.addInternal(arr[i]);

    swap(*this, tmp);
}

Let’s go!

Please don’t. Especially not in a header file.

using namespace std;

This pollutes the current namespace with all std symbols. If new symbols are introduced, they might clash with existing ones, silently switch the methods being called, … it’s better to be explicit, really.

This resize method is incorrect:

template <typename T>
void ArrayList<T>::resize()
{
    allocatedSize *= 2;
    ArrayList tmp(allocatedSize);

    for(size_t i=0; i<actualSize; i++)
        addInternal(arr[i]);

    swap(*this, tmp);
}

You intend to create a copy with twice the capacity, but instead modify the this and leave tmp empty.

It should be:

template <typename T>
void ArrayList<T>::resize()
{
    ArrayList tmp(this->allocatedSize * 2);

    for(size_t i = 0; i < this->actualSize; ++i) {
        tmp.addInternal(this->arr[i]);
    }

    swap(*this, tmp);
}

It would also be more resilient to consider the edge case of allocatedSize starting at 0.

It would also make sense to either have a parameter (specifying by how much to resize), or change its name to grow (resize could be either way, but this is only ever growing).

The two overloads of add are unnecessary. You can provide a single one, taking the parameter by value instead:

template <typename T>
void add(T e) {
    if (this->actualSize >= this->allocatedSize) { this->resize(); }

    new (this->arr + this->actualSize) T(std::move(e));
    this->actualSize += 1;
}

Here, the caller will automatically invoke the copy constructor or move constructor of T as appropriate, and you then inside move the item (if possible) or copy it (if necessary).

It is slightly less efficient if the item is not movable, but this is an edge case not worth suffering for.

It is also a good occasion for getting rid of the unnecessary addInternal method: just use add when you need to, the additional check is not worth worrying about.

Your remove method does not provide the Strong Exception Guarantee, if the assignment of T throws you are in trouble.

It’s also slightly weird that it does not mirror add (which does not let one specify the index).

I would simplify it:

template <typename T>
T ArrayList<T>::remove()
{
    if (this->empty()) { throw std::runtime_error("Cannot remove from empty"); }

    this->actualSize -= 1;
    this->arr[this->actualSize].~T();
}

If you wish to add or remove elements at a specific index, it is easy enough to add dedicated methods.

However, adding an element at a specified index whilst still offering the Strong Exception Guarantee is inefficient without further guarantees: it requires making a full copy each time in the worst case. You can special case adding/removing from the last position, but still…

… it is much easier to place as a requirement to the Strong Exception Guarantee that the swap method of T offer the No Exception Guarantee. It is generally an easy guarantee to provide, so this should not cause your users much trouble.

This is the assumption I will take here.

template <typename T>
void ArrayList<T>::addAt(size_t index, T e) {
    if (index > this->actualSize) { throw std::out_of_range(); }

    // Potentially throwing operations first
    if (this->actualSize >= this->allocatedSize) { this->resize(); }

    new (this->arr + this->actualSize) T(std::move(e));

    // No-Throw only now
    this->actualSize += 1;

    for (size_t i = this->actualSize; i > index; --i) {
        using std::swap;
        swap(this->arr[i - 1], this->arr[i]);
    }
}

We place e at the end of the array, then have it “bubble down” (as in the bubble sort algorithm) using swaps until it’s in place and we’ve shifted all the elements after it one step to the right.

The same can be done, but bubbling the element to be removed up, with removeAt:

template <typename T>
void ArrayList<T>::removeAt(size_t index) {
    if (index >= this->actualSize) { throw std::out_of_range(); }

    // No-throw operations first
    for (size_t i = index; i < this->actualSize - 1; ++i) {
        using std::swap;
        swap(this->arr[i], this->arr[i+1]);
    }

    this->actualSize -= 1;

    // Potential throwing operations now
    this->arr[this->actualSize].~T();
}

Note: in C++17, where swap throws can actually be tested with the is_nothrow_swappable trait, which can be used to SFINAE those methods or with a static_assert. This is an exercise left to the reader ^^.

It is interesting to discuss what happens in the case T throws an exception when adding or removing an element.

In the case of add/addAt, this may occur either:

  • during the resize: in this case, resize offers the Strong Exception Guarantee, so nothing has changed
  • when constructing T at the end of the array: in this case, the end of the array contained garbage before, which may have changed, but it is still invisible to the user

In the case of remove/removeAt, this may occur only in the destructor of T. In this case, the element to be destroyed is no longer visible (the size is reduced before), and in the garbage zone. Interestingly, this means that even if remove or removeAt throw, they have already succeeded.

This is an edge case of the Strong Exception Guarantee, the “transaction” is committed but an error is still signaled. You could conceivably swallow the exception here, however I would let it bubble up because the user decided to throw so they must have a good reason for it.

Leave a Reply

Your email address will not be published. Required fields are marked *