Schedule‎ > ‎

09B: Arrays, Array Algorithms and Vectors

Questions, Answers and Review

  • Questions from last class? 
  • Questions about homework?

Vector Declaration and Initialization

This code demonstrates several method of declaration and initialization of vectors.  It assumes you understand the material in 9A.  Copy the code into the Arduino IDE,  run it with autoscroll off and step through each section of code.

void printVector(vector<int> &myVect)  {
  cout << "in printVector" << endl;
  for (int i = 0; i < myVect.size(); i++) {
    cout << myVect[i] << " ";
  }
  cout << endl;
}

void loop() {
  /*    Experiments with no size on vector declaration    */
  vector<int> myIntegers;
  cout << "Printing myIntegers with no size on decl: size is  " << myIntegers.size() << endl;
  printVector(myIntegers);
  myIntegers.push_back(3);
  myIntegers.push_back(5);
  myIntegers.push_back(7);
  cout << "Printing myIntegers with no size on decl after 3 push_backs: size is  " << myIntegers.size() << endl;
  printVector(myIntegers);

  /***********************************************************/
  /*     Experiments with size on vector declaration         */
  vector<int> myNewVector(3);    //puts 0 in each of 3 elements
  cout << "printing myNewVector(3)after decl: size is  " << myNewVector.size() << endl;
  printVector(myNewVector);
  myNewVector.push_back(99);
  myNewVector.push_back(100);
  myNewVector.push_back(200);
  cout << "printing myNewVector(3)after 3 push_backs: size is  " << myNewVector.size() << endl;
  printVector(myNewVector);
  myNewVector[0] = 1;
  myNewVector[1] = 10;
  myNewVector[2] = 20;
  myNewVector[3] = 30;   //can I do this?  yes!
  myNewVector[8] = 50;   //can I do this?  No!  exceeds current size of vector CAN'T ALTER SIZE WITH ASSIGNMENT
  cout << "printing myNewVector(3) after 5 assignments: size is  " << myNewVector.size() << endl;
  printVector(myNewVector);

  /**************************************************************/
  /*   Experiments with initialization of vecors                */
  vector<int> myInitVector = {31, 32, 33, 34};  //only with C++11
  cout << "printing myInitVector after decl+init: size is " << myInitVector.size() << endl;
  printVector(myInitVector);
  vector<int> myInitVector2(5,9);  //puts 9 in each of 5 elements
  cout << "printing myInitVector2 after decl+init(5,9): size is " << myInitVector2.size() << endl;
  printVector(myInitVector2);

  delay(5000);
}

Arrays and Algorithms

Arrays store data. Analyzing data can provide your program with useful information. For that you need an algorithm. 

Learner Outcomes

  • Define an algorithm
  • Use an algorithm to analyze data
  • Use loops and arrays

Algorithms

From Wikipedia:
    "In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing and automated reasoning."

All programs are self-contained step-by-step operations. That makes all programs algorithms, though not necessarily very interesting ones. A program is often called an algorithm when it does some form of computation.

Summing Numbers

Let's look at an algorithm that takes the sum of a sequence of numbers:

1 + 2 + 3 + ... + n = ??

How would we solve this with a program? We have to divide the work into steps. In each step we'll add one number. The table below shows the running total at each step:

 Step Number Total
 1 1 1
 2 2 3
 3 3 6
 4 4 10
 5 5 15
 6 6 21

After six steps we come to the total of 21

Try It: Calculating a Summation

Start with the code below and write a program that implements the algorithm above. 

long total = 0;
for (int i=0; i<6; i++) {
   /* your code here */
}
  • Do you get the same answer? Why or why not? 
  • How many steps did your program take?
    • Could you do it in fewer steps? 

Using Real Data

Of course, you don't need an algorithm to sum number in series, there's a formula that can do it. What if you had an array of unpredictable numbers (like numbers you read from an analog input)? You have to do that using the loop above. Build the light sensor circuit shown on the right. Use the code below to get started:

const int SENSOR_PIN = 0; 
const int NUM_READINGS = 16; 

void setup() {
  Serial.begin(9600);
  analogReference(DEFAULT);
}

void getLight(int data[], int len) {
  for (int i=0; i<len; i++) {
    data[i] = analogRead(SENSOR_PIN);
    delay(100);
  }
}

void loop() {
  int readings[NUM_READINGS]; 
  getLight(readings, NUM_READINGS);

  // Print readings and compute average here

  delay(1000);
}

Exercise 1: Summing Sensor Data (15 minutes) - Averaging.ino

Update the code above to take the average reading after getLight call. 
  • Print each reading
  • Print the running total
  • Print the average once you're done.
  • Don't submit it yet.  Save it as Averaging.ino

