Homework 5

In class today we're going to build pieces of the homework together from scratch. I'm including the finished version here for those looking at this page later.

hw5.cpp

There are a bunch of different small details to learn from this. Try to compare it with your code and see which differences are important and which are not.

Vectors

Vectors are a great tool for storing multiple pieces of data. Each vector has a type, which is indicated by brackets.

Example: Creating an empty vector and storing data inside it

#include<iostream>
#include<vector>
using namespace std;

int main() {

    vector<int> vec;   // Creates an empty vector called vec

    vec.push_back(2);     // Adds 2 to the end of vec
                          // Since vec was empty, 2 becomes the first element

    vec.push_back(7);     // Adds 7 to the end of vec (7 is the second element)
    vec.push_back(13);    // Adds 13 to the end of vec

    /* At this point we have
       vec.at(0) is storing 2
       vec.at(1) is storing 7
       vec.at(2) is storing 13
       You can do anything with these numbers that you could do with a normal int
    */

    // Here we do some computation with our 3 numbers
    int x = vec.at(0)*vec.at(1) + vec.at(2);
    cout << "I calculated x. x = " << x << endl;

    // Here we change the values of our 3 numbers.
    vec.at(0) = 14;
    vec.at(1) = vec.at(2) - 4;
    vec.at(2) -= 5;
    // Here we print our 3 numbers to the screen.
    cout << "I changed my vector values to\n" << vec.at(0)
         << "\n" << vec.at(1) << "\n" << vec.at(2) << "\n";

    return 0;
}

Example: Creating a vector with a predetermined size.

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main() {

    vector<string> vec(4);   // Creates a vector of size 4 called vec
                          // At the beginning, all 4 strings will be empty

    cout << "I just created a vector with 4 strings. Here they are:\n"
         << vec.at(0) << "\n"
         << vec.at(1) << "\n"
         << vec.at(2) << "\n"
         << vec.at(3) << "\n";

    // As before, we can do anything with these numbers that we can
    // do with normal strings
    vec.at(0) = "Aluminium";
    vec.at(1) = vec.at(0) + "Turpentine";
    cout << "I did a little bit of modifications. Here's the edited vector:\n"
         << vec.at(0) << "\n"
         << vec.at(1) << "\n"
         << vec.at(2) << "\n"
         << vec.at(3) << "\n";

    // Check out the syntax here. vec.at(position).some_string_function();
    cout << "Look at the string in position 1. It contains "
         << vec.at(1).length() << " characters.\n"
    
    // We can also get the size of the vector. This
    //   is the number of elements stored int the vector.
    cout << "The size of my vector is " << vec.size() << "\n";
    
    return 0;
}

Example: Playing with the size of a vector

#include<iostream>
#include<vector>
using namespace std;

int main() {

    vector<int> vec(2);

    cout << "Size of vec is " << vec.size() << "\n";

    vec.push_back(2);
    vec.push_back(7);

    cout << "Size of vec is " << vec.size() << "\n";

    return 0;
}

Quality of life: A function to print vectors to the screen

Look at how much cout work we're doing in the above pieces of code. Writing all that out is pretty miserable. Instead we're going to define a function called printVec that will do the job of printing out the entries of our vector.

// Prototype of printVec
void printVec(const vector<int>& vec);

// Function definition for printVec
void printVec(const vector<int>& vec) {
    for(int i=0; i<vec.size(); i++)
        cout << vec.at(i) << " ";

    cout << "\n";
}

Important: Why do input our vector by constant reference? We talked about this earlier. We don't want to make copies of large chunks of data. This vector might contain 1000000 integers (we don't know beforehand), so passing by value would be pretty bad. As for the word "const", that's just good style. The function will not alter our vector, so let's indicate that by putting const next to the parameter.

Last Example: Removing elements from a vector

In this last example we're going to remove some elements from a vector. For now, we can only remove the last element (one at a time) using a function called pop_back. There is a different function called erase that can remove many elements at once, but it requires something called an iterator that we haven't learned about yet.

#include<iostream>
#include<vector>
using namespace std;

int main() {

    vector<int> vec;

    // Practice problem: What does this loop do?
    for(int i=0; i<5; i++)
        vec.push_back(i*2+1);
    
    cout << "My vector currently has " << vec.size() << " elements."
         << "\nHere they are:\n";
    printVec(vec);

    // Each time we pop_back, it removes the last element from the vector
    vec.pop_back();
    vec.pop_back();
    
    cout << "My vector currently has " << vec.size() << " elements."
         << "\nHere they are:\n";
    printVec(vec);
    
    return 0;
}

