[Notes] Ch.20 More Data Structures (Runestone)

EXERCISE) Printing a Vector of int

Write a function that prints out the contents of a vector of int.

II. Vectors of Vectors 

1. Review: declaring the element type of a vector

 (1) Declare a vector like this: 

 => In addition to the base type of vector, provide the type of elements it will hold. 

(2) A vector can store elements of any type, as long as they match the type with which it is declared. 

2. Vectors of vectors 

(1) The element type for a vector can by anything, even another vector type. 

(2) This allows us to create nested vectors; 

 * On some compilers, the spaces is necessary to prevent confusion with the >> operator. 

 

3. Outer vector vs. Inner vector

EX)  What is the base type of this vector of vectors? 

A: int 

 

EX)  The outer vector in v2 has how many elements? 

A: 3

 

EX) The first inner vector in v2 has how many elements? 

A: 4

 

 

EX)  What is the base type of this vector of vectors? 

A: char

 

EX)  The outer vector in c2 has how many elements? 

A: 3

 

EX) The last inner vector in v2 has how many elements? 

A: 7

 

III. Indexing into a Vectors of Vectors

1. Indexing in a vector of vectors

(1) Indexing in a vector of vectors selects a vector. 

(2) To select an element from that vector, index again. 

2. Order of Indexing

(1) First, select the vector at index 2. 

(2) Then, from that vector, select the element at index 4. 

ex) someVectors [2][4]

 

3. Recall: Indexing out of bounds

(1) As with string, it’s possible to index off the end of a vector, which results in undefined behavior at runtime. 

(2) Basically, this goes to whatever memory happens to be next to the vector. 

• Maybe you got “lucky” and this memory wasn’t important. 
• Maybe you mess up another variable that happens to be there. 
• Maybe your program isn’t allowed to use that chunk of memory. -> This causes a crash called a segmentation fault. 
• Maybe it catches on fire. 

 

4. The at function

(1) Use the .at function rather than indexing with the square brackets. 

-> This contains an implicit check to make sure the index is valid. 

(2) The tradeoff is that at.function is slightly slower than []. 

5. Caution! 

(1) If you use indexing to select something and then assign it into a variable, you make a copy!

(2) vector<int> vec = somevectors

Indexing into a vector of vectors selects a vector. To select an element from that vector, index again. Like indexing into a single vector, you can use .at() to index, which checks that the index is valid but is slightly slower.

 

EX)  What is the value of v2[1]?

A: 42,42

 

EX)  What is the value of v2.at(0)? 

A: 5,2,23,8

 

EX)  What is the value of v2[0][1]?

A: 2

 

EX)  What is the value of v2[2][5]?

A: 13

 

EXERCISE) Printing a Vector of Vectors

 

 

{ 5 2 23 8 }

{ 42 42 }

{ 2 3 4 5 11 13 }

The first “row” in this representation corresponds to the vector in v2.at(0) (or v2[0] if you prefer to use the [] method)

The second “row” corresponds to the vector in v2.at(1) (or v2[1] ), and so on until all the data is printed. 

Write a function to print out a vector of vectors of int using this representation.

Complete the missing parts of the printVecOfVecs function. Compile the code using the -std=c++11 flag like this: 

g++ -std=c++11 printVectorOfVectors.cpp -o printVectorOfVectors

EX) Run the printVectorOfVectors program and enter what is printed to the terminal

A: 

IV. Building and Modifying Vectors of Vectors  

1. Building vectors of vectors

 (1) Use vector constructors:

(2) Use push_back/pop_back: 

2. Modifying vectors of vectors

 

* Always be mindful of whether an operation is being performed on the “outer” vector or one of the “inner” vectors. 

 

EX) Which diagram shows the contents of v2 after this code is run?

Answer: 

EXERCISE) Modifying Elements in a Vector of Vectors

For the questions below, consider the vector v2 shown in an initial state that we’ll call “State 1”.

We would like to change the contents of v2 to match “State 2”:

Arrange the lines of code below such that they would change v2 from “State 1” to “State 2”. 

Change “State 2” to “State 3”:

Arrange the lines of code below such that they would change v2 from “State 2” to “State 3”.

 

V. Uses for Vectors of Vectors  

1. Simulating a matrix

(1) Each vector represents a row. 

(2) Elements within represent different columns. 

2. Representing multiple sequences of data

(1) Vectors of Vectors do not have to be “rectangular” like matrices.

(2)  ex) measuring network latency. 

• We “ping” several different servers by sending 5 packets of information to each. We measure the time taken to receive a response for each packet. 

 

IV. Application: Analyzing Data in a Matrix

Write a program that reads in data to a matrix and then analyzes the data.The testData.txt file has some sample test data in it. Here is the contents of the file:

==========================

numRows 5

numCols 7

 

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31 32 33 34 35