Mathematical Analysis

Taking the average of repeated readings reduces the effect of noise on your readings and is an important algorithm for making the most out of sensor data. The more samples you take the more stable the average will be. What if you wanted to also understand now noisy your samples are? You could take the maximum and the minimum values and compare them. The farther apart the max and min are the more noisy your samples are. The table below shows a step-by-step algorithm for determining the maximum and minimum values of a set of numbers. 

 Step Input Max Min
 1 23 23 23
 2 34 34 23
 3 86 86 23
 4 6 86 6
 5 678 678 6
 6 67 678 6
 7 78 678 6
 8 2 678 2
 9 35 678 2

Exercise 2: Average and Difference (15 minutes)

Update your Averaging.ino program from Exercise 1 to calculate the maximum and minimum values over one sample set.  Save it as MaxMin.ino
  • Print the average
  • Print the difference between the maximum and minimum values.
  • Submit MaxMin.ino on Canvas

Mutants: Changing Vectors

You've seen maximum and minimum values before. In the above programs you took the array that was given to you as constant. What if you had an algorithm that changed the array? In programming changing an array or vector is call mutating it. In this section we're going to switch from arrays to vectors. Why? Because arrays are very difficult to mutate and vectors are easy.

Using the same circuit from earlier start with this code:

#include <ArduinoSTL.h>
using namespace std;

static int SENSOR_PIN = 0; 
static int NUM_READINGS = 16; 

void setup() {
  Serial.begin(9600);
  analogReference(DEFAULT);
}

void getLight(vector<int> &data, int len) {
  for (int i=0; i<len; i++) {
    data.push_back(analogRead(SENSOR_PIN));
    delay(100);
  }
}

void loop() {
  vector<int> readings;
  getLight(readings,NUM_READINGS);

  delay(1000);
}

This is basically the same as the starter code above except using vectors. 

Try It: Substituting a Vector

In the previous exercise you added your code between getLight() and delay(1000). Copy and paste your code from the array example to the vector example and compile it. 
  • Does your old code still work? 
  • If not, what's wrong?
If your code is like mine, the exact same code worked for both vectors and arrays. This is because an amazing and controversial thing in C++ called Operator Overloading. That's a topic for another day. Today we're learning about changing values in your vector. 

Modifying a Vector

There are two kinds of functions that modify vectors: Simple functions and ones that use Iterators. The simple operations are push_back(), pop_back() and clear(). The table below shows an example of what happens to a vector after each operation. 

Operation push_back(1) push_back(3) push_back(7) pop_back() push_back(9) clear() push_back(4) push_back(6)
 vect[0] 1 1 1 1 1  4 4
 vect[1]  3 3 3 3   6
 vect[2]   7  9   
 vect[3]        

There are two operators insert() and erase() that put a value into or take a value out of the middle of the vector. Shifting the remaining contents over. The table below shows an example of using the insert and erase functions. 

Operation push_back(1) push_back(3)insert(1,10) insert(0,5)erase(1)erase(0)insert(1,7)clear()
 vect[0]1115 51010
 vect[1] 3101 1037 
 vect[2]  310 3 3 
 vect[3]   3   
 


There's a catch. I have shown insert() and erase() taking an integer that says what position to put or delete. Unfortunately C++ doesn't make it quite that easy. The insert() and erase() functions take an Iterator as their first argument. There's a hack that makes it easy for beginners to insert and remove items from a vector. You can insert an item at position pos with the following statement:

my_vector.insert( my_vector.begin() + pos, item );

You can delete an item at position pos with the following statement:

my_vector.erase( my_vector.begin() + pos );


There's more information about vectors in the "In Depth" section at the end of this lesson. 

Exercise 3: Vector Max (20 min)

What if you wanted to remove the maximum value from your set of samples? Starting with the code above add a function that finds and returns the position of the maximum value in your vector. It should look something like this:

int findMaxPosition(vector<int> &data) {
    for (int i=0; i<data.size(); i++) {
        ...
    }
}

Remember: You should return the location of the maximum value, not the value itself. In the case of a tie you can return the position of any of the highest values. 
  • After you calculate the position of the highest value delete it from your vector
  • Print out the vector before and after the deletion
  • Calculate the average before and after the deletion
  • Submit FindMax.ino on Canvas

Inserting in Order

