DATA STRUCTURES
LECTURE 02
WE WILL LEARN
• Debugging on Visual Studio
• Deep / Shallow Copy
• Templates
A GLIMPSE FROM PREVIOUS LECTURE
• IntPointer Task
• Error Solution
• Avoid Memory Leakage
• Destructor
• Example 1 (Debug)
SHALLOW AND DEEP COPY
void main()
{
int a=9;
int b=a;
a=10;
cout<<a<<b;
}
?? Does change in value of a leads to
change in value of b
COPYING POINTER
void main()
{
int a=9;
int*p =&a;
int*r=p;
*r=6;
cout<<a;
}
COPYING POINTER
void main()
{
int*p=new int;
int *r;
*p=8;
r=p;
*p=9;
cout<<*p<<*r;
}
DEEP COPY
void main()
{
int*p=new int;
int *r=new int;
*p=8;
*r=*p;
*p=10;
}
COPY CONSTRUCTOR
The copy constructor is a constructor
which creates an object by initializing it with
an object of the same class, which has been
created previously. The copy constructor is
used to:
• Initialize one object from another of the same
type.
• Copy an object to pass it as an argument to a
function.
• Copy an object to return it from a function.
CONTD.
If the class has pointer variables and has
some dynamic memory allocations, then it
is a must to have a copy constructor
If a copy constructor is not defined in a
class, the compiler itself defines one
Syntax: classname(const classname&
obj)
POINTER CLASS COPY CONSTRUCTOR
Class PointerInt{ int *ptr;
public:
PointerInt():ptr(NULL){}
PointerInt(int val):ptr(new int),*ptr(val){}
void allocMem(int val) {…..} ;
int addval(PointerInt p){return *ptr+*(p.ptr)}
~PointerInt(){delete ptr; ptr=NULL;}
PointerInt(const PointerInt& b){
ptr=new int;
*ptr=*(b.ptr);
};
COPY CONSTRUCTOR
• Deep Copying
• Called whenever
• an object is created by initializing it with already existing
object of same class
• An object is passed as an argument to a function
• An object is returned from a function
• Class_name(class_name & obj)
DEEP COPY VS SHALLOW COPY
Shallow Copy Deep Copy
Void main() Void main()
{ {
int *p,*q; int *p,*q;
p=new int; p=new int;
*p=5; *p=5;
q=p; // shallow copy q=new int;
*q=9; *q=*p; // deep copy
cout<<*p; cout<<*p;
} }
CLASSES WITH POINTER DATA MEMBER
• Constructor to ensure Memory is allocated
• Setter to ensure Value initialized to
memory
• Destructor to ensure de allocation
• Copy constructor should be provided to
ensure deep copy
Why?
TEMPLATES
• Generic Programming (one template->multiple
data types)
• 2 types of templates
• Function templates
• Class templates
FUNCTION TEMPLATES
• How to deal with different data types using
functions
• Without templates
• We rewrite (overload) functions Min(), Max(), and
InsertionSort() for many different types
• There has to be a better way (where we do not have to
rewrite)
• Function template
• Describes a function format that when instantiated with
particular data types generates a function definition
• Write once, use multiple times
• Compact way to make overloaded functions
FUNCTION TEMPLATE EXAMPLE :
MIN
Indicates a template is being
defined
Indicates T is our formal
template parameter
template <class T>
T Min(T a, T b) {
if (a < b)
Instantiated
return a;
else Instantiated
functions will return
functions require
a value whose type return b; two actual
is the actual
} parameters of the
template parameter
same type. Their
type will be the
actual value for T
MIN TEMPLATE
• Code segment (e.g. in main() function)
int Input1, Input2; cin>>Input1>>Input2;
cout << Min(Input1, Input2) << endl;
• Causes the following function to be generated
from our template
int Min(int a, int b) {
if (a < b)
return a;
else
return b;
}
MIN TEMPLATE
• Code segment (e.g. in main() function)
double Value1 = 4.30;
double Value2 = 19.54;
cout << Min(Value1, Value2) << endl;
• Causes the following function to be generated
from our template
double Min(double a, double b) {
if (a < b)
return a;
else
return b;
}
MIN TEMPLATE
• Code segment
complex r(6,21);
Complex s(11,29);
cout << Min(r, s) << endl;
• Causes the following function to be generated from
our template
complex Min(complex a, complex b) {
Operator < needs to be defined for
if (a < b) the actual template parameter
return a; type i.e. complex. If < is not
defined, then a compile-time error
else occurs
return b;
}
FUNCTION TEMPLATE EXAMPLE 2:
GENERIC SORTING
template <class T>
void InsertionSort(T A[], int n)
//T is data type of array A, n is size of A
{
for (int i = 1; i < n; ++i) {
if (A[i] < A[i-1]) {
T val = A[i];
int j = i;
do { A[j] = A[j-1];
--j;
} while ((j > 0) && (val < A[j-1]));
A[j] = val;
}
}
}
FUNCTION TEMPLATES EXAMPLE 3
# include <iostream>
using namespace std;
template <class T>
T abs (T n){return (n<0) ? –n:n; }
void main()
{ int int1=5, int2=-6;
long lon1=7000;
double dub1=-10.15;
cout<<abs(int1);
cout<<abs(lon1);
}
MORE THAN ONE TEMPLATE
ARGUMENT
template <class atype, class btype>
// finds an element in an array
// atype is type of elements, btype is type of size
btype find (atype * array, atype value, btype size)
{
for (btype j=0; j<size; j++)
if (array[j] == value)
return j;
return (btype) (-1);
}
CLASS TEMPLATES
#include <iostream> T remove() {
using namespace std; return a[currentpos--];
template <class T> }
class array { };
T a[10]; void main()
{array <float> arr1;
int currentpos;
array <int> arr2;
public:
arr1.insert(12.9);
array() {currentpos=-1;}
cout<<arr1.remove();
void insert (T var) {
arr2.insert(1234);
a[++currentpos]=var;
cout<<arr2.remove();}
}
ANNOUNCEMENT
Syndicate B : You have to give viva of Lab 2 Tasks before upcoming
lab i.e. 5th March, 2020
Syndicate A: You have to give viva of Lab 2 Task 2 before upcoming
lab i.e. 4th March, 2020
CLASS WORK
Write a template function that returns the
average of all the elements of an array with
a generic data type. The arguments to the
function should be the array name and the
size of the array. In main () , exercise the
function with arrays of type int, long, and
double.
PRE-LAB TASK
• Convert all the ADTs you have designed in
Lab # 01 to templated ADTs.
BOOK READINGS
• Data Structures and Algorithms in C++
by Michael T. Goodrich, Roberto Tamassia, David
M. Mount Second Edition : Chapter 2 (2.3)
• C++ How to program , Deitel & Deitel Chapter 7
