Introduction to C++: -------------------- * Abstract Data Types ( King 19.3 ): - An Abstract Data Type (ADT) consists of a data type and the operations that can be performed on it. For example: integers in a FIFO queue operations: enqueue(x) x <- dequeue() empty?() The ADT makes _no_mention_ of the actual implementation. A program using the ADT may make use of _only_ the things defined in the interface. All other parts (e.g., the implementation) are hidden. This means that the implementation can change in the future while programs using the ADT don't have to change. * In general... - C++ is an *extension* of C, which means anything that's valid C code according to the ANSI standard is also valid C++ code. It also means that C++ does many things the same way they're done in C: . basic data types (int, char, float, void, etc.) are the same; . variable and function declarations are the same; . a program must still have a `main' function where execution will start (unlike in Java, it is quite allright in C++ to have functions that are outside of any class, which is what `main' should be like); . preprocessor directives, like `#include', `#define', etc. are still used. Other features are quite different: . input/output is done differently; . dynamic memory allocation is much easier; . C++ has classes! - In what follows, we're going to look at some of those differences. * Comments: - Comments in C++ appear as /* comment */ which can span many lines. A comment at the end of a single line appears as // comment * I/O in C++: - Output is done like this: cout << ... << ... << ... ; where ... is a numeric expression, a string, or a class instance that has an output method defined for it (output methods will be discussed later). Don't forget the semicolon at the end of this statement! - Output to the standard error stream is done like this: cerr << ... << ... << ... ; - Input is done like this: cin >> x; where x is a variable that has an input method defined. This is true of ints, floats, chars, and other basic data types, as well as for many of the predefined classes in C++. (For other types of variable, you might have to define your own input method. Look up "operator>>" in a C++ book like Stroustrup's or Lippman & Lajoie's to see how to do this.) - For example, to request an integer from the user: cout << "Enter an integer: "; cin >> x; * Storage Allocation: - C++ has a `new' operator that's a lot like Java's `new' (which is itself similar to `malloc' in C). Unlike Java, C++ does NOT have garbage collection: it has a `delete' operator that's similar to `free' in C. Here's an example: int *a, *b; a = new int; // a points to an integer b = new int[100]; // b points to an array of 100 integers *a = 5; b[3] = 5; delete a; // free the memory used by a's integer delete [] b; // free the memory used by b's array. // (note the weird syntax) * Classes: - Classes are just like structures, except: . they can contain functions, . they can `hide' some of their components. Classes in C++ are very similar to classes in Java, but they are declared differently. For example, here's a stack class: class stack { public: void push( int x ); int pop(); int empty(); stack() { size = 0; } private: int size; int a[100]; }; Note the semicolon at the end of the class. Don't forget it! The `public' parts are accessible by any part of the program, just like in Java. The `private' parts are accessible only by program code defined within the class, just like in Java. There is also a `protected' modifier, just like in Java, but we'll talk about it more when we cover inheritance. push(), pop(), and empty() are prototypes (i.e., declarations) of functions defined within the class. Their code appears elsewhere. They have access to private parts of the class. All this should be familiar from Java, except for the syntax used in C++. For example, `public' and `private' modifiers appear only ONCE in each class in C++, instead of appearing for each member. * Using Class Functions: - Here's an example of using the stack: main() { stack s; s.push(5); s.push(7); s.push(10); while ( ! s.empty() ) cout << "popping " << s.pop() << "\n"; } The output is popping 10 popping 7 popping 5 - A class function is used just like a field within a structure. If function `f' is defined in class `myclass' which has an instance `x', it is called as myclass x; // x is an instance of myclass x.f(); // call the function f() defined in myclass If we have a _pointer_ to a class instance, we use the other standard notation: myclass *p; // p is a pointer to an instance of myclass p = new myclass; // allocate an instance and point p to it p->f(); // call f() * Class Functions: - In the definition of the stack class is a public function of the _same_name_ as the class: stack() { size = 0; } This is a `constructor' and is called automatically when an instance of the class is created. It typically contains a very small bit of code and initializes the class. This is called, for example, when a class instance is created with "new" or when a function is entered that has a class instance as a local variable. Global variables that are class instances are also initialized this way _before_ main() is called. - Program code that appears _inside_ the class definition (like stack() above) is typically compiled "inline". That is, whereever there is a call to a function defined inside the class definition, the code of the function replaces the function call. This saves the cost of the function call, at the cost of some extra space to copy the function's code. Only define very small functions inside your class definition! - A function with a _prototype_ in the class definition still has access to all parts of the class. The function code is defined _outside_ the class definition. The compiler must be told that such code belongs to the class, so "classname::" must precede the function name. This isn't necessary if the code appears inside the class definition. void stack::push( int x ) { if ( size < 99 ) a[ size++ ] = x; else { cerr << "stack:push() called with a full stack\n"; exit(1); } //end if } * Function Calls and Instances: - *This is important to understanding C++*. - When a class function is called, there is an instance of the class associated with that call. Above, x.f() had instance x associated with the call, while p->f() had the instance pointed to by p (i.e., the instance *p) associated with the call. - Inside the function, class variables are referred to. Above, push() refers to array `a' and integer `size'. These are the class variables that are stored in the instance that is associated with the function call. That is, in the call to s.push(), the push() function refers to the variables `s.a' and `s.size'. As a further example, suppose we have two stacks: stack s; stack t; s.push(5); t.push(9); In the call to s.push(), the push() function refers to `s.a' and `s.size', while in the call to t.push(), the push function refers to `t.a' and `t.size'. * The Special Variable `this': - The compiler doesn't really create two separate pieces of code, one for s.push() and the other for t.push(). It uses the same code, but instantiates a special variable called `this' that points to the instance associated with the function call. So your code void stack::push( int x ) { if ( size < 99 ) a[ size++ ] = x; } is really implemented by the compiler as void stack::push( stack *this, int x ) { if ( (this->size) < 99 ) (this->a)[ (this->size)++ ] = x; } and your function calls s.push(5) t.push(7) p->push(9) are really implemented by the compiler as push( &s, 5 ); push( &t, 7 ); push( p, 9 ); ============================================================= More on C++: ------------ * Constructors and Destructors: - The `constructor' of a class is implicitly called every time that a new object from that class is created. It should properly initialize all data members for the class. There is a special syntax for doing this in C++: class A { private: int x, y; public: A() : x(0), y(0) {} }; Following a class constructor, the syntax ": identifier(expression)" is called an initializer and can be used to give initial values to some (or all) of the data members of a class. If there are more than one members to initialize, simply separate them with a comma. It is still possible to do the initialization inside the body of the function, for example: A::A() { x = 0; y = 0; } would work just as well. - The `destructor' for a class is implicitly called every time that an object from that class ceases to exist. It is responsible for freeing any memory that was dynamically allocated inside the object. For example, if we declare a dynamic array inside a class: class B { int *x; public: B( int size ) { x = new int[size]; } }; then we can create a member of class B like this: "B foo(5);". When this object ceases to exist (for example, at the end of the function in which it was declared), the object will be deleted: but this only removes from memory the space that was used to hold the pointer x. It does *not* free the memory that x pointed to! In this case, we need to define a destructor, to reclaim this memory. The new class might look like this: class B { int *x; public: B( int size ) { x = new int[size]; } ~B() { delete [] x; } }; * Inline functions: - When a function is very small, it seems like we pay a high price (in terms of overhead for the function call) for the extra structure that the function provides in the program. C++ has a way of getting the best of both worlds! For example, if we write a function to compute the cube of a double number: double cube( double x ) { return x * x * x; } it makes it easier to compute cubes elsewhere in our program, but everytime we call the function, extra time is spent doing the function call. If we put the keyword `inline' in front of the function declaration: inline double cube( double x ) { return x * x * x; } then everywhere we call the function, the compiler will actually replace the call with its computation directly (so a call like "cube( 3.0 )" would be replaced with "3.0 * 3.0 * 3.0")! The compiler makes the final decision, and it is not obligated to do this; generally, it will do it only for very small functions. - For class functions, if a function is defined inside the class, it is treated as `inline' automatically. Thus, the convention in C++ is to include only declarations (i.e., prototypes) of functions inside a class, and to write the definition of the function outside (remember the syntax for this? `ClassName::function_name'). This is also good from the point of view of information hiding: if we put the definition of a class in a ".h" file, users of the class see only the declaration of the functions, while the actual definitions are contained in a separate ".cc" file. (See the started code for A3 for an example of this.) * "Constant functions": - When a class function does *not* modify any of the data members of the class (either directly or indirectly), we say that it is a "constant" function. For example, in the starter code for A3, the function `size()' for BST and BBT simply returns the value of one of the data members without changins anything. - To indicate this to the compiler, we simply put the keyword "const" after the parameter list of the function. For example, `size()' is declared as "int size() const...". * Inheritance: - One class can be built on top of another. The classical example is the class "Shape" that serves as a basis for more specialized classes "Circle", "Rectangle", and "Triangle". Each of these is a separate class, but it is also a kind of shape. In C++, this is indicated when declaring the subclasses, for example, if "Shape" has already been defined, we would define "Circle" in this way: class Circle : public Shape { ... }; The word `public' in front of Shape is IMPORTANT! There are different kinds of inheritance in C++ and we won't talk about all of them. For now, just remember that you should always put `public' in front of the name of the base class when defining a derived class. - A derived class inherits all the members of the base class that are not private. This includes all "public" members (data and functions), and also all members declared "protected". The difference between the three modifiers is this: public: can be accessed by any function outside the class protected: can only be accessed by members of the class and its derived classes (and `friend's of the class) private: can only be accessed by members of the class (and `friend's of the class; more on this later) - Inheritance vs. composition: Intuitively, inheritance is a way to represent "is-a" relationships between types (for example, a circle *is* a shape, just a special kind of shape). When the relationship we want to express is more "has-a" (for example, a car *has* tires, but a car is *not* a tire), then composition is more appropriate (i.e., having one class contain data members whose type is the second one, for example, a Car class that has four Tire data members). * Virtual functions: - A virtual function is a function of the base class that cannot be fully implemented because the details depend on each subclass. For example, we know that every shape can be drawn, but it doesn't make sense to say "Draw a shape!", we have to know *which* shape to draw. So, we have a function `draw' in class shape, but we make it `virtual': class Shape { virtual void draw(); }; Then, every subclass of Shape also has a function draw, and they can redefine it to do the right thing. (Look at the example simulation code in the readings for examples more directly relevant to A3.) - What does this allow us to do? Now, we can have a list of pointers to Shapes and call the draw function for each of those, without worrying about what kind of shape they point to: because of polymorphism, the correct function will be called for each one! * Special topic: random-number generation! - `rand' and `srand': functions declared in . rand() produces a pseudo-random int in the range 0 to RAND_MAX (defined in also). Before using rand, the pseudo-random generator must be "seeded" by calling srand( s ) with an unsigned "seed" s. THIS SHOULD ONLY BE DONE ONCE IN AN ENTIRE PROGRAM! "Restarting" the random number generator with a new seed many times in a program is *NOT* a good idea: it can destroy the statistical properties of the random number generator. rand and srand have the property that rand will generate the same sequence of pseudo-random numbers every time that it is seeded with the same seed (it is only a "pseudo"-random number generator after all). In order to get a different seed every time the program is run, a common trick is to use the value of the "system clock": by #including , we can truly randomize the generator with the call "srand( time( 0 ) );". - UNIX-SPECIFIC: `random' and `srandom' are almost identical to `rand' and `srand' except that they produce "better" random values and `random' returns a long instead of an int. - Read the file random.C in the starter code; we use a family of random-number generators (rand48).