by Conor Houghton is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
This is a program that prints out "Of man's first disobedience"; it is traditional to begin talking about a computer language by giving an example program which prints something out. This is often called a "Hello World!" example. The line numbers, and the space following the line numbers are not part of the program, they are just there to make it easier to explain what is happening. Sometimes the example numbers include letters, this is just a trick for adding extra examples without renumbering.
HelloWorld.cpp
1.1
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 cout << "Of man's first disobedience" << endl;
9
10 return 0;
11
12 }
This example looks quite complicated and obscure at first and contains statements that we won't think too hard at first, this example does give the standard form that all C++ programs take and we will discuss each part of this program soon. First, though here is how the program is run. Here, the dollar sign, $, is supposed to represent the prompt, the prompt does vary for different command shells, for example, it might read something like salmon ~/www/481++/text%.
1.2
1 $ g++ HelloWorld.cpp -o hw
2 $ ./hw
3 Of man's first disobedience
4 $
The command on line 1.2.1 compiles the program, that is, it converts it from the high level c++ code we can understand into the machine code the computer understands. g++ refers to the gcc compilers, other compilers will have different commands. After g++ is HelloWorld.cpp, the name of the program, after that is -o hw which tells it to name the machine code program hw; if the -o hw is omitted the program is given the default name a.out. On the next line the program is run. When the computer is given a command it looks in a set of standard places for the program corresponding to that command, unless you have set it up otherwise, the folder containing your program will not be one of those places, so the computer has to be told that in this case it should look for the program in the current folder, that is the role of the ./ in line 1.2.2, this ./hw tells the computer to run the program called hw in the current folder, the current folder is always called ".". The program runs and the output appears in line 1.2.3.
Lets go back to the actual program: before we begin, most spaces in a C++ program are there for visual convenience, it is useful to put lots of spaces in, but the convention is arbitrary since the compiler ignores them. Obviously in the program, in line 1.1.5 for example, the space between int and main is needed, the compiler wouldn't know what intmain meant, but the space between cout and << in line 1.1.8 is not needed, the compiler would know that cout<< is a cout followed by a << and so that space is only there to make the line easy to read. This is also true of new lines: lots of extra vertical space make the program easier to read. Now, to the program itself, line 1.1.1 is an instruction to the preprocessor; the preprocessor makes changes to the program before it is actually compiled. In this case it is including the iostream package. c++ has a core and a large set of packages, although input and output is an important part of most programs, it is nonetheless not in the core, but has to be loaded as a package. Without the #include<iostream> the part of the program that prints out the words "Of man's first disobedience" would not work. At the moment, this line should just be seen as something that is included in a standard c++ program.
The situation with line 1.1.3 is somewhat similar, it is not going to be immediately obvious why it is needed and it should be thought of as just a standard part of the program template. Roughly speaking c++ has what are called namespaces. The idea behind namespaces is to avoid accidently using names that the language is already using for something else. Here, for example, in the iostream package there is a command cout which is used for printing to screen; if you weren't used to the iostream package you might inadvertently use cout as a variable or whatever, causing complicated errors. To avoid this, any name used in iostream is put in a separate namespace called std, short for standard. Names in the std namespace are specified by the prefix std:: and this will distinguish them from any other use of the same names. Other commonly used packages use the std:: namespace. However, if you feel confident that you won't make a mistake by using a name that the language also used, writing std:: quickly becomes annoying; the command using namespace std; says that this prefix can be dropped, it says that the std namespace is being used and so the prefix isn't needed to tell the compiler where the name is. Without this command the program would look like this, with extra std::'s in line 1.3.8.
1 #include<iostream>
2
3
4
5 int main()
6 {
7
8 std::cout << "Of man's first disobedience" << std::endl;
9
10 //it is good practice to include the next line but most compilers won't mind if you leave it out.
11 return 0;
12
13 }
Next, line 1.1.5 has the main statement, the statements inside main are what are actually run, as you can see line 1.1.6 has a left brace, {, which is closed by a right brace, } on line 1.1.12. It is good practice, though not essential, to indent stuff enclosed in braces, it makes it easier to read the code. Emacs will indent automatically. Again, we won't worry too much about the form the main statement takes, it has a return type int which passes a value back to the computer when the program runs, in programs that interact with the computer in a sophisticated way this can be used to tell the computer whether or not the program has run successfully or not by passing back different values, here we just pass back the value 0, this is done on line 1.1.11. Again, this is something we will talk more about again and, as noted in line 1.3.10 you won't actually get an error if you leave this out. line 1.3.10 is a comment, the compiler ignores any line starting with //.
The actual printing is done in line 1.1.8. This is a statement and so it ends in a semicolon, ;, return 0; in line 1.1.10 and using namespace std; in line 1.1.3 also end with semicolons. cout is a stream, this can be thought of as a pipe leading from the program to the screen, the stream operator << adds stuff to the pipe, in this case it adds "Of man's first disobedience" and so that gets printed on the screen. The endl is also added, endl is short for end line and endl causes a carriage return. It does slightly more than that however, when a program is running it often delays output and input until it is convenient: the output is stored up "in the pipe" until there is a good moment for flushing out the pipe by actually outputting on the screen. This can be inconvenient and another effect of an endl is to flush the stream, that is print out everything that has been stored up for printing. Here it is not needed since the program finishes a line later and the stream is always flushed at the end, but it is something of a habit to flush screen output as it is made. flush also flushes the stream but without a carriage return. A \n in a string gives a carriage return without flushing, so the following is functionally identical to the HelloWorld.cpp program 1.1 despite the change to line 1.4.9. The backslash in \n is the notation used for what is called an escaped character, one that can't be typed. It should be also be noted that strictly speaking \n is a line feed and \r is a carriage return; basically \n finishes the line and returns the cursor to the start of the next line. Lines 1.4.2/3 also illustrate another way to do comments, anything appearing between a /* and */ is ignored.
1 #include<iostream>
2 /* this is another way
3 to do comments*/
4 using namespace std;
5
6 int main()
7 {
8
9 cout << "Of man's first disobedience\n"<< flush;
10
11 return 0;
12
13 }
Summary 1
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 SOME STATEMENTS
9
10 return 0;
11
12 }
In mathematics variables are quite a subtle idea and if we weren't so familiar with them, variables in c++ would be much more straight forward. In c++ when you declare a variable say x, the program reserves a memory location to store a value. x is the name of the variable and evaluating it returns the value at the memory location. As a program runs it evaluates expression; a variable evaluates to the value it stores.
Add.cpp
2.1
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 int a=2;
9
10 int b;
11 b=3;
12
13 cout<<a<<" "<<b<<" "<<a+b<<endl;
14 a=7;
15 cout<<a<<"\n"<<endl;
16 cout<<&a<<endl;
17 cout<<&b<<endl;
18
19 return 0;
20
21 }
Here we see it compiled and run. 2.2
1 $ g++ Add.cpp -o ad
2 $ ./ad
3 2 3 5
4 5
5
6 0x7fff32d681cc
7 0x7fff32d681c8
8 $
In the example Add.cpp a variable a is declared at line 2.1.8; first the variable type is specified, in this case int for integer, declaring the variable type tells the program how much memory to set aside, an int requires more memory than a bool for example, a bool short for boolean, can only take the values 0 and 1. Knowing the variable type also specifies which operations can be performed on the variable. An int can be added for example and on line line 2.1.13 that is what happens, we output the value of a, of b and of a+b. Along with declaring a and b we give them values, = is the assignment operator, b=3 gives b the value 3; it stores 3 at the memory location set aside for b.
Notice that a value can be assigned when the variable is declared, as with a in line 2.1.8, or the variable can be declared and given a value later, as with b in line 2.1.10/11. Even though a was given a value when it was declared, it can still be given a new value later as happens on line 2.1.14. When a variable is being declared, it can be initialized, given an initial value, this is effectively the same as assigning it a value and is done using a bracket: int a(3) declare an int a with the value 3, just as int a=3 does.
As a curio the actual memory locations are also printed out, &a is the memory location of a and this is printed out in line 2.2.6, this will vary from run to run, the program decides when it gets to the declaration of a where to store it. Luckily we needn't know anything about this, the high level language and the compiler hide this from us.
In the Add.cpp example, b=3 assigns a constant as the value of b; however, while the left hand side of an assignment statement has to be a variable, the right hand side only needs to something that returns a value when it is evaluated. There are all sorts of expressions that can appear on the right hand side; at the moment lets look at a simple example just using some simple algebra
Assign.cpp
2.1a
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 int a;
9 int b;
10 int c
11
12 a=2;
13 b=3;
14
15 c=a+b;
16
17 cout<<a<<" "<<b<<" "<<c<<endl;
18
19 c=c+a;
20
21 cout<<c<<endl;
22
23 c+=a;
24
25 cout<<c<<endl;
26
27 c++;
28
29 cout<<c<<endl;
30
31 ++c;
32
33 cout<<c<<endl;
34
35 return 0;
36
37 }
giving
2.1b
1 2 3 5
2 7
3 9
4 10
5 11
So, in line 2.1a.15 the right hand side of the assignment is an expression, this is evaluated to give 2+3=5 and c is set equal 5, as testified by line 2.1b.1. Next, in line 2.1a.19 we see that c itself can appear on the right hand side, the right hand side is read first by the program, it has to, it works out what value to assign before assigning it, so the value of c is used in the expression, giving 5+2=7 and this value is assigned to c, line 2.1b.2. In fact, expressions like this are so common that there is a short hand, for any variable foo for which addition is defined, foo+=bar is short for foo=foo+bar, there are similar -=, *= and /= assignment operators, line 2.1a.23 gives an example. Now, expressions like c+=1 are so common that it is given an even shorter short hand for adding one to a variable c++ and its near synonym ++c. There are also decrement operators c-- and --c which both have the effect of reducing the value of c by one.
Here is a list of some standard data types:
There are also, or example, long int and short
int data types, for most compilers, short ints have a
rather small range and use half the memory of an ordinary
This program uses the standard data types
DataTypes.cpp
2.1c
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 int a(-23);
9 cout<<a<<endl;
10
11 unsigned int b(23);
12 cout<<b<<endl;
13
14 bool c(false);
15 cout<<c<<endl;
16
17 cout.precision(22);
18
19 float d(3.14159265358979323846);
20 cout<<d<<endl;
21
22 double e(3.14159265358979323846);
23 cout<<e<<endl;
24
25 char f('E');
26 cout<<f<<endl;
27 }
which gives output
2.1d
1 -23
2 23
3 0
4 3.141592741012573242188
5 3.141592653589793115998
6 E
Without worrying about its syntax, statement cout.precision(22) at line 2.1c.17 changes the precision that cout outputs at; it is normally six significant figures and cout.precision(22) changes it to 22. This is larger than the precision of either the float or the double data type, you can see on lines 2.1d.4/5 that the float produces nonsense after eight significant figures and the double after 16. In line 2.1c.3 we see that for bools false has the value 0, true has the value 1.
One important point is that different data types have different operations and, in fact, the same operation can behave differently for different data types. For example if you take one unsigned int from another the answer is assumed to be an unsigned int.
UIntAdd.cpp
2.3a
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 unsigned int a=2,b=1;
9 cout<<a-b<<endl;
10 cout<<b-a<<endl;
11
12 }
giving
2.3b
1 $ g++ UIntAdd.cpp -o ui
2 $ ./ui
3 1
4 4294967295
5 $
It assumes a-b is an unsigned int which is fine, it is 1, it also assumes b-a is; this is a problem since it gives -1, a negative number, as you can see in line 2.4.4 it responds by assigning it a nonsense value. Notice, by the way, in line 2.3a.8 the same int is used to declare two variables, separated by commas. It is possible to get around this by casting the data; this instructs the program to reinterpret one type as another, see line 2.4.9
Cast.cpp
2.4
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 unsigned int a=2,b=1;
9 cout<<int(b)-int(a)<<endl;
10
11 char letter='e';
12 cout<<letter<<endl;
13 cout<<int(letter)<<endl;
14
15 double x=1.2;
16 cout<<int(x)<<endl;
17 int c=x;
18 cout<<c<<endl;
19 }
giving
2.5
1 $ g++ Cast.cpp -o ca
2 $ ./ca
3 -1
4 e
5 101
6 1
7 1
8 $
As you can see from lines 2.5.5 and 2.4.13 a char can be cast to an int; a char stores numbers not characters, but when evaluated, converts that number to a character; if you cast the char to an int you get the number instead. As lines 2.5.6 and 2.4.15/16 shows, doubles cast to ints by rounding down. Finally assignments between types are often cast automatically, as lines 2.5.7 and 2.4.17/18 shows.
One data type we haven't covered is string: unlike the
data types above string has to be loaded as a separate
package, if you want to use strings in a program, you need
to have a #include
String.cpp
2.6
1 #include<iostream>
2 #include<string>
3
4 using namespace std;
5
6 int main()
7 {
8
9 string line1="Of man's first disobedience";
10 cout<<line1<<endl;
11
12 string line2="and the fruit of that forbidden tree";
13
14 string twoLines=line1+" "+line2;
15
16 cout<<twoLines<<endl;
17
18 cout<<twoLines.length()<<endl;
19 cout<<twoLines.at(5)<<endl;
20 }
giving
2.7
1 Of man's first disobedience
2 Of man's first disobedience and the fruit of that forbidden tree
3 64
4 n
Thus, line1 stores "Of man's first disobedience". Notice in lines 2.6.14 and 2.6.2 that addition for strings is defined as concatenation. The string data type or class has other functions defined along with addition. The length of the string twoLines is given at line 2.6.18. The program prints out twoLines.length() which is the output of the string function length() applied to the string twoLines. Put another way, since twoLines is an instance of a string it has a set of functions which can be called, they are called using a dot and the function name and the brackets. In the case of length, the brackets are empty, this is because length() doesn't have an argument. In lines 2.6.19 and 2.7.4 we see another function, at(int i) which takes an integer argument and returns the character at the integer, in this case "n"; noting that it counts from 0 so twoLines.at(0) would return "O" from "Of".
There is another, older, synatax which is almost equivalent to at(int i): [int i]. twolines[5] would of had the same effect. However, this is method is not as good, firstly, it is ugly, it doesn't conform with other language conventions as well as at(int i) and secondly, it is not range safe. If you wrote twoLines.at(64) you would get a runtime out of range error because twoLine only has 64 letters and, counting from 0, twoLines.at(64) attempts to return the 65th letter. twoLines[64] will also do something wrong, but the consequence is less predictable and may not be so easy to find.
One important aspect of variables is that they are scoped, this means they are only declared inside the current block of code, delimited by braces. This is something we will see more of later, but here is an example.
Scope.cpp
2.8
1 #include<iostream>
2 #include<string>
3
4 using namespace std;
5
6 int main()
7 {
8
9 string line;
10
11 {
12 string word("disobedience");
13 line="Of man's first "+word;
14 }
15
19 cout<<line<<endl;
20 }
which will print out Of man's first disobedience. line is declared in the main scope, however, word is scoped inside the braces at lines 2.8.11/14, if you tried to print out word at line 2.8.19 you would get an error because line is not declared outside of its scope, the program creates it at the declaration, line 2.8.12 and then deletes it when it goes out of scope at line 2.8.14. Obviously, here, the braces have only been put in to scope the variable word, this is actually sometimes useful, but in most examples, the brackets are also there for other reasons. Scoping can be subtle if a variable name is repeated, the more local name takes precedence over the less local one.
Scope_2.9.cpp
2.9
1 #include<iostream>
2 #include<string>
3
4 using namespace std;
5
6 int main()
7 {
8
9 string line("Of man's first disobedience");
10
11 {
12 string line;
13 line="And the fruit of that forbidden tree";
14 }
15
16 cout<<line<<endl;
1 }
returns Of man's first disobedience, the assignment to "And the fruit of that forbidden tree" happens only to the local line scoped inside the braces.
Summary 2
Exercises 2
Consider the following programme
If.cpp
3.1
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 cout<<"Choose an integer"<<endl;
9 int number;
10 cin >> number;
11
12 int remainder=number%2;
13
14 if(remainder==0)
15 cout<<"even"<<endl;
16 else
17 cout<<"odd"<<endl;
18
19 return 0;
20 }
In line 3.1.10 this programme contains the input stream cin, this is like the output stream cout, but the pipe goes the other way, from the screen back to the programme. It allows input; when the programme gets to the cin command it waits until a number is inputed and then gives that value to number using the stream operator >>. There is a novel arithmetic operation at line 3.1.12, in addition to the obvious addition, +, subtraction, -, multiplication , * and division, /, c++ has a modulus operator % which finds a remainder, so a%b is the remainder when a is divided by b and, for example, 15%4 returns 3.
These technicalities over with, the important part of the programme is at lines 3.1.14-17 where there is an if statement. Here are two runs of the programme.
3.2
1 g++ If.cpp -o if
2 $ ./if
3 Choose an integer
4 42
5 even
6 $ ./if
7 Choose an integer
8 69
9 odd
lines 3.2.4 and 3.4.8 are my input, the first time I chose an even number and the computer replied even, the second time an odd number and the computer replied odd. This works because the if statement at line 3.1.14 evaluates a boolean expression remainder==0 and the programme executes line 3.1.15 if the expression is true and line 3.1.17 if it is false. In the boolean expression we have ==; this means equals, it has the two = signs to distinguish it from the assignment operator. Using only one = when you mean to use two is an error that is easy to make and very hard to spot. Now, if the boolean expression is true, the statement after if is executed, if it is false, the statement after else executes. Further choices can be added using one or more else if and further statements by using braces.
Bigger.cpp
3.3
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 cout<<"Choose a big integer"<<endl;
9 int big;
10 cin >> big;
11
12 cout<<"Choose a small integer"<<endl;
13 int small;
14 cin >> small;
15
16 if(big<small)
17 {
18 cout<<"big is smaller than small: swapping"<<endl;
19 int temp=small;
20 small=big;
21 big=temp;
22 }
23 else if(big==small)
24 cout<<"equal"<<endl;
25 else
26 cout<<"big is bigger than small"<<endl;
27
28 cout<<"\nbig: "<<big<<" small: "<<small<<endl;
29
30 return 0;
31 }
So, if big<small is true, the programme executes the lines between the braces at line 3.3.17 and line 3.3.22; these lines swap big and small so that they are the right way around, note in passing that the int introduced in line 3.3.19 to do the swap only exists inside the scope of the braces, that is between line 3.3.17 and line 3.3.22. If big<small is false, the programme checks the next condition else if(big==small), if big==small is true then the statement at line 3.3.24 is executed, there is only one statement here so no braces are needed. Finally if neither of these is true, the statement following the else, line 3.3.26 is executed. Often you only need to do something if the boolean expression is true and nothing if it is false and, in fact, there is no syntactical requirement for the else statement if it is not needed.
There are other relational operators
Relational.cpp
3.4
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 cout<<"Choose the first integer"<<endl;
9 int first;
10 cin >> first;
11
12 cout<<"Choose the second integer"<<endl;
13 int second;
14 cin >> second;
15
16 if(first!= second)
17 cout<<"the integers are not equal"<<endl;
18
19 if(first>= second)
20 cout<<"the first integer is not less than the second"<<endl;
21
19 if(first<= second)
20 cout<<"the first integer is not greater than the second"<<endl;
29
30 return 0;
31 }
The != in line 3.4.16 is not equal, so (a!=b) will return true if a is not equal to b. The less than or equal to and greater than or equal to operators in lines 3.4.19 and 3.4.16 have the obvious meanings. The exclamation mark is used more generally for negation, so if expression is true !expression is false and vice versa.
Negation.cpp
3.5
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 bool aTrueThing=true;
9
10 if(aTrueThing)
11 cout<<"aTrueThing is true"<<endl;
12
13 if(!aTrueThing)
14 cout<<"not aTrueThing is true"<<endl;
15 else
16 cout<<"not aTrueThing is false"<<endl;
17 }
which gives
3.6
1 aTrueThing is true
2 not aTrueThing is false
Negation, !, is a logical operator; there are two more: && for and and || for or. They have their usual logical meaning: (a&&b) is true if a is true and b is true, it is false otherwise. (a||b) is true if a is true or b is true, so it is only false if a and b are both false.
Logic.cpp
3.7
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 cout<<"Choose the first integer"<<endl;
9 int first;
10 cin >> first;
11
12 cout<<"Choose the second integer"<<endl;
13 int second;
14 cin >> second;
15
16 if(first>0&&second>0)
17 cout<<"the integers are both positive"<<endl;
18 else if(first>0||second>0)
19 cout<<"the first multiplied by the second will be negative"<<endl;
20 else
21 cout<<"the integers are both negative"<<endl;
22
23 return 0;
24 }
A boolean expression with an && is evaluated in a lazy way: in (a&&b) the expression b is not evaluated if a is false, there is no need, since if a is false so must (a&&b) be false as well. This can be useful if evaluating b could cause an error when a is false.
In fact, it is harder than you might think to find simple statement that causes a run-time error, modern compilers give programmes that can deal gracefully with division by zero. The following contrived illustrative example exploits the fact that all statements return a value, so when you have a cout statement, as well as printing to screen it returns a value which casts to true; when you output the value of a boolean, it prints as 1 for true and 0 for false. Anyway, the point is checking the second boolean expression will print if the second part of the boolean expression is evaluated, something that only happens if number is positive.
LazyAnd.cpp
3.8
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8 cout<<"Choose a number"<<endl;
9 int number;
10 cin >> number;
11
12 cout<<bool(cout<<"successfully outputing casts to true"<<endl)<<endl;
13
14 if(first>0&&cout<<"checking the second boolean expression"<<endl)
15 cout<<"The number is positive"<<endl;
16
17 return 0;
18 }
Exercises 3
When people talk about what computers are good at, they often mention boring repetitive computational tasks and it is certainly true that most scientific programs involve the computer to do almost the same calculation again and again. This is a loop and the two main ways to do loops in c++ are for and while.
ForAdd.cpp
4.1
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8
9 int high=100;
10
11
12 int total=0;
13 for(int i=0;i<=high;i++)
14 total+=i;
15
16 cout<<"Sum of the numbers from 0 to "<<high<<" is "<<total<<endl;
17
18 return 0;
19 }
ForAdd.cpp (4.1 is a program for adding all the numbers from zero to 100; as you all know you don't need a computer for this, you just pair up 0 with 100, 1 with 99, 2 with 98 and so, so each pair makes a 100 and every number is paired except 50, so the answer is 5050. Lets pretend we don't know the trick: the loop is at lines 4.1.13/14 and is controlled by the for statement. The for statement has three arguements seperated by semicolons. Each is an expression and so the semicolon makes some sense; the first arguement declares and initializes a variable, in this case an int named i initialized to zero. The next statement is a boolean expression, the loop will continue as long as this is true, here the expression is i<=high which remains true until i gets to 101, at which point the loop is not executed and the program continues with the next line, in this case the cout on line 4.1.16. The final statement is a command which is run at the end of each loop, here i++, increasing i each time. Now the i, declared where it is, is only scoped inside the loop, which is very useful since you may need to do lots of loops and it would be inconvient to end up with lots of variables declared for different loops: in fact, at line 4.1.15 i will have been deleted and the name i could be used again for something else.
One thing you have to realise is that the syntax of the for statement is designed for convenience and legibility as well as computational constraints. For example, the i could have been declared before the loop and the increament, i++ could have been written at the end of the loop where it actually occurs
ForAdd_4.2.cpp
4.2
1 #include<iostream>
2
3 using namespace std;
4
5 int main()
6 {
7
8
9 int high=100;
10
11
12 int total=0;
13
14 {
15 int i=0;
16
17 for(;i<=high;)
18 {
19 total+=i;
20 i++;
21 }
22 }
23
24 cout<<"Sum of the numbers from 0 to "<<high<<" is "<<total<<endl;
25
26 return 0;
27 }
In 4.2 the first and third arguement of the for statement are blank, the declaration and initialization are done at line 4.2.15 and the braces at lines 4.2.14/22 restrict the scope of i the same way it would be restricted if it have been declared in the for statement; the increment is now done at line 4.2.20. In fact, we will see later on that the while statement is identical to the for statement with the first and third arguement blank and they can both perform the same function. However, the particular convenience of the normal for statement is that it allows the three important parts, the declaration and initialization of the loop variable, the boolean expression that limits the loop and the principle change to the loop variable, to be kept in one place. In 4.2 you should also note the braces at lines 4.2.18/21 bracket the loop, something we need to do when the loop contains more than one line of statement.
The next program is just another if example, it examines the accuracy of the Euler method for solving the growth equation f'=rf. Euler's method is the simple approach of dividing time into time steps and making f increase by f' by the step size for each step, it basically uses the first order approximation in the Taylor expansion.
Growth.cpp
4.3
1 #include<iostream>
2 #include<cmath>
3
4 using namespace std;
5
6 int main()
7 {
8
9 double r=1.5;
10
11 double x0=0;
12 double x1=5;
13 double f0=2;
14
15
16 deltaX=.1;
17
18 double f=f0;
19 for(double x=x0;x<=x1;x+=deltaX)
20 {
21 f+=r*f*deltaX;
22 cout<<x<<" "<<f<<" "<<f0*exp(r*(x-x0))<<endl;
23 }
24
25 return 0;
26 }
The for loop in this program, lines 4.3.19-23, is pretty unremarkable, it has two statements in the loop so it uses braces and it the loop variable is a double which increases an amount deltaX at the end of each iteration.
There are a few other things to note about this program. First, the cmath package is included at the start, this is so that we exp available at line 4.3.22; if we weren't using the std namespace this would be std::exp. Furthermore, notice that I avoid using numbers in the program proper, instead defining parameters, like $r$, the rate, at the start, this is good practise, it makes it easier to change the parameters later, even if you don't think this will ever happen, you should declare parameters at the start, just in case. Finally running the program just gives a long stream of numbers; it is nice to plot them. Perhaps the easiest way to do this is to redirect the output into a file.
4.4
1 $g++ Growth.cpp -o gr
2 $ ./gr > Growth.dat
So, in line 4.4.2 I have redirected the output to the file Growth.dat, a name I chose for convenience and not because I had to chose a name that coincided with the program name. The redirect, a greater than symbol, >, is a unix command that sends what should have been printed on the screen into a file. Hence, the program doesn't output to file, as far as it is concerned it is outputting to screen, however, this output is being redirected by the shell, the window where the output would have appeared. It is not difficult to add an output to file into the program, however, for very simple output a redirect is often simpler. The redirect will create the Growth.dat if it doesn't exist, if it does, it will delete the previous contents; a similar redirect >> will create the file if it doesn't exist, but append to its current contents if it does.
Growth.dat is a simple text file containing the three columns of numbers. The file can be opened in emacs, it can be printed out using the unix command cat as in cat Growth.dat, the first few lines can be printed out using head Growth.dat or the last few using tail Growth.dat. Now, awk, for example, could be used to do calculations on the columns. However, the obvious thing to do here would be to graph the data. Perhaps the quickest way to do that is to use gnuplot. Input gnuplot into the command line in the same directory as Growth.dat to enter gnuplot and then use
4.5
1 gnuplot> plot "Growth.dat" using 1:2 with lines
2 gnuplot> replot "Growth.dat" using 1:3 with lines
The first gnuplot command, line 4.5.1 tells it to plot the data in Growth.dat using columns 1 and 2 with the plot done with lines. The second line, line 4.5.2 is the same but it plots columns 1 and 3 and it has a replot command instead of a plot command, this means the graph is added on top of the previous one, instead of plotting a completely new graph. In gnuplot using can be abbreviated to us and with to w.
As mentioned above, the while is similar to the for loop and is used when it is not useful to include a declaration and increment. The syntax is while(boolean) followed by some statements enclosed in braces where, as with for and if, the braces aren't needed if there is only one statement. The loop continues as long as the boolean evaluates to true. There is an example below where a letter is removed from a word with each iteration of the loop.
EraseString.cpp
4.6
1 #include<iostream>
2 #include<string>
3 using namespace std;
4 int main()
5 {
6 string word;
7 cout<<"Input your favourite word!"<<endl;
8 cin >> word;
9 while(word.length()>0)
10 {
11
12 char letter=word.at(0);
13 word.erase(0,1);
14 cout<<letter;
15
16 if(word.length()!=0)
17 cout<<"*";
18
19 }
20
21 cout<<endl;
23
23 return 0;
24 }
giving
4.7
1 Input your favourite word!
2 Elbow
3 E*l*b*o*w
This program uses a few methods in the string class: word.length() returns the length of word and so word.length()>0 at line 4.6.9 is true until all the letters in word have been erased. In line 4.6.12 word.at(0) returns the first letter in word as a char and it is assigned to the char names letter; in the next line word.erase(0,1) erases one letter of word starting with the first, 0th, one. The purpose of the if in line 4.6.16 is to have the program only print *s between the letters, not after the last one when word.length()==0.
Exercises 4
At their simplest functions can be thought of as a way to organize code, to make it easier to read and to avoid repetition; in fact, we have seen functions before, computer programmes are designed around functions, statements that take arguments and return a value. What we look at here is how the programmer defines functions.
3nPlus1.cpp
5.1
1 //http://en.wikipedia.org/wiki/Collatz_conjecture
2
3 #include<iostream>
4
5 using namespace std;
6
7 int update(int integer)
8 {
9 if(integer%2==0)
10 return integer/2;
11 else
12 return 3*integer+1;
13 }
14
15
16 int main()
17 {
18
19 cout<<"Choose an integer"<<endl;
20 int number;
21 cin >> number;
22
23 while(number!=1)
24 {
25 cout<<number<<endl;
26 number=update(number);
27 }
28
29 cout<<"1"<<endl;
30
31 return 0;
32 }
The Collatz conjecture holds that if you choose any positive integer and successively halve it if it is even or triple it and add one if it is odd, you will eventually get to one. This programme illustrates this. For our purposes here the important thing is the code at line 5.1.3-13; this defines the function int update(int number). Inside the loop in the main programme at line 5.1.26 the function is called when number is assigned the value update(number). Inside the function there is a local int called integer and it is assigned the value of number. The function returns a int and when it gets to a return statement it returns the value following the return, in this case either integer/2 or 3*integer+1.
The function statement has three parts and is written with the return type, followed by the function name, followed by the parameters in brackets, each of which is also given a datatype. The function is written at the top of the programme because the compiler needs to know that about the function when it gets to line 5.1.26 where it is called; otherwise it would not know what sort of object update(number) is. However, it can be very messy having all the functions written at the top and it is possible to prototype the function; this basically means that there is a one line statement at the top of the programme which gives the compiler the information it needs as it is compiling main, the function proper is elsewhere, at the bottom of the file, or even in a different file, and the compiler links that in when it gets to it. The easiest thing is to look at an example.
1 #include<iostream>
2
3 using namespace std;
4
5 int update(int number);
6
7 int main()
8 {
9
10 cout<<"Choose an integer"<<endl;
11 int number;
12 cin >> number;
13
14 while(number!=1)
15 {
16 cout<<number<<endl;
17 number=update(number);
18 }
19
20 cout<<"1"<<endl;
21
22 return 0;
23 }
24
25 int update(int number)
26 {
27 if(number%2==0)
28 return number/2;
29 else
30 return 3*number+1;
31 }
The prototype is at line 5.2.5; it is the same as the function statement except it ends in a semicolon instead of a curly-brackets delimited block giving the function commands, the function itself is at lines 5.2.25-31.
Functions can call themselves, this is known as recursion; this is usually used to write a factorization example, here I use it in another version of the 3nPlus1 programme.
1 #include<iostream>
2
3 using namespace std;
4
5 void update(int number);
6
7 int main()
8 {
9
10 cout<<"Choose an integer"<<endl;
11 int number;
12 cin >> number;
13
14 cout<<endl;
15
16 update(number);
17
18 return 0;
19 }
20
21
22 void update(int number)
23 {
24 cout<<number<<endl;
25
26 if (number==1)
27 return;
28
29 if(number%2==0)
30 update(number/2);
31 else
32 update(3*number+1);
33 }
Now the function only gets called once from inside the main function; in the function itself, it prints out the value of number and stops if it is one, otherwise it calls itself with the value number/2 or 3*number+1. This function does not return a value and so it is given the return value void in the prototype at line 5.3.5 and at the start of the function statement at line 5.3.22.
Here is another example
Cursing.cpp
5.4
1 #include<iostream>
2 #include<cstdlib>
3 #include<ctime>
4
5 using namespace std;
6
7
8 void curse(int);
9 int rand0To3();
10
11 int main()
12 {
13
14 srand ( time(NULL) );
15
16 curse(rand0To3());
17
18 return 0;
19 }
20
21 void curse(int number)
22 {
23 switch(number)
24 {
25 case 0:
26 cout<<"Meatus"<<endl;
27 return;
28 case 1:
29 cout<<"Belguim"<<endl;
30 return;
31 case 2:
32 cout<<"R*!&%er"<<endl;
33 return;
34 case 3:
35 cout<<"Tanj"<<endl;
36 return;
37 default:
38 cout<<"f/p"<<endl;
39 return;
40 }
41 }
42
43 int rand0To3()
44 {
45 return int(4*double(rand())/(double(RAND_MAX)+1));
46 }
In this programme there are there two functions, void curse(int number) and int rand0To3(), one does not return anything so its type is void, the other has no argument so it has an empty pair of round brackets. These functions are prototyped at the start, at lines 5.4.8/9; notice that the prototype does not actually need the variable names for the arguments, these are only needed in the actual function definition, all the prototype needs is the datatypes of the arguments. It is, however, quite common to leave the variable names in, partly because it sometimes helps, for complicated function, to remember which argument is which, are partly, because the prototype is often cut-and-pasted from the function definition.
At line 5.4.16 curse; its argument is something that evaluates to an integer, rand0To3(). The call to rand0To3 returns a number between 0 and 3 inclusive and using a switch statement curse prints out one of four curses, depending on what value is passed to it. This shows that an argument can be another function, provided the function evaluates to the correct type, the compiler can check that it does evaluate to the right type because it has read the prototype at line 5.4.9. Notice as well that there is no need for break statements, the returns perform the same function of preventing the programme from executing the rest of the statements in the switch block.
The Cursing.cpp programme uses the random number generator; this is done inside rand0To3. Of course, one advantage of writing things in functions is that provided you are told what a function does and what its interface is, and provided you trust the person who wrote it, you can use the function without knowing precisely how it does what it does. Furthermore, if you discover a better way of doing something, having it in a function allows you to change in only one place. This might actually happen with the c++ random number generator, better random number support is likely to be included in the next version of the language.
The random number generator is included in the cstdlib package and so this must be included, this happens at line 5.4.2. The statement rand() returns an integer between zero and a large number RAND_MAX; this number of often equal the maximum possible int. Here you can see the c-style syntax with a pre-defined global variable; a more c++ syntax would have a function which returns this value. Anyway, with suitable casting to doubles rand() is divided by RAND_MAX+1 to give a number in [0,1); multiplying by four and casting to an integer gives the required random number. An alternative way of doing this is to use modulo:
5.5
42
43 int rand0To3()
44 {
45 return rand()%4;
46 }
The random numbers produced by rand() are, of course, actually calculated by a deterministic algorithm seeded by an initial condition. Since the default seed is always the same, unless the seed is explicitly changed, a programme will always produce the same random numbers, sometimes this is useful, but if it isn't then the usual way of getting different random numbers each time is to seed the random number generator using the internal clock. This requires that ctime is included, as it is in line 5.4.3; the random number generator is seeded at line 5.4.14.
Two function can have the same name provided they have different argument datatypes, the signature of the argument list allows the compiler to identify which function is being called. This is not true of the return type, having two function which differ only in return type will cause an error. Here is an example of a programme where two functions have the same name:
Adding.cpp
5.6
1 #include<iostream>
2
3 using namespace std;
4
5
6 int add(int,int);
7 char add(char,int);
8
9 int main()
10 {
11
12 cout<<add(5,3)<<" "<<add('h',3)<<endl;
13
14 return 0;
15 }
16
17 int add(int a, int b)
18 {
19 return a+b;
20 }
21
22 char add(char letter,int number)
23 {
24 int newNumber=int(letter)+number;
25
26 if(newNumber>127)
27 newNumber-=96;
28
29 return newNumber;
30 }
In the argument list new variables are declared and initialized with the call value, in other words, in Adding.cpp for example, the char letter declared in line 5.6.22 is a new char scoped to the function; while it is initialized by the value of the variable letter in main it is a different variable. This is called passing by copy and the next example is the standard illustration of how passing by copy works.
BadSwap.cpp
5.7
1 #include<iostream>
2
3 using namespace std;
4
5 void swap(int a,int b);
6
7 int main()
8 {
9
10 int a=4;
11 int b=1;
12
13 cout<<"inside main, before a="<<a<<" b="<<b<<endl;
14
15 swap(a,b);
16
17 cout<<"inside main, after a="<<a<<" b="<<b<<endl;
18
19 }
20
21
22 void swap(int a,int b)
23 {
24
25 cout<<"inside swap, before a="<<a<<" b="<<b<<endl;
26
27 int c=a;
28 a=b;
29 b=c;
30
31 cout<<"inside swap, after a="<<a<<" b="<<b<<endl;
32
33 }
Which has output
5.8
1 inside main, before a=4 b=1
2 inside swap, before a=4 b=1
3 inside swap, after a=1 b=4
4 inside main, after a=4 b=1
So, although the a and b inside swap are swapped, this doesn't swap the a and b in main. There are two alternatives to passing by copy, one involves pointers, which we won't deal with here, and the other is passing by reference. When a variable is passed by reference, the function is told where the calling variable is, and works with that variable instead of making its own; the syntax for passing by reference is simple, an ampersand & is added after the data type in the parameter list
Swap.cpp
5.9
1 #include<iostream>
2
3 using namespace std;
4
5 void swap(int & a,int & b);
6
7 int main()
8 {
9
10 int a=4;
11 int b=1;
12
13 cout<<"inside main, before a="<<a<<" b="<<b<<endl;
14
15 swap(a,b);
16
17 cout<<"inside main, after a="<<a<<" b="<<b<<endl;
18
19 }
20
21
22 void swap(int & c,int & d)
23 {
24
25 cout<<"inside swap, before c="<<c<<" d="<<d<<endl;
26
27 int e=a;
28 c=d;
29 d=e;
30
31 cout<<"inside swap, after c="<<c<<" d="<<d<<endl;
32
33 }
Now, noting the ampersand at lines 5.9.5 and 5.9.22, the c and d inside swap are references to the variables a and b, I have changed the names of the variables in swap so as to make this easier to explain, but they could just as well of being a and b. Variables inside a scope are like dummy indices in sums, it does not matter what they are called; in BadSwap.cpp the a and b inside the swap function are new variables scoped to the function, in Swap.cpp c and d are references to the a and b in the main and the output is
5.10
1 inside main, before a=4 b=1
2 inside swap, before c=4 d=1
3 inside swap, after c=1 d=4
4 inside main, after a=1 b=4
There are two main reasons to use pass by reference, the first is the one illustrated here, where we want the function to act on more than one variable: a function can only return one value, using references allows more than one value to be recovered from the action of the function. The other reason has to do with speed and memory, we have only been using simple, small, datatypes so far, ints, doubles and so on. Soon we will start looking at more complex datatypes, vectors, vectors of vectors and then classes and these can take some time to copy, making a pass by copy expensive from a performance point of view, passing by reference does not carry that expense, however, you need to be aware that if something is passed by reference and changed in the function, it is changed elsewhere as well. We will see that using const in the datatype can help protect against errors of this sort.
Exercises 5
Templates are a powerful tool in c++ that allow generic programming, they allow, for example, functions to be defined where the datatype of the arguments aren't fully specified. We aren't going to talk about templates here, but we will discuss a library called the standard template library, or STL, which includes what are called container classes; things like vectors and lists. It is also possible to define vectors in c++ using the old c-like array syntax, but the STL container classes are better.
The vector is probably the most straight-forward container; the syntax is illustrated in this programme
Vectors.cpp
6.1
1 #include<iostream>
2 #include<vector>
3
4 using namespace std;
5
6 void print(const vector<int> & v);
7 vector<int> operator+(const vector<int> & a,const vector<int> & b);
8
9 int main()
10 {
11
12 int vectorN=10;
13
14 vector<int> v;
15
16 cout<<"the size of v is"<<v.size()<<endl;
17
18 for(unsigned int i=0;i<vectorN ;++i)
19 v.push_back(i);
20
21 cout<<"the size of v is"<<v.size()<<endl;
22
23 vector<int> w(10,1);
24
25 cout<<"v=";
26 print(v);
27
28 cout<<"w=";
29 print(w);
30
31 cout<<"v+w=";
32 print(v+w);
33
34 return 0;
35 }
36
37 void print(const vector<int> & v)
38 {
39
40 cout<<"[";
41 for(unsigned int i=0;i<v.size() ;++i)
42 {
43 cout<<v.at(i);
44 if(i!=v.size()-1)
45 cout<<" ";
46 else
47 cout<<"]";
48 }
49
50 cout<<endl;
51
52 return;
53 }
54
55 vector<int> operator+(const vector<int> & a,const vector<int> & b)
56 {
57 vector<int> c;
58
59 for(unsigned int i=0;i<a.size() ;++i)
60 c.push_back(a.at(i)+b.at(i));
61
62 return c;
63
64 }
First of all there is an include at line 6.1.2 to include the vector package; there are two function prototypes on lines 6.1.6 and 6.1.7, these functions will be discussed in detail later but the simpler is the first print which will print out a vector. The first vector v is declared at line 6.1 14; this is just like any of the other variable declarations we have seen before except the datatype itself has an argument in angle brackets, in this case this declares what the vector is a vector of; hence vector<int> declares a vector of ints. The vector isn't initialized and so the default initialization is called, giving an empty vector. The statement at line 6.1.19 calls the vector class's push_back method, this makes the vector one longer by adding the value in the brackets, i here to the vector. We can see this because v.size() returns the size of v and at lines 6.1.16 and 6.1.21 this is printed out before and after the values from zero to nine are pushed back onto the vector.
After the vector has been filled with the values zero to nine these values are printed out in the print function at lines 6.1.37-53. cout can't print out vectors, it isn't a datatype it knows how to handle and so, instead, each of the entries of the vector are sent to the cout one by one; v.at(i) returns the ith entry of v remembering that the entries are numbered from zero. There are actually two ways to access elements of a vector by index, v.at(i) as we have seen and v[i]. The second method has some advantages; it uses the same notation as arrays in c; though the syntax is different, and it kind of makes mathematical sense if you want to think about v as a map from the index set to the datatype of the entries. However, v.at(i) is better; if it is used with i out of the range of entries of v the programme will fail with an error; if this happens v[i] it may give an error, but it will be a more obscure error and it may not fail at all but will continue to run with a nonsense value, leading to a wrong results or a confusing error later in the run. Unfortunately some older compilers do not support the at(i) method and so, at the moment, [i] needs to be used if the code needs to be portable.
On line 6.1.23 a second vector is defined, this uses a different method for initializing the vector, this takes two values, the first, an int gives the size of the vector, in this case 10 and the second gives a value for the entries, in this case the entries are ints and the value is 1.
Now, as far as c++ is concerned vectors are a data structure, not algebraic objects and so none of the standard algebraic operations, like addition and dot product are defined in the standard library; there are packages that do this but there aren't part of the definition of c++ as the STL is. Here we define addition as a function on lines 6.1.55-64. We could have just written it as a function call add, or whatever; I have done something fancier, I have overloaded the + operator: this is called operator overloading. + is an function like any other, with int or double arguments it has been defined in the definition of the language, what is unusual is that, because it is so well known as an operator, it is represented with an operator notation, instead of +(a,b) we have a+b. It is possible to use the same notation for a function; in line 6.1.55 we have a function statement, but instead of a normal function name we have operator+ which means that this function defines a + operator. This is useful because it leads to readable code, provided v+w does what v+w should, it is easy to see what is happening in code including this addition. Later, when we see that c++ includes user defined datatypes, called classes and it is useful to be able to define operators, like +, = or == for these objects.
There is no matrix class in the definition of c++; however there are lots of excellent matrix classes defined in libraries available elsewhere and one thing that it is important note is that if you are writing code that involves finding eigenvectors or matrix inverses, it is far better to use a well-established library than write your own code. People have thought a lot about how to write efficient code for matrix operations.
If, however, you need matrices but don't need high-performance
linear algebra, the easiest thing to do is to consider matrices to be
vectors of vectors. A matrix of doubles can be declared
as vector<vector<double> > m; m.at(i)
will then be a vector<double>, a row of the
matrix; m.at(i).at(j) will be the jth entry of
the ith row, the
As an example we will look at a programme that multiplies a matrix by a vector. The programme has a few extra features, the first being that it takes a command line argument: the size of the matrix is given when you run the programme. Say the programme is compiled as mat and you want to run it with 5X5 matrices, then you would write ./mat 5. The syntax for doing this is quite obscure; first the main statement at line 6.2.15 reads int main(int argc, char *argv[]); so main has arguments in its brackets. The first argument argc counts how much is written after the name of the programme when it is being run; for some reason argc has the value one if there is nothing, two if there is one word, three if there is two and so on. The second argument in the main statement, argv[] actually stores these words with argv[1] referring to the first word. In line 6.2.25 this word is converted in to an integer: the words are being stored as c-style arrays of chars and atoi converts this to the corresponding numerical value. Finally, this procedure gives a segmentation error if there the programme is called with no argument; the conditional at lines 6.2.19-23 catches this and ends the programme more elegantly and more informatively. Again, the syntax here is not at all obvious and when I need it I usually just copy it from a previous programme.
The programme has a vector vectorV constructed at line 6.2.27 and the matrix matrixA at line 6.2.29. The vector is a vector of doubles in the usual way; the matrix is a vector of vectors of doubles. Both the matrix and the vector are constructed with random entries between -1 and 1; the vector constructor calls the function randVector defined at lines 6.2.50-66; basically this has a loop that goes around size times pushing a random number back on to the vector each time. There is also a randMatrix function for constructing the matrix with random entries at lines 6.2.63-72. Since the matrix is a vector of vectors, this function has a loop that goes around size times pushing a random vector back each time: the randMatrix.
1 #include<iostream>
2 #include<vector>
3 #include<cstdlib>
4 #include<string>
5
6 using namespace std;
7
8 void print(const vector<double> & v);
9 void print(const vector<vector<double> > & v);
10 vector<vector<double> > randMatrix(int size);
11 vector<double> randVector(int size);
12 double dotProduct(const vector<double> & a,const vector<double> & b);
13 vector<double> operator*(const vector<vector<double> > & a,const vector<double> & b);
14
15 int main(int argc, char *argv[])
16 {
17
18
19 if(argc==1)
20 {
21 cout<<"You need run this programme with an integer which gives the matrix size"<<endl;
22 return 0;
23 }
24
25 int vectorN=atoi(argv[1]);
26
27 vector<double> vectorV=randVector(vectorN);
28
29 vector<vector<double> > matrixA=randMatrix(vectorN);
30
31 cout<<"v=";
32 print(vectorV);
33
34 cout<<"A=\n";
35 print(matrixA);
36
37
38
39
40
41
42 cout<<"Av=\n";
43 print(matrixA*vectorV);
44
45 return 0;
46 }
47
48
49
50 vector<double> randVector(int size)
51 {
52
53 vector<double> v;
54
55 for(unsigned int i=0;i<size ;++i)
56 v.push_back(2*double(rand())/double(RAND_MAX)-1);
57
58 return v;
59 }
60
61
62
63 vector<vector<double> > randMatrix(int size)
64 {
65
66 vector<vector<double> > v;
67
68 for(unsigned int i=0;i<size ;++i)
69 v.push_back(randVector(size));
70
71 return v;
72 }
73
74 void print(const vector<double> & v)
75 {
76
77 cout<<"[";
78 for(unsigned int i=0;i<v.size() ;++i)
79 {
80 cout<<v.at(i);
81 if(i!=v.size()-1)
82 cout<<" ";
83 else
84 cout<<"]";
85 }
86
87 cout<<endl;
88
89 return;
90 }
91
92
93 void print(const vector<vector<double> > & v)
94 {
95
96
97 for(unsigned int i=0;i<v.size() ;++i)
98 {
99 for(unsigned int j=0;j<v.at(i).size() ;++j)
100 {
101 cout<<v.at(i).at(j);
102 if(j!=v.at(i).size()-1)
103 cout<<" ";
104 }
105 cout<<endl;
106 }
107
108 return;
109 }
110
111
112 vector<double> operator*(const vector<vector<double> > & a,const vector<double> & b)
113 {
114 vector<double> c;
115
116 for(unsigned int i=0;i<a.size() ;++i)
117 c.push_back(dotProduct(a.at(i),b));
118
119 return c;
120
121 }
122
123
124 double dotProduct(const vector<double> & a,const vector<double> & b)
125 {
126 double dot=0;
127
128 for(unsigned int i=0;i<a.size() ;++i)
129 dot+=a.at(i)*b.at(i);
130
131 return dot;
132 }
The matrix multiplication is quite straightforward; it overloads the * operator at lines 6.2.112-121; it uses the fact that ith entry of the product is a matrix by a vector is the dot product of the ith row with the vector. In the programme, the ith row is just the vector matrixA.at(i). Of course, one funny thing about creating matrices as a vector of vectors is that this the asymmetry, the matrix is a vector of rows and the rows have a very neat description as in matrixA.at(i); the columns are not so easily described. Below is a function which returns a column vector
6.3
1
2 vector<double> column(const vector<vector<double> > & a,unsigned int columnN)
3 {
4 vector<double> col;
5
6 for(unsigned int i=0;i<a.size() ;++i)
7 col.push_back(a.at(i).at(columnN));
8
9 return col;
10 }
It is often very useful that vectors allow us to access individual elements directly using at or square brackets. There are other data structures, like lists that do not allow this: conversely though, it is easy to add elements anywhere on a list whereas with a vector the only place a new element can easily be added is at the end using push_back. We will not be considering the other data structures here; they are all similar in that they store a list of some sort of data, but they differ in how this data is stored and accessed, as another example, a map is more general than a vector in that the index doesn't have to be an unsigned int starting at zero.
However, the statement above, that the elements of a list can't be accessed directly may seem a curious one, if the elements can't be answered directly how can they be accessed? What happens is that they can be accessed one-by-one in order using what is called an iterator. You can use an iterator for vectors too, they provide a more efficient way of going through the elements of a vector in order, as often happens in for loops, in the dotProduct function of MatrixVectorMult.cpp for example. Some algorithms for vectors also use iterators and so we will look at them briefly.
Iterators are a form of pointer and one reason for looking at iterators is that they give us an excuse for briefly considering pointers. Pointers can be quite complicated; we will only go through them briefly. The main idea behind a pointer is that it stores a memory location: it points to somewhere in the memory, this might seem like the references we mentioned earlier and, really, references and pointers are very similar, pointers can be thought of a more powerful and, in fact, more dangerous, form of reference and, in fact, in many compilers, references are converted in to pointers during compilation..
Here is a pointer example: the two important operators are the & operator which returns the memory location of a variable and the dereferencing operator * which returns the value at a memory location.
1 #include<iostream>
2 #include<string>
3
4 using namespace std;
5
6 int main()
7 {
8
9
10 int anInt=100;
11
12 int * pointer=&anInt;
13
14 cout<<"anInt="<<anInt<<endl;
15 cout<<"*pointer="<<*pointer<<endl;
16 cout<<"pointer="<<pointer<<endl;
17 cout<<"&anInt="<<&anInt<<endl;
18 cout<<"&pointer="<<&pointer<<endl;
19
20 int aNewInt=200;
21
22 pointer=&aNewInt;
23
24 cout<<"\n";
25
26
27 cout<<"aNewInt="<<aNewInt<<endl;
28 cout<<"*pointer="<<*pointer<<endl;
29 cout<<"pointer="<<pointer<<endl;
30 cout<<"&aNewInt="<<&aNewInt<<endl;
31 cout<<"&pointer="<<&pointer<<endl;
32
33 aNewInt=300;
34
35
36 cout<<"\n";
37
38 cout<<"aNewInt="<<aNewInt<<endl;
39 cout<<"*pointer="<<*pointer<<endl;
40 cout<<"pointer="<<pointer<<endl;
41 cout<<"&aNewInt="<<&aNewInt<<endl;
42
43 int ** pointer2Pointer=&pointer;
44
45 cout<<"&pointer2Pointer="<<&pointer2Pointer;
46 cout<<"pointer2Pointer="<<pointer2Pointer;
47 cout<<"*pointer2Pointer="<<*pointer2Pointer;
48 cout<<"**pointer2Pointer="<<**pointer2Pointer;
49
50
51
52 return 0;
53 }
Now an int is declared at line 6.3.10 and it is assigned the value 100. At line 6.3.12 a pointer to an int is declared using int *. This can hold the memory address of an int and here it is immediately assigned the memory address of anInt: again, anInt returns the value of the int it stores while &anInt returns the memory address of anInt. Thus pointer holds that address and when we output pointer at line 6.3.16 this will confirm that pointer holds the memory address of anInt, something that is printed out on the next line. pointer itself has a different address, this is printed out at line 6.3.18. In line 6.3.15 *pointer is printed out, the dereferenced pointer returns the value stored at pointer; pointer stores the location of anInt so *pointer returns the value stored at this address, which is 100.
The idea behind lines 6.3.20-31 is just to show the address stored by the pointer can be changed, as can the value stored at the address; this is illustrated in lines 6.3.33-41. Finally in lines 6.3.43-48 we have a pointer to a pointer: pointer2Pointer points to pointer, so, pointer2Pointer stores the address of pointer, *pointer2Pointer is the value at that address, the value stored in pointer; this, in turn, is the address of aNewInt. **pointer2Pointer is the same as *pointer and so it is the value stored in aNewInt, that is, 300.
Pointers can point to nearly any sort of variable. They can also be declared, using new so that they point to a newly allocated piece of memory which can then be assigned a value using the dereferenced pointer. Unlike the memory we have been discussing, using new allocated memory which is exclusive to the pointer, the pointer examples above give a pointer to memory which has already been allocated. In fact, allocating memory using new is useful and powerful, but subtle and slightly dangerous. We won't discuss it here, but would in a longer course.
An iterator is a pointer to an element in a container like a vector; it is not an ordinary pointer in that it has an increment, ++, operator so that incrementing moves it to the next element. Hence, if it points to v.at(3) for some vector v, then it++ will point to v.at(4) and, in fact, it-- will point to v.at(2). It is important to remember what a pointer does: if it points to v.at(3) that means it stores the address of v.at(3), to get the actual value v.at(3) the iterator needs to be dereferenced: *it.
Here is an iterator example
Iterator.cpp
6.4
1 #include<iostream>
2 #include<vector>
3 #include<algorithm>
4
5 using namespace std;
6
7 void print(vector<int> & v);
8
9 int main()
10 {
11
12 int someInts[]={12,3,45,6,7,28,8,4};
13
14 vector<int> v(someInts,someInts+8);
15
16 cout<<"v=";
17 print(v);
18
19 vector<int> w(v);
20
21 cout<<"sort first 4 entries\nv=";
22
23 sort(v.begin(),v.begin()+4);
24
25 print(v);
26
27 v=w;
28
29 cout<<"back again\nv=";
30
31 print(v);
32
33 cout<<"sort all entries\nv=";
34
35 sort(v.begin(),v.end());
36
37 print(v);
38
39 return 0;
40 }
41
42 //const won't work here
43 void print(vector<int> & v)
44 {
45
46 cout<<"[";
47 for(vector<int>::iterator it=v.begin();it!=v.end();it++)
48 {
49 cout<<*it;
50 if(it!=v.end()-1)
51 cout<<" ";
52 else
53 cout<<"]";
54 }
55
56 cout<<endl;
57
58 return;
59 }
The first thing to look at is the print function at lines 6.4.43-59; it illustrates the common use of an iterator in s for loop. In the for statement at line 6.4.47 an iterator is declared: it is an iterator for a vector of ints so the declaration is is vector<int>::iterator; basically this reads as the iterator scoped inside vector<int>. This iterator is initialized to v.begin(); an iterator value pointing to the first element in the v. v.end() is an iterator value that points beyond the end of the vector, in other words, if the iterator it is pointing to the last element in the vector then it++ is equal v.end(). Now, at line 6.4.49 the element of the vector is printed out; if it points to an element *it is the value of that element. Notice that the elements of the vector are not accessed by name, instead the iterator steps through them in order and iterators are used for lists and so on where there is no direct access to the elements.
The rest of the programme illustrates an example of an algorithm available for vectors; again, since vectors are a data structure, the algorithms are data algorithms, not linear algebra algorithms. To use the standard template library algorithms, we include the package at line 6.4.3. Now, first of all we construct a vector holding some integers; this is done in a way we haven't seen before: annoyingly there is no way of constructing a vector with a given set of elements: one method, of course, would be to construct an empty vector and push the elements back one by one. Hence to make a vector holding 12, 3 and 45
6.5
1 vector<int> v;
2 v.push_back(12);
3 v.push_back(3);
4 v.push_back(45);
A shorter, but more indirect method is used in the Iterator.cpp programme at lines 6.4.12/14. The annoying thing about this technique is that it uses the old c-style arrays; basically an array of ints is constructed at line 6.4.12 and this array is used to initialize the vector. The syntax is somewhat obscure, you need to tell the constructor the place to start on the array, someInts, and where to end: someInts+8. The main thing is that v then contains the integers 12, 3, 45, 6 and so on; the annoying thing is that to use this construction in anything but a cut-and-paste way relies on knowing about c-style arrays.
Having set up the vector v, we apply the sort algorithm to it; sort(it1,it2) sorts all the elements from the element it1 points to, to the element before the one it2 points to, [it1,it2) as it were. Hence, the sort on line 6.4.23 sorts the first four elements and the sort on line 6.4.35 sorts them all. Obviously we can make a vector of anything but the sort relies on there being an ordering, so it can only be applied to vectors of objects where the < operator is defined; for other datatypes, of course, this could be done by overloading; in fact, it is also possible to give an order as an argument to the sort function. This won't be discussed here, nor will the other algorithms or container methods, their description on the web is usually easy enough to follow when you understand that they often use iterators.
Exercises 6
Historically classes are what distinguishes c++ from c; c++ began as an extension of c which includes classes, now the difference is much greater and c++ is generally a more advanced language than its parent but it is hard these days to imagine programming large programmes in a language without classes. At the simplest classes play a similar role to functions in spliting the programming tasks up and in helping to keep the programme neat and easy to modify.
Classes are a user defined datatype. Think back to vectors, once you define a particular vector, what is called an instance of a vector, v say, then there are vector methods available like size so that v.size() returns the size of the vector, or at which returns the i element. With a class you define the methods that an instance of the class will have.
Here is a class called Bop stored in a file called Bop.cpp.
Bop.cpp
7.1
1 #include<string>
2 #include<iostream>
3
4 using namespace std;
5
6 class Bop
7 {
8 public:
9 Bop();
10 Bop(string word);
11 void speak();
12 int howMany(){return counter;}
13 void setHowMany(int counter){this->counter=counter;}
14 private:
15 string word;
16 int counter;
17 };
18
19 Bop::Bop()
20 {
21 word="bop";
22 counter=0;
23 }
24
25 Bop::Bop(string word)
26 {
27 this->word=word;
28 counter=0;
29 }
30
31 void Bop::speak()
32 {
33 cout<<word<<" ";
34 counter++;
35 }
This programme has no main statement and can't be run on its own, next we are going to write a programme which will include this one in much the same way as the standard packages are included. It is possible to compile the programme by writing g++ -c Bop.cpp, but compiling it won't produce a binary which can run: the -c tells the compiler not to expect a main statement and therefore not to try to produce a executable, in fact it produces something called an object or .o file, but for now the only point in compiling this file separately is to check that it is syntactically correct.
Before discussing how the class works, lets use it in a programme.
DoBop.cpp
7.2
1 #include<iostream>
2 #include<string>
3 #include<cstdlib>
4
5 #include"Bop.cpp"
6
7 using namespace std;
8
9 int main()
10 {
11
12 int loopN=100;
13
14 Bop bop1;
15 Bop bop2("bip");
16
17 for(unsigned int i=0;i<loopN ;++i)
18 if(rand()%2==0)
19 bop1.speak();
20 else
21 bop2.speak();
22
23 cout<<endl;
24
25 cout<<bop1.howMany()<<" Bops and "<<bop2.howMany()<<" Bips"<<endl;
26
27 }
First, notice that the file containing the class definition has been included at line 7.2.5; this is just like the earlier preprocessor commands including the packages iostream and so on, but here there is double quotes instead of angle brackets, basically this tells the preprocessor to look for the Bop.cpp programme in the current directory, rather than where ever it stores the packages. You might worry about the includes at the start of Bop.cpp, it looks like iostream and string are going to be included twice, in fact, the preprocessor is clever enough to deal with this and it is useful to have all the includes Bop.cpp needs in Bop.cpp so that it can be compiled separately.
Anyway the key lines are lines 7.2.14/15 where two instances of Bops are made, much the same way as we would make two ints or two vectors. The first isn't initialized, there is no bracket after bop1, the second is initialized with the word Bip. Back in the class definition, we have the class statement at the top in line 7.1.6, this says that a class called Bop is going to be defined. Inside the curly brackets are a list of all the methods and variables the class will have, some are private and can't be accessed from outside the class, some are public and can. The syntax is easy to get wrong, the class definition block starts with a curly bracket at line 7.1.7 and ends with a curly bracket followed by a semicolon at line 7.1.17, missing the semicolon can lead to very confusing errors. The words public and private are followed by colons.
In the Bop class there are two constructors, these give the code that is run when an a Bop is declared. As with other methods the constructors are prototyped in the class definition block but the actual code is given outside the block, so the prototype for the default constructor, the one with no argument, is at line 7.1.9 whereas the actual code is at lines 7.1.19-23. Notice that there is a Bop:: to indicate that this definition is for something in Bop. The other construct has an argument, a string: it is prototyped inside the class definition and, again, the actual code is given outside the definition with a Bop:: to indicate what is being defined.
In the actual programme, when bop1 is declared without being initialized at line 7.2.14 the default constructor is called and so the word inside bop1 is set to bop and counter to zero. The only subtly inside the constructor is the use of this->; basically there are two word, the one in the argument and the one declared at line 7.1.15 in the class definition. The one in the argument is the more local one, so if you write word it will refer to the word from the argument, this->word is the one from class definition. The only way to call the default constructor is to declare without initializing, surprisingly Bop bop1(); gives an error. At line 7.2.15 bop2 is declared and initialized using the other constructor, the one that takes a string as an argument, hence bop2 has its word set to bip, its counter is also set to zero.
The speak method is prototyped at line 7.1.11 and the actual definition is given at lines 7.1.31-35; it prints out word and advances counter by one. Apart from the constructors, all the methods have the same syntax as functions, they have a return type, a name and an argument list, the difference is that it is prototyped in the class definition and is defined with the Bop:: in front of the name. The difference between a function and a method is that a method belongs to the instance of the class, to the object, so line 7.2.19 is bop1.speak(), it calls bop1's speak method, so it will print out bop1's word and advances bop1's counter.
There is also a method for returning the value of the counter: howMany at line 7.1.12: it is defined in the class definition rather than being prototyped there and being defined later, this is because it only has a one line definition, it is possible to give all the definitions in the class definition, but this would make it harder to read what the class does, the usual thing is to have the definitions separate if they are more than one line long. There is also the method setHowMany defined for setting the counter, this isn't ever used in the programme, but reflects the way programmes with classes are often written, often we write the important classes first and give them the obvious methods: once the classes are written writing the programme itself is easy, but it may not actually use all the methods. Often, the same class with be reused in some later project.
Here is another example: it is a polynomial class which stores polynomials as a set of coefficients in the private vector called coefficients. One awkward thing about polynomials is that all polynomials have at least one coefficient since the zero polynomial is regarded as having constant coefficient zero. In the class, there are three constructors, but they are all designed to make sure coefficients is not empty; the default constructor at line 7.3.13, for example, gives a coefficients vector holding just the value zero and corresponds to the zero polynomial. Polynomials are slightly awkward to print out as well and a print method has been defined to handle this, even printing out x is awkward since you don't write the one in x^1; to make this a bit clearer printing out powers of x has be separated out in to a separate method xToI. However, there is no reason xToI would be needed from outside the class, so it is listed as private; this means that it can be called inside the class, for example, at lines 7.3.77/84 in the print method but f.XToI(i) called from the main programme will give an error.
Polynomial.cpp
7.3
1 #include<iostream>
2 #include<fstream>
3 #include<cmath>
4 #include<vector>
5 #include<string>
6 #include<cstdlib>
7
8 using namespace std;
9
10 class Polynomial
11 {
12 public:
13 Polynomial(){coefficients.push_back(0);}
14 Polynomial(vector<double> coefficients){this->coefficients=coefficients; if(coefficients.size()==0){coefficients.push_back(0);}}
15 Polynomial(string fileName);
16 double operator()(double x);
17 Polynomial differentiate();
18 int degree(){return coefficients.size()-1;}
19 void save(string fileName);
20 void print();
21 private:
22 vector<double> coefficients;
23 void xToI(int i);
24 };
25
26 Polynomial::Polynomial(string fileName)
27 {
28 ifstream coeffs;
29 coeffs.open(fileName.c_str());
30
31 while(!coeffs.eof())
32 {
33 double entry;
34 coeffs>>entry;
35 coefficients.push_back(entry);
36 }
37
38 coeffs.close();
39
40 }
41
42 double Polynomial::operator()(double x)
43 {
44
45 double fOfX=coefficients[0];
46
47 for(unsigned int i=1;i<coefficients.size();i++)
48 fOfX+=coefficients[i]*pow(x,i);
49
50 return fOfX;
51 }
52
53 Polynomial Polynomial::differentiate()
54 {
55 if(coefficients.size()==1)
56 {
57 Polynomial zero;
58 return zero;
59 }
60
61 vector<double> newCoeffs;
62
63 for(unsigned int i=1;i<coefficients.size() ;++i)
64 newCoeffs.push_back(i*coefficients[i]);
65
66 Polynomial newPoly(newCoeffs);
67
68 return newPoly;
69 }
70
71 void Polynomial::print()
72 {
73
74 cout<<coefficients[coefficients.size()-1];
75
76 if(coefficients.size()!=1)
77 xToI(coefficients.size()-1);
78
79
80 for(unsigned int i=coefficients.size()-2;i>0;--i)
81 if(coefficients[i]!=0)
82 {
83 cout<<"+"<<coefficients[i];
84 xToI(i);
85 }
86
87 if(coefficients[0]!=0)
88 cout<<"+"<<coefficients[0];
89
90 cout<<endl;
91
92 }
93
94
95 void Polynomial::save(string fileName)
96 {
97 ofstream file;
98 file.open(fileName.c_str());
99
100 for(vector<double>::iterator it=coefficients.begin();it!=coefficients.end() ;++it)
101 file<<*it<<endl;
102
103 file.close();
104 }
105
106 void Polynomial::xToI(int i)
107 {
108 if(i>1)
109 cout<<"x^"<<i;
110 else
111 cout<<"x";
112 }
One of the methods, differentiation at line 7.3.17 and lines 7.3.53-69, returns another Polynomial; this can be assigned to an instance of Polynomial in the main programme, ignoring for now how f is constructed, look at g below at line 7.4.20 in the DoPolynomial.cpp programme; a Polynomial is declared and assigned the value f.differentiate(). It should be noted that if the class contains pointers, copying it can cause problems and sometimes the assignment operator = needs to be overloaded, we have no pointers here so there is no problem.
One nice thing is that the class has a method overloading the () operator, this is done at line 7.3.16 and at line 7.3.42-51; you name the method operator() and then have an argument list as normal: the programme will then expect these arguments inside the bracket. What this means is that f(2), for example, is the polynomial evaluated at x=2.
DoPolynomial.cpp
7.4
1 #include<iostream>
2 #include<string>
3
4 #include "Polynomial.cpp"
5
6 using namespace std;
7
8 int main()
9 {
10
11 Polynomial f("fCoeffs");
12
13 cout<<"Degree of f="<<f.degree()<<endl;
14
15 cout<<"f(x)=";
16 f.print();
17
18 cout<<"f(2)="<<f(2)<<endl;;
19
20 Polynomial g=f.differentiate();
21
22 cout<<"g(x)=";
23 g.print();
24
25 }
The DoPolynomial.cpp programme uses a constructor that reads the coefficients in from a file. This constructor is prototyped at line 7.3.15 where we see it has one argument, a string, and it is defined at lines 7.3.26-40; using files also requires the fstream, for file stream, package is included, this happens at line 7.3.2. The syntax for dealing with files is very natural: at line 7.3.28 an ifstream, standing for input file stream, object called coeffs is declared. ifstream has a method called open which opens a file; the file is passed as a c-style char array, which is annoying, but the string class has a method which converts strings into these char arrays, this is what happens with fileName.c_str(): fileName is converted and passed to open which then opens the file with the name stored in fileName. This process can be made safe, but as written here the programme fails very badly if there is no file with that name: it hangs and seems to use lots of memory.
Inside the constructor there is a while loop at lines 7.3.31-36; this reads entries from the file one-by-one using a stream operator, much as for cin; coeffs>>entry; takes the next item in the file opened by the ifstream object coeffs and assigns it to entry. It does this until it reaches the end of the file; in coeffs.eof() the eof stands for end of file and this method returns true when the file opened by coeffs is finished: !coeff.eof() is true until the end of the file is reached. In the DoPolynomial.cpp example the constructor is called with the string fCoeffs so there should be a file in the same directory as the programme with this name. The stream operator is clever about taking the next non-white string, so it doesn't matter if the coefficients in the file are written in a column or a row; it isn't clever about spotting the end of the file so it is important that the file has no blank lines after the last data entry.
The input file could look like
fCoeffs
7.5
1 3 4 5 0 2
or
7.6
1 3
2 4
3 5
4 0
5 2
Outputting and inputting is quite complicated; the example described above and the one for outputting given at lines 7.3.95-104 only serve to illustrate a kind of simplest case scenario for doing file input and output; nonetheless copying these example will be enough for lots of applications.
The c++ language has only been introduced here; there is a lot more to do, classes can be built on classes for example and even compiling can be done in a more sophisticated way by splitting off the linking stage and using makefiles. However, it is hoped that the basics given here will be enough to make it easy enough to learn more by looking things up. Most importantly, however, the way to get good at programming is to programme.
Exercises 7
by Conor Houghton is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.