Transcript dynamic arrays

Templates
&
STL
Introduction
Benefit of OOP is Code Reusability
Templates are Used for this Purpose
Two Types of Templates
Rough
Sketch
Function Templates
Same Operation on Different Types of Data
Class Templates
They perform appropriate operations depending on the data type of the
parameters
passed Programming
to them.
Computer
II
‹#›
Function Templates
Some Functions we may need often which work on Different Data Types
ANY METHOD ? YES OVERLOADING
Disadvantage : Write One type function for One type of Data passed to it
Using Function Templates
Great !!!
It can be overcome
Functions For SWAPPING TWO VALUES
1. Using Function Overloading
2. Using Function Templates
Example: Next Slide
Example Using Function Overloading
void swap(char &x, char &y)
{
char t;
t=x;
x=y;
y=t;
}
void swap(int &x, int &y)
{
int t;
t=x;
x=y;
y=t;
}
void swap(float &x, float &y)
{
float t;
t=x;
x=y;
y=t;
}
void main()
{
char ch1, ch2;
cin>>ch1>>ch2;
swap(ch1, ch2);
// compiler invokes swap(char &x, char &y);
cout<< ch1<< ch2<<endl;
int a, b;
cin>>a>>b;
swap(a, b);
// compiler invokes swap(int &x, int &y);
cout<<a<< b<<endl;
float c, d;
cin>>c>>d;
swap(c, d);
// compiler invokes swap(float &x, float
cout<<c<< d<<endl;
}
Function Templates
Such functions can be declared as a single function template without
redefining them for each and every data type.
The C++ template feature enables substitution of a single piece of code for all
these overloaded functions with a single template function as follows:
template <class T>
void swap(T &x, T &y)
{
T t;
t = x;
x = y;
y =t;
}
When swap operation is requested on operands of any data type, the compiler
creates a function internally without the user intervention and invokes the same.
Syntax: Function Templates
keyword
template data
types
at least one argument
must be template type
template <class T, … >
ReturnType FunctionName (arguments)
{
……
// body of the template function
……
}
template <class T>
void swap(T &x, T &y)
{
T t;
t = x;
x = y;
y =t;
}
Example: Functions For SWAPPING TWO VALUES
Using Function Templates
# include <iostream.h>
template <class T>
void swap(T &x, T &y)
{
T t;
t = x;
x = y;
y =t;
}
Cool !!!
compiler calls swap(char &x, char &y);
void main()
{
char ch1, ch2;
cin>>ch1>>ch2;
swap(ch1, ch2);
cout<<ch1<< “ “<<ch2<<endl;
compiler calls swap(int &x, int &y);
int a, b;
cin>>a>>b;
swap(a, b);
cout<<a<< “ “<<b<<endl;
float c, d;
compiler calls swap(float &x, float &y);
cin>>c>>d;
swap(c, d);
cout<<c<< “ “<<d<<endl;
}
More Example: Using Function Templates
#include <iostream.h>
template <class T>
T Max(T a, T b)
{
if (a>b)
return a;
else
return b;
}
void main()
{
// max with character data types
char ch, ch1, ch2;
cout<<”Enter two characters <ch1, ch2>: “;
cin>>ch1>>ch2;
ch=Max(ch1, ch2);
cout<<”Max(ch1, ch2):” <<ch<<endl;
// max with integer data types
int a, b, c;
cout<<”Enter two integers <a, b>: “;
cin>>a>>b;
c=Max(a, b);
cout<<”Max(a, b):” <<c<<endl;
// max with float data types
int f1, f2, f3;
cout<<”Enter two integers <f1, f2>: “;
cin>>f1>>f2;
f3=Max(f1, f2);
cout<<”Max(f1, f2): “<<f3<<endl;
Kool !!!
}
Class Templates
Class can also operate on different data types
A class template specifies how individual classes can be
constructed similar to normal class specification.
template
<class T>
class IntStack
class CharStack
class
DataStack
{
{
{
int array[25];
char array[25];
T
// declare a stack of 25 elements
int top; of data type T
intarray[25];
top;
public:
public: int top;
public:
IntStack();
CharStack();
DataStack();
void Push( const int &element);
void Push( const char
&element);
char Pop(void); void Push(const T &element); int Pop(void);
T Pop(void);
int GetSize(void) const;
int GetSize(void) const;
int GetSize(void) const;};
};
};
We need to Write two different Class - One for Integer / One for Char
Only One Class Type for all types of arrays
Standard
Template
Library
Standard Template Library
STL is a part of Standard C++ Library
STL provide C++ with DATA STRUCTURES and OPERATIONS on those
data types
e.g., : STACKS - Operations such as PUSH and POP
Components of STL
Containers
Collection of Objects
algorithms
iterators
EG: vectors, stacks,queues
Is a Mechanism for
accessing
In other words they are data
structures
objects in a container
one at a time
Is a function for processing
Container’s Content
EG: Sort ,Merge Containers
Reasons for Using STL
STL Containers unlike C++ arrays can grow and shrink in size
automatically
Program for Average of Integers :
1. Define a Large array
2. Fill them
3. Constantly Check for Overflow
Disadvantage : Tedious and Error Prone
The Same operation can be
done using DMA
Disadvantage : Still Tedious
and Error Prone
Such problems are eliminated with STL Containers - because they
grow and
shrink automatically
- makes
programming
Computer
Programming
II
‹#›
easy,efficient,robust
Example-1: Double each element
for (I = 0 ; I<n ; I++)
{ array[I] * = 2; }
We have to keep track of the
Lower and upper bounds of the
array
#include <vector>
vector<int > v;
// fill up v with values
for_each(v.begin( ),v.end( ),sq);
Automatically the lower and
upper bounds will be kept
track off
More Example on:STL vector container
#include <vector>
int main( )
{
int I;
vector<int > nums;
nums.insert(nums.begin( ), -99);
nums.insert(nums.begin( ), 14);
nums.insert(nums.end( ), 50);
for (I=0; I <nums.size( ); I++)
cout<<nums[I]<<endl;
nums.erase(nums.begin( ));
nums.erase(nums.begin( ));
for (I=0; I <nums.size( ); I++)
cout<<nums[I]<<endl;
return 0;
}
14
-99
50
14
-99
50
Container Basics
STL contains 7 containers - divided into two groups.
List - linked list of elements
vector- arrays which grows & shrinks
dequeue - Arrays with insertion/deletions
set
- Collection of nonduplicate keys
multiset- A set with duplicates
map
- Collection on non duplicates
with access key
multimap- A map with duplicates
Computer Programming II
Sequential
Associative
‹#›
Container Adaptor
A container adaptor adapts a container to
behave in a particular way
Three adaptors : stack ,queue,priority queue
Stack adaptor - creates a LIFO list
Queue adaptor- creates a FIFO list
Computer Programming II
‹#›
Algorithms


