Lesson 10 - Vectors
10.1 Vector of integers
// ex10-1.cpp - vector of integers
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// create a vector of 3 integers
vector<int> list(3);
// assign them some values
list[0]=10; list[1]=20; list[2]=30;
// print out the values
int i;
for (i=0;i<3;i++)
cout << "list[" << i << "]=" << list[i] << endl;
// get the number of elements
cout << "list is of length " << list.size() << endl;
// extend the list by one more element
list.push_back(40);
// print out the values now
for (i=0;i<list.size();i++)
cout << "list[" << i << "]=" << list[i] << endl;
return(0);
}
|
ex10-1
list[0]=10
list[1]=20
list[2]=30
list is of length 3
list[0]=10
list[1]=20
list[2]=30
list[3]=40
|
Example ex10-1 introduces one method of dealing with tables of values in
C++. By a table, we mean a number of values referred to under one
name: it could be a list of numbers, or a two-dimensional grid. In
computer jargon these are often referred to as 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:
vector-name [ index-expression ]
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
// ex10-2.cpp - vector of doubles
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
// pseudo random number generator
double random()
{
static int seed=123456789;
int tmp_seed = 16807 * ( seed % 127773 ) -
2836 * (seed / 127773 );
if (tmp_seed >= 0)
seed = tmp_seed;
else
seed = tmp_seed + 2147483647;
return(seed/2147483648.0);
}
// count number of values between brackets
int countinrange(vector<double>& table,double lo,double hi)
{
int num=0;
for (int i=0;i<table.size();i++)
if ((lo <= table[i]) && (table[i] < hi))
num++;
return(num);
}
int main()
{
// create a vector of 100 doubles initialised to 0
vector<double> list(100,0);
// assign each a random value
for (int i=0;i<100;i++) list[i] = random();
// print out how many numbers in each tenth
for (double lo=0.0;lo+0.1 <= 1.0;lo=lo+0.1)
cout << "Number between " << setprecision(1)
<< setiosflags(ios::fixed)
<< lo << " and " << lo+0.1 << " = "
<< setw(2) << countinrange(list,lo,lo+0.1)
<< endl;
return(0);
}
|
ex10-2
Number between 0.0 and 0.1 = 14
Number between 0.1 and 0.2 = 10
Number between 0.2 and 0.3 = 11
Number between 0.3 and 0.4 = 8
Number between 0.4 and 0.5 = 10
Number between 0.5 and 0.6 = 8
Number between 0.6 and 0.7 = 6
Number between 0.7 and 0.8 = 12
Number between 0.8 and 0.9 = 13
Number between 0.9 and 1.0 = 8
|
There are two main new ideas presented in example ex10-2. Firstly
this example uses a vector of double variables rather than integer variables,
and secondly the example shows the recommended way of passing a vector
as an argument to a function. The declaration '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
// ex10-3.cpp - vector of strings
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
void listtable(vector<string>& table,string title)
{
cout << title << endl;
for (int i=0;i<table.size();i++)
cout << table[i] << endl;
}
int main()
{
// create an empty vector of strings
vector<string> list;
// read some lines from the keyboard
cout << "Enter some lines (end in EOF)" << endl;
string sval;
while (!getline(cin,sval).eof())
list.push_back(sval);
// list them back to the screen
listtable(list,"Entered:");
// sort them and list them
sort(list.begin(),list.end());
listtable(list,"Sorted:");
// randomise them and list them
random_shuffle(list.begin(),list.end());
listtable(list,"Randomised:");
return(0);
}
|
ex10-3
Enter some lines (end in EOF)
fred
bert
joe
^Z
Entered:
fred
bert
joe
Sorted:
bert
fred
joe
Randomised:
joe
bert
fred
|
Example ex10-3 introduces vectors of strings and demonstrates two useful
functions which can operate on vectors. The declaration '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 Exercises
a. 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:
namelist
Catherine Zeta Jones
Fred Bloggs
Khalid El Choukri
^Z
Bloggs, Fred
Choukri, Khalid El
Jones, Catherine Zeta
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. |
