p1 on the autograder.)
This project will develop your skills on structuring object-oriented software via class hierarchies.
This project has you build an array implementation that gains
efficiency by doubling the array size (rather than just extending by
1) when the array needs to be extended. This will give you
implementation constant amortized insertion
time. I.e., if you perform
n insertions, the runtime will be of
O(n), rather than O(n^2).
This project contains a few files, each implementing classes in a class hierarchy you will flesh out:
IArray.h– This is an interface. Although C++ does not technically have an
interfacekeyword (as in Java), the term “interface” refers to a class which has no concrete method implementations (i.e., every method is pure virtual) and contains no data members. You do not need to modify this file, but you should read it to get an idea of how the rest of the project works.
AArray.h– An abstract class (one which contains a mix of unimplemented and concrete methods) that implements a few methods using other methods (some of which are undefined). TODO: Extend
CArray.h– A slow (i.e., not-doubling-size) implementation of resizing arrays that will give O(n^2) time for
ninsertions. TODO: Extend
SArray.h– A faster (doubling-size) implementation of resizing arrays that will give O(n) time for
Your job is to implement these last three classes.
You will need to read about:
- Exceptions and try
- Abstract classes
- Virtual methods