Skip to main content

Welcome to Programming and Data Structures

Andrew Scholer

Section 14.4 Multidimensional Vector Traversals

When traversing a two dimensional structure, we typically work in row major order or column major order. A row major approach reads each row one at a time, processing all the elements in that row before moving on to the next row. A column major approach reads each column one at a time, processing all the elements in that column before moving on to the next column. These approaches can both be implemented with nested loops:
🔗
for each row in table {
  start row
  for each element in row {
      work with element
  }
  end row
}
Figure 14.4.1. Row Major Order
🔗
for each column in table {
  start column
  for each element in column {
      work with element
  }
  end column
}
Figure 14.4.2. Column Major Order
🔗
Sometimes it does not matter what strategy we use to traverse a two-dimensional vector. If we want to add up all the elements, either approach will work just fine. But other times, we will want to think about the data with the rows or columns in mind. For example, if we want to print out the table, we need to traverse it in row major order because output to the console needs to happen one line at a time:
🔗
for each row in table {
  for each element in row {
      print element + " "
  }
  print endline
}
On the other hand, if we want to add up the values in each column, we would need to process the data in column major order. An algorithm to do that might look like:
🔗
for each column in table {
  total = 0
  for each element in column {
      total = total + element
  }
  print total for column
}

Subsection 14.4.1 Range Based Approach

Range-based loops feel like a natural way to traverse a two-dimensional vector. The outer vector is essentially a list of rows. So we can say something like “for each row in the table” to process each row. Then, for that row, we can say “for each element in the row”. The sample below uses this approach to print out an entire table of numbers:
🔗
Listing 14.4.3.
🔗
Notice the type used for the first loop variable: const vector<int>&. We are iterating through each row of matrix and referring to it as row. That row is a vector of integers and we are making a reference to that. row is an alias for “the current row”.
🔗

Note 14.4.1.

If we changed like 15 to read for (vector<int> row : matrix), the code would work the same, but row would no longer be a reference. It would be a copy of the current row. Making a temporary copy of each row would be pretty wasteful.
🔗
🔗
Although this works, the row reference feels a little clumsy. More importantly, there is no way to modify it to traverse in column major order! A two-dimensional vector is essentially a list of rows and there is no way to easily talk about a particular column.
🔗
🔗

Subsection 14.4.2 Counting Loop Approach

Because of the limitations of range-based loops, we will prefer to use counting loops to iterate through the row and column indexes. Something like:
🔗
for rowIndex 0 to size-1 {
  start row # rowIndex
  for colIndex 0 to rowSize-1 {
      work with column # colIndex in row # rowIndex
  }
  end row # rowIndex
}
Here is that approach implemented. In it, we assume all rows have the same number of columns.
🔗
Listing 14.4.4.
🔗
Because the inner loop (columns) runs completely with each step of the outer loop (rows), line 24 ends accessing the elements of the matrix in this order:
🔗
matrix.at(0).at(0)  (start of first row)
matrix.at(0).at(1)
matrix.at(0).at(2)
matrix.at(0).at(3)  (done with inner loop)
matrix.at(1).at(0)  (start of new row)
matrix.at(1).at(1)
matrix.at(1).at(2)
matrix.at(1).at(3)  (done with inner loop)
matrix.at(2).at(0)  (start of new row)
...
This version is more flexible than the range-based approach. By switching the order of the two loops, we can iterate in column major order. Doing so will print out each column on a separate line of output:
🔗
Listing 14.4.5.
🔗
Note that all that is different about this version is that lines 21 and 23 (and the comments above them) have swapped places. We still specify the row first when accessing the matrix using matrix.at(row).at(col). But, since we count through all the possible rows before changing the column, we end up accessing elements in this order:
🔗
matrix.at(0).at(0)  (start of first col)
matrix.at(1).at(0)
matrix.at(2).at(0)  (done with inner loop)
matrix.at(0).at(1)  (start of new col)
matrix.at(1).at(1)
matrix.at(2).at(1)  (done with inner loop)
matrix.at(0).at(2)  (start of new col)
...

Insight 14.4.2.

The row index always goes in the first .at() and the column index always goes in the second .at(). Even if you are traversing in column major order.
🔗
These samples intentionally use row and col as the counters instead of i and j to make this clear. Although many programmers will use i and j for nested loop counters keeping track of if i is for rows or columns can be confusing.
🔗
🔗

Checkpoint 14.4.1.

Construct nested loops to set each element of a two-dimensional vector of strings called gridto be "?". Do the traversal in row major order.
🔗
You will not need all of the blocks.
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext