CS 112 Lab 3: Vec -- A First Dynamic Data Structure

Objectives:

In this exercise, you will:
  1. Build a class that uses dynamic allocation/deallocation.
  2. Use pointer variables to access items in a dynamically allocated array.

Introduction

In last week's exercise, we explored addresses, pointer variables, and their use with dynamic arrays. This week, we want to use pointers to build our first dynamic data structure. To get started, download and import tester.cpp, VecTester.h, VecTester.cpp, Vec.h, and Vec.cpp into your project.

The Vec Class. The Vec class is a simpler version of the vector<T> class template available in the C++ standard template library. It will provide the basic functionality, without some of the more advanced "bells and whistles" of the STL version.

The class in Vec.h is a mere shell at this point. Filling in this shell is our task this week.

Getting Started

Open each file and take a moment to browse through them, to get a sense what each one contains. Note that VecTester.cpp contains test-methods for a variety of Vec operations. Its runTests() method invokes all of these tests, but both their calls and their definitions are "commented out" at this point. Build and run the project, and verify that the "All tests passed!" message appears.

Our approach today will be to use the following steps to build each operation:

  1. This exercise will provide you with a description of what the operation should do, and a stub for the method that provides that operation;
  2. You will uncomment the call to the test-method for that operation in runTests();
  3. You will complete the method by adding statements to the stub; and
  4. You will compile and run the project.

If all is well, you can then proceed to the next operation; otherwise you will need to debug your operation to figure out why it is failing the test, recompile, and rerun the test, until it is passed.

Instance Variables

If you look in Vec.h, you'll see that we are (for now) using a typedef to define the identifier Item as a synonym for the type double.

You'll also see that the private: section of class Vec is currently empty. As a minimalist dynamic array, our Vec will need to "remember" two things:

  1. How many Items it is currently storing; and
  2. The Items it is currently storing.
To let a Vec "remember" the first of these, add an instance variable named mySize of type unsigned:
  private:
     unsigned mySize;
  };
To let a Vec "remember" the second of these, add an instance variable named myArray capable of storing the address of an Item:
  private:
     unsigned mySize;
     Item *   myArray;
  };
With these two variables, a Vec object can "remember" (i) how many items it is storing, and (ii) the address of a dynamically allocated array in which its items are stored.

The Default Constructor

The role of the default constructor is to provide the instance variables with default values. In a data structure, these are usually values that are appropriate for an "empty" structure. Complete the default constructor for the class, so that it sets mySize to zero, and sets myArray to NULL. Then in VecTester::runTests(), "uncomment" the line that tests the default constructor and the method definition, and compile the project.

You should get an error message in the test method for the default constructor, indicating that myArray and mySize are private. To resolve this, we can use the C++ friend mechanism, in which one class grants another class permission to access its private attributes. In this case, we can have Vec grant VecTester (and only VecTester) permission to access mySize and myArray:

   ...
   private:
      unsigned mySize;
      Item * myArray;
      friend class VecTester;
   };
With this change, our test method should be able to access a Vec's private instance variables.

Recompile and run the test. When your definition passes the test, continue; otherwise fix and retest your constructor.

Note that a test class has legitimate reasons to access the private attributes of the class it is testing -- it needs to verify that those attributes have the right values. The C++ friend mechanism makes this possible. However, the friend mechanism should not be used so as to avoid having to define accessor and/or mutator methods; to do so is to misuse the friend mechanism.

The Explicit-Value Constructor

The explicit-value constructor's role is to initialize an object using values provided by the user. In a data structure, the user often wants to specify a non-zero starting size for the structure. (e.g., Vec v(5); should construct v as a vector capable of storing 5 items.) To store the value the user specifies, our constructor will need a parameter, so we might start by writing this stub for the constructor:

   Vec::Vec(unsigned size) {
   }

Add a prototype for this constructor to the Vec class. Then in VecTester::runTests(), "uncomment" the method that tests this constructor, and its definition. Save/compile/run your project; then add the statements to your constructor so that it passes all tests. Don't look at this hint unless you get stuck. Continue when your class passes all tests.

