Subsections

On C++ and programming.

In this chapter I introduce C ++ and discuss how to run programs written in C ++. This is by no means a complete reference to programming in C ++, it is designed to give enough information to understand the rest of the book. This chapter also only discusses a subset of C ++, it concentrates on the parts of the language used in the remainder of this book. For really learning C ++ a textbook is necessary. I have found Lippman and Lajoie (1998) an excellent introduction to the language. The authorative source on the language is Stroustrup (1997).

Compiling and linking

To program in C ++ one has to first write a separate file with the program, which is then compiled into low-level instructions (machine language) and linked with libraries to make a complete executable program. The mechanics of doing the compiling and linking varies from system to system, and we leave these details as an exercise to the reader.

The structure of a C++ program

The first thing to realize about C ++ is that it is a strongly typed language. Everything must be declared before it is used, both variables and functions. C ++ has a few basic building blocks, which can be grouped into types, operations and functions.

Types

The types we will work with in this book are bool, int, long, double and string.

Here are some example definitions

bool this_is_true=true;
int i = 0;
long j = 123456789;
double pi = 3.141592653589793238462643;
string s("this is a string");
The most important part of C ++ comes from the fact that these basic types can be expanded by use of classes, of which more later.

Operations

To these basic types the common mathematical operations can be applied, such as addition, subtraction, multiplication and division:
int i = 100 + 50;
int j = 100 - 50;
int n = 100 * 2;
int m = 100 / 2;
These operations are defined for all the common datatypes, with exception of the string type. Such operations can be defined by the programmer for other datatypes as well.

Increment and decrement

In addition to these basic operations there are some additional operations with their own shorthand. An example we will be using often is incrementing and decrementing a variable. When we want to increase the value of one item by one, in most languages this is written:
int i=0;
i = i+1;
i = i-1;
In C++ this operation has its own shorthand
int i=0; 
i++;
i--;
While this does not seem intuitive, and it is excusable to think that this operation is not really necessary, it does come in handy for more abstract data constructs. For example, as we will see later, if one defines a date class with the necessary operations, to get the next date will simply be a matter of
date d(1,1,1995);
d++;
These two statements will result in the date in d being 2jan95.

Functions and libraries

In addition to the basic mathematical operations there is a large number of additional operations that can be performed on any type. However, these are not parts of the core language, they are implemented as standalone functions (most of which are actually written in C or C ++). These functions are included in the large library that comes with any C ++ installation. Since they are not part of the core language they must be defined to the compiler before they can be used. Such definitions are performed by means of the include statement.

For example, the mathematical operations of taking powers and performing exponentiation are defined in the mathematical library cmath. In the C ++ program one will write

#include <cmath>
cmath is actually a file with a large number of function defintions, among which one finds pow(x,n) which calculates $x^n$, and exp(r) which calculates $e^r$. The following programming stub calculates $a=2^2$ and $b=e^1$.

#include <cmath>
double a = pow(2,2);
double b = exp(1);
which will give the variables a and b values of 4 and 2.718281828..., respectively.

Templates and libraries

The use of libraries is not only limited to functions. Also included in the standard library is generic data structures, which can be used on any data type. The example we will be considering the most is the vector<>, which defines an array, or vector of variables.
#include <vector>
vector<double> M(2);
M[0]=1.0;
M[1]=2.0;
M.push_back(3);
This example defines an array with three elements of type double

\begin{displaymath}M = \left[
\begin{array}{c}
1\\
2\\
3
\end{array}\right]
\end{displaymath}

Note some pecularities here. When first defining the vector with the statement
vector<double> M(2);
we defined an array of 2 elements of type double, which we then proceeded to fill with the values 1 and 2. When filling the array we addressed each element directly. Note that in the statement
M[0]=1.0;
lies one of the prime traps for programmers coming to C or C ++ from another language. Indexing of arrays starts at zero, not at one. M[0] really means the first element of the array.

The last statement,

M.push_back(3);
shows the ability of the programmer of changing the size of the array after it has been defined. push_back is a standard operation on arrays which ``pushes'' the element onto the back of the array, extending the size of the array by one element. Most programming languages do not allow the programmer to specify variable-sized arrays ``on the fly.'' In FORTRAN or Pascal we would usually have to set a maximum length for each array, and hope that we would not need to exceed that length. The vector$<>$ template of C ++ gets rid of the programmers need for ``bookkeeping'' in such array manipulations.

Flow control

To repeat statements several times one will use on of the possibilities for flow control, such as the for or while constucts. For example, to repeat an operation n times one can use the following for loop:

