Skip to content

Section 8: Object-Oriented Programming Lab

In this discussion, we will implement, test, and evaluate an object-oriented list data structure using C++.

1. Logging Into ecelinux with VS Code

Follow the same process as in the last section. Find a free workstation and log into the workstation using your NetID and standard NetID password. Then complete the following steps (described in more detail in the last section):

  • Start VS Code
  • Use View > Command Palette to execute Remote-SSH: Connect Current Window to Host...
  • Enter netid@ecelinux.ece.cornell.edu
  • Use View > Explorer to open folder on ecelinux
  • Use View > Terminal to open terminal on ecelinux

Now clone the GitHub repo we will be using in this section using the following commands:

1
2
3
4
5
6
% source setup-ece2400.sh
% mkdir -p ${HOME}/ece2400
% cd ${HOME}/ece2400
% git clone git@github.com:cornell-ece2400/ece2400-sec08 sec08
% cd sec08
% tree

The repository includes the following files:

  • CMakeLists.txt : CMake configuration script to generate Makefile
  • src/ece2400-stdlib.h : Header file for course standard library
  • src/ece2400-stdlib.cc : Source code for course standard library
  • src/SListInt.h : Header file for list
  • src/SListInt.cc : Source code for list
  • src/slist-int-adhoc.cc : Ad-hoc test program for list
  • test/slist-int-directed-test.cc : Directed test cases for list
  • eval/slist-int-eval.cc : Evaluation program for list
  • scripts/*-eval.sh : Bash shell scripts for running evaluation
  • scripts/*-plot.py : Python scripts for plotting

Take a look at the SListInt.h header file to understand all of the public member functions we will be implementing in this lab.

  • SListInt(): default constructor
  • ~SListInt(): destructor
  • SListInt( const SListInt& lst ): copy constructor
  • void swap( SListInt& lst ): swap this list with given list
  • SListInt& operator=( const SListInt& lst ): assignment operator
  • void push_front( int v ): push item on front of list
  • int size() cont: return number of items in the list
  • int at( int idx ) const: return copy of item at given index (for reading)
  • int& at( int idx ): return reference to item at given index (for writing)
  • void reverse_v1(): reverse all items in list using algorithm v1
  • void reverse_v2(): reverse all items in list using algorithm v2
  • void print() const: print the list

2. Implementing the Constructor, Destructor, Push Front

Let's start by taking a look at these functions:

  • SListInt(): default constructor
  • ~SListInt(): destructor
  • void push_front( int v ): push item on front of list

We have implemented the default constructor for you. Implement push_front based on the code discussed in lecture. We have started the implementation of the destructor for you. Add the code to delete the node. When you are finished taking a look use adhoc testing to quickly see if your data structure is basically working:

1
2
3
% cd ${HOME}/ece2400/sec08/src
% g++ -Wall -o slist-int-adhoc slist-int-adhoc.cc SListInt.cc
% ./slist-int-adhoc

3. Implementing Size and At

Obviously, we want to do more than just ad-hoc testing, but we need some way to check what is in the slist before we can write real directed test cases. Let's next implement these functions:

  • int size() cont: return number of items in the list
  • int at( int idx ) const: return copy of item at given index (for reading)
  • int& at( int idx ): return reference to item at given index (for writing)

We have already implemented the size member functions for you. Notice how we have two versions of at: the const version is automatically used by the compiler when reading an item and the non-const version is automatically used by the compiler when writing an item. The non-const version returns a reference which enables one to directly modify an item that is stored in the list.

When you are finished, take a look at the first two directed test cases in slist-int-directed-test.c. Build and run the test cases like this:

1
2
3
4
5
6
7
% cd ${HOME}/ece2400/sec08
% mkdir build
% cd build
% cmake ..
% make slist-int-directed-test
% ./slist-int-directed-test 1
% ./slist-int-directed-test 2

6. Implementing the Copy Constructor, Swap, and Assignment Operator

Because we need to implement a destructor, the rule of three tells us we also need to implement a copy constructor and assignment operator. We have implemented the copy constructor for you, but spend some time reviewing it. We will be using a copy-and-swap pattern to implement the assignment operator, so we need to start by implementing the swap member function. This member functions swaps the internal state between this list and the given list.

Once you have implemented swap you can now use the copy-and-swap pattern which reuses the functionality already implemented in the copy constructor and destructor to implement the overloaded assignment operator:

1
2
3
4
5
6
SListInt& SListInt::operator=( const SListInt& lst )
{
  SListInt tmp( lst ); // create temporary copy of given list
  swap( tmp );         // swap this list with temporary list
  return *this;        // destructor called for temporary list
}

We first use the copy constructor to make a temporary copy of the given list. We then swap the head pointers between this list and the temporary list. Now this list has a copy of all of the nodes in the given list, and the temporary list has all of the nodes which used to be in this list. When the temporary list goes out of scope, the destructor will handle deleting all of the nodes which used to be in this list. Here is a good article that discusses this pattern:

When you are finished use the corresponding directed test cases to verify your implementation is working:

1
2
3
4
5
6
% cd ${HOME}/sec08/build
% make slist-int-directed-test
% ./slist-int-directed-test 3
% ./slist-int-directed-test 4
% ./slist-int-directed-test 5
% ./slist-int-directed-test 6

5. Implementing Reverse v1

Take a look at the SListInt.cc source file to find the reverse_v1 member function. This function should reverse all of the items in the list. Let's use a simple algorithm inspired by the following pseudocode used for reversing an array:

1
2
3
4
5
def reverse( x, n ):
  for i in 0 to n/2:
    lo = i
    hi = (n-1) - i
    swap( x[lo], x[hi] )

You can use the size member function to get the number of items in the list and you can use the at member function to read and write items in the list by index. When you are finished use the corresponding directed test cases to verify your implementation is working:

1
2
3
4
5
% cd ${HOME}/ece2400/sec08/build
% make slist-int-directed-test
% ./slist-int-directed-test 3
% ./slist-int-directed-test 4
% ./slist-int-directed-test 5

6. Evaluating Reverse v1

We have provided you an evaluation program to quantitatively evaluate the execution time of the linked list data structure and reverse v1 algorithm. Take a look at this evaluation program in slist-int-reverse-v1-eval.c. You can build and run this evaluation program like this:

1
2
3
4
5
6
% cd ${HOME}/ece2400/sec08
% mkdir build-eval
% cd build-eval
% cmake -DCMAKE_BUILD_TYPE=eval ..
% make slist-int-reverse-v1-eval
% ./slist-int-reverse-v1-eval

You will see that the evaluation program takes one command line argument specifying the size of the input array. Let's do an experiment to see how the execution time of the reverse v1 algorithm grows as a function of the input array size.

1
2
% cd ${HOME}/ece2400/sec08/build-eval
% ./slist-int-reverse-v1-eval 200

While we could run each experiment individually, let's automate this by using a Bash for loop to run a command multiple times with different parameters in a single step. We could enter the Bash for loop on the command line, but let's put it in a Bash script instead so we can easily run it. A Bash script is just a file that contains a sequence of Linux commands that you can run together. We have provided you a Bash script that runs several experiments and saves all of the results in a file named slist-int-reverse-v1-eval.txt. You can look at the Bash script in scripts/slist-int-reverse-v1-eval.sh. You can run the commands in the Bash script by using the source command:

1
2
% cd ${HOME}/ece2400/sec08/build-eval
% source ../scripts/slist-int-reverse-v1-eval.sh

Instead of using the standard grep and cut command line tools to extract the average execution time for each experiment, we can just incorporate reading the results into the beginning of a Python plotting script. Take a look at an example Python script in scripts/slist-int-reverse-v1-eval-plot.py. You can easily plot the result data with a 0th, 1st, and 2nd order polynomial fit using the script:

1
2
% cd ${HOME}/ece2400/sec08/build-eval
% python ../scripts/slist-int-reverse-v1-plot.py

Then you can download the PDF file using VS Code and then open the PDF file on your local workstation or laptop. Do these quantitative results match your qualitative expectations given what you know about the asymptotic time complexity of the reverse v1 algorithm?

7. Implementing Reverse v2

Let's experiment with an alternative reverse algorithm. This reverse v2 algorithm should use the following steps:

  1. Create temporary singly linked list
  2. Push front all values from this list onto temporary list
  3. Swap this list with the temporary list

When you are finished use the corresponding directed test cases to verify your implementation is working:

1
2
3
4
5
% cd ${HOME}/ece2400/sec08/build
% make slist-int-directed-test
% ./slist-int-directed-test 10
% ./slist-int-directed-test 11
% ./slist-int-directed-test 12

Your implementation should now pass all tests:

1
2
% cd ${HOME}/ece2400/sec08/build
% make check

8. Evaluating Reverse v2

We have provided you an evaluation program to quantitatively evaluate the execution time of the linked list data structure and reverse v2 algorithm. You can build and run this evaluation program like this:

1
2
3
% cd ${HOME}/ece2400/sec08/build-eval
% make slist-int-reverse-v2-eval
% ./slist-int-reverse-v2-eval 2000

We have provided you a Bash script and two Python plotting scripts similar in spirit to what we worked with in a previous section. Let's run the bash script and create the plots.

1
2
3
4
% cd ${HOME}/ece2400/sec08/build-eval
% source ../scripts/slist-int-reverse-v2-eval.sh
% python ../scripts/slist-int-reverse-v2-plot.py
% python ../scripts/slist-plot-all.py

Then you can download the PDF files for both plots using VS Code and then open the PDF file on your local workstation or laptop. Do these quantitative results match your qualitative expectations given what you know about the asymptotic time complexity of reverse v1 vs v2 algorithms?

10. Extensions to Try On Your Own

The code used in this discussion section serves as an excellent framework for continuing to explore object-oriented programming on your own. Consider copying over the code for a C++ string class presented elsewhere in the course so you can implement a list of strings (SListStr) data structure.