Home

Department of Computer Science



Short notes on C++


C++ is an extension of the C programming language, the extensions are primarily to support object oriented programming. C dates from the early 70s, its original purpose was to re-write one program, the Unix operating system. Since then it has spread widely due to the spread of Unix and its own simplicity and portability. During the 70s it evolved fast acquiring type checking and other features. In the late 70s and early 80s it was more stable even though there was no standard until the mid 80s.

C++ was developed by Bjarne Stroustrup in the early 80s in AT&T's Bell Laboratories. It is an object oriented extension of C and most C programs can be compiled by C++ with no change. There is now a draft ANSI and ISO standard, it hasn't yet (1997) been finally approved but will be soon.

Stroustrup has said that many of the features of C++ have been influenced by ideas that originated with Simula-67. The other main factors affecting the design of the language were efficiency and availability. The efficiency was important because the only widely known object oriented language at the time was Smalltalk-80 which was thought to be too inefficient to use for production programs. This ``inefficient'' label also seemed to be associated with object oriented programming, so C++ has designed to allow object oriented techniques to be used for production programs with minimal overheads.

Another important goal was that the language should be quickly accepted by programmers. The way this was achieved was to make it a superset of C which would ease the transition to object oriented techniques for C programmers, they wouldn't feel it was completely alien. In addition, the way it was built on top of C made it quickly available on any machine that already had a C compiler.

