CPP

C++ Object-Oriented Programming

2013-2015 Margit ANTAL

C++ - Object-Oriented Programming

Course content

Introduction to C++

Object-oriented programming

Generic programming and the STL

Object-oriented design

2013-2015 Margit ANTAL

C++ - Object-Oriented Programming

References

M. Gregoire, Professional C++, 3rd edition, John Wiley & Sons, 2014.

S. Lippman, J. Lajoie, B. E. Moo, C++ Primer, 5th edition, Addison

Wesley, , 2013.

S. Prata, C++ Primer Plus, 6th edition, Addison Wesley, 2012.

N. Josuttis, The C++ standard library. a tutorial and reference. Pearson

Education. 2012.

A. Williams, C++ Concurrency in Action:Practical Multithreading.

Greenwich, CT: Manning. 2012.

2013-2015 Margit ANTAL

Module 1
Introduction to C++

2013-2015 Margit ANTAL

Introduction to C++
Content

History and evolution

Overview of the key features

New built-in types

Scope and namespaces
Enumerations
Dynamic memory: new and delete
Error handling with exceptions
References
The const modifier
2013-2015 Margit ANTAL

Introduction to C++
History and evolution

Creator: Bjarne Stroustrup 1983

Standards:

The first C++ standard

1998 (C++98)
2003 (C++03) technical corrigendum minor bug fixes
2007(TR1) library extensions

The second C++ standard

2011 (C++11) significant improvements in language and library

2013-2015 Margit ANTAL

Introduction to C++
Philosophy

Statically typed

General purpose

Efficient

Supports multiple programming styles:

Procedural programming
Object-oriented programming
Generic programming

2013-2015 Margit ANTAL

Introduction to C++
Standard library

C++ standard library = C standard library + STL

(Standard Template Library)

STL designed by Alexander Stepanov, provides:

Containers: list, vector, set, map

Iterators
Algorithms: search, sort,

2013-2015 Margit ANTAL

Introduction to C++
Portability

Recompilation without making changes in the

source code means portability.

Hardware specific programs are usually not

portable.

2013-2015 Margit ANTAL

Introduction to C++
Creating a program

Use a text editor to write a program and save it in a

file source code

Compile the source code (compiler is a program

that translates the source code to machine
language) object code

Link the object code with additional code (libraries)

executable code

2013-2015 Margit ANTAL

Introduction to C++
Creating a program (using GNU C++ compiler, Unix)

Source code: hello.cpp

Compile: g++ -c hello.cpp

Compile + Link: g++ hello.cpp

Output: hello.o (object code)

Output: a.out (executable code)

C++ 2011: g++ hello.cpp -std=c++0x

2013-2015 Margit ANTAL

Introduction to C++
The first C++ program

One-line comment

//hello.cpp

Preprocessor directive

#include <iostream>
using namespace std;
int main(){
cout<<Hello<<endl;
return 0;
}

The main function

I/O streams

#include <iostream>
int main(){
std::cout<<Hello<<std::endl;
return 0;
}

2013-2015 Margit ANTAL

Introduction to C++
Building a C++ program: 3 steps

