Embed Size (px)
Citation preview
Informatik 1Woche 10Moritz Schneider
Moritz Schneider 9. Mai 2019 1
Heute:
1. Repetition: Operator Overloading
2. Pointer
Moritz Schneider 9. Mai 2019 2
Übungen
Hat alles geklappt?
Moritz Schneider 9. Mai 2019 3
Operator Überladen I
• Beispiel: Komplexe Zahlen: class Complex {...};
• +, -, *, / sollen auch auf Komplexen Zahlen definiert seinComplex operator +( const Complex &a, const Complex &b);
• binary operator ==bool operator ==( const Complex &a, const Complex &b);
• unary operator - (z.B. -c)?Complex operator -( const Complex &a);
Moritz Schneider 9. Mai 2019 4
Operator Überladen II
• Beispiel: Komplexe Zahlen
• Einlesen?
// POST: Reads value into t.std:: istream& operator >> (std:: istream& in, Complex& t);
• Ausgeben?
// POST: Outputs this into the streamstd:: ostream& operator << (std:: ostream& out , const Complex& t);
Moritz Schneider 9. Mai 2019 5
Operator Überladen III
• Wir definieren Print-Format: "[Re(z),Im(z)]", z.B. "[1,2]"
• Beispiel Ausgeben
std :: ostream & operator << (std :: ostream &out , const Complex & t) {out << ’[’ << t.real << ’,’ << t.imag << ’]’;return out;
}
• Durch Rückgabe des Streams out kann man diese hintereinanderhängen:
Complex a,b = ..;std :: ostream out = std :: cout; // ist Instanz von std :: ostreamout <<a<<b; // ruft auf: operator <<(out , a) .. operator (out , b)
Moritz Schneider 9. Mai 2019 6
Operator Überladen IV
• Wir definieren Print-Format: "[Re(z),Im(z)]", z.B. "[1,2]"• Beispiel Einlesen
std :: istream & operator >> (std :: istream &in , Complex & t) {char open_b , close_b , comma;if (in >> open_b >> t.real >> comma >> t.imag >> close_b
&& open_b == ’[’ && comma == ’,’ && close_b == ’]’) {// here , operator >>( std :: istream , char) (built -in) is called// read successfully
} else {// Failed to read.in. setstate (std :: ios :: failbit );
}return in;
}Moritz Schneider 9. Mai 2019 7
References Recap I
Was wird ausgegeben?
int a = 1;int b = 1;int& x = a;int& y = x;y = b;std::cout << a << "␣" << b << "␣" << x << "␣" << y;
→ 2 2 2 2
Moritz Schneider 9. Mai 2019 8
References Recap II
• Referenzen koennen nicht mehr veraendert werden– Der Wert auf den gezeigt wird schon:
y = b // der wert auf den y zeigt wird veraendert– Nicht möglich: y nachträglich auf b zeigen zu lassen!
• Pointer sind ähnlich wie Referenzen
• Pointer speichern die Adressen der Variablen im Speicher
• Daher: Pointer können verändert werden→ Die Adresse, auf die sie zeigen wird geändert
Moritz Schneider 9. Mai 2019 9
Introduction to Pointers
Pointer Program
2
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863
Pointer Program
3
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862
5
int a
863
Pointer Program
4
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862
8405
int a int* x
863
Pointer Program
5
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
x
Visualization
840 841 842 843 844 845 846 847 848 849 850 851
5
int a
852 853 854 855 856 857 858 859 860 861 862
840
int* x
863
Pointer Program
6
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
x
840 841 842 843 844 845 846 847 848 849 850 851
5
int a
852 853 854 855 856 857 858 859 860 861 862
840
int* x
863
Pointer Program
7
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
x
840 841 842 843 844 845 846 847 848 849 850 851
5 d
int a char c
852 853 854 855 856 857 858 859 860 861 862
840
int* x
863
Pointer Program
8
int a = 5;
int* x = &a;
char c = 'd';
char* z = &c;
x z
840 841 842 843 844 845 846 847 848 849 850 851 858 859 860 861 862
8505 d
int a char c char* z
852 853 854 855 856 857
840
int* x
863
Pointers - Zweites Beispiel
int a = 5;int b = 7;int* x = 0; // always initialize empty pointers to 0 (NULL), if
// you do not want to immediately assign them!x = &a; // the address of a is written to x; x points to astd :: cout << a << "\n"; // outputs 5std :: cout << *x << "\n"; // outputs 5 toostd :: cout << x << "\n"; // outputs something like 0 x28fef8 ( address of a)std :: cout << &a << "\n"; // outputs something like 0 x28fef8 ( address of a) toox = &b; // x now points to b*x = 1; // changes value of b to 1
Moritz Schneider 9. Mai 2019 10
Operators & / *
& has three distinct meanings in c++
1. the bitwise AND operator (eg. z = x & y;)
2. to declare a variable as a reference (eg. int& y = x;)
3. to take the address of a variable (address operator) (eg. int *ptr_a = &a;)
* has three distinct meanings in c++
1. as the arithmetic multiplication operator (eg. z = x * y;)
2. to declare a pointer variable (eg. int *ptr_a = &a;)
3. to take the content of a variable via its pointer (dereference operator) (eg.int a = *ptr_a;)
Moritz Schneider 9. Mai 2019 11
Pointers
3 -8 1 5 -3 4 1 7 2 7
Pointer Program
2
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6
4 1 7 2 7
Pointer Program
3
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 2 -1a
4 1 7 2 7
Pointer Program
4
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 2 -1
ptr
a
4 1 7 2 7
Pointer Program
5
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 2 -1
ptr
a
4 1 7 7
Pointer Program
6
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 2 -1
ptr
8my_inta
4 1 7 7
Pointer Program
7
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 2 -1
ptr
8my_inta
4 1 7 7
Pointer Program
8
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 18 -1
ptr
8my_inta
4 1 7 7
Pointer Program
9
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 18 -1
ptr past
8my_inta
4 1 7 7
Pointer Program
10
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 18 -1
ptr past
Output:true
Because ptr is"to the left" of
past.
Output:true
Because ptr is"to the left" of
past.
8my_inta
4 1 7 7
Pointer Program
11
int* a = new int[5]{0, 8, 7, 2, -1};int* ptr = a; // pointer assignment++ptr; // shift to the rightint my_int = *ptr; // read targetptr += 2; // shift by 2 elements*ptr = 18; // overwrite targetint* past = a+5;std::cout << (ptr < past) << "\n"; // compare pointers
1-6 0 8 7 18 -1
ptr past
8my_inta
Exercise!
Pointer Program
Find and fix at least 3 problems in the following program.
(From: Script Exercise 117) 13
#include <iostream>int main () { int* a = new int[7]{0, 6, 5, 3, 2, 4, 1}; int* b = new int[7]; int* c = b;
// copy a into b using pointers for (int* p = a; p <= a+7; ++p) *c++ = *p;
// cross-check with random access for (int i = 0; i <= 7; ++i) if (a[i] != c[i]) std::cout << "Oops, copy error...\n";
return 0;}
Pointer Program
(From: Script Exercise 117) 14
#include <iostream>int main () { int* a = new int[7]{0, 6, 5, 3, 2, 4, 1}; int* b = new int[7]; int* c = b;
// copy a into b using pointers for (int* p = a; p <= a+7; ++p) *c++ = *p;
// cross-check with random access for (int i = 0; i <= 7; ++i) if (a[i] != c[i]) std::cout << "Oops, copy error...\n";
return 0;}
p = a+7 is dereferenced
Solution: Use < instead of <=
p = a+7 is dereferenced
Solution: Use < instead of <=
Pointer Program
(From: Script Exercise 117) 15
#include <iostream>int main () { int* a = new int[7]{0, 6, 5, 3, 2, 4, 1}; int* b = new int[7]; int* c = b;
// copy a into b using pointers for (int* p = a; p <= a+7; ++p) *c++ = *p;
// cross-check with random access for (int i = 0; i <= 7; ++i) if (a[i] != c[i]) std::cout << "Oops, copy error...\n";
return 0;}
p = a+7 is dereferenced
Solution: Use < instead of <=
p = a+7 is dereferenced
Solution: Use < instead of <=
Same problem as aboveSame problem as above
Pointer Program
(From: Script Exercise 117) 16
#include <iostream>int main () { int* a = new int[7]{0, 6, 5, 3, 2, 4, 1}; int* b = new int[7]; int* c = b;
// copy a into b using pointers for (int* p = a; p <= a+7; ++p) *c++ = *p;
// cross-check with random access for (int i = 0; i <= 7; ++i) if (a[i] != c[i]) std::cout << "Oops, copy error...\n";
return 0;}
Same problem as aboveSame problem as above
c doesn’t point to b[0] anymore.
Solution: Use b instead of c
c doesn’t point to b[0] anymore.
Solution: Use b instead of c
p = a+7 is dereferenced
Solution: Use < instead of <=
p = a+7 is dereferenced
Solution: Use < instead of <=
Exercise – Applying Pointers
Exercise – Applying Pointers
• Apply this function…
• … to this example-array:
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 2
1 3 -8 1 5 -3 4
b oe o+(e-b)
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 3
1 3 -8 1 5 -3 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 4
1 3 -8 1 5 -3 4
b oe
truetrue
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 5
1 3 -8 1 5 -3 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 6
1 3 -8 1 3 -3 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 7
1 3 -8 1 3 -3 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 8
1 3 -8 1 3 -3 4
b oe
truetrue
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 9
1 3 -8 1 3 -3 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 10
1 3 -8 1 3 1 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 11
1 3 -8 1 3 1 4
b oe
Exercise – Applying Pointers
void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 12
1 3 -8 1 3 1 4
b oe
falsefalse
Exercise – Applying Pointers
• Now determine a POST-condition for the function.
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 13
Exercise – Applying Pointers
• Something like this:
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid ranges// POST: The range [b, e) is copied in reverse// order into the range [o, o+(e-b))void f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
(From: Script Exercise 113) 14
Exercise – Valid Inputs
Exercise – Valid Inputs
• Which of these inputs are valid?
(From: Script Exercise 113) 16
int* a = new int[5];// Initialise a. a) f(a, a+5, a+5); b) f(a, a+2, a+3); c) f(a, a+3, a+2);
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
int* a = new int[5];// Initialise a. a) f(a, a+5, a+5); b) f(a, a+2, a+3); c) f(a, a+3, a+2);
Exercise – Valid Inputs
• Which of these inputs are valid?
(From: Script Exercise 113) 17
[o,o+(e-b))is out of bounds
[o,o+(e-b))is out of bounds
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
int* a = new int[5];// Initialise a. a) f(a, a+5, a+5); b) f(a, a+2, a+3); c) f(a, a+3, a+2);
Exercise – Valid Inputs
• Which of these inputs are valid?
(From: Script Exercise 113) 18
[o,o+(e-b))is out of bounds
[o,o+(e-b))is out of bounds
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
int* a = new int[5];// Initialise a. a) f(a, a+5, a+5); b) f(a, a+2, a+3); c) f(a, a+3, a+2);
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
Exercise – Valid Inputs
• Which of these inputs are valid?
(From: Script Exercise 113) 19
[o,o+(e-b))is out of bounds
[o,o+(e-b))is out of bounds
Ranges not disjoint
Ranges not disjoint
Exercise – const Correctness
Exercise – const Correctness
• Make the function const-correct.
(From: Script Exercise 113) 21
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (int* b, int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
Exercise – const Correctness
• Make the function const-correct.
(From: Script Exercise 113) 22
// PRE: [b, e) and [o, o+(e-b)) are disjoint// valid rangesvoid f (const int* const b, const int* e, int* o) { while (b != e) { --e; *o = *e; ++o; }}
Shortcut: The − >
struct C{int b;
};...C a;C* c = &a; // pointer to a
a.b = 3; // worksc.b = 3; // compiler error(*c).b = 3; // one way to get b. Paranthesis needed
// as . has higher precedence than *c->b = 3; // same effect but nicer to reada->b = 3; // compiler error
Moritz Schneider 9. Mai 2019 12
CodeExpert: Push Back
Push Back on CodeExpert
Moritz Schneider 9. Mai 2019 13
CodeExpert: Push Back
The files vector_array.h and vector_array.cpp contain a simplified version of theavec vector from the lecture slides. Implement the push_back method that appendsan element at the end of the vector. On a high level this involves the following steps:
1. Allocating a new memory block that is larger by one element.
2. Copying all elements from the old memory block to the new one.
3. Adding the new element to the end of the new memory block.
Moritz Schneider 9. Mai 2019 14
Push Back: Solution// PRE: source_begin points to the first element to be copied .// PRE: source_ends points to the element after the last element to be copied .// PRE: destination_begin points to the first element of the destination memory block// PRE: The target memory location has at least as many elements as there are// elements between source_begin and source_end .void copy_range (int* const source_begin , int* source_end , int* destination_begin ) {
int* dst = destination_begin ;for ( const int* src = source_begin ; src != source_end ; ++ src) {
*dst = *src;++ dst;
}}
// POST: this contains the same sequence as before with the// new_element appended at the end.void avec :: push_back (int new_element ) {
int* const new_elements = new int[this -> count + 1];copy_range (this ->elements , this -> elements + this ->count , new_elements );new_elements [this -> count ] = new_element ;this -> count ++;this -> elements = new_elements ;
}
Moritz Schneider 9. Mai 2019 15
Fragen?
Moritz Schneider 9. Mai 2019 16
