Multidimensional Vector Traversals

Section 14.4 Multidimensional Vector Traversals

When traversing a two dimensional structure, we typically work in row major order or column major order. These terms refer to whether our first loop is processing rows or if it is processing columns.

🔗

Subsection 14.4.1 A first attempt

Range-based loops feel like a natural way to traverse a two-dimensional vector. The outer vector is what we consider to be the rows, so we can loop over those and for each one, loop over its elements. Say I want to print a table of numbers in its natural structure. I would want to do something like:

🔗

Listing 14.4.1.

🔗

for each row in table {
  for each element in row {
      print element
  }
  end line
}

In C++, that will look like this:

🔗

Listing 14.4.2.

🔗

Notice the type used for the first loop variable: const vector<int>& row. row is storing each element of matrix one at a time. And what matrix stores are vector<int>s. But we don’t want to copy those vectors into the variable row. That would be a waste of time. So we make row be a const reference to the current element. If we changed like 15 to read for (vector<int> row : matrix), the code would work, but it would be making copies of each row.

🔗

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.

🔗

Subsection 14.4.2 A better traversal

Our preferred way of looping over multidimensional arrays will be to use counting loops. For a row major traversal, our outer loop is based on the size of the top-level array - the number of rows. The inner loop is based on the number of columns, which is the length of one of the rows (assuming they all have the same length).

🔗

Listing 14.4.3.

🔗

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.4.

🔗

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)
...

Warning 14.4.1.

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 here, you are encouraged to use meaningful names to help keep track of which counter is for rows and which is for columns.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next