# Simplified implementation of std::vector in C++

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

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

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++)

swap(*this, tmp);
}

template <typename T>
{
if(actualSize >= allocatedSize)
resize();

}

template <typename T>
{
if(actualSize >= allocatedSize)
resize();

}

template <typename T>
{
new (arr+actualSize)T(item);
actualSize++;
}

template <typename T>
{
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];
}
}

• I have rolled back Rev 2 → 1. Please see What to do when someone answers. – 200_success Jul 28 '16 at 9:41
• Please compile, and test, your code before submitting it for review. As provided it does not compile and there are a number of bugs (such as the usage of throw;). – Matthieu M. Jul 28 '16 at 11:51
• @MatthieuM. Unfortunately throw; is legal syntax that does compile. Though testing would have a shown the error as it is not semantically correct usage. – Martin York Jul 28 '16 at 17:09
• @LokiAstari: Indeed, thus the "and" between "does not compile" and "number of bugs". I sometimes wonder if the syntax is worth it, writing throw e; would be sufficient if only this did not copy (or even move) e. – Matthieu M. Jul 28 '16 at 17:33

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).

### 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++)

// 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)
{
}
}
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++)


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

• Quick question about T*arr. Am I allowed to use unique pointers to represent arr in this case rather than raw pointers so that it's easier for me to do garbage collection ? Under what circumstances should I use smart pointers to make pointers as member variables? – Mantracker Jul 30 '16 at 3:39
• @Mantracker: There are basically two times when you should be managing raw pointers. 1) When creating smart pointers. 2) When creating container. BUT if you want the you can use a unique_ptr to simplify your container then that is fine. But it will only not save you much as you still need to build all the copy/move functionality for the other members. – Martin York Jul 30 '16 at 3:52

## 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++)
}


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


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


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>
{
// --snip--
}


Should be:

template <typename T>
{
// --snip--
}


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++)

for(size_t i=index + 1; i<actualSize; i++)

swap(*this, tmp);
}

• You moved ::operator delete(arr); to inside the loop in the constructor. Was that intentional? – Carcigenicate Jul 28 '16 at 11:26
• Note: constructing a list of size 0 should be allowed (and I would argue, would make a much better default size). Instead of forbidding it, it would be better to allow it, and simply use nullptr for arr, as happens in your recommendation of move assignment. – Matthieu M. Jul 28 '16 at 11:47
• @Carcigenicate -- you mean the destructor? I removed the braces so the for loop only has one statement in it (the call to ~T()). @Matthieu M -- that's more of a spec/design issue than coding one. Without context, it's hard to say if the behavior is good or not. I kept the original post's behavior, but I agree that setting nullptr for arr is also a fine choice (and perhaps valuable if you have containers of ArrayList<T>s.) If you went that way, you'd need to make resize handle allocatedSize == 0. – Sean Jul 28 '16 at 12:09
• I disagree with using std::size_t in the constructor. Yes the standard containers use this. BUT the standards committee agree this was a mistake (unfortunately it is set now so they are not going to change it). The problem is that because of automatic conversions it is impossible to catch negative numbers. std::vector x(-1); The -1 is automatically converted to a very large unsigned number which will probably fail to allocate. So you get bad_alloc() rather than a bad_range() exception. – Martin York Jul 28 '16 at 16:53
• Eliminate redundant using: This is wrong. using std::swap; is actually the correct way to do it because of koenig lookup (ADL). If you ever change the types in the class this becomes important as you will only change the types without having to update the code and still get correct koenig lookup. – Martin York Jul 28 '16 at 16:56

Let's go!

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++)

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

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>
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.

• I have a question about changing add(const T& e) to add(T e) as you suggested. If I do pass by value instead for add, wouldn't it be very inefficient for large objects of T? – Mantracker Jul 29 '16 at 5:45
• @Mantracker: Possibly. This is two-fold: (1) when passing T const& you later call the copy constructor, so here it's called twice instead of once which is the same ballpark anyway and (2) we are looking at small template methods, which have a good chance of getting inlined, which in turns mean that the optimizer is likely to elide useless copies. So there's a chance it will be less efficient if (1) the object has no move constructor and (2) the optimizer does not optimize the copy away. For std::vector I would worry about it, but here the class is not at this optimization level. – Matthieu M. Jul 29 '16 at 9:51