Sample: Pointers to C++ documentation and help

C++ Lexemes

Lexemes in c++.glossary

C++ has always had a BNF-like description of its syntax since it was C. However the precision of this description has varied as has the language being described. Syntax summary from the draft standard December 1996:
(C++ draft syntax): [ gram.html ] Latest MATHS version (based on December 1996 draft) [ syntax.html ] ARM version Circa 1990(C++ as updating C and giving the same value) [ c++.syntax.html ]

The Standard Template Library

STL::=Standard Template Library, a collection of predefined data structures and classes and functions that can handle any class of object. We have some local notes on this [ stl.html ]

Also see Mumit's historical STL Newbie Guide: [ STL.newbie.html ]

(C Library Reference Guide): webmonkeys??? [ index.html ]

Inheritance and Polymorphism

Inheritance

Why Inheritance

It is even more irritating to realize that a new class you want to create is almost the same as an existing class. There new class has an extra function and one changed definition perhaps.

This happens often enough in real software for people to have invented a set of techniques for handling it. These come under the heading of "inheritance" and "polymorphism". Here are pointers to definitions:

inheritance::= See http://cse.csusb.edu/dick/samples/glossary.html#inheritance.
Polymorphism::= See http://cse.csusb.edu/dick/samples/glossary.html#polymorphism.
Practical Example
Inheritance lets you use and enhance an existing class without changing that class.

Programming by Extension
Suppose you are programming for a college. They have already have designed, written, coded and tested a class called Person. An object in this class holds personal information about somebody like their Social Security Number, their names, their address, their gender, date_of_birth(dob), phone number, and so on. A Person also has functions (know-how) that can print the information in a standard format, display it, construct a new person from given data, destroy the records of a person, increase the age, change the name, handle a change of address, ... and so on. Further the college also wants a Faculty class, a Student_assistant class, and a Staff class that are all different kinds of People!
A student is a special kind of Person - one that can take courses, can add and drop sections, has a GPA, and so on. Just like a Person a student need to be able to print itself, display itself, construct it self, destroy all its data, increase its age, change a name, change an address, ... plus doing student things like adding, dropping, passing, failing, and such.
In the old days you had to copy the Person class file and edit it to make the Student class. But this will take time and may introduce errors. Further, if something changes in the Person class (like change the year in the date of birth from 2 digits to 4 digits say) or adding a new function, forces you to duplicate the changes in the Student class.
It would be better to define the class Student so that it explicitly had a field for the personal data and #include the file containing the Person classes code (person.h), like this:
```
 		#include "person.h"
```
```
 		class Student {
```
```
 		  private:
```
```
 			Person person;
```
```
 			float GPA;
```
```
 			//data structures pointing to sections ...
```
```
 		  public:
```
```
 			//add, drop, pass, fail, ....
```
```
 			//copy public functions from Person
```
```
 		};//class Student
```
The code for the functions in student mimicking a Person will be like this:
```
 		void Student::display(){ person.display(); ...}
```
```
 		void Student::inc_age(int years){person.inc_age(years);...}
```
and so on.
Similarly for the other "People-like" classes: Faculty, Staff, etc.
If Person is changed by adding or deleting any functions then so must all these other classes. This is not a good use of our time.
The better solution is called "inheritance". It makes sure that a Student has a complete up-to-date Person as part of the student, but also, automagically gives the functions of Person to a Student. The code is simple we just add
```
		: public Person
```
to the class header of Student:
```
 		#include "person.h"
```
```
 		class Student : public Person {
```
```
 		  public:
```
```
 			//add, drop, pass, fail, ....
```
```
 		  private:
```
```
 			float GPA;
```
```
 			//data structures pointing to sections
```
```
 		};//class Student
```
The above means that Student is derived from Person. Student inherits properties of a Person. Person is said to be the base of a Student.
There is no need to declare or define functions that can be done by a Person. All Students inherit them from their parent: Person. Similarly we can derive Faculty from Person. We could also derive Staff from Person. We could perhaps derive Student_Assistant from Student or from Person. Now when Person changes it as if all the other classes are updated to fit.
Inheritance is a labor-saving device.
How It Works in C++
C++ inheritance is based on a pair of techniques chosen to make inheritance an efficient process. The compiler does most of the work. The running program (normally) does not have to decide what function or data item is to be used in each case. The choice is made by the compiler and encode into the executable program.
The compiler finds the right function to apply by looking at the type of object: Person or Student or Faculty etc. If a function only appears in Person but is applied to a Student then the parents function is called. If a function is only in the Student then the compiler uses this function. If a function is declared in but Student and Person then the compiler chooses the Student's version. This is called over-riding.
Note: There is a way to ask for a slower and more dynamic implementation that is discussed later in the notes. In some object-oriented languages the functions and data have to be searched for inside the hierarchy of classes making op a particular object.
The data describing a Person is actually hidden inside the Student. In C++ the base component is placed in memory before the items added by Student.
```
 		<------------Student-------->
```
```
 		<---Person----><-added data->
```
However these data items are not explicitly mentioned inside Student. There is no need to declare a Person person in Student... but the data is hidden in there just the same.
This means the address of the start of a student is automatically also the address of the start of a Person (Person's data is before the added data). So all the machine code that accesses person.name for a person could in theory also access student.name - except that no object except a bona fide Person can access a Person's data normally.
The compiler also makes sure that Peoples data can not be corrupted by deriving a new class from it. A student does not get any privileged access to its Person's data!

Words
We say that Student is derived from Person. We say that Person is the base class of a Student. We can also say that Student is a child of Person and Person is the (or a) parent of Student). We can also talk about Student being the class and Parent its super-class, or the Parent having a subclass Student. We can also say that Student extends Parent. We have all these different words because object-oriented languages are recent developments and their inventors all chose their own words for their ideas. In the Unified Modelling Language we talk about a derived class being a specialization of the parent, and the parent or base being a generalization of the child/derived class:

