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.
#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.
#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
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
Genericity in C++ is achieved by templates.
|
|
The line template <class T> above the function getAverage specifies that this is a generic function that can access data of all data types, which can be processed by that function. In the generic implementation, this data type is referred to as T, and acts as an alias to the actual type passed at runtime. For example, this function can accept arrays of integer, float, long and short numbers. Even an array of chars can be processed as an array of byte sized numbers. However, this function cannot process an array of a structure of one integer and one float number as addition (+) and division (/) operators are not defined for this structure. The actual type of the data being sent to the function is (optionally) specified in the call between the function name and the arguments with in angular brackets.
The compiler auto-generates a version (or instance) of the template function for a specific data type when it encounters a function call to the template function with that data type in the arguments. The generic type T in the template function is replaced in the instance of the template function by the specific type specified in the function call.
The concept of template can also be applied to classes, resulting in generic classes. The most common application of generic or template classes is as containers for collection of data values or objects. Template classes have also been used successfully as file input output classes that allow storage and retrieval of objects different data types and also as data communication classes that allow communication of objects of different data types.
Following is an example of a generic Calculator class,
template <class T>
class Calculator
{
private:
T lastAnswer;
public:
Calculator(void);
T add(T a, T b);
T subtract(T a, T b);
T multiply(T a, T b);
T divide(T a, T b);
T getLastAnswer(void);
};
template <class T>
Calculator<T>::Calculator(void)
{
lastAnswer = 0;
}
template <class T>
T Calculator<T>::add(T a, T b)
{
lastAnswer = a+b;
return lastAnswer;
}
template <class T>
T Calculator<T>::subtract(T a, T b)
{
lastAnswer = a-b;
return lastAnswer;
}
template <class T>
T Calculator<T>::multiply(T a, T b)
{
lastAnswer = a*b;
return lastAnswer;
}
template <class T>
T Calculator<T>::divide(T a, T b)
{
lastAnswer = a/b;
return lastAnswer;
}
template <class T>
T Calculator<T>::getLastAnswer(void)
{
return lastAnswer;
}
The following program shows the application of this class in processing integers,
#include "calc.cc"
#include <iostream>
using namespace std;
int main(void)
{
int a = 18;
int b = 3;
Calculator<int> calc;
cout << calc.add(a,b) << endl;
cout << calc.subtract(a,b) << endl;
cout << calc.multiply(a,b) << endl;
cout << calc.divide(a,b) << endl;
cout << calc.getLastAnswer() << endl;
return(0);
}
The output of this program is listed below,
21 15 54 6 6
The following program shows the application of this generic Calculator class in processing floating point values,
#include "calc.cc"
#include <iostream>
using namespace std;
int main(void)
{
float a = 18.3;
float b = 3.5;
Calculator<float> calc;
cout << calc.add(a,b) << endl;
cout << calc.subtract(a,b) << endl;
cout << calc.multiply(a,b) << endl;
cout << calc.divide(a,b) << endl;
cout << calc.getLastAnswer() << endl;
return(0);
}
The output of this program is shown below,
21.8 14.8 64.05 5.22857 5.22857
The strength of templates is fully exploited when user defined data types have the required operators overloaded. For instance, the following example shows a ComplexNumber class with the +, -, * and / operators overloaded. The main function declares two ComplexNumber objects and then performs the arithmetic operations on these objects using the generic Calculator class.
#include "calc.cc"
#include <iostream>
#include <math.h>
using namespace std;
class ComplexNumber
{
private:
float real;
float imag;
public:
ComplexNumber(void)
{
real = 0.0;
imag = 0.0;
}
ComplexNumber(float a, float b)
{
real = a;
imag = b;
}
void operator = (float a)
{
real = a;
imag = 0.0;
}
ComplexNumber operator + (const ComplexNumber& num)
{
ComplexNumber reply(real + num.real, imag + num.imag);
return reply;
}
ComplexNumber operator - (const ComplexNumber& num)
{
ComplexNumber reply(real - num.real, imag - num.imag);
return reply;
}
ComplexNumber operator * (const ComplexNumber& num)
{
float tempReal;
float tempImag;
tempReal = (num.real * real) - (num.imag * imag);
tempImag = (real * num.imag) + (imag * num.real);
ComplexNumber reply(tempReal, tempImag);
return reply;
}
ComplexNumber operator / (const ComplexNumber& num)
{
ComplexNumber temp(num.real, -num.imag);
ComplexNumber temp2;
ComplexNumber temp3;
ComplexNumber temp4(real, imag);
temp2 = temp * num;
temp3 = temp4 * temp;
ComplexNumber reply(temp3.real/temp2.real, temp3.imag/temp2.real);
return reply;
}
float getReal(void)
{
return real;
}
float getImag(void)
{
return imag;
}
};
void printComplexNumber(ComplexNumber& num)
{
float real = num.getReal();
float imag = num.getImag();
cout << real;
if (fabs(imag) == imag)
{
cout << "+";
}
cout << imag << "i" << endl;
}
int main(void)
{
ComplexNumber a(2, 3);
ComplexNumber b(5, 2);
ComplexNumber c;
Calculator<ComplexNumber> calc;
c = calc.add(a,b);
printComplexNumber(c);
c = calc.subtract(a,b);
printComplexNumber(c);
c = calc.multiply(a,b);
printComplexNumber(c);
c = calc.divide(a,b);
printComplexNumber(c);
return(0);
}
This example illustrates that if the operators required in the template class are supported by a user defined data type, variables of that type can be processed by objects of the template class without any modification in the template class. The output of this program is shown below,
7+5i -3+1i 4+19i 0.551724+0.37931i