(Suggested book reading: Programming Abstractions in C++, 11.2 - 11.3, 12.1, 12.3, 14.1, 14.4)
We have used several collections so far from the Stanford libraries, such as
Map, and so on.
Today we will explore how collection classes are implemented.
We will implement a simple version of
Vector, which we will call
Inside a Vector is an array storing the elements you have added. Typically the array is larger than the data added so far, so that it has some extra slots in which to put new elements later. We call this an unfilled array.
If you execute the following code:
Vector<int> v; v.add(42); v.add(-5); v.add(17);
The state inside the vector looks like this:
To write our own implementation of a vector, we must learn about how to use arrays in C++. C++ arrays are a bit cumbersome to use and require unusual syntax, which is why we have avoided them thus far. Here is a brief example of constructing an array and storing data in some of its elements:
int* a = new int; a = 42; a = 17; a = 90210;
The unusual use of a
* character above is related to how C++ manages memory using a feature called pointers.
We will learn about this feature in detail this week.
You are expected to follow the Stanford Honor Code.
If this is an assignment that allows pairs, the same rules apply to each team. For example, do not look at assignment solutions that do not belong to your team, and do not give your solution to anyone outside of your team.
Remember that we run similarity-detection software over all solutions, including this quarter and past quarters, as well as any solutions we find on the web.
If you need help solving an assignment, we are happy to help you. You can go to the LaIR, or the course message forum, or email your section leader, or visit the instructor / head TA during office hours. You can do it!