preprocessor (line starting with #)

compiler

linker

2013-2015 Margit ANTAL

Introduction to C++
Most common preprocessor directives

#include [file]

the specified file is inserted into the code

#define [key] [value]

every occurrence of the specified key is replaced

with the specified value
#ifndef [key] #endif

code block is conditionally included

2013-2015 Margit ANTAL

Introduction to C++
Header files

C++ header
#include <iostream>
C header
#include <cstdio>
User defined header
#include "myheader.h"

2013-2015 Margit ANTAL

Introduction to C++
Avoid multiple includes
//myheader.h
#ifndef MYHEADER_H
#define MYHEADER_H
// the contents
#endif

2013-2015 Margit ANTAL

Introduction to C++
The main() function

int main(){ }

or

int main( int argc, char* argv[] ){ }

Result status

The number
of arguments

2013-2015 Margit ANTAL

The arguments

Introduction to C++
I/O Streams

cout: standard output

cout<<Hello, world!<<endl;

cin: standard input

int i; double d;
cin >> i >> d;

2013-2015 Margit ANTAL

End of line

Introduction to C++
Namespaces

avoid naming conflicts

//my1.h
namespace myspace1{
void foo();
}

//my2.h
namespace myspace2{
void foo();
}

//my1.cpp
#include "my1.h"
namespace myspace1{
void foo(){
cout<<"myspace1::foo\n";
}
}

//my2.cpp
#include "my2.h"
namespace myspace2{
void foo(){
cout<<"myspace2::foo\n";
}
}

myspace1::foo()

myspace2::foo()

2013-2015 Margit ANTAL

Introduction to C++
Variables

can be declared almost anywhere in your code

double d;

//uninitialized

int i = 10; //initialized

2013-2015 Margit ANTAL

Introduction to C++
Variable types

short, int, long range depends on compiler, but usually 2, 4, 4

bytes

long long (C++11) range depends on compiler usually 8 bytes

float, double, long double

bool

char, char16_t(C++11), char32_t(C++11), wchar_t

auto (C++11) the compiler decides the type automatically (auto i=7;)

decltype(expr) (C++11)
int i=10;
decltype(i) j = 20; // j will be int
2013-2015 Margit ANTAL

Introduction to C++
Variable types
#include
<iostream>

using namespace std;

int main(int argc, char** argv) {
cout<<"short
: "<<sizeof( short)<<" bytes"<<endl;
cout<<"int
: "<<sizeof( int ) <<" bytes"<<endl;
cout<<"long
: "<<sizeof( long) <<" bytes"<<endl;
cout<<"long long: "<<sizeof( long long)<<" bytes"<<endl;
return 0;
}

2013-2015 Margit ANTAL

Introduction to C++

C++0x/C++11 Support in GCC

https://gcc.gnu.org/projects/cxx0x.html

Online C++ compilers:

http://isocpp.org/blog/2013/01/online-c-compilers

2013-2015 Margit ANTAL

Introduction to C++
C enumerations (not type-safe)

always interpreted as integers

you can compare enumeration values from completely

different types

enum Fruit{ apple, strawberry, melon};

enum Vegetable{ tomato, cucumber, onion};
void foo(){
if( tomato == apple){
cout<<"Hurra"<<endl;
}
}

2013-2015 Margit ANTAL

Introduction to C++
C++ enumerations (type-safe)
enum class Mark {
Undefined, Low, Medium, High
};
Mark myMark( int value ){
switch( value ){
case 1: case2: return Mark::Low;
case 3: case4: return Mark::Medium;
case 5: return Mark::High;
default:
return Mark::Undefined;
}
}

2013-2015 Margit ANTAL

Introduction to C++
Range-based for loop
int elements[]={1,2,3,4,5};
for( auto& e: elements){
cout<<e<<endl;
}

2013-2015 Margit ANTAL

Introduction to C++
The std::array

replacement for the standard C-style array

cannot grow or shrink at run time

#include <iostream>
#include <array>
using namespace std;
int main() {
array<int, 5 > arr = {10, 20, 30, 40, 50};
cout << "Array size = " << arr.size() << endl;
for(int i=0; i<arr.size(); ++i){
cout<<arr[ i ]<<endl;
}
}

2013-2015 Margit ANTAL

Introduction to C++
Pointers and dynamic memory

compile time array

int ctarray[ 3 ]; //allocated on stack

run time array

int * rtarray = new int[ 3 ]; //allocated on heap

Stack

Heap

rtarray

2013-2015 Margit ANTAL

Introduction to C++
Dynamic memory management

allocation
int * x = new int;
int * t = new int [ 3 ];

deletion
delete x;
delete [] t;

2013-2015 Margit ANTAL

Introduction to C++
Strings

C-style strings:

array of characters

'\0' terminated

functions provided in <cstring>

C++ string

described in <string>

string firstName = "John"; string lastName = "Smith";

string name = firstName+ " "+ lastName; cout<<name<<endl;

2013-2015 Margit ANTAL

Introduction to C++
References

A reference defines an alternative name (alias) for an object.

A reference must be initialized.

Defining a reference = binding a reference to its initializer

int i = 10;
int &ri = i; //OK
int &ri1;

ri refers to (is another name for) i

//ERROR: a reference must be initialized

2013-2015 Margit ANTAL

Introduction to C++
Operations on references

the operation is always performed on the referred object

int i = 10;
int &ri = i;
++ri;
cout<<i<<endl;

// outputs 11

++i;
cout<<ri<<endl; // outputs 12

2013-2015 Margit ANTAL

Introduction to C++
References as function parameters

to permit pass-by-reference:

allow the function to modify the value of the parameter

avoid copies

void inc(int &value)

{
value++;
}
usage:
int x = 10;
inc( x );

bool isShorter(const string &s1,

const string &s2)
{
return s1.size() < s2.size();
}
usage:
string str1 ="apple";
string str2 ="nut";
cout<<str1<<"<"<<str2<<": " <<
isShorter(str1, str2);

2013-2015 Margit ANTAL

Introduction to C++
Exceptions

Exception = unexpected situation

Exception handling = a mechanism for dealing with problems

throwing an exception detecting an unexpected situation

catching an exception taking appropriate action

2013-2015 Margit ANTAL

Introduction to C++
Exceptions
#include <iostream>
#include
<stdexcept>

using namespace std;

double divide( double m, double n){
if( n == 0 ){
throw std::exception();
}else{
return m/n;
}
}
int main() {
try{
cout<<divide(1,0)<<endl;
}catch( const exception& e){
cout<<"Exception was caught!"<<endl;
}
}

2013-2015 Margit ANTAL

Introduction to C++
The const modifier

Defining constants
const int N =10;
int t[ N ];

Protecting a parameter
void sayHello( const string& who){
cout<<"Hello, "+who<<endl;
who = "new name";
}

2013-2015 Margit ANTAL

Compiler error

Introduction to C++
Using the standard library
#include <string>
#include
<vector>

#include <iostream>
using namespace std;

const int N =10;

int main() {
int t[ N ];
vector<string> fruits = {"apple","melon"};
fruits.push_back("pear");
fruits.push_back("nut");
Iterate over the elements in the vector and print them
//
for (auto it = fruits.cbegin();
it != fruits.cend(); ++it) {
cout << *iterator << endl;
}
//Print the elements again using C++11 range-based for loop
for (auto& str : fruits)
cout << str << endl;
return 0;
}
2013-2015 Margit ANTAL

Introduction to C++
Programming task:

Write a program that reads one-word strings from the

standard input, stores them and finally prints them on the
standard output

Sort the container before printing

use the sort algorithm

#include <algorithm>
...
vector<string> fruits;
...
sort(fruits.begin(),fruits.end());

2013-2015 Margit ANTAL

Module 2
Object-Oriented Programming
Classes and Objects

2013-2015 Margit ANTAL

Object-Oriented Programming (OOP)

Content

Classes and Objects

Advanced Class Features

Operator overloading

Object Relationships

Abstraction

2013-2015 Margit ANTAL

OOP: Classes and Objects

Content

Members of the class. Access levels. Encapsulation.

Class: interface + implementation

Constructors and destructors

const member functions

Constructor initializer

Copy constructor

Object's lifecycle

2013-2015 Margit ANTAL

OOP: Classes and objects

Class = Type ( Data + Operations)

Members of the class

Data:

Operations:

data members (properties)

methods (behaviors)

Each member is associated with an access level:

private

public

protected

2013-2015 Margit ANTAL

OOP: Classes and objects

Object = Instance of a class

An employee object: Employee emp;

Properties are the characteristics that describe an

object.
What makes this object different?

id, firstName, lastName, salary, hired

Behaviors answer the question:

What can we do to this object?

hire(), fire(), display(), get and set data

members

2013-2015 Margit ANTAL

OOP: Classes and objects

class TYPES

Encapsulation

Employee

an object encapsulates data and functionality.

Functionality

Data

2013-2015 Margit ANTAL

m Id: int
m FirstNam e: string
m LastNam e: string
m Salary: int
bHired: b ool

+
+
+
+
+
+
+
+
+
+
+
+
+

Em ployee()
display() : void {query}
hire() : void
fire() : void
setFirstNam e(strin g) : void
setLastNam e(strin g) : void
setId(int) : vo id
setSalary(int) : vo id
getFirstNam e() : string {query}
getLastNam e() : string {query}
getSalary() : int {query}
getIsHired() : bool {query}
getId() : i nt {query}

OOP: Classes and objects

Class creation

class declaration - interface

Employee.h

class definition implementation

Employee.cpp

2013-2015 Margit ANTAL

OOP: Classes and objects

Employee.h
class Employee{
public:
Employee();
void display() const;
void hire();
void fire();
// Getters and setters
void setFirstName( string inFirstName );
void setLastName ( string inLastName );
void setId( int inId );
void setSalary( int inSalary );
string getFirstName() const;
string getLastName() const;
int getSalary() const;
bool getIsHired() const;
int getId() const;
private:
int mId;
string mFirstName;
string mLastName;
int mSalary;
bool bHired;
};

2013-2015 Margit ANTAL

Methods' declaration

Data members

OOP: Classes and objects

The Constructor and the object's state

The state of an object is defined by its data members.

The constructor is responsible for the initial state of the object

Employee :: Employee() : mId(-1),
mFirstName(""),
mLastName(""),
mSalary(0),
bHired(false){
}
Employee :: Employee() {
mId = -1;
mFirstName="";
mLastName="";
mSalary =0;
bHired = false;
}

2013-2015 Margit ANTAL

Members are initialized

through the
constructor initializer list
Members are assigned
Only constructors can use
this initializer-list syntax!!!

OOP: Classes and objects

Constructors

responsibility: data members initialization of a class object

invoked automatically for each object

have the same name as the class

have no return type

a class can have multiple constructors (function overloading)

may not be declared as const

constructors can write to const objects

2013-2015 Margit ANTAL

OOP: Classes and objects

Defining a member function

Employee.cpp

A const member function cannot change the object's

state, can be invoked on const objects
void Employee::hire(){
bHired = true;
}
string Employee::getFirstName() const{
return mFirstName;
}

2013-2015 Margit ANTAL

OOP: Classes and objects

Defining a member function
void Employee::display() const {
cout << "Employee: " << getLastName() << ", "
<< getFirstName() << endl;
cout << "-------------------------" << endl;
cout << (bHired ? "Current Employee" :
"Former Employee") << endl;
cout << "Employee ID: " << getId() << endl;
cout << "Salary: " << getSalary() << endl;
cout << endl;
}

2013-2015 Margit ANTAL

OOP: Classes and objects

TestEmployee.cpp

Using const member functions

void foo( const Employee& e){

e.display(); // OK. display() is a const member function
e.fire();
// ERROR. fire() is not a const member function
}
int main() {
Employee emp;
emp.setFirstName("Robert");
emp.setLastName("Black");
emp.setId(1);
emp.setSalary(1000);
emp.hire();
emp.display();
foo( emp );
return 0;
}

2013-2015 Margit ANTAL

OOP: Classes and objects

Interface:

Employee.h

Implementation:

Employee.cpp

#ifndef EMPLOYEE_H
#define EMPLOYEE_H

#include "Employee.h"

#include <string>
using namespace std;

Employee::Employee() :
mId(-1),
mFirstName(""),
mLastName(""),
mSalary(0),
bHired(false){
}

class Employee{
public:
Employee();
//...
protected:
int mId;
string mFirstName;
string mLastName;
int mSalary;
bool bHired;
};

string Employee::getFirstName() const{

return mFirstName;
}
/
/ ...

#endif

2013-2015 Margit ANTAL

OOP: Classes and objects

Object life cycles:

creation

assignment

destruction

2013-2015 Margit ANTAL

OOP: Classes and objects

Object creation:
int main() {
Employee emp;
emp.display();

Employee *demp = new Employee();

demp->display();
// ..
delete demp;
return 0;
when an object is created,

one of its constructors is executed,

all its embedded objects are also created

2013-2015 Margit ANTAL

object's
lifecycle

OOP: Classes and objects

Object creation constructors:

default constructor (0-argument constructor)

Employee :: Employee() : mId(-1), mFirstName(""),

mLastName(""), mSalary(0), bHired(false){
}
Employee :: Employee() {
}

when you need

Employee employees[ 10 ];
vector<Employee> emps;
2013-2015 Margit ANTAL

memory allocation
constructor call on
each allocated object

OOP: Classes and objects

Object creation constructors:

Compiler-generated default constructor

class Value{
public:
void setValue( double inValue);
double getValue() const;
private:
double value;
};

if a class does not specify any constructors, the compiler will generate
one that does not take any arguments

2013-2015 Margit ANTAL

OOP: Classes and objects

Constructor initializer
class ConstRef{
public:
ConstRef( int );
private:
int mI;
const int mCi;
int& mRi;
};
ConstRef::ConstRef( int inI ){
mI = inI; //OK
mCi = inI; //ERROR: cannot assign to a const
mRi = inI; //ERROR: uninitialized reference member
}
ConstRef::ConstRef( int inI ): mI( inI ), mCi( inI ), mRi( inI ){}

ctor initializer
2013-2015 Margit ANTAL

OOP: Classes and objects

Constructor initializer

data types that must be initialized in a ctor-initializer

const data members

reference data members
object data members having no default
constructor
superclasses without default constructor

2013-2015 Margit ANTAL

OOP: Classes and objects

A non-default Constructor
Employee :: Employee( int inId, string inFirstName,
string inLastName,
int inSalary, int inHired) :
mId(inId), mFirstName(inFirstName),
mLastName(inLastName), mSalary(inSalary),
bHired(inHired{
}

2013-2015 Margit ANTAL

OOP: Classes and objects

Copy Constructor

called in one of the following cases:

Employee emp1(1, "Robert", "Black", 4000, true);

Employee emp2( emp1 ); //copy-constructor called
Employee emp3 = emp2; //copy-constructor called
void foo( Employee emp );

if you don't define a copy-constructor explicitly, the compiler

creates one for you

this performs a bitwise copy

2013-2015 Margit ANTAL

OOP: Classes and objects

//Stack.h

//Stack.cpp

#ifndef STACK_H
#define STACK_H

#include "Stack.h"

class Stack{
public:
Stack( int inCapacity );
void push( double inDouble );
double top();
void pop();
bool isFull();
bool isEmpty();
private:
int mCapacity;
double * mElements;
double * mTop;
};
#endif /* STACK_H */

Stack::Stack( int inCapacity ){

mCapacity = inCapacity;
mElements = new double [ mCapacity ];
mTop = mElements;
}
void Stack::push( double inDouble ){
if( !isFull()){
*mTop = inDouble;
mTop++;
}
}

2013-2015 Margit ANTAL

OOP: Classes and objects

//TestStack.cpp
#include "Stack.h"

s1: Stack
mCapacity: 3
mElements
mTop

int main(){
Stack s1(3);
Stack s2 = s1;
s1.push(1);
s2.push(2);

cout<<"s1: "<<s1.top()<<endl;
cout<<"s2: "<<s2.top()<<endl;

1
s2: Stack
mCapacity: 3
mElements
mTop

2013-2015 Margit ANTAL

OOP: Classes and objects

Copy constructor:

T ( const T&)

//Stack.h

//Stack.cpp

#ifndef STACK_H
#define STACK_H

#include "Stack.h"

class Stack{
public:
//Copy constructor
Stack( const Stack& );
private:
int mCapacity;
double * mElements;
double * mTop;
};
#endif /* STACK_H */

Stack::Stack( const Stack& s ){

mCapacity = s.mCapacity;
mElements = new double[ mCapacity ];
int nr = s.mTop - s.mElements;
for( int i=0; i<nr; ++i ){
mElements[ i ] = s.mElements[ i ];
}
mTop = mElements + nr;
}

2013-2015 Margit ANTAL

OOP: Classes and objects

s1: Stack
//TestStack.cpp
#include "Stack.h"

mCapacity: 3
mElements
mTop

int main(){
Stack s1(3);
Stack s2 = s1;
s1.push(1);
s2.push(2);

0
1

cout<<"s1: "<<s1.top()<<endl;
cout<<"s2: "<<s2.top()<<endl;

s2: Stack

mCapacity: 3
mElements
mTop
0
1
2
2013-2015 Margit ANTAL

OOP: Classes and objects

Destructor

when an object is destroyed:

the object's destructor is automatically invoked,

the memory used by the object is freed.

each class has one destructor

usually place to perform cleanup work for the object

if you don't declare a destructor the compiler will generate

one, which destroys the object's member

2013-2015 Margit ANTAL

OOP: Classes and objects

Destructor

Syntax: T :: ~T();
Stack::~Stack(){
if( mElements != nullptr ){
delete[] mElements;
mElements = nullptr;
}
}
{

// block begin
Stack s(10);
// s: constructor
Stack* s1 = new Stack(5);// s1: constructor
s.push(3);
s1->push(10);
delete s1;
//s1: destructor
s.push(16);
// block end
//s: destructor

2013-2015 Margit ANTAL

OOP: Classes and objects

Default parameters

if the user specifies the arguments the defaults are ignored

if the user omits the arguments the defaults are used

the default parameters are specified only in the method declaration

(not in the definition)

//Stack.h
class Stack{
public:
Stack( int inCapacity = 5 );
..
};
//Stack.cpp
Stack::Stack( int inCapacity ){
mCapacity = inCapacity;
mElements = new double [ mCapacity ];
mTop = mElements;
}

//TestStack.cpp
Stack s1(3);
//capacity: 3
Stack s2;
//capacity: 5
Stack s3( 10 ); //capacity: 10

2013-2015 Margit ANTAL

OOP: Classes and objects

The this pointer

every method call passes a pointer to the object for which it

is called as hidden parameter having the name this

Usage:

for disambiguation
Stack::Stack( int mCapacity ){
this mCapacity = mCapacity;
//..
}

2013-2015 Margit ANTAL

OOP: Classes and objects

Programming task [Prata]
class Queue
{
enum {Q_SIZE = 10};
private:
// private representation to be developed later
public:
Queue(int qs = Q_SIZE); // create queue with a qs limit
~Queue();
bool isempty() const;
bool isfull() const;
int queuecount() const;
bool enqueue(const Item &item); // add item to end
bool dequeue(Item &item); // remove item from front
};

2013-2015 Margit ANTAL

OOP: Classes and objects

Programming task [Prata]
class Queue
{
private:
// class scope definitions
// Node is a nested structure definition local to this class
struct Node { Item item; struct Node * next;};
enum {Q_SIZE = 10};
// private class members
Node * front; // pointer to front of Queue
Node * rear; // pointer to rear of Queue
int items; // current number of items in Queue
const int qsize; // maximum number of items in Queue
};

2013-2015 Margit ANTAL

Module 3
Object-Oriented Programming
Advanced Class Features

2013-2015 Margit ANTAL

OOP: Advanced class features

Content

Inline functions

Stack vs. Heap

Array of objects vs. array of pointers

Passing function arguments

Static members

Friend functions, friend classes

Nested classes

2013-2015 Margit ANTAL

OOP: Advanced class features

Inline functions

designed to speed up programs (like macros)

the compiler replaces the function call with the

function code (no function call!)

advantage: speed

disadvantage: code bloat

ex. 10 function calls 10 * function's size

2013-2015 Margit ANTAL

OOP: Advanced class features

How to make a function inline?

use the inline keyword either in function declaration

or in function definition

both member and standalone functions can be inline

common practice:

place the implementation of the inline function

into the header file
only small functions are eligible as inline

the compiler may completely ignore your request

2013-2015 Margit ANTAL

OOP: Advanced class features

inline function examples
inline double square(double a){
return a * a;
}
class Value{
int value;
public:
inline int getValue(){ return value; }

};

inline void setValue( int value ){

this->value = value;
}

2013-2015 Margit ANTAL

OOP: Advanced class features

Stack vs. Heap

Heap Dynamic allocation

void draw(){
Point * p = new Point();
p->move(3,3);
//...
}

Stack Automatic allocation

void draw(){
Point p();
p.move(6,6);
//...
}

2013-2015 Margit ANTAL

OOP: Advanced class features

Array of objects
class Point{
int x, y;
public:
Point( int x=0, int y=0);
//...
};

What is the difference between these two arrays?

Point * t1 = new Point[ 4];
t1

Point t1[ 4];

:Point

:Point

:Point

:Point

x: 0
y: 0

x: 0
y: 0

x: 0
y: 0

x: 0
y: 0

2013-2015 Margit ANTAL

OOP: Advanced class features

Array of pointers
Point ** t2 = new Point*[ 4 ];
for(int i=0; i<4; ++i ){
t2[i] = new Point(0,0);
}
for( int i=0; i<4; ++i ){
cout<<*t2[ i ]<<endl;
}
t2

:Point
x: 0
y: 0

:Point
x: 0
y: 0

:Point
x: 0
y: 0

2013-2015 Margit ANTAL

:Point
x: 0
y: 0

OOP: Advanced class features

Static members:

static methods
static data

Functions belonging to a class scope which don't access

object's data can be static

Static methods can't be const methods (they do not access

object's state)

They are not called on specific objects they have no this

pointer

2013-2015 Margit ANTAL

OOP: Advanced class features

Static members

initializing static class member

//Complex.h
class Complex{
public:
Complex(int re=0, int im=0);
static int getNumComplex();
// ...
private:
static int num_complex;
double re, im;
};

instance counter

//Complex.cpp
int Complex::num_complex = 0;
int Complex::getNumComplex(){
return num_complex;
}
Complex::Complex(int re, int im){
this->re = re;
this->im = im;
++num_complex;
}

2013-2015 Margit ANTAL

OOP: Advanced class features

Static method invocation

elegant

Complex z1(1,2), z2(2,3), z3;

cout<<"Number of complexs:"<<Complex::getNumComplex()<<endl;
cout<<"Number of complexes: "<<z1.getNumComplex()<<endl;

non - elegant

2013-2015 Margit ANTAL

OOP: Advanced class features

Complex z1(1,2), z2(2,3), z3;

re: 1
im: 2

num_complex: 3
Only one copy of
the static member

re: 2
im: 3

Each object has

its own re and im

re: 0
im: 0

2013-2015 Margit ANTAL

OOP: Advanced class features

Classes vs. Structs

default access specifier

class: private
struct: public
class: data + methods, can be used polimorphically
struct: mostly data + convenience methods

2013-2015 Margit ANTAL

OOP: Advanced class features

Classes vs. structures

class list{
private:
struct node
{
node *next;
int val;
node( int val=0, node * next=NULL):val(val), next(next){}
};
node * head;
public:
list ();
~list ();
void insert (int a);
};

2013-2015 Margit ANTAL

OOP: Advanced class features

Passing function arguments

by value

by reference

the function works on a copy of the variable

the function works on the original variable, may modify it

by constant reference

the function works on the original variable, may not modify

(verified by the compiler)

2013-2015 Margit ANTAL

OOP: Advanced class features

Passing function arguments

void f1(int x) {x = x +
void f2(int& x) {x = x +
void f3(const int& x) {x
void f4(int *x) {*x = *x
int main(){
int y = 5;
f1(y);
f2(y);
f3(y);
f4(&y);
return 0;
}

passing primitive values

1;}
1;}
= x + 1;}
+ 1;}

2013-2015 Margit ANTAL

OOP: Advanced class features

Passing function arguments

void f1(Point p);
void f2(Point& p);
void f3(const Point& p);
void f4(Point *p);
int main(){
Point p1(3,3);
f1(p1);
f2(p1);
f3(p1);
f4(&p1);
return 0;
}

passing objects
copy constructor will be used on the argument

2013-2015 Margit ANTAL

only const methods of the class can be

invoked on this argument

OOP: Advanced class features

friend functions, friend classes, friend member

functions

friends are allowed to access private members of a class

Use it rarely
operator overloading

2013-2015 Margit ANTAL

OOP: Advanced class features

friend vs. static functions

class Test{
private:
int iValue;
static int sValue;
public:
Test( int in ):iValue( in ){}
void print() const;
static void print( const Test& what );
friend void print( const Test& what );
};

2013-2015 Margit ANTAL

OOP: Advanced class features

friend vs. static functions

int Test :: sValue = 0;

void Test::print() const{

cout<<"Member: "<<iValue<<endl;
}
void Test::print( const Test& what ){
cout<<"Static: "<<what.iValue<<endl;
}
void print( const Test& what ){
cout<<"Friend: "<<what.iValue<<endl;
}
int main() {
Test test( 10 );
test.print();
Test::print( test );
print( test );
}

2013-2015 Margit ANTAL

OOP: Advanced class features

friend class vs. friend member function

class List{
private:
ListElement * head;
public:
bool find( int key );

};

class ListElement{
private:
int key;
ListElement * next;
friend class List;
...
};

class ListElement{
private:
int key;
ListElement * next;
friend class List::find( int key);
...
};

2013-2015 Margit ANTAL

OOP: Advanced class features

Returning a reference to a const object

// version 1
vector<int> Max(const vector<int> & v1, const vector<int> & v2)
{
if (v1.size() > v2.size())
Copy
return v1;
constructor
else
return v2;
invocation
}
// version 2
const vector<int> & Max(const vector<int> & v1, const vector<int> & v2)
{
if (v1.size() > v2.size())
More
return v1;
efficient
else
return v2;
}

The reference should be to

a non-local object
2013-2015 Margit ANTAL

OOP: Advanced class features

Nested classes

the class declared within another class is called a

nested class
usually helper classes are declared as nested

// Version 1
class Queue
{
private:
// class scope definitions
// Node is a nested structure definition local to this class
struct Node {Item item; struct Node * next;};
...
};

2013-2015 Margit ANTAL

OOP: Advanced class features

Nested classes [Prata]

Node visibility!!!

// Version 2
class Queue
{
// class scope definitions
// Node is a nested class definition local to this class
class Node
{
public:
Item item;
Node * next;
Node(const Item & i) : item(i), next(0) { }
};
//...
};

2013-2015 Margit ANTAL

OOP: Advanced class features

Nested classes

a nested class B declared in a private section of a class A:

a nested class B declared in a protected section of a class A:

B is local to class A (only class A can use it)

B can be used both in A and in the derived classes of A

a nested class B declared in a public section of a class A:

B is available to the outside world ( A :: B b;)

2013-2015 Margit ANTAL

OOP: Advanced class features

Features of a well-behaved C++ class

implicit constructor
T :: T(){ }
destructor
T :: ~T(){ }
copy constructor
T :: T( const T& ){ }
assignment operator (see next module)
T :: operator=( const T& ){ }

2013-2015 Margit ANTAL

Module 4
Object-Oriented Programming
Operator overloading

2013-2015 Margit ANTAL

OOP: Operator overloading

Content

Objectives
Types of operators
Arithmetic operators
Increment/decrement
Inserter/extractor operators
assignment operator
index operator
relational and equality operators
conversion operators
2013-2015 Margit ANTAL

OOP: Operator overloading

Objective

To make the class usage easier, more intuitive

the ability to read an object using the extractor operator (>>)

Employee e1; cin >> e;
the ability to write an object using the inserter operator (<<)
Employee e2; cout<<e<<endl;
the ability compare to objects of a given class
cout<< ((e1 < e2) ? "less" : "greater");
Operator overloading: a service to the clients of the class

2013-2015 Margit ANTAL

OOP: Operator overloading

Limitations

You cannot add new operator symbols. Only the existing operators
meaning can be redefined.

Some operators cannot be overloaded:

. (member access in an object)

::(scope resolution operator)

sizeof

?:

You cannot change the arity (the number of arguments) of the operator

You cannot change the precedence or associativity of the operator

2013-2015 Margit ANTAL

OOP: Operator overloading

How to implement?

write a function with the name operator<symbol>

alternatives:

method of your class

global function (usually a friend of the class)

2013-2015 Margit ANTAL

OOP: Operator overloading

There are 3 types of operators:

operators that must be methods (member functions)

operators that must be global functions

they don't make sense outside of a class:

assignment operator: operator=

the left-hand side of the operator is a variable of different type than your class:
operator<<, operator>>

cout << emp;

cout: ostream

emp: Employee

operators that can be either methods or global functions

Gregoire: Make every operator a method unless you must make it a global
function.

2013-2015 Margit ANTAL

OOP: Operator overloading

Choosing argument types:

value vs. reference

Prefer passing-by-reference instead of passing-by-value.
const vs. non const

Prefer const unless you modify it.

Choosing return types

you can specify any return type, however

follow the built-in types rule:

comparison always return bool

arithmetic operators return an object representing the result of the arithmetic

2013-2015 Margit ANTAL

OOP: Operator overloading

The Complex class: Complex.h, Complex.cpp

class TYPES

Complex
-

re: double
im : double

+
+
+
+
+
+
+

Com plex(double, d ouble)

Com plex(Com plex&)
setRe(double ) : void
setIm (double) : voi d
getRe() : dou ble {query}
getIm () : doubl e {query}
print() : void {query}

#include "Complex.h"
#include <iostream>
using namespace std;
Complex::Complex( double re, double im):re( re), im(im) {}
Complex::Complex(const Complex& orig):re( orig.re), im(orig.im){}
void Complex::setRe( double re){this->re = re;}
void Complex::setIm( double im){ this->im = im;}
double Complex::getRe() const{ return this->re;}
double Complex::getIm() const{ return this->im;}
void Complex::print() const{ cout<<re<<"+"<<im<<"i";}

2013-2015 Margit ANTAL

OOP: Operator overloading

Arithmetic operators (member func.)

unary minus
binary minus

Complex Complex::operator-() const{

Complex temp(-this->re, -this->im);
return temp;
}
Complex Complex::operator-( const Complex& z) const{
Complex temp(this->re - z.re, this->im- z.im);
return temp;
}

2013-2015 Margit ANTAL

OOP: Operator overloading

Increment/Decrement operators

postincrement:

int i = 10; int j = i++; // j 10

preincrement:

int i = 10; int j = ++i; // j 11

The C++ standard specifies that the prefix increment and decrement
return an lvalue (left value).

2013-2015 Margit ANTAL

OOP: Operator overloading

Increment/Decrement operators (member func.)

Complex& Complex::operator++(){
//prefix
(this->re)++;
(this->im)++;
Which one is more efficient?
return *this;
Why?
}
Complex Complex::operator++( int ){ //postfix
Complex temp(*this);
(this->re)++;
(this->im)++;
return temp;
}

2013-2015 Margit ANTAL

OOP: Operator overloading

Inserter/Extractor operators (standalone func.)

//complex.h
class Complex {
public:
friend ostream& operator<<( ostream& os, const Complex& c);
friend istream& operator>>( istream& is, Complex& c);
//...
};
//complex.cpp
ostream& operator<<( ostream& os, const Complex& c){
os<<c.re<<"+"<<c.im<<"i";
return os;
}
istream& operator>>( istream& is, Complex& c){
is>>c.re>>c.im;
return is;
}

2013-2015 Margit ANTAL

OOP: Operator overloading

Inserter/Extractor operators

Syntax:
ostream& operator<<( ostream& os, const T& out)
istream& operator>>( istream& is, T& in)

Remarks:

Streams are always passed by reference

Q: Why should inserter operator return an ostream&?
Q: Why should extractor operator return an istream&?

2013-2015 Margit ANTAL

OOP: Operator overloading

Inserter/Extractor operators

Usage:
Complex z1, z2;
cout<<"Read 2 complex number:";
//Extractor
cin>>z1>>z2;
//Inserter
cout<<"z1: "<<z1<<endl;
cout<<"z2: "<<z2<<endl;
cout<<"z1++: "<<(z1++)<<endl;
cout<<"++z2: "<<(++z2)<<endl;

2013-2015 Margit ANTAL

OOP: Operator overloading

Assignment operator

Q: When should be overloaded?

A: When bitwise copy is not satisfactory (e.g. if you have
dynamically allocated memory

when we should implement the copy constructor and the

destructor too).
Ex. our Stack class

Syntax: X& operator=( const X& rhs);

2013-2015 Margit ANTAL

OOP: Operator overloading

Assignment operator (member func.)

Syntax: X& operator=( const X& rhs);

Q: Is the return type necessary?

Analyze the following example code

Complex z1(1,2), z2(2,3), z3(1,1);

z3 = z1;
z2 = z1 = z3;

2013-2015 Margit ANTAL

OOP: Operator overloading

Assignment operator example

Stack& Stack::operator=(const Stack& rhs) {
if (this != &rhs) {
//delete lhs
delete [] this->mElements;
//copy rhs
mCapacity = rhs.mCapacity;
mElements = new double[ mCapacity ];
int nr = rhs.mTop - rhs.mElements;
for (int i = 0; i < nr; ++i) {
mElements[ i ] = rhs.mElements[ i ];
}
mTop = mElements + nr;
}
return *this;
}

2013-2015 Margit ANTAL

OOP: Operator overloading

Assignment operator vs Copy constructor

Complex z1(1,2), z2(3,4); //Constructor
Complex z3 = z1; //Copy constructor
Complex z4(z2);

//Copy constructor

z1 = z2;

//Assignment operator

2013-2015 Margit ANTAL

OOP: Operator overloading

Subscript operator: needed for arrays (member func.)

Suppose you want your own dynamically allocated C-style

array implement your own CArray

#ifndef CARRAY_H
#define CARRAY_H
class CArray{
public:
CArray( int size = 10 );
~CArray();
double& operator[]( int index );
double& operator[]( int index ) const;
protected:
double * mElems;
int mSize;
private:
CArray( const CArray&);
CArray& operator=( const CArray&);
};
#endif /* ARRAY_H */

2013-2015 Margit ANTAL

Provides read-only access

OOP: Operator overloading

Implementation

CArray::CArray( int size ){

if( size < 0 ){
size = 10;
}
this->mSize = size;
this->mElems = new double[ mSize ];
}

double& CArray::operator[](
int index ) const{
if( index <0 || index >= mSize ){
throw out_of_range("");
}
return mElems[ index ];
}

CArray::~CArray(){
if( this->mElems != NULL ){
delete[] mElems;
}
}
double& CArray::operator[]( int index ){
if( index <0 || index >= mSize ){
throw out_of_range("");
}
return mElems[ index ];
}

2013-2015 Margit ANTAL

#include<stdexcept>

OOP: Operator overloading

const vs non-const [] operator

void printArray(const CArray& arr, size_t size) {
for (size_t i = 0; i < size; i++) {
cout << arr[i] << "" ;
// Calls the const operator[] because arr is
// a const object.
}
cout << endl;
}
CArray myArray;
for (size_t i = 0; i < 10; i++) {
myArray[i] = 100;
// Calls the non-const operator[] because
// myArray is a non-const object.
}
printArray(myArray, 10);

2013-2015 Margit ANTAL

OOP: Operator overloading

Non-integral array indices: associative array

( Key, Value )

Ex: Key string, Value double

Homework

2013-2015 Margit ANTAL

OOP: Operator overloading

Relational and equality operators

used for search and sort

the container must be able to compare the stored objects

bool operator ==( const Point& p1, const Point& p2){

return p1.getX() == p2.getX() && p1.getY() == p2.getY();
}
bool operator <( const Point& p1, const Point& p2){
return p1.distance(Point(0,0)) < p2.distance(Point(0,0));
}
set<Point> p;

vector<Point> v; //...
sort(v.begin(), v.end());

2013-2015 Margit ANTAL

OOP: Operator overloading

The function call operator ()

Instances of classes overloading this operator behave as

functions too (they are function objects = function + object)

#ifndef ADDVALUE_H
#define ADDVALUE_H
class AddValue{
int value;
public:
AddValue( int inValue = 1);
void operator()( int& what );
};
#endif /* ADDVALUE_H */

#include "AddValue.h"
AddValue::AddValue( int inValue ){
this->value = inValue;
}
void AddValue::operator()( int& what ){
what += this->value;
}

2013-2015 Margit ANTAL

OOP: Operator overloading

The function call operator

AddValue func(2);
int array[]={1, 2, 3};
for( int x : array ){
func(x);
}
for( int x: array ){
cout <<x<<endl;
}

2013-2015 Margit ANTAL

OOP: Operator overloading

Function call operator

used frequently for defining sorting criterion

struct EmployeeCompare{
bool operator()( const Employee& e1, const Employee& e2){
if( e1.getLastName() == e2.getLastName())
return e1.getFirstName() < e2.getFirstName();
else
return e1.getLastName() < e2.getLastName();
};

2013-2015 Margit ANTAL

OOP: Operator overloading

Function call operator

sorted container

set<Employee, EmployeeCompare> s;
Employee e1; e1.setFirstName("Barbara");
e1.setLastName("Liskov");
Employee e2; e2.setFirstName("John");
e2.setLastName("Steinbeck");
Employee e3; e3.setFirstName("Andrew");
e3.setLastName("Foyle");
s.insert( e1 ); s.insert( e2 ); s.insert( e3 );
for( Employee emp : s){
emp.display();
}

2013-2015 Margit ANTAL

OOP: Operator overloading

Sorting elements of a given type:

A. override operators: <, ==

B. define a function object containing the comparison
Which one to use?

Q: How many sorted criteria can be defined using method A?

Q: How many sorted criteria can be defined using method B?

2013-2015 Margit ANTAL

OOP: Operator overloading

Writing conversion operators

class Complex{
public:
operator string() const;
//
};
Complex::operator string() const{
stringstream ss;
ss<<this->re<<"+"<<this->im<<"i";
string s;
ss>>s;
return s;
}
//usage
Complex z(1, 2), z2;
string a = z;
cout<<a<<endl;

2013-2015 Margit ANTAL

OOP: Operator overloading

After templates

Overloading operator *
Overloading operator

2013-2015 Margit ANTAL

OOP: Review

Find all possible errors or shortcommings!

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)

class Array {
public:
Array (int n) : rep_(new int [n]) { }
Array (Array& rhs) : rep_(rhs.rep_) { }
~Array () { delete rep_; }
Array& operator = (Array rhs) { rep_= rhs.rep_;
int& operator [] (int n) { return &rep_[n]; }
private:
int * rep_;
}; // Array

Source: http://www.cs.helsinki.fi/u/vihavain/k13/gea/exer/exer_2.html

2013-2015 Margit ANTAL

Solution required!

It is given the following program!

#include <iostream>
int main(){
std::cout<<Hello<<\n;
return 0;
}
Modify the program without modifying the main function so that the output of
the program would be:
Start
Hello
Stop

2013-2015 Margit ANTAL

Singleton Design Pattern

#include <string>
class Logger{
public:
static Logger* Instance();
bool openLogFile(std::string logFile);
void writeToLogFile();
bool closeLogFile();
private:
Logger(){}; // Private so that it can not be called
Logger(Logger const&){}; // copy constructor is private
Logger& operator=(Logger const&){};// assignment operator
static Logger* m_pInstance;
};

http://www.yolinux.com/TUTORIALS/C++Singleton.html

2013-2015 Margit ANTAL

is private

Singleton Design Pattern

static
class Framewor...

Singleton
-

uniqueInstance
singletonData

Instance()
return unique Instance
SingletonOperation()
GetSingletonData ()

+
+

static

Ensure that only one instance of a class is created.

Provide a global point of access to the object.

2013-2015 Margit ANTAL

Module 5
Object-Oriented Programming
Public Inheritance

2013-2015 Margit ANTAL

OOP: Inheritance

Inheritance

is-a relationship - public inheritance

protected access
virtual member function
early (static) binding vs. late (dynamic) binding
abstract base classes
pure virtual functions
virtual destructor

2013-2015 Margit ANTAL

class cppinheritance

Employee

OOP: Inheritance

public inheritance

is-a relationship
base class: Employee
derived class: Manager
You can do with inheritance

add data

ex. department
ex. getDepartment(), setDepartment()

modify methods' behavior

firstNam e: stri ng
lastNam e: stri ng
salary: do uble

+
+
+
+
+
+
+
+

Em ployee(strin g, string, doubl e)

getFirstNam e () : string {query}
setFirstNam e(string) : void
getLastNam e () : string {query}
setLastNam e(string) : void
getSala ry() : double {qu ery}
setSalary(d ouble) : void
print(o stream&) : void {query}

Manager

add functionality

ex. print()

2013-2015 Margit ANTAL

depa rtm e nt: string

+
+
+
+
+

M anager()
M anager(string, string, do uble, string)
setDepa rtm ent(string) : void
getDe partm ent() : string {query}
print(ostream &) : void {query}

OOP: Inheritance

protected access

base class's private members can not be accessed in a

derived class
base class's protected members can be accessed in a
derived class
base class's public members can be accessed from
anywhere

2013-2015 Margit ANTAL

OOP: Inheritance

public inheritance
class Employee{
public:
Employee(string firstName = "", string lastName = "",
double salary = 0.0) : firstName(firstName),
lastName(lastName),
salary(salary) {
}
//...
};
class Manager:public Employee{
string department;
public:
Manager();
Manager( string firstName, string lastName, double salary,
string department );
//...
};

2013-2015 Margit ANTAL

OOP: Inheritance

Derived class's constructors

Manager::Manager(){
}

Employee's constructor invocation Default constructor can be invoked implicitly

2013-2015 Margit ANTAL

OOP: Inheritance

Derived class's constructors

Manager::Manager(){
}

Employee's constructor invocation Default constructor can be invoked implicitly

Manager::Manager(string firstName, string lastName, double salary,

string department): Employee(firstName, lastName, salary),
department(department){
}

base class's constructor invocation constructor initializer list

arguments for the base class's constructor are specified in the definition of a derived class's constructor

2013-2015 Margit ANTAL

OOP: Inheritance

How are derived class's objects constructed?

bottom up order:
base class constructor invocation
member initialization
derived class's constructor block
destruction
in the opposite order

2013-2015 Margit ANTAL

Manager

Employee

OOP: Inheritance

Method overriding

Employee {
class Employee{
public:
virtual void print( ostream&) const;
};
class Manager:public Employee{
public:
};

virtual void print(ostream&) const;

2013-2015 Margit ANTAL

OOP: Inheritance

Method overriding

class Employee {
public:
virtual void print( ostream&) const;
};
void Employee::print(ostream& os ) const{
os<<this->firstName<<" "<<this->lastName<<" "<<this->salary;
}
class Manager:public Employee{
public:
virtual void print(ostream&) const;
};
void Manager::print(ostream& os) const{
Employee::print(os);
os<<" "<<department;
}

2013-2015 Margit ANTAL

OOP: Inheritance

Method overriding - virtual functions

non virtual functions are bound statically

compile time
virtual functions are bound dynamically
run time

2013-2015 Margit ANTAL

OOP: Inheritance

Polymorphism

void printAll( const vector<Employee*>& emps ){

for( int i=0; i<emps.size(); ++i){
emps[i]-> print(cout);
cout<<endl;
}
}
int main(int argc, char** argv) {
vector<Employee*> v;
Employee e("John", "Smith", 1000);
v.push_back(&e);
Manager m("Sarah", "Parker", 2000, "Sales");
v.push_back(&m);
cout<<endl;
Output:
printAll( v );
John Smith 1000
return 0;
Sarah Parker 2000 Sales
}

2013-2015 Margit ANTAL

OOP: Inheritance

Polymorphism

a type with virtual functions is called a polymorphic type

polymorphic behavior preconditions:
the member function must be virtual
objects must be manipulated through
pointers or
references

Employee :: print( os )

static binding no

polymorphism

2013-2015 Margit ANTAL

OOP: Inheritance

Polymorphism Virtual Function Table

class Employee{
public:
virtual void print(ostream&) const;
//...
};

e1

vtbl

class Manager:public Employee{

virtual void print(ostream&) const;
//...
};
Employee e1, e2;
Manager m1, m2;

e2
Discussion!!!

firstName:
lastName:
salary:0.0

Employee::print

firstName:
lastName:
salary:0.0

vtbl

Employee * pe;
pe = &e1; pe->print();//???
pe = &m2; pe->print();//???

2013-2015 Margit ANTAL

firstName:
firstName:
lastName:
lastName:
m1salary:0.0
salary:0.0
department
department
vtbl
vtbl

Manager::print

m2

firstName:
lastName:
salary:0.0
department

vtbl

OOP: Inheritance

Abstract classes

used for representing abstract concepts

used as base class for other classes
no instances can be created

2013-2015 Margit ANTAL

OOP: Inheritance

Abstract classes pure virtual functions

class Shape{ // abstract class
public:
virtual void rotate(int) = 0;
virtual void draw() = 0;
// ...
};

// pure virtual function

// pure virtual function

Shape s; //???

2013-2015 Margit ANTAL

OOP: Inheritance

Abstract classes pure virtual functions

class Shape{ // abstract class
public:
virtual void rotate(int) = 0;
virtual void draw() = 0;
// ...
};

// pure virtual function

// pure virtual function

Shape s; //Compiler error

2013-2015 Margit ANTAL

OOP: Inheritance

Abstract class concrete class

class Point{ /* ... */ };
class Circle : public Shape {
public:
void rotate(int);
void draw();
Circle(Point p, int r) ;
private:
Point center;
int radius;
};

// override Shape::rotate
// override Shape::draw

2013-2015 Margit ANTAL

OOP: Inheritance

Abstract class abstract class

class Polygon : public Shape{
public:
// draw() and rotate() are not overridden
};

Polygon p; //Compiler error

2013-2015 Margit ANTAL

OOP: Inheritance

Virtual destructor

Every class having at least one virtual function should

have virtual destructor. Why?
class X{
public:
// ...
~X();
};

2013-2015 Margit ANTAL

OOP: Inheritance

Virtual destructor
void deleteAll( Employee ** emps, int size){
for( int i=0; i<size; ++i){
delete emps[ i ];
Which destructor is invoked?
}
delete [] emps;
}
// main
Employee ** t = new Employee *[ 10 ];
for(int i=0; i<10; ++i){
if( i % 2 == 0 )
t[ i ] = new Employee();
else
t[ i ] = new Manager();
}
deleteAll( t, 10);

2013-2015 Margit ANTAL

Module 6
Object-Oriented Programming
Object relationships

2013-2015 Margit ANTAL

OOP: Object relationships

Content

The is-a relationship

The has-a relationship
Private inheritance
Multiple inheritance
...

2013-2015 Margit ANTAL

OOP: Object relationships

Super

The is-a relationship Client's view (1)

works in only one direction:

every Sub object is also a Super one
but Super object is not a Sub

void foo1( const Super& s );

void foo2( const Sub& s);
Super super;
Sub sub;
foo1(super);
foo1(sub);
foo2(super);
foo2(sub);

//OK
//OK
//NOT OK
//OK

2013-2015 Margit ANTAL

Sub

OOP: Object relationships

Super

The is-a relationship Client's view (2)

class Super{
public:
virtual void method1();
};
class Sub : public Super{
public:
virtual void method2();
};

Super * p= new Super();

p->method1(); //OK
p = new Sub();
p->method1(); //OK
p->method2(); //NOT OK
((Sub *)p)->method2();//OK

2013-2015 Margit ANTAL

Sub

OOP: Object relationships

The is-a relationship Sub-classs view

Super

the Sub class augments the Super class by

adding additional methods
the Sub class may override the Super class methods
the subclass can use all the public and
protected members of a superclass.

2013-2015 Margit ANTAL

Sub

OOP: Object relationships

The is-a relationship: preventing inheritance C++11

final classes cannot be extended

class Super final

{
};

2013-2015 Margit ANTAL

OOP: Object relationships

The is-a relationship: a client's view of overridden methods(1)

polymorphism

Super super;
super.method1(); //Super::method1()

class Super{
public:
virtual void method1();
};
class Sub : public Super{
public:
virtual void method1();
};

Sub sub;
sub.method1();

//Sub::method1()

Super& ref =super;

ref.method1();
//Super::method1();
ref = sub;
ref.method1();

//Sub::method1();

Super* ptr =&super;

ptr->method1(); //Super::method1();
ptr = &sub;
ptr->method1();

2013-2015 Margit ANTAL

//Sub::method1();

OOP: Object relationships

The is-a relationship: a client's view of overridden methods(2)

object slicing

class Super{
public:
virtual void method1();
};
class Sub : public Super{
public:
virtual void method1();
};

Sub sub;
Super super = sub;
super.method1(); // Super::method1();

Sub
Super

Super

super

sub

2013-2015 Margit ANTAL

OOP: Object relationships

The is-a relationship: preventing method overriding C++11

class Super{
public:
virtual void method1() final;
};
class Sub : public Super{
public:
virtual void method1(); //ERROR
};

2013-2015 Margit ANTAL

OOP: Object relationships

Inheritance for polymorphism

www.javatutorialhub.com

2013-2015 Margit ANTAL

OOP: Object relationships

The has-a relationship

Window

Button

2013-2015 Margit ANTAL

OOP: Object relationships

Implementing the has-a relationship

An object A has an object B

class B;

class B;

class B;

class A{
private:
B b;
};

class A{
private:
B* b;
};

class A{
private:
B& b;
};

2013-2015 Margit ANTAL

OOP: Object relationships

Implementing the has-a relationship

An object A has an object B

strong containment (composition)
class B;

A anObject;

class A{
private:
B b;
};

anObject: A
b: B

2013-2015 Margit ANTAL

OOP: Object relationships

Implementing the has-a relationship

An object A has an object B

weak containment (aggregation)

class B;
class A{
private:
B& b;
public:
A( const B& pb):b(pb){}
};

B bObject;
A aObject1(bObject);
A aObject2(bObject);
bObject: B

aObject1: A

2013-2015 Margit ANTAL

aObject2: A

OOP: Object relationships

Implementing the has-a relationship

An object A has an object B

weak containment

strong containment

class B;

class B;

class A{
private:
B* b;
public:
A( B* pb):b( pb ){}
};

class A{
private:
B* b;
public:
A(){
b = new B();
}
~A(){
delete b;
}
};

2013-2015 Margit ANTAL

OOP: Object relationships

Implementing the has-a relationship

An object A has an object B

weak containment
class B;
class A{
private:
B* b;
public:
A( B* pb):b( pb ){}
};

Usage:
B bObject;
A aObject1(&bObject);
A aObject2(&bObject);

bObject: B

aObject1: A

2013-2015 Margit ANTAL

aObject2: A

OOP: Object relationships

Implementing the has-a relationship

An object A has an object B

strong containment
class B;

Usage:
A aObject;

class A{
private:
B* b;
public:
A(){
b = new B();
}
~A(){
delete b;
}
};

anObject: A
b: B *

2013-2015 Margit ANTAL

OOP: Object relationships

Combining the is-a and the has-a relationships

class Class Mo...

Component
+
+
+
+

Client

1..*
Operation()
Add() : Component
Rem ove() : Com ponent
GetChild() : Com ponent

Leaf
+

Operation()

Composite
+

+
+
+

Operation()
forall g in children
g.Operation();
Add() : Com ponent
Rem ove() : Com ponent
GetChild() : Com ponent

2013-2015 Margit ANTAL

-children

Composite Design Pattern

class Class Mo...

Component
+
+
+
+

Client

1..*
O peration()
Add() : Component
Rem ove() : Com ponent
G etChild() : Com ponent

Leaf
+

Operation()

Composite
+

+
+
+

Operation()
forall g in children
g.Operation();
Add() : Com ponent
Rem ove() : Com ponent
GetChild() : Com ponent

-children

Compose objects into tree structures to represent part-whole

hierarchies.
Lets clients treat individual objects and composition of objects
uniformly.

2013-2015 Margit ANTAL

Composite Design Pattern

Examples:

Menu MenuItem: Menus that contain menu items, each of which could be a
menu.

Container Element: Containers that contain Elements, each of which could be a

Container.

GUI Container GUI component: GUI containers that contain GUI components,
each of which could be a container

Source: http://www.oodesign.com/composite-pattern.html

2013-2015 Margit ANTAL

Private Inheritance

another possibility for has-a relationship

public

public

Base class

Base class

public
inheritance

private
inheritance

Derived class

Derived class

Derived class inherits the

base class behavior

public

private

Derived class hides the

base class behavior

2013-2015 Margit ANTAL

Private Inheritance
template <typename T>
class MyStack : private vector<T> {
Why is public inheritance
public:
in this case dangerous???
void push(T elem) {
this->push_back(elem);
}
bool isEmpty() {
return this->empty();
}
void pop() {
if (!this->empty())this->pop_back();
}
T top() {
if (this->empty()) throw out_of_range("Stack is empty");
else return this->back();
}
};

2013-2015 Margit ANTAL

Non-public Inheritance

it is very rare;
use it cautiously;
most programmers are not familiar with it;

2013-2015 Margit ANTAL

What does it print?

class Super{
public:
Super(){}
virtual void someMethod(double d) const{
cout<<"Super"<<endl;
}
};
class Sub : public Super{
public:
Sub(){}
virtual void someMethod(double d){
cout<<"Sub"<<endl;
}
};
Sub sub; Super super;
Super& ref = sub;ref.someMethod(1);
ref = super; ref.someMethod(1);

2013-2015 Margit ANTAL

What does it print?

class Super{
public:
Super(){}
virtual void someMethod(double d) const{
cout<<"Super"<<endl;
}
creates a new method, instead
};
of overriding the method
class Sub : public Super{
public:
Sub(){}
virtual void someMethod(double d){
cout<<"Sub"<<endl;
}
};
Sub sub; Super super;
Super& ref = sub;ref.someMethod(1);
ref = super; ref.someMethod(1);

2013-2015 Margit ANTAL

The override keyword C++11

class Super{
public:
Super(){}
virtual void someMethod(double d) const{
cout<<"Super"<<endl;
}
};
class Sub : public Super{
public:
Sub(){}
virtual void someMethod(double d) const override{
cout<<"Sub"<<endl;
}
};
Sub sub; Super super;
Super& ref = sub;ref.someMethod(1);
ref = super; ref.someMethod(1);

2013-2015 Margit ANTAL

OOP: Object relationships

Multiple inheritance

2013-2015 Margit ANTAL

class Class Mo...

Jatekos
Jatek
Logika
-

han yS zi m bol um : int

tab la: T ab la*

+
+
+

jate kV ege() : bo ol
Log ika(T ab la*, int)
nye roE(Jatekos*, int, int) : b ool

-logika

hanySzim bol um : int

jatekos: vector<Jatekos*>
logi ka: Logika*
tabl a: T abl a*

+
+
+
+

addJate kos(string, ch ar) : void

Jate k(in t, int, in t)
~Jatek()
jatszm a() : vo id

-tab la
-tabla

Tabla
-

cella k: char ([ M A X ][ M AX ])
coun ter: int
oszlo p: i nt
sor: int

+
+
+
+
+
+
+
+
+

getCella(int, in t) : ch ar
getCounter() : i nt
getO szlop() : int {que ry}
getS or() : int {q uery}
printT abla(o stre am & ) : void {query}
setCella (int, int, char) : void
T abla(int, in t)
torle s() : void
uresE (in t, int) : bool

frie nd
+ operator<<(ostream & , T abla &) : ostre am &

2013-2015 Margit ANTAL

n ev: strin g
szim bo lum : ch ar

+
+
+
+
+
+

g etNev() : string {que ry}

g etS zim bolu m () : char {que ry}
Jate kos(string, cha r)
l ep(i nt, i nt, T abl a*) : bo ol
setNev(char*) : voi d
setS zim bolum (char) : void

fri end
+ o perator<<(ostream & , Jateko s& ) : ostream &

Module 7
Generic Programming: Templates

2013-2015 Margit ANTAL

Outline

Templates

Class template
Function template
Template metaprogramming

2013-2015 Margit ANTAL

Templates

2013-2015 Margit ANTAL

Templates

http://www.stroustrup.com/

2013-2015 Margit ANTAL

Templates

Allow generic programming

to write code that can work with all kind of objects

template programmer's obligation: specify the
requirements of the classes that define these objects
template user's obligation: supplying those operators
and methods that the template programmer requires

2013-2015 Margit ANTAL

Function Template

Template
parameter

Allows writing function families

template<typename T>
const T max(const T& x, const T& y) {
return x < y ? y : x;
}
template<class T>
const T max(const T& x, const T& y) {
return x < y ? y : x;
}

What are the requirements regarding the type T?

2013-2015 Margit ANTAL

Function Template
template<class T>
const T max(const T& x, const T& y) {
return x < y ? y : x;
}

Requirements regarding the type T:

less operator (<)
copy constructor

2013-2015 Margit ANTAL

Function Template
template<class T>
const T max(const T& x, const T& y) {
return x < y ? y : x;
}

Usage:

cout<<max(2, 3)<<endl; // max: T int

string a(alma); string b(korte);
cout<<max(a, b)<<endl; // max: T string
Person p1(John,Kennedy),p2(Abraham, Lincoln);
cout<<max(p1,p2)<<endl;// max: T-> Person

2013-2015 Margit ANTAL

Function Template
template<class T>
void swap(T& x, T& y) {
const T tmp = x;
x = y;
y = tmp;
}

Requirements regarding the type T:

copy constructor
assignment operator

2013-2015 Margit ANTAL

Function Template

Allows writing function families

polymorphism: compile time
How the compiler processes templates?

cout<<max(2, 3)<<endl; // max: T int

cout<<max(2.5, 3.6)<<endl; // max: T double

How many max functions?

Warning: Code bloat!

2013-2015 Margit ANTAL

Function Template

What does it do? [Gregoire]

static const size_t MAGIC = (size_t)(-1);

template <typename T>
size_t Foo(T& value, T* arr, size_t size)
{
for (size_t i = 0; i < size; i++) {
if (arr[i] == value) {
return i;
}
}
return MAGIC;
}

2013-2015 Margit ANTAL

Class Template

Allow writing class families

template<typename T>
class Array {
T* elements;
int size;
public:
explicit Array(const int size);
...
};

2013-2015 Margit ANTAL

Class Template

Template class's method definition

template<typename T>
class Array {
T* elements;
int size;
public:
explicit Array(const int size);
...
};
template<typename T>
Array<T>::Array(const int size):size(size),
elements(new T[size]){
}

2013-2015 Margit ANTAL

Class Template

Template parameters
type template parameters
non-type template parameters

template<typename T>
class Array {
T* elements;
int size;
public:
Array(const int size);
...
};

template<class T, int MAX=100>

class Stack{
T elements[ MAX ];
public:
...
};

2013-2015 Margit ANTAL

Class Template

Distributing Template Code between Files

Normal class:

Person.h interface
Person.cpp implementation

Template class:

interface + implementation go in the same file e. g. Array.h

it can be a .h file
usage: #include Array.h
it can be a .cpp file usage: #include Array.cpp

2013-2015 Margit ANTAL

Class Template+ Function Template

template<class T1,
struct pair {
typedef T1
typedef T2
T1 first;
T2 second;
pair();
pair(const
...
};

class T2>

#include <utility>

first_type;
second_type;

T1& x, const T2& y);

template< class T1, class T2>

pair<T1, T2> make_pair(const T1& x, const T2& y)
{
return pair<T1, T2>(x, y);
}

2013-2015 Margit ANTAL

Advanced Template

template template parameter

template<typename T, typename Container>
class Stack{
Container elements;
public:
void push( const T& e ){
elements.push_back( e );
}
...
};
Usage:
Stack<int, vector<int> > v1;
Stack<int, deque<int> > v2;

2013-2015 Margit ANTAL

Advanced Template

template template parameter

template<typename T, typename Container=vector<T> >
class Stack{
Container elements;
public:
void push( const T& e ){
elements.push_back( e );
}
...
};

2013-2015 Margit ANTAL

Advanced Template

What does it do?

template < typename Container >
void foo( const Container& c, const char * str="")
{
typename Container::const_iterator it;
cout<<str;
for(it = c.begin();it != c.end(); ++it)
cout<<*it<<' ';
cout<<endl;
}

2013-2015 Margit ANTAL

Examples

Implement the following template functions!

template <typename T>
bool linsearch( T* first, T* last, const T& what);
template <typename T>
bool binarysearch( T* first, T* last, const T& what);

2013-2015 Margit ANTAL

More Advanced Template

Template Metaprogramming
template<unsigned int N> struct Fact{
static const unsigned long int
value = N * Fact<N-1>::value;
};
template<> struct Fact<0>{
static const unsigned long int value = 1;
};
// Fact<8> is computed at compile time:
const unsigned long int fact_8 = Fact<8>::value;
int main()
{
cout << fact_8 << endl;
return 0;
}

2013-2015 Margit ANTAL

Module 8
STL Standard Template Library

2013-2015 Margit ANTAL

Alexander Stepanov
https://www.sgi.com/tech/stl/drdobbs-interview.html

2013-2015 Margit ANTAL

Outline

Containers
Algorithms
Iterators

2013-2015 Margit ANTAL

STL General View

library of reusable components

a support for C++ development
based on generic programming

2013-2015 Margit ANTAL

STL General View

Containers Template Class

generalized data structures (you can use them for any

type)
Algorithms Template Function

generalized algorithms (you can use them for almost any

data structure)
Iterators Glue between Containers and Algorithms

specifies a position into a container (generalized pointer)

permits traversal of the container
2013-2015 Margit ANTAL

Basic STL Containers

Sequence containers

Container
adapters

linear arrangement

<vector> <deque> <list>

vector, deque, list
stack, queue, priority_queue
<stack> <queue>

Associative containers

provide fast retrieval of data based on keys

set, multiset, map, multimap

2013-2015 Margit ANTAL

<set> <map>

Sequence Containers

2013-2015 Margit ANTAL

Associative Containers

2013-2015 Margit ANTAL

STL Containers C++11

Sequence containers

<forward-list>
<array> <forward_list>

array (C-style array)

forward_list (singly linked list)

Associative containers

<unordered_set>
<unordered_map>

unordered_set, unordered_multiset (hash table)

unordered_map, unordered_multimap (hash table)

2013-2015 Margit ANTAL

STL Containers

homogeneous:
vector<Person>, vector<Person*>
polymorphism
vector<Person*>
class Person{};
class Employee: public Person{};
class Manager : public Employee{};

2013-2015 Margit ANTAL

STL Containers
vector<Person>
Person

Person

Person

...

2013-2015 Margit ANTAL

homogenous

STL Containers
vector<Person>
Person

Person

Person

homogenous

...

vector<Person *>

homogenous

...

Person

Employee

2013-2015 Margit ANTAL

Manager

heterogenous

The vector container - constructors

vector<T> v;
//empty vector
vector<T> v(n, value);
//vector with n copies of value
vector<T> v(n);
//vector with n copies of default for T

2013-2015 Margit ANTAL

The vector container add new elements

vector<int> v;
for( int i=1; i<=5; ++i){
v.push_back( i );
}

v.begin()

1 2

2013-2015 Margit ANTAL

v.end()

The vector container

vector<int> v( 10 );
cout<<v.size()<<endl;//???
for( int i=0; i<v.size(); ++i ){
cout<<v[ i ]<<endl;
}
for( int i=0; i<10; ++i){
v.push_back( i );
}
cout<<v.size()<<endl;//???
typedef vector<int>::iterator VectIt;
for( VectIt it = v.begin(); it != v.end(); ++it ){
cout<<*it<<endl;
}

2013-2015 Margit ANTAL

The vector container: typical errors

Find the error and correct it!

vector<int> v;
cout<<v.size()<<endl;//???
for( int i=0; i<10; ++i ){
v[ i ] = i;
}
cout<<v.size()<<endl;//???
for( int i=0; i<v.size(); ++i ){
cout<<v[ i ]<<endl;
}

2013-2015 Margit ANTAL

The vector container: capacity and size

vector<int> v;
v.reserve( 10 );
cout << v.size() << endl;//???
cout << v.capacity() << endl;//???

2013-2015 Margit ANTAL

The vector container: capacity and size

vector<int> v;
v.reserve( 10 );
cout << v.size() << endl;//???
cout << v.capacity() << endl;//???
-------------------------------------vector<int> gy( 256 );
ifstream ifs("szoveg.txt"); int c;
while( (c = ifs.get() ) != -1 ){
gy[ c ]++;
}

2013-2015 Margit ANTAL

Purpose?

The vector - indexing

int Max = 100;
vector<int> v(Max);
//???...
for (int i = 0; i < 2*Max; i++) {
cout << v[ i ]<< ;
}
-------------------------------------int Max = 100;
vector<int> v(Max);
for (int i = 0; i < 2*Max; i++) {
cout << v.at( i )<< ;
}

2013-2015 Margit ANTAL

The vector - indexing

int Max = 100;
vector<int> v(Max);
//???...
for (int i = 0; i < 2*Max; i++) {
cout << v[ i ]<< ;
}
-------------------------------------int Max = 100;
vector<int> v(Max);
for (int i = 0; i < 2*Max; i++) {
cout << v.at( i )<< ;
}

out_of_range exception

2013-2015 Margit ANTAL

Efficient

Safe

The list container

doubly linked list

list<int> l;
for( int i=1; i<=5; ++i){
l.push_back( i );
}

l.begin()

l.end()

2013-2015 Margit ANTAL

The deque container

double ended vector

deque<int> l;
for( int i=1; i<=5; ++i){
l.push_front( i );
}

2013-2015 Margit ANTAL

Algorithms - sort
template <class RandomAccessIterator>
void sort ( RandomAccessIterator first,RandomAccessIterator last );

template <class RandomAccessIterator, class Compare>

void sort ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );

what to sort: [first, last)

how to compare the elements:

<

comp
2013-2015 Margit ANTAL

Algorithms - sort
struct Rec {
string name;
string addr;
};
vector<Rec> vr;
//
sort(vr.begin(), vr.end(), Cmp_by_name());
sort(vr.begin(), vr.end(), Cmp_by_addr());

2013-2015 Margit ANTAL

Algorithms - sort
struct Cmp_by_name{
bool operator()(const Rec& a, const Rec& b) const
{
return a.name < b.name;
}
function object

};
struct Cmp_by_addr{

bool operator()(const Rec& a, const Rec& b) const

{
return a.addr < b.addr;
}

};

2013-2015 Margit ANTAL

Strategy Design Pattern

class ceepus_iterator

Context
+

Strategy

+strategy
+

ContextIn terface()

ConcreteStrategyA
+

Algorith m In terface()

Algorith mInterface()

ConcreteStrategyB
+

Algorith m In terface()

ConcreteStrategyC
+

Alg orithm Interface()

Define a family of algorithms, encapsulate each one, and make them

interchangeable.
Strategy lets the algorithm vary independently from clients that use it.

2013-2015 Margit ANTAL

Strategy Design Pattern

sort

class ceepus_iterator

Context
+

Strategy

+strategy
+

ContextIn terface()

ConcreteStrategyA
+

Algorith m In terface()

Algorith mInterface()

ConcreteStrategyB
+

Algorith m In terface()

ConcreteStrategyC
+

Alg orithm Interface()

Define a family of algorithms, encapsulate each one, and make them

interchangeable.
Strategy lets the algorithm vary independently from clients that use it.

2013-2015 Margit ANTAL

Strategy Design Pattern

sort

Context
+

Strategy

+strategy
+

ContextIn terface()

ConcreteStrategyA
+

bool operator()(
const T&,
const T&)

class ceepus_iterator

Algorith m In terface()

Algorith mInterface()

ConcreteStrategyB
+

Algorith m In terface()

ConcreteStrategyC
+

Alg orithm Interface()

Define a family of algorithms, encapsulate each one, and make them

interchangeable.
Strategy lets the algorithm vary independently from clients that use it.

2013-2015 Margit ANTAL

Strategy Design Pattern

sort

bool operator()(
const T&,
const T&)

class ceepus_iterator

Context
+

Strategy

+strategy
+

ContextIn terface()

ConcreteStrategyA
+

Algorith m In terface()

Cmp_by_name

Algorith mInterface()

ConcreteStrategyB
+

Algorith m In terface()

Cmp_by_addr

2013-2015 Margit ANTAL

ConcreteStrategyC
+

Alg orithm Interface()

Iterators

The container manages the contained objects but does

not know about algorithms

The algorithm works on data but does not know the

internal structure of containers

Iterators fit containers to algorithms

2013-2015 Margit ANTAL

Iterator - the glue

int x[]={1,2,3,4,5}; vector<int>v(x, x+5);
int sum1 = accumulate(v.begin(), v.end(), 0);
v.begin()

v.end()

1 2

list<int> l(x, x+5);

double sum2 = accumulate(l.begin(), l.end(), 0);
l.begin()

l.end()

2013-2015 Margit ANTAL

Iterator - the glue

template<class InIt, class T>
T accumulate(InIt first, InIt last, T init)
{
while (first!=last) {
init = init + *first;
++first;
}
return init;
}

2013-2015 Margit ANTAL

The set container

set< Key[, Comp = less<Key>]>

usually implemented as a balanced binary search tree

multiset: allows duplicates

Source:http://www.cpp-tutor.de/cpp/le18/images/set.gif

2013-2015 Margit ANTAL

The set container - usage

#include <set>
set<int> intSet;
set<Person> personSet1;
set<Person, PersonComp> personSet2;

2013-2015 Margit ANTAL

The set container - usage

#include <set>

<

set<int> intSet;
set<Person> personSet1;

set<Person, PersonComp> personSet2;

2013-2015 Margit ANTAL

The set container - usage

<

#include <set>

bool operator<(const Person&, const Person&)

set<int> intSet;

set<Person> personSet1;

set<Person, PersonComp> personSet2;

2013-2015 Margit ANTAL

The set container - usage

<

#include <set>

bool operator<(const Person&, const Person&)

set<int> intSet;

set<Person> personSet1;
struct PersonComp{
bool operator() ( const Person&, const Person& );
};

set<Person, PersonComp> personSet2;

2013-2015 Margit ANTAL

The set container - usage

#include <set>
set<int> mySet;
while( cin >> nr ){
mySet.insert( nr );
}
set<int>::iterator iter;
for (iter=mySet.begin(); iter!=mySet.end(); ++iter){
cout << *iter << endl;
}

2013-2015 Margit ANTAL

The set container - usage

set<int>::iterator iter;
for (iter=mySet.begin(); iter!=mySet.end(); ++iter){
cout << *iter << endl;
}
---------------------------------------------------for( auto& i: mySet ){
cout<<i<<endl;
}

2013-2015 Margit ANTAL

The multiset container - usage

multiset<int> mySet;
size_t nrElements = mySet.count(12);
multiset<int>::iterator iter;

iter = mySet.find(10);
if (iter == mySet.end()){
cout<<"The element does not exist"<<endl;
}

2013-2015 Margit ANTAL

The set container - usage

class PersonCompare;
class Person {
friend class PersonCompare;
string firstName;
string lastName;
int yearOfBirth;
public:
Person(string firstName, string lastName, int yearOfBirth);
friend ostream& operator<<(ostream& os, const Person& person);
};

2013-2015 Margit ANTAL

The set container - usage

class PersonCompare {

function object

public:
enum Criterion { NAME, BIRTHYEAR};
private:

state

Criterion criterion;
public:
PersonCompare(Criterion criterion) : criterion(criterion) {}
bool operator()(const Person& p1, const Person& p2) {
switch (criterion) {
case NAME: //
case BIRTHYEAR: //
}
}
};

2013-2015 Margit ANTAL

behaviour

The set container - usage

set<Person, PersonCompare> s( PersonCompare::NAME);
s.insert(Person("Biro", "Istvan", 1960));
s.insert(Person("Abos", "Gergely", 1986));
s.insert(Person("Gered","Attila", 1986));
---------------------------------------------------for( auto& p: s){
cout << p <<endl;

C++
2011

2013-2015 Margit ANTAL

The set container - usage

set<Person, PersonCompare> s( PersonCompare::NAME);
s.insert(Person("Biro", "Istvan", 1960));
s.insert(Person("Abos", "Gergely", 1986));
s.insert(Person("Gered","Attila", 1986));
---------------------------------------------------for( auto& p: s){
cout << p <<endl;

C++
2011

2013-2015 Margit ANTAL

The map container

map< Key, Value[,cComp = less<Key>]>

usually implemented as a balanced binary tree

map: associative array

multimap: allows duplicates

?
Source: http://www.cpp-tutor.de/cpp/le18/images/map.gif

2013-2015 Margit ANTAL

The map container - usage

#include <map>
map<string,int> products;
products.insert(make_pair("tomato",10));
---------------------------------------------products["cucumber"] = 6;
cout<<products["tomato"]<<endl;

2013-2015 Margit ANTAL

The map container - usage

#include <map>
map<string,int> products;
products.insert(make_pair("tomato",10));
---------------------------------------------products["cucumber"] = 6;
cout<<products["tomato"]<<endl;

2013-2015 Margit ANTAL

Difference between
[ ] and insert!!!

The map container - usage

typedef map<string,int>::iterator MapIt;

for(MapIt it=aruk.begin(); it != aruk.end(); ++it)
{
cout<<(it->first)<<" : "<<(it->second)<<endl;
}
-------------------------------------------------for( auto& i: aruk ){
cout<<(i.first)<<" : "<<(i.second)<<endl;
}

2013-2015 Margit ANTAL

C++
2011

The multimap container - usage

multimap<string, string> cities;
cities.insert(make_pair("HU", "Budapest"));
cities.insert(make_pair("HU", "Szeged"));
cities.insert(make_pair("RO", "Seklerburg"));
cities.insert(make_pair("RO", "Neumarkt"));
cities.insert(make_pair("RO", "Hermannstadt"));
typedef multimap<string, string>::iterator MIT;
pair<MIT, MIT> ret = cities.equal_range("HU");
for (MIT it = ret.first; it != ret.second; ++it)
cout << (*it).first <<"\t"<<(*it).second<<endl;
}

2013-2015 Margit ANTAL

The multimap container - usage

multimaps do not provide
operator[ ]
Why???

multimap<string, string> cities;

cities.insert(make_pair("HU", "Budapest"));
cities.insert(make_pair("HU", "Szeged"));
cities.insert(make_pair("RO", "Seklerburg"));
cities.insert(make_pair("RO", "Neumarkt"));
cities.insert(make_pair("RO", "Hermannstadt"));

typedef multimap<string, string>::iterator MIT;

pair<MIT, MIT> ret = cities.equal_range("HU");
for (MIT it = ret.first; it != ret.second; ++it)
cout << (*it).first <<"\t"<<(*it).second<<endl;
}

2013-2015 Margit ANTAL

The set/map container - removal

void erase ( iterator position );
size_type erase ( const key_type& x );
void erase ( iterator first, iterator last );

2013-2015 Margit ANTAL

The set pointer key type

Output??
set<string *> allatok;
allatok.insert(new string("majom"));
allatok.insert(new string("szarvas"));
allatok.insert(new string("kutya"));
allatok.insert(new string("bka"));
for( auto i: allatok ){
cout<<*i<<endl;
}

2013-2015 Margit ANTAL

The set pointer key type

Corrected
struct StringComp{
bool operator()(const string* s1,
const string * s2){
return *s1 < *s2;
}
};
set<string*, StringComp> s;
s.insert( new string("alma"));
s.insert( new string("szilva"));
s.insert( new string("dio"));
s.insert( new string("mogyoro"));
------------------------------------------------------------------for( auto i: allatok ){
cout<<*i<<endl;
}

2013-2015 Margit ANTAL

Hash Tables

collision

http://web.eecs.utk.edu/~huangj/CS302S04/notes/extendibleHashing.htm

2013-2015 Margit ANTAL

Hash Tables
Collision resolution by chaining

Source: http://integrator-crimea.com/ddu0065.html

2013-2015 Margit ANTAL

Unordered Associative Containers - Hash Tables

unordered_set
unordered_multiset
unordered_map
unordered_multimap

C++
2011

2013-2015 Margit ANTAL

Unordered Associative Containers

The STL standard does not specify which collision

handling algorithm is required

most of the current implementations use linear chaining

a lookup of a key involves:

a hash function call h(key) calculates the index in the

hash table
compares key with other keys in the linked list

2013-2015 Margit ANTAL

Hash Function

perfect hash: no collisions

lookup time: O(1) - constant

there is a default hash function for each STL hash

container

2013-2015 Margit ANTAL

The unordered_map container

template <class Key, class T,
class Hash = hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc= std::allocator<pair<const Key, T>>>
class unordered_map;
Template parameters:

Key key type

T value type

Hash hash function type

Pred equality type

2013-2015 Margit ANTAL

The unordered_set container

template <class Key,
class Hash = hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc= std::allocator<pair<const Key, T>>>
class unordered_set;
Template parameters:

Key key type

Hash hash function type

Pred equality type

2013-2015 Margit ANTAL

Problem

Read a file containing double numbers. Eliminate the

duplicates.

Solutions???

2013-2015 Margit ANTAL

Solutions

vector<double> + sort + unique

set<double>

unordered_set<double>

Which is the best? Why?

What are the differences?

2013-2015 Margit ANTAL

Elapsed time

#include <chrono>

auto begin =chrono::high_resolution_clock::now();

//Code to benchmark
auto end =

chrono::high_resolution_clock::now()

cout <<chrono::duration_cast<std::chrono::nanoseconds>
(end-begin).count()
<< "ns" << endl;

2013-2015 Margit ANTAL

class Class Mo...

RandomNumbers

SetRandomNumbers

size: int

+
+
+

Random Num bers(int)

generate() : voi d
getSize() : int

UnorderedSetRandomNumbers

VectorRandomNumbers

num bers: set<dou ble>

num bers: uno rdered_set<do uble>

num bers: vector<d ouble>

+
+
+

SetRandom Num bers(int)

generate() : vo id
getSize() : int

+
+
+

Unordered SetRandom Num bers(int)

generate () : void
getSize() : in t

+
+
+

VectorRandom Num bers(int)

generate () : void
getSize() : in t

2013-2015 Margit ANTAL

Ellapsed time
Container

Time (mean)

vector

1.38 sec

set

3.04 sec

unordered_set

1.40 sec

2013-2015 Margit ANTAL

Which container to use?

implement a PhoneBook, which:

stores names associated with their phone numbers;

names are unique;
one name can have multiple phone numbers
associated;
provides O(1) time search;

2013-2015 Margit ANTAL

Which container to use?

Usage:
PhoneBook pbook;
pbook.addItem("kata","123456");
pbook.addItem("timi","444456");
pbook.addItem("kata","555456");
pbook.addItem("kata","333456");
pbook.addItem("timi","999456");
pbook.addItem("elod","543456");
cout<<pbook<<endl;

2013-2015 Margit ANTAL

unordered_map: example
class PhoneBook{
unordered_map<string, vector<string> > book;
public:
void addItem( string name, string phone);
void removeItem( string name, string phone);
vector<string> findItem( string name );
friend ostream& operator<<( ostream& os,
const PhoneBook& book);
};

2013-2015 Margit ANTAL

unordered_map: example
typedef unordered_map<string, vector<string> >::iterator Iterator;

void PhoneBook::addItem( string name, string phone){

Iterator it = this->book.find( name );
if( it != book.end() ){
it->second.push_back( phone );
}else{
vector<string> phones;
phones.push_back(phone);
book.insert( make_pair(name, phones ));
}
}

2013-2015 Margit ANTAL

unordered_map: example
typedef unordered_map<string, vector<string> >::iterator Iterator;

void PhoneBook::addItem( string name, string phone){

Iterator it = this->book.find( name );
if( it != book.end() ){
vector<string> phones = it->second;
phones.push_back( phone );
}else{
vector<string> phones;
phones.push_back(phone);
book.insert( make_pair(name, phones ));
}
}

2013-2015 Margit ANTAL

Find the error and

correct it!

unordered_map: example
typedef unordered_map<string, vector<string> >::iterator Iterator;

void PhoneBook::addItem( string name, string phone){

Iterator it = this->book.find( name );
if( it != book.end() ){
vector<string>& phones = it->second;
phones.push_back( phone );
}else{
vector<string> phones;
phones.push_back(phone);
book.insert( make_pair(name, phones ));
}
}

2013-2015 Margit ANTAL

phone will be
inserted into the
map

C++/Java
C++

Java

Objects

X x;
X * px = new X();

X x = new X();

Parameter passing

void
void
void
void

run-time binding

only for virtual

functions

for each function (except

static functions)

memory management

explicit

implicit (garbage collection)

multiple inheritance

yes

no

f(
f(
f(
f(

X x );
void f( X x );
//pass through reference
X * px);
X& rx);
const X&rx);

2013-2015 Margit ANTAL

Algorithms

2013-2015 Margit ANTAL

Algorithms

The STL separates the data (containers) from the

functionality (algorithms)

only partial separation:

OOP encapsulates data and functionality

data + functionality = object

2013-2015 Margit ANTAL

Algorithms why separation?

STL principles:

algorithms and containers are independent

(almost) any algorithm works with (almost) any container

iterators mediate between algorithms and containers

provides a standard interface to traverse the elements of

a container in sequence

2013-2015 Margit ANTAL

Algorithms
Which one should be used?
set<int> s;
set<int>::iterator it = find(s.begin(), s.end(), 7);
if( it == s.end() ){
//Unsuccessful
}else{
//Successful
}
set<int> s;
set<int>::iterator it = s.find(7);
if( it == s.end() ){
//Unsuccessful
}else{
//Successful
}

2013-2015 Margit ANTAL

Algorithms
Which one should be used?

O(n)

set<int> s;
set<int>::iterator it = find(s.begin(), s.end(), 7);
if( it == s.end() ){
//Unsuccessful
}else{
//Successful
}
set<int> s;
set<int>::iterator it = s.find(7);
if( it == s.end() ){
//Unsuccessful
}else{
//Successful
}

O(log n)
2013-2015 Margit ANTAL

Algorithm categories

Utility algorithms

Non-modifying algorithms

Search algorithms

Numerical Processing algorithms

Comparison algorithms

Operational algorithms

Modifying algorithms

Sorting algorithms

Set algorithms

2013-2015 Margit ANTAL

Utility Algorithms

min_element()

max_element()

minmax() C++11

swap()

2013-2015 Margit ANTAL

Non-modifying algorithms
Search algorithms

find(), find_if(), find_if_not(), find_first_of()

binary_search()

lower_bound(), upper_bound(), equal_range()

all_of(), any_of(), none_of()

...

2013-2015 Margit ANTAL

Non-modifying algorithms
Search algorithms - Example
bool isEven (int i) { return ((i%2)==0); }

typedef vector<int>::iterator VIT;

int main () {
vector<int> myvector={1,2,3,4,5};
VIT it= find_if (myvector.begin(), myvector.end(), isEven);
cout << "The first even value is " << *it << '\n';
return 0;

auto

2013-2015 Margit ANTAL

Non-modifying algorithms
Numerical Processing algorithms

count(), count_if()

accumulate()

...

2013-2015 Margit ANTAL

Non-modifying algorithms
Numerical Processing algorithms - Example
bool isEven (int i) { return ((i%2)==0); }
int main () {
vector<int> myvector={1,2,3,4,5};
int n = count_if (myvector.begin(), myvector.end(), isEven);
cout << "myvector contains " << n << " even values.\n";
return 0;

[ ] (int i){ return i %2 == 0; }

2013-2015 Margit ANTAL

Non-modifying algorithms
Comparison algorithms

equal()

mismatch()
lexicographical_compare()

2013-2015 Margit ANTAL

Non-modifying algorithms
Comparison algorithms - Example
// 'strange alphabet: 'a' ->3, 'b'->1, c->'2'
// abc >bca
map<char, int> order;
// Compares two characters based on the strange order
bool compChar( char c1, char c2 ){
return order[c1]<order[c2];
}
// Compares two strings based on the strange order
bool compString(const string& s1, const string& s2){
return lexicographical_compare(
s1.begin(), s1.end(), s2.begin(), s2.end(), compChar);
}

2013-2015 Margit ANTAL

Non-modifying algorithms
Operational algorithms

for_each()
void doubleValue( int& x){
x *= 2;
}
vector<int> v ={1,2,3};
for_each(v.begin(), v.end(), doubleValue);

2013-2015 Margit ANTAL

Non-modifying algorithms
Operational algorithms

for_each()
void doubleValue( int& x){
x *= 2;
}
vector<int> v ={1,2,3};
for_each(v.begin(), v.end(), doubleValue);
for_each(v.begin(), v.end(), []( int& v){ v *=2;});

2013-2015 Margit ANTAL

Modifying algorithms

copy(), copy_backward()
move(), move_backward()

fill(), generate()

unique(), unique_copy()
rotate(), rotate_copy()

next_permutation(), prev_permutation()

nth_element() ...

C++11

2013-2015 Margit ANTAL

Modifying algorithms
Permutations
void print( const vector<int>& v){
for(int i=0; i<v.size(); ++i){
cout<<v[ i]<<"\t";
}
cout << endl;
}
int main(){
vector<int> v ={1,2,3};
print( v );
while( next_permutation(v.begin(), v.end())){
print( v );
}
return 0;
}

2013-2015 Margit ANTAL

Iterators

2013-2015 Margit ANTAL

Outline

Iterator Design Pattern

Iterator Definition
Iterator Categories
Iterator Adapters

2013-2015 Margit ANTAL

Iterator Design Pattern

class Framewor...

Iterator

Aggregate
+

CreateIterator()

ConcreteAggregate
+

+
+
+
+

First()
Next()
IsDone()
CurrentItem()

ConcreteIterator

CreateIterato r()
return new
ConcretIterator(this)

Provide a way to access the elements of an aggregate object sequentially

without exposing its underlying representation.
The abstraction provided by the iterator pattern allows you to modify the
2013-2015 Margit ANTAL
collection implementation without
making any change

Iterator Design Pattern - Java

class Framewor...

java.util.Iterator

java.util.Collection
Iterator

Aggregate
+

CreateIterator()

+
+
+
+

First()
Next()
IsDone()
CurrentItem()

java.util.ListIterator

java.util.LinkedList
ConcreteAggregate
+

ConcreteIterator

CreateIterato r()
return new
ConcretIterator(this)

2013-2015 Margit ANTAL

Iterator Design Pattern - C++

<iterator>
class iterator

class Framewor...

Iterator

Aggregate
+

CreateIterator()

+
+
+
+

First()
Next()
IsDone()
CurrentItem()

list<T>::iterator

list<T>
ConcreteAggregate
+

ConcreteIterator

CreateIterato r()
return new
ConcretIterator(this)

2013-2015 Margit ANTAL

Definition

Each container provides an iterator

Iterator smart pointer knows how to
iterate over the elements of that specific
container
C++ containers provides iterators a common
iterator interface

2013-2015 Margit ANTAL

Base class
template <class Category, class T, class
Distance = ptrdiff_t,
class Pointer = T*, class
Reference = T&>
struct iterator {
typedef T
value_type;
typedef Distance difference_type;
typedef Pointer
pointer;
typedef Reference reference;
typedef Category iterator_category;
};
does not provide any of the functionality an iterator is expected to have.

2013-2015 Margit ANTAL

Iterator Categories

Input Iterator
Output Iterator
Forward Iterator
Bidirectional Iterator
Random Access Iterator

2013-2015 Margit ANTAL

Iterator Categories

Input Iterator: read forward, object=*it; it++;

Output Iterator: write forward, *it=object; it++;

Forward Iterator: read and write forward

Bidirectional Iterator: read/write forward/backward,

it++, it--;

Random Access Iterator: it+n; it-n;

2013-2015 Margit ANTAL

Basic Operations

*it: element access get the element pointed to

it->member: member access

++it, it++, --it, it--: advance forward/

backward

==, !=: equality

2013-2015 Margit ANTAL

Input Iterator
template<class InIt, class T>
InIt find( InIt first, InIt last, T what)
{
for( ; first != last; ++first )
if( *first == what ){
return first;
}
return first;
}

2013-2015 Margit ANTAL

Input Iterator
template<class InIt, class Func>
Func for_each( InIt first, InIt last,
Func f){
for( ;first != last; ++first){
f( *first );
}
return f;
}

2013-2015 Margit ANTAL

Output Iterator
template <class InIt, class OutIt>
OutIt copy( InIt first1, InIt last1,
OutIt first2){
while( first1 != last1 ){
*first2 = *first1;
first1++;
first2++;
}
return first2;
}

2013-2015 Margit ANTAL

Forward Iterator
template < class FwdIt, class T >
void replace ( FwdIt first, FwdIt last,
const T& oldv, const T& newv ){
for (; first != last; ++first){
if (*first == oldv){
*first=newv;
}
}
}

2013-2015 Margit ANTAL

Bidirectional Iterator
template <class BiIt, class OutIt>
OutIt reverse_copy ( BiIt first, BiIt
last, OutIt result){
while ( first!=last ){
--last;
*result = *last;
result++;
}
return result;
}

2013-2015 Margit ANTAL

Containers & Iterators

vector Random Access Iterator

deque - Random Access Iterator

list Bidirectional Iterator

set, map - Bidirectional Iterator

unordered_set Forward Iterator

2013-2015 Margit ANTAL

Iterator adapters

Reverse iterators
Insert iterators
Stream iterators

2013-2015 Margit ANTAL

Reverse iterators

reverses the direction in which a bidirectional

or random-access iterator iterates through a
range.
++ - container.rbegin()
container.rend()

2013-2015 Margit ANTAL

Insert iterators

special iterators designed to allow algorithms

that usually overwrite elements to instead
insert new elements at a specific position in
the container.
the container needs to have an insert
member function

2013-2015 Margit ANTAL

Insert iterator - Example

//Incorrect
int x[] = {1, 2, 3};
vector<int> v;
copy( x, x+3, v.begin());

//Correct
int x[] = {1, 2, 3};
vector<int> v;
copy( x, x+3, back_inserter(v));

2013-2015 Margit ANTAL

Insert iterator - Example

template <class InIt, class OutIt>
OutIt copy( InIt first1, InIt last1,OutIt first2){
while( first1 != last1){
*first2 = *first1;//overwrite insert
first1++;
first2++;
}
return first2;
}

2013-2015 Margit ANTAL

Types of insert iterators

*pos = value;

Type

Class

Function

Back inserter

back_insert_iterator push_back(value)

back_inserter(container)

Front inserter

front_insert_iterator push_front(value)

front_inserter(container)

Inserter

insert_iterator

inserter(container, pos)

insert(pos, value)

2013-2015 Margit ANTAL

Creation

Stream iterators

Objective: connect algorithms to streams

cin

copy

vector

vector

copy

cout

2013-2015 Margit ANTAL

Stream iterator - examples

vector<int> v;
copy(v.begin(), v.end(),
ostream_iterator<int>(cout, ","));
copy(istream_iterator<int>(cin),
istream_iterator<int>(),
back_inserter(v));

2013-2015 Margit ANTAL

Carray iterator
template <class T>
class CArray{
T * data;
int size;
public:
...
};

2013-2015 Margit ANTAL

Problem 1.

It is given a CArray class

string str[]=
{"apple", "pear", "plum",
"peach", "strawberry", "banana"};
CArray<string> a(str, str+6);

2013-2015 Margit ANTAL

Problem 1.

It is given a Smart API too

Call the doIt function for CArray!

Smart<string> smart;
smart.doIt( ? );

2013-2015 Margit ANTAL

Problem 1. - Solution

string str[]= {"apple", "pear", "plum", "peach", "strawberry"};

CArray<string> a(str, str+5);
CArrayIterator<string> cit ( a );
Smart<string> smart;
2013-2015 Margit ANTAL
smart.doIt( cit );

Problem 2.

It is given a CArray class

string str[]=
{"apple", "pear", "plum",
"peach", "strawberry", "banana"};
CArray<string> a(str, str+6);

2013-2015 Margit ANTAL

Problem 2.

It is given a Smarter API

class Smarter{
public:
template <class RaIt>
void doIt( RaIt first, RaIt last ){
while( first != last ){
cout<< *first <<std::endl;
++first;
}
}
};

2013-2015 Margit ANTAL

Problem 2.

Call the doIt function in the given way!

CArray<string> a(str, str+6);

//...
Smarter smart;
smart.doIt( a.begin(), a.end() );

2013-2015 Margit ANTAL

Problem 2. - Solution A.
class CArray{
public:

class iterator{
T* poz;
public: ...
};

iterator begin(){ return iterator(array);}

iterator end(){ return iterator(array+size);}
private:
T * array;
int size;
};

2013-2015 Margit ANTAL

Problem 2. - Solution A.
class CArray{
public:
class iterator{

T* poz;
public:
iterator( T* poz=0 ): poz( poz ){}
iterator( const iterator& it ){ poz = it.poz; }
iterator& operator=( const iterator& it ){
if( &it == this ) return *this;
poz = it.poz; return *this;}
iterator operator++(){ poz++; return *this; }
iterator operator++( int p ){
iterator temp( *this ); poz++; return temp;}
bool operator == ( const iterator& it )const{
iteratorreturn
begin(){
iterator(array);}
poz ==return
it.poz;}
iterator
end(){ !=
return
iterator(array+size);}
bool operator
( const
iterator& it )const{
private:
return poz != it.poz; }
operator*() const { return *poz;}
T * T&
array;
}; size;
int

};

2013-2015 Margit ANTAL

Problem 2. - Solution B.
class CArray{
public:
typedef T * iterator;

iterator begin(){ return array;}

iterator end() { return array+size;}
private:
T * array;
int size;
};

2013-2015 Margit ANTAL

Carray iterator
template <class T>
class CArray{
T * data;
int size;
public:
...
typedef T*
typedef T
typedef T&
typedef ptrdiff_t
typedef T *
};

iterator;
value_type;
reference;
difference_type;
pointer;

2013-2015 Margit ANTAL

Module 9
Function Objects & Lambdas

2013-2015 Margit ANTAL

Function object
class
FunctionObjectType {

public:
return_type operator() (parameters) {
Statements
}
};

2013-2015 Margit ANTAL

Function pointer vs. function object

A function object may have a state

Each function object has its own type, which can be

passed to a template (e.g. set, map)

A function object is usually faster than a function pointer

2013-2015 Margit ANTAL

Function object as a sorting criteria

class PersonSortCriterion {
public:
bool operator() (const Person& p1, const Person& p2)
const {
if (p1.lastname() != p2.lastname() ){
return p1.lastname() < p2.lastname();
} else{
return p1.firstname()<p2.firstname());
}
};
// create a set with special sorting criterion
set<Person,PersonSortCriterion> coll;

2013-2015 Margit ANTAL

Function object with internal state

class IntSequence{
private:
int value;
public:
IntSequence (int initialValue) : value(initialValue) {
}
int operator() () {
return ++value;
}
};

2013-2015 Margit ANTAL

Function object with internal state

[Josuttis]

list<int> coll;
generate_n (back_inserter(coll), // start
9, // number of elements
IntSequence(1)); // generates values,
// starting with 1

2013-2015 Margit ANTAL

Function object with internal state

[Josuttis]

list<int> coll;
generate_n (back_inserter(coll), // start
9, // number of elements
IntSequence(1)); // generates values,
// starting with 1

???

2013-2015 Margit ANTAL

Function object with internal state + for_each

[Josuttis]
class MeanValue {
private:
long num; // number of elements
long sum; // sum of all element values
public:
MeanValue () : num(0), sum(0) {}
void operator() (int elem) {
++num; // increment count
sum += elem; // add value
}
double value () {
return static_cast<double>(sum) / num;
}
};

2013-2015 Margit ANTAL

function object with internal state + for_each

[Josuttis]

int main()
{
vector<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8 };

MeanValue mv = for_each (coll.begin(), coll.end(),

MeanValue());
cout << "mean value: " << mv.value() << endl;

Why to use the return value?

http://www.cplusplus.com/reference/algorithm/for_each /

2013-2015 Margit ANTAL

Predicates

Are function objects that return a boolean value

A predicate should always be stateless

template <typename ForwIter, typename Predicate>
ForwIter std::remove_if(ForwIter beg, ForwIter end,
Predicate op)

2013-2015 Margit ANTAL

Predefined function objects

Expression Effect

Expression Effect

negate<type>() - param
plus<type>()
param1 + param2
minus<type>() param1 - param2
multiplies<type>()param1 * param2
divides<type>() param1 / param2
modulus<type>() param1 % param2
equal_to<type>()param1 == param2
not_equal_to<type>() param1 !=
param2
less<type>() param1 < param2
greater<type>() param1 > param2
less_equal<type>() param1 <=
param2

greater_equal<type>() param1 >=

param2
logical_not<type>() ! param
logical_and<type>() param1 &&
param2
logical_or<type>() param1 ||
param2
bit_and<type>() param1 & param2
bit_or<type>() param1 | param2
bit_xor<type>() param1 ^ param2

2013-2015 Margit ANTAL

Lambdas

Syntactic sugar
C++
2011

a function that you can write inline in your source code

#include <iostream>
using namespace std;
int main()
{
auto func = [] () { cout << "Hello world"; };
func(); // now call the function
}

2013-2015 Margit ANTAL

Lambdas

Syntactic sugar

no need to write a separate function or to write a function object

set
auto comp = [](string x, string y) {
return x > y;
};
set<string, decltype(comp)> s(comp);
//...
for (auto& x : s) {
cout << x << endl;
}

2013-2015 Margit ANTAL

Lambda syntax
[ ] ( )opt ->

opt

Syntactic sugar

{ }

[ captures ]

( params ) ->ret { statements; }

[ captures ]
What outside variables are available, by value or by reference.
( params )
How to invoke it. Optional if empty.
-> ret
Uses new syntax. Optional if zero or one return statements.
{ statements; }

Herb Sutter: nwcpp.org/may-2011.html

The body of the lambda

2013-2015 Margit ANTAL

Examples
[ captures ]

Syntactic sugar

( params ) ->ret { statements; }

Earlier in scope: Widget w;

Capture w by value, take no parameters when invoked.

auto lamb = [w] { for( int i = 0; i < 100; ++i ) f(w); };
lamb();

Capture w by reference, take a const int& when invoked.

auto da = [&w] (const int& i) { return f(w, i); };
int i = 42;
da( i );

Herb Sutter: nwcpp.org/may-2011.html

2013-2015 Margit ANTAL

Lambdas == Functors
[ captures ]

Syntactic sugar

( params ) ->ret { statements; }

class __functor {
private:
CaptureTypes __captures;
public:
__functor( CaptureTypes captures )
: __captures( captures ) { }
auto operator() ( params ) { statements; }
Herb Sutter: nwcpp.org/may-2011.html

};

2013-2015 Margit ANTAL

Capture Example
[ c1, &c2 ]

Syntactic sugar

{ f(c1, c2); }

class __functor {
private:
C1 __c1; C2& __c2;
public:
__functor( C1 c1, C2& c2 )
: __c1(c1), __c2(c2) { }
void operator() () { f(__c1, __c2); }
Herb Sutter: nwcpp.org/may-2011.html

};

2013-2015 Margit ANTAL

Parameter Example
[]

Syntactic sugar

( P1 p1, const P2& p2 ){ f(p1, p2); }

class __functor {

public:
void operator() ( P1 p1, const P2& p2) {
f(p1, p2);
}
Herb Sutter: nwcpp.org/may-2011.html

};

2013-2015 Margit ANTAL

Syntactic sugar

Type of Lambdas
auto g = [&]( int x, int y ) { return x > y; };
map<int, int, ? > m( g );

2013-2015 Margit ANTAL

Syntactic sugar

Type of Lambdas
auto g = [&]( int x, int y ) { return x > y; };
map<int, int, ? > m( g );

auto g = [&]( int x, int y ) { return x > y; };

map<int, int, decltype(g) > m( g );

2013-2015 Margit ANTAL

Example
int x = 5;
int y = 12;
auto pos = find_if (
coll.cbegin(), coll.cend(),
// range
[=](int i){return i > x && i < y;}// search criterion
);
cout << "first elem >5 and <12: " << *pos << endl;

= symbols are passed

by value

2013-2015 Margit ANTAL

Example
vector<int> vec = {1,2,3,4,5,6,7,8,9};
int value = 3;
int cnt = count_if(vec.cbegin(),vec.cend(),
[=](int i){return i>value;});
cout << Found << cnt << values > << value <<
endl;

2013-2015 Margit ANTAL

Module 10
Advanced C++

2013-2015 Margit ANTAL

Outline

Casting. RTTI

Handling Errors

Smart Pointers

Move Semantics

Random Numbers

Regular Expressions

2013-2015 Margit ANTAL

Casting & RTTI

2013-2015 Margit ANTAL

Casting

converting an expression of a given type into another type

traditional type casting:

(new_type) expression
new_type (expression)

specific casting operators:

dynamic_cast <new_type> (expression)

reinterpret_cast <new_type> (expression)
static_cast <new_type> (expression)
const_cast <new_type> (expression)
2013-2015 Margit ANTAL

static_cast<>() vs. C-style cast

static_cast<>() gives you a compile time checking ability,

C-Style cast doesn't.

You would better avoid casting, except dynamic_cast<>()

2013-2015 Margit ANTAL

Run Time Type Information

Determining the type of any variable during execution

(runtime)

Available only for polymorphic classes (having at least one

virtual method)

RTTI mechanism

the dynamic_cast<> operator

the typeid operator
the type_info struct

2013-2015 Margit ANTAL

Casting Up and Down

class Super{
public:
virtual void m1();
};
class Sub: public Super{
public:
virtual void m1();
void m2();
};
Sub mySub;
//Super mySuper = mySub; // SLICE
Super& mySuper = mySub; // No SLICE
mySuper.m1(); // calls Sub::m1() - polymorphism
mySuper.m2(); // ???

2013-2015 Margit ANTAL

dynamic_cast<>
class Base{};
class Derived : public Base{};
Base* basePointer = new Derived();
Derived* derivedPointer = nullptr;
//To find whether basePointer is pointing to Derived type of object
derivedPointer = dynamic_cast<Derived*>(basePointer);
if (derivedPointer != nullptr){
cout << "basePointer is pointing to a Derived class object";
}else{
cout << "basePointer is NOT pointing to a Derived class object";
}

2013-2015 Margit ANTAL

dynamic_cast<>
class Person{
public: virtual void print(){cout<<Person;};
};
class Employee:public Person{
public: virtual void print(){cout<<Employee;};
};
class Manager:public Employee{
public: virtual void print(){cout<<Manager;};
};
vector<Person*> v;
v.push_back(new Person());
v.push_back(new Employee());
v.push_back( new Manager());
...

2013-2015 Margit ANTAL

dynamic_cast<>
class Person{
public: virtual void print(){cout<<Person;};
};
class Employee:public Person{
public: virtual void print(){cout<<Employee;};
};
class Manager:public Employee{
public: virtual void print(){cout<<Manager;};
};
vector<Person*> v;
v.push_back(new Person());
v.push_back(new Employee());
v.push_back( new Manager());
...

Write a code that counts

the number of employees!

2013-2015 Margit ANTAL

dynamic_cast<>
class Person{
public: virtual void print(){cout<<Person;};
};
Write a code that counts
class Employee:public Person{
the number of employees!
public: virtual void print(){cout<<Employee;};
};
class Manager:public Employee{
public: virtual void print(){cout<<Manager;};
Employee * p = nullptr;
};

for( Person * sz: v ){

vector<Person*> v;
p = dynamic_cast<Employee *>( sz );
v.push_back(new Person());
if( p != nullptr ){
v.push_back(new Employee());
++counter;
v.push_back( new Manager());
}
...
}

2013-2015 Margit ANTAL

Which solution is better? (Solution 1)

void speak(const Animal& inAnimal) {
if (typeid (inAnimal) == typeid (Dog)) {
cout << "VauVau" << endl;
} else if (typeid (inAnimal) == typeid (Bird)) {
cout << "Csirip" << endl;
}
}
.
Bird bird; Dog d;
speak(bird); speak( dog );

???

2013-2015 Margit ANTAL

Which solution is better? (Solution 2)

class Animal{
public:
virtual void speak()=0;
};
class Dog:public Animal{
public:
virtual void speak(){cout<<"VauVau"<<endl;};
};
class Bird: public Animal{
public:
virtual void speak(){cout<<"Csirip"<<endl;};
};
void speak(const Animal& inAnimal) {
inAnimal.speak();
}
Bird bird; Dog d;
speak(bird); speak( dog );

2013-2015 Margit ANTAL

typeid
class Person{
public: virtual void print(){cout<<Person;};
};
Write a code that counts the number of
class Employee:public Person{
employees (the exact type of the objects is
public: virtual void print(){cout<<Employee;};
Employee)!
};
class Manager:public Employee{
public: virtual void print(){cout<<Manager;};
};

counter = 0;
vector<Person*> v;
for( Person * sz: v ){
v.push_back(new Person());
if( typeid(*sz) == typeid(Employee) ){
v.push_back(new Employee());
++counter;
v.push_back( new Manager());
}
...
}

2013-2015 Margit ANTAL

Typeid usage
#include <iostream>
#include <typeinfo>
using namespace std;

a and b are of different types:

a is: Pi
b is: i

int main ()
{
int * a;
int b;
a=0; b=0;
if (typeid(a) != typeid(b))
{
cout << "a and b are of different types:\n";
cout << "a is: " << typeid(a).name() << '\n';
cout << "b is: " << typeid(b).name() << '\n';
}
return 0;
}

2013-2015 Margit ANTAL

Handling Errors

2013-2015 Margit ANTAL

Handling Errors

C++ provides Exceptions as an error

handling mechanism

Exceptions: to handle exceptional but not

unexpected situations

2013-2015 Margit ANTAL

Return type vs. Exceptions

Return type:

Exceptions:

caller may ignore

caller may not propagate
upwards
doesn't contain sufficient
information

2013-2015 Margit ANTAL

easier
more consistent
safer
cannot be ignored (your
program fails to catch an
exception will terminate)
can skip levels of the call
stack

Exceptions
int SafeDivide(int num, int den)
{
if (den == 0)
throw invalid_argument(Divide by zero);
return num / den;
}
int main()
{
try {
cout << SafeDivide(5, 2) << endl;
cout << SafeDivide(10, 0) << endl;
cout << SafeDivide(3, 3) << endl;
} catch (const invalid_argument& e) {
cout << Caught exception: << e.what() << endl;
}
return 0;
}

2013-2015 Margit ANTAL

<stdexcept>

Discussion??!!!

Exceptions

<stdexcept>

int SafeDivide(int num, int den)

{
if (den == 0)
throw invalid_argument(Divide by zero);
return num / den;
}
int main()
{
try {
cout << SafeDivide(5, 2) << endl;
cout << SafeDivide(10, 0) << endl;
cout << SafeDivide(3, 3) << endl;
} catch (const invalid_argument& e) {
cout << Caught exception: << e.what() << endl;
}
return 0;
}

It is recommended to catch exceptions by const reference.

2013-2015 Margit ANTAL

HandExceptions
try {
// Code that can throw exceptions
} catch (const invalid_argument& e) {
// Handle invalid_argument exception
} catch (const runtime_error& e) {
// Handle runtime_error exception
} catch (...) {
// Handle all other exceptions
}

Any exception

2013-2015 Margit ANTAL

<stdexcept>

Throw List

<stdexcept>

void func() throw (extype1, extype2){

// statements
}
The throw list is not enforced at compile time!

2013-2015 Margit ANTAL

Throw List

<stdexcept>

http://www.cplusplus.com/doc/tutorial/exceptions/

void func() throw (){

// statements
}
void func() noexcept{
// statements
}

2013-2015 Margit ANTAL

C++
2011

The Standard Exceptions

<stdexcept>

http://cs.stmarys.ca/~porter/csc/ref/cpp_standlib.html
2013-2015 Margit ANTAL

User Defined Exception

<stdexcept>

It is recommended to inherit

directly or indirectly from the standard

exception

exception class
your_exception

2013-2015 Margit ANTAL

User Defined Exception

<stdexcept>

class FileError : public runtime_error{

public:
FileError(const string& fileIn):runtime_error ()
, mFile(fileIn) {}
virtual const char* what() const noexcept{
return mMsg.c_str();
}
string getFileName() { return mFile; }
protected:
string mFile, mMsg;
};

2013-2015 Margit ANTAL

Smart Pointers

2013-2015 Margit ANTAL

Why Smart Pointers?

When to delete an object?

No deletion memory leaks
Early deletion (others still pointing to)
dangling pointers
Double-freeing

2013-2015 Margit ANTAL

Smart Pointer Types

unique_ptr
shared_ptr

C++
2011

It is recommended to use smart pointers!

2013-2015 Margit ANTAL

The good old pointer

void oldPointer(){
Foo * myPtr = new Foo();
myPtr->method();
}

Memory leak

2013-2015 Margit ANTAL

The good old pointer

void oldPointer1(){
Foo * myPtr = new Foo();
myPtr->method();
}

void oldPointer2(){
Foo * myPtr = new Foo();
myPtr->method();
delete myPtr;
}

Memory leak

Could cause
memory leak
When?

2013-2015 Margit ANTAL

The Old and the New

void oldPointer(){
Foo * myPtr = new Foo();
myPtr->method();
}

Memory leak

void newPointer(){
shared_ptr<Foo> myPtr (new Foo());
myPtr->method();
}

2013-2015 Margit ANTAL

The new smart pointer

void newPointer(){
shared_ptr<Foo> myPtr (new Foo());
myPtr->method();
}

void newPointer(){
auto myPtr = make_shared<Foo>();
myPtr->method();
}

2013-2015 Margit ANTAL

unique_ptr

it will automatically free the resource in case of the

unique_ptr

goes out of scope or

is deleted

2013-2015 Margit ANTAL

shared_ptr

Each time a shared_ptr is assigned

a reference count is incremented (there is one more

owner of the data)
When a shared_ptr goes out of scope

the reference count is decremented

if reference_count = 0 the object referenced by the
pointer is freed.

2013-2015 Margit ANTAL

Implementing your own smart pointer class

CountedPtr<Person> p(new Person("Para Peti",1980));

:Person
p: CountedPtr<Person>

"Para Peti"

ptr
count

2013-2015 Margit ANTAL

Implementing your own smart pointer class

CountedPtr<Person> p1 = p;
CountedPtr<Person> p2 = p;

:Person

p
ptr
count

"Para Peti"

p1

ptr
count
p2
ptr
count

2013-2015 Margit ANTAL

Implementation (1)
template < class T>
class CountedPtr{
T * ptr;
long * count;
public:
...
};

2013-2015 Margit ANTAL

Implementation (2)
CountedPtr( T * p = 0 ):ptr( p ),
count( new long(1)){
}
CountedPtr( const CountedPtr<T>& p ): ptr( p.ptr),
count(p.count){
++(*count);
}
~CountedPtr(){
--(*count);
if( *count == 0 ){
delete count; delete ptr;
}
}

2013-2015 Margit ANTAL

Implementation (3)
CountedPtr<T>& operator=( const CountedPtr<T>& p ){
if( this != &p ){
--(*count);
if( *count == 0 ){ delete count; delete ptr; }
this->ptr = p.ptr;
this->count = p.count;
++(*count);
}
return *this;
}
T& operator*()

const{ return *ptr;}

T* operator->() const{ return

ptr;}

2013-2015 Margit ANTAL

Module 11
I/O Streams

2013-2015 Margit ANTAL

Outline

Using Streams
String Streams
File Streams
Bidirectional I/O

2013-2015 Margit ANTAL

Using Streams
Program

file
keypad
program

Input Stream

Output Stream

stream:
is data flow
direction
associated source and destination

2013-2015 Margit ANTAL

file
screen
program

Using Streams
cin

An input stream, reads data from the input console.

cout A buffered output stream, writes data to the output console.

cerr An unbuffered output stream, writes data to the error console
clog A buffered version of cerr.

2013-2015 Margit ANTAL

Using Streams

Stream:
includes data
has a current position
next read or next write

2013-2015 Margit ANTAL

Using Streams
ios_base

basic_streambuf<>
streambuf, wstreambuf

basic_ios<>
ios, wios

basic_istream<>
istream, wistream

basic_ostream<>
ostream, wostream

basic_iostream<>
iostream, wiostream

2013-2015 Margit ANTAL

Using Streams

Output stream:

inserter operator <<

raw output methods (binary):
put(), write()

void rawWrite(const char* data, int dataSize){

cout.write(data, dataSize);
}
void rawPutChar(const char* data, int charIndex)
{
cout.put(data[charIndex]);
}

2013-2015 Margit ANTAL

Using Streams

Output stream:

most output streams buffer data (accumulate)

the stream will flush (write out the accumulated data)
when:
an endline marker is reached ('\n', endl)
the stream is destroyed (e.g. goes out of scope)
the stream buffer is full
explicitly called flush()

2013-2015 Margit ANTAL

Using Streams

Manipulators:

objects that modify the behavior of the stream

setw, setprecision
hex, oct, dec
C++11: put_money, put_time

int i = 123;
printf(This should be '
cout <<This should be '

123': %6d\n, i);

123': << setw(6) << i << endl;

2013-2015 Margit ANTAL

Using Streams

Input stream:

extractor operator >>

will tokenize values according to white spaces

raw input methods (binary):

get(): avoids tokenization
string readName(istream& inStream)
{
string name;
char next;
while (inStream.get(next)) {
name += next;
}
return name;
}

2013-2015 Margit ANTAL

reads an input having

more than one word

Using Streams

Input stream:

getline(): reads until end of line

reads an input having
more than one word
string myString;
getline(cin, myString);

2013-2015 Margit ANTAL

Using Streams

Input stream:

getline(): reads until end of line

reads an input having
more than one word
string myString;
getline(cin, myString);
Reads up to new line character
Unix line ending: '\n'
Windows line ending: '\r' '\n'
The problem is that getline leaves
the '\r' on the end of the string.
2013-2015 Margit ANTAL

Using Streams

Stream's state:

every stream is an object has a state

stream's states:
good: OK
eof: End of File
fail: Error, last I/O failed
bad: Fatal Error

2013-2015 Margit ANTAL

Using Streams

Find the error!

list<int> a;

Input:
1
2
3
(empty line)

int x;
while( !cin.eof() ){
cin>>x;
a.push_back( x );
}

a: 1, 2, 3, 3

2013-2015 Margit ANTAL

Using Streams

Handling Input Errors:

while( cin )
while( cin >> ch )

int number, sum = 0;

while ( true ) {
cin >> number;
if (cin.good()){
sum += number;
} else{
break;
}
}

int number, sum = 0;

while ( cin >> number ){
sum += number;
}

2013-2015 Margit ANTAL

String Streams

<sstream>

ostringstream

istringstream

stringstream

string s =12.34;
stringstream ss(s);
double d;
ss >> d;

double d =12.34;
stringstream ss;
ss<<d;
string s = szam:+ss.str()

2013-2015 Margit ANTAL

File Streams
{
ifstream ifs("in.txt");//Constructor
if( !ifs ){
//File open error
}
//Destructor
}
{
ifstream ifs;
ifs.open("in.txt");
//...
ifs.close();
//...
}

2013-2015 Margit ANTAL

File Streams

Byte I/O
ifstream ifs("in.txt");
if( !ifs ){
cerr<<"File Open Error"<<endl; exit( 1 );
}
char c;
while( ifs.get( c ) ){
cout.put( c );
}

2013-2015 Margit ANTAL

Object I/O

Operator overloading
istream& operator>>( istream& is, T& v ){
//read v
return is;
}
ostream& operator<<(ostream& is, const T& v ){
//write v
return os;
}

2013-2015 Margit ANTAL

Module 12
Concurrency

2013-2015 Margit ANTAL

Outline

High-level interface: async() and future

Low-level interface: thread, promise

Synchronizing threads
Mutexes and locks: mutex, lock_guard,

unique_lock

Atomics
2013-2015 Margit ANTAL

Problem
Find all words matching a pattern in a dictionary!
Pattern: a..l.
Word: apple, apply, ...

http://marknelson.us/2012/05/23/c11-threading-made-easy/

2013-2015 Margit ANTAL

Single-threaded Solution (1)

string pattern ="a..l.";
// Load the words into the deque
ifstream f( "dobbsdict.txt" );
if ( !f ) {
cerr << "Cannot open dobbsdict.txt in the current directory\n";
return 1;
}
string word;
deque<string> backlog;
while ( f >> word ){
backlog.push_back( word );
}
// Now process the words and print the results
vector<string> words = find_matches(pattern, backlog);
cerr << "Found " << words.size()<< " matches for " << pattern<< endl;
for ( auto s : words ){
cout << s << "\n";
}

2013-2015 Margit ANTAL

Single-threaded Solution (2)

inline bool match( const string &pattern, string word )
{
if ( pattern.size() != word.size() )
return false;
for ( size_t i = 0 ; i < pattern.size() ; i++ )
if ( pattern[ i ] != '.' && pattern[ i ] != word[ i ] )
return false;
return true;
}
vector<string> find_matches( string pattern, deque<string> &backlog )
{
vector<string> results;
for ( ; ; ) {
if ( backlog.size() == 0 ) { return results;}
string word = backlog.front();
backlog.pop_front();
if ( match( pattern, word ) ){ results.push_back( word );}
}
return results;
}

2013-2015 Margit ANTAL

Multi-threaded Solution (1)

string pattern ="a..l.";
// Load the words into the deque
ifstream f( "dobbsdict.txt" );
if ( !f ) {
cerr << "Cannot open sowpods.txt in the current directory\n";
return 1;
}
string word;
deque<string> backlog;
while ( f >> word ){ backlog.push_back( word );}
// Now process the words and print the results
auto f1 = async( launch::async, find_matches, pattern, ref(backlog) );
auto f2 = async( launch::async, find_matches, pattern, ref(backlog) );
auto f3 = async( launch::async, find_matches, pattern, ref(backlog) );
print_results( f1, pattern, 1 );
print_results( f2, pattern, 2 );
print_results( f3, pattern, 3 );

2013-2015 Margit ANTAL

Worker thread
Returns a std::future object

Multi-threaded Solution (1)

string pattern ="a..l.";
// Load the words into the deque
ifstream f( "dobbsdict.txt" );
if ( !f ) {
cerr << "Cannot open sowpods.txt in the current directory\n";
return 1;
}
string word;
deque<string> backlog;
while ( f >> word ){ backlog.push_back( word );}
// Now process the words and print the results
auto f1 = async( launch::async, find_matches, pattern, ref(backlog) );
auto f2 = async( launch::async, find_matches, pattern, ref(backlog) );
auto f3 = async( launch::async, find_matches, pattern, ref(backlog) );
print_results( f1, pattern, 1 );
print_results( f2, pattern, 2 );
print_results( f3, pattern, 3 );

2013-2015 Margit ANTAL

parameter as a reference

Multi-threaded Solution (2)

template<class ASYNC>
void print_results( ASYNC &f, string &pattern, int threadno )
{
vector<string> words = f.get();
cerr << "Found " << words.size()<< " matches for " << pattern
<< " in thread " << threadno<< endl;
for ( auto s : words ){ cout << s << "\n";}
}

std::future<>::get()
-returns the return value of the
async function
-blocks until the thread is complete

2013-2015 Margit ANTAL

Multi-threaded Solution (3)

std::mutex m;
vector<string> find_matches( string pattern, deque<string> &backlog )
{
vector<string> results;
for ( ; ; ) {
m.lock();
if ( backlog.size() == 0 ) {
m.unlock();
return results;
}
string word = backlog.front();
backlog.pop_front();
m.unlock();
if ( match( pattern, word ) )
results.push_back( word );
}
}

2013-2015 Margit ANTAL

Performance

Multi-threaded vs. Single-threaded solution!!!

2013-2015 Margit ANTAL

Futures
Objectives

makes easy to get the computed result back from a thread,

able to transport an uncaught exception to another thread.

1. When a function has calculated the return value

2. Put the value in a promise object
3. The value can be retrieved through a future

2013-2015 Margit ANTAL

inter-thread
communication
channel

Futures
future<T> fut = // launch a thread or async
T result = fut.get();

if the other thread has not yet finished the call to get() will
block

avoid blocking:
if( fut.wait_for( 0 ) ){
T result = fut.get();
} else{
...
}

2013-2015 Margit ANTAL

mutex
int val;
mutex valMutex;
valMutex.lock();
if (val >= 0) {
f(val);
}
else {
f(-val);
}
valMutex.unlock();

[Gregoire]

mutex = mutual exclusion

Helps to control the

concurrent access of
a resource

2013-2015 Margit ANTAL

mutex
int val;
mutex valMutex;
valMutex.lock();
if (val >= 0) {
f(val);
}
else {
f(-val);
}
valMutex.unlock();

2013-2015 Margit ANTAL

What happens
in case of an exception?

mutex vs. lock_guard<mutex>

int val;
mutex valMutex;
valMutex.lock();
if (val >= 0) {
f(val);
}
else {
f(-val);
}
valMutex.unlock();

int val;
mutex valMutex;
lock_guard<mutex>
if (val >= 0) {
f(val);
}
else {
f(-val);
}

lg(valMutex);

RAII principle (Resource Acquisition Is Initialization)

2013-2015 Margit ANTAL

lock_guard<mutex>
int val;
mutex valMutex;
{
lock_guard<mutex>
if (val >= 0) {
f(val);
}
else {
f(-val);
}
}

lg(valMutex);

Constructor: acquires the resource

Destructor: releases the resource

RAII principle (Resource Acquisition Is Initialization)

2013-2015 Margit ANTAL

unique_lock<mutex>

unique_lock = lock_guard + lock() & unlock()

2013-2015 Margit ANTAL

Multithreaded Logger [Gregoire]

class Logger {
public:
Logger();
void log(const string& entry);
protected:
void processEntries();
mutex mMutex;
condition_variable mCondVar;
queue<string> mQueue;
thread mThread;
// The background thread.
private:
// Prevent copy construction and assignment.
Logger(const Logger& src);
Logger& operator=(const Logger& rhs);
};

2013-2015 Margit ANTAL

Multithreaded Logger [Gregoire]

Logger::Logger() {
// Start background thread.
mThread = thread{&Logger::processEntries, this};
}
void Logger::log(const std::string& entry) {
// Lock mutex and add entry to the queue.
unique_lock<mutex> lock(mMutex);
mQueue.push(entry);
// Notify condition variable to wake up thread.
mCondVar.notify_all();
}

2013-2015 Margit ANTAL

Multithreaded Logger [Gregoire]

void Logger::processEntries()
{
ofstream ofs(log.txt);
if (ofs.fail()){ return; }
unique_lock<mutex> lock(mMutex);
while (true) {
// Wait for a notification.
mCondVar.wait(lock);

// Condition variable is notified something is in the queue.

lock.unlock();
while (true) {
lock.lock();
if (mQueue.empty()) {
break;
} else {
ofs << mQueue.front() << endl;
mQueue.pop();
}
lock.unlock();
}

2013-2015 Margit ANTAL

Usage: Multithreaded Logger [Gregoire]

void logSomeMessages(int id, Logger& logger)
{
for (int i = 0; i < 10; ++i) {
stringstream ss;
ss << Log entry << i << from thread << id;
logger.log(ss.str());
}
}
int main()
{
Logger logger;
vector<thread> threads;
// Create a few threads all working with the same Logger instance.
for (int i = 0; i < 10; ++i) {
threads.push_back(thread(logSomeMessages, i, ref(logger)));
}
// Wait for all threads to finish.
for (auto& t : threads) {
t.join();
}
return 0;
}

2013-2015 Margit ANTAL

Netbeans: Logger1
Logger1.exe..stackdump

Problem: Multithreaded Logger [Gregoire]

2013-2015 Margit ANTAL

Problem: Multithreaded Logger [Gregoire]

end of main() terminate abruptly Logger thread

2013-2015 Margit ANTAL

Solution: Multithreaded Logger [Gregoire]

class Logger
{
public:
Logger();
// Gracefully shut down background thread.
virtual ~Logger();
// Add log entry to the queue.
void log(const std::string& entry);
protected:
void processEntries();
bool mExit;
...
};

2013-2015 Margit ANTAL

Solution: Multithreaded Logger [Gregoire]

void Logger::processEntries()
{

while (true) {
// Wait for a notification.
mCondVar.wait(lock);
// Condition variable is notified, so something is in the queue
// and/or we need to shut down this thread.
lock.unlock();
while (true) {
lock.lock();
if (mQueue.empty()) {
break;
} else {
ofs << mQueue.front() << endl;
mQueue.pop();
}
lock.unlock();
}
if (mExit) break;
}
}

2013-2015 Margit ANTAL

Solution: Multithreaded Logger [Gregoire]

Logger::Logger() : mExit(false)
{
// Start background thread.
mThread = thread{&Logger::processEntries, this};
}
Logger::~Logger()
{
// Gracefully shut down the thread by setting mExit
// to true and notifying the thread.
mExit = true;
// Notify condition variable to wake up thread.
mCondVar.notify_all();
// Wait until thread is shut down.
mThread.join();
}

2013-2015 Margit ANTAL

Solution: Multithreaded Logger [Gregoire]

Logger::Logger() : mExit(false)
{
// Start background thread.
mThread = thread{&Logger::processEntries, this};
}
Logger::~Logger()
{
// Gracefully shut down the thread by setting mExit
// to true and notifying the thread.
mExit = true;
// Notify condition variable to wake up thread.
mCondVar.notify_all();
// Wait until thread is shut down.
mThread.join();
}

2013-2015 Margit ANTAL

Solution: Multithreaded Logger [Gregoire]

?
Deadlock

2013-2015 Margit ANTAL

Solution: Multithreaded Logger [Gregoire]

It can happen that this remaining code from the main()
function, including the Logger destructor, is executed before
the Logger background thread has started its processing loop.
When that happens, the Logger destructor will already have
called notify_all() before the background thread is waiting for
the notifi cation, and thus the background thread will miss this
notifi cation from the destructor.

2013-2015 Margit ANTAL

Object Pool
Thread Pool

ObjectPool
resources: Collection
maxResources: int
rFactory: Factory
aquireObject()
releaseObject()

Factory

createResource()

Resource

2013-2015 Margit ANTAL

Object Pool
C++ implementation [Gregoire]
template <typename T>
class ObjectPool{
public:
ObjectPool(size_t chunkSize = kDefaultChunkSize)
throw(std::invalid_argument, std::bad_alloc);
shared_ptr<T> acquireObject();
void releaseObject(shared_ptr<T> obj);
protected:
queue<shared_ptr<T>> mFreeList;
size_t mChunkSize;
static const size_t kDefaultChunkSize = 10;
void allocateChunk();
private:
// Prevent assignment and pass-by-value
ObjectPool(const ObjectPool<T>& src);
ObjectPool<T>& operator=(const ObjectPool<T>& rhs);
};

2013-2015 Margit ANTAL

Object Pool
C++ implementation [Gregoire]

template <typename T>

ObjectPool<T>::ObjectPool(size_t chunkSize)
throw(std::invalid_argument, std::bad_alloc){
if (chunkSize == 0) {
throw std::invalid_argument(chunk size must be positive);
}
mChunkSize = chunkSize;
allocateChunk();
}

2013-2015 Margit ANTAL

Object Pool
C++ implementation [Gregoire]

template <typename T>

void ObjectPool<T>::allocateChunk()
{
for (size_t i = 0; i < mChunkSize; ++i) {
mFreeList.push(std::make_shared<T>());
}
}

2013-2015 Margit ANTAL

Object Pool
C++ implementation [Gregoire]

template <typename T>

shared_ptr<T> ObjectPool<T>::acquireObject()
{
if (mFreeList.empty()) {
allocateChunk();
}
auto obj = mFreeList.front();
mFreeList.pop();
return obj;
}

2013-2015 Margit ANTAL

Object Pool
C++ implementation [Gregoire]
template <typename T>
void ObjectPool<T>::releaseObject(shared_ptr<T> obj)
{
mFreeList.push(obj);
}

2013-2015 Margit ANTAL