Hunter Liu's Website

12. Week 6 Thursday: Vectors

Consider the following problem:

Sample Run: 
INPUT   3
INPUT   5.1 5.1 5.1 
OUTPUT  0 

INPUT   6
INPUT   1 2 3 4 5 6
OUTPUT  1.70783

When determining just the average of a list of numbers, there’s a way to do this “in parallel” to reading the user’s input. Set up a running sum, then add the inputs to the running sum as you recieve them; there’s no need to “remember” all the inputs.

In this problem, however, there is a mathematical barrier. To compute the standard devation, one needs to know the mean, and you can’t know the mean until the user has inputted all of the data! We therefore need a way to store the user’s input.

This is what vectors are for: the represent “lists” of variables that can be added to or deleted from.

We should first write some pseudocode to describe, in moderate detail, how to compute the standard deviation.

1. Ask the user for a positive integer input n.
2. Create a vector of doubles called inputs.
3. Repeat n times: ask the user for a number, then append it to inputs.
4. Compute the mean as follows:
   • Initialise a running sum to 0
   • For each double i in inputs, add i to the running sum.
   • The mean is the running sum divided by n.
5. Now compute the standard deviation as follows:
   • Initialise a running sum to 0
   • For each double i in inputs, add (i - mean) * (i - mean) to the running sum.
   • Divide the running sum by n, then take the squareroot to get the standard deviation.
6. Print the standard deviation to the screen.

Wow, that’s a lot of steps! This is one of the longer pieces of pseudocode we’ve written this quarter; directly writing this in C++ may be daunting and challenging. Having have written out these steps, however, we can simply translate them into code, step by step:

 1#include <cmath>        // needed for sqrt 
 2#include <iostream>     // needed for cin, cout, endl 
 3#include <vector>       // needed for vector 
 4
 5using namespace std; 
 6
 7int main() {
 8    // 1. take n as user input 
 9    int n; 
10    cin >> n; 
11
12    // 2. create a vector of user inputs 
13    vector<double> inputs; 
14
15    // 3. obtain n inputs from the user
16    for(int i = 0; i < n; i++) {
17        double input; 
18        cin >> input; 
19        inputs.push_back(input); 
20    }
21
22    // 4. compute the mean
23    double running_sum = 0; 
24    for(int i = 0; i < n; i++) {
25        running_sum += inputs.at(i); 
26    }
27    double mean = running_sum / n; 
28
29    // 5. compute the standard deviation. We'll reset the
30    // running sum to 0 and reuse the variable 
31    running_sum = 0; 
32    for(int i = 0; i < n; i++) {
33        running_sum += pow(inputs.at(i) - mean, 2); 
34    }
35    double std_dev = sqrt(running_sum / n); 
36
37    // 6. print out the result 
38    cout << std_dev << endl; 
39
40    return 0; 
41}

The key idea here is that we used a vector to “remember” all the numbers the user inputted. Note that we only need one vector variable as opposed to declaring a new variable for each user input! We then looked back at the user inputs, which we can access after the user already inputted, and computed our statistics.

Vectors, References, References to Vectors…

I have been using the word “remember” rather frequently when talking about vectors, and there are some very subtle interactions vectors have with memory that are important to think about.

Vectors occupy a contiguous chunk of memory in your computer. Consider the following snippet of code:

1vector<int> v = {1, 4, 7, 9}; 

The four integers in the vector are stored in neat boxes side-by-side in your computer, in order. Each of these boxes are treated as individual int variables (in this example), hence can be passed by value or passed by reference into functions. Consider the following snippet of code, for instance:

 1// squares a variable. 
 2void square(int& n) {
 3    n *= n; 
 4} 
 5
 6int main() {
 7    vector<int> v = {1, 3, 5}; 
 8    square(v.at(2)); 
 9    cout << v.at(2) << endl; 
10    return 0; 
11} 

This outputs 25: the changes made to n are reflected by v.at(2)!

As you add more and more elements to your vector, this block of memory it occupies gets longer and longer. However, your operating system will use pieces of memory from all over its RAM, and if you keep adding data to your vector ad infinitum, you’ll probably eventually run into a piece of memory that’s in use.

As long as you have enough memory on your computer, this does not cause any runtime errors. If you run out of memory, your computer will probably crash. This is classified as a “budget issue” in the professional world rather than a “runtime error”. This shifts the blame away from engineering teams.

The dudes at C++ thought of this long before we did: whenever a vector grows too long to fit in a contiguous block, C++ will automatically find a bigger, more open piece of memory and move the whole vector there, where it can grow and flourish with the other fauna and flora.

However, this very behaviour can cause unpredictable behaviour when mixed with references. Consider, for instance, the following code:

 1void foo(vector<int>& vec, int& n) {
 2    for(int i = 0; i < 1000000; i++) {
 3        vec.push_back(i); 
 4    }
 5
 6    cout << n << endl; 
 7} 
 8
 9int main() {
10    vector<int> v = { 1 }; 
11    foo(v, v.at(0)); 
12
13    return 0; 
14} 

The foo function adds a million numbers to the provided vector, then prints out the provided integer. On my computer, this usually prints out something that’s not 1.

This is because of this movement of memory phenomenon described earlier: the vector has moved, but the reference to its first element, n, has not. How the heck was n supposed to know that another variable has moved? In fact, every time I run this program, I get a different number. This is an example of undefined behaviour!

Note that your computer may still print out 1 — operating systems do not always “clean” reclaimed memory, and you may also just have enough memory to accommodate a million integers. Be very cautious when you’re using a reference to a vector’s contents.

Here’s a similar example:

 1void bar(vector<int>& vec, int& n) {
 2    vec.clear(); // empties the contents of vec. 
 3    cout << n << endl; 
 4} 
 5
 6int main() {
 7    vector<int> v = {1, 5, 8, 9}; 
 8    bar(v, v.at(3)); 
 9    return 0; 
10} 

Does this behave differently from the prior example? What does this suggest about removing elements from a vector?

Practise Problems

Here are some additional problems that you can use vectors to solve. Write a solution that does use vectors. Some of these problems can be solved without using vectors at all, usually by some kind of “parallelisation” like what we described above. Determine wich problems can be solved without vectors, then do so.

Sample Run: 
INPUT   5
INPUT   1 2 3 4 5 
OUTPUT  4 

INPUT   5
INPUT   4 4 4 5 5 
OUTPUT  4 

INPUT   1
INPUT   0
OUTPUT  0

Sample Run 
INPUT   1
INPUT   100
OUTPUT  158.22594

INPUT   3
INPUT   50 55 42
OUTPUT  77.53071

       *
       *
 *     **
 * **  ***
----------
0123456789