C++ generics provide a powerful way to create an extensible design with the help of templates. The primary motivation of any generic model of programming is that it enables the programmer to develop components that provide easy and seamless transition from the design to the application code. It also better expresses design intention and highly supports the reuse of design structure with minimal recoding. A sense of the generic pattern also can be achieved through other means, such as polymorphism and virtual classes, void objects, and so forth, which simulate a flavor of generics by providing multiple service with a single interface, but they are quite different from templates. When we talk of generics, especially in C++, a template is what we actually mean. This article focuses on templates in particular and generics in general with appropriate code examples.
Templates Overview
A template is a construct to create functions and classes with undefined types. The types later can be associated according to the requirement. As a result, when we need multiple versions of similar functions and classes, only one template definition is needed. For example, a Stack class representing an array of int values is very similar to the Stack with an array of double or a string value. The logic implemented for pop and push methods remains the same. The actual implementation varies only in the type of elements that one wants to represent. Another similar scenario may be the use of a sorting technique where the implementation also remains the same but the type of the element varies. Sometimes, it is an array of int values that we want to sort or sometimes an array of double values or long, and so on.
C++ allows defining templates as functions or classes.
- A function template defines a set of operations using parameters of type defined at the function call.
- A class template defines a class structure using a parameter instead of a concrete type. The generic definition of the class can be used to create a generic structure of Stacks, Queues, Linked List, and the like. During instantiation, the type is supplied and the object is created based on the template definition.
C++ templates have many advantages, primarily for:
- Code reuse
- Uniform solution to a similar problem
- Avoid the complexity of multiple coding, thus reducing the chance of multiple errors
- Easy maintenance, debug etc.
Function Template
Suppose we want to write a code to swap two int elements with the help of a function. We may write the code as follows:
#include <iostream> using std::cout; using std::endl; void swap(int &a, int &b){ int temp; temp=a; a=b; b=temp; } int main(int argc, char **argv) { int a=10, b=20; cout<<"a="<<a<<" b="<<b<<endl; swap(a,b); cout<<"a="<<a<<" b="<<b<<endl; return 0; }
The code works fine, but the problem is that, at a letter point, if we want to swap a double value or a string value, another swap function has to be written which invariably will have the same logic. We can resort to the technique of function overloading to make the idea almost look like a generic. But, this is ridiculous, because in that case we have to write n number of functions to support n number of types. This type of problem can be easily solved by a template function.
The definition of a function template begins with the template keyword and then we write <class T> or <typename T>. Although we state the class keyword, T can be of any type int, double, string, and so forth. Using a letter T is just a convention; you may use any letter or word, such as A, B, C…Z or SpIdErMaN, even _Z24AK. You can use pretty much anything provided they do not begin with a number (such as 99M; this is a compile time error).
Thus, the previous function can be rewritten with a template to support a generic swap, as follows.
#include <iostream> #include <string> using std::cout; using std::endl; using std::string; template<class T> void swap(T &a, T &b){ T temp(a); a=b; b=temp; } int main(int argc, char **argv) { int a=10, b=20; double d1=1.11111, d2=2.222222; string s1="Coca", s2="Cola"; cout<<"Before swap "<<"a="<<a<<" b="<<b<<endl; swap(a,b); cout<<"After swap "<<"a="<<a<<" b="<<b<<endl; cout<<"Before swap "<<"d1="<<d1<<" d2="<<d2<<endl; swap(d1,d2); cout<<"After swap "<<"d1="<<d1<<" d2="<<d2<<endl; cout<<"Before swap "<<"s1="<<s1<<" s2="<<s2<<endl; swap(s1,s2); cout<<"After swap "<<"s1="<<s1<<" s2="<<s2<<endl; return 0; }
Class Template
Class templates are, in essence, similar to function templates and use the same template keyword for the definition. The idea is to create a generic class that plays around for many data types. For example, consider a container class called Stack. A Stack may be of type int, char, double, string, and so on, depending upon the requirements. As a result, this container is an ideal candidate to be implemented as a template class. A simple Stack data structure to illustrate the idea is as follows.
#include <iostream> using namespace std; template <typename E>class MyStack{ private: int SIZE; int tos; E *items; public: MyStack(int=10); ~MyStack(){ delete[] items;} void push(const E&); E pop(); }; template<typename E>MyStack<E>:: MyStack(int s):SIZE(s>0?s:10),tos(-1),items(new E[SIZE]){} template<typename E> void MyStack<E>::push(const E &value){ if (tos == SIZE - 1) cout<<"Stack is full"<<endl; else items[++tos] = value; } template<typename E> E MyStack<E>::pop(){ E item; if (tos == -1) cout<<"Stack is empty"<<endl; else item = items[tos--]; return item; } int main(){ MyStack<string> strStack(4); strStack.push("January"); strStack.push("February"); strStack.push("March"); strStack.push("April"); cout<<strStack.pop()<<endl; cout<<strStack.pop()<<endl; cout<<strStack.pop()<<endl; cout<<strStack.pop()<<endl; cout<<strStack.pop()<<endl; // stack is empty now return 0; }
Standard Template Library (STL)
C++ generics emphasizes the importance of software reuse. The ideal cornerstone of implementing generics is the library of data structures and algorithms. The C++ standard committee realized the programmers’ needs and added STL just for the cause. STL is collection of reusable components, built based on a template, to fulfill everyday programming needs. It contains several template classes, such as the stream classes for input/output, string, and container classes. The algorithm library associated with the STL comprises numerous search and sort algorithms. These algorithms are implemented as global function templates. As a result, they can be invoked for any set of objects as and when required.
Note: It is worth mentioning that the STL, as we see it today, is the result of the research on generic programming by Alexander Stepanov and Meng Lee at Hewlett-Packard. |
As its primary goal, STL is optimized for performance and flexibility. As a result, one should use components from STL as much as possible rather than build everything from scratch.
To provide a glimpse, STL contains classes, such as the following.
Associative Containers
- set: A collection of elements without duplicates
- multiset: A collection of elements, duplicates allowed
- map: A collection of elements with one to one mapping, no duplicates
- multimap: A collection of elements with one to one mapping, duplicates allowed
Container Adapters
- stack: A last-in-first-out (LIFO) data structure
- queue: A first-in-first-out (FIFO) data structure
- priority_queue: A queue, but the element ID is popped based on priority
Sequence Containers
- vector: A linear, extendable array
- deque: A double-ended queue; elements can be inserted and deleted at both ends
- list: A doubly linked list
A Quick Example
#include <iostream> #include <vector> #include <string> using namespace std; int main() { vector<string> planets; cout << "Size=" << planets.size() << endl; cout << "Capacity=" << planets.capacity() << endl; planets.push_back("Mercury"); planets.push_back("Venus"); planets.push_back("Earth"); planets.push_back("Mars"); planets.push_back("Jupiter"); planets.push_back("Saturn"); planets.push_back("Uranus"); planets.push_back("Neptune"); cout << "Size=" << planets.size() << endl; cout << "Capacity=" << planets.capacity() << endl; // using iterator vector<string>::const_reverse_iterator revi; for(revi = planets.rbegin(); revi != planets.rend(); revi++) cout << *revi<<' '; cout << endl; }
Conclusion
Apart from containers, STL also provides many ready-to-use template implementations of common algorithms. These algorithms are optimized for performance. They come in quite handy. But, to understand them, a basic knowledge of templates is a must. The primary motivation of study can be such as inducing a generic flavor in the code, to understand the design implementation and use of the standard library. In real-world programming, STL is the most used library and a thorough understanding of it can leverage one’s efficiency as a C++ programmer.