child derived subclass specialized
parent base superclass generalized
method function method operation

For more on the the different words used by different groups of people see [ objects.glossary.html ] and for some informal definitions see [ Informal Definitions of Terms in objects.glossary ]

Inheriting Operations and Data
In the above Student and Faculty had no special access to the data they inherited from their base class: Person. We can easily change Person so that it shares its private data with classes derived from it and no others. It just a matter of using the word: "protected" in place of the word "private":
```
 		class Parent{
```
```
 		  public:  //things any class can access
```
```
 		  private: //things only Parent can access.
```
```
 		  protected: //things that Parent and Children can access
```
```
 		};//end Parent
```
```
 		class Child: public Parent{...}
```
Protected data and functions are declared exactly like private and public data and functions. The word "protected" and symbolic colon(":") are placed before a list of declarations in the class that the derived class shares with its children.

Diagrams
Diagrams can make inheritance much clearer. The United Modeling Language(UML) will probably end up being the standard notation: [ uml.html ]
This kind of diagram is not difficult to do in code if you omit the arrow heads and always put the parent above the child. [ inheritance.cc ]

The Rules of Inheritance
1. A derived class can not inherit the constructors and destructors of its base/parent class. Typically you have to rethink construction and destruction. They also have the wrong names! However Destructors are also called automatically. It is easy to derive a new constructor from the Base like this:
```
 	Student::Student(string s, string n, string d):Person(s,n,d){GPA=0.0;}
```
  [ ex9a.cc ] The general syntax is:
```
 	Derived::Derived(formal arguments):Base(actual Arguments){added}
```
2. A derived class does not get access to its base class's private data and functions. This would lead to breaches of encapsulation.
3. protected::=members of a class that can be accessed by that class and classes derived from it only.
4. A base class can declare certain data and functions to be protected. Protected data and functions can be accessed by objects and functions in derived classes - but there are some rules that make sure that you can not as a result get at private data and functions: [ protected.cc ]
5. A derived class can add new functions and data to its base class.
6. A derived class can change the meaning(implementation) of functions. This is called over-loading or over-riding functions in the base class.
  
  It is difficult for a derived class to remove a function that it's base class defines. All you can do is overload the base function with a function that (1) does nothing, or (2) gives an error message. If you want this effect it may mean that the two classes should share some common parent, or perhaps your choice of child and parent was backwards.
