Memory Based Array List Assignment

For this assignment you will be writing the class shown below that implements a list ADT using an array. You need to implement all the memory handling functions. As usual, move operations will only be significant for performance.

template<typename T>

class ArrayList {

public:

// Types

// value_type

// iterator

// const_iterator

// General Methods

ArrayList();

ArrayList(const ArrayList &that);

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

~ArrayList();

void push_back(const T &t); // add to the end.

void pop_back(); // remove last element.

int size() const;

void clear();

void insert(const T &t,int index); // insert this element before the given index.

const T &operator[](int index) const; // get the element at index.

T &operator[](int index); // get the element at index.

void remove(int index); // remove the item at the given index.

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

const_iterator cbegin() const;

const_iterator cend() const;

};

For the nested types, you can declare value_type with a typedef or a using statement. For the others I recommend a nested class with the proper name. If you do that, then the begin method has the following signature when you write it below the class declaration.

typename ArrayList<T>::iterator ArrayList<T>::begin()

Your iterators need to satisfy the requirements for a bi-directional iterator in C++ (http://www.cplusplus.com/reference/iterator/BidirectionalIterator/). This means that the declaration of iterator might contain the following:

iterator(T *l);

iterator();

iterator(const iterator &i);

T &operator*();

bool operator==(const iterator &i) const;

bool operator!=(const iterator &i) const;

iterator &operator=(const iterator &i);

iterator &operator++();

iterator &operator--();

iterator operator++(int);

iterator operator--(int);

If you write the methods below the classes you will need to specify them with both scopes for the outer class and the nested class. Since these should all be rather short you can write them in the class declaration as inlining is probably approriate. Note that the versions of ++ and -- that take an int argument are the postfix version. The ones with no argument are prefix.

Why should you put begin and end methods in your class and have iterators? Try using a ranged for loop with your class. I will in my testing.

For testing, you should put your code in a file called ArrayList.h.

Test Rubric:

Basic tests of all methods (10 points)

Large tests (1000+ items) (5 points)

Tests with multiple types, including non-primitives (5 points)