Informatik I - Ãœbung 12

Pascal Schärli

pascscha@student.ethz.ch

24.05.2019

Was gibts heute?

  • Self-Asessment
  • Best-Of Vorlesung
    • Memory Management
  • Vorbesprechung
  • Prüfungstipps

Pascal Schärli 24.05.2019

Self-Assesment

Pascal Schärli 24.05.2019

1 Pointers

Pascal Schärli 24.05.2019

int a = 4;
int& b = a;
int* c = &a;
Ausdruck Ungültig 4 Adresse von a Adresse von c
std::cout << b;
std::cout << *b;
std::cout << &b;
std::cout << c;
std::cout << *c;
std::cout << &c;

2 Iteratoren

Pascal Schärli 24.05.2019

int f(const int* begin, const int* end) {
    int val1 = *begin;
    if (++begin != end) {
        const int val2 = f(begin, end);
        if (val2 > val1) {
            val1 = val2;
        }
    }
    return val1;
}

int g(const int* begin, const int* end) {
    int val = *begin;
    for (const int* it=++begin; it != end; ++it) {
        if (*it > val) {
            val = *it;
        }
    }
    return val;
}
  • f und g haben dieselbe Vorbedingung
     
  • f und g haben dieselbe Nachbedingung
// PRE:  The interval [begin, end) is valid 
//        and not empty
// POST: Returns the maximum value of the
//         interval

2 Iteratoren

Pascal Schärli 24.05.2019

int f(const int* begin, const int* end) {
    int val1 = *begin;
    if (++begin != end) {
        const int val2 = f(begin, end);
        if (val2 > val1) {
            val1 = val2;
        }
    }
    return val1;
}
  • Was ist der Wert der Variable result nach dem Aufruf?
     
  • Wie oft wird f insgesamt aufgerufen?
{
    const int my_size = 7;
    int* my_values = new int[my_size]{ 3, 8, 1,
                                  12, 20, 2, 6 };
    int result = f(my_values, my_values+my_size);
}
20
7

3 Felder und Arrays

Pascal Schärli 24.05.2019

int* a = new int[8]{3, 1, -3, -2, 10, 0, 0, 0};
a[7] = 5;
*(a + 3) = 4;
int* p = a + 4;
*(a + a[3] + *(p - 2)) = *(p + 3) - 9;

3

1

-3

-2

10

0

0

0

3

1

-3

4

10

0

0

5

3

-4

-3

4

10

0

0

5

4 Structs und Operatoren

Pascal Schärli 24.05.2019

#include<iostream>

struct vector_2 { double x; double y; };

// POST: the scalar product of v and w is returned

{

}

// POST: the scaled vector lambda * v is returned

{



}

int main() {
    vector_2 v = {1.0, 2.0}; vector_2 w = {3.0, 4.0};
    std::cout << v * w << std::endl; // 11
    vector_2 u = 5.0 * v;
    std::cout << ’(’ << u.x << ", " << u.y << ’)’ << "\n"; // (5, 10)
    return 0;
}
#include<iostream>

struct vector_2 { double x; double y; };

// POST: the scalar product of v and w is returned
double operator* (vector_2 v, vector_2 w)
{

}

// POST: the scaled vector lambda * v is returned

{



}

int main() {
    vector_2 v = {1.0, 2.0}; vector_2 w = {3.0, 4.0};
    std::cout << v * w << std::endl; // 11
    vector_2 u = 5.0 * v;
    std::cout << ’(’ << u.x << ", " << u.y << ’)’ << "\n"; // (5, 10)
    return 0;
}
#include<iostream>

struct vector_2 { double x; double y; };

// POST: the scalar product of v and w is returned
double operator* (vector_2 v, vector_2 w)
{
    return v.x * w.x + v.y * w.y;
}

// POST: the scaled vector lambda * v is returned

{



}

int main() {
    vector_2 v = {1.0, 2.0}; vector_2 w = {3.0, 4.0};
    std::cout << v * w << std::endl; // 11
    vector_2 u = 5.0 * v;
    std::cout << ’(’ << u.x << ", " << u.y << ’)’ << "\n"; // (5, 10)
    return 0;
}
#include<iostream>