7. A single base class can have to any number of derived classes. Each can add its own functionality and data to the common base class.
8. A class can be both a parent and a child at the same time. You can derive a new class from one that was derived from another one: for example you could derive a Student_intern from a Student and Student from Person. In a complex program you end up with a whole hierarchy of classes.
9. In a complex project you must make time early on to plan a stable hierarchy. This takes some thought, experimentation, and discussion: Is A special kind of B? or is B a special A? or do A and B share some common features C? A well thought-out hierarchy can make a set of programs easy to develop. A badly thought out hierarchy can make the work harder. Note
  2. Luckily human beings seem to be habitual makers of classification hierarchies. The idea goes back to Plato and Aristotle in Ancient Greece. Indeed most of Aristotle's extant works spend their time setting up large (and boring) hierarchies.
  3. People sell ready-made hierarchies of classes. The commonest of these describe the attributes and behavior of objects on a graphic display: Window, Button, Menu, Icon, and so on. Typically when you buy a Visual C++ you are getting C++ with such a hierarchy and some powerful tools for constructing new classes graphically from old ones. These are not free. Object-oriented languages like Java and Smalltalk also come with ready made hierarchies of useful classes. [ java.class.tree.html ] The Java class library is free.
  Syntax
  1. derived_class_declaration::= class derived_class_name : public base_class_name { added_members };
  2. derived_class_name::=any identifier, But its good style to put a capital letter first.
  3. base_class_name::=any identifier that has been declared to be the name of a class.
  4. added_members::=a set of public, private and protected declarations. Members can be data or functions or anything else.
    Notice the new use of the reserved word: "public" and the position of the colon before the "public".
    
    Syntax Exercise
    Which of the following correctly derives class Lion from class Animal
```
 	class Lion { public Animal animal; ... };
```
```
 	class Lion public : Animal { ... };
```
```
 	class Lion : public Animal { ... }
```
```
 	class Lion :: public Animal { ... };
```
```
 	class Animal : public Lion { ... };
```
    Think about how this should be written and the follow this link to [ Answer to exercise ]
  . . . . . . . . . ( end of section Syntax) <<Contents | End>>
  When to use inheritance
  Before you derive a new class D from a base class B ask yourself the following questions:
  Net
  1. Is each D a special kind of B?
  2. Is every D automatically a B?
  3. Is it impossible to have a D without also having a B?
  4. Is there exactly one B associated with each D and vice-versa?
  5. If an object is a D, is it always a D?
  6. If an object is a B but not a D, does it never become a D?
  7. Are you sure that the B is not really a part of D?
  8. Does each D behave like a B?
  9. Are D's and B's created and destroyed simultaneously?
  10. Are there always more (or the same number) of B's than D's?
  11. D isn't a particular instance of a template B<...>, is it?
  12. Are You sure that B and D are not derived from a common base?
  (End of Net)
  If you answer: "yes, because...." to all of these you can be sure that the Ds should be derived from the Bs.
. . . . . . . . . ( end of section Some Rules of Inheritance) <<Contents | End>>

Multiple Inheritance
1. interface::=a class of public member function prototypes
  We can then write the interface for a set of classes once and derive the implementations from the common interface:
```
 		class interface_name {
```
```
 			public:
```
```
 			   //common function prototypes
```
```
 		};//end interface_name
```
```
 		class implementation1_name: public interface_name{
```
```
 			private:
```
```
 			    //private data storage for first implementation
```
```
 		};//end implementation1_name
```
```
 		class implementation2_name: public interface_name{
```
```
 			private:
```
```
 			    //private data storage for first implementation
```
```
 		};//end implementation2_name
```
  The implementations of the functions would be listed like this:
```
 		Type  implementation1_name::function_name(arguments) {...}
```
```
 		Type  implementation2_name::function_name(arguments) {...}
```
  The classes and functions would probably be in different header and .cc files and compiled into the library for efficiency.
  A program can be written to call precisely the functions in the interface. Objects are declared using the different implementation classes. It is easy to switch between implementations - especially if you use a 'typedef' [ typedef.html ] statement to associate a name with a particular implementation class:
```
 	typedef implementation_1 my_favorite_implementation;
```
  This is like declaring a const - only we here declare our data type.
  The is no problem with defining a class by combining two or more non-overlapping interfaces with some private data representing the internal state.
  
  Summary
  With the exception of inheriting interfaces it might be best if you don't use multiple inheritance until you have had some experience!
