Transcript EE4E Lec5

EE4E. C++ Programming
Lecture 5
Templates and the Standard Template
Library (STL)
Contents
Introduction
 Function templates
 Class templates
 Creating function templates from class
templates
 The Standard Template Library (STL)

Introduction

Templates are a powerful feature of C++

They allow the programmer to specify with a
single code segment an entire range of related
functions or classes


For example we might write a sort() function
template able to sort ints, floats, chars and
programmer defined classes

We might write a linked list class template able
to handle many different data types
The Standard Template Library is a sophisticated
set of class templates enabling us to use
generalized container classes
Function templates

Function templates are useful if we want to
perform identical operations on different types of
data

Examples would include searching and sorting
arrays of different data types

The algorithms used would be the same for all
data types

Only object equality and relational tests would
differ

Function template definitions begin with the
template keyword

A list of formal type parameters follows in angle
(< and >) brackets


template <class T> function_name

template <class A, class B> function_name
The function template is instantiated by specifying
actual types (which can be primitive types or user
defined types) in place of the formal types
Example

A function template printArray() that prints
the contents of an array of any instantiated
type
template class<T> void printArray(const T* array,
const int count)
{
for (int i=0; i<count; i++)
{
cout << array[i] << “ “;
cout << “\n”;
}
}
void main()
{
const int n=5;
int intArray[n]={1,2,3,4,5};
float floatArray[n]={1.0,2.0,3.0,4.0,5.0};
char charArray[n]=“Hiya”;
printArray(intArray,n);
printArray(floatArray,n);
printArray(charArray,n);
}

The compiler in this case instantiates the
following printArray() functions

printArray(const int*, const int)

printArray(const float*, const int)

printArray(const char*, const int)

No runtime overhead is involved

If T is replaced by a programmer defined type
(such as Date), then the complier will look for a
overloaded operator<<() function
void main()
{
const int n=5;
Date d(1,1,1990);
Date* DateArray=new Date[n];
for (int i=0; i<n; i++)
DateArray[i]=d++;
// operator<<(ostream& os, const Date& d) called here
printArray(DateArray,n);
}
Class templates


Class templates enable reusable data types to be
easily created
 Often called generic programming
For example we can create a generic stack (a last
in first out data structure) using class templates
 The generic stack can be instantiated with any
data type
 Stack of integers, stack of doubles, stack of
