Some Extra Info About C++ ========================= Using Templates to Make Classes and Functions More Flexible ----------------------------------------------------------- Consider the following code for implementing a queue:: typedef string ItemType; class Queue { public: // Constructs an empty queue. Queue() : front(nullptr), back(nullptr) { } ~Queue() { while (!is_empty()) dequeue(); } // Pre: // Post: returns true iff queue has no items bool is_empty() { return front == nullptr; } // Pre: // Post: adds x to the end of this queue void enqueue(const ItemType& x) { if (is_empty()) { Node* tmp = new Node(x, nullptr); front = tmp; back = tmp; } else { Node* tmp = new Node(x, nullptr); back->next = tmp; back = tmp; } } // Pre: queue is not empty // Post: returns and removes the item at the front of the queue ItemType dequeue() { check_pre(!is_empty()); if (front == back) { // queue has exactly 1 item ItemType result = front->val; delete front; front = nullptr; back = nullptr; return result; } else { // queue has 2 or more items Node* tmp = front; ItemType result = front->val; front = front->next; delete tmp; return result; } } private: struct Node { ItemType val; Node* next; // Constructor for convenience Node(const ItemType& v, Node* n) : val(v), next(n) { } }; // struct Node Node* front; // head of the queue Node* back; // tail of the queue }; // class Queue The problem with this kind of ``Queue`` is that it can only hold items of type ``ItemType``. While you can define what ``ItemType`` is using ``typedef``, you can only define ``ItemType`` to be one data type. If you want two different kinds of queues, e.g. one holding integers and the other holding strings, it's not easy to do. You pretty much need to copy the queue code and change ``ItemType`` in the copy. C++ provides a technique know as **templates** to help deal with this problem. The idea is that the data type of the value being stored in the queue will be given like this:: Queue qs; // qs contains strings Queue qd; // qd contains doubles The way to do this is to add the following to the top of the ``Queue`` class:: template // T is the data type of the values stored Queue class Queue { // ... }; // class Queue Here, ``T`` is a data type, such as ``string`` or ``double``, and it is not known until a queue is declared in code, e.g.:: Queue qs; When the compiler sees this line of code, you can imagine, roughly speaking, that ``T`` is replaced by ``string`` throughout the ``Queue`` class. The compiler automatically does the substitution for us. What we need to do is replace every occurrence of ``ItemType`` with ``T``:: template class Queue { public: // Constructs an empty queue. Queue() : front(nullptr), back(nullptr) { } ~Queue() { while (!is_empty()) dequeue(); } // Pre: // Post: returns true iff queue has no items bool is_empty() { return front == nullptr; } // Pre: // Post: adds x to the end of this queue void enqueue(const T& x) { if (is_empty()) { Node* tmp = new Node(x, nullptr); front = tmp; back = tmp; } else { Node* tmp = new Node(x, nullptr); back->next = tmp; back = tmp; } } // Pre: queue is not empty // Post: returns and removes the item at the front of the queue T dequeue() { check_pre(!is_empty()); if (front == back) { // queue has exactly 1 item T result = front->val; delete front; front = nullptr; back = nullptr; return result; } else { // queue has 2 or more items Node* tmp = front; T result = front->val; front = front->next; delete tmp; return result; } } private: struct Node { T val; Node* next; // Constructor for convenience Node(const T& v, Node* n) : val(v), next(n) { } }; // struct Node Node* front; // head of the queue Node* back; // tail of the queue }; // class Queue The ``Queue`` class is now much more useful: we can easily create queues that hold any type of data. .. warning:: The example we've shown here is a simple one. You should know that templates quickly get *much* more complex, and have many details that we've not mentioned here. .. warning:: Due to how they are compiled, errors in code with templates sometimes suffer from extremely long and complex error messages that can be very hard to decipher. Inheritance and Polymorphism ---------------------------- What if you want to store two different kinds of objects in the *same* queue? Suppose we are writing code for a GUI that needs to store that various events --- mouse clicks, window changes, etc. --- that can occur. The events are stored in the queue as soon as they are generated so that they can be processed later by the correct handling code. The tricky part is that GUI events come in a variety of types that can stored vastly different information. There's no one class that we could make that could possibly store all the information that occurs in all events. But if we create multiple classes, then we uses a ``Queue`` to store them, because a ``Queue`` requires that all of its items be of the same type. One way to solve this problem in C++ is to use a base class and inheritance. This is how we could set things up:: // Event is an abstract base class (ABC) for events that // might occur in, say, a GUI framework. // // You cannot create an object of type Event. The purpose // of Event is to act as a common base class that other // classes can inherit from. class Event { public: // virtual means that classes that inherit from Event are // allowed to over-ride print(), i.e. provide their own // special version of the function. // // The "= 0" part on the end indicates that this is a // "pure virtual function" with no default implementation, // and so classes that inherit from Event *must* implement // their own print function. virtual void print() const = 0; void println() { print(); cout << endl; } // Line below declares a "virtual destructor", which is necessary // if you want code like that at the end of event_test3 not to // leak memory. virtual ~Event() { } }; // class Event class Mouse_click : public Event { public: // Constructor Mouse_click(int xi, int yi) : x(xi), y(yi) { } void print() const { cout << ""; } private: int x; int y; }; // class Mouse_click class Window_focused : public Event { public: // Constructor Window_focused(const string& wn) : window_name(wn), flags(new bool[3]) { flags[0] = false; flags[1] = false; flags[2] = false; } ~Window_focused() { delete[] flags; } void print() const { cout << ""; } private: string window_name; // in practice, more likely that this would // be a pointer to a "window object" bool* flags; }; // class Window_focused Here we've created a number of classes in the form of an inheritance hierarchy. ``Event`` it as the top of the hierarchy: it is an *abstract base class* that all other event classes must inherit from. Notice that ``Event`` has a *pure virtual* function named ``print`` that has no implementation, and instead ends with ``= 0``. This tells C++ that ``print`` *must* be implemented in any class that inherits from ``Event``. Thus, because ``print`` has no implementation in ``Event``, there is no way to actually create an ``Event`` object. The ``Mouse_click`` and ``Window_focussed`` classes each define the data they need to store. Objects of these types would be created by some other part of the GUI system when necessary. Notice that both provide an implementation of ``print`` that is specific to the data it contains. Also, both classes inherit the ``println`` function from ``Event``. Here's one way to use these classes:: Mouse_click* mcp = new Mouse_click(380, 66); Window_focused* wfp = new Window_focused("Chrome"); mcp->println(); wfp->println(); delete mcp; // give back the memory delete wfp; Here's another, way with an important difference:: Event* mcp = new Mouse_click(380, 66); // notice that mcp and wfp are Event* wfp = new Window_focused("Chrome"); // both of type Event* mcp->println(); wfp->println(); delete mcp; // give back the memory delete wfp; .. warning:: Unlike the previous example, this code has a *very* subtle memory leak we will diagnose when we discuss the ``valgrind`` memory leak checker. For now, though, we will ignore the leak. The results printed on screen are the same as the previous code, but the types of ``mcp`` and ``wfp`` are now the same: they are both of type ``Event*``. This turns out to be important, because now we can store both of them in a data structure such as a ``Queue`` that only holds data of the same type:: Queue q; q.enqueue(mcp); q.enqueue(wfp); while (!q.is_empty()) { Event* e = q.dequeue(); e->println(); } A limitation of this code is that the pointer ``e`` can only call functions that are declared in ``Event``, because those are the only functions it knows for sure are in all objects that ``e`` can point to. If we tried to execute ``e->set_all_flags()`` in the while-loop we'd get a compiler error because there is no ``set_all_flags`` function in ``Event``. This is clearly a good thing, because there is no ``set_all_flags`` function in a ``Mouse_click``, and we don't know if an ``Event*`` variable is point to a ``Mouse_click`` or ``Window_focussed`` object. Through an ``Event`` pointer, we can only ever call functions that we know for sure are in any object from a class that inherits from ``Event`` --- which is the same as saying we can only access functions declared in ``Event``. If you do need to call a function specific to a particular kind of object, then you should ``dynamic_cast`` to change the type of the pointer to be the same as the type of the object. Using valgrind to Check for Memory Leaks ---------------------------------------- ``valgrind`` is a useful tool that can help you locate memory leaks. For example, suppose the name of your executable program is ``queue_test``. Then to run it with ``valgrind`` use this command:: $ valgrind ./queue_test If ``queue_test`` runs with no memory leaks, then you will see a message like this:: All heap blocks were freed -- no leaks are possible Otherwise, you will get a message telling you some memory has, possibly, not been properly de-allocated. There are some options you can then call ``valgrind`` with to help locate these memory leaks, or at least narrow done the culprit code (it can still be tricky to figure out why the leaks are happening, and now best to fix them). ``valgrind`` is easy to use and run, and so you should *always* run it when you write C/C++ programs. You might be surprised how easy it can be to mis-manage memory! For instance, consider this code that we saw above:: Event* mcp = new Mouse_click(380, 66); // notice that mcp and wfp are Event* wfp = new Window_focused("Chrome"); // both of type Event* mcp->println(); wfp->println(); Do you see the error? If you run it without using ``valgrind``, it will appear to work properly. However, ``valgrind`` reports a memory leak:: ==8826== HEAP SUMMARY: ==8826== in use at exit: 22 bytes in 2 blocks ==8826== total heap usage: 5 allocs, 3 frees, 76 bytes allocated ==8826== ==8826== LEAK SUMMARY: ==8826== definitely lost: 22 bytes in 2 blocks ==8826== indirectly lost: 0 bytes in 0 blocks ==8826== possibly lost: 0 bytes in 0 blocks ==8826== still reachable: 0 bytes in 0 blocks ==8826== suppressed: 0 bytes in 0 blocks There is a problem, but where? Running ``valgrind`` with the option ``--leak_check=full`` prints a lot more information, but it's not clear how any of it helps find out what the real problem is. Debugging a problem like this takes persistence, knowledge, and creativity. Good luck!