struct vector_2 { double x; double y; };

// POST: the scalar product of v and w is returned
double operator* (vector_2 v, vector_2 w)
{
    return v.x * w.x + v.y * w.y;
}

// POST: the scaled vector lambda * v is returned
vector_2 operator* (double lambda, vector_2 v)
{



}

int main() {
    vector_2 v = {1.0, 2.0}; vector_2 w = {3.0, 4.0};
    std::cout << v * w << std::endl; // 11
    vector_2 u = 5.0 * v;
    std::cout << ’(’ << u.x << ", " << u.y << ’)’ << "\n"; // (5, 10)
    return 0;
}
#include<iostream>

struct vector_2 { double x; double y; };

// POST: the scalar product of v and w is returned
double operator* (vector_2 v, vector_2 w)
{
    return v.x * w.x + v.y * w.y;
}

// POST: the scaled vector lambda * v is returned
vector_2 operator* (double lambda, vector_2 v) {
    vector_2 result;
    result.x = lambda * v.x;
    result.y = lambda * v.y;
    return result;
}

int main() {
    vector_2 v = {1.0, 2.0}; vector_2 w = {3.0, 4.0};
    std::cout << v * w << std::endl; // 11
    vector_2 u = 5.0 * v;
    std::cout << ’(’ << u.x << ", " << u.y << ’)’ << "\n"; // (5, 10)
    return 0;
}

5 Dynamische Datentypen

Pascal Schärli 24.05.2019

class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return p->key;
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert ( first_node != nullptr );
        assert ( first_node->next != nullptr );
        list_node∗ p = first_node->next;
        first_node->next = first_node->next->next;
        delete p;
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return p->key;
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert ( first_node != nullptr );
        assert ( first_node->next != nullptr );
        list_node∗ p = first_node->next;
        first_node->next = first_node->next->next;
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return p->key;
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert ( first_node != nullptr );
        assert ( first_node->next != nullptr );
        list_node∗ p = first_node->next;
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return p->key;
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert ( first_node != nullptr );
        assert ( first_node->next != nullptr );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return p->key;
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert ( first_node != nullptr );
        assert (                             );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return p->key;
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert (                       );
        assert (                             );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            p = p->next;
        return 
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert (                       );
        assert (                             );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while ( p->next != nullptr)
            
        return 
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert (                       );
        assert (                             );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = first_node;
        while (                   )
            
        return 
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert (                       );
        assert (                             );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (first_node != nullptr);
        const list_node∗ p = 
        while (                   )
            
        return 
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert (                       );
        assert (                             );
        list_node∗ p = 
        
        
    }
};
class list {
private :
    list_node∗ first_node ;
public :
    ...
    // PRE: ∗ this is not empty
    // POST: the key of the last element in ∗ this is returned
    int last () const {
        assert (                     );
        const list_node∗ p = 
        while (                   )
            
        return 
    }

    // PRE: ∗ this contains at least two elements
    // POST: the second element is removed from ∗ this
    void remove_second ()
    {
        assert (                       );
        assert (                             );
        list_node∗ p = 
        
        
    }
};

Vorlesung

Pascal Schärli 24.05.2019

New & Delete

Pascal Schärli 24.05.2019

  • Mit dem Keyword new kann man Pointer erstellen, welche auf Daten zeigen die niemals out of scope gehen.
  • Im Gegenzug muss man selber die Daten mit dem Keyword delete löschen falls man diese nicht mehr braucht.
  • Jedes new braucht ein delete

New & Delete

#include <iostream>

int* create_value(){
    int* x = new int(5);
    return x;
}

int main(){
    int* ptr = create_value();

    std::cout << *ptr << "\n";

    delete ptr;

    return 0;
}
#include <iostream>

int* create_array(){
    int* a = new int[5];

    for(unsigned int i = 0; i < 5; i++){
        a[i] = i;
    }

    return a;
}