. . . . . . . . . ( end of section Multiple Inheritance) <<Contents | End>>


child	derived	subclass	specialized
parent	base	superclass	generalized
method	function	method	operation

. . . . . . . . . ( end of section Inheritance) <<Contents | End>>

Polymorphism

polymorphism::=Greek(many shaped). Polymorphism is a very powerful idea. In a polymorphic programming language the program would efficiently and invisible select the correct functions to apply to each object. This would allow sever possibilities which I'll take in turn.
Polymorphism and Templates
A template creates class and functions that will automatically adjust themselves to any type of data that is given them. This is a kind of polymorphism. However the forms that we introduce here can be used in some different ways.
Polymorphism by Ignorance
Sometimes we can write code that does not need to know anything about the objects that it is handling: sorting and searching algorithms work an any type of data. However they do need to know how much data they are sorting or searching. There is an old fashioned and disliked way to express the idea of a pointer to an unknown type of data. You declare the pointer like this:
```
 		void * p;
```
This means: 'p' is an address (or NULL). If non-NULL it refers to the start of some data. *p means nothing! You then manipulate the data one byte at a time. Ugly, messy and dangerous.
However, a pointer can pointer to the parent of several objects and we can be sure that it points at data of the parental type and that all the parent's operations apply - even if it actually points at an object of a derived type: The address of a student is automatically the address of a Person as well!
A Pointer can act as a surrogate or proxy for an object. This is useful because all pointers are the same size. At the machine level a pointer is just an address of a place in RAM. All addresses take op the same number of bits. As a result we can declare and manipulate arrays of pointers to objects even if (1) we are not sure what objects we are pointing at, and (2) the pointers are pointing at different types of object. We will find a neat way to use this freedom when all the different types of object are derived from a common base class.
Polymorphism by Overloading
You have already met the idea that "+" is polymorphic: it can add two integers, two floats, two doubles, two chars, .... Each time the code at the machine's level is different but the C++ symbol is the same. A symbol that has multiple meanings is said to be overloaded. The C++ compiler looks at the context of the symbol to determine what you mean by it. You should remember that
```
 		1/2
```
is 0 but
```
 		1.0/2
```
has the value 0.5.
You can also overload functions - one name with different arguments.
You can even add further meanings to the operators in C++. We don't have time to do this but it is not as hard as you might think.
Suppose that and Animal is either a cat or a dog. Then we know that every animal makes a noise and needs feeding. Further we know that dogs bark and cats mew. We could encode this in C++:
```
 	class Animal { ... make_noise(){...}; name()...};
```
```
 	class Cat: public Animal{ .... make_noise(){ /*Meou*/}}
```
```
 	class Dog: public Animal{ .... make_noise(){ /*Woof*/}}
```
Notice that this is like (but not the same as) having two implementations of an abstract Animal.
Now this means that the compiler will recognize and compile in the correct operations in the following:
```
 		Animal a; a.name(); a.make_noise();
```
```
 		Dog    d; d.name(); d.make_noise();
```
```
 		Cat    c; c.name(); c.make_noise();
```
Because Cat and Dog are both special kinds of Animals, the Animal operation on 'name()' applies to cand d as well as a.
This is the first kind of polymorphism: Operations apply to objects of different shapes that are extended from some common core. Secondly, the compiler selects the right operation for making noises for the declared type of the data to which it is applied.
Consider the following code:
```
 		Animal *p;
```
```
 		p=new Dog(...); // *p is a Dog but p is an Animal's address
```
```
		p=new Cat(...); // *p is a Cat but p is an Animal's address
```
```
		p=new Dog(...); // *p is a another Dog
```
As the program runs the kind of Animal stored in an element in storage pointed at by p changes. Sometimes *p is a Dog and sometimes *p is a Cat... even tho' p is always an `Animal*'. So the compiler won't be able to figure out what this means:
```
 		p->make_noise();
```
in terms of Cat and Dog. It gives up and uses
```
 		p->Animal::make_noise()
```
whether p points at a Cat or a Dog.
To make a C++ program pick the right method (Cat or Dog) at runtime using the thing pointed at and not the pointer itself to determine what to do. This is called: dynamic dispatching. This is not as efficient as compile-time dispatching shown above. C++ provides it as a special option in a class declaration called a virtual function.
In C++ we get it by putting the word 'virtual' in front of the function declaration... like this:
```
 	class Animal { ... virtual make_noise(){...}; name()...};
```
```
 	class Cat: public Animal{ .... make_noise(){ /*Meou*/}}
```
```
 	class Dog: public Animal{ .... make_noise(){ /*Woof*/}}
```
As the program runs the code for
```
 		p->make_noise()
```
is more complex. It tests the type of the object that a points at and selects:
```
 		p->Animal::make_noise()
```
```
 		p->Cat::make_noise()
```
```
 		p->Dog::make_noise()
```
depending on the type of *p.

