In the first decade after C++ was released, there were two frequent statements made about the new programming language, especially in the C community:
- C allows you to shoot your foot off, but C++ allows you to shoot the whole leg off.
- C++ is “just an object-oriented language”.
If you have heard of either of these, it’s time to put those ideas away. Looking at C++ in 2019, it’s clearly a rich language that provides many features for writing safe, efficient code, using concepts such as generic programming. The expressive power of modern C++ comes mainly from the use of templates and their uses in generic programming, and not so much from object-oriented concepts (although it does support object-oriented programming with class inheritance and virtual functions). This article introduces some of the basic ideas with templates.
Over their years of programming, most C programmers will have accumulated sets of routines for linked lists, arrays, stacks etc. in their coding libraries; for example, stack routines for pushing, popping, and searching for items on a stack. In C++, you may implement a stack for holding integer data with code that looks something like this:
class int_stack {
public :
bool push(int item);
int pop(void);
…
};
A class is basically a struct declaration that includes member functions and other advanced features. The declaration above declares a class name “int_stack”, which contains two member functions, push and pop, and other items not listed here (shown as “…”).
In C, a set of such routines would only work for one data type (e.g., int). If you want stack routines for double data types, you will have to duplicate the routines, and change the names and internals to work with double data types, though most of the code would be identical. If you are clever, perhaps you might use void pointers and such to make the same set of routines work with different data types, but it would be a hack.
C++ templates solve that. Here’s an example of a template stack class:
template <typename T> stack {
public:
bool push (T item);
T pop(void);
…
};
Note 1: This is just a simple example. The actual implementation of the stack in the standard C++ library STL (Standard Template Library) is far more capable and complex than this example.
Note 2: You may also write the template declaration with the word “class” instead of “typename”, e.g. “template <class T> stack { …”.
A template declaration such as above does not create anything per se, not even a class type. However, if you use it to declare variables, e.g.:
stack<int> int_stack; stack<double> double_stack;
“stack<int>” is known as a parameterized type. With these two declarations, the compiler creates two declarations, as if you have written something akin to:
class int_stack {
public :
bool push(int item);
int pop(void);
…
};
class d_stack {
public :
bool push(double item);
double pop(void);
…
};
Templates eliminate having to write similar-looking code, reducing the effort to write and maintain a project. Note that there is only one template name (“stack”) which is decorated with the actual data type to declare a class type (e.g. “stack<int>”). While this simple example might be done using clever C preprocessing macros, the full power of templates cannot be replaced by C macros.
If you use the template declaration multiple times, e.g:
stack<int> stack1; stack<int> stack2;
The compiler is smart enough to know that the two implicitly created stack classes are the same.
Baby Steps to Generic Programming
Now imagine you want to add an “==” equality operator to the stack class (in C++, you can overload the meaning of any C operator symbol within a class, but you cannot create new operator symbols that do not exist in the base language):
To do this, first, let’s look at an example of non-template operator definition:
class int_stack {
public :
bool push(int item);
int pop(void);
bool operator==(int_stack &);
…
};
The definition of the operator, if written outside of the class declaration, starts with:
bool int_stack::operator==(int_stack &stack2) ...
This declaration is for an == operator of a non-template class “int_stack”. In this example, there are two symbols not used in C:
- :: is the scope resolution operator. The left-hand side is either a class name or a namespace name (we will not be discussing namespace in this short article). In this example, you can think of the words “int_stack::operator==” to mean “this is the == operator for the int_stack class”.
- &, as used in a variable declaration, after the type name and before the variable name as shown above, signifies that this is a reference to the variable. A reference has the same semantic as a pointer-to a variable (i.e. in a function call, a reference parameter allows efficient passing of the argument, and allows the function to modify the argument), except that you don’t use the * indirect operator to access the variable, as the variable name itself suffices. For a struct/class variable, this means that you use the dot “.” field member operator, instead of the “->” field member operator.
For a template, operator declaration is just a little bit more complicated:
template <typename T> stack {
public:
bool push (T item);
T pop(void);
bool operator==(stack<T> &stack2);
…
};
The definition of the operator, if written outside of the class declaration, starts with:
template <typename T> bool stack<T>::operator==(stack<T> &stack2) …
A parameterized type “stack<T>” is used in place of a concrete type “int_stack” and the whole declaration is prefixed with “template <typename T>” to tell the compiler that this is a template declaration. Once you understand the basics of operator declaration, this is just a bit more syntactic sugar on top.
The code for the template == operator could be something as follows:
template <typename T> bool stack<T>::operator==(stack<T> &stack2)
{
if (size() != stack2.size())
return false;
for (unsigned i = 0; i < size(); i++)
if (elems[i] != stack2[i])
return false;
return true;
}
There is a lot to unpack here. Looking at the code, you may make the following observations:
- The stack class supports a size() function, presumably to indicate the number of elements in the class.
- The stack class includes a member named “elems”, presumably containing the actual elements of the stack.
- The stack class supports an array indexing [i] operator, where [i] presumably returns the i’th sequential member of the stack.
- You may apply the array indexing [] to either a class object (e.g. stack2[i]) or to the elements member (e.g. elems[i]), presumably with the same semantic effect.
- Each element is compared against the element in the other stack in the same position. This implies that the element data type must support the == and != operators as well.
Taking together, the function returns true if and only if the stacks have the same number of elements and each element compares equality.
Power of Templates
So why is this important? The template mechanism allows the above code to work for any stack<T> objects, as long as they implement the features as noted above. Not only does this reduce the amount of code you have to write, it allows you to use templates (and their routines) written by other people, saving you much design, implementation, and debugging time.
I have already mentioned the STL (Standard Template Library), which provides templates for stacks, vectors, lists, hash tables, etc. There are more advanced libraries such as Boost, which provides support for linear algebra, pseudorandom number generation, multithreading, image processing, regular expressions, and unit testing. Boost contains over eighty individual libraries. Without templates, STL and Boost would not have been possible.
Any C++ programmers who haven’t done so yet should get familiar with STL and Boost libraries.
More C++: Iterators and New FOR loop
Instead of using array indexing syntax, most classes that support sequential access also provides iterators, and the above function can be rewritten (only the main loop is given here) as:
for (auto & iter = elems.begin(); iter != elems.end(); iter++)
{
if (iter != stack2[i])
return false;
++i;
}
So what are the differences?
- The C keyword “auto” has now been repurposed to request the compiler to deduce the data type of the variable automatically. The compiler does this by looking at the type of the right hand side of the assignment expression. There is no need to write out the data type for “iter”. This is a powerful feature, especially if the data type declaration is complex (the data type for an iterator is indeed fairly complex).
- There are iterator functions and idioms that allow you to sequentially access the elements of the stack just like using the array indexing [i].
As they say, there’s more! Instead of using explicit iterator, you can also write:
for (auto & elem::elems)
{
if (elem != stack2[i])
return false;
}
This new “for” loop syntax, which assumes an iterator over a class object, combined with “auto” type deduction, allow you to iterate through the elements simply and elegantly.
A Stupid Implementation
If you just want to get your feet wet and become familiar with C++ syntax, you can implement a dumb version of the stack template based on the STL’s vector class. Of course the STL has a far more capable version of stack template with a lot more features, but nothing beats learning a language by actually typing in some code:
#include <vector>
template <typename T>
class stack {
public:
bool push(T item) { elems.push_back(item); return true; }
T pop(void) { T val = elems.back(); elems.pop_back(); return val; }
bool operator==(stack<T> &stack2);
unsigned size(void) { return elems.size(); }
T& operator[](int i);
private:
vector<T> elems;
};
The “==” operator is as described above, and I will leave it as an exercise to the readers to implement the [] array indexing operator.
You can write a simple test like this:
int main()
{
stack<int> istack, istack2;
istack.push(42);
istack.push(1000);
int x = istack.pop();
cout << "Hello world! x is " << x << endl;
if (istack == istack2)
cout << "stacks equal" << endl;
cout << istack.pop() << endl;
if (istack == istack2)
cout << "stacks equal" << endl;
}
When run, you should see:
Hello world! x is 1000 42 stacks equal
Summary
C++ is a mature programming language, capable to efficiently write high performance programs. The core of its usability and efficiency is the extensive use of templates. This article only briefly scratches what is possible.