int main(){
    int* a = create_array();

    std::cout << *a << " ";
    std::cout << *(a + 1) << " ";
    std::cout << *(a + 2) << " ";
    std::cout << *(a + 3) << " ";
    std::cout << *(a + 4) << " ";

    delete[] a;

    return 0;
}
0 1 2 3 4
5

Pascal Schärli 24.05.2019

New & Delete

Pascal Schärli 24.05.2019

  • Innerhalb von Klassen können auch Elemente mit new Erstellt werden.
  • Diese müssen spätestens im destruktor (~Vec) gelöscht werden
#include <iostream>

class A {
    int* array;
public:
    A(unsigned int size) {
        std::cout << "create\n";
        array = new int[size];
    }

    ~A() {
        std::cout << "delete\n";
        delete[] array;
    }
};

int main(){
    A a(5);
    a.array[3] = 0;
    return 0;
}

Array wurde mit new erstellt

Array muss im destructor gelöscht werden.

"create"

"delete" (out of scope)

Pascal Schärli 24.05.2019

class Cell {
  int value;
public:

  Cell(): value(0) {
    std::cerr << "default constructor" << std::endl;
  }

  Cell(int val): value(val) {
    std::cerr << "overloaded constructor: value=" << value << std::endl;
  }
};
void step1() {
  Cell demo(1);
  Cell* demo_ptr = new Cell;
}
default constructor
default constructor

Was ist der Output von step1?

overloaded constructor: value=1
overloaded constructor: value=0
overloaded constructor: value=1
default constructor
default constructor
overloaded constructor: value=0

Pascal Schärli 24.05.2019

class Cell {
  int value;
public:

  Cell(): value(0) {
    std::cerr << "default constructor" << std::endl;
  }

  Cell(int val): value(val) {
    std::cerr << "overloaded constructor: value=" << value << std::endl;
  }
};
void step1() {
  Cell demo(1);
  Cell* demo_ptr = new Cell;
}
overloaded constructor: value=1
default constructor

Pascal Schärli 24.05.2019

class Cell {
  int value;
public:

  Cell(): value(0) {
  //  std::cerr << "default constructor" << std::endl;
  }

  Cell(int val): value(val) {
  //  std::cerr << "overloaded constructor: value=" << value << std::endl;
  }

  ~Cell() {
    std::cerr << "destructor: value=" << value << std::endl;
  }
};
void step1() {
  Cell demo(1);
  Cell* demo_ptr = new Cell;
}
destructor value=1
destructor value=0

Was ist der Output von step1?

destructor value=0
destructor value=1
destructor value=1
destructor value=0

Pascal Schärli 24.05.2019

class Cell {
  int value;
public:

  Cell(): value(0) {
  //  std::cerr << "default constructor" << std::endl;
  }

  Cell(int val): value(val) {
  //  std::cerr << "overloaded constructor: value=" << value << std::endl;
  }

  ~Cell() {
    std::cerr << "destructor: value=" << value << std::endl;
  }
};
void step1() {
  Cell demo(1);
  Cell* demo_ptr = new Cell;
}
destructor value=1

Die mit new erstellte Klasse geht nicht out of scope und wird daher nicht gelöscht.

-> Memory Leak!

Pascal Schärli 24.05.2019

class Cell {
  int value;
public:

/* constructor, destructor */

Cell(const Cell& other) {
  value = other.value;
  std::cerr << "copy constructor: value=" << value << std::endl;
}

Cell& operator= (const Cell& other) {
  value = other.value;
  std::cerr << "assignment operator: value=" << value << std::endl;
  return *this;
}

};
void step2() {
  Cell demo(3);
  Cell demo2 = demo;
  demo = demo2;
}
copy constructor: value=3
copy constructor: value=3

Was ist der Output von step2?

copy constructor: value=3
assignment operator: value=3
assignment operator: value=3
copy constructor: value=3
assignment operator: value=3
assignment operator: value=3

Pascal Schärli 24.05.2019

  • Wenn eine neue Klasse erstellt wird, bedeutet "=" den Copy constructor
     
  • Wenn die Klasse bereits existiert, ist es der Assignment operator
