Home‎ > ‎CS 11M‎ > ‎

Vector Algorithms

Questions, Answers and Review

  • Questions from last class? 
  • Questions about homework?

Vectors and Algorithms

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

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

Using Sensor Data

In last week's assignment you:
  • Read sensor data
  • Sorted the readings
  • Used the sorted list to find
    • The maximum value
    • The minimum value
    • The median value

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.

Sorting a Vector

Sorting a vector is easy. But, you need to understand the iterator syntax. There's a special way to access the first and last elements of a vector:

  vector<int> v; 
  // insert some stuff here...
  cout << "The first element: " << *v.begin() << endl;
  cout << "The last element: " << *v.end() << endl;

The sort function in the standard library takes a vector as input and lets you partially sort a vector. If you want to sort the whole thing you tell the function to sort from the beginning to the end:

  vector<int> v; 
  // insert some stuff here...
  sort(v.begin(), v.end());
  cout << "The first element: " << *v.begin() << endl;
  cout << "The last element: " << *v.end() << endl;

Exercise 1: Average and Median 

In the assignment you implemented sort. That wasn't necessary because the standard library already implements sort on vectors. Start this exercise with the following code:

#include <ArduinoSTL.h>

using namespace std; 

const int lightSensor = A0; 

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

void loop() {
  cout << "Enter how many samples to take for calibration." << endl;
  int sampleCount; 
  cin >> sampleCount; 

  // Get samples from the light sensor...
  vector<int> samples; 
  for (int i=0; i<sampleCount; i++) {
    samples.push_back(analogRead(lightSensor));
    delay(100);
  }

  // Sort the samples that were retrieved...
  sort(samples.begin(), samples.end());

  // Calculate the average and differences here

  // Print the information about the samples...
  cout << "There are " << samples.size() << " samples." << endl;
  cout << "The minimum sample is: " << samples[0] << endl;
  cout << "The maximum sample is: " << samples[samples.size()-1] << endl;
  cout << "The median sample is: " << samples[samples.size()/2] << endl;
}

Requirements

Update your program to calculate the following: 
  • Save you sketch as vector_analysis.ino
  • The average sample value
  • The difference between the average and the median 
  • The difference between the minimum and maximum value. 

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] 1 1 1 5  5 10 10
 vect[1]   3 10 1  10 3 7  
 vect[2]     3 10  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. You have seen the two built-in iterators:
  • vect.begin() - The first element in the vector
  • vect.end() - The last element in the vector
You can make a vector to any element in a vector by simply adding an integer to the begin:

  cout << "The first element: " << *v.begin() << endl;
  vector<int>::iterator secondElement  = v.begin() + 1;
  cout << "The second element: " << *secondElement << endl;

You can also find the second to last element the same way: 

  cout << "The last element: " << *v.end() << endl;
  vector<int>::iterator secondToLastElement  = v.end() - 1;
  cout << "The second to last element: " << *secondToLastElement << endl;

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: 

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

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

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

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

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 sorted insertion. Sorted insertion 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 sorted insertion works: 

 New Value  Decision Action   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 }
 5s  (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() return 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 2: Sorted Insertion 

In this exercise you will implement your own version of insert that ensures a vector never needs to be sorted. 
Requirements
  • Start with the code form Exercise 1
  • Name this exercise sorted_insert.ino
  • Add a function with the following signature:

    void sortedInsert( vector<int> &vect, int pos )

  • When you get new samples from the light sensor insert them with sortedInsert() instead of push_back()

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: 

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

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

  for (vector<int>::iterator it = vect.begin(); it != vect.end(); it++) {
    cout << *it << endl;
  }
    
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 sortedInsert() function would look like if it used an iterator rather than the [] syntax:

void sortedInsert(vector<int> &vect, int value) {
  vector<int>::iterator it = vect.begin();
  while ( it != vect.end() && *it < value ) {
    it++;
  }
  vect.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.

The Automatic for Loop

There is one more form of the for loop worth explaining. This for loop is the same as the ones in earlier in this section. It simply steps through each element in the vector: 

  for (int value : vect) {
    cout << value << endl;
  }

Very nice! It's clean, compact and easy to read. There's just one thing. You have to remember what type of vector you're working on. But, C++ already knows what type of vector vect is. So, the compiler will allow you to use the auto datatype. That is a symbolic data type that tells the compiler to figure out what data type you mean when it can. Here's the for loop updated to use the auto datatype: 

  for (auto value : vect) {
    cout << value << endl;
  }

There's a general for loop that works on all vectors. The downside of this syntax is that you don't have a way to modify the vector. Therefore you couldn't use it for your sortedInsert() function. 

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 
Comments