Transcript Function Templates

Data Structure
Lecture 1
Data Structures
The Logical Organization of Data is called data
structures
 organize data  more efficient programs.
More powerful computers  more complex
applications.
More complex applications demand more
calculations.
Organizing Data
Any organization for a collection of records that
can be searched, processed in any order, or
modified.
The choice of data structure and algorithm can
make the difference between a program
running in a few seconds or many days.
Efficiency
A solution is said to be efficient if it solves the
problem within its resource constraints.
• Space
• Time
The cost of a solution is the amount of
resources that the solution consumes.
Templates
• C++ supports code reuse in different ways.
• The template feature in C++ provides way to reuse source code.
Function Templates
• Suppose you want to write a function that returns the
absolute value of a number.
• Ordinarily, this function would be written for a
particular data type:
int abs(int n) // absolute value of ints
{
return (n<0) ? -n : n; // if n is negative, return –n
}
• Here the function is defined to take an argument of
type int and to return a value of this same type.
Function Templates
• But now suppose you want to find the absolute value of a type long.
You need to write a completely new function:
long abs(long n) // absolute value of longs
{
return (n<0) ? -n : n;
}
• And again, for type float:
float abs(float n) // absolute value of floats
{
return (n<0) ? -n : n;
}
Function Templates
• The body of the function is the same in each case, but they must be
separate functions because they handle variables of different types.
• It’s true that in C++ these functions can all be overloaded to have the
same name, but you must nevertheless write a separate definition
for each one.
• Rewriting the same function body over and over for different types
Wastes time as well as space in the listing.
Function Templates
• Also, if you find you’ve made an error in one such function, you’ll
need to remember to correct it in each function body. Failing to do
this correctly is a good way to introduce inconsistencies into your
program.
• It would be nice if there were a way to write such a function just once
and have it work for many different data types. This is exactly what
Function templates do for you.
Function Templates
#include <iostream.h>
template <class T> // function template
T abs(T n)
{ return (n < 0) ? -n : n; }
void main()
{ int int1 = 5;
int int2 = -6;
long lon1 = 70000;
long lon2 = -80000;
double dub1 = 9.95;
double dub2 = -10.15; // calls instantiate functions
cout << "abs(" << int1 << ")=" << abs(int1) << endl; // abs(int)
cout << "abs(" << int2 << ")=" << abs(int2) << endl; // abs(int)
cout << "abs(" << lon1 << ")=" << abs(lon1) << endl; // abs(long)
cout << "abs(" << lon2 << ")=" << abs(lon2) << endl; // abs(long)
cout << "abs(" << dub1 << ")=" << abs(dub1) << endl; // abs(double)
cout << "abs(" << dub2 << ")=" << abs(dub2) << endl; // abs(double)
}
OUTPUT:
abs(5)=5
abs(-6)=6
abs(70000)=70000
abs(-80000)=80000
abs(9.95)=9.95
abs(-10.15)=10.15
Function Templates
• The key innovation in function templates is to represent
the data type used by the function not as a specific type
such as int, but by a name that can stand for any type.
• In the function template above, this name is T.
• The template keyword signals the compiler that I’m about
to define a Function template.
• The keyword class, within the angle brackets, might just as
well be called type. As you’ve seen, you can define your
own data types using classes, so there’s really no
distinction between types and classes.
• The variable following the keyword class (T in this
example) is called the template argument.
Function Templates
• What does the compiler do when it sees the template keyword and the
Function definition that follows it?
• The function template itself doesn’t cause the compiler to generate any
code.
• It can’t generate code because it doesn’t know yet what data type the
function will be working with.
• It simply remembers the template for possible future use.
• Code generation doesn’t take place until the function is actually called
(invoked) by a statement within the program. This happens in expressions
such as abs(int1) in the Statement
cout << "abs(" << int << ")=" << abs(int1);
Function Templates
• When the compiler sees a function call, it knows that the type to use
is int, because that’s the type of the argument int1.
• So it generates a specific version of the abs() function for type int,
substituting int wherever it sees the name T in the function template.
• This is called instantiating the function template, and each
instantiated version of the function is called a template function.
Function Templates
• Notice that the amount of RAM used by the program is
the same whether we use the template approach or
write three separate functions.
• What we’ve saved is having to type three separate
functions into the source file. This makes the listing
shorter and easier to understand.
• Also, if we want to change the way the function works, I
need to make the change in only one place in the listing
instead of three.
Function Templates with Multiple Arguments
• Let’s look at another example of a function template.
This one takes Three arguments: two template
arguments and one basic type.
• The purpose of this function is to search an array for a
specific value.
• The function returns the array index for that value if it
finds it, or -1 if it can’t find it.
• The arguments are a pointer to the array, the value to
search for, and the size of the array.
Function Templates with Multiple Arguments
// function returns index number of item, or -1 if not found template
template <class atype>
int find(const atype* array, atype value, int size)
{
for(int j=0; j<size; j++)
if(array[ j ]==value) return j;
return -1;
}
char chrArr[ ] = {'a', 'c', 'f', 's', 'u', 'z'}; // array
char ch = 'f'; // value to find
int intArr[ ] = {1, 3, 5, 9, 11, 13};
int in = 6;
double dubArr[ ] = {1.0, 3.0, 5.0, 9.0, 11.0, 13.0};
double db = 4.0;
Function Templates with Multiple Arguments
int main()
{
cout << "\n 'f' in chrArray: index=" << find(chrArr, ch, 6);
cout << "\n 6 in intArray: index=" << find(intArr, in, 6);
cout << "\n 4 in dubArray: index=" << find(dubArr, db, 6);
return 0;
}
• Here, the name of the template argument is atype. The compiler generates
three versions of the function, one for each type used to call it.
OUTPUT:
'f' in chrArray: index=2
6 in intArray: index=-1
4 in dubArray: index=-1
Template Arguments Must Match
• When a template function is invoked, all instances of the same template
argument must be of the same type. For example, in find(), if the array name
is of type int, the value to search for must also be of type int. You can’t say
int intarray[ ] = {1, 3, 5, 7}; // int array
float f1 = 5.0; // float value
int value = find(intarray, f1, 4); // error
• Because the compiler expects all instances of atype to be the same type.
find(int*, int, int); // It can generate a function
find(int*, float, int); // It can’t generate a function
• Because the first and second arguments must be the same type.
Linear Data Structures
• There are two ways of storing data structures in
the computer’s memory.
• The first of these storage-allocation methods, which
takes advantage of the one-dimensional property of
the computer’s memory, is called sequential
allocation.
• The second allocation method, which is based on
the storage of the address or location of each
element in the list, is known as linked allocation.
Stack
• A stack is a special case of a list.
• Rather than being allowed to insert a new item into the list
at any place, additions to a stack are restricted to one end
identified as the top of the stack.
• Deletions from the stack are also restricted to the top of the
stack.
• Usually, only the item at the top of the stack is accessible to
someone using the stack ADT.
• A stack is often referred to as a FILO (First In Last Out) or
LIFO (Last In First Out) list. The stack only allows addition
and removal from the top so the order of removal is the
opposite to that of insertion.
Stack
• A stack is a list with the restriction that Inserts and
Removes can be performed in only one position,
namely the end of the list, called the top.
• Fundamental operations on a stack are
Push - equivalent to an insert
Pop - removes the most recently inserted
element
• Pop from an empty stack is generally considered an
error in the stack ADT.
• Running out of space when performing a push is an
implementation error but not an ADT error.
The Stack (Common Examples)
• Plates on a cafeteria serving line.
• This arrangement of trays is supported by a spring so that a person desiring
a tray finds that only one is available at the surface of the tray counter.
Top tray of pile
Stacked trays
Spring
The Stack (Common Examples)
• Railway Shunting System
• Suppose that we have four railway
cars (DCBA) sitting on the left-hand
(input) track, as shown in the fig.
Input
D
C
B
A
Before
A C D
B
After
Stack
• We are required to rearrange these
cars so that their order is (ACDB) that
of the right-hand (output) track in the
fig.
• We will restrict our shunting system
so that it typifies a stack.
• Therefore, once a railway car has left
the left-hand (input) track for the
stack, it cannot return.
• Likewise, once a railway car has
left the stack for the right hand
(output) track, it cannot return to
the stack.
The Stack (Common Examples)
• Railway Shunting System
Input
D
C
B
A
Before
A C D
B
After
Stack
• Clearly, at any given time, the
only car that can move onto the
stack is the one at the front of the
input stream.
• The only car that can move to the
output stream is the one at the top
of the stack.
The Stack (Common Examples)
• Railway Shunting System
Input
D
C
B
A
Before
A C D
B
After
Stack
Operation Input
Initial DCBA
Push(A) DCB
A
Push(B) DC
B
A
Pop() DC
A
Push( C)D
C
A
Push(D)
D
C
A
Pop()
C
A
Pop()
A
Pop()
Stack
B
B
B
DB
CDB
ACDB
Output
The Stack (Common Examples)
• A list of recently visited URLs for a web browser’s “Back” and
“Forward” buttons.
• The “undo” mechanisms in word processors.
The Stack
• Assume an initially empty stack and following sequence of insertions
and deletions:
Stack
• The five common operations which are associated
with a stack are:
• Initialize: Initializes stack; that is, prepare it for use as a
stack.
• Push: Inserts an element on top of stack and returns the
new stack.
• Pop: Removes the top element from the stack and return
the updated stack.
• IsEmpty: Returns “true” as the function result if stack
contains no element, or otherwise returns “false”.
• TopValue: returns the top element of stack as the
function result.
Stack (stack.h)
#include<iostream.h>
const int MAX = 100;
class Stack {
private:
int data[MAX]; // stack: array of any type
int top; // number of top of stack
public:
Stack(); // constructor
void push(Type); // put number on stack
int pop(); // take number off stack
bool isEmpty();//checks if stack is empty or not
int topValue();//gives top value of stack
};
Stack (stack.h)
Stack::Stack()
{
top = -1;
}
// Push a value onto the stack
void Stack::push(int item)
{
if (top == MAX-1)
cerr << "Stack Full!\n";
else
data[++top] = item;
}
Stack (stack.h)
// Pop a value fromthe stack
int Stack::pop()
{
if (top == -1)
{
cerr << "Stack Empty!\n";
return 0;
}
else
return data[top--];
}
Stack (stack.h)
// Check whether the stack is empty
bool Stack::isEmpty()
{
if (top == -1)
return true;
else
return false;
}
// Provide the top value of the stack
Type Stack::topValue()
{
return data[top];
}
Stack (driver.cpp)
#include<iostream.h>
#include"stack.h"
void main()
{
// s1 is object of class Stack<float>
Stack s1;
s1.push(11);
s1.push(22);
s1.push(33);
cout << "1: " << s1.pop() << endl;
cout << "2: " << s1.pop() << endl;
while (!s1.isEmpty())
{cout <<"from loop: " << s1.pop() <<endl;}
Output
1: 33
2: 22
from loop: 11
Class Templates
• The template concept can be applied to classes as well
as to functions.
• Class templates are generally used for data storage
(container) classes.
• Stacks and linked lists, are examples of data storage
classes.
• The Stack class in the program that is presented below,
could store data only of type int:
Class Templates
class Stack {
int st[MAX]; // array of ints
int top; // index number of top of stack
public:
Stack(); // constructor
void push(int var); // takes int as argument
int pop(); // returns int value
};
• If I wanted to store data of type long in a stack, I would need to define a
completely new class:
class LongStack {
long st[MAX]; // array of longs
int top; // index number of top of stack
public:
LongStack(); // constructor
void push(long var); // takes long as argument
long pop(); // returns long value
};
Class Templates
Solution with a class template:
template <class Type>
class Stack{
enum {MAX=100};
Type st[MAX]; // stack: array of any type
int top; // number of top of stack
public:
Stack(){top = 0;} // constructor
void push(Type ); // put number on stack
Type pop(); // take number off stack
};
template<class Type>
void Stack<Type>::push(Type var) // put number on stack
{
if(top > MAX-1) // if stack full,
cout<< "Stack is full!";
st[top++] = var;
}
Class Templates
template<class Type>
Type Stack<Type>::pop() // take number off stack
{
if(top <= 0) // if stack empty,
cout<< "Stack is empty!";
return st[--top];
}
Class Templates
int main()
{
// s1 is object of class Stack<float>
Stack<float> s1;
// push 2 floats, pop 2 floats
s1.push(1111.1);
s1.push(2222.2);
cout << "1: " << s1.pop() << endl;
cout << "2: " << s1.pop() << endl;
Class Templates
// s2 is object of class Stack<long>
Stack<long> s2;
// push 2 longs, pop 2 longs
s2.push(123123123L);
s2.push(234234234L);
cout << "1: " << s2.pop() << endl;
cout << "2: " << s2.pop() << endl;
return 0;
} // End of program
Class Templates with an int as template
template <class Type, int Size>
class Stack{
Type st[Size]; // stack: array of any type
int top; // number of top of stack
public:
Stack(){top = 0;} // constructor
void push(Type ); // put number on stack
Type pop(); // take number off stack
};
template<class Type, int Size>
void Stack<Type>::push(Type var) // put number on stack
{
if(top > Size-1) // if stack full,
cout<< "Stack is full!";
st[top++] = var;
}
Class Templates with an int as template
template<class Type, int Size>
Type Stack<Type>::pop() // take number off stack
{
if(top <= 0) // if stack empty,
cout<< "Stack is empty!";
return st[--top];
}
Class Templates with an int as template
int main()
{ // s2 is object of class Stack<long> and of Size 10
Stack<long, 10> si;
Stack<float, 50> sf;
// push 2 longs, pop 2 longs
si.push(123123123L);
si.push(234234234L);
cout << "1: " << si.pop() << endl;
cout << "2: " << si.pop() << endl;
// push 2 longs, pop 2 longs
sf.push(8.91);
si.push(100.2345);
cout << "1: " << sf.pop() << endl;
cout << "2: " << sf.pop() << endl;
return 0;
} // End of program