class Cell {
  int value;
public:

/* constructor, destructor */

Cell(const Cell& other) { // COPY CONSTRUCTOR
  value = other.value;
  std::cerr << "copy constructor: value=" << value << std::endl;
}

Cell& operator= (const Cell& other) { // ASSIGNMENT OPERATOR
  value = other.value;
  std::cerr << "assignment operator: value=" << value << std::endl;
  return *this;
}

};
void step2() {
  Cell demo(3);
  Cell demo2 = demo;
  demo = demo2;
}
copy constructor: value=3
assignment operator: value=3

Welches Programm ist Fehlerfrei?

Pascal Schärli 24.05.2019

class A{
    int array[5];
public:
    A(){
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }

    ~A(){
        delete array;
    }
};
class B {
    int array[5];
public:
    B(){
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }
};
class C {
    int* array;
public:
    C(){
        array = new int[5];
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }

    ~C(){
        delete array;
    }
};
class D {
    int* array;
public:
    D(){
        array = new int[5];
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }
};

Welches Programm ist Fehlerfrei?

Pascal Schärli 24.05.2019

class A{
    int array[5];
public:
    A(){
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }

    ~A(){
        delete array;
    }
};
class A{
    int array[5];
public:
    A(){
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }




};

Variablen welche nicht mit new erstellt wurden müssen und dürfen nicht mit delete gelöscht werden.

Welches Programm ist Fehlerfrei?

Pascal Schärli 24.05.2019

class C {
    int* array;
public:
    C(){
        array = new int[5];
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }

    ~C(){
        delete[] array;
    }
};

Arrays müssen mit delete[] gelöscht werden, sonst wird nur das erste Element gelöscht

class C {
    int* array;
public:
    C(){
        array = new int[5];
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }

    ~C(){
        delete array;
    }
};

Welches Programm ist Fehlerfrei?

Pascal Schärli 24.05.2019

class D {
    int* array;
public:
    D(){
        array = new int[5];
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }

    ~D(){
        delete[] array;
    }
};

Arrays müssen mit delete[] gelöscht werden, sonst wird nur das erste Element gelöscht

class D {
    int* array;
public:
    D(){
        array = new int[5];
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }
};

Welches Programm ist Fehlerfrei?

Pascal Schärli 24.05.2019

class B {
    int array[5];
public:
    B(){
        for(unsigned int i = 0; i < 5; i++){
            array[i] = i;
        }
    }
};

Variablen welche nicht mit new erstellt wurden müssen und dürfen nicht mit delete gelöscht werden.

Welche Zeile ist falsch?

Pascal Schärli 24.05.2019

class Arr5 {
public:
    int* array;

    Arr5(){
        array = new int[5];
    }

    ~Arr5(){
        delete[] array;
    }
};

int main(){
    Arr5 a = Arr5();
    delete[] a.array;
    return 0;
}
array = new int[5];

delete[] array;

Arr5 a = Arr5();

delete[] a.array;

Welche Zeile ist falsch?

Pascal Schärli 24.05.2019

class Arr5 {
public:
    int* array;

    Arr5(){
        array = new int[5];
    }

    ~Arr5(){
        delete[] array;
    }
};

int main(){
    Arr5 a = Arr5();
    delete[] a.array;
    return 0;
}
  • Die Funktion main darf delete nicht auf a.array anwenden, da dieser von der Klasse Arr5 managed wird.
     
  • Sobald nachher~Arr5() aufgerufen wird, gibt es einen Segmentation fault, da die daten bereits gelöscht wurden.
     
  • ~Arr5() wird aufgerufen wenn a out of scope geht (am Ende von main)

Pascal Schärli 24.05.2019

Wir haben dieselbe Klasse wie zuvor, nur dass "value" jetzt ein Pointer ist.


Implementiert im File cell.cpp Einen destructor, einen constructor und einen assignment operator sodass keine memory leaks auftreten

class Cell {
  int* value;
public:
  Cell();
  Cell(int val);
  ~Cell();
  Cell(const Cell& other);
  Cell& operator= (const Cell& other);
  int get_value();
  void set_value(int new_value);
};

Vorbesprechung

