# Absolute Beginners C++

## Lesson 10 - Vectors

### 10.1 Vector of integers

 ```// ex10-1.cpp - vector of integers #include #include using namespace std; int main() {     // create a vector of 3 integers     vector 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
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 #include #include 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& table,double lo,double hi) {     int num=0;     for (int i=0;i 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 #include #include #include using namespace std; void listtable(vector& table,string title) {     cout << title << endl;     for (int i=0;i 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.

© 1999 Mark Huckvale University College London