STL has a rich assortment of algorithms for processing containers
Categories :sorting, searching, copying and so on
STL classes are implemented as template classes
STL algorithms are implemented as template functions
Template <class bidirectionaIterator>
void reverse(bidirectionalIterator I1, BidirectionalIterator I2));
Two arguments are iterators,which can traverse a container from either
end
Computer Programming II
‹#›
STL Algorithms
sort() algorithm
#include <vector>
#include <algorithm>
int main( )
{
vector<int > v;
vector<float > v1;
sort(v.begin( ),v.end( ));
sort(v1.begin( ),v1.end( ));
//…
}
Computer Programming II
‹#›
ADT-Abstract Data Type
Abstract Data Type (ADT)
- An Abstract Data Type is a set objects together with a set of
operations.
Data Structure
- A construct within a programming language that stored a
collection of data
ADT
interface of ADT
add
changeMark
Program
sortAccordingToIDs
display
Data
Structure
What is ADT List
•A collection of elements of the same type
•Operations :
•Create the list; initialized to an empty state
•Determine whether the list is empty
•Determine whether the list is full
•Find the size of the list
•Destroy, or clear, the list
•Determine whether an item is the same as a given list element
•Insert an item in the list at the specified location
•Remove an item from the list at the specified location
•Replace an item at the specified location with another item
•Retrieve an item from the list at the specified location
•Search the list for a given item
Array-based List : STL's vector class
STL = Standard Template Library
- three basic components :
- containers (Sequence, Associative,
Container adapters)
- iterators
- algorithms
STL's Sequence Containers :
- three types : vector, deque, list
STL's vector class :
- Sequential container which can be accessed in a
random access manner.
- implemented as an array which can resize
dynamically when required.
Major operations of STL's vector class :
• push_back
add an item to the end of the container
• pop_back
remove an item from the end of the container
• at
return the item given a position
• operator[]
return the item given a position
• front
return the first item in the container
• back
return the last item in the container
• size
return the size of the container
• capacity
return the capacity of the container
• empty
check if the container is empty
• resize
resize the container
• clear
clear all the items in the container
Computer Programming II
‹#›
More Example of vector class :
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
v.push_back(4);
v.push_back(2);
v.push_back(1);
v.push_back(6);
v.push_back(8);
v.push_back(3);
for (int i=0;i<6;i++)
cout << v[i] << " ";
}
must include this
The vector class is
parameterized class (generic
class) using template, you
need to specify the type of
data to be stored.
output:
4 2 1 6 8 3
push the item to the end
of the array
The items are accessed just
as if they are array elements
Demonstrate that you do not need to worry about memory allocating for it :
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> v;
int n;
do {
cout << "=> ";
cin >> n;
if (n!=-1) v.push_back(n);
} while (n!=-1);
output:
=> 1
=> 5
=> 3
=> 2
=> -1
1 5 3 2
return the size
for (int i=0;i<v.size();i++)
cout << v[i] << " ";
}
Computer Programming II
‹#›
Demonstrate that the vector class will automatically increase its internal
storage capacity when required :
int main() {
vector<int> v;
v.push_back(5); v.push_back(1);
cout << "size = " << v.size()
<< endl;
v.push_back(3); v.push_back(7);
v.push_back(4);
cout << "size = " << v.size()
<< endl;
v.pop_back(); v.pop_back();
cout << "size = " << v.size()
<< endl;
for (int i=0;i<v.size();i++)
cout << v[i] << " "; cout << endl;
}
Computer Programming II
output:
size = 2
size = 5
size = 3
5 1 3
remove
item from
end
‹#›
Demonstrate that the vector class can be used with any data type :
int main() {
vector<string> v;
string name;
do {
cout << "=> ";
cin >> name;
if (name!="quit")
v.push_back(name);
} while (name!="quit");
for (int i=0;i<v.size();i++)
cout << v[i] << endl;
}
Computer
output:
=> shohel
=> dominic
=> angeline
=> bllaw
=> norhana
=> azzyati
=> quit
shohel
dominic
angeline
bllaw
norhana
azzyati
There are many more operation you can perform
using the vector class, you need to refer to the STL
documentation for more details.
Programming II
‹#›