Pascal Schärli 24.05.2019

Pascal Schärli 24.05.2019

  • Ihr bekommt verschiedene Programme, welche entweder Errors oder Memory Leaks haben
  • Findet bei jedem Programm den Fehler.
  • Falls es einen Error gibt, schreibt in welcher Zeile dieser vorkommen wird.

Tipps:

  • Jedes Programm hat irgend einen Fehler
  • Wenn ihr Probleme habt, schaut euch unsere Kahoot Aufgaben nochmals an.

Pascal Schärli 24.05.2019

  • Gegeben ist eine Implementation von einem Array-based Vector.
  • Dieser Vector wird mit einer fixen Grösse initialisiert und speichert seine Elemente in einem Array.
  • Schreibt einen
    1. Copy constructor.
    2. Assignment operator.
    3. Destructor.

Tipps:

  • Sehr ähnlich wie in der Aufgabe Memory Management
  • Verwendet den Copy constructor bei eurer Implementation vom Assignment operator

Pascal Schärli 24.05.2019

tracked* t1 = new tracked;
tracked* t2 = new tracked;

Smart s1 = Smart(t1);
Smart* s2 = new Smart(t2);
Smart s4;
{
  Smart s3 = s1;
      
  s1 = *s2;
  delete s2;
}
s4 = s1;
t1
1
ptr

count

s1

ptr

count

s2

t2
1
ptr

count

s3

ptr

count

s4

2
2
1
1
2
1: Wir erstellen ein Objekt vom typ tracked t1, welches wir in unseren smart-pointer speichern werden
2: Wir erstellen ein Objekt vom typ tracked t2, welches wir in unseren smart-pointer speichern werden
4: Smart::Smart(tracked* v){}

Wir erstellen einen neuen Smart Pointer s1, welcher auf t1 Zeigt.
s1 erstellt direkt auch einen counter mit Wert 1, welcher die Referenzen auf t1 zählt.
5: Smart::Smart(tracked* v){}

Wir erstellen einen neuen Smart Pointer s2, welcher auf t2 Zeigt.
s1 erstellt direkt auch einen counter mit Wert 1, welcher die Referenzen auf t2 zählt.
7: Smart::Smart(const Smart& src){}

Wir erstellen einen neuen Smart Pointer s3, welcher auf das selbe Objekt wie t1 zeigt.
s3 erhöht den counter um 1.
8: Smart::Smart(){}

Wir erstellen einen neuen Smart Pointer s4, welcher auf nullptr zeigt.
Der counter zeigt ebenfalls auf nullptr.
10: Smart& Smart::operator=(const Smart& src) {

s1 zeigt nun auf dassebe Objekt wie s2. Der alte counter wird verkleinert und der neue wird erhöht.
(achtung, falls count == 0 muss das alte objekt gelöscht werden)
11: Smart::~Smart() {}

s2 wird gelöscht. Der counter wird verkleinert.
(achtung, falls count == 0 muss das alte objekt gelöscht werden)
12: Smart::~Smart() {}

s3 geht out of scope. Der counter wird verkleinert.
Weil falls count == 0 muss das alte objekt gelöscht werden.
13: Smart& Smart::operator=(const Smart& src) {}

s4 zeigt nun auf dasselbe Objekt wie s3.
Der neue Counter wird erhöht.
Da kein alter Pointer existiert, darf dieser auch nicht verkleinert werden.

Prüfungstipps

Pascal Schärli 24.05.2019

Prüfungstipps

Pascal Schärli 24.05.2019

Generell

  • Macht euch einen Lernplan für die ganze Lernphase.
  • Löst nochmals viele Serien
  • Zu wenig lernen ist schlecht, zu viel aber genau so
    -> Gönnt euch Freizeit
     

Info I

  • Es gibt viele Alte Prüfungen, löst so viele wie möglich.
  • Der Prüfungsstil war bis jetzt gleich wie bei Prof. Friedrich
  • Viele Aufgaben sind jedes Jahr gleich
  • Programmiert in eurer Freizeit

Viel Spass!

Pascal Schärli 24.05.2019