Unfortunately there is a disadvantage to building on top of C -- you inherit all the deficiencies. There are many features of C that can make program development and debugging quite difficult. For example the simple conditional statement: 

  if( x = y ) {
     ...

does not actually compare 2 numbers (the comparison operator is ==), yet instead of producing a simple compile time error this can produce very confusing runtime errors. This is because ``='' is assignment and it is legal to use it in expressions or conditions! In many other ways C (and therefore C++) is very primitive and eccentric, it lacks the ``safety'' that many more recent software engineering languages seem to have. Nonetheless C++ is very widely used at the moment (end of the 90s), it has been used for almost all types of application, it is successful, flexible, powerful and exciting (dangerous?).

The following is a random selection of some books that are not too bad, in most cases there will be some comment on, what I estimate, to be the intended audience. First, the definitive description of the language by its designer Bjarne Stroustrup, The C++ Programming Language, third edition [6]; it is a very comprehensive description of all features of the language and how to use them but it is not very easy as an introduction.

There are some books that are very introductory, The apprentice C++ programmer by Lee and Phillips [3] assumes no knowledge of programming at all. Similarly the book by Perry and Levin, An introduction to object-oriented design in C++ [5] introduces the idea of object oriented programming; it does eventually cover all aspects of the language. An introductory book but with, perhaps, more about C++ than about object oriented design, is C++, How to Program by Deitel and Deitel [1]. Another introduction that really emphasises the C++ language with not much about how to use it is in the Schaum series, it is called Programming with C++ by Hubbard [2].

C++ Primer by Lippman [4] is a fairly systematic coverage of C++, make sure to get the third edition as the earlier editions are much weaker on object oriented programming. There is also a short book by P. H. Winston [7] that has explanation and uses lots of examples in the text, good, if you like that sort of thing.


1 C++ after Java or Eiffel


C++ is an object oriented language like Java, Eiffel and others. They all have classes, inheritance and subtyping, so you can design programs in very similar ways in all languages, the structures will be similar. However there are lots of differences:


2 C++Basic Components and Layout


C, upon which C++ is based, is an older procedural language this makes it different from newer languages like Java or Eiffel which were designed to be to object oriented without being an extension of an older, non object oriented, language. In addition to classes C++ has all the features of older languages such as: variables, expressions, subroutines (called functions), the normal assignment, conditional and loop statements and simple composite data types: arrays, records (structs) and pointers. The basic types are:

The int and float types have all the ordinary operators defined on them.


2.1 First Example

The following program illustrates some of its features: 

    // Example Program 1,  print powers of 2 less than 10000
    #include <iostream>
    using namespace std;
    const int LIMIT = 10000;
    
    int main() {
        int pot = 1;
 
        while ( pot < LIMIT ) {
            cout << pot << "\n";
            pot = pot * 2;
        }
    }
The # lines:
Lines beginning with # are dealt with before real compilation starts. The #include directive causes the named file to be textually included in the source file before it is fed to the compiler. It is used to provide a way of incorporating a lot of declarations. The file iostream.h contains declarations about the standard IO library, it defines, for example, the class type of the object cout.
const
The const directive is a very similar to a variable but it is a read-only variable, in this case: 
        const int LIMIT = 10000

Text Layout:
C++ programs are free format and can have any amount of white-space (ie. spaces newlines etc.) between tokens (words or symbols). Comments are either // which cause the rest of the line to be ignored or are surrounded by /*...*/ and can span many lines. All simple statements (eg. assignment, procedure call) are followed by a semicolon ``;'', while loops and compound statements {..} are not followed by semicolon.

Program Structure:
Programs consist of any number of: in one or more files. Programmers have a lot of choice about how to organise programs. When a program is executed the system starts by calling the function main.

Function structure:
Each function has a header and a body. The header includes the result type, the name and argument list, eg: main(). The body is enclosed in braces {...} and contains zero or more declarations followed by statements.

main declaration
main is an unusual function, it is called by the operating system not from C++. It can return an int result to the operating system indicating normal(0) or non-zero for abnormal termination. This does not need an explicit return to give the result as it is usually generated by the runtime system on termination. If the programmer wishes they can receive command line arguments as a count and an array of strings: 
        int main(int argc, char *argv[])

However it is possible to ignore the arguments: 
        int main()

Declarations:
A declaration consists of a type name (eg. int) followed by a comma separated list of variables with optional initialisation. So to declare one variable pot and initialise it: 
      int pot = 1;

The while statement:
The while statement consists of the keyword followed by an expression in (..) and a statement.
while ( expression ) statement
expression is evaluated and if true statement is executed, this is repeated until expression is false when the while finishes and statements after the while are executed. Above it was required to repeat 2 statements so they are enclosed in {..} to make them a single compound statement.

The cout « call:
It is not a statement, it is an operation on a pre-defined object from the standard library classes in iostream. cout is an object associated with the standard output which is normally the terminal screen, the operator << takes its right hand argument and prints it in a suitable form on the screen. Strings can be printed too: 
       cout << "hello world\n";

which just prints ``hello world''and a newline on the standard output. In the output string any characters preceded by \ are treated specially: \n is a newline, \t is a tab, \b is a backspace and \\ is a backslash.

Assignment:
C++ uses just = for the assignment operator. So: pot = pot * 2; assigns twice pot to pot.


2.1.1 Exercises

  1. Write a program to print out the Fibonacci sequence of numbers less than 10000, where the next number is the sum of the previous two: 
            1 1 2 3 5 8 13 21 34 ...

  2. Modify the program to print the first 18 Fibonacci numbers.


2.2 Second Example

This second example is a simple program to read a sequence of integers up to end of file, and then print the value of the number which was the largest. 

  #include <iostream>  
  #include <limits.h>    
  using namespace std;

  int main() {
    int num, count=0, max_so_far=INT_MIN;
      
    while ( cin >> num ) {
       if ( num > max_so_far ) max_so_far = num;
       count = count + 1;
    }
    if ( count > 0 )
       cout << "largest of = " << max_so_far << "\n";
    else
       cout << "no numbers input\n";
  }

limits.h
The header file limits.h contains implementation dependent definitions of various integer constants such as the smallest and largest ints, unsigned ints, etc. That is where the symbolic constant INT_MIN, the smallest int value, comes from.

limits.h comes from C but like many other standard C headers is available in C++. In the new C++ standard there is supposed to be a generic class defining various ``limit'' values as consts to replace the C ones but not all implementations provide this part of the library yet.

The cin object
is the standard input channel object; cin » x attempts to read characters from whatever file is open on the standard input (usually the keyboard). How the characters are interpreted depends on the type of the variable read into, in this case x. If the variable is declared int x then the characters must be numeric digits and they will be converted and stored as an int.
Why while(cin»?
Oh dear! I find this a problem. Any expression which not only yields a value (the proper job of all expressions) but also alters variables, is known as a side effect expression. As a general rule using side effects should, where possible, be avoided; they make program behaviour harder to understand. C and C++ provide hundreds of ways to write side-effect expressions, unlike nearly all other programming languages. Here cin»num alters a variable num in an expression that must also yield a bool to control the while loop.

Unfortunately in this one particular context, checking for end of file of a C++ stream, it is probably necessary. Consider the simple clear loop: 

     while(! cin.eof() ) {
         cin >> num;
         ...
     }

which checks for end of file using the eof() operation on streams, then, if it's alright, reads the number inside the loop. It doesn't use side-effects, but it doesn't work! After reading the characters that represent an integer there will probably be space or newline characters remaining in the file even though there are no more digit characters, so cin.eof() will say ``no, not end of file'', and cin»num will fail to get a number.

In C++ all input stream operations (», get() and others) have been designed to cope with this. If the read is successful they will store a value and return the bool value true. If they fail to read, because of end of file or errors, they return false.

So in this one context, although I think it is a bad principle, I use the side effect of doing input in the conditional expression of a while loop.

conditional statements:
C++ has 2 branch conditionals:
if( expression ) stat1 else stat2
The condition expression is evaluated and if true stat1 is executed, if it is false stat2 after the else is evaluated.

one branch conditionals:
Easy, just leave out the else part.


2.3 Third Example

This third example will be used to explain about characters and their input and output. The program simply copies all its standard input to the standard output: 

    #include <iostream>
    using namespace std;
    int main() {
        char c;
        while ( cin.get(c) ) cout.put(c);
    }
The expression cin.get(c) reads the next character from the standard input into the variable c. If it succeeds it returns true and the body of the loop is executed calling cout.put(c) which writes the character to standard output.

Why use cin.get(c) instead of cin » c? The operator » works but it skips white-space characters, newline, tab, and space. So the program: 

    #include <iostream>
    using namespace std;
    int main() {
        char c;
        while ( cin >> c ) cout << c;
    }
if compiled, run and given itself as the file to copy, will produce: 
    rabbit(273)$ g++ copy2.cc
    rabbit(274)$ a.out < copy2.cc   
    #include<iostream>intmain(){charc;while(cin>>c)cout<<c;}


2.4 Fourth Example

This example shows the use of character constants. If a text file has lines longer than a certain width it can be hard to display or print it as sometimes the lines get truncated. The following program wrap reads its standard input and writes the text to its standard output. If a line is longer than LINELENGTH characters it ``folds'' it by inserting a newline character and continuing the rest of the characters of th input line on the next output line. The program can be used as a filter before printing or displaying files. 

  #include <iostream>
  const int LINELENGTH = 30;
  using namespace std;
  
  int main() {
      int pos = 0;
      char c;
      
      while ( cin.get(c) ) {
          if (c == '\n') pos = 0;
          else pos = pos + 1;
          
          if (pos > LINELENGTH) {
              cout << '\n';  pos = 1;
          }
          cout << c;
      }
  }
equality tests:
The operator to test for equality is: ==, and != for not equals, NB. this must not be confused with = which is assignment. This causes many problems in programs because = is legal in expressions but has completely different effects.

character constants:
Anything in '..' is a character constant (actually the integer value of that character in the character set as chars are really little ints), non-printing characters are represented by \n, \b, \0, \t and \r for linefeed, backspace, null, tab and carriage-return respectively.


2.4.1 Exercise

Write a program to read the standard input and write each character to the standard output except upper case letters which must be converted to lower case.

Note: in order to convert the upper case letters you must be able to determine if a character is between 'A' and 'Z' and if so output the appropriate lower case letter. Conditions such as ==, !=, <, >= or <= can be combined with && meaning ``and'' or || meaning ``or''. So if(a==10 && b>0) means: if a equals 10 and b is greater than 0.

Since chars are small integers they can be used in arithmetic expressions. So c - 'A' produces 0 if c contains 'A', 2 if c holds 'C' etc. And 'a' + 3 is the letter 'd'.


3 Functions


This section introduces the definition and use of functions in C++. The following main program repeatedly reads two numbers, a real, and an integer, then calls the ``power'' function and then displays the result. The looping will stop when it fails to read the numbers successfully. 

  #include <iostream>
  using namespace std;
  extern double power(double, int);    

  int main() {
      int pow;
      double res, num;
  
      while(cin >> num >> pow) {
          res=power(num,pow);
          cout << num << " to power " << pow << "=" << res << "\n";
      }
  }
Notice the extern declaration1of power as a function returning a double (a double precision real value) result and taking a double and an int as arguments; externs can be read as saying: ``somewhere else there is a function of this type''. This is necessary so the compiler knows the type when it encounters the call (in this case power(num,pow)). Then ``somewhere-else'', in a separate file or later in the same file, there must be the full definition of the function: 
    double power(double n,int p) {
        if(p < 0)  return 0.0;
        if(p == 0) return 1.0;
        return n * power(n,p-1);
    }
This definition of the function will not cope with negative powers, it returns zero. The zeroth power of any number is 1.0, for any other power: \ensuremath{ x^{n} = x \times n^{n-1}}.

Functions are defined with a header eg: double power(double n,int p) (which declares the result type, here double, the name, power, and the types and names of the arguments separated by commas) then the body which contains local declarations and statements.

When a function is called eg: ..power(2.0,i).., the actual argument expressions are evaluated and the values assigned to the corresponding formal arguments, ie. n=2.0 and p=0 (i is 0 the first time). Then the body is executed. Execution continues until either the end of the body is reached or a return statement is encountered. If the return has a expression it is returned as the value of the function. All non-void functions must have a return with an expression.


void function results and arguments

All functions have a result type but if a function is only to be used as a procedure then the word void should be used instead; void is not a type it means there is no result. For example putlots takes a character c and a count n and outputs the character n times but there is no result: 

    void putlots(char c, int n) {
        int i=0;
        while(i < n) { cout.put(c); i=i+1; }
    }
If a function has no arguments the declaration and definition (not the call) must have an empty argument list. eg: 
    extern void greeting();

    int main() {
        greeting();
        ...
    }
    void greeting() { cout << "hello world\n"; }
This differs from ANSI C where the reserved word void is used in the argument list of the declaration and leaving the argument list blank means something else and is a hang-over from pre-draft standard C.


3.1 Value and reference parameters

The only way parameters are passed in C, and the primary way in C++, is by value; this means that the expression for the actual parameter is evaluated and its value is then copied to the formal parameter which is then a sort of temporary separate variable for the duration of the execution of the function. So: 

  void twice(int n) {
    n = n * 2;
  }
  int main() {
    int x = 10;
    twice(x);
    ...     // x is still 10
  }
has no effect whatsoever on the variable x in the main program; in the call twice(x) the actual argument expression x is evaluated giving 10 which is copied to the formal n, then n = n * 2 is executed which changes the local formal variable n leaving x untouched.

To get a function like twice to alter the value of a variable given as an actual argument C++ provides reference parameters. 

  void twice(int &n) {
    n = n * 2;
  }
  int main() {
    int x = 10;
    twice(x);
    ...     // now x contains 20
  }
Notice that the declaration of the formal parameter is int &n. When the function is called the actual argument must be a variable and it is not evaluated, instead when the function is executed the formal parameter name, in this case n, acts as an alias for the actual variable so that all uses of n actually refer to x (in this case). So the expression 
   n = n * 2;
has the same meaning and effect as: 
   x = x * 2;


3.2 Exercises

  1. Design a function to return the larger of two integers. You should also provide a small main program to test the function by calling it. Test it by calling it from the main program with different constants.
  2. Write a function and its test program to find the greatest common divisor of 2 integers. The test program should read pairs of numbers from the standard input and call gcd each time. To read numbers from the standard input use cin ».


4 A simple class


This example is very simple, it is intended to present some of the details of how to write classes, it is not meant as an example of a useful class in a real application. The program reads numbers from standard input, cin, until end of file, it accumulates a running total in an Accumulator object and at the end prints the mean. The requirements for the ``running total'' class are:

(i) keep track of the sum,
(ii) record the number of numbers making up the sum,
(iii) have a way to add in numbers, and
(iv) have a way to get the mean.
First the main program including the class definition, this is file mean.cc: 
  #include <iostream>
  using namespace std;

  class Accumulator {
    private:
      double total;
      int count;
    public:
      Accumulator() { total = 0.0; count=0;}

      void add_in(double n) {
          total = total + n; count++;
      }
      int number() { return count; }
      double mean() { return total/count; }
  };
  int main() {
      Accumulator acc;
      double x;
  
      while(cin >> x) acc.add_in(x);
  
      cout << "mean of " << acc.number() 
           << " numbers is " << acc.mean() << "\n";
  }
The following shows the program being compiled and run using the GNU compiler; the standard input, cin, is the terminal, to simulate ``end of file'' from the keyboard type ``control-d'' was typed after the numbers but it wasn't echoed: 
  rabbit(269)$ g++ mean.cc
  rabbit(270)$ a.out
  1.1 2.2 3.3 4.4 5.5
  mean of 5 numbers is 3.3
  rabbit(271)$
program structure:
As described in section 2.1 a C++ program is a collection of one or more declarations in one or more files; the declarations can be of global variables, functions or classes, and one, and only one, of the functions is called main. Here one file contains a class type declaration and a main function.
Class syntax:
The syntax of classes is the same as that of structs in C (which are called records in other languages), except that in C++ structs and classes can have function as well as data members (fields). This is one way of thinking of a class, as a record that has function members (also called methods) aswell as data, and in addition can restrict access to the member fields.

a class is a type:
A class declaration is a type, a pattern; no storage is allocated until the class is used to declare objects (variables): 
     Accumulator acc;

declares a variable acc, this allocates storage and creates an object.

Member Access:
Given an object of a class type, access to its members is by selection using a ``.'' followed by the member name. Member functions are the same, so the call of mean in an object acc is: acc.mean(x). Inside a member function access to fields is direct and does not require selection if they are the fields of the object on which mean was invoked, eg: 
      double mean() { return total/count; }

if invoked on acc then total and count are the fields in acc.

Scope Rules:
All the members of a class (or struct) after a private label are NOT accessible from outside the class, they are only accessible to code inside the class, ie. using acc.count in main is illegal. All the fields after a public label are accessible from outside by selection. This is used to enforce data hiding: hidden data fields use: private, accessor functions use: public.

Constructors:
When an object is declared it will probably need initialising, this is the job of the constructor functions of a class. A constructor function is one with the same name as the class and no result. Once appropriate storage is allocated (for example on the stack for a local variable) the appropriate constructor is implicitly called on it, so the declaration: Accumulator acc; causes Accumulator() to be called inside acc which sets total and count to 0.

The word ``constructor'' can be misleading, it is better to think of them as initialisers, the storage has already been allocated before they are invoked, and their job is just to set initial values.


4.1 Header files

If a program is large enough to be broken into more than one file, and if the same class is to be used in more than one of the files making up the program, then the class declaration is usually put in a header file (a ``.h'' file). Classes are nearly always in their own separate header files. It is necessary to do this because since the class is a type declaration it must be available to the compiler during the compilation of each file that has code that needs to use it. To avoid duplicating the definition, it is put in a header file and then ``included'' into each file that wants to use it. The #include causes textual substitution of the definition during compilation, therefore header files never need compiling separately, they are compiled whenever a code file including then is compiled. Putting the class in a header file makes it easier to re-use in other programs. Here Accumulator is in file accum.h: 

  class Accumulator {
    private:
      double total;
      int count;
    public:
      Accumulator() {
      ...
  };
Now the main program file looks like this: 
  #include <iostream>
  #include "accum.h"
  using namespace std;

  int main() {
      Accumulator acc;
      double x;
      while(cin >> x) acc.add_in(x);
      cout << "mean of " << acc.number() 
           << " numbers is " << acc.mean() << "\n";
  }


4.2 Exercise

  1. Add a new operation to the Accumulator class to return the total accumulated value. Choose a name other than total which is the name of one of the data members. Modify the test program to use the new operation.
  2. Design and implement a class called MaxMin that will accept numbers. There must be a member function which can be called accept, and it will keep check each number it is given against the numerically largest and smallest numbers it has accepted so far, then update them if necessary. There must also be functions to return, at any point, the number of numbers accepted and the current largest or smallest.


5 Arrays



5.1 Arrays: the basics

To declare an array just follow the name by square brackets containing a constant expression, the element type is determined by the name at the front of the declaration, eg: 

    int  i, a[10];
    char line[132];
declares i to be an integer, a to be an array of 10 ints and line to be an array of 132 chars. Notice that the easiest way to read C++ declarations and definitions is inside-out: ``[start with the variable name] line is an array of 132, [to the front] chars''.

Access to an element of an array is by indexing so: line[3] accesses the 4th element of the array line, note that all arrays in C++ start at zero so the first element of a is a[0] and the last is a[9]. C++ never checks the index value of array accesses so line[201] is legal but will yield some unknown value at runtime.

The following small program reads a line of characters from the terminal and then writes them out again: 

    #include <iostream>
    using namespace std;
    
    int main() {
        char line[132], c;
        int i, nxt=0;
    
        do{ cin.get(c);
            line[nxt] = c;
            nxt++;
        } while(c != '\n');
    
        for(i=0;i<nxt;i++) cout.put(line[i]);
    }
In addition to using an array of characters line this program also introduces a do while loop, the increment operator ++ and the for loop.
The do while loop
The format is: do statement while( expression );, the statements in the body must be enclosed in {..}, the terminating ``;'' is part of the syntax. The loop executes its statement then if expression is true (non-zero) it repeats.
The ++ operator
Any storage location can be incremented by following (or preceding) the expression designating it by ++, eg: i++ increments i, and ++line[3] increments the 4th element of line. There is also a decrement operator: --, so x-- decrements x by 1.
The for loop
The syntax is:
for( expr$_1$ ; expr$_2$ ; expr$_3$ ) statement
where the expr$_i$ are expressions. The meaning is given by:
expr$_1$ ;
while ( expr$_2$ ) {
    statement ;
    expr$_3$ ;
}
so ``for(i=0;i<nxt;i++) stat'' sets i to 0 and while i is less than nxt, executes stat, increments i, re-checks i etc.


5.2 Trivial exercise

Write a program to read integers up to end of file and then print them out in reverse order.


5.3 An example class containing an array

This example shows how a queue (or buffer) of characters can be written as a class. Code using the queue only has access to the functions: join(c) which puts a character at the back of the queue, head() which returns whatever character is at the front, leave() which discards the character at the front and empty() which gives true if the queue is empty. In other words the only view clients have of a class object is via the operations on it and this is enforced by the scope rules of C++.

5.3.1 Using the Class

If a class Queue has been defined then a program could use it to declare a variable b. The following program reads characters and buffers them upto a newline ('\n') from the standard input then it extracts and outputs them until the queue is empty: 

      #include <iostream>
      using namespace std;
      #include "queue.h"

      main() {
          Queue b;
          char c;
    
          do { cin.get(c);
               b.join(c);
          } while(c != '\n');

          while(! b.empty()) {
              cout.put(b.head());
              b.leave();
          }
      }
The definition of the queue class is in queue.h. The declaration Queue b declares a variable of type Queue and allocates storage on the stack for the components of the buffer.

5.3.2 The Class Definition

The queue is implemented by using a fixed length array of characters and 2 integer indices, one to point to the front and one for the back. When a character is added to the queue (with join) it is stored at the position indexed by back and then back is incremented. Since front and back start at the same position the head() character is in the position indexed by front. To discard a character from the head of the queue leave() just moves the front index on.

Figure 1: States of a queue
0\includegraphics[width=8cm]{../cpp/queue1.eps}

Sub-figure (i)    a b c d added



0\includegraphics[width=8cm]{../cpp/queue2.eps}

Sub-figure (ii)    e f g added a b departed



0\includegraphics[width=8cm]{../cpp/queue3.eps}

Sub-figure (iii)    u at front and y at back

In figure 1 (i) a b c d have been added and nothing has been removed, ``a'' is at the front. In figure 1 (ii) a b have been discarded by leave so that now ``c'' is at the front. After 256 additions to the queue the back index has reached the end of the array, however if there have been any departures then there is space vacated at the beginning of the array so the back index is ``incremented'' to 0; figure 1 (iii) shows the queue after the back has ``wrapped round''.

In order to determine if the queue is full or empty there is a count of the number of elements it contains. It is not essential because the relative positions of the front and back indices could be compared; it is just simpler to use count.

The whole class definition is in one file queue.h that was included into the calling program. Here are the contents of that file: 

    #include <assert.h>
    const int SIZE=256;

    class Queue {
      private:
        char mem[SIZE];
        int front,back,count;
        int succ(int x) { 
            if(x < SIZE-1) return x+1; else return 0;
        }
      public:
        Queue() { count=front=back=0; }
        bool empty() { return count==0; }
        bool full() { return count==256; }
        char head() {
            assert(! empty());
            return mem[front];
        }
        void leave() {
            assert(! empty());
            front=succ(front);  count = count - 1;
        }
        void join(char c) {
            assert( ! full());
            mem[back] = c;
            back=succ(back);  count = count + 1;
        }
    };
If head is called but the queue is empty what should be returned? Nothing, there is no possible answer, there is nothing there. The queue has been ``abused'' by the client code. In a sense the program has an internal logic error in the code that attempted to retrieve an element when there wasn't one. There are various ways to deal with this: try to return an ``error'' value, raise an exception or (as here) crash the program. The assert macro is defined in assert.h. When assert is executed it evaluates its expression argument and if it is true nothing happens, but if it is false then the program is stopped with an message saying which assertion has failed. Here is a test: 
    #include <iostream>
    using namespace std;
    #include "queue.h"

    main() {
        Queue b;
        cout << "attempting to access an empty queue\n";
        cout << b.head() << "\n";
        cout << "after accessing the empty queue\n";
    }
When it is executed it will break the assertion in head: 
 attempting to access an empty queue
 queue.h:15: char Queue::head(): Assertion `! empty()' failed
 IOT trap/Abort
Notice that the output command after the call on head is never executed. Crashing programs might not be desireable under all circumstances so it can be used for testing and later disabled; if the symbol NDEBUG is defined before the assert then no code is produced and no checking done.

One other small point to notice about Queue is that although functions are usually publically available, they don't have to be. Here the succ function, that increments indices modulo the length of the array, is private. It is only used internally and not part of the functional interface of Queue objects.


5.3.3 Exercise

  1. Declare and test a class Stack that provides the operations:
    push to add a character
    top to return the character at the top
    pop to discard the character at the top
    empty to give true if there is nothing on the stack and false otherwise.

    Base the program on the way that queue has been written, but note that, since a stack always adds and removes elements at one end only, there is only need for one index into the array storing the elements, and therefore no need to wrap-around the index.
  2. Design and implement a class and a small test program for a simple frequency table (or histogram) called FreqTable. Objects of this type will accept numbers in the range 0 to 99. They will record the number of occurrences of these numbers in the intervals 0-9, 10-19 etc. up to 90-99. There are 10 intervals and this will obviously need an array. The class must, in addition, provide an operation to take an interval number (between 0 and 9) and return the number of occurrences in that interval.


5.4 Strings and arrays of characters in C++

There is no primitive string type in C++, instead arrays of char have been used, but now the C++ standard has a library that has a type string in a header file of the same name.


5.4.1 C++ string

The new standard library class string provides a wide range of special functions for extracting sub-strings and other manipulations. In addition there are operations between strings such as assignment, comparison and concatenation; some of this is shown below: 

    #include <iostream>
    #include <string>
    using namespace std;

    int main() {
        string s1("hello");
        string s2, s3;
    
        s2 = "world";
        s3 = s1 + " " + s2;
        cout << s3 << "\n";
    }


5.4.2 Arrays of characters: char []

In C there are many library functions that treat an array of characters as if it is a string to be manipulated as a whole. C++ is the same, the C function declarations can be got by including cstring.h (or for backwards compatibility with C, just string.h. Although the standard now has the string library class it is still important to understand arrays of characters because they (a) are the underlying form of the string, (b) sometimes provide more flexibility and efficiency, (c) are a fundamental part of the language, and (d) probably most existing programs use them instead of the newer library class string.

Since there is no index checking and arrays of any length can be passed to functions expecting strings the convention is to terminate the string with a byte containing zero (the null byte) written as '\0', as an end marker. The output operator cout « will take a null terminated character array as argument, : 

    char line[100];
    line[0] = 'h'; line[1] = 'i'; line[2] = '\0';
    cout << line;
will print hi; line must be null terminated otherwise the undefined values of elements later in the array will be printed.

The standard library of C contains various functions to manipulate arrays of char as if they are strings. To get the correct declarations for them use the header file: string.h or cstring. 

  #include <iostream>
  #include <string.h>
  using namespace std;
  
  int main() {
    char s1[6] = "hello";
    char s2[7] = " world";
    char s3[64], s4[64];
    strcpy(s3,s1);
    strcat(s3,s2);
    cout << s3 << "\n";
    cout << "length of: \"" << s3 << "\" is " << strlen(s3) << "\n";
  }
Here are some notes on the use of char arrays and other library routines:


5.5 Array parameters

The value of an array name by itself, eg: line is the address of the first element of the sequence of storage units allocated for the array (see figure 2). Indexing an array name involves following the pointer and using the index value as an offset into the sequence of element storage locations. No storage location is allocated for the pointer itself, the array name is like a constant pointer used where necessary by the compiler. Note that this is completely different from Pascal, Modula-2 or Ada where the use of an array name by itself stands for the whole array.

When an array is given as argument eg: ``strlen(line)'', the value used is the address of the first of the element sequence. The formal argument in the function acts as a pointer variable initialised with the address so all references in the function through the formal argument access the storage of the elements of the actual argument.

Figure 2: Calling a function with an array parameter. 
#include <iostream>
using namespace std;

extern void lower(char[]);

int main() {
  char line[132];

  while( cin.getline(line,132) ) {
    lower(line);
    cout << line << "\n";
  }
}
void lower(char s[]) {
  for(int i=0;i<strlen(s);i++)
    if(s[i] >= 'A' && s[i] <= 'Z')
      s[i] = s[i] - 'A' + 'a';
}
0\includegraphics[width=2.4in]{../cpp/arrayarg1.eps}

5.5.0.1 Example

In figure 2 the example program loops through a file reading lines, converting all upper case letters to lower case and printing them out. The main program is just a test for the function lower, if it was only required to lower the case of all the upper case letters in a file it would obviously simpler to have a single while loop reading the file character by character.
Array parameters:
The formal array parameter is defined as type char s[] which means that it can be passed any size array of characters; there must be no size for a formal parameter.
getline
There is a standard iostream library function called getline that takes a character array and size as arguments and reads the standard input file up to, and not including, newline or end of file and then stores the characters in the array. So: 
    char s[100];
    cin.getline(s,100);

when given the input: 
    hi there

will store 'h' in s[0] and the rest in consecutive array elements up to 'e' in s[7] and put null '\0' in s[8]; it has not stored the newline character (note that cin » s or cin.get(s) will only read in "hi" because the space is treated as a separator).
character macros
There is a standard library of macros (inline expanded definitions) in ctype.h. These allow characters to be tested and converted. Amongst these macros is a test called isupper(c) and a converter called tolower(c) (NB tolower doesn't change a variable, it alters the character value which then needs assigning back to the variable). If we use these macros the function becomes: 
  void lower(char s[]) {
      for(int i=0;i<strlen(s);i++)
          if( isupper(s[i]) )
             s[i] = tolower(s[i]);
  }

it is also necessary to include the definitions at the start using: 
  #include <ctype.h>


5.5.1 Exercises

  1. Write and test a function to sort an array of integers into ascending order. It should only take the array and a count of the number of elements to sort as arguments. The function should just sort the numbers, it should not do any input or output, that is the job of the main calling, test function. If you are not familiar with sorting algorithms use the simple ``swap'' or ``bubble'' sort in the follow program. You can write your program by extracting the sorting code from the following program and wrapping it up as a function: 
      #include <iostream>
  using namespace std;
  
  int main() {
      int nums[6] = { 25, 4, 77, 2, 11, 1 };
      bool changed = true;
  
      while( changed ) {
          changed = false;
          for(int i=0; i<5; i++)
              if(nums[i] > nums[i+1]) {
                  int tmp = nums[i];
                  nums[i] = nums[i+1];
                  nums[i+1] = tmp;
                  changed = true;
              }
      }
      for(int i=0;i<6;i++)
          cout << nums[i] << " ";
      cout << "\n";
  }

  2. Write a program to read lines of characters from the standard input (upto end of file), check to see if they are in ascending lexical order (the lines, not the characters in each line), and print out either ``In Order'' or ``Not in Order'' at the end. So: 
        77777
    the cat is on the mat
    the gnu 
    walter

    is in order (ASCII collating sequence); but:
    v
        67
    the cat is on the mat
    SAM

    is not, because upper case letters precede lower case in the ASCII set. Note: you will need to use strcmp and strcpy discussed in the previous section 5.4, and the getline function defined above. As an alternative to getline there is a standard iostream library function called getline that takes a character array and size as arguments and reads the standard input file up to, and not including, newline or end of file and then stores the characters in the array. So: 
        char s[100];
    cin.getline(s,100);

    when given the input: 
        hi there

    will store 'h' in s[0] and the rest in consecutive array elements up to 'e' in s[7] and put null '\0' in s[8]; it has not stored the newline character (note that cin » s or cin.get(s) will only read in "hi" because the space is treated as a separator).


6 Pointers


A pointer is a variable that holds the address of another object, it points to it. Pointers are declared by preceding the identifier with a ``*'', 

   int *ip, *ptr;
   Account *ap;
declares three variables, ip and ptr that can point to integer variables, and ap that can point to any sort of Account. Such declarations do not allocate storage for the int or the Account, they are just boxes that can hold addresses.

Storage can be allocated dynamically using the operator new, its argument is the type of the object to allocate, it returns a pointer to the object. Storage is allocated from a pool of storage often known as the heap. 

   ptr = new int;
   ap = new Account("Blackbeard", 1000000.0);
First new is used to allocate storage for one int, and the address is assigned to ptr. Then the new operator allocates storage for an Account object and returns a pointer to it (its address), which is assigned to ap. If the object created is of a class type then arguments can be passed to the constructor when new is called.

Apart from the normal things that can be done with variables: assignment, passing as a parameter, or returning as a result, the only pointer specific operation is to go through it to the object (variable or value) pointed to. The operator is ``*'', for example:

Figure 3: Accessing values through pointers 
   int *ptr, i, *pp;
   ptr = new int;
   *ptr = 11;
   pp = ptr;
   i = *ptr;
   *pp = *pp + 1;



0\includegraphics[width=2.0in]{../cpp/ptr-access.eps}
In figure3 storage is allocated for one int on the heap and its address is assigned to ptr, then 11 is stored in it by going through the pointer *ptr, this is know as de-referencing the pointer or going indirect. Then the pointer variable pp is made to point to the same int by pp=ptr, NB this copies the pointer not the value pointed at. Then the value is copied into the plain int variable i from the int on the heap by de-referencing. Finally value on the heap is incremented using de-referencing.

If the storage pointed to is an object (ie. it is of a class type) then it can also be accessed; the result of de-referencing will be to get to the object, and components of an object are accessed by dot (``.'') selection, so: 

   Account *ap;
   ap = new Account("Blackbeard", 1000000.0);
   cout << (*ap).balance();
the parentheses show that (i) the pointer is de-referenced, then (ii) the balance() field of the object is called. There is an abbreviation for the combined operation of de-referencing and dot selection, it is the ``->'', right arrow operator: 
   cout << ap->balance();
Note that the left argument of -> must be a pointer to a class type object and the right argument must be one of its fields (methods).

6.1 Pointer arithmetic

The operator new can allocate a sequence of storage elements, not just one. Then the pointer will point to the first element of the sequence. The number of elements required is given after then element type: 

   char *cp = new char[100];
allocates space of 100 chars and initialises cp to point to the first. If this is done then pointer arithmetic can be used to access later elements in the sequence offset from the one pointed at (it is scaled correctly by the size of the elements). So the storage can be accessed through the pointer, in this case ip, by arithmetic followed by indirection. The code in figure 4
Figure 4: Pointer arithmetic 
 int *ip;
 ip = new int[10];
 *(ip+2) = 99;

0\includegraphics[width=2.4in]{../cpp/ptr-arith.eps} \includegraphics[width=2.4in]{../cpp/ptr-arith.eps}
adds 2 (scaled by the size of an int) to the address in ip and then goes through the result to access the third integer in the allocated block. This gives the same effect as dynamic arrays (in fact there is almost no difference between arrays and pointers, see sub-section 6.3). This gives a lot of flexibility in storage allocation, it means that storage requirements can be computed dynamically and the correct amount of storage allocated.

6.2 The address operator

The address of any lvalue (ie. variable designating expression) can be taken with the address operator: ``&'', which returns a value of type ``pointer to whatever the type of the variable was''. Variables can be declared has holding pointers to another type by preceding the name in a declaration by ``*'', so: 

   int x,y,*ip1,*ip2;
   x=3;
   ip1 = &x;

0\includegraphics[width=2.1in]{../cpp/ptr.eps}

declares x and y to be ints and ip1 and ip2 to be pointers to ints, it assigns 3 to x then assigns the address of x to ip1. Note that the type of &x is int *, a pointer to an int, therefore the assignment is type correct, however the assignment: 

  ip1 = x;
is a type error: ip1 requires an int * value and x is just an int.

As the type of ip1 is the same as that of ip2 it can be freely assigned: 

    ip2 = ip1;
makes both ip1 and ip2 point to x. The value pointed at by a pointer can be accessed by ``following'' the pointer using the indirection operator ``*'', this can only be applied to a pointer and returns the lvalue pointed at, so: 
    y = *ip2;
    *ip1 = 100;
follows ip2's pointer to the location of x, extracts the value: 3 and assigns it to the int y; then it sets x's value to 100.

This operator must be used with caution as it can produce very tangled storage where plain variables can be accessed via pointers and pointers point to the same object. It can also produce ``dangling pointers'' when a pointer is set to a local variable which is later lost when the function containing it returns.


6.3 Pointers and Arrays

Arrays and pointers in C and C++ are semantically very similar, the only difference being that arrays have storage allocated at compile time and cannot be made to point anywhere else; this sub-section will explain the similarity. The value of an array name is the address of the first location of the storage allocated to it, which is type equivalent to a pointer. In figure 5

Figure 5: Pointers and arrays 
    int *pi, a[10], i = 6;
    pi = a;
is the same as the assignment of the address of the first element explicitly: 
    pi = &(a[0]);
0\includegraphics[width=0.96\textwidth]{../cpp/ptr-array.eps}
after the assignment to the pointer the same locations can be accessed via the pointer or by indexing the array: 
    *(pi+2) = i;
sets the third element of a to 6 as pi points to the first element and the expression pi+2 points to the third and *(pi+2) goes indirect through it. It is equivalent to a[2]=i. Since arrays are similar to pointers, array names can be used in pointer expressions and pointers can be indexed: 
    *(pi+9) = 3;
    *(a+9) = 3;
    pi[9] = 3;
    a[9] = 3;
are legal and equivalent. The only difference between pointers and arrays is that the array name cannot be assigned to since it only functions as a constant pointer to its storage and no location for the pointer exists (unlike real pointers). So although pi = a is ok, a = pi is impossible. Since it is possible to index sequences of dynamically allocated variables using a pointer it is in effect a dynamic array, see the following exercise.


6.3.1 Exercise

Write a program to sort some floating point numbers (doubles). The program should read a number from the standard input to determine how many numbers to sort. It should use new to allocate a suitable amount of storage. Then read into the dynamic storage the right number of numbers. Finally it should sort them and output them. In other words it is using a pointer and new to produce a dynamically allocated array.


6.4 Lists and dynamic data structures

The implementation of many data abstractions requires sequences of data items to be stored, the commonest, and usually the most appropriate, form of data type to use for this is an array. However there are situations when an array is not the best structure, if insertions or deletions have to take place in the middle of the sequence then there is a serious overhead of moving all later elements up or down. Instead linked lists can be used, where each element of the sequences has a pointer to the next element of the sequence:

Figure 6: A linked list
0\includegraphics[width=8.0cm]{../cpp/list-idea1b.eps}
Each element is an object containing the value to be stored and a pointer to the next object, for example: 
    class Cell {
      public:
        Cell(int v, Cell *n) {val=v; next=n;}
        int val;
        Cell *next;
    };
here the list cell holds an integer and a pointer field to objects of the same type, Cell *. The class makes both data fields publically accessible. There is also a constructor even though the class is so simple, this is to simplify the setting of fields when an object is created: 
     rep = new Cell(1, rep);
which (if rep is of type Cell*) inserts a new cell with value 1 in front of whatever rep previously pointed to. The two diagrams in figure 7 show the creation and insertion of a new cell into the front of a list.

Figure 7: Inserting a new list cell
0\includegraphics[width=8.5cm]{../cpp/list-eg2.eps}



0\includegraphics[width=8.5cm]{../cpp/list-eg3.eps}

A simplified class to manage a linked list might be as follows: 

#ifndef _LISTH
#define _LISTH
#include <assert.h>

class List {
  private:
    class Cell {
      public:
        Cell(int v, Cell *n) {val=v; next=n;}
        int val;
        Cell *next;
    };
    Cell *rep;
  public:
    List() { rep=0; }
    bool empty() {return 0==rep; }
    void putfirst(int i) { rep=new Cell(i,rep); }
    int first() { assert(! empty()); return rep->val; }
    void butfirst() { assert(! empty()); rep = rep->next; }
};
#endif _LISTH
The operations are chosen to be similar to those on lists in functional languages like Lisp, Miranda or Haskell. They allow elements to be added at the front, putfirst, removed from the front butfirst and for the front value to be accessed, first. In this version all the functions are defined in the class because they are so short they are suitable for in-line expansion. The class can be used very simply: 
#include <iostream>
using namespace std;
#include "list.h"

int main() {
    List s;

    s.putfirst(2); s.putfirst(1); s.putfirst(8); s.putfirst(1);
    cout << "front should be 1, it is: " << s.first() << "\n";
    s.butfirst();
    cout << "butfirst, front should now be 8, it is: " 
         << s.first() << "\n";
}
If a remove or delete function is needed it will have to go in a separately compiled file because it is to long to be in-line expanded. So first add the prototype declaration to List: 
class List {
  public:
    List() { rep=0; }
    ...
    void butfirst() { assert(! empty()); rep = rep->next; }
    void remove(int i);
  private:
and then a separate file list.cc that contains the full definition of remove: 
#include "list.h"

void List::remove(int i) {
    Cell *ptr = rep;

    if(0==ptr) return;
    if(ptr->val==i) {
        rep = ptr->next; delete ptr; return;
    }
    while(ptr->next != 0) {
        if(ptr->next->val == i) {
            Cell *t = ptr->next;
            ptr->next = ptr->next->next;
            delete t;
            return;
        }
        ptr = ptr->next;
    }
}
this is so complicated because (i) the first case of an empty list must be checked, (ii) if the element to be removed is in the first cell then the ``root'' pointer rep must be altered, (iii) in the main loop it is necessary to examine one ahead, ptr->next->val, so the ptr->next pointer of the current cell can be changed, and (iv) it is necessary to save a copy of the changed pointer so it can be deleted and returned to free storage.


6.4.1 Exercise

Design and implement a class to provide a set of integers. The set should behave a bit like the simple mathematical idea of a set, there is no concept of order and elements belong uniquely to a set, so that if 42 is in a set it is in once no matter how many times it is added. The operations that should be provided on this abstract type are add, member which tests whether a value is in the set, and remove to remove a value.

The implementation can be done however you wish but clearly it is possible to use linked storage (that is why the exercise is suggested here) or an array. Given the existence of the List class it should be possible to use it two or three different ways:

For this first exercise use the first approach, at the end of the next section 6.5 there will be another exercise that will use the second approach. Also try to devise a simple test using add, remove and member to see if the set implements unique (non-repeating) membership.


6.5 Lists and iterators

In the first version of the list, in order to examine all the elements stored in it, the list must be destroyed; to access the second element the first must be removed, etc. This can obviously be remedied by adding some new accessors but there is a different form of solution called an iterator. An iterator is an object associated with a container storage object, like a list, that allows each element in the container object to be examined in turn without destroying the container. Iterators are ``throw-away'' objects in that they are created for one inspection of the list and then discarded, the next time the list is examined another will be created. First the new header file list.h: 

#ifndef _LISTH
#define _LISTH
#include <assert.h>

class List {
  private:
    class Cell {
      public:
        Cell(int v, Cell *n) {val=v; next=n;}
        int val;
        Cell *next;
    };
    Cell *rep;
    friend class Iterator;
  public:
    List() { rep=0; }
    bool empty() {return 0==rep; }
    void putfirst(int i) { rep=new Cell(i,rep); }
    int first() { assert(! empty()); return rep->val; }
    void butfirst() { assert(! empty()); rep = rep->next; }
};
class Iterator {
  private:
    List::Cell *ip;
  public:
    Iterator(List l) { ip=l.rep; }
    bool done() { return 0==ip; }
    int get() { assert(! done()); return ip->val; }
    void step() { assert(! done()); ip = ip->next; }
};
#endif _LISTH

The code to use Iterator is in test-list.cc which builds a list and then uses an iterator i to examine it: 

#include <iostream>
using namespace std;
#include "list.h"

int main() {
    List s;

    s.putfirst(2); s.putfirst(1); s.putfirst(8); s.putfirst(1);
    cout << "iterating from front to back, should see 1 8 1 2\n";
    for(Iterator i(s); ! i.done() ; i.step() )
        cout << i.get() << " ";
    cout << "\n";
}
Iterators are a very useful tool, nearly all libraries of container classes such as sets, lists, queues or tables provide iterators. In general they make using container classes easier. However care must be taken if an item is removed from a list then any iterator currently active on that list could be corrupt.


6.5.1 Exercise

Now re-implement the integer set exercise using the second approach:

take the List type and use it unchanged as the internal representation of the Set, and have very simple methods for Set that manipulate the internal List member.
You will need the iterator for lists in order to implement the member function. Also provide a SetIterator implemented using the list Iterator. The test program can be as before but add some code to try out the SetIterator.

6.6 When to use linked storage

The decision to use linked storage or an array to implement some data abstraction depends on how the structure will be accessed and used.


7 References


A reference to a value is an alias for it (a hidden pointer). Preceding a name by & in a declaration makes it a reference (NB a reference is not a pointer and must not be confused with the & operator, although behind the scenes references might be implemented using addresses, at the language level there is NO connection between pointers and references, the are separate concepts). Given: 

    double d = 3.0;
    double &ali = d;
    double e = ali;
    ..
    ali = ali + 0.5;
declares ali to be a reference to doubles and initialises it to refer to d (references can only be set by initialisation). All subsequent mentions of ali can only access whatever is referred to, ie. d (so unlike pointers the reference cannot be manipulated), e is initialised with d ie. 3.0, ali=ali+0.5 takes the value from d and assigns d, e is not touched. Despite the preceding example NEVER use references in that way, there is no point and it makes programs unnecessarily hard to understand if there are two ways to refer to a variable when there is no pressing need. The following sections show other more sensible ways to use pointers.

7.1 Reference Parameters

When used for the parameters or for the results of functions references are useful2. Given the function: 

    void swap(int &a, int &b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
    int main() {
        int x=100, y=200;
        swap(x,y);
      ...
swap really does exchange the values in x and y. This is because when the function is called and the formal arguments are initialised they are made aliases for their actual arguments and subsequent use of a and b in the function actually accesses x and y. The argument setting during the call is like: int &a=x which makes a an alias for x. This provides argument passing just like Fortran, the VAR parameters of Pascal and Modula-2, or the in out parameters of Ada.

Argument passing with references can be useful to allow modification of the actual arguments OR it can be used to avoid copying large values. If it is used just to avoid creating and copying value arguments then the reference argument can be made const so it cannot accidentally be changed: 

    void dontchange(const bigstruct &a)
    {
will just pass a reference to the actual argument and won't allow it to be altered. The use of const for an argument means that code in the function cannot change the value of it. It is a way of adding extra reliability to a program, if the code is not intended to alter its argument, the compiler can now check that it won't do it by accident.

7.2 Reference Results

Similarly reference results can be useful. With references programs can have lvalue functions, ie. functions used on the left of assignments.

In the List example of the previous section there is an Iterator function called get that returns the int value of the cell currently pointed to by the iterator, this can be changed to have a reference result: 

    int &get() { assert(! done()); return ip->val; }
when the function is used to retrieve a value (as an rvalue expression, meaning on the right hand side of assignment, or in any expression) it works exactly as before: 
    for(Iterator i(s); ! i.done() ; i.step() )
        cout << i.get() << " ";
it just gets a reference back and then uses the value in it. However since the result of get is an alias for a storage box (the val field in the list cell) it can be assigned to: 
    for(Iterator i(s); ! i.done() ; i.step() )
        i.get() = i.get() * 2;
this means every element stored in the list will be doubled. Note that in get to return a reference the result type must be &, but no special operator is used in the return. If it is used where a value is needed, the value in the storage referred to is used (an rvalue), but if used in a context where a variable is altered (an lvalue), the location referred to is used.

7.2.1 Does it violate encapsulation?

No. Although it would now seem that returning references from objects gives, to client code, hidden pointers to the object's inner secret, private parts (?), it is quite safe. Even using an element of the storage is altered, that is all that happens here. The client code cannot manipulate the reference to look at other parts of the data representation: the runtime integrity of objects is preserved, and the source code independence is retained so the implementation of the class can still be changed without affecting client code

Bibliography

1
H. M. Deitel and P. J. Deitel.
C++ How to Program.
Prentice-Hall, second edition, 1998.
A reasonably balanced and systematic coverage, not sure why I wouldn't choose it, but I wouldn't.

2
John R. Hubbard.
Programming with C++.
Schaum's Outline Series, McGraw-Hill, 1996.
Systematic treatment of language features with lots of examples and exercises; weaker on using language features like classes.

3
P. A. Lee and C. Phillips.
The apprentice C++ programmer, a touch of class.
International Thomson, 1997.
This is an introduction to programming aswell as OO and C++; it is quite good though maybe a bit slow; it doesn't cover all language features.

4
S.B. Lippman.
C++ Primer.
Addison-Wesley, third edition, 1998.
No knowledge of C assumed, covers all aspects of the language systematically; not a lot of emphasis on object oriented program structure.

5
Jo Ellen Perry and Harold D. Levin.
An introduction to object oriented design in C++.
Addison-Wesley, 1996.
This is an introduction to programming aswell as OO and C++; it is quite good even though it starts right at the beginning; it does eventually cover nearly all language features.

6
B. Stroustrup.
The C++ Programming Language.
Addison-Wesley, third edition, 1997.
This is a very comprehensive description of all featureslanguage and how to use them but it is notnow reflects the ANSI standard and contains a long description of the STL.

7
P. H. Winston.
On to C++.
Addison-Wesley, 1994.
Very short and simple, does not explore all aspects of the language.


8 Answers to exercises


The following small programs are possible solutions to the simple exercises suggested earlier. These small programs are not meant to be perfect examples of programming style, they might at best be examples of not totally imperfect C++.


8.1 Answers for subsection 2.1.1

For the first exercise: 

//  generate and print the Fibonacci
//    numbers less than 10000

#include <iostream>
using namespace std;
int main() {
    int last, last_but_one, new_last;

    last_but_one = 0;
    last = 1;
    while ( last < 10000 ) {
        cout << last << " ";
        new_last = last + last_but_one;
        last_but_one = last;
        last = new_last;
    }
    cout << "\n";
}

And for the second version: 

//  generate and print the first 18
//    Fibonacci numbers
#include <iostream>
using namespace std;

int main() {
    int count=1, last=1, last_but_one=0, new_last;

    while ( count <= 18 ) {
        cout << last << " ";
        new_last = last + last_but_one;
        last_but_one = last;
        last = new_last;
        count = count + 1;
    }
    cout << "\n";
}


8.2 Answer for subsection 2.4.1 

//  read and write characters converting all
//    upper case to corresponding lower case
#include <iostream>
using namespace std;

int main() {
    char c;

    while ( cin.get(c) ) {
        if ( c >= 'A' && c <= 'Z' )
            cout.put('a' + c - 'A');
        else
            cout.put(c);
    }
}


8.3 Answers for subsection 3.2

The first exercise: 

//  a function to return the larger of 2 numbers
//  and a simple main program to call it & test it.
#include <iostream>
using namespace std;

extern int larger(int,int);

int main() {
  cout << "larger of 67 and 4 =" << larger(67,4) << "\n";
  cout << "larger of 4 and 67 =" << larger(4,67) << "\n";
  cout << "larger of -8 and -1 =" << larger(-8, -1) << "\n";
  cout << "larger of 5 and -10 =" << larger(5,-10) << "\n";
}
int larger(int a, int b) {
    if ( a >= b ) return a;
    else  return b;
}
The second exercise sample answer: 
//  a function to find the greatest common
//  divisor of 2 integers
//  and a simple main program to call it & test it.
#include <iostream>
using namespace std;

extern int gcd(int,int);

int main() {
    int a,b;
    cout << "gcd: input 2 integers, to stop input 0 0\n";
    cout << "2 ints: ";
    cin >> a >> b;
    while( a != 0 || b != 0) {
        cout << "gcd of " << a << "," << b << "=" << gcd(a,b) << "\n";
        cout << "2 ints: ";
        cin >> a >> b;
    }
}
int gcd(int x, int y) {
    int xx = x, yy = y;
    while (xx != yy) 
        if (xx > yy)
            xx = xx - yy;
        else
            yy = yy - xx;
    return xx;
}


8.4 Answers for subsection 4.2

The first exercise: 

#include <iostream>
using namespace std;

class Accumulator {
  private:
    double total;
    int count;
  public:
    Accumulator() { total = 0.0; count=0;}

    void add_in(double n) {
        total = total + n; count++;
    }
    int number() { return count; }
    double getTotal() { return total; }
    double mean() { return total/count; }
};
int main() {
    Accumulator acc;
    double x;

    while(cin >> x) acc.add_in(x);

    cout << "mean of " << acc.number() 
         << " numbers is " << acc.mean() 
         << " sum = " << acc.getTotal() << "\n";
}
The second exercise: 
#include <iostream>
using namespace std;

class MaxMin {
  private:
    int lsf, ssf;
    int count;
  public:
    MaxMin() { count=0;}

    void accept(int n) {
        count++;
        if(count==1) lsf = ssf = n;
        else {
            if(n > lsf) lsf = n;
            if(n < ssf) ssf = n;
        }
    }
    int number() { return count; }
    int largestSoFar() { return lsf; }
    int smallestSoFar() { return ssf; }
};
int main() {
    MaxMin mm;

    mm.accept(56);    mm.accept(3);
    mm.accept(4);    mm.accept(17);
    mm.accept(23);    mm.accept(34);


    cout << "number of numbers= " << mm.number() 
         << " largest= " << mm.largestSoFar() 
         << " smallest = " << mm.smallestSoFar() << "\n";
}


8.5 Answers for subsection 5.2

The first exercise: 

#include <iostream>
using namespace std;

int main() {
    char line[132], c;
    int i, nxt=0;

    do{ cin.get(c);
        line[nxt] = c;
        nxt++;
    } while(c != '\n');

    // start at nxt-2 to avoid the newline char 
    for(i = nxt-2; i >= 0; i--)
        cout.put(line[i]);
    cout.put('\n');
}

8.6 Answers for subsection 5.3.3

The first exercise, a simple stack class. First the header file stack.h: 

static const int MAXSIZE=256;

class Stack {
  private:
    char mem[MAXSIZE];
    int topp;
  public:
    Stack(void)    { topp=-1; }
    int empty(void) { return topp<0; }
    int full(void)  { return topp==MAXSIZE-1; }
    char top(void) {
        assert(! empty());
        return mem[topp]; 
    }
    void pop(void) { 
        assert(! empty());
        topp--;
    }
    void push(char c) {
        assert(! full());
        topp = topp+1;
        mem[topp] = c;
    }
};
Now the test program that includes the header file: 
#include <iostream>
using namespace std;
#include "stack.h"

int main() {
    Stack filo;
    char c;

    cin.get(c);
    while(c != '\n') {
        filo.push(c);
        cin.get(c);
    } 

    while(! filo.empty()) {
        cout.put(filo.top());
        filo.pop();
    }
    cout << "\n";
}

The second exercise, a simple frequency table. First the class definition in header file freqtab.h: 

#include <assert.h>

class FreqTab {
  private:
    int icounts[10];
  public:
    FreqTab() {
        for(int i=0; i<10; i++) icounts[i]=0;
    }
    void accept(int n) {
        assert(0 <= n && n <100);
        icounts[n / 10]++;
    }
    int interval(int i) {
        assert(0 <= i && i <10);
        return icounts[i];
    }
};
Next a small test program to read numbers, put them in a frequency table and finally retrieve the frequencies. 
#include <iostream>
using namespace std;
#include "freqtab.h"

void printStars(int c) {
    for(int i=0; i<c; i++) cout << "*";
}

int main() {
    FreqTab ft;
    int n;

    while(cin >> n)
        if(n >= 0 && n < 100) ft.accept(n);

    for(int i=0; i<10; i++) {
        cout << i << ": ";
        printStars(ft.interval(i));
        cout << "\n";
    }
}

8.7 Answers for subsection 5.5.1

The first exercise, to sort some numbers: 

//  function to sort an array of integers
//  and a test program 
#include <iostream>
using namespace std;
extern void sort(int, int[]);

int main() {
    int nums[6] = { 25, 4, 77, 2, 11, 1 };
    sort(nums, 6);
    for(int i=0; i<6; i++)
        cout << nums[i] << " ";
    cout << "\n";
}
void sort(int n[], int count) {
    bool changed = true;
    while( changed ) {
        changed = false;
        for(int i=0; i<count-1; i++)
            if(n[i] > n[i+1]) {
                int tmp = n[i];
                n[i] = n[i+1];
                n[i+1] = tmp;
                changed = true;
            }
    }
}
The second exercise to check whether lines of text are in ascending order: 
#include <iostream>
#include <string.h>
using namespace std;

int main() {
    char line1[132], line2[132];
    bool inorder=true;  /* assume in order */

    line1[0] = '\0';     /* the empty string is lexically
                           prior to any others */
    while(inorder && cin.getline(line2,132)) {
        if(strcmp(line1,line2) > 0)
        /* > 0 means 1st arg is lexically later than 2nd */
            inorder = false;
        strcpy(line1,line2);
    }
    if(inorder) cout << "In Order\n";
    else  cout << "Out of Order\n";
}


8.8 Answer for subsection 6.3.1 

#include <iostream>
using namespace std;

extern void sort(int, double[]);

int main(void) {
    int how_many;
    double *nums;
    cout << "how many numbers? > "; cin >> how_many;

    nums = new double[how_many];
    
    cout << "now input " << how_many << " reals\n";
    for(i=0;i<how_many;i++) cin >> nums[i];
    
    sort(how_many,nums);
    
    for(int i=0; i<how_many; i++) cout << nums[i] << " ";
    cout << "\n";
}

void sort(int count, double n[]) {
    bool changed = true;
    while( changed ) {
        changed = false;
        for(int i=0; i<count-1; i++)
            if(n[i] > n[i+1]) {
                double tmp = n[i];
                n[i] = n[i+1];
                n[i+1] = tmp;
                changed = true;
            }
    }
}

8.9 Answer for subsection 6.4.1

This is a version of Set that mimics List but because there is no order there are no putfirst and butfirst methods, instead there is a member function to test if an integer is present in the set. Also the add method must not allow elements to be repeated, so it uses member to avoid adding elements twice. First the header file set.h: 

#ifndef _SETH
#define _SETH
#include <assert.h>

class Set {
  private:
    class Cell {
      public:
        Cell(int v, Cell *n) {val=v; next=n;}
        int val;
        Cell *next;
    };
    Cell *rep;
  public:
    Set() { rep=0; }
    bool empty() {return 0==rep; }
    bool member(int e);
    void add(int i) {
        if( ! member(i) )  rep=new Cell(i,rep);
    }
    void remove(int e);
};
#endif _SETH
Now the code for the methods not defined in the class definition, file set.cc: 
#include "set.h"

bool Set::member(int e) {
    Cell *tmp = rep;
    while(tmp != 0) {
        if(tmp->val == e) return true;
        tmp = tmp->next;
    }
    return false;
}

void Set::remove(int e) {
    Cell *ptr = rep;

    if(0==ptr) return;
    if(ptr->val==e) {
        rep = ptr->next;
        delete ptr;
        return;
    }
    while(ptr->next != 0) {
        if(ptr->next->val == e) {
            Cell *t = ptr->next;
            ptr->next = ptr->next->next;
            delete t;
            return;
        }
        ptr = ptr->next;
    }
}
And lastly a simple program to test some parts of the set. This program deliberately adds a value three times and then removes it, if the class correctly implemented unique membership then the value will be gone. 
#include <iostream>
using namespace std;
#include "set.h"

int main() {
    Set s;

    cout << "adding 2 5 8 1 to the set\n";
    s.add(2); s.add(5); s.add(8); s.add(1);
    if(s.member(5))
        cout << "5 should be in the set, it is\n";
    else
        cout << "panic...\n";
    
    if(s.member(3))
        cout << "panic...\n";
    else
        cout << "3 should not be in the set, it isn't, good\n";
            
    s.add(1); s.add(1); // 1 add-ed 3 times, but should only be in once
    s.remove(1);        // remove it,
    cout << "added 1 twice more, and now removing it once\n";
    if(s.member(1))
        cout << "panic, 1 shouldn't be there now\n";
    else
        cout << "1 should not be in the set, it isn't, good\n";
}

8.10 Answer for subsection 6.5.1

This time the integer set is implemented using an internal list. This is completely transparent to client code. This the header file set.h: 

#ifndef _SETH
#define _SETH
#include <assert.h>
#include "list.h"

class Set {
  private:
    List srep;
  public:
    Set(): srep() { }
    bool empty() {return srep.empty(); }
    bool member(int e) { // can't be bothered to put this in set.cc
        Iterator i(srep);
        while(! i.done() ) {
            if(i.get() == e) return true;
            i.step();
        }
        return false;
    }
    void add(int e) {
        if( ! member(e) ) srep.putfirst(e);
    }
    void remove(int e) { srep.remove(e); }
    friend class SetIterator;
};
class SetIterator {
  private:
    Iterator li;
  public:
    SetIterator(Set s):li(s.srep) {  }
    bool done() { return li.done(); }
    int &get() { return li.get(); }
    void step() { li.step(); }
};
#endif _SETH
In this case there is no code file for the extra methods, because there are no methods not fully defined in the class. There should be, member has a loop and ought to be moved out of the class but I couldn't be bothered.

So on to the test program, which is exactly as before but has a simple function to test the SetIterator. 

#include <iostream>
using namespace std;
#include "set.h"

void printset(Set &s) {
    SetIterator si(s);
    for( ; ! si.done() ; si.step() ) cout << si.get() << " ";
}

int main() {
    Set s;

    cout << "adding 2 5 8 1 to the set\n";
    s.add(2); s.add(5); s.add(8); s.add(1);
    cout << "set contents at start: ";
    printset(s); cout << "\n";
    if(s.member(5))
        //  as in the previous test
        // ....
    cout << "set contents at end: ";
    printset(s); cout << "\n";
}


Footnotes

... declaration1
The extern is optional as the compiler can determine that the declaration only gives the type of a name and does not fully define the function, these lines are sometimes called prototypes.
... useful2
The use of reference parameters has already been briefly mentioned in section 3 Functions, this just provides a further example
Home
Page generated: 2004-10-11 by Bob Dickerson

© University of Hertfordshire Higher Education Corporation

Disclaimer