For this assignment you will be writing two implementations of the list interface shown below. One should use a linked list and the other should use a dynamic array. You need to implement all the memory handling functions. As usual, move operations will only be significant for performance.
template<typename T>
class List {
public:
// Types
// value_type
// iterator
// const_iterator
// General Methods
virtual ~List() {}
virtual void push_back(const T &t) = 0; // add to the end.
virtual void pop_back() = 0; // remove last element.
virtual int size() const = 0;
virtual void clear() = 0;
virtual void insert(const T &t,int index) = 0; // insert this element before the given index.
virtual const T &operator[](int index) const = 0; // get the element at index.
virtual T &operator[](int index) = 0; // get the element at index.
virtual void remove(int index) = 0; // remove the item at the given index.
// You must write these in the subclasses.
// virtual iterator begin() = 0;
// virtual const_iterator begin() const = 0;
// virtual iterator end() = 0;
// virtual const_iterator end() const = 0;
// virtual const_iterator cbegin() const = 0;
// virtual const_iterator cend() const = 0;
};
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 look like 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, the class above will be in a file called List.h. You will call your two subtypes ArrayList and LinkedList. You will put them in ArrayList.h and LinkedList.h.