Templates and Generic Programming for STL

[thiruvasagamani]

Standard Template Library

Introduction

The Standard Template Library (STL) is a collection of generic fundamental computing data structures (or containers of data), mechanisms to access and manipulate data contained in these containers and algorithms that can be applied to these data structures.

These data structures and algorithms are implemented in C++ and provide reusable components that form the building blocks of most structurally complex and computationally intensive object oriented software systems.

This article provides an introduction to STL and illustrates its application in object oriented software using several programming examples. These examples have been compiled and tested on Linux. This article proceeds with a brief review of templates and generic programming in C++. A detailed introduction to the characteristics of STL is followed by a discussion on various STL containers will be covered in a series of articles.. Access and manipulation of contained data using iterators is then described followed by a discussion on STL algorithms. The article is concluded with an explanation of using STL in multi-threaded software.
Templates and Generic Programming
Templates allow a single implementation of a function or a class to handle many different data types. This is also referred to as parametric polymorphism and is different from method overloading where a different implementation of a method exists for a different data type. Consider the following example of an overloaded function getAverage.

Code Select Expand

#include <iostream>
using namespace std;
float getAverage(int* intArray, int size)
{
float sum = 0.0;
int i;
cout << "Processing " << size << " element int array" << endl;
for (i=0;i<size;i++)
{
sum += intArray[i];
}
return sum/size;
}
float getAverage(float* realArray, int size)
{
float sum = 0.0;
int i;
cout << "Processing " << size << " element float array" << endl;
for (i=0;i<size;i++)
{
sum += realArray[i];
}
return sum/size;
}
int main(void)
{
int intArray[] = {5, 4, 7, 9, 2};
float floatArray[] = {3.25, 5.45, -10.25, 4.55, 6.90, -0.65, 3.21};
float avgFromIntArray;
float avgFromRealArray;
avgFromIntArray = getAverage(intArray, sizeof(intArray)/sizeof(int));
avgFromRealArray = getAverage(floatArray, sizeof(floatArray)/sizeof(float));
cout << "Average from intArray " << avgFromIntArray << endl;
cout << "Average from floatArray " << avgFromRealArray << endl;
return(0);
}

One implementation of this method accepts an array of integers and the size of the array as arguments while the other accepts an array of floating point numbers and the size of the array. Both these functions provide the average value of the data contained in the arrays. In method (or function) overloading, the compiler can determine the implementation that needs to be executed from the type of the arguments passed to the function call. The output of this program is listed below,

Processing 5 element int array
Processing 7 element float array
Average from intArray 5.4
Average from floatArray 1.78

Parametric polymorphism, on the contrary, attempts to handle all data types, including user defined types using a single implementation. This single implementation of functions or classes can be considered a generic implementation. Therefore parametric polymorphism is also referred to as genericity. Thus, in parametric polymorphism, the same generic implementation is executed for each data type. The following program performs the same operation as the one in the previous example but it uses a generic function instead of overloaded functions.

Code Select Expand


#include <iostream>
using namespace std;
template <class T>
float getAverage(T* array, int size)
{
float sum = 0.0;
int i;
cout << "Processing " << size << " element array" << endl;
for (i=0;i<size;i++)
{
sum += array[i];
}
return sum/size;
}
int main(void)
{
int intArray[] = {5, 4, 7, 9, 2};
float floatArray[] = {3.25, 5.45, -10.25, 4.55, 6.90, -0.65, 3.21};
float avgFromIntArray;
float avgFromRealArray;
avgFromIntArray = getAverage(intArray, sizeof(intArray)/sizeof(int));
avgFromRealArray = getAverage(floatArray, sizeof(floatArray)/sizeof(float));
cout << "Average from intArray " << avgFromIntArray << endl;
cout << "Average from floatArray " << avgFromRealArray << endl;
return(0);
}

The output of this program is shown below,

Processing 5 element array
Processing 7 element array
Average from intArray 5.4
Average from floatArray 1.78