Transcript template

CE00314-2
Further Programming Concepts
in C++
Lecture 6
Collections & Templates
Introduction

Part 1 Collections





Static - Dynamic
Template definition
Function templates
Class templates
Part 2 Adaptable collections

Further inheritance
Collections


Arrays
Dynamic collections

Linked lists




Constructed within application (specific)
Generic linked list class
Template implementation of generic l. list
Standard Template Library contains



Vectors
Linked Lists
Other STLs
Array of accounts

COLLECTIONS
Array initialisation
int b[5] = {75,25,100,-45,60};
Account acct[3] = {Account(500,5,0.6),
Account(),
Account(100.0) };
An array of various accounts

main()
{
Savings
Time
Investment
acc1(100.0);
acc2(500.0, 100.0);
acc3(101.5, 6.5);
Account* staffacct[3] = { &acc1,
&acc2,
&acc3}
for(i = 0; i<3; i++)
{
staffacct[i]->print();
}
Arrays and new




Arrays can be created with new
int* p = new int[10];
elements are accessed using subscripts
p[0],p[1] ...
similarly for objects:
Account * acs = new Account[20];
cout<< acs[0]->balance();
Deleting Objects




Once an object created with new is finished it
can be destroyed using delete
delete ac1;
If the pointer points to an array it is necessary
to tell C++ this by writing:
delete [ ] p;
Dynamic Collections
•
•
•
Arrays are a fixed size although can be
resized dynamically by using memory
management features used in C
Dynamic structres ccccna be used to allow
collection to shrink and grow dynamically
Different implementations exist
Comparing Implementations

Fixed size versus dynamic size

A statically allocated array


Prevents the enqueue operation from adding an item
to the queue if the array is full
A resizable array or a reference-based
implementation

Does not impose this restriction on the enqueue
operation
Comparing Implementations

Pointer-based implementations

A linked list implementation


More efficient
The ADT list implementation

Simpler to write
A Summary of Position-Oriented
ADTs

Position-oriented ADTs




Stacks and queues


List
Stack
Queue
Only the end positions can be accessed
Lists

All positions can be accessed
A Summary of Position-Oriented
ADTs

Stacks and queues are very similar

Operations of stacks and queues can be paired
off as





createStack and createQueue
Stack isEmpty and queue isEmpty
push and enqueue
pop and dequeue
Stack getTop and queue getFront
A Summary of Position-Oriented
ADTs

ADT list operations generalize stack and
queue operations
–
–
–
–
getLength
insert
remove
retrieve
ADT objects

Rely on use of an Abstract Class which
contains the referencing mechanism and
allows objects to be included in the collections.
ABSTRACT BASE CLASSES

class Object
{
public:
Object(){;}
virtual ~Object(){;}
virtual ostream& printOn(ostream&) const = 0;
friend ostream& operator<<(ostream& out,
const Object& ob)
{
ob.printOn(out);
return out;
}
}
A linked List
class Entry{
public:
Entry *next;
Object *info;
Entry( Object *obj ) {info = obj; next = 0; }
~Entry() { if( ! (info==0) ) delete info; }
};
Use this as data for linked list
class List
{
private:
Entry *head;
int NoEntries;
public:
List() { head = 0; NoEntries=0;}
~List();
linked list cont.
Entry* returnHead() const { return head ;}
void
int
};
add( Object& );
isEmpty(){return head == 0;}
Linked list
void List::add( Object& newEntry )
{
Entry *newElement = new Entry(
&newEntry );
newElement->next = head;
head = newElement;
NoEntries++;
}
Destructor

List::~List()
{
while(head != 0)
{
Entry* temp = head;
head = head-> next;
delete temp;
}
}
Container Class


As can be seen form the previous example the
object is a Node which is part of a list
The list is an example of a container class
Container Classes



Container classes are an important category of ADTs
 They are used to maintain collections of elements like stacks,
queues, linked lists, tables,trees, etc.
Container classes form the basis for various C++ class libraries
C++ container classes can be implemented using several
methods:
 Ad hoc, rewrite from scratch each time
 A generic class facility (eg. list class with list nodes)
 Parameterised Types (use of templates to generalise the class)
 void Pointer Method (allows heterogenous collections)
Example Pointer Method


Generic ADT List container class
4 basic operations




Insert
Membership (e.g. IsInList)
Removal
Iteration (e.g. Display routine)
Example Applications
Generic List.h
#ifndef Generic List
#define Generic List
class List {
public:
List (void);
~List (void);
void remove current (void);
// Used as iterators: : :
void reset (void);
void next (void);
protected:
class Node f
friend List;
public:
Node (void *, Node *n = 0);
~Node (void);
void add to front (void *);
void add to end (void *);
Node *remove (void *);
private:
void *element ; // Pointer to actual data
Node *next ;
};
Generic List.h (cont'd)
protected:
// used by subclasses for implementation
void add to end (void *);
void add to front (void *);
Node *current value (void);
void *current (void);
bool includes (void *);
void *remove (void *);
// important to make match virtual!
virtual bool match (void *, void *);
private:
Node *head ;
Node *iter ; // used to iterate over lists
};
// Iterator functions
inline List::Node *List::current value (void) {
return this->iter ;
}
inline void List::reset (void) {
this->iter = this->head ;
}
inline void *List::current (void) {
if (this->iter )
return this->iter ->element ;
else
return 0;
}
inline void List::next (void) {
this->iter = this->iter->next ;
}
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;
int top;
T* stackPtr;
// No. of elements in the stack
// Location of the top element
// 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;}
};
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 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
Template Definition