One possible error: Accessing memory out of bounds

What goes wrong in this code?

#include<iostream>
#include<vector>
using namespace std;

int main() {

    vector<int> vec;
    for(int i=0; i<5; i++)
        vec.push_back(i*2+1);
    
    cout << vec.at(5) << "\n";
    
    return 0;
}

Recap: Important Vector Syntax

For a full description of the vector class, see the //www.cplusplus.com/reference/vector/vector/">C++ page.

Here are the functions/operations associated with vectors that I think are the most important.

Constructor #1:
vector<TYPE> NAME; // Creates an empty vector called NAME that accepts variables of type TYPE.

Constructor #2:
vector<TYPE> NAME(NUMBER);  // Creates a vector with size NUMBER called NAME that accepts variables of type TYPE.
            // Be careful: your vector will have size NUMBER, but the variables inside will be uninitialized.

Once you have created your vector:
(1) myVector.push_back(someVariable)
    Adds the element someVariable to the end of myVector.
(2) myVector.at(i)
    Returns the ith element inside myVector.
    Note1: Numbering always starts at 0. So myVector.at(0) is the first element in the vector.
        myVector.at(myVector.size()-1) is the last element in the vector.
    Note2: The compiler won't stop you from putting in bad values for i. Be careful!
(3) myVector.size()
    Returns the number of elements in myVector.
(4) myVector.pop_back()
    Returns the last element in myVector and removes that element from the vector.

A Practice Problem

The basic idea of vectors is simple: store a bunch of data in one neat package. But working with vectors takes some practice. It's very important to be good at writing loops, since most problems will involve performing some action on each individual vector element.

Problem

Write a program that allows the user to input as many integers as they would like (via cin). Create a vector that stores each of these integers. After the user is finished with inputs, cout the sum of the integers to the screen.

(we could calculate the sum without using a vector at all, but we're doing it this way for practice)

  Example input/output:

  Please input an int: 5
  Would you like to input another int? (y/n): y
  Please input an int: -1
  Would you like to input another int? (y/n): y
  Please input an int: 2
  Would you like to input another int? (y/n): y
  Please input an int: -5
  Would you like to input another int? (y/n): y
  Please input an int: 3
  Would you like to input another int? (y/n): n

  The sum of your integers is 4

Vector size versus vector capacity

We've already introduced the concept of the size of a vector. This is the number of pieces of data that are currently stored in your vector. There is a related concept called vector capacity. Here's how it works:

Inside your computer memory, there is some space reserved to store the elements of your vector. The amount of reserved space is called the capacity of the vector. It is always at least equal to the size of the vector (there is enough room to store each vector element), but sometimes the capacity is larger (there is enough room for a few more elements).

Example: Size vs. Capacity

#include<iostream>
#include<vector>
using namespace std;

int main() {

    vector<int> vec(5);
    for(int i=0; i<5; i++)
        vec.at(i) = i;

    // Here we expect to see size and capacity are both 5
    cout << "My vector has size " << vec.size() << " and capacity "
         << vec.capacity() << "\n";

    vec.pop_back();
    vec.pop_back();

    // Here we removed 2 elements from our vector, so the size is 3.
    // However, your vector still has reserved 5 spaces in the computer memory
    //   so we expect the capacity to be 5.
    cout << "After some edits, my vector has size " << vec.size()
         << " and capacity " << vec.capacity() << "\n";
    
    return 0;
}

We can directly manage the size of a vector (there is a function called resize that lets us do exactly that), but the capacity is managed automatically.

The vector class is smart enough to guarantee that the capacity will always be large enough to store all the elements of your vector. But it's possible that the capacity will be larger. Later we will learn about arrays, where we will manually set both the capacity and the size of the container.

Example#2: It's hard to predict capacity

In this example, we create an empty vector, then use push_back to fill it with elements. At the end we'll see that the vector size is exactly what we expected, but the capacity won't be easily predictable.

#include<iostream>
#include<vector>
using namespace std;

int main() {

    // Try this code with different values of VEC_SIZE
    const int VEC_SIZE = 50;
    vector<int> vec;
        
    for(int i=0; i<VEC_SIZE; i++)
        vec.push_back(i);

    cout << "My vector has size " << vec.size() << " and capacity "
         << vec.capacity() << "\n";
    
    return 0;
}

A very short explanation of why it works this way: The process of reserving new space in memory takes a while, so c++ likes to reserve big chunks all at once rather than reserving one new space at a time.