Lab: Dynamic Container Class

A better array

Hold Me

As we discussed in class, it is very useful to create abstractions that contain data and allow us to access and manipulate it in different ways. In this lab, you are going to create a List class that holds lists of numbers and does useful things with them.

In lab, we'll walk through using SVN to submit your work. This is the URL for the repository (repo) we'll be using today (where username is your utrgv username without the @utrgv.edu part)

https://cssvn.utrgv.edu/svn_etomai/201720_2380/lab01_classes/username

When you're done working for the day, commit your changes! You get participation credit for today by committing the work you got done in lab. Only commit the main.cpp file! We don't need or want all the other stuff, as we can easily create a new project whenever we need it.

Lift Me Up

We already have a perfectly good way to store a list of numbers: an array. But arrays are very low-level, meaning they give you control and power but lots of details to keep straight. We want a higher level abstraction that supports more convenient features like keeping track of it's own length, automatically resizing and functionality like searching.

For any class we make, there is the public interface (the constructors and methods) and the private implementation (the data members and private methods). When using a class, we don't want to care or think about the private implementation, just what it does for us. For your List class, the private internal implementation is going to be an array of integers. That's the only way at the moment that you know how to store a list of numbers.

Below is a starting point for the class definition, and testing code in main.

1. Start by looking over the testing code! See what you're going to do!
2. Then, only copy the first testing line into your project
3. Copy the class starter and work on it until that first testing line works!
4. Then get the next line(s) and repeat

The testing code is important because it completely specifies everything in the public interface. But trying to make it all work at once is foolish. Always keep the code working! Don't have a big pile of stuff that doesn't compile, that's a horrible strategy.

Note on Resizing

How do you resize an array? You can't. That's why your List class is going to be better than using an array. With dynamic memory allocation, you can create a new, bigger array and copy the data over, then discard the old one. This all happens in the private, internal space, so the user doesn't even worry about it.

Reallocating and copying is expensive, so you don't want to resize one step bigger at a time. Instead, increase by the initial capacity again. So in the example below, when we add a 6th item, we resize our List to hold 10. Then 15. Then 20 and so on.

The Testing Code

#include <iostream>
#include <cassert>
using namespace std;

class List
{
private:
  // data members here, starting with a pointer for the internal array

public:
  // public interface here, starting with the constructor that takes an initial capacity


};

int main()
{
  // Part I: Tests for Basic Usage

  List ages( 5 );      // create a list that can hold up to 5 integers

  ages.Add( 17 );
  ages.Add( 43 );
  ages.Add( 71 );

  // this should print "List length: 3"
  cout << "List length: " << ages.Length() << endl;  

  // this should print "List items: [ 17, 43, 71 ]"
  cout << "List items: " << ages.toString() << endl;

  ages.Remove(1);

  // this should print "List length: 2"
  cout << "List length: " << ages.Length() << endl;

  // this should print "List items: [ 17, 71 ]"
  cout << "List items: " << ages.toString() << endl;


  // Part II: Tests for Resizing

  ages.Add( 2 )
  ages.Add( 30 )
  ages.Add( 51 )

  ages.Add( 15 )       // the list needs to resize here!

  // this should print "List length: 6"
  cout << "List length: " << ages.Length() << endl;

  // this should print "List items: [ 17, 71, 2, 30, 51, 15 ]"
  cout << "List items: " << ages.toString() << endl;


  // Part III: Additional Functionality

  // this should print "Max item: 71"
  cout << "Max item: " << ages.Max() << endl;

  // testing the find method (four cases: first, middle, last, not found)
  assert( ages.Find(17) == 0 );
  assert( ages.Find(30) == 3 );
  assert( ages.Find(15) == 5 );
  assert( ages.Find(1000) == -1 );



  return 0;
}