Cambridge Dictionary

template
1 a pattern made of metal, plastic or paper, which is used
for making many copies of a shape or to help cut material
accurately
2 a system that helps you arrange information on a
computer screen

C++

Pattern for handling generic data
Function overloading

Swap revisited

To handle integers
void swap(int& rnA, int& rnB)
{
int nTemp;
nTemp = rnA;
rnA = rnB;
rnB = nTemp
}
Function overloading

Swap revisited

To handle characters
void swap(char& rnA, char& rnB)
{
char nTemp;
nTemp = rnA;
rnA = rnB;
rnB = nTemp
}
Function overloading

Swap revisited



float, double …….
Separate functions for each ??
Generic function



Generic functionality
Generic data – automatically typed when used
Template function
Template function

Conceptually
void swap(Type_of_Var& Var1, Type_of_Var& Var2)
{
Type_of_Var Temp;
Temp = Var1;
Var1 = Var2;
Var2 = Temp;
}
Template Function - syntax
template<class T>
// template prefix
void swapValues(T& Var1, T& Var2)
{
T Temp;
Temp = Var1;
Var1 = Var2;
Var2 = Temp;
}

For demonstration see – Template1.cpp
Template functions - array print


Handling unspecified arrays
Array length?
template<class T>
void printArray(const T *array, const int nSize)
{
for(int nCount = 0; nCount < nSize; nCount++)
cout << array[nCount] << “ “;
cout << endl;
}

For usage example see – Template2.cpp
Template Functions - returning
Also possible to have generic return
template<class T>
T addValues(T Val1, T Val2)
{
return Val1 + Val2;
}

See Template3.cpp for usage example
Template Functions – multiple types

Possible to have more than one type





template<class T1, class T2>
Must use all parameters
All must be utilised within function
See Template4.cpp
Possible to use Tx for casting and return type

See Template5.cpp
Template functions - Plenary





Produce generic solution
Data types provided at run time
Operators must be able to handle types
Overloaded operators included
Use of keyword “class” can be replaced with
“typename”


ANSI/ISO standard allows
Programmers tend to use “class”
Class Templates

Syntax basically the same as when using function
templates

must use keyword “class”
template<class T>
class Pair
{
private:
T first;
T second;
private:
Pair();
Pair(T Val1, T Val2);


etc…..
See Template6.cpp for further details
Class templates



So far…..
Class within main file
Could place within .h file


and include
See Template7.cpp


Shows use of Array of pointers
? – mixed types?
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 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 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;
….
}
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.


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

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

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
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