2. Object Oriented Programming und Templates · OOP Prinzipien Abstraktion – Funktionalität gegeben über Schnittstellen (Memberfunktionen) wie bei abstrakten Datentypen – Komplexität

2. Object Oriented Programmingund

TemplatesAlDaBi Praktikum

René Rahn, Hannes HauswedellWS 2015/16 © David Weese 2010/11

PROGRAMMING PARADIGMSFundamental Programming Styles

Imperative Paradigmen

• Programm besteht aus Anweisungen, die den Status des Programms ändern

• Programmierer beschreibt, wie diese Anweisungen auszuführen sind, ähnlich einem Kochrezept

• Wiederverwendbare Anweisungsblöcke werden meist in Funktionen ausgelagert

• Ergebnisse von Funktionen sind oftmals vom Programmstatus abhängig

Beispiel Naives Pattern Matching#include <iostream>#include <string>#include <vector>

// Iteration über das Pattern (inner loop)int computeLocalScore(std::string const & text, std::string const & pattern,

int const & textPos) {...}// Iteration über den Text (outer loop)std::vector<int> computeScore(std::string const & text, std::string const &

pattern){...}int main() {

// Initialisierungstd::string text = "This is an awesome tutorial to get to know some C++!";std::string pattern = "some"; // Computation of the similaritiesstd::vector<int> score = computeScore(text, pattern);// Ergebnisausgabefor (unsigned i = 0; i < score.size(); ++i)

std::cout << score[i];std::cout << std::endl;return 0;

}

OOP ParadigmenAusführung von Anweisungen mit Hilfe von interagierenden Objekten

– Objekte sind reale oder abstrakte Einheiten mit einer best. Rolle– Objekte haben klar definierte Verhaltensweisen– Objekte enthalten private Informationen– Objekte interagieren miteinander über ihre Funktionalitäten

Programmierer entwerfen ein Set von Objekten für das aktuelle Problem– Menschen sehen die Welt als eine Zusammenwirkung von Objekten

Wichtig für Softwarekonzeption, Wartung und Erweiterbarkeit– Objekt ist kleinste Moduleinheit, erweiterbar und wiederverwendbar

Moderne Programmiersprachen unterstützen OOP– Java und C++ wurden direkt für OOP konzipiert

OOP PrinzipienAbstraktion

– Funktionalität gegeben über Schnittstellen (Memberfunktionen) wie bei abstrakten Datentypen

– Komplexität der Implementierung beschränkt sich auf das Objekt, d.h. für den Benutzer nicht notwendig und ersichtlich

Datenkapselung– Interner Status des Objektes nicht nach außen ersichtlich– Objekt (Member) kann nur über seine Methoden verändert und

eingesehen werden– Methoden sichern ab, dass Member nur gültige Zustände erreichen

Vererbung– Erlaubt Wiederverwendung und Erweiterung von Objekten

Polymorphismus– Erlaubt Spezialisierung von Subtypen von Objekten (z.B. nach

Vererbung)

Beispiel Parkplatz für Autos• Anweisungen

– Programmiere Anwendung zum Parkplatzmanagement– Berechne zu jeder Zeit den aktuellen Gewinn durch die parkenden

Autos– Parkgebühr abhängig von der Automarke

• Objekte– Parking: enthält Autos– Car: Auto– Brand: Automarke– BrandPricer: Bestimmt Gebühr anhand der Automarke

Beispiel entnommen aus der Vorlesung „La programmation objet “ of Rémi Forax, WS07, Univ. Paris-Est MLV

Beispiel Parkplatz für Autos (II)

ObjektbeziehungenAssoziation

– Generische Beziehung zwischen zwei Objekten

– Objekte benutzen andere Objekte oder stellen sie zur Verfügung

Aggregation– „Hat ein(e)“ Beziehung– Tritt z.B. in Containern (z.B.

Vektoren) aufKomposition

– „Teil eine(s)“ Beziehung– Objekt existiert nur als Teil