The Copy Constructor

The compiler invokes a special copy constructor anytime it needs a copy of an object, for example:

The C++ compiler supplies a default copy constructor, but it merely does a bit-by-bit copy of the instance variables of the object being copied. This bit-copy is inadequate for classes with pointer instance variables, because it just copies the address within such variables, rather than making a distinct copy of the dynamically allocated memory to which that address points. Because of this, every class that contains a pointer instance variable should define its own copy constructor that makes a distinct copy of the object, including its dynamically allocated memory.

The stub for a Vec copy constructor looks like this:

   Vec::Vec(const Vec& original) {
   }

(If we were to mistakenly make the copy constructor's parameter a call-by-value parameter instead of a call-by-const-reference parameter, an infinite recursion will occur when the copy constructor is invoked. The reason is that passing a Vec to a call-by-value parameter will invoke the copy-constructor, which will take the thing to be copied as a parameter, which will invoke the copy constructor, which will taks the thing to be copied as a parameter, which will invoke the copy constructor, which... To avoid this, the parameter of a copy constructor should always be a const-reference parameter, as shown above.)

Add a prototype to the Vec class, and in VecTester::runTests(), "uncomment" the call to and definition of testCopyConstructor(). Then add statements to your stub to construct a Vec that is a distinct copy of original, and check to see if they pass the test. Only look at this hint if you get stuck. Continue when your constructor passes all tests.

The Destructor

The C++ compiler invokes an object's destructor when the object ceases to exist. The role of the destructor is thus to perform any "clean up" actions that are needed to return the system to the same state it was in before the object existed. In a data structure that uses dynamic memory allocation, the main task is usually to return dynamically allocated memory to the system using the delete operation.

A destructor cannot have any parameters, and its name is the name of the class preceded by the tilde character (~), so we can begin with the stub:

   Vec::~Vec() {
   }
If necessary, add a prototype for this method to the class. Then "uncomment" the testDestructor(); statement in VecTester::runTests(), and the definition of this method. Then add the statements to the destructor to reclaim the dynamic array whose address is in myArray, set myArray to NULL, and set mySize to zero. Compile and see if your statements pass the test. Only look at this hint if you get stuck. Continue when your destructor passes all tests.

The Assignment Operator

The assignment operator's role is similar to that of the copy constructor, but with some extra considerations:

  1. Where the copy constructor is building a copy "from scratch," the assignment operator appears in expressions of the form:
       v2 = v1;
    This makes v2 a copy of v1, overwriting any previous values v2 held. In particular, if v2 already has a dynamically allocated array, then the operator=() method must take care to delete that array, or else it will leak memory.
  2. Where the copy constructor returns nothing, the assignment operator should return the object to the left of the = sign (e.g., v2 in the example above). This is so that assignment chaining works properly (e.g., v3 = v2 = v1;).
  3. When defining the assignment operation, you have to check for a special case called self-assignment (e.g., v1 = v1;). Although not especially useful, this is a legal statement, and executing it should not destroy the contents of the Vec.
To accomplish all of this, we might start with this stub:
   Vec& Vec::operator=(const Vec& original) {
      return *this;
   }

Note that the return-type of this method is Vec&. If we were to instead use Vec, the function return mechanism would make a copy (via the copy constructor) of what we return. To "turn off" this copy-mechanism, C++ lets us use a reference return type. By using it here, we return the actual object, rather than a copy of it.

Note also that to make our method return the Vec object on the left-hand-size of the = sign, we have our method return *this for its return value. Every C++ method has a "hidden" pointer parameter named this, in which that object's address is stored. (C++'s hidden parameter this is similar to the explicit parameter self that all Python methods must have.) The expression *this dereferences this pointer, thus accessing the object at that address. (If you imagine that you are the Vec whose operator=() method is being invoked [also known as the receiver of the = message], then *this is just a cryptic C++ way of identifying you).

