Lecture Overview

Just yesterday Bjarne Stroutrup and Herb Stutter (the two main creators of C++) released a C++ Core Guidelines document on how to write modern C++ code. It is something to bookmark for if you ever have to actually write C++ code.

Templates

The implementation of linked lists I show today uses a new feature of C++, templates. We covered the idea behind templates in MCS 275; they are what mypy called Generics. As a reminder, types are sets and generics/templates are functions on types. Templates allow us to write functions on types, so we will write a type-function LinkedList. This type-function takes as input any type T (which we think of as a set of values) and outputs a type which is the set consisting of all singly-linked lists with values drawn from the set/type T. For example, we identify the type int with the set of all 32/64-bit integers. (32 or 64 depends on your processor and compiler settings.) Passing the type int to the type-function LinkedList will produce a type/set which consists of all linked lists where values are 32/64-bit integers.

C++ supports this by allowing us to write these type-functions which C++ calls templates. A simple example is:

template <typename T>
struct Foo {
    private:
        T val;

    public:
        T getVal() {
            return val;
        }

        void setVal(T x) {
            val = x;
        }
};

The syntax is

template <comma separated list of parameters> struct Name { Definition };

where each template parameter is typename VarName. It is common to use T as the VarName parameter but not required. The semantics is that C++ creates a type-function called Name. The type-function takes as input the type parameters, and the output of the type-function is a struct which looks exactly as if anywhere the parameters appear inside the Definition, they are replaced by whatever was passed to the type-function.

Calling a type function (also called instantiating the template) uses the following syntax:

Name<comma separated list of types>

So for example both Foo<int> and also something like Foo<Foo<int>> are both types/structs. It is important to realize that these are different types and it is essentially like you had defined two different structs. As an example,

int main() {
    Foo<int> x;
    x.setVal(12);

    Foo<float> y;
    y.setVal(53.12);

    cout << x.getVal() << y.getVal() << endl;
}

Linked Lists in C++

linkedlist.cpp is an implementation of a singly linked list in C++. The code contains comments describing how the pointers are stored.

Exercises

Problem 1 Add the following destructor to the ListEntry structure. It can go right after the definition of the two properties.

~ListEntry() {
    cout << "Deleting " << val << endl;
}

Next, compile and execute it. Describe why each call to the destructor occurs, in particular how the destructor is called when popping and once the main function returns.

Problem 2 Last time, you wrote psuedocode for methods second_last, get, set, add, remove, and reverse. Implement them in the LinkedList struct. When you want to loop through the entries in the list, you can use a for loop just like is used inside the existing print method.