==========================

 

IV. Application: Analyzing Data in a Matrix  - Designing the Program

1. Write a program: Analyze Data!

(1) Calculate:

• Sum of each row
• Sum of each column
• Sum of all data points

 

2. Analyzing data: Top-Down Design

(1) load the test data

• Open the test data file
• If it did not open correctly, display error message and end program
• Load in the test data and store in a vector of vectors (abstract into function loadDate)

(2) analyze data

• Calculate sum of each row (abstract into function sumOfRows)
• Calculate sum of each column (abstract into function sumOfCols)
• Calculate total sum (abstract into function sum)

(3) print result 

 

3. Recall: Check for errors opening a file

4. Pseudocode: main function

 

IV. Application: Analyzing Data in a Matrix  - Designing the Program - Writing the helper function

 

There are four helper functions that we need to write:

• loadData()
• sumOfRows()
• sumOfCols()
• sum()

1. Pseudocode: loadData helper function

2. Pseudocode: sumOfRows helper function

3. Pseudocode: sumOfCols helper function

4. Pseudocode: sum helper function

 

EXERCISE) A loadData Function

Complete the loadData function in the analyzeData.cpp file. 

Here is the pseudocode for the loadData function:

===============================================================

void loadData(vector of vectors, input stream from file) {

 

  get number of rows from vector of vectors

  get number of columns from vector of vectors

 

  make a temporary variable to store numbers in from >> operator

 

  loop on outer vector

    loop on inner vector

      read a number from input stream

      store that number in the correct element of the vec of vecs

    end of loop on inner vector

  end of loop on outer vector

}

===============================================================

EXERCISE) A sumOfRows Function

Complete the sumOfRows function in the analyzeData.cpp file. 

Here is the pseudocode for the sumOfRows function:

===============================================================

void sumOfRows(vector of vectors, vector) {

 

  traverse the outer vector to go through each row one by one

    traverse the inner vector

      use the "accumulator" pattern to find the sum of each row

    end of loop on inner vector

  end of loop on outer vector

}

===============================================================

 

 

EXERCISE) A sumOfCols Function

Complete the sumOfCols function in the analyzeData.cpp file. 

Here is the pseudocode for the sumOfCols function:

===============================================================

void sumOfCols(vector of vectors, vector) {

 

  traverse an inner vector to go through each column one by one

    traverse the outer vector

      use the "accumulator" pattern to find the sum of each column

    end of loop on outer vector

  end of loop on inner vector

}

===============================================================

 

EXERCISE) A sum Function

Complete the sum function in the analyzeData.cpp file. 

Here is the pseudocode for the sum function:

===============================================================

int sum(vector of vectors) {

 

  traverse the outer vector to go through each row one by one

    traverse the inner vector

      use the "accumulator" pattern to find the total sum

    end of loop on inner vector

  end of loop on outer vector

 

  return sum of all elements

}

===============================================================

EXERCISE) Analyzing the Data

Compile the code using the -std=c++11 flag like this:

g++ -std=c++11 analyzeData.cpp -o analyzeData

 

EX) Run the analyzeData program and fill in the boxes below based on what is printed to the terminal:

IX. Debugging the Program

To debug your program, you need to find where in the code things are not working correctly. Here are some ways to find the place(s) where your code’s behavior deviates from what you want it to do:

1. Use the printVecOfInts and printVecOfVecs helper functions to print out the values in your vectors and vectors of vectors at different points in your code. There is an example of this in the main function: the printVecOfVecs helper function is used to print out the values of the “matrix” so that we can check if what we read in matches what is in the text file. After you have verified the data, you can comment out these lines.
2. Use cout statements like, "This is the start of the sumOfRows function" to help you see how far your program gets before it crashes, throws an error, or otherwise stops working correctly.
3. Use cout statements that print out the value of the index variable in a for loop to help debug loops, especially nested loops.

If your code compiles and runs but then gets to a point where it “doesn’t seem to do anything”, then you might have one of these situations:

1. There is a stray cin statement somewhere and the program is “not doing anything” because it’s waiting for you to type something and hit enter. (Note: this particular program does not require user input via cin, so cin should not be anywhere in your finished program.)
2. There is an infinite loop somewhere. In this case, fall back on method #3 above to help you debug the loop.

X. Summary

1.We can create nested vectors, which are useful for storing matrix data. When working with a vector of vectors, make sure to keep track of whether you are working with the inner vector or the outer vector.

2. To index into a vector of vectors, you need to index twice - once for the inner vector and once for the outer vector. For example, vec[0][1] or vec.at(0).at(1).

3. Use a doubly-nested loop to print out a vector of vectors (or to iterate through a vector of vectors, more generally).

4. If we are representing a matrix with a vector of vectors, each vector represents a row. Elements within represent different columns.