An Example
A base class called B has a function 'f()' that outputs 'B' and a derived class D has a function with the same name that outputs 'D':
```
 	#include <iostream.h>
```
```
 	class B{ public: void f(){cout <<"B"; } };
```
```
 	class D: public B{ public: void f(){cout <<"D"; } };
```
```
 	main(){
```
```
 		B b; D d;
```
```
 		b.f(); d.f(); d.B::f();
```
```
 	}
```
outputs 'BDB'. So the effect of f on an object fits that object's type.
The compiler sorts this kind of polymorphism out, before the program starts running. The program (once running) has no decision to make. It has been told which function is which.
This works when there are several different derived classes.
```
 	#include <iostream.h>
```
```
 	class B{ public: void f(){cout <<"B"; } };
```
```
 	class D1: public B{ public: void f(){cout <<"D1"; } };
```
```
 	class D2: public B{ public: void f(){cout <<"D2"; } };
```
```
 	main(){
```
```
 		B b; D1 d1; D2 d2;
```
```
 		b.f(); d1.f(); d1.B::f();
```
```
 		d2.f(); d2.B::f();
```
```
 	}
```
outputs: "BD1BD2B" -- again try this out.
Now try the following main program in place of the above:
```
 	main(){
```
```
 		B* p;
```
```
          p = new D1; p->f(); p->B::f();
```
```
          p = new D2; p->f(); p->B::f();
```
```
 	}
```
It will compile because the address of a D1 (new D1) is also the start address of a B - because each D1 is a B with some added data. Similarly new D2 is also an address of a B. Thus the pointer p is polymorphic in the sense that it can point at objects of three different types: B, D1, and D2. It can even extract public data from B part of objects of these three types.
We get a surprise when we run the above code however because the indirect access to functions with -> is not polymorphic. We don't get "D1BD2B". Instead we get "BBBB".
The compiler compiles 'p->f()' without trying to find the previous assignment to 'p' - it may be determined at run time:
```
 		if(user_input.indicates_d1()) p=new D1; else p=new D2;
```
So the compiler uses the declared type of p (B*) and deduces that this is pointing at a B, and gives us B's function.
We could program round the above. But it gets worse... suppose we have an array of items each either being a D1 or D2. We might send a pointer down the array - and we would like it to treat each item as itself not a B! The same thing happens if the D1s and D2s are in a List, Stack or Queue, or any other data structure -- we want iterators to be declared so that that they refer to the general, and yet we want the functions that apply to the thing they specifically point at.

Virtual Functions
C++ has a simple way to handle this indirect or dynamic polymorphism. The word used is rather weird for its purpose: virtual. Here are three similar classes but with a simple change: the f function is now virtual.
```
 	#include <iostream.h>
```
```
 	class BV{ public: virtual void f(){cout <<"B"; } };
```
```
 	class D1V: public BV{ public: void f(){cout <<"D1"; } };
```
```
 	class D2V: public BV{ public: void f(){cout <<"D2"; } };
```
```
 	main(){
```
```
          BV* p;
```
```
          p = new D1V; p->f(); p->BV::f();
```
```
          p = new D2V; p->f(); p->BV::f();
```
```
 	}
```
The code outputs "D1BD2B" as you might expect.

Notice that only the base class (BV) has the word virtual in it.
virtual_function::=a member function that is resolved when the program is running, rather than when the compiler is running.