eines anderen Objektes

OOP IN C++A Very Brief Overview

Klassen und ObjekteKlasse definiert Implementierung von Objekten

Objekt ist Instanz einer Klasse– a, b, c sind alles Instanzen derselben Klasse Car

class Car { // private: };

class Car { // private: };

void main() { Car a; Car b; Car c;}

void main() { Car a; Car b; Car c;}

struct Car { // public:};

struct Car { // public:};

Member• Eigenschaften eines Objektes sind die Member (Typen, Variablen) der

Klasse• Sichtbarkeit der Member kann eingeschränkt sein

– Schlüsselwort private nur sichtbar innerhalb der Klasse– Schlüsselwort protected erlaubt Sichtbarkeit für Subklassen– Schlüsselwort public erlaubt Sichtbarkeit für alle Klassen

class Car {private: string idPlate;protected: unsigned seats;public: string brandName;};

class Car {private: string idPlate;protected: unsigned seats;public: string brandName;};

void main() { Car c; // OK c.BrandName = ”BMW”; // Compile Error c.seats = 5; // Compile Error cout << c.idPlate;}

void main() { Car c; // OK c.BrandName = ”BMW”; // Compile Error c.seats = 5; // Compile Error cout << c.idPlate;}

Methoden• Methoden sind Funktionen mit einem impliziten Argument this• this ist ein Pointer auf das spezielle, instanziierte Objekt

class Car { private: string idPlate;

public: string getIdPlate() { return this>idPlate; }

bool setIdPlate(string &idPlate) { if (!idPlate.empty()) return false; this>idPlate = idPlate; return true; }};

class Car { private: string idPlate;

public: string getIdPlate() { return this>idPlate; }

bool setIdPlate(string &idPlate) { if (!idPlate.empty()) return false; this>idPlate = idPlate; return true; }};

int main() { Car c; // Returns false c.setIdPlate(“”); // Returns true c.setIdPlate(”B ER 2025”); // Prints B ER 2025 cout << c.getIdPlate();}

int main() { Car c; // Returns false c.setIdPlate(“”); // Returns true c.setIdPlate(”B ER 2025”); // Prints B ER 2025 cout << c.getIdPlate();}

Methoden extern definieren• Methoden müssen in der Klasse deklariert werden• Der Übersichtlichkeit wegen werden sie aber oft außerhalb definiert

// Deklaration in car.cppclass Car { private: string idPlate;public:

bool setIdPlate(string &); // Deklaration};

// Definition in car.hbool Car::setIdPlate(string &idPlate) { if (!idPlate.empty()) return false; this>idPlate = idPlate; return true; }

// Deklaration in car.cppclass Car { private: string idPlate;public:

bool setIdPlate(string &); // Deklaration};

// Definition in car.hbool Car::setIdPlate(string &idPlate) { if (!idPlate.empty()) return false; this>idPlate = idPlate; return true; }

Method OverloadingMethoden (und Funktionen) können überladen werden

– Zwei Funktionen können denselben Namen, aber andere Signaturen haben

– Der Compiler wählt den mit der passendsten Signatur aus– Überladung bezieht sich dabei nicht auf den Rückgabewert!!

Methoden nur überladen, wenn sie inhaltlich (mehr oder weniger) dasselbe machen!

struct Class { static void m(int a) { cout << ”1” } static bool m(char a) { cout << ”2” } static void m(double a, double b) { cout << ”3” }};

struct Class { static void m(int a) { cout << ”1” } static bool m(char a) { cout << ”2” } static void m(double a, double b) { cout << ”3” }};

void main() { // Prints 1 Class::m(5); // Prints 2 Class::m((char)5); // Prints 3 Class::m(3.1, 2);}

void main() { // Prints 1 Class::m(5); // Prints 2 Class::m((char)5); // Prints 3 Class::m(3.1, 2);}

VererbungVererbung besteht aus drei Konzepten

– Strukturelle Vererbung der Methoden und Member– Subtyping– Method overloading

Die abgeleitete Klasse ElectricCar– Erbt Methoden refill und drive von Car– Ist ein Subtyp der Klasse Car– Hat die Möglichkeit die Klasse Car zu erweitern und spezialisieren

struct Car { void refill() {} void drive() {}};struct ElectricCar : Car {}

struct Car { void refill() {} void drive() {}};struct ElectricCar : Car {}

void main() { ElectricCar e; e.drive();}

void main() { ElectricCar e; e.drive();}

Subtyping• Problem: Können wir ein ElectricCar Auto auf einem Parkplatz für Car

Autos parken?– Yes we can!

struct Parking { vector<Car> cars;

Parking(unsigned places) { cars.resize(places); } void park(unsigned place, Car &car) { cars[place] = car; } Car & leave(unsigned place) {

return cars[place]; }};

struct Parking { vector<Car> cars;

Parking(unsigned places) { cars.resize(places); } void park(unsigned place, Car &car) { cars[place] = car; } Car & leave(unsigned place) {

return cars[place]; }};

void main() { Parking p(2);

Car c; p.park(0, c);

ElectricCar e; p.park(1, e);

Car & b = p.leave(1); b.drive();}

void main() { Parking p(2);

Car c; p.park(0, c);

ElectricCar e; p.park(1, e);

Car & b = p.leave(1); b.drive();}

Note: due to space constraints, class Parking is not implemented as it should be!

QuizWoher weiß die Memberfunktion Date::month(), dass sie beim ersten

Aufruf d1.m und beim zweiten d2.m zurückgeben muss?

Class Date { // ... int month() {return m;} // ... private: int y, m, d; // Jahr, Monat, Tag};

void f(Date d1, Date d2) { cout << d1.month() << d2.month() << endl;};



QuizWoher weiß die Memberfunktion Date::month(), dass sie beim ersten

Aufruf d1.m und beim zweiten d2.m zurückgeben muss?





month(&d1)month(&d1) month(&d2)month(&d2)

int month(Date *this) { return *this.m; }int month(Date *this) { return *this.m; }

TEMPLATES

Templates: MotivationAufgabe: Schreibe eine Funktion max(a, b), die das Maximum zweier Zahlen

a und b ausgibt:

Problem: Funktion wird für alle Typen benötigt

float x = max(1.4, y);float x = max(1.4, y);

int max (int a, int b){

if (a > b) return a;return b;

}

int max (int a, int b){


}

Lösung: TemplatesTemplates sind Schablonen, nach denen der Compiler Code herstellt

template <typename T>T max (T a, T b){


}

...

float x = 1, y = 2;float z = max (x, y);



}

...

float x = 1, y = 2;float z = max (x, y);

Template-ArgumenteBeim Kompilieren müssen die Template-Argumente bestimmt werden.Es gibt zwei Möglichkeiten:

1. Explizit:

2. Implizit:

template <typename T1, typename T2>void f (T1 a, T2 b) { ... }

f<int,float>(0, 3.5);

template <typename T1, typename T2>void f (T1 a, T2 b) { ... }

f<int,float>(0, 3.5);

int x = 0; float y = 3.5;

f(x, y);

int x = 0; float y = 3.5;

f(x, y);

Template-Argumente, gemischtMischung von expliziter und impliziter Bestimmung von Template-

Argumenten:

1. Argument: char x2. Argument: float y3. Argument: int z

template <typename T1, typename T2, typename T3>void f (T3 x, T2 y, T1 z) { ... }

f<int>( (char) 0, 3.5F, 7 );

template <typename T1, typename T2, typename T3>void f (T3 x, T2 y, T1 z) { ... }

f<int>( (char) 0, 3.5F, 7 );

Implizit: Problem 1Folgender Code verursacht ein Problem:

error: template parameter 'T' is ambiguous

Grund:– x (double) und 0 (int) haben unterschiedliche Typen– In Funktionssignatur müssen beide Argumente denselben Typ haben


//...}

double x = 1.0;double y = max(x, 0);


//...}

double x = 1.0;double y = max(x, 0);

Implizit: Problem 2Bei folgendem Beispiel funktioniert eine implizite Bestimmung des Template-

Arguments gar nicht:

error: could not deduce template argument

Grund:– Implizite Bestimmung benutzt Argumente, nicht den Rückgabewert

template <typename T>T zero (){

return 0;}

int x = zero();

template <typename T>T zero (){

return 0;}

int x = zero();

Parameter-DeklarationenStatt eines Types kann auch eine Konstante als Template-Parameter

spezifiziert werden:

Ausgabe: 5

template <int I>void print (){

std::cout << I;}

print<5>();

template <int I>void print (){

std::cout << I;}

print<5>();

Template-KlassenWie Template-Funktionen lassen sich auch Template-Klassen definieren:

Beispiel:– vector, map, list (STL Template Klassen)

template <typename T>struct Pair{

T element1;T element2;

};

Pair <int> p;



};

Pair <int> p;

Bei Template-Klassen müssen die Argumente immer explizit angegeben werden

Defaults für Template-ParameterFür Template-Klassen können Default-Argumente definiert werden:

Nachfolgende Parameter müssen dann auch Defaults haben.

template <typename T = int>struct Pair{


};

Pair < > p;

template <typename T = int>struct Pair{


};

Pair < > p;

Default nur bei Template-Klassen, nicht bei Template-Funktionen

Template BeispieleFrage: Wozu kann man die Argumente von Template-Klassen verwenden?

– Beispiel: Typen für Member


T element1;T element2;T get_max();void set_both(T elm1, T elm2);

};


T element1;T element2;T get_max();void set_both(T elm1, T elm2);

};

Hinweis für den Compiler: „hier kommt ein Type!“

typename steht vor ...1. Template-Argumenten, die Typen sind (keine Konstanten)2. Typen, die von Template-Argumenten abhängen

typename

template <typename T>struct A{

typename T::Alphabet x; // abhängig, T ist TemplateArgtypedef int MyInteger;

};

A<char>::MyInteger y; // char ist kein TemplateArg

template <typename T>struct A{

typename T::Alphabet x; // abhängig, T ist TemplateArgtypedef int MyInteger;

};

A<char>::MyInteger y; // char ist kein TemplateArg

Achtung: In der originalen Fassung von C++ wurde „class“ statt „typename“ für offene Typen verwendet.

Typen von Klassentemplates können als eine Art "Pattern" angegeben werden:

"Patterns" von Template Typen

template <typename T1, typename T2>struct MyClass;

template <typename T>void function1 (T & obj);

template <typename T1, typename T2>void function2 (MyClass<T1, T2> & obj);

template <typename T>void function3 (MyClass<T, int> & obj);

template <typename T1, typename T2>struct MyClass;

template <typename T>void function1 (T & obj);

template <typename T1, typename T2>void function2 (MyClass<T1, T2> & obj);

template <typename T>void function3 (MyClass<T, int> & obj);

Template SpezialisierungTemplates können für bestimmte Template-Argumente spezialisiert werden.

Grund:– foo ist in MyClass<int> nicht bekannt.

template <typename T>struct MyClass { int foo; };

template < >struct MyClass <int>{ int x; };

MyClass<int> obj;obj.x = 17;

obj.foo = 18; // ERROR! Keine Vererbung

template <typename T>struct MyClass { int foo; };

template < >struct MyClass <int>{ int x; };

MyClass<int> obj;obj.x = 17;

obj.foo = 18; // ERROR! Keine Vererbung

Quiz: Was wird ausgegeben?template <typename T> struct C {

static void f() { std::cout << "allgemein"; }};

template < > struct C <char*> {

static void f() { std::cout << "speziell"; }};

template <typename T> void call_f(T & t){

C<T>::f();}

typedef char * c_ptr;c_ptr x;call_f(x);

template <typename T> struct C {





C<T>::f();}


Quiz: Was wird ausgegeben?template <typename T> struct C {





C<T>::f();}







C<T>::f();}


Quiz: Und jetzt?template <typename T> struct C {





C<T>::f();}

call_f("hallo");






C<T>::f();}

call_f("hallo");

Quiz: Und jetzt?template <typename T> struct C {





C<T>::f();}

call_f("hallo");






C<T>::f();}

call_f("hallo");

const char*const char*

TEMPLATE SUBCLASSING

Das Delegation-ProblemProblem: Es sei z.B. folgendes Programm gegeben:

struct Car { void refill() { cout << ”Gas Please”; }

void drive() { if (tank.empty()) this>refill(); ... }};

struct ElectricCar: Car { // Override function from Car void refill() { cout << ”Energy Please”; }};




Das Delegation-ProblemProblem: Was passiert hier?







ElectricCar e;e.drive();ElectricCar e;e.drive();

?

Das Delegation-ProblemAusgabe: Gas Pleases

Lösung:virtual functions







ElectricCar e;e.drive();ElectricCar e;e.drive();

struct Car { virtual void refill()

{ ... }};

struct Car { virtual void refill()

{ ... }};

Wie funktioniert virtual?Prinzip: Objekt hält Zeiger auf eine Tabelle mit Zeigern auf die richtigen

Funktionen

ElectricCar e

VTablesObjects Methods

Car::drive

Car::refill

ElectricCar::refill

0 refill1 drive

0 refill1 drive

Car

ElectricCar

Pointer

Eigenschaften virtueller Funktionendynamic binding

– Die tatsächlich aufgerufene Funktion wird erst zur Laufzeit bestimmt

Nachteile des dynamic binding– zusätzlicher Speicherbedarf pro Objekt– langsamer, indirekter Sprung– kein Inlining

Beobachtung– oft braucht man gar kein dynamic binding– Typen stehen schon zur Compile-Zeit fest

Template SubclassingEine alternative Lösung des Delegation-Problems mit static binding

Bisher (objektorientiert):

struct Car { /*Car*/ };struct ElectricCar : Car { /*ElectricCar*/ };struct Car { /*Car*/ };struct ElectricCar : Car { /*ElectricCar*/ };

Template SubclassingSchritt 1: “Template Spezialisierung statt Ableitung”

template <typename T> struct Car { /*Car*/ };

struct ElectricCar;

template <> struct Car <ElectricCar> { /*ElectricCar*/ };

template <typename T> struct Car { /*Car*/ };

struct ElectricCar;

template <> struct Car <ElectricCar> { /*ElectricCar*/ };

ElectricCar ist ein Tag, das nur deklariert werden muss

Template Subclassing (II)Schritt 2: “Globale Funktionen statt Member Funktionen”

template <typename T>void refill (Car<T> & obj){

std::cout << “Gas Please"; ... }

void refill (Car<ElectricCar> & obj){

std::cout << ”Energy Please"; ... }

template <typename T>void drive (Car<T> & obj){

refill(obj); ... }

template <typename T>void refill (Car<T> & obj){

std::cout << “Gas Please"; ... }

void refill (Car<ElectricCar> & obj){

std::cout << ”Energy Please"; ... }

template <typename T>void drive (Car<T> & obj){

refill(obj); ... }

Template Subclassing (III)Template Subclassing löst das Delegation Problem:

Car<ElectricCar> car;drive(car);

// Output: “Energy Please"

Car<ElectricCar> car;drive(car);

// Output: “Energy Please"

AnwendungsbeispielGesucht: Funktion, die das größte Element eines Feldes bestimmt

– Gegeben ist eine Feld von Zeigern auf eigentliche Elemente– Vergleichsfunktion soll frei wählbar sein

Lösung 1: Objektorientiert– Basisklasse Comparable mit virtueller Vergleichsfunktion less– Definiere Elementtyp als Kindklasse und überlade less

Lösung 2: Templates– Definiere globale less-Funktion und templatisiere maxArg– Spezialisiere less für Elementtyp

Objektorientiertstruct Comparable{ virtual bool less(Comparable &right) {

return *this < right;}

};

struct Element: public Comparable{ int a; bool less(Comparable &right) { return a < static_cast<Element&>(right).a; }};

Comparable* maxArg(Comparable* arr[], int size){ Comparable *max = NULL; for (int i = 0; i < size; ++i) if (max == NULL || *max.less(*arr[i])) max = arr[i];

return max;}

struct Comparable{ virtual bool less(Comparable &right) {

return *this < right;}

};

struct Element: public Comparable{ int a; bool less(Comparable &right) { return a < static_cast<Element&>(right).a; }};

Comparable* maxArg(Comparable* arr[], int size){ Comparable *max = NULL; for (int i = 0; i < size; ++i) if (max == NULL || *max.less(*arr[i])) max = arr[i];

return max;}

Templatestemplate <typename T>inline bool less(T &left, T &right){ return left < right; // allgemein}

template < >inline bool less(Element &left, Element &right){ return left.a < right.a; // speziell}

template <typename T>T * maxArg(T *arr[], int size){ T *max = NULL; for (int i = 0; i < size; ++i) if (max == NULL || less(*max, *arr[i])) max = arr[i];

return max;}

template <typename T>inline bool less(T &left, T &right){ return left < right; // allgemein}

template < >inline bool less(Element &left, Element &right){ return left.a < right.a; // speziell}

template <typename T>T * maxArg(T *arr[], int size){ T *max = NULL; for (int i = 0; i < size; ++i) if (max == NULL || less(*max, *arr[i])) max = arr[i];

return max;}

VergleichObjektorientiert mit virtueller Funktion

– Es existiert genau eine maxArg-Funktion– Indirektion beim Lesen der Funktionsadresse von less– Sprung und Rücksprung, Stackframe auf- und abbauen

Templates und inline– Für jeden benutzten Elementtyp wird eine eigene maxArg-Funktion

erzeugt– less-Funktion wird direkt in maxArg eingebaut (inline)

Laufzeitmessung mit 1 Mrd. Elementen– 3350 ms mit OOP– 2150 ms mit Templates

BEMERKUNGEN ZUR P-AUFGABE

Tipps zu Aufgabe 2• Enums um Aufzählungstypen zu definieren.

enum TracebackDirection{

TRACEBACK_DIRECTION_DIAGONAL,TRACEBACK_DIRECTION_HORIZONTAL,TRACEBACK_DIRECTION_VERTICAL,TRACEBACK_DIRECTION_NONE

};

std::vector<TracebackDirection> traceback;

enum TracebackDirection{

TRACEBACK_DIRECTION_DIAGONAL,TRACEBACK_DIRECTION_HORIZONTAL,TRACEBACK_DIRECTION_VERTICAL,TRACEBACK_DIRECTION_NONE

};

std::vector<TracebackDirection> traceback;

Tipps zu Aufgabe 2

• Speichern einer Matrix im eindimensionalen Raum

// Matriximplementierung mit 2 Vektoren.std::vector<int> rows(20, 0);std::vector<std::vector<int> > matrix(15, rows)

int val = matrix[3][4];

// Matriximplementierung mit einem Vektor.std::vector<int> matrix(20 * 15, 0);

int val = matrix[3 * 15 + 4];

// Matriximplementierung mit 2 Vektoren.std::vector<int> rows(20, 0);std::vector<std::vector<int> > matrix(15, rows)

int val = matrix[3][4];

// Matriximplementierung mit einem Vektor.std::vector<int> matrix(20 * 15, 0);

int val = matrix[3 * 15 + 4];

Documents

2. Object Oriented Programming und Templates · OOP Prinzipien Abstraktion – Funktionalität gegeben über Schnittstellen (Memberfunktionen) wie bei abstrakten Datentypen – Komplexität