In the next class we're going to discuss how to sort the values inside of a vector. That topic will show you how to take an unsorted vector and make it a sorted vector. Today you'll learn how to perform Insertion Sort. Insertion Sort is when you insert a new number in the place where it belongs, just like placing a file in a filing cabinet. Here's an illustration of how Insertion Sort works:

 New Value DecisionAction  Original Vector Contents New Vector Contents 
 5 Hit the end of the vector push_back(5) { } { 5 }
 4 (4 < 5)? Yes insert(0, 4) { 5 } { 4, 5 }
 7 (7 < 4)? No  { 4, 5 } { 4, 5 } 
  (7 < 5)? No  { 4, 5 } { 4, 5 } 
  Hit the end of the vector push_back(7) { 4, 5 } { 4, 5, 7 } 
 6  (6 < 4)? No  { 4, 5, 7 } { 4, 5, 7 }
  (6 < 5)? No  { 4, 5, 7 } { 4, 5, 7 }
  (6 < 7)? Yes insert(2, 6) { 4, 5, 7 } { 4, 5, 6, 7 }
 5 (5 < 4)? No  { 4, 5, 6, 7 } { 4, 5, 6, 7 }
  (5 < 5)? No  { 4, 5, 6, 7 } { 4, 5, 6, 7 }
  (5 < 6)? Yes insert(2, 5) { 4, 5, 6, 7 } { 4, 5, 5, 6, 7 }

Notice the the number 5 is inserted the second time the list stays in order with 5 inserted twice. 

Check Yourself:

  1. If my_vector.size() returns x, what argument would you give to erase() to remove the last value?
  2. If I execute my_vector.insert(5,6) what is the value of my_vector[5]?
  3. Write a form of insert() that is exactly the same as push_back() 
    1. Hint: use size();

Exercise 4: Insertion Sort

Start with the following code:

#include <ArduinoSTL.h>
using namespace std;

static int SENSOR_PIN = 0; 
static int NUM_READINGS = 16; 

void setup() {
  Serial.begin(9600);
  analogReference(DEFAULT);
}

void insertionSort(vector<int> &data, int newValue) {

    /* algorithm here */

}

void loop() {
  vector<int> readings;
  for (int i=0; i<NUM_READINGS; i++) {
    insertionSort(readings, analogRead(SENSOR_PIN));
    delay(100);
  }

  cout << "Sorted readings: " << endl;
  for (int i = 0; i < NUM_READINGS; i++) {
    cout << readings[i] << " ";
  }
  cout << endl;

  delay(1000);
}

Your code should implement the algorithm above to insert values into the vector. At the end the vector should be sorted. Print the contents of the vector to be sure you got it right.

Here is some pseudocode for your insertionSort function.  (You do not have to use this pseudocode if you have another way you'd like to implement it):

void insertionSort(vector <int> data, int newValue),  {
   Loop while not done (starting at index 0):
        if newValue < data[i]
            insert newValue into index i of data vector
            set done = true
        else
            i++;
            check if i is at the end of vector,  if so set done = true
   End while loop
   If you got to end of vector without inserting newValue, push it onto the back of the vector.
}
  

Submit your code in a file called insertionSort.ino to Canvas. 

In Depth: Iterators 

An Iterator is a machine for walking through a vector one element at time. Here's one way to walk through a vector:

vector<int> vect;
...
for (int i=0; i<vect.size(); i++) {
    cout << v[i];
}

That is not the preferred way to walk over a vector. This is:

vector<int> vect;
...
vector<int>::iterator it;
for (it = vect.begin(); it != vect.end(); it++) {
  cout << *it;
}

Ugly, yes. But effective. There're a few things worth explaining: 
  • The type of the iterator depends on the type of the vector:
    • A vector<int> has an iterator of type vector<int>::iterator
    • A vector<char> has an iterator of type vector<char>::iterator 
  • vect.begin() and vect.end() are ways to say "the beginning iterator" and the "end iterator"
    • When an iterator is equal to vect.end() the iterator has finished walking the vector
  • The ++ operator moves an iterator from one element to the next
  • Placing a star ('*') in front of the iterator gets the element that the iterator is on. 
Why does C++ make you do this? Using iterators is a compromise between ease for the programmer and performance. This is what the insertionSort() function would look like if it used an iterator rather than the [] syntax:

void insertionSort(vector<int> &data, int value) {
  vector<int>::iterator it = data.begin();
  while ( it != data.end() && *it < value ) {
    it++;
  }
  data.insert(it, value);
}
 
Despite the complicated syntax the function is clean and compact. You will not be tested on the use of iterators in this class, but if you want practice using them try implementing functions that find and remove the minimum and maximum values in your vector using iterators.

Summary

  • Algorithms are step-by-step procedures that do something with data 
  • Algorithms make it possible to do interesting things with computers
  • Vectors are better than arrays when you want to change their contents at run time
  • Vectors support the following mutators
    • Clearing the contents of the vector
    • Adding and removing the last element
    • Inserting and erasing an element at any position