Place a prototype for this method in the Vec class, and in VecTester::runTests(), "uncomment" the call to testAssignment() and its definition. Then add statements to the method stub so that it passes the test. Only look at this hint if you get stuck. Continue when your method passes all of the tests.

Getting a Vec's Size

Now we come to some easier operations. Our first one is an accessor-method to retrieve the size of a Vec (e.g., v.getSize()). We might start by defining this stub:

   unsigned Vec::getSize() const {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), "uncomment" the call to and definition of testGetSize(). Then complete the stub so that it passes the test. Only use this hint if you get stuck. When your method passes all tests, continue.

Setting the Value of an Item

Our next operation is to set the value of a particular item in a Vec (e.g., v.setItem(i, val);). Since the method needs both the index of the item to change, and the new value for the item, we might start with this stub:

   void Vec::setItem(unsigned index, const Item& it) {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), "uncomment" the call to and definition of testSetItem(). Note that testSetItem() calls exit(), which is declared in <cstdlib>, so you may need to #include that file.

Try to build and run the test to see what errors you get; then complete the stub so that it passes the test. Use this hint if you get stuck. When your method passes all tests, compare your method against the hint, make any last-minute changes, retest, and when all tests are passed, continue.

Getting the Value of an Item

This operation is the complementary operation to setItem(), in that it lets us retrieve the value of an item at a given index (e.g., Item it = v.getItem(i);). Since this method (i) needs the index of the value it is to retrieve, and (ii) does not change its receiver's instance variables, we might start by defining this stub:

   Item Vec::getItem(unsigned index) const {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), "uncomment" the call to and definition of testGetItem(). Then complete the stub so that it passes the test. Only use this hint if you get stuck. When your method passes all tests, compare your method against the hint, make any last-minute changes, retest, and when all tests are passed, continue.

Setting a Vec's Size

Our next operation is to set a Vec's size via a method (e.g., v.setSize(8);. The role of this method is to allow us to change the size of an existing Vec to some new size. Since the user must specify this new size, we need a parameter to store it. We might start by defining this stub:

   void Vec::setSize(unsigned newSize) {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), "uncomment" the call to and definition of testSetSize(). Then complete the stub so that it passes the test. Think carefully! This one is deceptively tricky to get right! Use this hint if you get stuck. When your method passes all tests, continue.

Equality

The purpose of the equality operation is to let us compare two objects (e.g., if (v1 == v2) { ... }), returning true if they are equal, and returning false if they are not. We can start by defining this stub:

   bool Vec::operator==(const Vec& v2) {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), "uncomment" the call to and definition of testEquality(). Then add statements to the stub so that it passes the test. Use this hint if you get stuck. Continue when your method passes all tests.

ostream Output

It is useful to be able to write a vector to an ostream, as this allows us to display it on the screen (or write it to a file via an ofstream). Since our method needs to "know" the ostream to which it is to write, since it modifies the ostream, and since it should not modify the Vec instance variables, we might begin with this stub:

   void Vec::writeTo(ostream& out) const {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), uncomment the call to and definition of testWriteToStream(). Then add statements to this stub so that it passes the test. Use this hint, but only if you get stuck. Continue when your method passes all the tests.

istream Input

It is also useful to be to read a vector from an istream, as this lets us enter a vector's values interactively, from a keyboard (or read them from a file via an ifstream). Since our method needs to "know" the istream from which it is to read, since it modifies that istream, and since it will modify its instance variables, we might begin with this stub:

   void Vec::readFrom(istream& in) {
   }
Place a prototype for this method in the Vec class, and in VecTester::runTests(), uncomment the call to and definition of testReadFromStream(). Then add statements to this stub so that it passes the test. Use this hint, but only if you get stuck. Continue when your method passes all the tests.

Congratulations! You have just built a class that offers the basic functionality one would expect from a vector!

Turn In

Copy your project to a new /home/cs/112/current/yourUserName/lab3 folder.

If time permits, you may begin working on this week's project.


CS > 112 > Labs > 03


This page maintained by Joel Adams.