Section 11: Static Polymorphism Lab¶
In this discussion, we will implement, test, and evaluate a generic list data structure that uses static polymorphism and then compare it to an object-oriented list that uses dynamic polymorphism and an object-oriented list that is monomorphic.
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-sec11 sec11 % cd sec11 % tree |
The repository includes the following files:
CMakeLists.txt
: CMake configuration script to generate Makefilesrc/ece2400-stdlib.h
: Header file for course standard librarysrc/ece2400-stdlib.cc
: Source code for course standard librarysrc/types-dpoly.h
: Header fileIObject
typessrc/types-spoly.cc
: Source code forIObject
typessrc/SListInt.h
: Header file for monomorphic listsrc/SListInt.cc
: Source code for monomorphic listsrc/SListIObj.h
: Header file for dynamic polymorphic listsrc/SListIObj.cc
: Source code for dynamic polymorphic listsrc/SList.h
: Header file for static polymorphic listsrc/SList.inl
: Inline source code for static polymorphic listsrc/slist-int-adhoc.cc
: Ad-hoc test program for monorphic listsrc/slist-dpoly-adhoc.cc
: Ad-hoc test program for dynamic polymorphic listsrc/slist-spoly-adhoc.cc
: Ad-hoc test program for static polymorphic listtest/types-spoly-directed.cc
: Directed test cases forIObject
typestest/slist-int-directed-test.cc
: Directed test cases for monomorphic listtest/slist-dpoly-directed-test.cc
: Directed test cases for dynamic polymorphic listtest/slist-spoly-directed-test.cc
: Directed test cases for static polymorphic listeval/slist-int-eval.cc
: Evaluation program for monomorphic listeval/slist-dpoly-eval.cc
: Evaluation program for dynamic polymorphic listeval/slist-spoly-eval.cc
: Evaluation program for static polymorphic listscripts/slist-*.sh
: Bash shell scripts for running evaluationscripts/slist-*.py
: Python scripts for plotting
Take a look at the SList.h
header file to understand all of the
public member functions we will be implementing in this lab.
SList()
: default constructor~SList()
: destructorSList( const SList<T>& lst )
: copy constructorvoid swap( SList<T>& lst )
: swap this list with given listSList<T>& operator=( const SList<T>& lst )
: assignment operatorvoid push_front( const T& v )
: push item on front of listint size() cont
: return number of items in the listconst T& at( int idx ) const
: return copy of item at given index (for reading)T& at( int idx )
: return reference to item at given index (for writing)void reverse_v1()
: reverse all items in list using algorithm v1void reverse_v2()
: reverse all items in list using algorithm v2void print() const
: print the list
2. Implementing a Generic Swap¶
Before starting work on a static polymorphic list, we will implement a generic swap function with the following function prototype:
1 2 | template < typename T > void swap( T& a, T& b ); |
Implement this function in the src/swap.inl
file. When you are finished
build and run the directed tests like this:
1 2 3 4 5 6 | % cd ${HOME}/ece2400/sec11 % mkdir build % cd build % cmake .. % make swap-directed-test % ./swap-directed-test |
3. Implementing the Constructor, Destructor, Push Front¶
Now let's take a look at these functions in src/SList.inl
:
SList()
: default constructor~SList()
: destructorvoid push_front( const T& 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. You can also look at the implementation for a monomorphic list from
the previous discussion section in src/SListInt.cc
. When you are
finished use adhoc testing to quickly see if your data structure is
basically working:
1 2 3 | % cd ${HOME}/sec11/src % g++ -Wall -o slist-spoly-adhoc slist-spoly-adhoc.cc % ./slist-spoly-adhoc |
4. 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 list before we can write real directed test cases. Let's take a look at these functions:
int size() cont
: return number of items in the listconst T& at( int idx ) const
: return copy of item at given index (for reading)T& at( int idx )
: return reference to item at given index (for writing)
We have already implemented these member functions for you, but you
should still take a close look. 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. You can also look at the implementation of at
for
a monomorphic list from the previous discussion section in
src/SListInt.cc
.
When you are finished, take a look at the first two directed test cases
in slist-spoly-directed-test.c
. Build and run the test cases like this:
1 2 3 4 | % cd ${HOME}/ece2400/sec11/build % make slist-spoly-directed-test % ./slist-spoly-directed-test 1 % ./slist-spoly-directed-test 2 |
5. 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. You should be able implement this swap in
constant time. You need to use ::swap
to call the generic swap function
developed earlier in this discussion section, to ensure the compiler
knows to call the swap
free function and not the swap
member
function.
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 7 | template < typename T > SList<T>& SList<T>::operator=( const SList<T>& lst ) { SList<T> 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}/sec11/build % make slist-spoly-directed-test % ./slist-spoly-directed-test 3 % ./slist-spoly-directed-test 4 % ./slist-spoly-directed-test 5 % ./slist-spoly-directed-test 6 |
6. Implementing Reverse v1¶
Take a look at the SList.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 | def reverse( x, n ): for i in 0 to n/2: swap( x[i], x[(n-1)-i] ) |
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. You should use the swap
free function you developed
earlier in the discussion esction. Note that you need to use ::swap
to
specify global scope (::
) to ensure the compiler knows to call the
swap
free function and not the swap
member function.
When you are finished use the corresponding directed test cases to verify your implementation is working:
1 2 3 4 5 | % cd ${HOME}/ece2400/sec11/build % make slist-spoly-directed-test % ./slist-spoly-directed-test 7 % ./slist-spoly-directed-test 8 % ./slist-spoly-directed-test 9 |
Using the generic swap
function can reduce the number of times we need
to traverse the linked list, so to have a fair comparison we need to go
back and modify the implementation of reverse_v1
for the monomorphic
list and the dynamic polymorphic list to also use the generic swap
function exactly as you have done for the static polymorphic linked
list. Do that now and rerun the tests for the previous data structures.
1 2 3 4 5 | % cd ${HOME}/ece2400/sec11/build % make slist-int-directed-test % ./slist-int-directed-test % make slist-dpoly-directed-test % ./slist-dpoly-directed-test |
7. 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-spoly-reverse-v1-eval.c
. You can build and run this evaluation
programs along with the evaluation programs from the previous discussion
section using the provided bash script.
1 2 3 4 5 6 7 8 9 10 | % cd ${HOME}/ece2400/sec11 % mkdir build-eval % cd build-eval % cmake -DCMAKE_BUILD_TYPE=eval .. % make slist-int-reverse-v1-eval % make slist-dpoly-reverse-v1-eval % make slist-spoly-reverse-v1-eval % source ../scripts/slist-int-reverse-v1-eval.sh % source ../scripts/slist-dpoly-reverse-v1-eval.sh % source ../scripts/slist-spoly-reverse-v1-eval.sh |
As in the previous discussion section, you can easily plot the result data with a 0th, 1st, and 2nd order polynomial fit using the script:
1 2 3 4 5 | % cd ${HOME}/ece2400/sec11/build-eval % python ../scripts/slist-plot.py ./slist-int-reverse-v1-eval.txt % python ../scripts/slist-plot.py ./slist-dpoly-reverse-v1-eval.txt % python ../scripts/slist-plot.py ./slist-spoly-reverse-v1-eval.txt % python ../scripts/slist-plot-all.py |
Then you can download the PDF file using VS Code and then open the PDF files 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? Do these quantitative results match your qualitative expectations given what you know about the performance of monomorphic, dynamic polymorphic, and static polymorphic data structures?
8. Implementing Reverse v2¶
Let's experiment with an alternative reverse algorithm. This reverse v2 algorithm should use the following steps:
- Create temporary singly linked list
- Push front all values from this list onto temporary list
- Swap this list with the temporary list
You can also look at the implementation of reverse_v2
for a monomorphic
list from the previous discussion section in src/SListInt.cc
. When you
are finished use the corresponding directed test cases to verify your
implementation is working:
1 2 3 4 5 | % cd ${HOME}/ece2400/sec11/build % make slist-spoly-directed-test % ./slist-spoly-directed-test 10 % ./slist-spoly-directed-test 11 % ./slist-spoly-directed-test 12 |
Your implementation should now pass all tests:
1 2 | % cd ${HOME}/ece2400/sec11/build % make check |
9. 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. We also modified the CMakeLists.txt
file to provide a new
target that will: (1) build all of the evaluation programs; (2) run all
of the experiments; and (3) generate all the plots. This demonstrates the
power of using automation through Bash scripts, Python scripts, and CMake
to enable much more productive workflows.
1 2 | % cd ${HOME}/ece2400/sec11/build-eval % make eval-run-plot |
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 generic programming with static polymorphism 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
(SList<String>
) data structure or implement a list of lists of integers
(SList<SList<int>>
) data structure. Alternatively, try to implement the
SListIObj
using an internal SList<IObject*>
list. The internal list
can manage the nodes, and the SListIObj
data structure just needs to
clone objects before pushing back the correponding pointer and delete all
objects in the destructor.