## Lesson 10 - Vectors## 10.1 Vector of integers
arrays, since the
values are arrayed out in some space. Thus we could hold, for example,
a table of exam results for a student, where the first element of the table
is the result in English, the second element holds the result in Maths
and so on. The table might have a name, maybe the name of the student.
We could then generalise this across all students, by a 2-dimensional grid
of results in which the rows represented the students and the columns the
subjects. The name of such an object might be the name of the class.
In this example we create and use a simple list of numerical values, called 'list'. The declaration of 'list' shows us that is of type 'vector<int>': this means that list is not a single value but a one dimensional table of values called a 'vector'. Furthermore, inside this table, each value is just an integer. The declaration 'vector<int> list(3);', then also specifies that the name of the table is 'list' and that its initial size is 3 elements. Note that to use vectors we need to include the standard software component 'vector' at the top of the program. To access each element of the list, we use a square bracket notation: Where the name of the vector is suffixed with an integer expression inside '[' and ']'. This expression should evaluate to a number between 0 and one less than the length of the vector: that is, vector elements are indexed starting from 0 not from 1 (this is an endless cause of problems!). In the example, the elements are given values with assignment statements, and these are listed out using a 'for' loop to run from 0 to 2. The current length of a vector is always available through the method function 'size()', as you can see in the program. An extremely useful property of vectors is that their size can change dynamically in the program. In the example, the method function 'push_back()' is used to append a new value to the end of the vector. This function firsts extends the size of the vector to 4 elements, then stores the value specified in the new element. |
||

## 10.2 Vector of doubles
vector<double>
list(100,0);' creates a vector of 100 variables called list[0]
to list[99], and in addition initialises each of them to 0.
You see that the parameter list in the declaration of 'list' contains two
arguments: the first specifies the starting number of elements, the second
an initial value for those elements. If you do not specify an initial
value, then the initial values could be anything.
Once the list has been created, it is filled with 100 random numbers using a function called 'random()' which exploits the fact that the remainders after multiplication and division by prime numbers follow a pseudo-random sequence. The function then scales the random number and returns a value betwen 0.0 and 1.0. The random() function contains a 'static' variable, seed, which holds its value from one call to the next. The rest of the program tests the effctiveness of the random number generator to generate equal numbers of values in each interval of size 0.1 between 0.0 and 1.0. To do this it uses a function called 'countinrange()' to scan the list of numbers and report how many of the numbers can be found within the limits specified as arguments. It is in the declaration of this function that you can see the recommended method of passing a vector to a function. You will see that in the parameter definition for the function the vector is referred to as ' vector<double>&
table'. This says that the first argument to the function is a vector
of doubles, but furthermore that this vector should not be copied
when it is passed to the function. That is: when the vector 'list'
in the main program is passed to the function, the actual vector
is passed to the function, not a copy of the vector. This means that
if in 'countinrange()' we changed any of the elements of 'table' then we would
be changing the actual elements of 'list' in the main program.
It is the presence of '&' in the definition which causes this behaviour:
it overrides the default argument passing logic which takes copies of all
the arguments before passing them to a function. The copying of arguments
has not bothered us before, because we were only passing single values
to functions; but you can see it would be very wasteful to take a copy
of a 100 element vector. |
||

## 10.3 Vector of strings
vector<string>
list;' declares list to be a vector of strings, but since we have not
specified an initial length for the vector, it contains no elements.
An empty vector is still useful because we can always append to the end
of a vector with the push_back() method. We then input a series of
lines from the keyboard using the 'getline()' function that we have met
before. Here however, we do not want to use a sentinel value to end
the series of lines, but simply to stop when the list of lines is complete:
this is when the list has reached its EOF (End Of File marker). The
EOF is a special character that cannot be stored in a file or in lines
of text and which is used simply to signal the end of some file or some
text. On MS-DOS systems, the EOF character is 'ctrl/Z', i.e. the
character you get if you hold down the Ctrl key simultaneously with the
Z key. On Unix systems, the EOF character is 'ctrl/D'. Thus
the conditional expression '(!getline(cin,sval).eof())' both reads
in a line of text into sval and tests to see if the EOF character was typed;
you should read it as: 'not true that getline() finds EOF' with the
side effect that any text input gets put into sval. For each non-EOF
line, we append it to the list with push_back(). In the example,
we input three lines, so the vector list ends up of size 3 with list[0]="fred";
list[1]="bert"; list[2]="joe";. Once we have those list of strings
we can demonstrate the effect of two useful functions: one which can sort
the order of a vector and one that can randomise the order of a vector.
The function 'sort' (included in the standard component <algorithm>)
will sort any vector - not just strings, using the properties of the '<='
operator for comparisons: i.e. it will rearrange the contents of the vector
such that element [0] <= element[1] <= element[2], etc.
The sort() function takes two arguments indicating which part of the vector
needs sorting. For now we need to sort the whole vector, so we can
use the vector method functions begin() and end() to identify the beginning
and the end of the vector as the range of operation of sort. The
'random_shuffle()' function is clearly the opposite of sort! It changes
the ordering of a vector so that the elements are in no particular order.
You might try to think how the function achieves this without requiring
a temporary list or accidentally duplicating values. This example
has a function 'listtable' which prints the contents of the list so that
we can see the effect of sort() and random_shuffle(). Notice that
the vector is passed with the argument copying logic over-ridden with '&' as
we saw in ex10-2. |
||

## 10.4 Exercisesa. Write a program (namelist.cpp) that produces a list of names sorted by last name from an input which is a list of full names, as in:b. The prime number tester in example ex9-3 is inefficient in that it tries to divide by all numbers less than the square root of the number to be
tested, rather than just the prime numbers less than the square root of
the number. A more efficient way to generate a list of all prime numbers is
to store the primes in a vector as they are generated then use the list
so
far to test the primality of the next number. Write a program (prime.cpp)
which generates a list of all prime numbers less than 1000 and which builds
a vector of primes to minimise the amount of calculation. |

© 1999 Mark Huckvale University College London