Function Templates in C++
By Shanigaram MaheshIn this tutorial, we learn about the function templates in C++ and sorting with a template using some examples.
What is a Function Template in C++
A template can define a parameterized non-member function. A typical example substitutes templates for the min and max macros often defined in C.
Before considering the function template, consider those C macros:
#define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b))
These macros have a problem related to side effects.
suppose you call one of the macros this way:
a=min(b++,-c);
The min macro would expand that expression into this:
a=(b++)<(-c) ?(b++) :(-c);
SIDE EFFECTS
The side effects occur when either b gets incremented twice or c gets decremented twice, depending on which one is greater.
C++ programmers overcome this problem with an inline function, as shown here:
inline int min(int a,int b)
{
return(a < b ? a : b);
}
NO SIDE EFFECTS
No side effects occurred, but a problem exists. The min function now works with integers only. If your type cannot be converted to a meaningful integral value, then it does not work with the inline min function. The apparent solution is to use a function template, as shown here:
template<class T>
T& min(T& a,T& b)
{
return (a < b ? a: b);
}This solution isn’t perfect either. It won’t work unless both objects being compared are of the same type and are both non-const. To solve this problem, you must provide the same function with all combinations of constant and non-constant parameterized parameters, as shown here:
template<class T>
T& min(const T& a,const T& b)
{
return(a < b ? a : b);
}
template<class T>
T& min(T& a,const T& b)
{
return (a < b ? a : b);
}
template<class T>
T& min(const T& a,T& b)
{
return (a < b ? a : b);
}
Sorting with a Template
The next example of function templates sorts arrays of parameterized types.
The Standard C qsort function does this by having you provide a call-back function that performs the comparisons of array elements. Using a template, however, is easier, as long as the type supports comparisons by overloading relational operators.
The template implements the quicksort algorithm. It sorts an array of types. Its parameters are the address of the array and the number of elements in the array.
The quicksort algorithm divides the array into two parts.
- First, it arbitrarily selects an elements to represent the median value.
- Then the algorithm places all elements greater than this value in the upper part and all the lower elements in the lower part.
- Then it calls itself recursively, once for each of the two parts.
- When only one part is left, the array is fully sorted.
Program to implement quicksort using template
#include<iostream>
#include<stdlib.h>
using namespace std;
template<typename T>
int split(T a[],int low,int high)
{
T i=a[low],temp;
int p=low+1,q=high;
while(q>=p)
{
while(a[p]<i)
{
p++;
}
while(a[q]>i)
{
q--;
}
if(q>p)
{
temp=a[q];
a[q]=a[p];
a[p]=temp;
}
}
temp=a[q];
a[q]=a[low];
a[low]=temp;
return q;
}
template<typename T>
void quicksort(T a[],int low,int high)
{
int pos;
if(low<high)
{
pos=split(a,low,high);
quicksort(a,low,pos-1);
quicksort(a,pos+1,high);
}
}
int main()
{
int ai[100],size_i,size_c,i;
char ac[100];
cout<<"\nenter the size of integer array :";
cin>>size_i;
cout<<"\n enter the "<<size_i<<" integer elements :";
for(i=0;i<size_i;i++)
cin>>ai[i];
quicksort(ai,0,size_i-1);
cout<<"\n after sorting elements are : ";
for(i=0;i<size_i;i++)
cout<<" "<<ai[i];
cout<<"\nenter the size of character array :";
cin>>size_c;
cout<<"\n enter the "<<size_c<<" character elements :";
for(i=0;i<size_c;i++)
cin>>ac[i];
quicksort(ac,0,size_c-1);
cout<<"\n after sorting elements are : ";
for(i=0;i<size_c;i++)
cout<<" "<<ac[i];
}
Output from Program
enter the size of integer array :10 enter the 10 integer elements:5 4 3 6 9 10 8 65 25 14 after sorting elements are : 3 4 5 6 8 9 10 14 25 65 enter the size of character array:10 enter the 10 character elements: a k o p l f y j i v after sorting elements are : a f i j k l o p v y
We hope now the concept of Function Templates in C++ is cleared to you.
also read:
Leave a Reply