C++ Lab #4

C++ Lab 4 - Pointers, References, Dynamic Arrays, Linked Lists

Download the example programs from this page or copy them from the course home page to your directory for this lab as follows (assuming you are currently in your lab directory):

    cp ~cpsc/public_html/Spring2011/CPSC270A/lab4/*.cc .
    cp ~cpsc/public_html/Spring2011/CPSC270A/lab4/*.h .

References and Pointers

Recall that in Java when you declare a variable to be some object type then the variable is actually a reference to the object, that is, it contains the address of the object rather than the object itself. So for example, if you have a Node class, then the declaration

    Node myNode;

would declare myNode to be a reference (currently null) to a Node object. The actual object would be created using the new operator. In C++, the above declaration would create the actual Node (no new would be needed).

To declare a reference (pointer) to an object we use *. The following declaration declares myNodePtr as a pointer to a Node:

     Node * myNodePtr;

The actual node would be constructed using the new operator as follows:

     myNodePtr = new Node;

You can also use * and new on primitive data types such as int. The following allocates space in memory for an int and assigns intPtr to point to it.

   int * intPtr = new int;

To access the actual value of the integer you need to use the operator * to dereference the pointer - *intPtr is the value of the integer in the location pointed to by intPtr.

The & operator gives the address of a variable. Some examples using * and &:

    myNodePtr = &myNode;       //myNodePtr (declared above) now points tomyNode  

    int * numPtr = new int;    //numPtr is the address of (pointer to) an int
    int num = 5;
    cout << &num << " an address!";  //prints the address of num

    *numPtr = 13;   // *numPtr is the contents of the location pointed
                    // to by numPtr - * is "dereferencing" numPtr

The program PointerFun.cc illustrates some of the properties of the & ("address of") operator and the * operator (when used to declare and when used to dereference a pointer variable). Study it then compile and run it.

Dynamic Arrays

To create arrays dynamically at runtime you need to use a pointer and new to allocate the space needed. The following declares the variable a to be a pointer and allocates space in memory for n ints.

      int * a = new int[n];

The program DynamicArray.cc illustrates this. Try it.

Problems with memory when using dynamic allocation: In C++ space allocated remains allocated to your process unless you explicitly free it. There is no automatic garbage collection as there is in Java. The delete command is used to place the memory allocated to a pointer back on free store.

     delete numPtr;   // returns the space for the int pointed to by numPtr

     delete [] a;     // frees the space for the array pointed to by a

The program ArrayMemory.cc illustrates the problem with allocating lots of space without freeing it. Follow the instructions below to run the program, examining memory as it runs. The program pauses for input so you can see how much memory is being used.

Compile and run the program. Input a large number for the number of arrays. Don't type in anything at the pause right now.
In a new terminal window, type the command ps aux. This shows info about all processes currently running. The fifth and sixth fields give memory usage. If you just used the default a.out as the name of the executable, that will be the process you want to look for. Otherwise look for whatever name you used for the executable. You can type the following shell command to just see your process (and this command!):
```
       ps aux | grep yourExecutable
```
After looking at memory usage, type in something to make the program stop execution.
Do the above several times. If you type in a large enough number for the number of arrays you will get a runtime error that basically indicates the system can't allocate the space.
After experimenting several times, go into the code and uncomment the delete statement. Compile and run again, checking memory. You should notice quite a difference.

Working with Linked Lists

The linked list example we examined in class used two classes - a SimNode class in which each node had two data fields (one for time and one for type) and a pointer to the next SimNode, an OrderedList class which was a linked list of SimNodes kept in ascending order according to the time field, and a test program. Separately compile the SimNode class (snode.cc), the OrderList class (olist.cc), and the test program (testList.cc) to get object files. (Or create a Makefile to do this!) Now link the files with the following command to get an executable named runlist as follows:

    g++ testList.o snode.o olist.o -o runlist

Run the program, comparing the behavior to the code.

Exercises: Open testList.cc and do the following:

To see the errors when you confuse using the dot operator with -> do the following:
- Change list.display() to list->display() then make runlist. See what error message was generated.
- Correct the earlier error and now change node->display() to node.display() then make runlist and see what error message is generated.
**** In the last loop that removes the nodes in the list one at a time, change the 5 to a 6. Recompile and run. What happens? Why did it happen? What would this error have been called in Java? Write your answers somewhere to turn in (it can be in your email).
**** Add the following to the OrderedList class:
- A data member length (type int) that keeps track of the length of the list. Initialize and update the variable where needed.
- A member function that returns the length.
- A member function isEmpty that returns true if the list is empty and returns false otherwise. (The return type should be bool.)
**** Add appropriate statements in testList.cc to test the new member functions.
**** Add to the OrderedList class a member function remove that goes through the list and removes all nodes of a given type. The type should be passed as an integer parameter. Be sure to free the memory (delete) for nodes that are deleted HOWEVER it is often wisest to get the code right first then add in your delete. Write your code to work directly with the pointers and list elements. Be sure to think carefully about special cases such as deleting from the front of the list. Add code to testList to test the remove function (or write your own test function).

Due Thursday, March 3: Submit the following

Tar or zip your directory that contains the files for this lab and send the tar file as an attachment in an email. Please delete all .o files before tarring. Also submit written answers to the questions in the lab handout.