Using C++ for Program 1 in CS 3411

This document is (and will be for some time) unfinished, so check back in the future for more info. (The end of the working document is clearly marked below--you'll see.)

The document has two main parts: the basics of how to "do" things with C++ (compile, run, etc.) as well as some basics about the C++ language.

Useful stuff to know (apart from the language)

There are some nuts and bolts you'll need to use to get started. The compiler to use for the project is g++. The version we are using is available only on the CoC machines.

You should be familiar with C. Invoking the C++ compiler is similar to the C compiler. The basic operation will be

   g++  -Wall  -O  -Woverloaded-virtual  foo.cc

where foo.cc is the name of a text file containing C++ source code. (Yes, that's a bear to type; I strongly suggest you create a script or a makefile to compile with.) Since you will certainly have multiple files with code, you can compile and link them separately, or just compile all the .cc files from the command line. A makefile is useful.

The other tool you should be familiar with is gdb. gdb is a debugger. Its utility is highly dependent on how well you know it. In any case, you should at least be familiar with it, as one thing it is certainly useful for is debugging mysterious coredumps, by providing a stack trace and showing you what line of code things blew up on. For a quick tutorial on gdb, I refer you to a document on my homepage.

C++ tutorial

This tutorial provides a quick-start to using C++ for the project. The best advice I can give to 3411 students about learning C++ is to

forget everything you know about C
forget everything you know about Java
selectively recall things from C and Java only when they are mentioned later on in this tutorial.

Useful stuff to know about C++

Basic types

There are lots of basic types; four will probably be useful to you. Here are some quick examples.

   bool is_crispy = true;
   int num_elves = 3;
   char snap_initial= 'S';
   string fun = "I like Rice Krispies!";

You can declare variables anywhere (almost) you like, not just at the top of a function.

Basic ops

Feel free to remember your C about basic operators, including favorites like

   assignment   =       
   equality     !=      ==      <=      >=      <       >
   math         +       -       *       /       ++      --
   boolean      &&      ||      !

You should probably avoid the funky operators like ?:. A few of the less-used operators will come back with a vengence in C++. For example, the bitshifting operators are also the I/O operators in C++:

   int x;
   cin >> x;                                   // Read in an integer
   cout << "The value of x is " << x << endl;  // Print it out

We'll learn more about I/O later. Notice that comments are like Java.

Control

if, for, while, do-while, and switch work as they do in C.

References

In addition to pointers, C++ has references. References are useful for pass-by-reference, as well as in some instances where you might use pointers in C (particularly referring to stack (non-heap) objects).

The typical pass-by-reference example is swap():

   void swap( int& x, int &y ) { // Note ref parameters with &
      int temp = x;
      x = y;
      y = temp;
   }

which would be called with something like

   int x=1, y=2;
   swap(x,y);

This is far less clumsy than how the same procedure would be made in C:

   void swap( int* x, int* y ) { /* Ugly C version with *'s everywhere */
      int temp = *x;
      *x = *y;
      *y = temp;
   }

   int x=1, y=2;
   swap(&x,&y);

You can make references to anything, not just parameters. For example:

   int x;
   int &y = x;
   y = 3;       // sets x to 3

Pointers, objects, new, and delete

To make objects on the heap, one still uses familiar C pointer syntax. However in C++, malloc() and free() have been replaced by operators: new and delete.

Here's an example to allocate and deallocate ten integers and a Foo, first in C, then in C++:

   int *a = (int *) malloc( 10 * sizeof( int ) );   /* C way */
   Foo *foo = (Foo *) malloc( sizeof( Foo ) );
   ...
   free(a);
   free(foo);
   
   int *b = new int[10];   // C++ way
   Foo *foo2 = new Foo;
   ...
   delete[] b;
   delete foo2;

Functions

Functions in C++ are just like functions in C. main() is the name of the main program as in C, as well.

Function templates

Templates in C++ allow things to be type-parameterized. Going back to our swap example before, the function we wrote can only swap two integers. If instead we want to write a general function to swap two of anything, we can make a template function so that we can use it on anything:

   int x=3, y=4;
   float a=5.5, b=6.6;
   string s="C++", t="rocks";
   
   swap(x,y);   // swap ints
   swap(a,b);   // swap floats
   swap(s,t);   // swap strings

To do this we create a template function:

   template <class T>
   void swap( T& x, T&y ) {
      T temp = x;
      x = y;
      y = temp;
   }

We can name our type parameter anything we like; the name T is common to use for template types. When you call a template function, it effectively tries to match the types of arguments, and make a function which is like a global-search-and-replace of the template argument with the actual type. So swap(x,y) replaced T with int; swap(s,t) replaced T with string.

Classes

Classes in C++ look like glorified structs. Indeed, in C++, a struct is simply a class whose members default to public (class members default to private).

   class Foo {
      public:
         // declarations (and optionally definitions) of
         // member functions and variables
      protected:
         // more of the same, hidden to outside, visible to subclasses
      private:
         // more of the same, hidden to everyone outside
   };

Don't forget that you need a semicolon at the end of a class declaration.

Constructors and destructors

Classes have special methods called constructors and destructors, which create an destroy instances of the class. Each is named after the class; destructors have a preceding tilda. Constructors can take any parameters but have no return type. Destructors take no parameters and return nothing.

Constructor bodies are different from normal methods in that there are initializers, as seen in the example below. Also, for reasons to be described later, you should always create a virtual destructor if the class might ever be inherited from.

Here's a sample class which we'll refer to a bit. It has lots of features; focus on those highlighted by comments for now.

   // This would probably appear in "point.h"
   class Point {
      public:
         Point( int x, int y );   // Constructor declaration
         virtual ~Point()  {  }   // Destructor declaration & definition

         int x() const { return _x; }
         int y() const;

         void rotate_clockwise( float degrees );
      private:
         int _x, _y;
   };
   ostream& operator<<( ostream& o, const Point &p );


   // and this would appear in "point.cc"
   Point::Point( int x, int y )     // Constructor definition
   : _x(x), _y(y)
   {}

   int Point::y() const
   { return _y; }

   void Point::rotate_clockwise( float degrees )
   {
      // code to do it
   }

   ostream& operator<<( ostream& o, const Point &p )
   {
      o << "(" << p.x() << "," << p.y() << ")";
      return o;
   }

Take note of the constructor definition.

   Point::Point( int x, int y )     // Constructor definition
   : _x(x), _y(y)
   {}

Here, between the header line and the code body there is an initializer list. Each constructor should initialize all its instance variables (and superclasses) in this initializer list, which is simply a colon, followed by a comma-separated list of entities of the form

   instance_variable_name( initial_value )

Default constructors

By default, C++ creates a zero-argument constructor for a class if you don't define any constructors. It's behavior is to call all the default constructors for the instance variables. Thus these two classes are equivalent:

class Foo {
   int x;
};
class Foo {
   int x;
   public:
      Foo() : x() {}
};

The default constructor gets called when you create a variable without specifying parameters, like any of these:

   Foo x;
   new Foo;
   new Foo();

In general, one should define constructors explicitly. Also, it is very often a good practice to provide no default constructor for a class. (C++ will not provide a default constructor if you write any constructors. Thus our Point class above has no default constructor). This ensures that you initialize all instances of the class properly, since, for example

   Point p1;    // no default constructor to call!

is a compile-time error. Instead you must do

   Point origin(0,0);   // ok

Copy constructors and the assignment operator

You can probably live without reading this section for 3411, but all C++ programmers must know this information well [--Ed]

Unlike most other OO languages, C++ is good in that it allows you to work with classes "by value". That is to say, you can have variables which hold an object, not just hold a pointer or a reference to an object. Thus, while in Smalltalk or Java, if you did something like

   Point p1(1,0);
   Point p2 = p1;

then p2 would be a reference or alias to p1 (that is, p1 and p2 both refer to the same object--modifying one makes changes visible to the other), in C++, copies are created. This is good, since it is how we are accustomed to variables working.

In order for this to happen, however, C++ needs code to copy instances of classes. By default, C++ will create two entities in your classes: a copy constructor, and an assignment operator. These have the following method signatures:

   class Point {
      ...
      Point( const Point& );             // copy constructor
      Point& operator=( const Point& );  // assignment operator
      ...
   };

These two get called implicitly a lot, so it's important to understand them.

The copy constructor is called whenever a new object is created that is initialized with another object--it becomes a copy. For example, in the code we saw above

   Point p1(1,0);
   Point p2 = p1;  // Calls copy constructor to create p2

the copy constructor is called. Copy constructors are also called when parameters are passed by value.

The assignment operator gets called when an existing variable is assigned to another object. For example, if instead we say

   Point p1(1,0);
   Point p2(0,0);
   p2 = p1;          // assignment operator

then the assignment operator method gets called. Note the subtle difference--in this example, p2 already exists (has been constructed). Also, note that these two lines

   Point p2 = p1;
   Point p2(p1);

are equivalent. This is true for any type, so these

   int x = 3;
   int x(3);

are the same, too.

The default copy constructor and assignment operator that the compiler provides (which just do memberwise copying of instance variables) will be sufficient for you unless you need special semantics. This usually happens when you have pointers as instance variables. For example, if you've defined a Stack class with a linked-list of nodes, then you'd need something like

   class Stack {
      private:
         ListNode head; 
      public:
         ...
         Stack( const Stack& s ) : head( copy_list( s.head ) ) {}
         Stack& operator=( const Stack& s ) {
            if( this != &s ) {
               free_list( head );
               head = copy_list( s.head );
            }
            return *this;
         }
         ...
   };

where we assume copy_list() is a function which copies a linked list of ListNodes and free_list() is a function which deletes such a list (and deallocates the memory). Note unhappily that in the assignment operator, we must often guard against the case where we assign a variable to itself, as in

   Stack s;
   s = s;

to prevent horrible things from happening.

Constant methods

Going back to the Point example, you may have noticed that the accessor methods were labelled const:

   class Point {
      public:
         Point( int x, int y );   
         virtual ~Point()  {  }  
   
         int x() const { return _x; }   // Note these
         int y() const;                 // "const" methods
   
         void rotate_clockwise( float degrees );   // non-const
      private:
         int _x, _y;
   };
...
   int Point::y() const      // const must reappear in definition
   { return _y; }
...
   void Point::rotate_clockwise( float degrees ) {
      // code to do it
   }

A const after a method declaration says that the method doesn't modify any of the instance variables. Thus, the method may be called on constant objects. Labelling all such methods (often all accessor methods) as const is important; without them, some good code like

   const Point ORIGIN(0,0);
   ... ORIGIN.x() ...         // call a method on const object

won't compile without a fight.

Other class miscellany

You can declare static members of a class simply by adding the word static to a declaration. Statics are just like in Java, and also like "class variables/methods" (as opposed to instance variables/methods) in Smalltalk. Static data members must be defined as well as declared, as in:

   // probably in "foo.h"
   class Foo { ...
      static int x;     // declaration
      ...
   };
   // in "foo.cc"
   int Foo::x;          // definition

Notice that whenever we refer to parts of a class outside of that class, we must use the namespace resolution operator :: (formerly known as the scope resolution operator). Each class comprises its own namespace.

Inheritance

C++ has a more powerful inheritance model than many other OOPLs. Here are the basics.

To make Foo inherit Bar, you'd say

   class Foo : public Bar {
      ...  // yadda yadda yadda
   };

The public in the code above signifies public (subtyping) inheritance. If you replace it with private, you have private (implementation) inheritance, and are prevented from casting up the class hierarchy.

As a pain-in-the-neck side effect of a C++ design goal ("you don't pay for (in efficiency) what you don't use"), whenever you want polymorphic methods, you must explicitly declare them as virtual. You must also call methods via a pointer or reference in order to see polymorphic behavior. A simple example is

   class Bar {
      public:
         virtual void f() { cout << "I'm a Bar!" << endl; }
   };
   class Foo : public Bar {
      public:
         void f() { cout << "I'm a Foo!" << endl; }
   };
   ...
   Bar *b = new Foo;
   b->f();              // displays "I'm a Foo!"

If we didn't declare the method virtual in the superclass, or we didn't use public inheritance, or we didn't call the method via a pointer or reference, then this wouldn't work.

To make a method deferred (abstract, subclassResponsibility, ...) you use the special syntax

    virtual void f()=0;

which makes what C++ calls a "pure virtual" function.

There's all kinds of crazy cool stuff about multiple inheritance, etc. that we won't talk about here since you don't need to know it.

Class templates

Class templates allow us to type-parameterize classes. Rather than having to create a stack of integers, or a stack of strings, or a stack of foos, we can just create a stack. Here's an example of a minimalist Set class.

   #include "listnode.h"
   // a small class for a data-and-next structure, which also defines
   // a function to delete a list (freeing the memory)

   template <class T>
   class Set {
      public:
         Set() : head(NULL) {}
         virtual ~Set() { empty(); }
   
         virtual bool contains( T x ) const;
         virtual void add( T x );        // duplicates ignored
   
         virtual bool is_empty() const;
         virtual void empty();           // remove all
   
      private:
         operator=( Set& );
         Set( Set& );                 // no copies allowed
   
         ListNode* head;
   };
   
   template <class T>
   bool Set::contains( T x ) const {
      ListNode *temp = head;
      while( (temp != NULL) && (temp->data() != x) )
         temp = temp->next();
      return temp != NULL;
   }
   
   template <class T>
   void Set::add( T x ) {
      if( !contains( x ) )
         head = new ListNode( x, head );
   }
   
   template <class T>
   bool Set::is_empty() const {
      return head==NULL;
   }
   
   template <class T>
   void Set::empty() {
      delete_list( head );
   }

To instantiate a template class, you must specify the type parameter. Here are some quick examples:

   Set s;             // illegal (compile error)
   
   Set<int> si;       // a set of ints
   Set<string> ss;    // and one for strings
   
   if( si.contains( 5 ) )
      ss.add( "hello" );
   
   si.add( "goodbye" );   // illegal (compile type error)

I/O in C++

C++ uses iostreams for input and output. The operators << and >> have been overloaded to work with the iostream classes. cin is the standard input stream, and cout is the standard output stream. (cerr is the standard error stream.)

   #include <iostream>
   int x;
   cin >> x;                                   // Read in an integer
   cout << "The value of x is " << x << endl;  // Print it out

endl just means "end of line"; on a unix system it'd be "\n".

The stream operators look a little funny at first, but they are very easy to use. One thing that makes them very cool is that (of course) you can overload them to work on your own types. So if we want to be able to print Points, we can write the function

   ostream& operator<<( ostream& o, Point p ) {
      o << "(" << p.x() << "," << p.y() << ")";
      return o;
   }

(Ack! Don't panic!) and then we can just say

   Point p(3,4);
   cout << "The value of p is " << p << endl;

and see happy output:

   The value of p is (3,4)

At this point the "official" document ends; what is below is notes that I intend to expand in the future [--Brian]


casts
include
exceptions
STL

Stuff to avoid (because its outside 3411's scope):

namespaces
rtti