for (int i=0; i<n; i++) { 
   some_operation(i); 
};
The for statement has tree parts. The first part gives the initial condition (i=0). The next part the terminal condition ( i$<$n), which says to stop when i$<$n is not fulfilled, which is at the n'th iteration. The last part is the increment statement (i++), saying what to do in each iteration. In this case the value of i is increased by one in each iteration. This is the typical for statement. One of the causes of C's reputation for terseness is the possibility of elaborate for constructs, which end up being almost impossible to read. In the algorithms presented in this book we will try to avoid any obfuscated for statements, and stick to the basic cases.

Input Output

For any program to do anything useful it needs to be able to output its results. Input and output operations is defined in a couple of libraries, iostream and fstream. The first covers in/output to standard terminals and the second in/output to files.

To write to standard output cout (the terminal), one will do as follows:

#include <iostream>
cout << "This is a test" << endl;
To write to a file "test.out", one will do as follows:
#include <fstream>
ofstream outf;
outf.open("test.out");
outf << "This is a test" << endl;
outf.clear();
outf.close();

Splitting up a program

Any nontrivial program in C ++ is split into several pieces. Usually each piece is written as a function which returns a value of a given type. To illustrate we provide a complete example program, shown in Code 1.1.

The program defines a function performing the mathematical power operation, power(x,n) which calculates $x^n$ through the simple identity $x^n=e^{n\ln(x)}$. This function is then used to calculate and print the first 5 powers of 2.


\begin{program}
% latex2html id marker 438\caption{A complete program}
\lgrindfile{/home/bernt/2003_algor/all_cc_tex_files/tst_power.cc}
\end{program}

When compiled, linked and run, the program will provide the following output

 2^1 = 2
 2^2 = 4
 2^3 = 8
 2^4 = 16
 2^5 = 32

Namespaces

To help in building large programs, the concept of a namespace was introduced. Namespaces are a means of keeping the variables and functions defined local to the context in which they are used. For now it is necessary to know that any function in the standard C ++ library lies in its own namespace, called the standard namespace. To actually access these library functons it is necessary to explicitly specify that one wants to access the standard namespace, by the statement

using namespace std;
Instead of such a general approach, one can also specify the namespace on an element by element basis, but this is more a topic for specialized C ++ texts, for the current purposes we will allow all routines access to the whole standard namespace.


Extending the language, the class concept.

One of the major advances of C ++ relative to other programming languages is the programmers ability to extend the language by creating new data types and defining standard operations on these data types. This ability is why C ++ is called an object oriented programming language, since much of the work in programming is done by creating objects. An object is best though of as a data structure with operations on it defined. How one uses an object is best shown by an example.

date, an example class

Consider the abstract concept of a date. A date can be specified in any number of ways. Let us limit ourselves to the Gregorian calendar. 12 august 2003 is a common way of specifying a date. However, it can also be represented by the strings: ``2003/8/12'', ``12/8/2003'' and so on, or by the number of years since 1 january 1900, the number of months since January, and the day of the month (which is how a UNIX programmer will think of it).

However, for most people writing programs the representation of a date is not relevant, they want to be able to enter dates in some abstract way, and then are conserned with such questions as:

A C ++ programmer will proceed to use a class that embodies these uses of the concept of a date. Typically one will look around for an extant class which has already implemented this, but we will show a trivial such date class as an example of how one can create a class.


\begin{program}
% latex2html id marker 468\caption{Defining a \texttt{date} class}
\lgrindfile{/home/bernt/2003_algor/all_cc_tex_files/date.h}
\end{program}

A class is defined in a header file, as shown in code 1.2. A number of things is worth noting here. As internal representation of the date is chosen the three integers day_, month_ and year_. This is the data structure which is then manipulated by the various functions defined below.

The functions are used to

After including this header file, programmers using such a class will then treat an object of type date just like any other.

For exmple,

date d(1,1,2001);
++d;

would result in the date object d containing the date 2 january 2001.

Any C ++ programmer who want to use this date object will only need to look at the header file to know what are the possible functions one can use with a date object, and be happy about not needing to know anything about how these functions are implemented. This is the encapsulation part of object oriented programming, all relevant information about the date object is specified by the header file. This is the only point of interaction, all details about implementation of the class objects and its functions is not used in code using this object.

Const references

Consider two alternative calls to a function, defined by function calls:

some_function(double r);
some_function(const double& r);

They both are called by an argument which is a double, and that argument is guaranteed to not be changed in the calling function, but they work differently. In the first case a copy of the variable referenced to in the argument is created for use in the function, but in the second case one uses the same variable, the argument is a reference to the location of the variable. The latter is more efficient, in particular when the argument is a large class. However, one worries that the variable referred to is changed in the function, which in most cases one do not want. Therefore the const qualifier, it says that the function can not modify its argument. The compiler will warn the programmer if an attempt is made to modify such a variable.

For efficiency, in most of the following routines arguments are therefore given as as constant references.

2003-10-22