Arrays of Pointers to Objects
The following two examples show how we can have an array of objects of different types, and each one knows how to behave without a single case or if. This array is effectively a mixture of D1s and D2s with each automatically doing its own thing.
```
 	main(){
```
```
 		BV *a[]={ new D1V, new D2V, new D2V, new D1V};
```
```
 		for( int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
```
```
 			a[i] -> f();
```
```
 	}
```
By the way, notice these other techniques in the code above:
Net
1. You can create an array of objects with explicit initialization.
2. You can find out the length of an array by using sizeof(array)/sizeof(item)
3. You can have an array of pointers to data of different types but you can't have an array with different types in it.
(End of Net)
Paul Tonning found a delightful example of this in a text book. It suggested that you could model a bowl of cereal as an array of crispies... each one either going "Snap", "Crackle", or "Pop" as defined. Applying a function to each crisp in turn gets the correct sound. Please try this. Low fat, no calories... [ rice.cc ]
You might like to think about feeding time at the zoo. Each animal makes its own noise.... and as you go round the cages.... the right noise is produced.

Abstract Classes
An abstract class is a class can not have objects of its own. An abstract class is like a brochure describe a collection of similar watches. It tells you what you can do with them but if you actually want to tell the time you need a concrete watch!
In other terms an abstract class can be used to express a framework that can be used in a family of related applications. By deriving a specialized version of the abstraction you can get the compiler to generate new versions of a program quickly and easily.
An abstract class has concrete classes derived from it and these can have objects. You can then treat the concrete objects as if they were also abstract ones (which they are anyway). Further - a pointer at the abstraction can actually be pointing at any of the concrete derived class's objects. One abstraction can have many different internal structures - and different performance properties.
An abstract class is more complex than an interface. It can have data and also can define the meanings of some functions while leaving others to be defined in concrete classes. The abstract class serves to organize a set of functions that are implemented in many different ways. It sets a standard that different implementations must meet. It is like a standard wall socket or jack - nothing happens unless a working device is plugged into it.
It is nice to be able to express an abstraction when we are programming a complex problem. Several object-oriented languages allow you to define an abstract class or an implementation and derive from it multiple implementations.
In C++ you (1)make all the public functions virtual. This makes sure that the correct implementation is always chosen. The compiler can sort out direct reference before the program starts. The virtual functions will figure out the rest dynamically (as the program runs). (2) make sure that it is impossible to create objects that are in the abstract class, except by declaring one of the implementations.
The syntax is odd. (1) all functions in the abstract class must be declared as virtual. (2) at least one function is declared as being equal to zero!
```
 	class Animal{
```
```
 		public:
```
```
 			virtual int legs()=0;//this is not a mistake!
```
```
 			virtual void feed(Food);//output a noise?
```
```
 			...
```
```
 	};
```
The function 'legs() above is said to be a "pure virtual function'.
In Animal above the meaning of feeding an animal and the number of legs it has are deferred to a derived classes:
```
 	class Lion : public Animal {
```
```
 		public:
```
```
 			virtual int legs(){return 4};
```
```
 		...
```
```
 	};
```
```
 	Class Snake: public Animal{
```
```
 		public:
```
```
 			virtual int legs(){return 0;}
```
```
 	};
```
```
 	...
```
It is now possible to declare Snakes and Lions but we can not declare an Animal. However we can declare variable that points to an Animal and make it point at a Snake or a Lion:
```
 		// Animal a; -- illegal
```
```
 		Snake s; // legal
```
```
 		Lion l; // legal
```
```
 		Animal * p; // legal
```
```
 			p=&s; //p is the address of s, *p is s.
```
```
 			p=&l; //p is the address of l, *p is l.
```
We can even declare an array of pointers to animals:
```
 		Animal * zoo[]={new Lion("Leo"); new Snake("Rattlebag"),...};
```
A Simple Useless example of abstract class
[ implement.cc ]

More Complex Examples
. . . . . . . . . ( end of section More Complex Examples) <<Contents | End>>
The Good and Bad News
Using this kind of polymorphism - where a base class has more than one derived class and the variations are in virtual functions - means you don't have to write so many 'if()...else...' and 'switch(...)...' statements in your code. This makes C++ code smaller than C code in many cases.
However in some early projects, people found their compiled programs were much bigger than they expected. They found that their compiler was not using an efficient implementation of their virtual functions. This may not be a big problem with later compilers.