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