### .pdf

```IBM Research – Zurich
C++ (4. Vorlesung)
LSP, Templates, Standard Library Algorithms
Thomas Gschwind <thg at zurich....>
1
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Agenda
The Liskov Substituion Principle
– Square
Rectangle
– Rectangle
Square
Templates
Standard Library Algorithms
2
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Squares and Rectangles
I had a colleague who was unsure whether to derive rectangle
from square or vice-versa. What would you recommend to
him?
Implement a set of sample programs illustrating various options
The programs should demonstrate why your solution is better
than the other solutions
3
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Squares and Rectangles
Shape
inherits
Line
Circle
Triangle
…
Class hierarchy for a vector graphics program
We have an abstract class Shape from which various geometric
shapes are being derived
4
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Liskov Substitution Principle
If for each object o1 of type S there is an object o2 of type
T such that for all programs P defined in terms of T, the
behaviour of P is unchanged when o1 is substituted for o2
then S is a subtype of T.
Put Simple: Every function/program must work the same
when it is invoked with a subclass instead of the expected
class. This is the responsibility of the subclasses!
5
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Square
Rectangle
class Rectangle {
private: int w, h;
public:
virtual void set_width(int wi) { w=wi; }
virtual void set_height(int he) { h=he; }
}
Rectangle
inherits
Square
class Square : public Rectangle {
public:
v. void set_width(int w) {
Rectangle::set_height(w);
Rectangle::set_width(w);
}
v. void set_height(int h) { set_width(h);
} }
6
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Square
Rectangle (cont’d)
What happens if we pass a Square to a function foo expecting a Rectangle?
Can we expect the function foo to know about Square?
Would it be OK if the function yields an unexpected outcome under the motto
garbage-in garbage-out?
No! Because we claim that a Square is a Rectangle!
void foo(Rectangle &r) {
r.set_width(5);
r.set_height(4);
assert((r.get_width()*r.get_height())
==20);
Rectangle
inherits
Square
}
7
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Square
Rectangle V2
class Rectangle {
private: int w, h;
public:
void set_width(int wi) { w=wi; }
void set_height(int he) { h=he; }
}
Rectangle
inherits
Square
class Square : public Rectangle {
public:
void set_width(int w) {
Rectangle::set_height(w);
Rectangle::set_width(w);
}
void set_height(int h) { set_width(h);
} }
8
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Square
Rectangle V2 (cont’d)
What happens if we pass a Square to a function foo expecting a
Rectangle?
The program works now as expected
However, since set_width/set_height are no longer virtual our
Square is now a Rectangle
==> This is not the solution either
void foo(Rectangle &r) {
r.set_width(5);
r.set_height(4);
assert((r.get_width()*r.get_height())
==20);
Rectangle
inherits
Square
}
9
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Rectangle
Square
Square has one field (height or width)
Rectangle adds another one for the
other dimension
– Makes sense from a memory usage point
of view
Square
inherits
Rectangle
Square has a method to set the length
Rectangle adds methods for height and width
– Also makes sense from the methods they provide
– A Square does not need set_height & set_width
10
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Rectangle
Square
class Square {
Square
private: int l;
public:
inherits
virtual void set_length(int le) {l=le;}
virtual int get_length() { return l; }
Rectangle
}
class Rectangle : public Square {
private: int w;
public:
virtual void set_length(int le) {
l=w=le; }
virtual void set_height(int he) {l=he;}
virtual void set_width(int wi) { w=wi;}
}
11
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Rectangle
Square (cont’d)
We cannot pass a Square to the foo function
– Everything’s fine here as well
void foo(Rectangle &r) {
r.set_width(5);
r.set_height(4);
assert((r.get_width()*r.get_height())
==20);
Square
inherits
Rectangle
}
12
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Rectangle
Square (cont’d)
What if foo would take Squares?
– No problem either
void foo(Square &s) {
s.set_length(5);
s.set_length(4);
assert((s.get_length()*s.get_length())
==16);
Square
inherits
Rectangle
}
13
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Rectangle
Square (cont’d)
Problem solved
Would it not be nice if Shapes had a
get_area() member?
int Square::get_area() { return l*l; }
int Rectangle::get_area() { return l*wi;}
Square
inherits
Rectangle
void foo(Square &s) {
assert((s.get_length()*s.get_length())
==s.get_area());
}
void oh_no_not_again() {
Rectangle r(3,4);
foo(r);
}
14
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Square
Shape, Rectangle
Shape
Shape
inherits
Line
Circle
…
Square
Rectangle
Correct, don’t use deep class
hierarchies just because it is
“object-oriented”
programming (is it?) or
because it’s “cool” or
“professional” (or whatever)!
15
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Lessons Learned
Avoid code inheritance
If inheritance is needed define an interface
Inherit the interface not the code
If code inheritance is needed, prefer the use of an interface plus
use aggregation
If this is not an option provide both an interface and a class to
inherit from
Question: Why is a pvector not a vector?
16
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Agenda
The Liskov Substituion Principle
– Square
Rectangle
– Rectangle
Square
Templates
Standard Library Algorithms
17
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Types of Polymorphisms
– Statically resolved by the compiler (using argument types)
Dynamic
– Using virtual member functions
– Method to be invoked identified during run-time
(using the virtual method table)
Static or Parametric
– Using templates
– Function to be invoked identified statically
– Concrete Functions/Classes are generated for the individual parameter types
18
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Templates
Allow the use of the same function/class for different types
Are checked and resolved statically
*.h
Template declaration and definition has to go into the header file
19
template<class T>
inline T min(T a, T b) {
return a<b?a:b;
}
Th. Gschwind. Fortgeschrittene Programmierung in C++.
This is “old style”, one
should use
If you use an old C++
compiler you may
have to use class.
IBM Research – Zurich
Using Templates
template<typename T>
inline T min(T a, T b) {
return a<b?a:b;
}
const double pi=3.141596;
void f() {
min(2.718282,1.0);
min('a','z');
min(1,26);
min(pi,2.718282);
min('a',26);
min(2.718282,1);
}
20
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Using Templates
template<typename T>
inline T min(T a, T b) {
return a<b?a:b;
}
const double pi=3.141596;
void f() {
min(2.718282,1.0);
min('a','z');
min(1,26);
min(pi,2.718282);
min('a',26);
min(2.718282,1);
}
21
//
//
//
//
//
//
ok
ok
ok
ok
error, ambiguous
error, ambiguous
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Templates – Resolving Ambiguities
Unlike for “normal” functions,
there is no explicit conversion for templates
Explicit
– If necessary
min<int>('a',26);
– Or even if unnecessary
min<const double>(pi,2.718282);
23
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Mixing Templates and Non-Templates
Templates and non-templates can be mixed
Can define a template-based function min
And define a non template-based function min at the same time
Non-templates are preferred over templates if no type
conversion necessary
template<typename T>
inline T min(T a, T b) {
return a<b?a:b;
}
inline double min(double a, double b) {
return a<b?a:b;
}
24
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Templates – Resolving Ambiguities (cont‘d)
Using separate helper functions
inline int min(int x, int y) {
return min<int>(x,y);
}
inline double min(double x, double y) {
return min<double>(x,y);
}
25
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
min Template – A Problem?
We have seen it works fine with numbers and characters
cout
//
//
//
//
//
//
26
<< min("Hello","World") << endl;
will compare the addresses where the
strings are stored and return the string
with the smaller address -- probably not
what we want…
Probably for strings we want a
lexicographical comparison using strcmp
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Template Specialization (1st Attempt)
min.h
template<typename T>
inline T min(T a, T b) {
return a<b?a:b;
}
inline char *min(char *a, char *b) {
return strcmp(a,b)<0?a:b;
}
foo.cc
#include "min.h"
27
void foo(char *x, char *y, const char *z) {
cout << min(x,y) << endl;
// yes
// no
cout << min(x,z) << endl;
cout << min<const char*>(x,z) << endl;
// oops
}
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Template Specialization (2nd Attempt)
template<typename T>
inline T min(T a, T b) {
return a<b?a:b;
}
min.h
template<> inline
char *min<char *>(char *a, char *b) {
return strcmp(a,b)<0?a:b; }
Still produces
foo.cc
an error – no // repeat specialization for const char *
implicit
parameter
#include "min.h"
conversions
for templates. void foo(char *x, char *y, const char *z) {
28
cout << min(x,y) << endl;
cout << min(x,z) << endl;
cout << min<const char*>(x,z) << endl;
// yes
// no
// yes
}
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Templates and Classes and Members
Works exactly the same
Simply put template <class T, class U, …> in front of the
declaration
It is even OK, to introduce new template parameters for
individual member functions
29
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
A Persistent pvector Class
template<typename T>
class pvector {
string filename;
vector<T> v;
…
public:
pvector(string fname) : filename(fname) {
}
vector.cc
~pvector() { writevector(); }
30
void push_back(const T &el) { v.push_back(el); }
void pop_back() { v.pop_back(); }
…
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
A Persistent pvector Class (cont’d)
template<typename T>
class pvector {
string filename;
vector<T> v;
vector.cc
ifstream ifs(filename);
for(;;) {
T x; ifs >> x; if(!ifs.good()) break;
v.push_back(x);
} }
31
void writevector() {
ofstream ofs(filename);
typename vector<T>::iterator fst=v.begin(),
lst=v.end();
while(fst!=lst) ofs << *fst++ << endl; }
…
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
A Persistent pvector Class (cont’d)
What happens if we pass the pvector around?
void foo(pvector<int> pv) {
if(pv.size()>0) cout << pv[0] << endl;
pv.push_back(17);
}
int main(int argc, char *argv[]) {
pvector<int> pv("/tmp/pvector-int.txt");
foo(pv);
}
32
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Agenda
The Liskov Substituion Principle
– Square
Rectangle
– Rectangle
Square
Templates
Standard Library Algorithms
33
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Algorithms
Containers alone are useful but not so useful
–
Typically we search for elements, remove them, iterate over them, …
Examples
–
find(…, x)
•
•
–
locates x in a sequence/container
returns an iterator/pointer to that element
find_if(…, pred)
•
Similar to find, but iterator/pointer to first elemet fulfilling pred
How shall we will solve it
1. Naive implementation of find()
2. Generalizing the find() function
3. Extend it to find_if()
34
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-0.0.cc
find (V0.0)
int *find(int *array, int n, int x) {
int *p=array;
for(int i=0; i<n; i++) {
int val=*p;
if(val==x) return p;
p++;
}
return 0;
}
Can only be used for int arrays
Assumes knowledge about the implementation (int*)
35
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-0.1.cc
find (V0.1)
template<class T>
T *find(T *array, int n, const T &x) {
for(int i=0; i<n; i++) {
T val=*array;
if(val==x) return array;
array++;
}
return 0;
}
Looks for “any” kind of data type
Still assumes knowledge about the implementation (T*)
36
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Iterators (cont‘d)
Work similar to a pointer
Implement the following operations (at least)
–
–
–
–
–
–
37
T operator*();
Ptr &operator++();
const Ptr &operator++(int);
bool operator==(const Ptr &)
bool operator!=(const Ptr &)
...
Th. Gschwind. Fortgeschrittene Programmierung in C++.
// ++prefix
// postfix++
const;
const;
IBM Research – Zurich
find-0.5.cc
find (V0.3)
template<class
Iter find(Iter
for(int i=0;
???
if(val==x)
begin++;
}
return 0;
}
Iter, class T>
begin, int n, const T &x) {
i<n; i++) {
val=*begin;
return begin;
How do we define val?
– T? Not a bad choice but not entirely correct
– Ideally, we want to ask the iterator for its value_type
38
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-0.5.cc
find (V0.4 prior to C++11)
template<class Iter, class T>
Iter find(Iter begin, int n, const T &x) {
for(int i=0; i<n; i++) {
typename Iter::value_type val=*begin;
if(val==x) return begin;
begin++;
}
return 0;
}
Every iterator (and also container) defines a value_type
One drawback, this only works for real iterators
It does not work for pointers
There is a solution for this: iterator_traits
(we will come back to them)
39
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-0.5.cc
find (V0.4 in C++11)
template<class Iter, class T>
Iter find(Iter begin, int n, const T &x) {
for(int i=0; i<n; i++) {
auto val=*begin;
if(val==x) return begin;
begin++;
}
return 0;
}
auto tells the C++ compiler to figure itself out what type this is
Number of elements needs to be knows
Inefficient
40
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Postfix – Prefix Operator
T &Iterator2::operator++() {
this->pos++;
return *this;
}
// prefix
T Iterator2::operator++(int) {
T t(*this);
this->pos++;
return t;
}
// postfix
Postfix Operator is less efficient
Prefer prefix operator over the postfix operator (if
possible/useful!)
41
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-0.6.cc
find (V0.7)
template<class Iter, class T>
Iter find(Iter begin, Iter beyond, const T &x) {
while(begin!=beyond) {
if(*begin==x) return begin;
++begin;
}
return 0; // error?
}
Which return-value?
– Special NULL-Iterator?
– Exception?
– Last element in the container!
42
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-0.9.cc
find (V0.8)
template<class Iter, class T>
Iter find(Iter begin, Iter beyond, const T &x) {
while(begin!=beyond) {
if(*begin==x) return begin;
begin++;
}
return beyond;
}
Can be used for any container, any data type, any iterator, and
works! :)
But not perfectly optimal/compact
43
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-1.0.cc
find (V1.0)
template<class Iter, class T>
Iter find(Iter begin, Iter beyond, const T &x) {
while((begin!=beyond) && (*begin!=x)) ++begin;
return begin;
}
Perfectly optimal and generic function
It doesn‘t get better than that
Any questions?
44
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
find-1.0.cc
find_if (V0.0)
template<typename Iter>
Iter find_if(Iter begin, Iter beyond,
void(*pred)(typename Iter::value_type)) {
while(begin!=beyond) {
if(pred(*begin)) break;
++begin;
}
return begin;
}
Need to always be a function, looks clumsy
Function always called through a function pointer
Better solution, C++ allows functions to be template arguments
as well
45
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Pointer to Functions
Functions can be viewed as variables
Variables that are constant and have the code of the function
assigned to them
As consequence, we can use the pointer to a function
Can also be achieved by interfaces but we do not always want
to create a new interface
Sounds theoretical? The benefits gained by this, certainly are
not.
46
IBM Research – Zurich
find-1.0.cc
find_if (V1.0)
template<typename Iter, typename Pred>
Iter find_if(Iter begin, Iter beyond, Pred pred) {
while(begin!=beyond) {
if(pred(*begin)) break;
++begin;
}
return begin;
}
pred may be a
– function (as before)
– lambda expression (again as before), or a
– function object (we will soon come to this)
47
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Decide which procedures you want;
use the best algorithms you can find.
Bjarne Stroustrup
48
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Some More Algorithms
Non mutating
– for_each, find, adjacent_find, count, mismatch, …
Mutating
– copy, swap, transform, replace, fill, unique, …
Sorting
– sort, nth_element, binary_search, partition, …
Sets
– includes, set_union, set_intersect, set_difference, …
49
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
algorithm
for_each
template <typename In, typename Op>
Op for_each(In first, In last, Op f);
Calls f for each element from first to last
O(n)
Attention!
– There is a controversy whether this algorithm may change its elements
– It is listed as non-mutable algorithm
– Arguments have been made whether this applies only to the element
order or the elements (first to last) itself
– It is not enforced by the compiler
50
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
algorithm
Output with for_each
template <typename In, typename Op>
Op for_each(In first, In last, Op f);
f can be an unary function
template <typename T>
void my_print(const T &x) {
cout << x << endl;
}
int main(int argc, char *argv[]) {
// …
for_each(v1.begin(), v1.end(), my_print);
}
51
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Output with for_each and lambda functions (C++11)
Traditionally, C++ does not offer lambda functions
(delegates, anonymous classes, etc.)
– C++ uses functors (functions and function objects)
– Functors are defined in the global context and not always where needed
int cnt;
for_each(v.begin(), v.end(), [](int i) {
cout << i << endl; // ++cnt;
});
[] indicates the environment that should be visible from within
the lambda expression
–
–
–
–
52
[&cnt] would pass a reference to the local variable cnt
[=cnt] indicates a value
[&] and [=] allow to indicate the entire current scope
Careful, [=] can generate a lot of copies
IBM Research – Zurich
algorithm
Maximum with for_each
template <typename In, typename Op>
Op for_each(In first, In last, Op f);
f is another unary function
int my_max_val;
template <typename T>
void my_max(const T &x) {
if(x>my_max_val) my_max_val=x;
}
int main(int argc, char *argv[]) {
// …
my_max_val=*v1.begin();
for_each(v1.begin(), v1.end(), my_max);
}
53
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
algorithm
Maximum with for_each II
template <typename In, typename Op>
Op for_each(In first, In last, Op f);
f can also be an instance of a class that implements operator()/1
A so-called function object
template <class T> struct my_max: public unary_function<T,void> {
T max;
my_max(const T& x) : max(x) {}
void operator() (const T& x) { if(x>max) max=x; }
}
int main(int argc, char *argv[]) {
// …
my_max<T> my_max_obj(*v1.begin());
cout << for_each(v1.begin(), v1.end(), my_max_obj).max;
}
54
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Related: Range For (foreach) Operator (C++11)
Copied over from Java
(which copied it over from C# (which …))
Easier to use than C++’s standard for function
Useful in combination with initializer lists
void print(const vector<int> &v) {
for(const auto &i : v) {
cout << i << endl;
}
}
55
IBM Research – Zurich
algorithm
transform
template <class In, class Out, class Op>
Out transform(In fst, In lst, Out res, Op o);
template <class In, class In2, class Out, class BinOp>
Out transform(In fst, In lst, In2 fst2, Out res, BinOp o);
Transform input and write it to out
O(n)
56
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Summary
The Liskov Substituion Principle
– Square
Rectangle
– Rectangle
Square
Templates
Standard Library Algorithms
57
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Exercise 1
Implement the persistent vector data type.
Experiment with the persistent vector and use it in combination
with different data types. What do you observe? Why do you
observe that behavior? How can it be changed?
58
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Exercise 2
Extend the RPN calculator such that it uses the persistent
vector for the stack of the numbers.
Hints
–
59
Don’t forget to create a copy of your old RPN calculator for the 1st
colloquium
Th. Gschwind. Fortgeschrittene Programmierung in C++.
IBM Research – Zurich
Exercise 3
Convert the RPN calculator to make use of templates, so that it
can be used with any number data type (e.g., the complex data
type). Show for the following types: int, double, complex
Add the operation ‘m’ that computes the minimum of the top
two numbers using the min function shown in these slides.
What is your solution for complex numbers?
Implement the operations ‘all+’ and ‘all*’ that add/multiply all
the values on the stack and put the result on top.
Hints
–
–
–
60
(You may or may not use the persistent version of the RPN calculator)
Don’t forget to create a copy of your previous RPN calculators
Rename the min function to mymin to avoid confusion with std::min
Th. Gschwind. Fortgeschrittene Programmierung in C++.