IBM Research – Zurich Process Management Technologies C++ (3. Vorlesung) Inheritance Thomas Gschwind <thg@zurich....> © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Agenda Constants and Constant Expressions Object Oriented Programming – – – – – – – 2 Object Model Code and Type Inheritance Binding: Static vs Dynamic Abstract Classes and Interfaces Multiple Inheritance Casts Implementation Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies C/C++ const vs Java final C/C++ const specifies that a given variable or object a variable points to is constant Java final specifies that the value of a variable cannot be changed 3 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies C/C++ const vs Java final C++ Java const int a=17; final int a=17; vector<string> v1; v1.push_back("Hello"); Vector v1=new Vector(); v1.add("Hello"); const vector<string> v2; v2.push_back("Hello"); final Vector v2=new Vector(); v2.add("Hello"); const vector<string> *vp=&v2; final Vector vp=v2; vp=&v1; vp=v1; Vp->bush_back("Hello"); vp.add("Hello"); vector<string> *const vq=&v2; vq=&v1; vq.bush_back("Hello"); vector<string> *vr=&v2; 4 Vector vr=v2; Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies C/C++ const vs Java final C++ Java OK const int a=17; final int a=17; OK OK vector<string> v1; OK v1.push_back("Hello"); Vector v1=new Vector(); v1.add("Hello"); OK OK OK const vector<string> v2; ====================== v2.push_back("Hello"); OK int sz=v2.size(); final Vector v2=new Vector(); OK v2.add("Hello"); OK int sz=v2.size(); OK OK const vector<string> *vp=&v2; final Vector vp=v2; OK vp=&v1; ====== vp=v1; ====================== vp.bush_back("Hello"); vp.add("Hello"); OK OK ============================ vector<string> *const vq=&v2; ====== vq=&v1; OK vq.bush_back("Hello"); ====================== vector<string> *vr=&v2; 5 Vector vr=v2; Th. Gschwind. Fortgeschrittene Programmierung in C++. OK © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies C/C++ const (cont’d) OK const vector<string> v2; ====================== v2.push_back("Hello"); OK int sz=v2.size(); v2.push_back is NOT OK BUT v2.size is OK? How can the compiler tell the difference? The secret is the declaration of the member… … class vector { public: void push_back(T elem); int size() const; } 6 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies C++11: Constant Expressions Certain initializers require a constant expression – Arrays stored on the stack (e.g., char buf[256]) – Switch expressions (same in Java) – Functions may not be used in such constant expressions (again, same in Java) C++11 allows to use functions in such expressions – Must be marked as constexpr – Must be possible to evaluate them at compile time Useful in combination with static_assert constexpr int min(int a, int b) { return a<b? a : b; } int numbers[min(consta, constb)]; 7 © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies C++11: static_assert Allows to assert that a given condition is met at compile time Alternatives – The assert statement is evaluated at run-time (not desirable if condition can be evaluated at compile time) – The #error directive by the C++ preprocessor (cannot deal properly with template instatiations) template<typename T, int N> class Buffer { static_assert(N>16, "Buffer size too small"); … }; 8 © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Agenda Constants and Constant Expressions Object Oriented Programming – – – – – – – 9 Object Model Code and Type Inheritance Binding: Static vs Dynamic Abstract Classes and Interfaces Multiple Inheritance Casts Implementation Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Inheritance Definition of a class on the basis of another Derived, sub, or child class – Inherits the implementation of the base or parent class – May add new methods – May replace existing methods Kinds of inheritance – Code inheritance – Interface inheritance 10 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Object Model: C++ vs. Java Java – Every object inherits from the class Object – All objects are stored on the heap and accessed through pointers – Primitive types (byte, int, long, float, double, etc) are not objects C++ – There is no Object class (i.e., there is no common base class) – Objects can be anywhere and passed using whatever mechanism – Primitive types (byte, int, long, float, double, etc) are not objects 11 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Types of Inheritance public – To define an is-a relationship – Public and protected members will be inherited as defined in the base class protected, private – To define a has-a relationship (style-wise, frequently it is better to define the base class as attribute in the derived class) – Public and protected members become protected, respectively private, members of the derived class – Avoid this type of inheritance 12 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Code and Type Inheritance – – – – find toupper tolower … String.h Extend a string class with new functions class String2: public String { // type definition public: void tolower() { int n=length(); for(int i=0;i<n;++i) { (*this)[i]=tolower(*this[i]); } } // … } 13 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies “public” Derived Classes They are polymorph – They have the type of both the derived class – They inherit the type of the base class(es) => May be used wherever the base class can be used In the base context – Only those attributes which are defined in the base class may be used 14 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Access The derived class may access the public members of the base class No access to private members Additionally, members may be declared protected => These members may be used by the class itself => These members may be used in derived classes Essentially, this is the same as in Java except that package does not exist 15 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies String2.h String.h String2 class String { // type declaration+definition protected: char *strg; unsigned int len; public: … } Style! In this case I would not consider this useful. Our previous implementation is not slower almost as readable and encapsulates the // type definition implementation of the string class. class String2: public String { public: void tolower() { for(int i=0;i<len;++i) { strg[i]=tolower(strg[i]); } } // … } 16 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Type Compatibility (“public” Sub Classes) type-comp-1.cc void foo(String2 s2) { s2.tolower(); cout << s2 << endl; } int main(int argc, char String s1="Hello "; String2 s2="World!"; String &s3=s2; cout << s1[0]; cout << s2[0]; cout << s3[0]; foo(s1); foo(s2); foo(s3); *argv[]) { // // // // ok, ok, ok, ok, every String2 is a String String implements operator[] String2 inherits operator[] String implements operator[] // error s1 is a String // ok, s2 is of type String2 // error, type of s3 is String } 17 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Type Compatibility (“private” & “protected” Sub Classes) type-comp.cc class parent { // … }; class priv_inh: private parent { // … public: void priv(…); }; class prot_inh: protected parent { // … public: void prot(); }; int main(int argc, char *argv[]) { Good for code-inheritance! Avoid! parent p1(1,2); If you need another class’s code, priv_inh pri(1,2); define it as attribute of your class prot_inh pro(1,2); (Aggregation). parent &p2=pri; parent &p3=pro; // error, private base // error, protected base } void priv_inh::priv(parent &p) { priv_inh pri(1,2); if(…) priv(pri); // ok, inheritance visible to ourself } 18 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Overriding Members In C++, members of the base class can be overridden Simply define the same member again in the sub class Like in Java 19 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Inheritance – An Example Stack_with_Count.cc Stack.cc class Stack { int buf[256], sp; 20 public: Stack() { sp=256; } void push(int i) { s[--sp]=i; } int pop() { return s[sp++]; } int empty() { return sp==256; } }; class Stack_with_Count: public Stack { int cnt; public: Stack_with_Count() { cnt=0; } void push(int i) { Stack::push(i); ++cnt; } int pop() { --cnt; return Stack::pop(); } int elements() { return cnt; } }; Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Inheritance and Binding This is extra dangerous, we’ll come back to it. void fill1(Stack s) { s.push(1); s.push(2); } void fill2(Stack &s) { s.push(1); s.push(2); } test-Stack.cc void fill3(Stack *s) { s->push(1); s->push(2); } int main(int argc, char *argv[]) { Stack s; Stack_with_Count sc; sc.push(2); sc.push(4); fill1(s); fill1(sc); cout << sc.elements() << endl; fill2(s); fill2(sc); cout << sc.elements() << endl; fill3(&s); fill3(&sc); cout << sc.elements() << endl; } 21 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Binding Binding refers to the process of binding different entities to a specific symbol – For instance a value to a variable – An implementation of a function to a function name – … 22 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Static Binding Member function to be executed is determined on the basis of the variable’s static type – Used in our current example – Member may be inlined – Faster code In object-oriented programming frequently not desired 23 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Dynamic Binding Member function to be executed is determined on the basis of the object’s runtime type (“dynamic binding”) Member functions where dynamic binding is to be used need to be declared as virtual – A member function declared virtual will stay virtual for all subclasses – Style: repeat the virtual keyword in all the subclasses Member function to be executed determined via virtual method table – No inlining – A bit slower (generally, don’t worry about this) 24 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Dynamic Binding (cont’d) Stack.cc class Stack { int s[256], sp; public: Stack() virtual virtual virtual : sp(256) {} void push(int i) { s[--sp]=i; } int pop() { return s[sp++]; } int empty() { return sp==256; } Stack_with_Count.cc }; 25 class Stack_with_Count: public Stack { int cnt; Not necessary to repeat virtual here, but it’s a good style! public: Stack_with_Count() : cnt(0) {} virtual void push(int i) { Stack::push(i); ++cnt; } virtual int pop() { --cnt; return Stack::pop(); } virtual int elements() { return cnt; } }; Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Dynamic Binding: C++11 Features override A member function may be marked as override to signify it overrides a non-final virtual member function of the base class final A member function or class may be marked final to indicate it may not be overridden class Stack_with_Count: public Stack { ... virtual void push(int i) override; } class Stack final { ... }; class Stack { ... int empty() final { return sp==256; } }; 26 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Where are Virtual Members Useful? Default implementations Callbacks and hooks In abstract classes or interfaces Never implement a member that only returns an error – Use abstract methods 27 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Dynamic Binding and Overriding Methods In C++ Arguments are fixed – void push(int x) cannot be replaced with void push(long x) in the subclass. Return value of a function can be restricted – Stack Stack::clone() can be replaced with Stack_wc Stack_wc::clone() in the subclass. – Again it can be preferable to return a pointer or a reference to the Stack/Stack_wc object 28 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies foo_client.cc Callbacks and Hooks class foo_client { protected: // callback virtual foo *get_foo_from_cache(int i) { return NULL; } // default implementation virtual foo *get_foo_from_server(int i) { // … } public: virtual foo *get_foo(int i) { foo *f=get_foo_from_cache(i); if (f==NULL) f=get_foo_from_server(i); return f; } // … }; 29 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Abstract Classes Express a concept Define an interface Cannot be instantiated Can use pointers and references to such classes Examples – Article data base – A hash map that can store any data type 30 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Article Database – Class Hierarchy ArticleDB inherits ArticleDBFactory creates LocalArticleDB RemoteArticleDB CachingRemoteArticleDB 31 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies ArticleDBFactory class ArticleDBFactory { Preferences p; public: ArticleDBFactory(const char *config_file) { // … } ArticleDB *getArticleDB(const char *group) { // determine the database to be used for // group if (caching_enabled) return new CachingRemoteArticleDB(…); else return new RemoteArticleDB(…); } } 32 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Article Database class ArticleDB { public: virtual Article *getArticle(int nbr)=0; virtual void postArticle(int nbr, Article *a)=0; }; =0 after the member indicates that it is abstract If one or methods are abstract, the entire class is abstract Abstract classes cannot be instantiated A method without state and all members being virtual defines a pure virtual class and is equivalent to a Java interface 33 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies RemoteArticleDB class RemoteArticleDB: public ArticleDB { string h; int p; // … public: RemoteArticleDB(const char *host, int port) : h(host), p(port) { // … } virtual Article getArticle(int nbr) { Article a; // connect to server, if not already connected // retrieve article return a; } // … ~RemoteArticleDB() { // close connection, if still open } }; 34 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies CachingRemoteArticleDB class CachingRemoteArticleDB: public RemoteArticleDB { string h; int p; // … Map<int,Article> cache; public: RemoteArticleDB(const char *host, int port) : h(host), p(port) { // … } virtual Article getArticle(int nbr) { Article a; try { a=cache.get(nbr) } catch (NotFoundException) { cache[nbr]=a=RemoteArticleDB::getArticle(nbr); } return a; } // … 35 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Using the Article Database int main(int argc, char *argv[]) { ArticleDBFactory f("…/.config"); const char *grp; while(grp=getselectionfromuser()) { ArticleDB *db=f.getArticleDB(grp); // interact with database db // … delete db; // // // // only calls the destructor of class ArticleDB! the connection to our server won’t be closed } } 36 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Solution Define a virtual destructor in the base class virtual ~ArticleDB() {} Now the virtual destructor is called and the derived class has a chance to free its resources Hint: As soon as you have a virtual member function, implement a virtual destructor 37 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Virtual or not Virtual? If possible/useful, define an interface – In C++ a pure virtual class defines an interface – C++ does not need special interface C++ has multiple inheritance Not Virtual – If not useful to derive a class from your class – Performance *is* important (unlikely) 38 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Multiple Inheritance: Interfaces Unlike Java, C++ does not provide an interface concept Multiple inheritance provides the same functionality Multiple inheritance is more powerful C++ provides multiple inheritance struct Car { struct Player { virtual void draw() = 0; } virtual void play() = 0; } class CarPlayer: public Car, public Player { // … } 39 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Multiple Inheritance: Name Collisions Two base classes/interfaces provide the “same” function – Members have different semantics, needs to be looked at individually – Interfaces and same semantics of the members, no problem – Classes with implementation, resolve explicitly Let’s assume, both Car and Player provide each a to_string() member function, each with an implementation class CarPlayer: public Car, public Player { string to_string() { return "("+Car::to_string()+","+ Player::to_string()+")"; } } 40 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Multiple Inheritance: “Diamond Shape” Inheritance If Base has no state, there is no problem class Base; class A: public Base; class B: public Base; class Child: public A, public B; If Base has a state, this becomes tricky (generally, avoid) – Shall Base be inherited twice: no change necessary to the above – Shall Base be shared among the sub-classes: inherit virtually • class A: public virtual Base; class B: public virtual Base; 41 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Casts Casts allow to “convert” an object of type FOO into a different type BAR. static_cast<T>(o) reinterpret_cast<T>(o) dynamic_cast<T>(o) const_cast<T>(o) (T)o 42 /* C-Cast */ Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies static_cast<T>(o) Converts an Object o into a given type T Is statically verified (i.e., during compile time) Pre-defined conversion User-defined conversion Example fraction fr(1,2); double f=static_cast<double>(fr); 43 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies reinterpret_cast<T>(o) The value (bit-pattern) of object o will be interpreted to be of type T Not verified Example char *mem=reinterpret_cast<char*> malloc(n*sizeof(char)); 44 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies dynamic_cast<T>(o) Checks whether o is of type T (down/crosscast) Dynamically verified (i.e., during run-time) Uses Run Time Type Information (RTTI, generated for classes with a virtual method) Returns NULL if o is not of type T Example child c(…), *c1; parent *p=&c; c1=dynamic_cast<child*>p; 45 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies 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 and your recommendation! The programs should demonstrate why your solution is better than the other solutions © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies 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 Task: Add the following classes: Square, Rectangle 47 © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Slicing void fill1(Stack s) { s.push(1); s.push(2); } void fill2(Stack &s) { s.push(1); s.push(2); } test-Stack.cc void fill3(Stack *s) { s->push(1); s->push(2); } int main(int argc, char *argv[]) { Stack s; Stack_with_Count sc; sc.push(2); sc.push(4); fill1(s); fill1(sc); cout << sc.elements() << endl; The stack will be passed by value. In order to be able to do this, it will be “sliced”. fill2(s); fill2(sc); cout << sc.elements() << endl; fill3(&s); fill3(&sc); cout << sc.elements() << endl; } 48 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Slicing (cont’d) That is the problem with the fill1(Stack s) function Using this signature, fill1 allocates enough memory to store an object of type Stack Stack_wc uses more memory than Stack! If Stack_wc is not implemented nicely we may get an inconsistent object (if the attributes of Stack are not kept in accordance with the guidelines of Stack) 49 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Dynamic Binding – Implementation How is dynamic binding implemented? How do we know which member function to execute? 50 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Stack_wc.cc Stack.cc Virtual Method Table 51 class Stack { virtual void push(int i); virtual int pop(); virtual int empty(); }; class Stack_wc : public Stack { virtual void push(int i); virtual int pop(); }; vmtab push pop empty vmtab push Adressraum Stack::push Stack::pop Stack::empty Stack_wc::push pop empty Th. Gschwind. Fortgeschrittene Programmierung in C++. Stack_wc::pop © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Summary Constants and Constant Expressions Object Oriented Programming – – – – – – – 52 Object Model Code and Type Inheritance Binding: Static vs Dynamic Abstract Classes and Interfaces Multiple Inheritance Casts Implementation Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Exercise 1 In what order are constructors and destructors being executed when an object is constructed or destructed respectively. Show the same in case of multiple inheritance. In case of multiple inheritance, what we can do in order to avoid the inheritance of multiple copies from the base class (diamond inheritance relationship). Justify your answer with a correct program. © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Exercise 2 – Connect 4 with Inheritance Implement a simple version of “Vier Gewinnt” – You have a playing field of 7 columns by 6 rows. – Player 1 and player 2 in turns type in the column where to throw in their stone in – Gravity pulls the stone towards the lowest row After each turn display the field using ASCII art. Once a player has 4 of his stones in a row (horizontal, vertical, diagonal), he has won Try to implement the game in a modular way as we will extend it in future classes Interfaces to be used, to be published 54 © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Exercise 3 – Connect 4 with Inheritance (1st Extension) Implement a computer player The computer first checks whether the player can get 4 in a row and if so tries to stop the player from winning If the player cannot win in the next turn, the computer throws in his stone into a random column You are free to improve your computer player per your liking Interface to be used, to be published 55 © 2014 IBM Corporation IBM Research – Zurich Process Management Technologies Next Lecture Liskov Substitution Principle Templates Have fun solving the examples! See you next week! 56 Th. Gschwind. Fortgeschrittene Programmierung in C++. © 2014 IBM Corporation