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<string> qs; // qs contains strings
Queue<double> qd; // qd contains doubles
The way to do this is to add the following to the top of the Queue class:
template<class T> // 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<string> 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 T>
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.
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 << "<Mouse_click:(" << x << ", " << y << ")>";
}
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 << "<Window_focused: \"" << window_name << "\", "
<< flags[0] << flags[1] << flags[2] << ">";
}
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<Event*> 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.
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!