dates etc
// Stack class template
template <class T> class Stack
{
private:
int size;
// No. of elements in the stack
int top;
// Location of the top element
T* stackPtr; // Pointer to the stack
public:
Stack(int);
~Stack() { delete[] stackPtr; }
int push(const T&); // Push an element
int pop(T&);
// Pop an element
int isEmpty() { return top==-1;}
int isFull() { return top==size-1;}
};
template<class T> Stack<T>::Stack(int a)
{
size=a;
top=-1;
// Initially empty
stackPtr=new T[size]; // Allocate memory
}
template<class T> int Stack<T>::push(T& val)
{
if (!isFull()) { stackPtr[++top]=val;
return 1;
}
return 0;
}
template<class T> int Stack<T>::pop(T& val)
{
if (!isEmpty()) { val=stackPtr[top--];
return 1;
}
return 0;
}
void main()
{
Stack<char> charStack(7);
char[] name=“Michael”;
int j=0;
while(charStack.push(name[j])
j++;
char c;
cout << “My name in reverse is : “;
while(charStack.pop(c))
cout << c;
}

This code assumes that an overloaded
assignment operator function exist for
programmer defined data types

This must be provided if the object used
with the Stack class contains
dynamically allocated memory
Creating function templates from
class templates

We can easily create a function template by
passing a class template as an argument to a
function
 A classic example is a sort() function
template which sorts the contents of a
container template (for example and
array) passed as an argument

We can demonstrate this by first creating a
simple Vector template (like an array)
template <class T> class Vector
{
private:
T* v;
int size;
public:
Vector(int) ;
// Constructor
int getSize( ) { return size; }
T& operator[] (int );
// overloaded []
};

We can then create a sort() function
template
template<class T> void sort(Vector<T>& v)
{
// sort the elements of v into increasing
// order using a bubble sort
int size=v.getSize();
for (int i=0; i<size-1; i++)
for (int j=size; i<j; j--)
if (v[j]<v[j-1])
// swap v[j] & v[i]
{
T t = v[j];
v[j]=v[j-1];
v[j-1] = t;
}
}
void main()
{
Vector<int>& vi(100);
Vector<char*>& vc(100);
Vector<float>& vf(100);
Vector<Circle>& vci(100);
// initialize the vectors
// …..
.
sort(vi);
sort(vc);
sort(vf);
sort(vci);
}

The compiler will try and create the correct sort()
functions by instantiating the templated functions

It will run into 2 problems in this example

Instantiating sort() with a char* (a string)
argument will produce incorrect results


The ‘<‘ operator will not test for alphabetical
ordering of the strings
Instantiating sort() with a Circle object
argument will produce a compilation error

We need an overloaded operator<() function
defined on Circle objects

We can create sort() functions for specific
datatypes that will override the instantiated
function
template<class T> void sort(Vector<char*>& v)
{
// sort the elements of v into increasing
// order using a bubble sort
int size=v.getSize();
for (int i=0; i<size()-1; i++)
for (int j=size()-1; i<j; j--)
if (strcmp(v[j],v[j-1])<0)
{
T t = v[j];
v[j]=v[j-1];
v[j-1] = t;
}
}

We can also create an operator<() function
for Circle objects
int operator < (Circle& c1,Circel& c2)
{
return c1.radius<c2.radius;
}
Other features of templates

Templates and friends
 With templates, friendship can be
established between either a class
template or a particular instantiation of
the template and global/member
functions or entire classes
 A few examples will clarify this:

Declare a function f() to be a friend of every class
specialization of class template X
template<class T> class X
{
….
friend void f();
….
}

Declare every member function of class Y to be a
friend of every class specialization of class
template X
template<class T> class X
{
….
friend class Y;
….
}

Declare a function f(X<T>) to be a friend of class
specialization X<T> for any T (such as float)
template<class T> class X
{
….
friend void f(X<T> &);
….
}

Declare every member function of class
specialization Y<T> to be a friend of class
specialization X<T> for any T (such as float)
template<class T> class X
{
….
friend class Y<T>;
….
}
The Standard Template Library
(STL)

The Standard Template Library (STL) is an
addition to the C++ Standard Library

Developed at the Hewlett-Packard Labs in the
mid-late 90’s

STL defines powerful, template-based,
reuseable components that implement many
common data structures and algorithms to
process those data structures

STL is extremely complex, being optimised for
efficiency. We will only scratch the surface


STL is based on 3 components

Containers

Iterators

Algorithms
Template-based containers are data structures used
to group objects of any type


Examples include linked lists, vectors and sets
Iterators encapsulate the mechanisms used to
access container elements

A simple pointer can be used as an iterator for a
standard array


Algorithms are functions that perform common
manipulations on containers
 Examples include searching and sorting
algorithms
 There are around 70 algorithms implemented in
the STL
A key aspect of the STL is that an algorithm can
be applied to a container without regard to the
exact implementation of the container
 The container’s iterator just has to support the
minimum requirement of the algorithm
 This means that programmers can write one
algorithm which can be applied to multiple
containers
Containers

Containers divided into 3 main categories
 Sequence containers
 Essentially linear data structures
 Associative containers
 Can be searched quickly using
name/value pairings
 Container adapters
 Stacks, queues and priority queues

Examples of sequence STL containers include
 vector
 Provides random access with constant time
insertions and deletions at the end
 deque (double entry queue)
 Provides random access with constant time
insertions and deletions at the beginning
and the end
 list
 Provides linear time access but constant
time insertions and deletions at any position
in the list

Examples of associative STL containers
include
 set
 Provides rapid lookup (set
membership), no duplicates around
 multiset
 As above but allows duplicates
Iterators

Iterators allow generic algorithms to ‘plug
in’ to different containers
 As long as the container supports the
iterator that the algorithm uses to access
container elements, the algorithm can be
applied to it
Container
vector
Iterator
Algorithm
sort
find
list

There are different classes of iterator to support
things like linear or random access

However, certain iterator operations are uniform
and can be applied to all containers

* (de-referencing) allows access to the element
to pointer to by the iterator

++ (increment) moves the iterator to the next
element

begin() points the iterator at the first element

end() points the iterator at the last element

Generally speaking, we have the following subdivision of iterators and associated containers
 Sequence containers vector, deque
 Random access iterators
 Sequence container list
 Linear bidirectional iterator
 Associative containers set, multi-set, map,
multi-map
 Linear bidirectional iterator
 No iterators supported for stack, queue, priority
queue
Iterator operations


Depends on iterator type
A few examples
 ++p, p++,--p, p--(pre and post
increment/decrement)
 Applies to bidirectional and random access
 *p (de-referencing)
 Applies to bidirectional and random access
 p==p1(test for equality)
 Applies to bidirectional and random access
p+=i, p-=i (increment/decrement iterator
p by i positions)
 Applies to random access only
 p[i] (returns a reference to the element
offset from p by i positions)
 Applies to random access only
 p<=p1(returns true if iterator p less than
iterator p1 (ie it is before p1 in the
container)
 Applies to random access only

Example. vector




Enables efficient random access rather like an
array but can re-size itself
Supports a random access iterator
All STL algorithms can operate on a vector as they
all support random access
A vector has a size (the actual number of elements
in the container) and a capacity (the number of
elements that can be added before the vector
resizes)
#include <vector>
int main()
{
int array[6]={1,2,3,4,5,6};
vector<int> vec(array,array+6);
for (int *ptr=array; ptr!=(array+6); ptr++)
cout<<*ptr;
vector<T>::iterator it;
for (it=vec.begin(); it!=vec.end(); it++)
cout << *it;
// sort the vector
sort(vec.begin(),vec.end());
}
The previous program shows the similarity
between array access using pointers and
container access using an iterator
 Also de-referening an iterator (pointer) to
access the container (array) element
 Also the program shows how a sort()
function is called
 Iterators passed as arguments
 In general the STL is enormously powerful
and should always be used in preference to
custom written container classes
